第2章 认识计算机学科

第2章认识计算机学科

2.1什么是计算机学科

2.2计算机学科的科学问题

2.3计算机学科的经典问题

2.4计算机学科的知识体系

什么是计算

■从字源上考察：

计：从言从十，有数数或计数的含义;

算：从竹从具，指计算工具。

■《现代汉语词典》对计算的定义：

根据已知数通过数学方法求得未知数。

什么是计算

■直观的计算：数的加减乘除；函数的微分、积

分；微分方程的求解；定理的证明推导等等。

■计算的实质：从一个符号串/（输入）得出另

一个符号串g（输出）。

■数学概念一普适概念

计算的例子

A从符号串“12+3”变换成符号串“15”——加法计

算

»符号串变换成符号串——微分；

»/表示一组公理和推导规则，g是一个定理，那么

从f到g的一系列变换——定理g的证明；

»符号串/代表一个英文句子，符号串g为含义相

同的中文句子，那么从/到g的变换——英文翻

磁中暹变换有什么共同点？

侬为什么他们都叫做计算？

图灵与巨人计算机

>5

图灵模型

有限状态

控制器

工作带

■一条无限长的工作带：工作带上的每个单元可以

存放一个符号；所有允许出现的符号属于一个预先

规定好的字母表。

图灵模型

有限状态

控制器

工作带

■一个读写头：读写头可以左移一个单元、右移一

个单元或者保持不动。

图灵模型

有限状态

控制器

1

工作带

■一个控制器：控制器在每个时刻处于一定的状态,

当读写头从工作带上读出一个符号后，控制器就根

据这个符号和当时的机器状态，指挥读写头进行读

写或者移动，并决定是否改变机器状态。

计算与可计算

所谓计算就是计算者（人或机器）对一条可以无

限延长的工作带上的符号串执行指令，一步一步

地改变工作带上的符号串，经过有限步骤，最后

得到一个满足预先规定的符号串的变换过程。

什么样的任务才是可计算的任务？这是计算机科

学必须要回答的一个最基本的问题。这是关系到

计算机能做什么、不能做什么的根本问题。

类比：什么样的衣服才是洗衣机可洗的？

用图灵模型来计算

构造一个识别符号串口=仍〃（〃21）的图灵机

基本思想：使读写头往返移动，每往返移动一

次，就成对地对输入符号串。左端的一个4和右

端的一个〃匹配并做标记心如果恰好把输入符

号串。的所有符号都做了标记，说明左端的符号

。和右端的符号〃的个数相等；否则，说明左端

的符号〃和右端的符号〃的个数不相等，或者符

号〃和力交替出现。

用图灵模型来计算

假定〃=2,输入符号串”=的防

工作带BaabbB

指令

机器状态

---------------------------S

、^当前数器状态

的字符

当前读

到的字筠读写头的动作

R:右移L：左移H:不动

用图灵模型来计算

子母表：

读写头{a,b,B}

工作带BaabbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)

制读写头扫描到符号处

(夕1,xxLql)

器则继续往右走

(夕1,axRql)

(夕1,BBHqN)

(夕2,xxRql)

用图灵模型来计算

读写头

工作市BaabbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)

制读写头扫描到符号处

(夕1,xxLql)

器则继续往右走

(夕1,axRql)

(夕

1,BBHqN)

(夕2,xxRql)

用图灵模型来计算

读写头

工作市BaabbB

程序

（夕0,aaR夕0）

控（夕0,bxL夕1）读写头扫描到符号儿

制（夕1,xxL夕1）将当前单元写入字符X,

器

（夕1,axR夕2）并使读写头往左走，

转移到状态夕。

（夕1,BBHqJ1

（夕2,xxR夕2）

用图灵模型来计算

读写头

工作市BaaxbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)读写头扫描到符号儿

制(夕1,xxLql)将当前单元写入字符x,

器

(夕1,axRql)并使读写头往左走，

(ql,BBHqJ转移到状态夕1。

(夕2,xxRql)

用图灵模型来计算

读写头

工作市BaaxbB

程序

（夕0,aaR夕0）

控读写头扫描到符号小

（夕0,bxL夕1）

制贝时巴〃改为标记X,

（夕LxxLql）

器并使读写头往右走，

（夕夕）

1,axR2转移到状态夕2

（夕1,BBHqJ

（夕2,xxR夕2）

用图灵模型来计算

读写头

工作市BaxxbB

程序

（夕0,aaR夕0）

控读写头扫描到符号小

（夕0,bxL夕1）

制贝时巴〃改为标记X,

（夕LxxLql）

器并使读写头往右走，

（夕夕）

1,axR2转移到状态夕2

（夕1,BBHqJ

（夕2,xxR夕2）

用图灵模型来计算

读写头

工作市BaxxbB

程序

(夕0,aaR夕0)

控读写头扫描到标记x,

(夕0,bxL夕1)

制则继续往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(夕2,xxRql)

用图灵模型来计算

读写头

工作带BaxxbB

程序

（夕2,bxL夕1）

控若读写头扫描到符号

（夕2,BBLq3）A,

制贝」把改为标记达

（夕3,xxL夕3）I6

器并使读写头往左走，

（夕3,aaH如）转移到状态贝

（夕3,BBHq4）

用图灵模型来计算

读写头

工作市BaxxxB

程序

(夕0,aaR夕0)

控若读写头扫描到符号A,

(夕0,bxL夕1)

制贝I」把6改为标记x,

(夕1,xxLql)

器并使读写头往左走，

(夕1,axRql)转移到状态贝

(ql,BBHqJ

(夕2,xxRql)

用图灵模型来计算

读写头

工作市BaxxxB

程序

(夕0,aaR夕0)

控读写头扫描到标记x,

(夕0,bxL夕1)

制则继续往左走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(夕2,xxRql)

用图灵模型来计算

读写头

工作市BaxxxB

程序

（夕0,aaR夕0）

控读写头扫描到符号小

（夕0,bxL夕1）

制贝时巴〃改为标记X,

（夕LxxLql）

器并使读写头往右走，

（夕夕）

1,axR2转移到状态夕2；

（夕1,BBHqJ

（夕2,xxR夕2）

用图灵模型来计算

读写头

工作市BxxxxB

程序

(夕0,aaR夕0)

控读写头扫描到标记x,

(夕0,bxL夕1)

制则继续往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用图灵模型来计算

读写头

工作市BxxxxB

程序

(夕0,aaR夕0)

控读写头扫描到标记x,

(夕0,bxL夕1)

制则继续往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用图灵模型来计算

读写头

工作市BxxxxB

程序

(夕0,aaR夕0)

控读写头扫描到标记x,

(夕0,bxL夕1)

制则继续往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用图灵模型来计算

读写头

工作市BxxxxB

程序

(夕2,bxLql)

控(夕2,BBLq3)读写头扫描到空白符5,

制(夕3,xxL夕3)说明符号A已处理完毕,

器则把状态改为夕3,

(夕3,aaH如)并使读写头往左走

(夕3,BBHq4)

平用图灵模型来计算

读写头

工作带BxxxXB

程序

（夕2,bxL夕1）

控读写头扫描到空白符5,

（夕2,BBLq3）

制说明符号A已处理完毕,

（夕3,xxL夕3）

器则把状态改为夕3,

（夕3,aaHqQ并使读写头往左走

（夕3,BBHq4）

用图灵模型来计算

读写头

工作市BxxxxB

程序

（夕2,bxL夕1）

控读写头扫描到标记

（夕2,BBLq3）x

制则继续往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用图灵模型来计算

读写头

工作市BxxxxB

程序

（夕2,bxL夕1）

控读写头扫描到标记

（夕2,BBLq3）x

制则继续往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用图灵模型来计算

读写头

工作市BxxxxB

程序

（夕2,bxL夕1）

控读写头扫描到标记

（夕2,BBLq3）x

制则继续往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用图灵模型来计算

读写头

工作市BxxxxB

程序

（夕2,bxL夕1）

控读写头扫描到空白符以

（夕2,BBLq3）

制说明符号〃和〃已成对标记,

（夕3,xxL夕3）

器转移到状态夕4,

（夕3,aaH如）达到接受状态。

（夕3,BBHq4）

从图灵机我们看到了什么?

■图灵机在一定程度上反映了人类最基本的、最原始的

计算能力，它的基本动作非常简单、机械、确定。因

止匕有条件用真正的机器来实现图灵机。

■程序并非必须顺序执行，指令中关于下一状态的指定,

实际上表明指令可以不按程序中所表示的顺序执行。

这意味着，虽然程序只能按线性顺序来表示指令序列,

但程序的实际执行可以与表示的顺序不同。

-计算的对象、中间结果和最终结果都在带上，程序则

在控制器中。这意味着什么？

思考：将做一件复杂事情的过程分解成许多简

单的、机械的步骤，你是否有过成功的经验？

科学与学科

科学是关于自然、社会和思维的发展与变化规律的知识体

系，是由人类在生产活动和社会活动中产生和发展的，是人类

实践经验的结晶。

（1）科学是逐步发展起来的

（2）科学的发展需要某种特殊的方法

（3）科学在不断超越中永无止境地发展

学科本身具有二重含义：

（1）指知识体系或学术分类，含义较广；

（2）指为培养人才而设立的教学科目。

科学与学科

■科学研究是以问题为基础的，学科是在科学

发展中不断分化和整合而形成和发展的，是

科学研究发展成熟的产物。

-科学研究发展成熟而成为一个独立学科的标

志是：必须有独立的研究内容、成熟的研究

方法、规范的学科体制。

计算机学科的定义

计算机学科是对描述和变换信息的算法

过程，包括对其理论、分析、设计、效率、

实现和应用等进行的系统研究。

它来源于对算法理论、数理逻辑、计算

模型、自动计算机器的研究，并与存储式电

子计算机的发明一起形成于20世纪40年代初

期。

计算机学科的特点

■计算机学科包括科学和技术两个方面。

A科学侧重于研究现象、揭示规律；

A技术则侧重于研制计算机、研究使用计算机

进行信息处理的方法与技术手段。

■科学是技术的依据，技术是科学的体现。

■二者高度融合是计算机科学与技术学科的突

出特点。

■计算机学科是一门科学性与工程性并重的学

科，表现为理论和实践紧密结合的特征。

计算机学科的特点

■科学：关于自然、社会和思维的发展与变化

规律的知识体系，其核心是发现。

■技术：根据实践经验和科学原理而发展形成

的各种工艺操作方法、技能和技巧，其核心

是发明。

■工程：将科学原理应用到生产实践中，是某

种形式的科学应用，其核心是建造。

计算机学科的根本问题

■计算机学科的根本问题是：什么能被（有

效地）自动计算。

■计算机学科所有分支领域的根本任务就是

进行计算，其实质就是字符串的变换。

计算机学科的符号化特征

・一一一一一一一一一一一一一一一一一」

计算机学科与其他学科的关系

■计算机学科是在数学和电子学基础上发展

起来的。

■计算机学科的发展也必然受制于其它学科

的发展。

■计算机学科可以在几乎所有的学科领域，

甚至我们日常生活的各个方面找到应用。

什么是科学问题

科学问题是指一定时代的科学认识主体，在已完

成的科学知识和科学实践的基础上，提出的需要解决

且有可能解决的问题，它包含一定的求解目标和应答

域，但尚无确定的答案。

科学问题具有如下主要特征：

（1）时代性（2）混沌性（3）可解决性（4）

可变异性（5）可待解性

科学问题的提出和解决是任何一个学科持续发展

的动力。

计算机学科的科学问题

1.计算的平台与环境问题

核心：计算问题的能行性

2.计算过程的能行操作与效率问题

核心：算法及算法分析

3.计算的正确性问题

核心：各种语言的语义

上述基本问题普遍出现在学科的各个分支

学科和研究方向之中，是学科研究与发展中经

常面对而又必须解决的科学问题。

计算机学科的经典问题

经典问题是指那些反映学科某一方面内

在规律和本质内容的典型问题。

经典问题往往以深入浅出的形式表达学

科深奥的科学规律和本质内容，在学科研究

中常常用来辅助说明思想、原理、方法和技

术。

GOTO语句问题与程序设计方法学

■1968年，计算机科学家狄杰斯

特拉首次提出了GOTO语句是

有害的。

■1974年，计算机科学家克努斯

发表论文《带有GOTO语句的

结构化程序设计》作了较全面

而公正的论述。

面条程序示例

GOTO语句问题与程序设计方法学

滥用GOTO语句是有害的，完全禁止也

是不明智的，在不破坏程序良好结构的前提

下，有限制地使用GOTO语句，有可能使程

序更清晰、效率更高。

关于“GOTO语句”问题的争论直接导

致了一个新的学科分支领域——程序设计方

法学的产生，它是一个对程序的性质及其设

计的理论和方法进行研究的学科。

哥尼斯堡七桥问题与图论

在一次步行中穿越全部的七

座桥后回到起点，且每座桥

D

只经过一次。

哥尼斯堡七桥问题与图论

欧拉回路的判定规则:

（1）如果通奇数桥的地方多于两个，则不存在

欧拉回路；

（2）如果只有两个地方通奇数桥，可以从这两

个地方之一出发，找到欧拉回路；

（3）如果没有一个地方是通奇数桥的，则无论

从哪里出发，都能找到欧拉回路。

哈密顿回路问题

1

哈密顿回路：要求

从一个城市出发，

经过每个城市恰好202

一次，然后回到出

发城市。

哲学家共餐问题与进程同步

哲学家的生活进程可表示为：

(1)思考问题；

(2)俄了停止思考，左手拿起一只

筷子(如果左侧哲学家已持有它，则

等待)；

(3)右手拿起一只筷子(如果右侧

哲学家已持有它，则等待)；

(4)进餐；

(5)放下左手筷子；

(6)放下右手筷子；

(7)重新回到状态(1)思考问题；

哲学家共餐问题与进程同步

程序并发执行时进程同步的两个关键问题一

—死锁和饥饿：

(1)按哲学家的生活进程，当所有的哲学家都同时拿起

左手筷子时，则所有哲学家都将拿不到右手筷子，并处于

等待状态，那么，哲学家都将无法进餐，最终饿死。

(2)将哲学家的生活进程修改为当拿不到右手筷子时，

就放下左手筷子。但是，可能在一个瞬间，所有的哲学家

都同时拿起左手筷子，则自然拿不到右手筷子，于是都同

时放下左手筷子，等一会，又同时拿起左手筷子，如此重

复下去，则所有的哲学家都将无法进餐。

汉诺塔问题与计算复杂性

汉诺塔问题：在世界刚被创建的时候有一座

钻石宝塔（塔A）,其上有64个金碟。所有碟子

按从大到小的次序从塔底堆放至塔顶。紧挨着这

座塔有另外两个钻石宝塔（塔B和塔C）。从世

界创始之日起，婆罗门的牧师们就一直在试图把

塔A上的碟子移动到塔C上去，其间借助于塔B

的帮助。每次只能移动一个碟子，任何时候都不

能把一个碟子放在比它小的碟子上面。当牧师们

完成任务时，世界末日也就到了。

汉诺塔问题与计算复杂性

ABC

A

(b)

ABC

LAX

(c)

汉诺塔问题与计算复杂性

〃个碟子的汉诺塔问题需要移动的碟子数是

个碟子的汉诺塔问题需要移动的碟子数的2倍再

加1。因此：

Zz(n)=2h(n—1)+1

=2(2/z(n-2)+1)+1

=22h{n-2)+2+1

=2nh(U)+2"T+•••+22+21+1

=2"i+•••+22+21+1

=2n-1

汉诺塔问题与计算复杂性

I・64个碟子的汉诺塔问题，需要移动的碟子数为：

264-1=18,446,744,073,709,551,615

■如果每秒移动一次，一年有31,536,000秒，则僧

侣们一刻不停地来回移动，也需要花费5849亿年的

时间；

■假定计算机以每秒1000万个碟子的速度进行移动,

则需要花费58,490年的时间。

Q理论上可以计算的问题，实际上并不一定能行，

K这属于计算复杂性领域的研究内容。

7证比求易问题与NP完全问题

■在计算复杂性领域中，一般认为求解一个问

题往往比较困难，但验证一个问题相对来说就

比较容易——证比求易。

»求大整数5=49,770,428,644,836,899的因子是

个难解问题，但是验证〃=223,092,871是不是大

整数S的因子却很容易；

A求一个线性方程组的解可能很困难，但是验

证一组解是否是方程组的解却很容易。

证比求易问题与NP完全问题

■在计算复杂性领域中，将所有可以在多项式时

间内求解的问题称为P类问题，而将所有可以

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

■P=NP是否成立是计算科学和当代数学研究中

最大的悬而未决的问题之一。

■20世纪70年代初，库克在证明了NP类中某些

问题的复杂性与整个NP类的复杂性有关，当

这些问题中的任何一个存在多项式时间算法，

则所有这些NP类问题都是在多项式时间内可

解决的，这些问题称为NP完全问题。

TSP问题与组合爆炸

TSP问题（又称货郎担问题、邮递员问题、

售货员问题）是数学家克克曼于19世纪初提出

的一个数学问题，是指旅行家要旅行〃个城市

然后回到出发城市，要求各个城市经历且仅经

历一次，并要求所走的路程最短。

由于TSP问题有着貌似简单的表述、重要

的应用、以及和其他NP完全问题的重要关系，

它在近200年的时间里强烈地吸引着计算机科

学工作者。

，ft

TSP问题与组合爆炸

序号路径路径长度是否最短

1a一b一c一d—a18否

2a一b一d—c-a11是

3a—c一b一d—a23否

4a—c一d—b一a11是

5a一d—b一c-a23否

6a一d—c一b一a18否

TSP问题与组合爆炸

对于具有〃个顶点的TSP问题，可能的解有：

(»1)!/2个。

■10城市的TSP问题有大约180,000个可能解。

■20城市的TSP问题有大约60,000,000,000,000,000个

可能解。

■50城市的TSP问题有大约1062个可能解，而一个行

星上也只有10口升水。

组合爆炸

-组合优化问题：寻找一个组合对象，比如一个

排列或一个组合，这个对象能够满足特定的约

束条件并使得某个目标函数取得极值。

■无论从理论的观点还是实践的观点，组合优化

问题都是计算领域中最难的问题，其原因是：

(1)随着问题规模的增大，组合对象的数量增

长产生组合爆炸；

(2)还没有一种已知算法能在可接受的时间内,

精确地求解绝大多数这类问题。

图灵测试与人工智能

回答者A回答者B

图灵测试与人工智能

■行为主义（弱AI）：不要求接受测试的思维机器

在内部构造上与人脑相同，而只是从功能的角度

来判定机器是否具有思维，也就是从行为角度对

机器思维进行定义。

■符号主义（强AI）：认知是一种符号处理过程，

人类思维过程也可以用某种符号来描述。

■由于人们对心理学和生物学的认识还很不成熟，

对人脑的结构还没有真正了解，更无法建立起人

脑思维完整的数学模型。因此，到目前为止，思

维就是计算的思想没有实质性的突破。

图灵测试与人工智能

■1994年11月，美国科学家阿德勒曼教授发表了

论文《解决组合问题的分子计算》。

■该论文论证了DNA（脱氧核糖核酸）计算技术

的可行性，并用DNA技术解决了一个简单的有向

哈密顿回路问题。

■2002年，阿德勒曼教授应用DNA技术解决了具

有200万种可能结果的有向哈密顿回路问题。

■阿德勒曼教授的工作从一个侧面探讨了生命过

程就是一种计算的思想。

计算机学科的知识体系

随着计算技术的发展，IEEE/ACM在CC2001

中将计算机学科称为计算学科，并将计算学科

分为四个领域（也称专业方向），分别是计算

机科学、计算机工程、软件工程和信息系统。

于2004年6月1日公布的CC2004报告，在上述

四个领域的基础上，增加了一个信息技术专业

学科领域，并预留了未来的新发展领域。

计算机学科的问题空间

组织系统行为

应用技术

软件开发

系统平台结构

计算机硬件体系

论

理开发应用

理

原<------——->部署

新

创倾向理论倾向应用配置

计算机科学

组织系统行为

应用技术

软件开发

系统平台结构

计算机硬件体系

计算机工程

组织系统行为

应用技术

软件开发

系统平台结构

计算机硬件体系

应

用

论

理开发

部

署

理

原<------------------------------------>

置

配

新

创倾向理论倾向应用

软件工程

应

用

论

理开发

部

署

理

原<------------------------------------>

置

配

新

创倾向理论倾向应用

信息系统

应

用

论

理开发

部

署

理

原<------------------------------------>

置

配

新

创倾向理论倾向应用

信息技术

组织系统行为