第2章计算科学优秀课件.ppt

《第2章计算科学优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章计算科学优秀课件.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章计算科学第1页，本讲稿共61页 第2章 计算科学 主要内容 2.1 计算理论 布尔代数 有穷自动机 图灵机 2.2 计算科学概述 计算科学的基本问题计算科学的基本内容计算科学与其他学科的关系2第2页，本讲稿共61页主要内容2.3 2.3 计算科学中的典型问题计算科学中的典型问题 七桥问题七桥问题 四色问题四色问题 3636军官问题军官问题 HanoiHanoi问题问题 汉密尔顿回路问题汉密尔顿回路问题 哲学家就餐问题哲学家就餐问题2.4 2.4 计算机学科的典型方法计算机学科的典型方法抽象方法抽象方法构造性方法构造性方法公理化方法公理化方法形式化方法形式化方法原型方法和演化方法原型方法和

2、演化方法3第3页，本讲稿共61页2.1 计算理论 1985年春，ACM和IEEE-CS联手组成攻关组，开始了“计算机作为一门学科”的存在性证明，其中对计算机学科作了以下定义：计算机学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。它来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储电子计算机一起形成于20世纪40年代中期。19世纪中期至20世纪中期诞生的布尔逻辑代数、图灵机模型和存储程序思想，促进了现代电子计算机的诞生，也构成了现代计算机科学的理论基础。4第4页，本讲稿共61页 2.1.1 布尔代数George Boole181518

3、64 布尔代数是英国数学家布尔为了研究思维规律于1847年和1854年提出的。布尔代数在创立时与计算机无关，但它的理论和方法为后来的数字电子学、自动化技术以及计算机的逻辑设计等提供了重要的理论基础。逻辑的数学分析思维的规律5第5页，本讲稿共61页 布尔的父亲是一位鞋匠，他布尔的父亲是一位鞋匠，他16岁起成为一名中学教师；从岁起成为一名中学教师；从20岁起布尔对岁起布尔对数学产生了浓厚兴趣，并广泛涉猎了著名数学家牛顿、拉普拉斯、拉格朗日、数学产生了浓厚兴趣，并广泛涉猎了著名数学家牛顿、拉普拉斯、拉格朗日、高斯等人的数学著作；高斯等人的数学著作；1839年，年，24岁的布尔决心尝试接受正规教育，并

4、申请进剑桥大学。当时岁的布尔决心尝试接受正规教育，并申请进剑桥大学。当时剑桥大学期刊剑桥大学期刊的主编格雷戈里表示反对他去上大学，他说：的主编格雷戈里表示反对他去上大学，他说：“如果你为如果你为了一个学位而决定上大学学习，那么你就必须准备忍受大量不适合于习惯独了一个学位而决定上大学学习，那么你就必须准备忍受大量不适合于习惯独立思考的人的思想戒律。这里，一个高级的学位要求在指定的课程上花费的立思考的人的思想戒律。这里，一个高级的学位要求在指定的课程上花费的辛勤劳动与才能训练方面花费的劳动同样多。如果一个人不能把自己的全部辛勤劳动与才能训练方面花费的劳动同样多。如果一个人不能把自己的全部精力集中于

5、学位考试的训练，那么在学业结束时，他很可能发现自己被淘汰精力集中于学位考试的训练，那么在学业结束时，他很可能发现自己被淘汰了。了。”于是，布尔放弃了受高等教育的念头，潜心致力于他自己的数学研究。于是，布尔放弃了受高等教育的念头，潜心致力于他自己的数学研究。1847年，布尔发表了第一部著作年，布尔发表了第一部著作逻辑的数学分析逻辑的数学分析；1854年，布尔发表了一部主要的著作年，布尔发表了一部主要的著作思维规律研究思维规律研究；1857年，布尔被推选为伦敦皇家学会会员。年，布尔被推选为伦敦皇家学会会员。6第6页，本讲稿共61页罗素与布尔代数 与所有的新生事物一样，布尔代数与所有的新生事物一样，

6、布尔代数发明后没有受到人们的重视。发明后没有受到人们的重视。20世纪初，世纪初，伟大的数学家罗素在伟大的数学家罗素在数学原理数学原理中指中指出，出，“纯数学是布尔在一部他称之为纯数学是布尔在一部他称之为思维规律思维规律的著作中发现的的著作中发现的”。今天，。今天，逻辑代数已经发展成为纯数学的一个主逻辑代数已经发展成为纯数学的一个主要分支。要分支。B.A.W.Russell187219707第7页，本讲稿共61页2.1.1 布尔代数 布尔认为：在未来可能制造的机器里应该用两种状态来代表几乎所有的信息。这两种状态可以根据布尔代数来处理。因此，可制造出一种很简单的信息处理设备，而不需要知道所有其他变

7、量的状态。逻辑非运算逻辑非运算 0=1；1=0逻辑与运算逻辑与运算 00=0；01=0；10=0；11=1逻辑或运算逻辑或运算 00=0；01=1；10=1；11=1逻辑异或运算逻辑异或运算 0 0=0；0 1=1；1 0=1；1 1=0；等价关系等价关系 00=1；01=0；10=0；11=1蕴涵关系蕴涵关系 00=1；01=1；10=0；11=18第8页，本讲稿共61页2.1.1 2.1.1 布尔代数布尔代数布尔代数布尔代数是一个集合是一个集合A A，提供了两个二元运，提供了两个二元运算算 (逻辑与逻辑与)、(逻辑或逻辑或)，一个一元运算，一个一元运算 /逻辑非逻辑非)和两个元素和两个元素

8、0 0（逻辑假）和（逻辑假）和1 1（逻辑真），此外，对于集合（逻辑真），此外，对于集合A A的所有元素的所有元素a a、b b和和c c，下列公理成立，下列公理成立:9第9页，本讲稿共61页香农与布尔代数Possibly the most important masters thesis of the twentieth century.1938年，年仅22岁的香农在硕士论文的基础上，写就了一篇著名的论文继电器开关电路的分析，将布尔代数引入计算科学领域。C.E.Shannon19162001 Vannevar Bush 1890 1974 10第10页，本讲稿共61页布尔代数的电路实现开关A

9、开关B灯L000010100111开关A开关B灯L00001110111111第11页，本讲稿共61页2.1.1 布尔代数0=1；1=000=0；01=0；10=0；11=100=0；01=1；10=1；11=100=0；01=1；10=1；11=0；00=1；01=0；10=0；11=100=1；01=1；10=0；11=1思考：能否用电路实现其他几种布尔运算？12第12页，本讲稿共61页13第13页，本讲稿共61页香农与信息论 1948年，香农又发表了另一篇至今还在闪烁光芒的论文年，香农又发表了另一篇至今还在闪烁光芒的论文通信的数学基础通信的数学基础，从，从而给自己赢来而给自己赢来“信息论

10、之父信息论之父”的桂冠。的桂冠。1956年，他参与发起了达特茅斯人工智能会议，成为这一新学年，他参与发起了达特茅斯人工智能会议，成为这一新学科的开山鼻祖之一。科的开山鼻祖之一。14第14页，本讲稿共61页2.1.1 布尔代数 应用课程数字电子技术数字电子技术计算机组成原理计算机组成原理计算机程序设计语言计算机程序设计语言15第15页，本讲稿共61页2.1.2 有穷自动机开？关？16第16页，本讲稿共61页有穷自动机FRONTREARBOTHNEITHER （1）当感应门处于）当感应门处于CLOSED状态时，且输入是状态时，且输入是NEITHER时，下一个状态仍时，下一个状态仍将处于将处于CLO

11、SED状态；状态；（2）当感应门处于）当感应门处于CLOSED状态时，且输入是状态时，且输入是BOTH或或FRONT或或REAR时，时，下一个状态将处于下一个状态将处于OPEN状态；状态；（3）当感应门处于）当感应门处于OPEN状态时，且输入是状态时，且输入是FRONT、REAR或或BOTH时，下时，下一个状态仍将处于一个状态仍将处于OPEN状态；状态；（4）当感应门处于）当感应门处于OPEN状态时，且输入是状态时，且输入是NEITHER状态时，则下一个状状态时，则下一个状态将处于态将处于CLOSE状态。状态。17第17页，本讲稿共61页有穷自动机18第18页，本讲稿共61页有穷自动机与字符串

12、的识别#include“stdio.h”void main()int a1,a2;int sum;printf(“please input the two numbers:n”);scanf(“%d%d”,&a1,&a2);sum=a1+a2;printf(“the sum of the two numbers is%dn”,sum);C语言源程序19第19页，本讲稿共61页有穷自动机与字符串识别 从左到右一个接一个接收输入串的所有符号，读到一个符号后，沿着标有该符号的转移从一个状态移动到另一个状态。当读到最后一个符号时，自动机产生它的输出。如果有穷自动机处于一个接受状态（双圈表示）时，则输出

13、为接受，否则输出为拒绝。输入字符串：输入字符串：011011001初态终态20第20页，本讲稿共61页有穷自动机的定义有穷自动机的定义一个有穷自动机是一个五元组（一个有穷自动机是一个五元组（Q,Q,q,q0 0,F,F），其中：），其中：(1)Q(1)Q是一个是一个有限状态集有限状态集，它的每一个元素称为一个状，它的每一个元素称为一个状态；态；(2)(2)是一个是一个有穷输入字母表有穷输入字母表，它的每一个元素称为一，它的每一个元素称为一个输入字符；个输入字符；(3)(3)是一个从是一个从QQQ Q的的映射函数映射函数（状态转换函数状态转换函数），即），即 (si,a)=sj(si,a)=sj

14、且有且有sisi、sjQsjQ和和aa；(4)q(4)q0 0 Q Q，是，是初始状态初始状态（初态）；（初态）；(5)F(5)F 是是Q Q的子集，是一个的子集，是一个接受状态集接受状态集（终态集）。（终态集）。21第21页，本讲稿共61页2.1.2 有穷自动机有穷自动机五元组五元组（Q,Q,q,q0 0,F,F）状态集字母表状态转换函数初始状态接受状态集22第22页，本讲稿共61页2.1.2 有穷自动机有穷自动机 举例举例有穷自动机定义Q=q1，q2，q3=0=0，11=(q1,0)=q1,(q1,0)=q1,(q1,1)=q2,(q1,1)=q2,(q2,1)=q2,(q2,1)=q2,

15、(q2,0)=q3,(q2,0)=q3,(q3,0)=q2,(q3,0)=q2,(q3,1)=q2(q3,1)=q2q1q1是初始状态是初始状态F=q2F=q2是接受状态集是接受状态集初态终态01q1q1q2q2q3q2q3q2q2字母表字母表状状态态集集Q Q状态转换函数状态转换函数F=q2是接受状态集是接受状态集有穷自动机的两种表示方法有穷自动机的两种表示方法状态转换图状态转换图状态转换表状态转换表23第23页，本讲稿共61页自动机自动机M M的语言的语言给定自动机能够识别的所有字符串的集合给定自动机能够识别的所有字符串的集合记为记为L L（M M）=A=A又称为又称为M M识别识别A A

16、或或M M接受接受A A2.1.2 有穷自动机有穷自动机 举例举例初态终态A=A=|至少含有一个至少含有一个1并且在最后的并且在最后的1后后面有偶数个面有偶数个0（包含（包含0个）个）该自动机该自动机M M的语言的语言24第24页，本讲稿共61页识别识别a开头的开头的a、b串串2.1.2 有穷自动机有穷自动机 练习练习a01ab02aab1a识别识别a开头开头a结尾的结尾的a、b串串识别识别ab结尾的结尾的a、b串串的有穷自动机的有穷自动机02bab1a25第25页，本讲稿共61页2.1.2 有穷自动机有穷自动机 练习练习识别数学上的十进制整数的有穷自动机定义 非非0数字表示数字表示19中的任

17、意数字中的任意数字 数字表示数字表示 09中的任意数字中的任意数字s1s2数字非0数字s00非0数字数字26第26页，本讲稿共61页2.1.2 有穷自动机有穷自动机 思考思考识别数学中的识别数学中的“数数”的定义的自动机，包含的定义的自动机，包含整数、含小数点的数整数、含小数点的数提示：提示：整数部分整数部分小数部分小数部分 s1s2数字非0数字s00非0数字数字s3.s4数字数字27第27页，本讲稿共61页2.1.2 有穷自动机有穷自动机 课程应用课程应用软件工程编译原理28第28页，本讲稿共61页2.1.3 图灵机Alan Mathison Turing19121954 图灵机模型是由图灵

18、于图灵机模型是由图灵于1936年在论文年在论文论可计算数及其在判定问题中的应用论可计算数及其在判定问题中的应用（On Computable Numbers with an Application to the Encryption Problem）中提）中提出的。在该论文中，图灵回答了出的。在该论文中，图灵回答了“计算机计算机”到底是怎样一种机器，应该由哪些部分组成，到底是怎样一种机器，应该由哪些部分组成，如何进行计算和工作如何进行计算和工作。29第29页，本讲稿共61页2.1.3 图灵机 图灵机可以看成一个附有两端无穷的带子的黑箱，带子由连成串的方格组成，黑箱和带子由一指针相联。图灵机的每一

19、个移动与所读的符号、所处的状态有关。读头每次读一图灵机的每一个移动与所读的符号、所处的状态有关。读头每次读一个符号，则在所读符号所在的磁带的方格中写入一个符号，修改图灵机所个符号，则在所读符号所在的磁带的方格中写入一个符号，修改图灵机所处的状态，同时决定读头移动的方向。处的状态，同时决定读头移动的方向。30第30页，本讲稿共61页2.1.3 实现加法运算的图灵机当前状态当前单元内容要写的值移动方向要输入的新状态START*LeftADDADD01RightRETURNADD10LeftCARRYADD*RightHALTCARRY01RightRETURNCARRY10LeftCARRYCAR

20、RY*1LeftOVERFLOWOVERFLOW*RightRETURNRETURN00RightRETURNRETURN11RightRETURNRETURN*No moveHALT31第31页，本讲稿共61页2.1.3 实现加法运算的图灵机二进制101+1=110START*ADD写写*，左移指针，左移指针磁带1写写0左移左移CARRY0写写1右移右移RETURN0写写0右移右移RETURN*写写*NO MOVEHALT32第32页，本讲稿共61页（1）初始数据101 加0？（2）初始数据110加1？（3）初始数据111加1？2.1.3 实现加法运算的图灵机实现加法运算的图灵机 练习练习不

21、用加，也不能用此图灵机不用加，也不能用此图灵机溢出的处理？溢出的处理？1*111*和和*111*运算结果的区别？运算结果的区别？结果结果*111*33第33页，本讲稿共61页当前状态当前单元内容要写的值移动方向要输入的新状态START*LeftADDADD01RightRETURNADD10LeftCARRYADD*RightHALTCARRY01RightRETURNCARRY10LeftCARRYCARRY*1LeftOVERFLOWOVERFLOW*RightRETURNRETURN00RightRETURNRETURN11RightRETURNRETURN*No moveHALT2.1

22、.3 实现加法运算的图灵机实现加法运算的图灵机 练习练习图灵机的状态转换图如何画？图灵机的状态转换图如何画？34第34页，本讲稿共61页图灵测试 1950年年10月，图灵发表了月，图灵发表了计算机与智能计算机与智能（Computing Machinery and Intelligence）的论文。在这篇经典论文中，图灵进一步阐明了计算机）的论文。在这篇经典论文中，图灵进一步阐明了计算机可以具有智能的思想，并提出了一个测试机器是否有智能的方法，即可以具有智能的思想，并提出了一个测试机器是否有智能的方法，即“图灵测试图灵测试”。为人工智能的建立作出了贡献。为人工智能的建立作出了贡献。35第35页，

23、本讲稿共61页2.1.3 图灵奖 图灵奖是美国计算机协会（图灵奖是美国计算机协会（ACM）于）于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个年设立的，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰人。其名称取自计算机科学的先驱、英国科学家阿兰图灵，这个奖设立目的之一是纪念这位科学家。图灵，这个奖设立目的之一是纪念这位科学家。获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。大多数获奖者是计算机科获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。大多数获奖者是计算机科学家。学家。图灵奖是计算机界最负盛名的奖项，有图灵奖是计

24、算机界最负盛名的奖项，有“计算机界的诺贝尔奖计算机界的诺贝尔奖”之称。图灵奖对获奖者的要求极之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前图灵奖由英特尔公司和献的科学家同时获奖。目前图灵奖由英特尔公司和GOOGLE公司赞助，奖金为公司赞助，奖金为250,000美元。美元。（1）吴鹤龄，崔林.ACM图灵奖（1966-2006）-计算机发展史的缩影，高等教育出版社，2008年；（2）苏运霖译.ACM图灵奖演

25、讲集前20年（1966-1985），电子工业出版社，2005年；（3）柳婵娟等.图灵奖：历史与启示.计算机教育，2011年；36第36页，本讲稿共61页2.2 计算科学概述计算科学概述2.2.1 计算科学基本问题计算科学基本问题计算科学是计算科学是研究研究信息的描述与变换的信息的描述与变换的算法算法过程过程，包括其理论、分析、设计、效率分，包括其理论、分析、设计、效率分析、实现和应用的系统的研究析、实现和应用的系统的研究主要有三个方面的问题：主要有三个方面的问题：计算的平台与环境的问题计算的平台与环境的问题计算过程的计算过程的可操作可操作与效率问题与效率问题计算的正确性问题计算的正确性问题37

26、第37页，本讲稿共61页2.2.2 计算科学基本内容计算科学基本内容构造性数学基础构造性数学基础计算的数学理论计算的数学理论计算机组成原理、器件与体系结构计算机组成原理、器件与体系结构计算机应用基础和应用技术计算机应用基础和应用技术软件基础软件基础新一代计算机体系结构与软件开发方法学新一代计算机体系结构与软件开发方法学38第38页，本讲稿共61页2.3 计算机科学的典型问题计算机科学的典型问题1.哥德斯堡七桥问题哥德斯堡七桥问题2.四色问题四色问题3.36军官问题军官问题4.哈密尔顿回路及旅行推销员问题哈密尔顿回路及旅行推销员问题5.Hanoi塔问题塔问题6.生产者生产者-消费者问题与哲学家供

27、餐问题消费者问题与哲学家供餐问题39第39页，本讲稿共61页1.哥尼斯堡七桥问题 普雷格尔河的两条支流环绕其普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、旁，并将整个城市分成北区、东区、南区和岛南区和岛4个区域，有个区域，有7座桥将座桥将4个个区连接起来。人们常通过这区连接起来。人们常通过这7座桥座桥到各城区游玩，于是产生了一个有到各城区游玩，于是产生了一个有趣的数学难题：寻找趣的数学难题：寻找走遍这走遍这7座桥，座桥，且只许走过每座桥一次，最后又回且只许走过每座桥一次，最后又回到原出发点到原出发点的路径。的路径。40第40页，本讲稿共61页1.哥尼斯堡七桥问题L.Euler170

28、71783 欧拉用A、B、C、D四个点代表4个区，用7条线表示7座桥41第41页，本讲稿共61页2.四色问题Francis Guthrie18311899 1852年英国古斯里提出任何四种颜色给地图着色就可使相邻国家着不同的颜色。42第42页，本讲稿共61页2.四色问题Augustus De Morgan1806 1871 A student of mine Guthrie asked me today to give him a reason for a fact which I did not know was a fact and do not yet.He says that if a

29、 figure be any how divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured four colours may be wanted but not more the following is his case in which four colours are wanted.Query cannot a necessity for five or more be inven

30、ted William Rowan Hamilton 1805-1865letter43第43页，本讲稿共61页2.四色问题18781878年英国数学家凯利对四年英国数学家凯利对四色问题进行了分析，并正式色问题进行了分析，并正式向伦敦数学学会提出了这个向伦敦数学学会提出了这个问题，于是四色猜想成为世问题，于是四色猜想成为世界数学界关注的问题，并成界数学界关注的问题，并成为为世界近代三大数学难题世界近代三大数学难题之之一。一。Arthur Cayley 1821 1895 费尔马大定理费尔马大定理四色问题四色问题哥德巴赫猜想哥德巴赫猜想44第44页，本讲稿共61页2.四色问题Alfred Bra

31、y Kempe1849 1922 Percy Heawood 1861-1955 1976年,美国伊利诺依大学（University of Illinois）的数学教授哈肯（W.Haken，1928）与阿佩尔（K.Appel，1932）利用计算机证明了四色定理。他们的证明需要在计算机上计算1200小时，程序先后修改了500多次。45第45页，本讲稿共61页3.36军官问题 一天，普鲁士腓特烈大王决定举行一次盛大的阅兵典礼，打算从6支部队里面，各选出6名不同军衔的军官 各一人，合计36人，排成一个每边正好6人的方阵，要求每行每列都必须有各个部队和各种军衔的代表，既不准重复，也不能遗漏。这件事情看

32、来很好办，不料命 令传达下去之后，却根本无法执行。阅兵司令接二连三地吹哨子，喊口令，排来排去，始终不符合国王的要求，他急得像只热锅上的蚂蚁。但这已使腓特烈大王在众多外国贵宾面前窘态毕露，出足洋相。事后，腓特烈大王去请教当时欧洲第一流的大数学家欧拉，希望能找出一个解决方案。欧拉经过长期苦心研究，他终于认为国王的要求是无法满足的，也就是说，那样的6阶方阵是排不出来的。欧拉猜测：对任何非负整数k，n=4k+2 阶欧拉方都是不存在的。46第46页，本讲稿共61页 北华航天工业学院计算机系北华航天工业学院计算机系3.36军官问题4B2C5D3E1A3C1D4E2A5B2D5E3A1B4C1E4A2B5C

33、3D5A3B1C4D2E 类似这样的方阵，在数学上称为正交拉丁方。奇怪的是：类似这样的方阵，在数学上称为正交拉丁方。奇怪的是：3，4，5，7，8，9，各阶正交拉丁方都是作得出来的，偏偏就是，各阶正交拉丁方都是作得出来的，偏偏就是6阶的作不出来。阶的作不出来。47第47页，本讲稿共61页3.36军官问题 1901年，法国数学家塔里用枚举法证明了年，法国数学家塔里用枚举法证明了欧拉猜想对于欧拉猜想对于n=6是成立的，即是成立的，即6阶欧拉方是阶欧拉方是不存在的；不存在的；在在1960年前后，三位统计学家年前后，三位统计学家R.C.Bose、E.T.Parke和和S.S.Shrikhande成功地证

34、明了成功地证明了欧拉猜想对于所有的欧拉猜想对于所有的n6都是不成立的，也就都是不成立的，也就是说是说n=4k+2（k2）阶欧拉方都是不存在的。）阶欧拉方都是不存在的。Gaston Tarry1843191348第48页，本讲稿共61页4.哈密尔顿回路William Rowan Hamilton 1805-1865 在某个图中，能否找到这样的路径，从一点出发不重复地走过所有的结点，最后又回到原出发点。49第49页，本讲稿共61页TSP问题 哈密尔顿回路问题进一步被发展成为哈密尔顿回路问题进一步被发展成为“旅行推销员问题旅行推销员问题”（Traveling Salesman Problem，TSP

35、）：有若干个城市，任何两个城市之间的距离都）：有若干个城市，任何两个城市之间的距离都是确定的，一旅行商从某城市出发，必须经过每一个城市且只能在每个城是确定的，一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。使其旅行的费用最少。50第50页，本讲稿共61页应用：最短路径问题、优化组合问题 -离散数学、数据结构4.哈密尔顿回路及旅行推销员问题哈密尔顿回路及旅行推销员问题51第51页，本讲稿共61页5.Hanoi塔问题 相传印度教的天神在创造世界时

36、，建了一座神庙，庙里竖立了相传印度教的天神在创造世界时，建了一座神庙，庙里竖立了3根柱子。天神将根柱子。天神将64个直径大个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成了一座小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成了一座Hanoi塔。天塔。天神让庙里的僧侣们将第一根柱子上的盘子借助第神让庙里的僧侣们将第一根柱子上的盘子借助第2根柱子全部移到第根柱子全部移到第3根柱子上。同时规定：每次只能根柱子上。同时规定：每次只能移动一个盘子；盘子只能在移动一个盘子；盘子只能在3根柱子上来回移动而不能放在他处；在移动过程中，根柱子上来回移动而不能放在他处；在移动过

37、程中，3根柱子上的盘子根柱子上的盘子必须始终保持大盘在下，小盘在上。天神说当这必须始终保持大盘在下，小盘在上。天神说当这64个盘子全部移到第三根柱子上后，世界末日就个盘子全部移到第三根柱子上后，世界末日就要到了。要到了。52第52页，本讲稿共61页5.Hanoi塔问题53第53页，本讲稿共61页5.Hanoi塔问题令h(n)表示盘子所需要的转移盘次，则有 如果每秒移动一次，一年有如果每秒移动一次，一年有365*24*3600=31 536 000秒，僧侣们秒，僧侣们一刻不停地来回搬运，也需要花费大约一刻不停地来回搬运，也需要花费大约5849亿年的时间。假定计算机亿年的时间。假定计算机以每秒以每

38、秒10000万个盘子的速度进行搬迁，则需要花费大约万个盘子的速度进行搬迁，则需要花费大约5849年的时间。年的时间。通过这一例子，我们可以了解到：通过这一例子，我们可以了解到：理论上可以计算的问题，实际上并不理论上可以计算的问题，实际上并不一定能实现一定能实现。数据结构54第54页，本讲稿共61页6.消费者问题与哲学家共餐问题E.W.Dijkstra19302002 5个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，每个人的面前摆有一碗面条，碗的两旁各摆有一只筷子。平时哲学家思考，饥饿时取用最靠近他的两支筷子，同时拿到两支筷子才能进餐。进餐结束继续思考。如何协调5个哲学家的生

39、活进程，使得每一个哲学家最终都可以进餐。55第55页，本讲稿共61页6.消费者问题与哲学家共餐问题 （1）当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐。（2）将哲学家的活动进程修改一下，变为当拿不到右手的筷子时，就放下左手的筷子。可能存在这样的瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手的筷子，如此这样永远重复下去。死锁死锁!操作系统操作系统数据库原理数据库原理56第56页，本讲稿共61页2.4计算机学科的典型方法 抽象方法 构造性方法 公理化方法 形式化方法

40、原型方法与演化方法 57第57页，本讲稿共61页抽象方法面对五颜六色的苹果、柑橘、香蕉、菠萝，我们却说“水果”，甚至说“植物的果实”；面对千姿百态的大雁、海燕、仙鹤、天鹅，我们却说“飞禽”，甚至说“鸟纲”。抽象思维作为一种重要的思维类型，具有概括性、间接性、超然性的特点，是在分析事物时抽取事物最本质的特性而形成概念，并运用概念进行推理、判断的思维活动。58第58页，本讲稿共61页抽象方法抽象，隐藏了复杂的细节，只保留了现实目标所必须的信息。（保留了你所关心的信息）抽象无处不在！59第59页，本讲稿共61页构造性方法递归和迭代是最具代表性的构造性方法1！=1n!=n(n-1)!60第60页，本讲稿共61页本章小结1.布尔代数的基本运算：与、或、非2.有穷自动机：含义、应用、如何识别字符串，如何设计自动机。3.图灵机：理解图灵机的应用4.理解计算机科学的6个典型问题5.其余了解61第61页，本讲稿共61页