认识计算机学科课件

1、L/O/G/O认识计算机学科 认识计认识计算机算机学学科科认识计算机学科内内容概概要计算机学科的根本问题计算机学科的根本问题计算机学科的科学问题计算机学科的科学问题认识计算机学科计算机学科的根本问题计算机学科的根本问题什么是计算机学科什么是计算机学科什么是计算 计算机学科的定义认识计算机学科什么是计算什么是计算图灵(Alan Turing):所为计算就是计算者(人或机器)对一条可以无限延长的工作带上的符号串执行命令，一步一步地改变工作带上的符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵的研究成果是：可计算性=图灵可计算性认识计算机学科computing认识计算机学科构造

2、一个识别符号串anbn（n1）的图灵机基本思想：使读写头往返移动，每往返移动一次，就成对地对输入符号串左端的一个a和右端的一个b匹配并做标记x。如果恰好把输入符号串的所有符号都做了标记，说明左端的符号a和右端的符号b的个数相等；否则，说明左端的符号a和右端的符号b的个数不相等，或者符号a和b交替出现。 用图灵模型来计算用图灵模型来计算认识计算机学科(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)程序程序假定n2，输入符号串aabb用图灵模型来计算用图灵模型来计算控控制制器器

3、工作带工作带B a a b b B指令指令机器状态机器状态当前读当前读到的字符到的字符当前写当前写入的字符入的字符读写头的动作读写头的动作R:右移右移L:左移左移H:不动不动下一机器状态下一机器状态读写头读写头认识计算机学科(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序字母表：a, b, B用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a a b b B读写头扫描到符号读写头扫描到符号a，则继续往右走则继续往右走 认识计算机学科(q0,

4、a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a a b b B读写头扫描到符号读写头扫描到符号a，则继续往右走则继续往右走 认识计算机学科(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a a b b

5、B读写头扫描到符号读写头扫描到符号b，将当前单元写入字符将当前单元写入字符x，并使读写头往左走，并使读写头往左走，转移到状态转移到状态q1。 认识计算机学科(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a a x b B读写头扫描到符号读写头扫描到符号b，将当前单元写入字符将当前单元写入字符x，并使读写头往左走，并使读写头往左走，转移到状态转移到状态q1。 认识计算机学科(q0, a a R

6、q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a a x b B读写头扫描到符号读写头扫描到符号a，则把则把a改为标记改为标记x，并使读写头往右走，并使读写头往右走，转移到状态转移到状态q2 认识计算机学科(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序用图灵模型来计算用图灵

7、模型来计算控控制制器器工作带工作带B a x x b B读写头扫描到符号读写头扫描到符号a，则把则把a改为标记改为标记x，并使读写头往右走，并使读写头往右走，转移到状态转移到状态q2 认识计算机学科(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a x x b B读写头扫描到标记读写头扫描到标记x，则继续往右走则继续往右走 认识计算机学科(q2, b x L q1) (q2, B B L q3)

8、(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a x x b B若读写头扫描到符号若读写头扫描到符号b，则把则把b改为标记改为标记x，并使读写头往左走，并使读写头往左走，转移到状态转移到状态q1 认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a x x x B若读写头扫描到符号若读写头扫描到符号b，则把则把b改为标记改为标记x，并使读写头往左走，并使读写头往左走，转移到状态转移到状态q1 (q0, a a R q0) (q0, b

9、 x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a x x x B读写头扫描到标记读写头扫描到标记x，则继续往左走则继续往左走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B a x x x B读写头扫描到符号

10、读写头扫描到符号a，则把则把a改为标记改为标记x，并使读写头往右走，并使读写头往右走，转移到状态转移到状态q2； (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到标记读写头扫描到标记x，则继续往右走则继续往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)

11、(q2, x x R q2)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到标记读写头扫描到标记x，则继续往右走则继续往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到标记读写头扫描到标记x，则继续往右走则继续往右走 (q0, a a R q0) (q0, b x L q

12、1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到空白符读写头扫描到空白符B，说明符号说明符号b已处理完毕，已处理完毕，则把状态改为则把状态改为q3，并使读写头往左走并使读写头往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带

13、工作带B x x x x B读写头扫描到空白符读写头扫描到空白符B，说明符号说明符号b已处理完毕，已处理完毕，则把状态改为则把状态改为q3，并使读写头往左走并使读写头往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到标记读写头扫描到标记x，则继续往左走则继续往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H q

14、N)(q3, B B H q4)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到标记读写头扫描到标记x，则继续往左走则继续往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到标记读写头扫描到标记x，则继续往左走则继续往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L

15、 q3)(q3, a a H qN)(q3, B B H q4)认识计算机学科读写头读写头程序程序用图灵模型来计算用图灵模型来计算控控制制器器工作带工作带B x x x x B读写头扫描到空白符读写头扫描到空白符B，说明符号说明符号a和和b已成对标记，已成对标记，转移到状态转移到状态q4，达到接受状态。达到接受状态。 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)认识计算机学科图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型而现代计算机正是这种模型的具体实现认识计算机学科科学与学科科学与学

16、科科学是关于自然、社会和思维的发展与变化规律的知识体系，是由人类在生产活动和社会活动中产生和发展的，是人类实践经验的结晶。 科学是逐步发展起来的科学的发展需要某种特殊的方法科学在不断超越中永无止境地发展认识计算机学科科学与学科科学与学科学科本身具有二重含义： 指知识体系或学术分类，含义较广；指为培养人才而设立的教学科目。认识计算机学科科学与学科科学与学科 科学研究是以问题为基础的，学科是在科学发展中不断分化和整合而形成和发展的，是科学研究发展成熟的产物。科学研究发展成熟而成为一个独立学科的标志是：必须有独立的研究内容、成熟的研究方法、规范的学科体制。认识计算机学科计算机学科的定义计算机学科的定

17、义计算机学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。它来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。认识计算机学科计算机学科的特点计算机学科的特点 计算机学科包括科学和技术两个方面。科学侧重于研究现象、揭示规律；技术则侧重于研制计算机、研究使用计算机进行信息处理的方法与技术手段。科学是技术的依据，技术是科学的体现。二者高度融合是计算机科学与技术学科的突出特点。计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。认识计算机学科计算机学科的特点计算机学科的特

18、点 科学：关于自然、社会和思维的发展与变化规律的知识体系，其核心是发现。技术：根据实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧，其核心是发明。工程：将科学原理应用到生产实践中，是某种形式的科学应用，其核心是建造认识计算机学科什么是科学问题什么是科学问题 科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题，它包含一定的求解目标和应答域，但尚无确定的答案。科学问题具有如下主要特征：（1）时代性 （2）混沌性 （3）可解决性 （4）可变异性 （5）可待解性科学问题的提出和解决是任何一个学科持续发展的动力。 认识计算机学科计算机学科

19、的科学问题计算机学科的科学问题 1. 计算的平台与环境问题 核心：计算问题的能行性 2. 计算过程的能行操作与效率问题 核心：算法及算法分析 3. 计算的正确性问题 核心：各种语言的语义 上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的科学问题。 认识计算机学科计算机学科的经典问题计算机学科的经典问题 经典问题是指那些反映学科某一方面内在规律和本质内容的典型问题。经典问题往往以深入浅出的形式表达学科深奥的科学规律和本质内容，在学科研究中常常用来辅助说明思想、原理、方法和技术。 认识计算机学科1968年，计算机科学家狄杰斯特拉首次提出了GOTO语句

20、是有害的。1974年，计算机科学家克努斯发表论文带有GOTO语句的结构化程序设计作了较全面而公正的论述。 面条程序示例面条程序示例GOTO语句问题与程序设计方法学语句问题与程序设计方法学认识计算机学科GOTO语句问题与程序设计方法学语句问题与程序设计方法学 滥用GOTO语句是有害的，完全禁止也是不明智的，在不破坏程序良好结构的前提下，有限制地使用GOTO语句，有可能使程序更清晰、效率更高。 关于“GOTO语句”问题的争论直接导致了一个新的学科分支领域程序设计方法学的产生，它是一个对程序的性质及其设计的理论和方法进行研究的学科。 认识计算机学科哥尼斯堡七桥问题与图论哥尼斯堡七桥问题与图论东区东区

21、北区北区岛区岛区南区南区CADB哥尼斯堡七桥问题：是否能哥尼斯堡七桥问题：是否能在一次步行中穿越全部的七在一次步行中穿越全部的七座桥后回到起点，且每座桥座桥后回到起点，且每座桥只经过一次。只经过一次。 认识计算机学科哥尼斯堡七桥问题与图论哥尼斯堡七桥问题与图论欧拉回路的判定规则：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；（3）如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。CADB认识计算机学科哈密顿回路问题哈密顿回路问题哈密顿回路：要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。

22、1983141202131545679101112161718认识计算机学科哈密顿回路问题哈密顿回路问题美国图论数学家奥勒奥勒在1960年给出了一个图是哈密尔顿图的充分条件充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。寻找哈密顿路径是一个典型的NP-完全完全问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。 认识计算机学科哲学家共餐问题与进程同步哲学家共餐问题与进程同步 哲学家的生活进程可表示为：哲学家的生活进程可表示为：（1）思考

23、问题；）思考问题；（2）饿了停止思考，左手拿起一只筷）饿了停止思考，左手拿起一只筷子（如果左侧哲学家已持有它，则等子（如果左侧哲学家已持有它，则等待）；待）；（3）右手拿起一只筷子（如果右侧哲）右手拿起一只筷子（如果右侧哲学家已持有它，则等待）；学家已持有它，则等待）；（4）进餐；）进餐；（5）放下左手筷子；）放下左手筷子；（6）放下右手筷子；）放下右手筷子；（7）重新回到状态（）重新回到状态（1）思考问题；）思考问题； 认识计算机学科哲学家共餐问题与进程同步哲学家共餐问题与进程同步程序并发执行时进程同步的两个关键问题死锁和饥饿：（1）按哲学家的生活进程，当所有的哲学家都同时拿起左手筷子时，则

24、所有哲学家都将拿不到右手筷子，并处于等待状态，那么，哲学家都将无法进餐，最终饿死。（2）将哲学家的生活进程修改为当拿不到右手筷子时，就放下左手筷子。但是，可能在一个瞬间，所有的哲学家都同时拿起左手筷子，则自然拿不到右手筷子，于是都同时放下左手筷子，等一会，又同时拿起左手筷子，如此重复下去，则所有的哲学家都将无法进餐。认识计算机学科汉诺塔问题与计算复杂性汉诺塔问题与计算复杂性汉诺塔问题：在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动

25、到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。 认识计算机学科汉诺塔问题与计算复杂性汉诺塔问题与计算复杂性BABCABCAACABC(a)(b)(c)(d)认识计算机学科汉诺塔问题与计算复杂性汉诺塔问题与计算复杂性n个碟子的汉诺塔问题需要移动的碟子数是个碟子的汉诺塔问题需要移动的碟子数是n-1个碟个碟子的汉诺塔问题需要移动的碟子数的子的汉诺塔问题需要移动的碟子数的2倍再加倍再加1。因。因此：此：1212221222)0(212)2(21)1)2(2(21)1(2)(1211212nnnnhnhnhnh

26、nh认识计算机学科用C语言对该问题的求解算法进行描述hanoi(int n,char left,char middle,char right) if(n=1) move(1,one,_,three); else hanoi(n-1,left,right,middle); move(1,left,_,right); hanoi(n-1,middle,left,right); 认识计算机学科汉诺塔问题与计算复杂性汉诺塔问题与计算复杂性64个碟子的汉诺塔问题，需要移动的碟子数为： 2641 18,446,744,073,709,551,615如果每秒移动一次，一年有31,536,000秒，则僧侣们一

27、刻不停地来回移动，也需要花费5849亿年的时间；假定计算机以每秒1000万个碟子的速度进行移动，则需要花费58,490年的时间。理论上可以计算的问题，实际上并不一定能行，这属于计算复杂性领域的研究内容。认识计算机学科证比求易问题与证比求易问题与NP完全问题完全问题在计算复杂性领域中，一般认为求解一个问题往往比较困难，但验证一个问题相对来说就比较容易证比求易。 求大整数S=49,770,428,644,836,899的因子是个难解问题，但是验证a=223,092,871是不是大整数S的因子却很容易；求一个线性方程组的解可能很困难，但是验证一组解是否是方程组的解却很容易。认识计算机学科证比求易问题

28、与证比求易问题与NP完全问题完全问题在计算复杂性领域中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有可以在多项式时间内验证的问题称为NP类问题。P=NP是否成立是计算科学和当代数学研究中最大的悬而未决的问题之一。 20世纪70年代初，库克在证明了NP类中某些问题的复杂性与整个NP类的复杂性有关，当这些问题中的任何一个存在多项式时间算法，则所有这些NP类问题都是在多项式时间内可解决的，这些问题称为NP完全问题。 认识计算机学科TSP问题与组合爆炸问题与组合爆炸 TSP问题（又称货郎担问题、邮递员问题、售货员问题）是数学家克克曼于19世纪初提出的一个数学问题，是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。 由于TSP问题有着貌似简单的表述、重要的应用、以及和其他NP完全问题的重要关系，它在近20