22计算机科学导论之二

第二讲∶计算机科学的内容计算学科的根本问题三个学科形态主要领域基本问题典型问题示例计算机科学的根本问题计算机科学与计算科学定义：计算学科是对描述和变换信息的算法过程，包括对其理论分析、设计、效率实现和应用等进行的系统研究。计算学科的根本问题计算学科的根本问题是什么能被有效地自动进行。计算学科中的3个学科形态抽象形态学科中的抽象形态包含着学科中所具有的科学概念、科学符号和思想模型。按客观现象的研究过程，抽象形态包括以下4个步骤的内容：1）形成假设2）建造模型并作出预测3）设计实验并收集数据4）对结果进行分析计算学科中的3个学科形态理论形态理论是经过实践检验的系统化了的科学知识体系，由科学概念、科学原理以及对这些概念原理的理论论证所组成的体系。在计算学科中，理论形态包括以下4个步骤的内容：1）表述研究对象的特征定义和公理2）假设对象之间的基本性质和对象之间可能存在的关系定理3）确定这些关系是否为真证明4）结论计算学科中的3个学科形态设计形态设计形态具有较强的实践性，社会性和综合性。在计算学科中，从为解决某个问题而实现系统或装置的过程来看，设计形态包括以下4个步骤的内容：1）需求分析2）建立规格说明3）设计并实现该系统4）对系统进行测试与分析计算学科中的3个学科形态三种形态关系设计、抽象和理论3个形态针对具体的研究领域均起作用，在具体研究中，就是要在其理论的指导下，运用其抽象工具进行各种设计工作，最终的成果将是计算机的软硬件系统及其相关资料。抽象源于现实世界理论源于数学设计源于工程计算机学科各主领域的基本问题离散结构主要内容：包括集合论、数理逻辑、近世代数、图论、以及组合数学等。计算机学科各主领域的基本问题程序设计基础1）主要内容：包括程序设计结构、算法、问题求解和数据结构等2）基本问题主要包括：对给定的问题，如何进行有效的描述并给出算法？如何正确选择数据结构？如何进行设计、编码、测试和调试程序？计算机学科各主领域的基本问题算法与复杂性1)主要内容：包括算法的复杂度分析、典型的算法策略、分布式算法、并行算法、可计算理论、自动机理论、密码算法等2）基本问题主要包括对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如何折衷？算法最好和最坏的情况是什么？算法的通用性如何？计算机学科各主领域的基本问题体系结构1)主要内容：包括数字逻辑数据的机器表示、汇编级机器组织、存储技术、接口和通信、性能优化网络和分布式系统的体系结构等2）基本问题主要包括:实现处理器内存和机内通信的方法是什么？如何设计和控制大型计算系统？哪种类型的体系结构能够有效地包含许多在一个计算中能够并行工作的处理元素？计算机学科各主领域的基本问题操作系统1）主要内容：包括操作系统的逻辑结构、并发处理资源分配与调度、存储管理、设备管理等2）基本问题主要包括：在计算机系统操作的每一个级别上，可见的对象和允许进行的操作各是什么？对于每一类资源能够对其进行有效利用的最小操作集是什么？如何组织接口才能使得用户只需与抽象的资源而非硬件的物理细节打交道？作业调度、内存管理、并发任务间的通信等。计算机学科各主领域的基本问题网络计算1）主要内容：包括计算机网络的体系结构、网络安全、网络管理、无线和移动计算，以及多媒体数据技术等2）基本问题主要包括网络中的数据如何进行交换？网络协议如何验证？如何保证网络的安全？分布式计算的性能如何评价？分布式计算如何组织才能够使通过通信网连接在一起的自主计算机参加到一项计算中？计算机学科各主领域的基本问题程序设计语言1）主要内容：包括程序设计模式、类型系统、执行控制模型、语言翻译系统、程序设计语言的语义学等2）基本问题主要包括语言（数据类型、操作、控制结构、引进新类型和操作的机制）表示的虚拟机的可能组织结构是什么？语言如何定义机器？机器如何定义语言？什么样的表示法语义可以有效地用于描述计算机应该做什么？计算机学科各主领域的基本问题人机交互1）主要内容：包括以人为中心的软件开发和评价，图形用户接口设计，多媒体系统的人机接口等2）基本问题主要包括表示物体和自动产生供阅览的照片的有效方法是什么？接受输入和给出输出的有效方法是什么？怎样才能减小产生误解和由此产生的人为错误的风险？图表和其他工具怎样才能通过存储在数据集中的信息去理解物理现象？计算机学科各主领域的基本问题图形学和可视化计算1）主要内容：包括计算机图形学、可视化、虚拟现实、计算机视觉等4个学科子领域的研究内容2）基本问题主要包括支撑图像产生以及信息浏览的更好模型？如何提取科学的计算和医学和更抽象的相关数据？图像形成过程的解释和分析方法？计算机学科各主领域的基本问题智能系统1）主要内容：知识表示和推理、Agent、自然语言处理、机器学习和神经网络、人工智能和机器人学等2基本问题主要有基本的行为模型是什么？如何建造模拟它们的机器？规则评估、推理、演绎在多大程度上描述了智能？通过这些方法模拟行为的机器的最终性能如何？传感数据如何编码才使得相似的模式有相似的代码？学习系统的体系结构怎样？计算机学科各主领域的基本问题信息管理1）主要内容：包括信息模型与信息系统、数据库系统、数据建模、数据库查询语言、关系数据库设计、事务处理、分布式数据库、数据挖掘、信息存储与检索、超文本和超媒体、多媒体信息与多媒体系统、数字图书馆等2）基本问题主要包括高级查询如何翻译成高质量的程序？怎样保护数据以避免非授权访问泄露和破坏？如何保护大型的数据库以避免同时更新引起的不一致性？当数据分布在许多机器上时如何保护数据保证性能？文本如何索引和分类才能够进行有效的恢复？计算机学科各主领域的基本问题软件工程1）主要内容：包括软件过程、软件需求与规格说明、软件设计、软件验证、软件演化、软件项目管理、软件开发工具与环境、形式化方法、软件可靠性等2）基本问题主要包括如何证明一个程序或系统满足其规格说明？如何编写不忽略重要情况且能用于安全分析的规格说明？软件系统是如何历经不同的各代进行演化的？如何从可理解性和易修改性着手设计软件？计算机学科各主领域的基本问题社会和职业的问题1）主要内容：包括计算的历史、计算的社会背景、分析方法和工具、专业和道德责任、基于计算机系统的风险与责任、知识产权、隐私与公民的自由、计算机犯罪与计算有关的经济问题等2）基本问题主要包括计算机学科本身的文化社会法律和道德的问题？有关计算的社会影响问题以及如何评价可能的一些答案的问题？哲学问题？技术问题以及美学问题？计算机学科各主领域的基本问题科学计算1）主要内容：包括数值分析、运筹学、模拟和仿真、高性能计算2）基本问题主要包括如何精确地以有限的离散过程近似表示连续和无限的离散过程？如何处理这种近似产生的错误？给定某一类方程在某精确度水平上能以多快的速度求解？如何实现方程的符号操作如积分微分以及到最小项的归约？计算机科学典型问题示例哥尼斯堡七桥问题寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径计算机科学典型问题示例梵天塔问题1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处；3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。计算机科学典型问题示例证比求易算法一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚，公主出了这样一道题：求出48770428433377171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后从早到晚共算了三万多个数最终还是没有结果，国王向公主求情，公主将答案相告223092827是它的一个真因子。公主说我再给你一次机会，如果还求不出将来你只好做我的证婚人了。国王立即回国并向时任宰相的大数学家求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位。于是他给国王出了一个主意，按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后国王用这个办法求婚成功。计算机科学典型问题示例旅行商问题与组合爆炸问题威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出的一个数学问题。大意是有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线使其旅行的费用最少。。计算机科学典型问题示例旅行商问题与组合爆炸问题计算机科学典型问题示例旅行商问题与组合爆炸问题据文献介绍，1998年科学家们成功地解决了美国13509个城市之间的TSP问题，2001年又解决了德国15112个城市之间的TSP问题，但这一工程代价也是巨大的。据报道解决15112个城市之间的TSP问题，共使用了美国Rice大学和普林斯顿大学之间网络互连的由速度为500MHz的CompaqEV6Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。计算机科学典型问题示例哲学家共餐问题5个哲学家围坐在一张圆桌旁，每个人的面前摆有一碗面条，碗的两旁各摆有一只筷子。假设哲学家的生活除了吃饭就是思考问题（这是一种抽象，即对该问题而言，其他活动都无关紧要），而吃饭的时候需要左手拿一只筷子、右手拿一只筷子，然后开始进餐，吃完后又将筷子摆回原处，继续思考问题。现在的问题是，如何协调5个哲学家的生活进程，使得每一个哲学家最终都可以进餐。