计算机导论-第一章绪论

1、第一章 绪论,本章内容,计算科学简介 计算科学的范畴,1.1计算科学简介,计算科学,是描述和变换信息的算法过程。,包括其理论分析、设计，效率分析、实现和应用系统的研究。,计算科学的基本问题就是：什么能（有效地）自动进行，什么不能（有效地）自动进行。 计算科学涵盖了：计算机科学、计算机技术、计算机工程。,1.1.1计算机科学,计算机科学是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，到更具体的主题如编程语言、程序设计、软件和硬件等。,计算机科学研究的课题是： 计算机程序能做什么和不能做什么（可计算性）； 如何使程序更高效的执行特定任务（算法和复杂性理论）；

2、 程序如何存取不同类型的数据（数据结构和数据库）； 程序如何显得更具有智能（人工智能）； 人类如何与程序沟通（人机互动和人机界面）。,计算机科学的大部分研究是基于“冯诺依曼计算机”和“图灵机”的，它们是绝大多数实际机器的计算模型。 计算机科学根植于电子工程、数学和语言学，是科学、工程和艺术的结晶。它在20世纪最后的三十年间兴起成为一门独立的学科，并发展出自己的方法与术语。,1.1.2计算机技术,计算机技术是计算机领域中所运用的技术方法和技术手段。 计算机技术具有明显的综合特性，它与电子工程、应用物理、机械工程、现代通信技术和数学等紧密结合，发展很快。第一台通用电子计算机 ENIAC就是以当时雷

3、达脉冲技术、核物理电子计数技术、通信技术等为基础的。 离散数学、算法论、语言理论、控制论、信息论、自动机论等，为计算机技术的发展提供了重要的理论基础。,基本内容 计算机技术的内容非常广泛，可粗分为： 计算机系统技术； 计算机器件技术； 计算机部件技术； 计算机组装技术等。,1.2 计算科学的范畴,1.2.1 计算科学的主要内容,计算科学的主要内容主要分为14个领域： 离散结构 程序设计基础 算法与复杂性 体系结构 操作系统 网络计算 程序设计语言,人机交互 图形学和可视化计算 智能系统 信息管理 软件工程 社会和职业问题 科学计算,离散结构,主要内容：集合论、数理逻辑、近似代数、图论和组合数学

4、等。 以抽象和理论两个学科形态出现在 计算学科中，为计算学科各分支领域解决其基本问题提供了强有力的数学工具。,程序设计基础,内容包括：程序设计结构、算法、问题求解和数据结构等。 基本问题主要包括：对给定的问题进行程序设计、编码、测试和调试。,算法与复杂性,主要包括：算法的复杂度分析、典型的算法策略、分布式算法、并行算法、可计算理论、P类和NP类问题、自动机理论、密码算法、以及几何算法等。 基本的问题：对于给定的问题类，最好的算法是什么？算法的复杂度如何？算法的性能如何？,操作系统,主要内容：操作系统的逻辑结构、并发处理、资源分配与调度、存储管理、设备管理、文件系统等。 基本问题：在计算机系统操

5、作的每一个级别上，可见的对象和允许进行的操作是什么？等等。,程序设计语言,主要内容：程序设计模式、虚拟机、类型系统、执行控制模型、语言翻译系统、程序设计语言的语义学、基于语言的并行构件等。 基本问题：语言表示的虚拟机的可能组织结构是什么？语言如何定义机器？机器如何定义语言？什么样的表示法可以有效地用于描述计算机应该做什么？,软件工程,主要内容：软件过程、软件需求与规格说明、软件设计、软件验证、软件演化、软件项目管理、软件开发工具与环境、基于构件的计算、形式化方法、软件可靠性、专用系统开发等。 基本问题主要包括：程序和程序设计系统发展背后的原理是什么？如何证明一个程序或系统满足其规格？,科学计算

6、,主要内容包括：数值分析、运筹学、模拟和仿真、高性能计算。 基本问题主要包括：如何精确地以有限地离散过程近似表示连续和无限的离散过程？如何处理这种近似产生的错误？等,1.2.2 计算科学的基本概念,算法的核心作用,在程序员中间有这么一个公式： 程序算法数据结构语言工具和环境 EG：有八个一模一样的小球，有一个比另外七个略轻点，只允许用一个天平秤，请问最少秤多少次可以找到那个轻的小球？ 方法一、可以一半一半的进行比较，秤三次可以得到结果。先把八个球分成两组分别放在天平的两边，取较轻四个再进行分组三次以后就可以找到较轻的小球。,算法,方法二、可以将八个球分为三组：A、B、C。其中A、B中各有三个球

7、，C中有两个。用天平比较A和B的重量，若不平衡则轻的小球在重量轻的那个组中。假设在A中，我们从A中取两个小球进行比较，如果不平衡，则马上可以知道哪个是轻的了；如果平衡，则剩下的是较轻的。若第一次A、B平衡了，则较轻的小球在C中。再秤一次必然也能找到它。,算法,从这个例子当中第二种方法的 效率比较高。可见算法在程序设计中的作用是很重要的。算法与特定的计算机语言没有关系，任何一种计算机语言的实现都离不开算法的支撑。所以，算法是程序设计的核心，也是软件技术的核心。,算法,算法的定义：是指解题方案的准确而完整的描述，也可以说它是解决某一特定问题的一组有穷规则的集合。,（计算科学）可以用计算机来解决一类

8、问题的程序和步骤,算法,算法特征： 有穷性：合理算法应在执行有限步后结束 如：N!=1*2*3*(N-1)*N 而式子：sum=1+2+3+N+ 不能称为算法，因为它执行有限步后仍不能结束,确定性：算法的每一步执行，其顺序和内容都必须有确切的规定，不能模棱两可 可执行性：即算法的所有操作都是能通过计算机程序代码实现，即可操作性 0个或多个输入； 1个或多个输出。,算法,抽象的定义,抽象的定义：一个实体外部特征与其内部构成细节之间的分离。也就是从众多的事物中抽取出共同的、本质性的特征，而舍弃其非本质的特征。 例如苹果、香蕉、生梨、葡萄、桃子等，它们共同的特性就是水果。得出水果概念的过程，就是一个抽象的过程。,抽象,抽象的作用,抽象化主要是为了使复杂度降低，以得到论域中较简单的概念，好让人们能够控制其过程或以综观的角度来了解许多特定的事态。 在