2010《计算机导论》复习提纲 - 下载本文

《计算机导论》复习纲要 2010/6/21 08:52

第1章 绪 论 1、第一台计算机;

2、计算机发展的五个阶段; 第一代(1945~1957):电子管计算机(Vacuum Tubes)

第二代(1958~1963):晶体管计算机(Transistor) 第三代(1964~1969):小规模集成电路计算机 Integrated Circuits

第四代(1970~1990):以微处理器(Micro processors)为标志的大规模/超大规模集成电路(LSI/VLSI)计算机(Large-scale Integrated Circuits ) 第五代(1991~目前):以互联网(Internet)为标志的信息系统

3、计算学科的定义

计算学科是对描述和变换信息的算法过程,包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。

4、计算学科的根本问题

计算学科的根本问题是:什么能被(有效地)自动进行。计算学科所有分支领域的根本任务就是进行计算,其实质就是字符串的变换。

5、计算学科的5个分支学科

计算机科学(Computer Science ,简称CS) 信息系统(Information System,简称IS) 软件工程(Software Engineering,简称SE) 计算机工程(Computer Engineering,简称CE) 信息技术(Information Technology ,简称IT)

6、学科知识体

计算机科学知识体由以下3个层次构成:

(1)最高层是分支领域(area),它代表一个特定的学科子领域。 (2)分支领域之下又分为更小的知识单元(unit),它代表该领域中的主题模块。

(3)知识单元又被细分为众多的知识点(topic),这些知识点构成了知识体结构的最底层。

7、计算机科学二维定义矩阵 三个过程 主领域 离散结构(Discrete Structures) 程序设计基础(Programming Fundamentals) 算法和复杂性(Algorithms & Complexity) 计算机结构与组织(Architecture & Organization) 操作系统(Operating Systems) 网络计算(Network Computing) 抽象 理论 设计

程序设计语言(Programming Languages) 人-机交互(Human-Computer Interaction) 图形学与可视计算(Graphics & Visual Computing) 智能系统(Intelligent Systems) 信息管理(Information Management) 软件工程(Software Engineering) 社会和职业问题(Social & Professional Issues) 科学计算 (Computational Science)

计算机科学二维定义矩阵是学科概念的认知模型。

―纵向‖关系,即计算机科学的研究领域。这些内容蕴含在学科3个过程中,并将学科各分支领域结合成一个完整的体系,而不是互不相关的领域。

―横向‖关系,即抽象、理论和设计3个过程的关系,是定义矩阵中最为重要的内容。它反映的是,人们在计算领域的认识规律,即是从感性认识(抽象)到理性认识(理论),再由理性认识(理论)回到实践(设计)的过程。 ―横向‖关系还蕴含着学科中的基本问题。

抽象、理论和设计3个过程

(1)理论源于数学。应用数学家们认为科学的进展都是建立在数学基础之上。它的研究内容表现在两个方面:一方面是建立完整的理论体系,另一方面是在现有理论的指导下,建立具体问题的数学模型,从而实现对客观世界的理性认识。 (2)抽象源于现实世界。抽象建模是自然科学的根本。 (3)设计源于工程。设计是工程的根本。

8、摩尔定律和―贝尔定律‖

在体系结构方面,有所谓―摩尔定律‖(Moore’s Law)和―贝尔定律‖(Bell’s Law)。

前者断定微处理器的速度会每18个月提升一倍,而后者则认为如果保持计算能力不变,微处理器的价格和体积每18个月缩减一倍。

第2章计算学科的基本问题

什么是科学问题?

科学问题是指一定时代的科学认识主体,在已完成的科学知识和科学实践的基础上,提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域,但尚无确定的答案。

罗素悖论

罗素悖论的表现形式:在对结果的观察中同时包含了观察者自身的行为,就会出现悖论。也就是说,理性无法回答关于自身的问题。

希尔伯特纲领

希尔伯特在数学基础的研究中提出了一个设想:将每一门数学的分支形式化,构成形式系统或形式理论,并在以此为对象的元理论即元数学中,证明每一个形式系统的相容性,从而导出全部数学的相容性。他企图寻找通用的形式逻辑系统,在该系统中,可以机械地判定任何

给定命题的真伪,即该系统是完备的。任何系统的完备和一致性,可以由系统本身得到证明。希尔伯特这一设想,就是所谓的―希尔伯特纲领‖。

库尔特·哥德尔(K.Godel)提出的关于形式系统的―不完备性定理‖中指出:形式系统不能穷尽全部数学命题,任何形式系统中都存在着该系统所不能判定其真伪的命题。没有一种公理系统可以导出数论中所有的真实命题,除非这种系统本身就有悖论。

―哥德尔第一定理‖,即哥德尔的―不完备性定理‖: 一个形式系统,如果是一致的(=相容的=无矛盾的),那么,就一定存在一个命题,这个命题在该系统中不能被证明,也不能被否证。换一种说法,这个命题在该系统中不能被证明,它的反命题在该系统中也不能被证明。 ―哥德尔第二定理‖,即:

任何一个被认为是一致的系统,它的一致性是不能在系统内部得到证明的。 因此:形式系统是不完备的

2.2哥尼斯堡七桥问题

欧拉回路

欧拉给出了哥尼斯堡七桥问题的证明,还用数学方法给出了三条判定规则(判定每座桥恰好走过一次,不一定回到原点,即对欧拉路径的判定):

(1)如果通奇数座桥的地方不止两个,满足要求的路线是找不到的。

(2)如果只有两个地方通奇数座桥,可以从这两个地方之一出发,找到所要求的路线。 (3)如果没有一个地方是通奇数座桥的,则无论从哪里出发,所要求的路线都能实现。 根据第3点,可以得出,任一连通图存在欧拉回路的充分必要条件是所有顶点均有偶数度。

哈密尔顿回路问题:

在某个图G中,能不能找到这样的路径,即从一点出发不重复地走过所有的结点,最后又回到原出发点。这个问题也被称作周游世界问题。

―哈密尔顿回路问题‖与―欧拉回路问题‖的不同点

―哈密尔顿回路问题‖是访问每个结点一次,而―欧拉回路问题‖是访问每条边一次。

对图G是否存在―欧拉回路‖前面已给出充分必要条件,而对图G是否存在―哈密尔顿回路‖至今仍未找到满足该问题的充分必要条件。

计算问题可以分为可计算问题与不可计算问题。 可计算问题:存在可解的算法。 不可计算问题:不存在可解的算法。

梵天塔问题说明了:理论上可以计算的问题,实际上并不一定能行,这属于算法复杂性方面的研究内容。

算法复杂性中的难解性问题、P类问题和NP类问题

算法复杂性包括算法的空间以及时间两方面的复杂性问题。

在计算复杂性理论中,将所有可以在多项式时间内求解的问题称为P类问题,而将所有在

多项式时间内可以验证的问题称为NP类问题。

证比求易算法

在计算机科学中,一般认为求解一个问题往往比较困难,但验证一个问题就比较简单。

顺序算法和并行算法

当将一个问题分解到多个处理器上解决时,由于算法中不可避免地存在必须串行执行的操作,从而大大地限制了并行计算机系统的加速能力。

阿达尔定律(参看书本)

一个不可计算问题:停机问题

停机问题(Halting Problem)是1936年图灵在其著名论文《论可计算数及其在判定问题上的应用》中提出,并用形式化方法给予证明的一个不可计算问题。

停机问题引出了一个悖论——当一个程序无限循环时才会停机,并且当它停机时才会无限循环。

什么是形式化方法:

引入表达形式结构的符号语言,用符号与符号之间的联系表达命题或推理的形式结构。

找零问题、背包问题与贪婪算法

一类可以用启发式的贪婪算法来处理的典型问题。

1.找零问题

2.背包问题

―哲学家共餐‖问题与计算机资源管理

计算机的资源分软件资源和硬件资源。硬件的资源主要指CPU、存储器以及输入和输出设备等;软件资源则是指存储在存储设备里面的各类文件。

在计算机中,操作系统负责对计算机软硬资源进行控制和管理,要使计算机系统中的软硬件资源得到高效的使用,就会遇到由于资源共享而产生的问题。

―哲学家共餐‖问题

哲学家进餐问题在计算机科学中所反映的问题实际上是程序并发执行时进程同步的问题: 为了提高系统的处理能力和机器的利用率,并发程序被广泛地使用,因此必须彻底解决并发进程中的死锁和饥饿问题。

并行处理

并行计算时的完整性和同步性出现了问题。

生产者-消费者问题

一个生产者和一个消费者以及一个硬件资源。所谓消费者是指使用某一软硬件资源时的进程,而生产者是指提供(或释放)某一软硬件资源时的进程。

一个重要的概念,即信号灯,它借用了火车信号系统中的信号灯来表示进程之间的互斥。 生产者-消费者问题

例如:大型数据库的共享、联网的售票系统、火车(航班)进出管理系统

2.6―两军问题‖与计算机网络

计算机网络的定义

计算机网络是将分散在不同地理位置上的,具有独立功能的多台计算机系统、各种终端设备、外部设备及其它附属设备,通过通信设备和通信线路连接起来,在网络协议和网络操作系统的管理和控制下,实现数据通信、资源共享和分布处理的系统。

计算机网络发展的四个阶段

计算机网络的发展,大致经历了四个阶段: 1.远程终端联机阶段 2.计算机网络阶段 3.网络互连阶段

4.信息高速公路(互联网)阶段

计算机网络的功能

资源共享、信息传输、提高系统的可靠性、分布处理,系统便于扩充。

计算机网络的分类

1.根据组成计算机网络的地理范围大小的不同,可分为广域网(WAN)、城域网(MAN)和局域网(LAN)三种。

2.按网络的使用范围划分,可将计算机网络分为公用网和专用网。

计算机网络的组成

计算机网络由计算机通过通信线路互连而成,用户通过终端访问网络。从组成网络的设备或系统功能看,计算机网络由通信子网和资源子网构成。

计算机网络的拓扑结构 局域网中,构成网络服务器、工作站(又称节点)等设备通过电缆在物理上互连的几何构形,称为网络的拓扑结构。

信道

信道是指信号的传输通道,可分为物理信道和逻辑信道。其中,物理信道是指用来传递信号的一条物理通道,由传输介质和相关设备组成。

按照传输方式分,信道可分为两类:点到点信道和广播信道。 按使用的传输介质不同,信道可分为有线信道和无线信道。

有线信道可以是架空明线、同轴电缆、光钎电缆及微波导管等信道。 无线信道可以是微波信道、短波信道等。

信道所能传送信号的频率宽度(即可传送信号的最高频率和最低频率之差)称为信道的带宽。

网络协议