计算机科学导论之二课件

1、第二讲计算机科学的内容计算学科的根本问题三个学科形态主要领域基本问题典型问题示例第1页，共27页。计算机科学的根本问题 计算机科学与计算科学 定义：计算学科是对描述和变换信息的算 法过程，包括对其理论分析、设计、 效率实现和应用等进行的系统研究。计算学科的根本问题 计算学科的根本问题是什么能被有 效地自动进行。 第2页，共27页。计算学科中的3个学科形态 抽象形态 学科中的抽象形态包含着学科中所具有的科学概念、科学符号和思想模型。按客观现象的研究过程，抽象形态包括以下4个步骤的内容： 1）形成假设 2）建造模型并作出预测 3）设计实验并收集数据 4）对结果进行分析 第3页，共27页。计算学科中

2、的3个学科形态 理论形态 理论是经过实践检验的系统化了的科学知识体系，由科学概念、科学原理以及对这些概念原理的理论论证所组成的体系。在计算学科中，理论形态包括以下4个步骤的内容： 1）表述研究对象的特征定义和公理 2）假设对象之间的基本性质和对象之间可能存在 的关系定理 3）确定这些关系是否为真证明 4）结论 第4页，共27页。计算学科中的3个学科形态 设计形态 设计形态具有较强的实践性，社会性和综合性。在计算学科中，从为解决某个问题而实现系统或装置的过程来看，设计形态包括以下4个步骤的内容： 1）需求分析 2）建立规格说明 3）设计并实现该系统 4）对系统进行测试与分析 第5页，共27页。计

3、算学科中的3个学科形态 三种形态关系 设计、抽象和理论3个形态针对具体的研究领域均起作用，在具体研究中，就是要在其理论的指导下，运用其抽象工具进行各种设计工作，最终的成果将是计算机的软硬件系统及其相关资料。 抽象源于现实世界 理论源于数学 设计源于工程 第6页，共27页。计算机学科各主领域的基本问题 离散结构 主要内容：包括集合论、数理逻辑、近世代数、图论、以及组合数学等。 第7页，共27页。计算机学科各主领域的基本问题 程序设计基础 1）主要内容：包括程序设计结构、算法、问 题求解和数据结构等 2）基本问题主要包括： 对给定的问题，如何进行有效的描述并给 出算法？ 如何正确选择数据结构？ 如

4、何进行设计、编码、测试和调试程序？ 第8页，共27页。计算机学科各主领域的基本问题 算法与复杂性 1) 主要内容：包括算法的复杂度分析、典型的算法策略、分布式算法、并行算法、可计算理论、自动机理论、密码算法等 2）基本问题主要包括 对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如何折衷？算法最好和最坏的情况是什么？ 算法的通用性如何？ 第9页，共27页。计算机学科各主领域的基本问题 体系结构 1) 主要内容：包括数字逻辑数据的机器表示、汇编级机器组织、存储技术、接口和通信、性能优化网络和分布式系统的体系结构等 2）基本问题主要包括: 实现处理器内存和机内通信的方

5、法是什么？ 如何设计和控制大型计算系统？ 哪种类型的体系结构能够有效地包含许多在一个计算中能够并行工作的处理元素？第10页，共27页。计算机学科各主领域的基本问题 操作系统 1）主要内容：包括操作系统的逻辑结构、并发处 理资源分配与调度、存储管理、设备管理等 2）基本问题主要包括： 在计算机系统操作的每一个级别上，可见的对象和 允许进行的操作各是什么？ 对于每一类资源能够对其进行有效利用的最小操作 集是什么？ 如何组织接口才能使得用户只需与抽象的资源而非 硬件的物理细节打交道？ 作业调度、内存管理、并发任务间的通信等。第11页，共27页。计算机学科各主领域的基本问题 网络计算 1）主要内容：包

6、括计算机网络的体系结构、网络安 全、网络管理、无线和移动计算，以及多媒体数 据技术等 2）基本问题主要包括 网络中的数据如何进行交换？网络协议如何验证？ 如何保证网络的安全？ 分布式计算的性能如何 评价？ 分布式计算如何组织才能够使通过通信 网连接在一起的自主计算机参加到一项计算中？第12页，共27页。计算机学科各主领域的基本问题 程序设计语言 1）主要内容：包括程序设计模式、类型系统、执行控制模型、语言翻译系统、程序设计语言的语义学等 2）基本问题主要包括 语言（数据类型、操作、控制结构、引进新类型和操作的机制）表示的虚拟机的可能组织结构是什么？ 语言如何定义机器？机器如何定义语言？ 什么样

7、的表示法语义可以有效地用于描述计算机应该做什么？ 第13页，共27页。计算机学科各主领域的基本问题 人机交互 1）主要内容：包括以人为中心的软件开发和评价，图形用户接口设计，多媒体系统的人机接口等 2）基本问题主要包括 表示物体和自动产生供阅览的照片的有效方法是什么？ 接受输入和给出输出的有效方法是什么？ 怎样才能减小产生误解和由此产生的人为错误的风险？ 图表和其他工具怎样才能通过存储在数据集中的信息去理解物理现象？ 第14页，共27页。计算机学科各主领域的基本问题 图形学和可视化计算 1）主要内容：包括计算机图形学、可视化、虚拟现实、计算机视觉等4个学科子领域的研究内容 2）基本问题主要包括

8、 支撑图像产生以及信息浏览的更好模型？ 如何提取科学的计算和医学和更抽象的相关数据？ 图像形成过程的解释和分析方法 ？ 第15页，共27页。计算机学科各主领域的基本问题 智能系统 1）主要内容：知识表示和推理、Agent、自然语言处理、机器学习和神经网络、人工智能和机器人学等 2基本问题主要有 基本的行为模型是什么？如何建造模拟它们的机器？ 规则评估、推理、演绎在多大程度上描述了智能？ 通过这些方法模拟行为的机器的最终性能如何？ 传感数据如何编码才使得相似的模式有相似的代码 ？学习系统的体系结构怎样 ？ 第16页，共27页。计算机学科各主领域的基本问题 信息管理 1）主要内容：包括信息模型与信

9、息系统、数据库系统、数据建模、数据库查询语言、关系数据库设计、事务处理、分布式数据库、数据挖掘、信息存储与检索、超文本和超媒体、多媒体信息与多媒体系统、数字图书馆等 2）基本问题主要包括 高级查询如何翻译成高质量的程序 ？怎样保护数据以避免非授权访问泄露和破坏 ？如何保护大型的数据库以避免同时更新引起的不一致性 ？当数据分布在许多机器上时如何保护数据保证性能 ？文本如何索引和分类才能够进行有效的恢复 ？ 第17页，共27页。计算机学科各主领域的基本问题 软件工程 1）主要内容：包括软件过程、软件需求与规格说明、软件设计、软件验证、软件演化、软件项目管理、软件开发工具与环境、形式化方法、软件可靠

10、性等 2）基本问题主要包括 如何证明一个程序或系统满足其规格说明 ？如何编写不忽略重要情况且能用于安全分析的规格说明？ 软件系统是如何历经不同的各代进行演化的 ？如何从可理解性和易修改性着手设计软件 ？ 第18页，共27页。计算机学科各主领域的基本问题 社会和职业的问题 1）主要内容：包括计算的历史、计算的社会背景、分析方法和工具、专业和道德责任、基于计算机系统的风险与责任、知识产权、隐私与公民的自由、计算机犯罪与计算有关的经济问题等 2）基本问题主要包括 计算机学科本身的文化社会法律和道德的问题 ？有关计算的社会影响问题以及如何评价可能的一些答案的问题 ？哲学问题 ？技术问题以及美学问题 ？

11、 第19页，共27页。计算机学科各主领域的基本问题 科学计算 1）主要内容：包括数值分析、运筹学、模拟和仿真、高性能计算 2）基本问题主要包括 如何精确地以有限的离散过程近似表示连续和无限的离散过程？ 如何处理这种近似产生的错误 ？给定某一类方程在某精确度水平上能以多快的速度求解 ？如何实现方程的符号操作如积分微分以及到最小项的归约 ？第20页，共27页。计算机科学典型问题示例 哥尼斯堡七桥问题 寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径 第21页，共27页。计算机科学典型问题示例 梵天塔问题 1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处 ；3）在

12、移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上 天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。 第22页，共27页。计算机科学典型问题示例 证比求易算法 一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚，公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后从早到晚共算了三万多个数最终还是没有结果，国王向公主求情，公主将答案相告223 092 827是它的一个真因子。公主说我再给你一次机会，如果还求不出将来你只好做我的证婚人了。国王立即回国并向时任宰相的大数学家求教，大数学家在仔细

13、地思考后认为这个数为17位，则最小的一个真因子不会超过9位。于是他给国王出了一个主意，按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后国王用这个办法求婚成功。第23页，共27页。计算机科学典型问题示例 旅行商问题与组合爆炸问题 威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出的一个数学问题。大意是有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线使其旅行的费用最少。 。 第24页，共27页。计算机科学典型问题示例 旅行商问题与组合爆炸问题第25页，共27页。计算机科学典型问题示例 旅行商问题与组合爆炸问题据文献介绍，1998年科学家们成功地解决了美国13509个城市之间的TSP问题，2001年又解决了德国15112个城市之间的TSP问题，但这一工程代价也是巨大的。据报道解决15112个城市之间的TSP问题，共使用了美国Rice大学和普林斯顿大学之间网络互连的由速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为2