第2章计算科学精选文档.ppt

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

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

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

3、计算机的诞生，也构成了现代计算机科学的理论基础。4本讲稿第四页，共六十一页 2.1.1 2.1.1 布尔代数布尔代数George Boole18151864 布尔代数是英国数学家布尔为了研究思维规律于1847年和1854年提出的。布尔代数在创立时与计算机无关，但它的理论和方法为后来的数字电子学、自动化技术以及计算机的逻辑设计等提供了重要的理论基础。逻辑的数学分析逻辑的数学分析思维的规律思维的规律5本讲稿第五页，共六十一页 布尔的父亲是一位鞋匠，他布尔的父亲是一位鞋匠，他16岁起成为一名中学教师；从岁起成为一名中学教师；从20岁起布尔对数学产岁起布尔对数学产生了浓厚兴趣，并广泛涉猎了著名数学家牛

4、顿、拉普拉斯、拉格朗日、高斯等生了浓厚兴趣，并广泛涉猎了著名数学家牛顿、拉普拉斯、拉格朗日、高斯等人的数学著作；人的数学著作；1839年，年，24岁的布尔决心尝试接受正规教育，并申请进剑桥大学。当时岁的布尔决心尝试接受正规教育，并申请进剑桥大学。当时剑桥大学期刊剑桥大学期刊的主编格雷戈里表示反对他去上大学，他说：的主编格雷戈里表示反对他去上大学，他说：“如果你为了一个学位而决定上大学学如果你为了一个学位而决定上大学学习，那么你就必须准备忍受大量不适合于习惯独立思考的人的思想戒律。这里，一个高习，那么你就必须准备忍受大量不适合于习惯独立思考的人的思想戒律。这里，一个高级的学位要求在指定的课程上花

5、费的辛勤劳动与才能训练方面花费的劳动同样多。如果级的学位要求在指定的课程上花费的辛勤劳动与才能训练方面花费的劳动同样多。如果一个人不能把自己的全部精力集中于学位考试的训练，那么在学业结束时，他很可能发一个人不能把自己的全部精力集中于学位考试的训练，那么在学业结束时，他很可能发现自己被淘汰了。现自己被淘汰了。”于是，布尔放弃了受高等教育的念头，潜心致力于他自己的数学于是，布尔放弃了受高等教育的念头，潜心致力于他自己的数学研究。研究。1847年，布尔发表了第一部著作年，布尔发表了第一部著作逻辑的数学分析逻辑的数学分析；1854年，布尔发表了一部主要的著作年，布尔发表了一部主要的著作思维规律研究思维

6、规律研究；1857年，布尔被推选为伦敦皇家学会会员。年，布尔被推选为伦敦皇家学会会员。6本讲稿第六页，共六十一页罗素与布尔代数 与所有的新生事物一样，布尔代数发与所有的新生事物一样，布尔代数发明后没有受到人们的重视。明后没有受到人们的重视。20世纪初，伟世纪初，伟大的数学家罗素在大的数学家罗素在数学原理数学原理中指出，中指出，“纯数学是布尔在一部他称之为纯数学是布尔在一部他称之为思维规律思维规律的的著作中发现的著作中发现的”。今天，逻辑代数已经发展成。今天，逻辑代数已经发展成为纯数学的一个主要分支。为纯数学的一个主要分支。B.A.W.Russell187219707本讲稿第七页，共六十一页2.

7、1.1 2.1.1 布尔代数布尔代数 布尔认为：布尔认为：在未来可能制造的机器里应该用两种状态来代表几乎所在未来可能制造的机器里应该用两种状态来代表几乎所有的信息有的信息。这两种状态可以根据布尔代数来处理。因此，可制造出。这两种状态可以根据布尔代数来处理。因此，可制造出一种很简单的信息处理设备，而不需要知道所有其他变量的状态一种很简单的信息处理设备，而不需要知道所有其他变量的状态。逻辑非运算逻辑非运算 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

8、；1 1=0；等价关系等价关系 00=1；01=0；10=0；11=1蕴涵关系蕴涵关系 00=1；01=1；10=0；11=18本讲稿第八页，共六十一页2.1.1 2.1.1 布尔代数布尔代数布尔代数布尔代数是一个集合是一个集合A A，提供了两个二元运，提供了两个二元运算算 (逻辑与逻辑与)、(逻辑或逻辑或)，一个一元运算，一个一元运算 /逻辑非逻辑非)和两个元素和两个元素0 0（逻辑假）和（逻辑假）和1 1（逻辑真），此外，对于集合（逻辑真），此外，对于集合A A的所有元素的所有元素a a、b b和和c c，下列公理成立，下列公理成立:9本讲稿第九页，共六十一页香农与布尔代数Possibly

9、 the most important masters thesis of the twentieth century.Possibly the most important masters thesis of the twentieth century.1938年，年仅年，年仅22岁的香农在硕士论文的基础上，写就了一篇著名的论文岁的香农在硕士论文的基础上，写就了一篇著名的论文继电器开关继电器开关电路的分析电路的分析，将，将布尔代数布尔代数引入计算科学领域。引入计算科学领域。C.E.Shannon19162001 Vannevar Bush 1890 1974 10本讲稿第十页，共六十一页布尔

10、代数的电路实现开关A开关B灯L000010100111开关A开关B灯L00001110111111本讲稿第十一页，共六十一页2.1.1 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本讲稿第十二页，共六十一页13本讲稿第十三页，共六十一页香农与信息论 1948年，香农又发表了另一篇至今还在闪烁光芒的论文年，香农又发表了另一篇至今还

11、在闪烁光芒的论文通信的数学基础通信的数学基础，从而给，从而给自己赢来自己赢来“信息论之父信息论之父”的桂冠。的桂冠。1956年，他参与发起了达特茅斯人工智能会议，成为年，他参与发起了达特茅斯人工智能会议，成为这一新学科的开山鼻祖之一。这一新学科的开山鼻祖之一。14本讲稿第十四页，共六十一页2.1.1 布尔代数 应用课程数字电子技术数字电子技术计算机组成原理计算机组成原理计算机程序设计语言计算机程序设计语言15本讲稿第十五页，共六十一页2.1.2 2.1.2 有穷自动机有穷自动机开？开？关？关？16本讲稿第十六页，共六十一页有穷自动机有穷自动机FRONTREARBOTHNEITHER （1）当感

12、应门处于）当感应门处于CLOSED状态时，且输入是状态时，且输入是NEITHER时，下一个状态仍将处于时，下一个状态仍将处于CLOSED状态；状态；（2）当感应门处于）当感应门处于CLOSED状态时，且输入是状态时，且输入是BOTH或或FRONT或或REAR时，下一个时，下一个状态将处于状态将处于OPEN状态；状态；（3）当感应门处于）当感应门处于OPEN状态时，且输入是状态时，且输入是FRONT、REAR或或BOTH时，下一个状态仍时，下一个状态仍将处于将处于OPEN状态；状态；（4）当感应门处于）当感应门处于OPEN状态时，且输入是状态时，且输入是NEITHER状态时，则下一个状态将处于状

13、态时，则下一个状态将处于CLOSE状态。状态。17本讲稿第十七页，共六十一页有穷自动机有穷自动机18本讲稿第十八页，共六十一页有穷自动机与字符串的识别有穷自动机与字符串的识别#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本讲稿第十九页，共六十一页有穷自动机与字符串识别 从左到右一个接一个接收输入串

14、的所有符号，读到一个符号后，从左到右一个接一个接收输入串的所有符号，读到一个符号后，沿着标有该符号的转移从一个状态移动到另一个状态。当读到最沿着标有该符号的转移从一个状态移动到另一个状态。当读到最后一个符号时，自动机产生它的输出。如果有穷自动机处于一个后一个符号时，自动机产生它的输出。如果有穷自动机处于一个接受状态（双圈表示）时，则输出为接受，否则输出为拒绝。接受状态（双圈表示）时，则输出为接受，否则输出为拒绝。输入字符串：输入字符串：011011001初态初态终态终态20本讲稿第二十页，共六十一页有穷自动机的定义有穷自动机的定义一个有穷自动机是一个五元组（一个有穷自动机是一个五元组（Q,Q,

15、q,q0 0,F,F），其中：），其中：(1)Q(1)Q是一个是一个有限状态集有限状态集，它的每一个元素称为一个，它的每一个元素称为一个状态；状态；(2)(2)是一个是一个有穷输入字母表有穷输入字母表，它的每一个元素称为一，它的每一个元素称为一个输入字符；个输入字符；(3)(3)是一个从是一个从QQQ Q的的映射函数映射函数（状态转换函数状态转换函数），），即即 (si,a)=sj(si,a)=sj且有且有sisi、sjQsjQ和和aa；(4)q(4)q0 0 Q Q，是，是初始状态初始状态（初态）；（初态）；(5)F(5)F 是是Q Q的子集，是一个的子集，是一个接受状态集接受状态集（终态集

16、）。（终态集）。21本讲稿第二十一页，共六十一页2.1.2 有穷自动机有穷自动机五元组五元组（Q,Q,q,q0 0,F,F）状态集字母表状态转换函数初始状态接受状态集22本讲稿第二十二页，共六十一页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,(q2,0)=q3,(q2,0)=q3,(q3,0)=q2,(q3,0)=q2,(q3,1)=q2(q3,1)=q2q1q1是初始状态是初始状态F=q2F=q2是接受状态集是接受状态集初态初

17、态终态终态01q1q1q2q2q3q2q3q2q2字母表字母表状状态态集集Q Q状态转换函数状态转换函数F=q2是接受状态集是接受状态集有穷自动机的两种表示方法有穷自动机的两种表示方法状态转换图状态转换图状态转换表状态转换表23本讲稿第二十三页，共六十一页自动机自动机M M的语言的语言给定自动机能够识别的所有字符串的集合给定自动机能够识别的所有字符串的集合记为记为L L（M M）=A=A又称为又称为M M识别识别A A或或M M接受接受A A2.1.2 有穷自动机有穷自动机 举例举例初态初态终态终态A=A=|至少含有一个至少含有一个1并且在最后的并且在最后的1后面有偶后面有偶数个数个0（包含（

18、包含0个）个）该自动机该自动机M M的语言的语言24本讲稿第二十四页，共六十一页识别识别a开头的开头的a、b串串2.1.2 有穷自动机有穷自动机 练习练习a01ab02aab1a识别识别a开头开头a结尾的结尾的a、b串串识别识别ab结尾的结尾的a、b串的串的有穷自动机有穷自动机02bab1a25本讲稿第二十五页，共六十一页2.1.2 有穷自动机有穷自动机 练习练习识别数学上的十进制整数的有穷自动机定义 非非0数字表示数字表示19中的任意数字中的任意数字 数字表示数字表示 09中的任意数字中的任意数字s1s2数字数字非非0数字数字s00非非0数字数字数字数字26本讲稿第二十六页，共六十一页2.1

19、.2 有穷自动机有穷自动机 思考思考识别数学中的识别数学中的“数数”的定义的自动机，包的定义的自动机，包含整数、含小数点的数含整数、含小数点的数提示：提示：整数部分整数部分小数部分小数部分 s1s2数字数字非非0数字数字s00非非0数字数字数字数字s3.s4数数字字数字数字27本讲稿第二十七页，共六十一页2.1.2 有穷自动机有穷自动机 课程应用课程应用软件工程编译原理28本讲稿第二十八页，共六十一页2.1.3 2.1.3 图灵机图灵机Alan Mathison Turing19121954 图灵机模型是由图灵于图灵机模型是由图灵于1936年在论文年在论文论可计论可计算数及其在判定问题中的应用

20、算数及其在判定问题中的应用（On Computable Numbers with an Application to the Encryption Problem）中提出的。在该论文中，图灵回答了）中提出的。在该论文中，图灵回答了“计算机计算机”到底是怎样一种机器，应该由哪些到底是怎样一种机器，应该由哪些部分组成，如何进行计算和工作部分组成，如何进行计算和工作。29本讲稿第二十九页，共六十一页2.1.3 2.1.3 图灵机图灵机 图灵机可以看成一个附有两端无穷的带子的黑箱，带子由连成串的方格组成，黑箱和带子由一指针相联。图灵机的每一个移动与所读的符号、所处的状态有关。读头每次读一个符号，则图灵

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

22、OWOVERFLOW*RightRETURNRETURN00RightRETURNRETURN11RightRETURNRETURN*No moveHALT31本讲稿第三十一页，共六十一页2.1.3 2.1.3 实现加法运算的图灵机实现加法运算的图灵机二进制二进制101+1=110START*ADD写写*，左移指针，左移指针磁磁带带1写写0左移左移CARRY0写写1右移右移RETURN0写写0右移右移RETURN*写写*NO MOVEHALT32本讲稿第三十二页，共六十一页（1）初始数据101 加0？（2）初始数据110加1？（3）初始数据111加1？2.1.3 实现加法运算的图灵机实现加法运

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

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

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

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

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

28、与效率问题与效率问题计算的正确性问题计算的正确性问题37本讲稿第三十七页，共六十一页2.2.2 计算科学基本内容计算科学基本内容构造性数学基础构造性数学基础计算的数学理论计算的数学理论计算机组成原理、器件与体系结构计算机组成原理、器件与体系结构计算机应用基础和应用技术计算机应用基础和应用技术软件基础软件基础新一代计算机体系结构与软件开发方法学新一代计算机体系结构与软件开发方法学38本讲稿第三十八页，共六十一页2.3 计算机科学的典型问题计算机科学的典型问题1.哥德斯堡七桥问题哥德斯堡七桥问题2.四色问题四色问题3.36军官问题军官问题4.哈密尔顿回路及旅行推销员问题哈密尔顿回路及旅行推销员问题

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

30、40本讲稿第四十页，共六十一页1.哥尼斯堡七桥问题L.Euler17071783 欧拉用欧拉用A、B、C、D四个点代表四个点代表4个区，个区，用用7条线表示条线表示7座桥座桥41本讲稿第四十一页，共六十一页2.四色问题Francis Guthrie18311899 1852年英国古斯里提出任何四种颜色给地年英国古斯里提出任何四种颜色给地图着色就可使相邻国家着不同的颜色。图着色就可使相邻国家着不同的颜色。42本讲稿第四十二页，共六十一页2.四色问题Augustus De Morgan1806 1871 A student of mine Guthrie asked me today to giv

31、e him a reason for a fact which I did not know was a fact and do not yet.He says that if a 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 hi

32、s case in which four colours are wanted.Query cannot a necessity for five or more be invented William Rowan Hamilton 1805-1865letter43本讲稿第四十三页，共六十一页2.四色问题18781878年英国数学家凯利对四年英国数学家凯利对四色问题进行了分析，并正式色问题进行了分析，并正式向伦敦数学学会提出了这个向伦敦数学学会提出了这个问题，于是四色猜想成为世问题，于是四色猜想成为世界数学界关注的问题，并成界数学界关注的问题，并成为为世界近代三大数学难题世界近代三大数学难题

33、之之一。一。Arthur Cayley 1821 1895 费尔马大定理费尔马大定理四色问题四色问题哥德巴赫猜想哥德巴赫猜想44本讲稿第四十四页，共六十一页2.四色问题Alfred Bray Kempe1849 1922 Percy Heawood 1861-1955 1976年年,美国伊利诺依大美国伊利诺依大学（学（University of Illinois）的数学教授哈肯（的数学教授哈肯（W.Haken，1928）与阿佩尔）与阿佩尔（K.Appel，1932）利用计）利用计算机证明了四色定理。他算机证明了四色定理。他们的证明需要在计算机上们的证明需要在计算机上计算计算1200小时，程序先

34、后修小时，程序先后修改了改了500多次。多次。45本讲稿第四十五页，共六十一页3.36军官问题 一天，普鲁士腓特烈大王决定举行一次盛大的阅兵典礼，打算从一天，普鲁士腓特烈大王决定举行一次盛大的阅兵典礼，打算从6支部队里支部队里面，各选出面，各选出6名不同军衔的军官名不同军衔的军官 各一人，合计各一人，合计36人，排成一个每边正好人，排成一个每边正好6人的方阵，人的方阵，要求每行每列都必须有各个部队和各种军衔的代表，既不准重复，也不能遗漏。要求每行每列都必须有各个部队和各种军衔的代表，既不准重复，也不能遗漏。这件事情看来很好办，不料命这件事情看来很好办，不料命 令传达下去之后，却根本无法执行。阅

35、兵司令接令传达下去之后，却根本无法执行。阅兵司令接二连三地吹哨子，喊口令，排来排去，始终不符合国王的要求，他急得像只热锅二连三地吹哨子，喊口令，排来排去，始终不符合国王的要求，他急得像只热锅上的蚂蚁。但这已使腓特烈大王在众多外国贵宾面前窘态毕露，出足洋相。上的蚂蚁。但这已使腓特烈大王在众多外国贵宾面前窘态毕露，出足洋相。事后，腓特烈大王去请教当时欧洲第一流的大数学家欧拉，希望能找出一个解决方案。事后，腓特烈大王去请教当时欧洲第一流的大数学家欧拉，希望能找出一个解决方案。欧拉经过长期苦心研究，他终于认为国王的要求是无法满足的，也就是说，那样的欧拉经过长期苦心研究，他终于认为国王的要求是无法满足的

36、，也就是说，那样的6阶方阶方阵是排不出来的。欧拉猜测：对任何非负整数阵是排不出来的。欧拉猜测：对任何非负整数k，n=4k+2 阶欧拉方都是不存在的。阶欧拉方都是不存在的。46本讲稿第四十六页，共六十一页 北华航天工业学院计算机系北华航天工业学院计算机系3.36军官问题4B2C5D3E1A3C1D4E2A5B2D5E3A1B4C1E4A2B5C3D5A3B1C4D2E 类似这样的方阵，在数学上称为正交拉丁方。奇怪的是：类似这样的方阵，在数学上称为正交拉丁方。奇怪的是：3，4，5，7，8，9，各阶正交拉丁方都是作得出来的，偏偏就是，各阶正交拉丁方都是作得出来的，偏偏就是6阶的作不出来。阶的作不出来

37、。47本讲稿第四十七页，共六十一页3.36军官问题 1901年，法国数学家塔里用枚举法证明年，法国数学家塔里用枚举法证明了欧拉猜想对于了欧拉猜想对于n=6是成立的，即是成立的，即6阶欧拉方阶欧拉方是不存在的；是不存在的；在在1960年前后，三位统计学家年前后，三位统计学家R.C.Bose、E.T.Parke和和S.S.Shrikhande成功成功地证明了欧拉猜想对于所有的地证明了欧拉猜想对于所有的n6都是不成都是不成立的，也就是说立的，也就是说n=4k+2（k2）阶欧拉方都）阶欧拉方都是不存在的。是不存在的。Gaston Tarry1843191348本讲稿第四十八页，共六十一页4.4.哈密尔

38、顿回路哈密尔顿回路William Rowan Hamilton 1805-1865 在某个图中，能否找到这样的路径，从一点出发不在某个图中，能否找到这样的路径，从一点出发不重复地走过所有的结点，最后又回到原出发点。重复地走过所有的结点，最后又回到原出发点。49本讲稿第四十九页，共六十一页TSP问题 哈密尔顿回路问题进一步被发展成为哈密尔顿回路问题进一步被发展成为“旅行推销员问题旅行推销员问题”（Traveling Salesman Problem，TSP）：有若干个城市，任何两个城市之间的距离都是确定的，一旅行商从某城）：有若干个城市，任何两个城市之间的距离都是确定的，一旅行商从某城市出发，必

39、须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。先确定好一条最短的路线，使其旅行的费用最少。50本讲稿第五十页，共六十一页应用：最短路径问题、优化组合问题 -离散数学、数据结构4.哈密尔顿回路及旅行推销员问题哈密尔顿回路及旅行推销员问题51本讲稿第五十一页，共六十一页5.Hanoi塔问题塔问题 相传印度教的天神在创造世界时，建了一座神庙，庙里竖立了相传印度教的天神在创造世界时，建了一座神庙，庙里竖立了3根柱子。天神将根柱子。天神将64个直径大小不个直

40、径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成了一座一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成了一座Hanoi塔。天神让塔。天神让庙里的僧侣们将第一根柱子上的盘子借助第庙里的僧侣们将第一根柱子上的盘子借助第2根柱子全部移到第根柱子全部移到第3根柱子上。同时规定：每次只根柱子上。同时规定：每次只能移动一个盘子；盘子只能在能移动一个盘子；盘子只能在3根柱子上来回移动而不能放在他处；在移动过程中，根柱子上来回移动而不能放在他处；在移动过程中，3根柱子上的盘子根柱子上的盘子必须始终保持大盘在下，小盘在上。天神说当这必须始终保持大盘在下，小盘在上。天神说当这64个盘子

41、全部移到第三根柱子上后，世界末日就要个盘子全部移到第三根柱子上后，世界末日就要到了。到了。52本讲稿第五十二页，共六十一页5.Hanoi塔问题塔问题53本讲稿第五十三页，共六十一页5.Hanoi塔问题塔问题令h(n)表示盘子所需要的转移盘次，则有 如果每秒移动一次，一年有如果每秒移动一次，一年有365*24*3600=31 536 000秒，僧侣们一秒，僧侣们一刻不停地来回搬运，也需要花费大约刻不停地来回搬运，也需要花费大约5849亿年的时间。假定计算机以亿年的时间。假定计算机以每秒每秒10000万个盘子的速度进行搬迁，则需要花费大约万个盘子的速度进行搬迁，则需要花费大约5849年的时间。通年

42、的时间。通过这一例子，我们可以了解到：过这一例子，我们可以了解到：理论上可以计算的问题，实际上并不理论上可以计算的问题，实际上并不一定能实现一定能实现。数数据据结结构构54本讲稿第五十四页，共六十一页6.消费者问题与哲学家共餐问题E.W.Dijkstra19302002 5个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，每个人的面前个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，每个人的面前摆有一碗面条，碗的两旁各摆有一只筷子。平时哲学家思考，饥饿时取用最靠近他的两支筷子，摆有一碗面条，碗的两旁各摆有一只筷子。平时哲学家思考，饥饿时取用最靠近他的两支筷子，同

43、时拿到两支筷子才能进餐。进餐结束继续思考。如何协调同时拿到两支筷子才能进餐。进餐结束继续思考。如何协调5个哲学家的生活进程，使得每一个哲个哲学家的生活进程，使得每一个哲学家最终都可以进餐。学家最终都可以进餐。55本讲稿第五十五页，共六十一页6.6.消费者问题与哲学家共餐问题消费者问题与哲学家共餐问题 （1 1）当所有的哲学家都同时拿起左手）当所有的哲学家都同时拿起左手筷子时，则筷子时，则所有的哲学家都将拿不到右手所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家的筷子，并处于等待状态，那么哲学家都将无法进餐。都将无法进餐。（2 2）将哲学家的活动进程修改一下，）将哲学家的活动进程修改

44、一下，变为当拿不到右手的筷子时，就放下左变为当拿不到右手的筷子时，就放下左手的筷子。可能存在这样的瞬间，手的筷子。可能存在这样的瞬间，所有的所有的哲学家都同时拿起左手的筷子，则自然拿不到哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子，等右手的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手的筷子，如此这样永远一会，又同时拿起左手的筷子，如此这样永远重复下去。重复下去。死锁死锁!操作系统操作系统数据库原理数据库原理56本讲稿第五十六页，共六十一页2.42.4计算机学科的典型方法计算机学科的典型方法 抽象方法抽象方法 构造性方法构造性方法 公理化方法公理化方法

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