计算机学科的科学问题-PowerPointPresentation课件.ppt

1、什么是科学问题什么是科学问题 科学问题科学问题是指一定时代的科学认识主体，在是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提已完成的科学知识和科学实践的基础上，提出的出的需要解决需要解决且且有可能解决有可能解决的问题，它包含的问题，它包含一定的求解目标和应答域，但尚无确定的答一定的求解目标和应答域，但尚无确定的答案。科学问题具有如下主要特征：案。科学问题具有如下主要特征：（1）时代性）时代性 （2）混沌性）混沌性 （3）可解决性）可解决性（4）可变异性）可变异性（5）可待解性）可待解性科学问题的提出和解决是任何一个学科持续科学问题的提出和解决是任何一个学科持续发展的动力。发

2、展的动力。计算机学科的科学问题计算机学科的科学问题 1.计算的平台与环境问题计算的平台与环境问题 核心：计算问题的能行性核心：计算问题的能行性 2.计算过程的能行操作与效率问题计算过程的能行操作与效率问题 核心：算法及算法分析核心：算法及算法分析 3.计算的正确性问题计算的正确性问题 核心：各种语言的语义核心：各种语言的语义 上述基本问题普遍出现在学科的各个分支上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的科学问题。常面对而又必须解决的科学问题。计算机学科的经典问题计算机学科的经典问题 经典问题是指那些反

3、映学科某一方面内在规经典问题是指那些反映学科某一方面内在规律和本质内容的典型问题。律和本质内容的典型问题。经典问题往往以深入浅出的形式表达学科深经典问题往往以深入浅出的形式表达学科深奥的科学规律和本质内容，在学科研究中常奥的科学规律和本质内容，在学科研究中常常用来辅助说明思想、原理、方法和技术。常用来辅助说明思想、原理、方法和技术。1968年，计算机科学家狄杰斯年，计算机科学家狄杰斯特拉首次提出了特拉首次提出了GOTO语句是语句是有害的。有害的。1974年，计算机科学家克努斯年，计算机科学家克努斯发表论文发表论文带有带有GOTO语句的语句的结构化程序设计结构化程序设计作了较全面作了较全面而公正

4、的论述。而公正的论述。面条程序示例面条程序示例GOTO语句问题与程序设计方法学语句问题与程序设计方法学GOTO语句问题与程序设计方法学语句问题与程序设计方法学 滥用滥用GOTO语句是有害的，完全禁止也语句是有害的，完全禁止也是不明智的，在不破坏程序良好结构的前提是不明智的，在不破坏程序良好结构的前提下，有限制地使用下，有限制地使用GOTO语句，有可能使程语句，有可能使程序更清晰、效率更高。序更清晰、效率更高。关于关于“GOTO语句语句”问题的争论直接导问题的争论直接导致了一个新的学科分支领域致了一个新的学科分支领域程序设计方程序设计方法学的产生，它是一个对程序的性质及其设法学的产生，它是一个对

5、程序的性质及其设计的理论和方法进行研究的学科。计的理论和方法进行研究的学科。哥尼斯堡七桥问题与图论哥尼斯堡七桥问题与图论东区东区北区北区岛区岛区南区南区CADB哥尼斯堡七桥问题：是否能哥尼斯堡七桥问题：是否能在一次步行中穿越全部的七在一次步行中穿越全部的七座桥后回到起点，且每座桥座桥后回到起点，且每座桥只经过一次。只经过一次。哥尼斯堡七桥问题与图论哥尼斯堡七桥问题与图论欧拉回路的判定规则：欧拉回路的判定规则：（1）如果通奇数桥的地方多于两个，则不存在）如果通奇数桥的地方多于两个，则不存在欧拉回路；欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两）如果只有两个地方通奇数桥，可以从这两个地方之

6、一出发，找到欧拉回路；个地方之一出发，找到欧拉回路；（3）如果没有一个地方是通奇数桥的，则无论）如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。从哪里出发，都能找到欧拉回路。CADB哈密顿回路问题哈密顿回路问题哈密顿回路：要求哈密顿回路：要求从一个城市出发，从一个城市出发，经过每个城市恰好经过每个城市恰好一次，然后回到出一次，然后回到出发城市。发城市。1983141202131545679101112161718哲学家共餐问题与进程同步哲学家共餐问题与进程同步 哲学家的生活进程可表示为：哲学家的生活进程可表示为：（1）思考问题；）思考问题；（2）俄了停止思考，左手拿起一只）俄

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

8、同时拿起左手筷子时，则所有哲学家都将拿不到右手筷子，并处于左手筷子时，则所有哲学家都将拿不到右手筷子，并处于等待状态，那么，哲学家都将无法进餐，最终饿死。等待状态，那么，哲学家都将无法进餐，最终饿死。（2）将哲学家的生活进程修改为当拿不到右手筷子时，）将哲学家的生活进程修改为当拿不到右手筷子时，就放下左手筷子。但是，可能在一个瞬间，所有的哲学家就放下左手筷子。但是，可能在一个瞬间，所有的哲学家都同时拿起左手筷子，则自然拿不到右手筷子，于是都同都同时拿起左手筷子，则自然拿不到右手筷子，于是都同时放下左手筷子，等一会，又同时拿起左手筷子，如此重时放下左手筷子，等一会，又同时拿起左手筷子，如此重复下

9、去，则所有的哲学家都将无法进餐。复下去，则所有的哲学家都将无法进餐。汉诺塔问题与计算复杂性汉诺塔问题与计算复杂性汉诺塔问题：在世界刚被创建的时候有一座钻石汉诺塔问题：在世界刚被创建的时候有一座钻石宝塔（塔宝塔（塔A），其上有），其上有64个金碟。所有碟子按从个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔有另外两个钻石宝塔（塔B和塔和塔C）。从世界创）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔上的碟子移动到塔C上去，其间借助于塔上去，其间借助于塔B的帮

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

11、(21)1(2)(1211212nnnnhnhnhnhnh汉诺塔问题与计算复杂性汉诺塔问题与计算复杂性 64个碟子的汉诺塔问题，需要移动的碟子数为：个碟子的汉诺塔问题，需要移动的碟子数为：264118,446,744,073,709,551,615 如果每秒移动一次，一年有如果每秒移动一次，一年有31,536,000秒，则僧秒，则僧侣们一刻不停地来回移动，也需要花费侣们一刻不停地来回移动，也需要花费5849亿年的亿年的时间；时间；假定计算机以每秒假定计算机以每秒1000万个碟子的速度进行移动，万个碟子的速度进行移动，则需要花费则需要花费58,490年的时间。年的时间。理论上可以计算的问题，实际

12、上并不一定能行，理论上可以计算的问题，实际上并不一定能行，这属于计算复杂性领域的研究内容。这属于计算复杂性领域的研究内容。证比求易问题与证比求易问题与NP完全问题完全问题 在计算复杂性领域中，一般认为求解一个问在计算复杂性领域中，一般认为求解一个问题往往比较困难，但验证一个问题相对来说就题往往比较困难，但验证一个问题相对来说就比较容易比较容易证比求易。证比求易。求大整数求大整数S=49,770,428,644,836,899的因子是个的因子是个难解问题，但是验证难解问题，但是验证a=223,092,871是不是大整是不是大整数数S的因子却很容易；的因子却很容易；求一个线性方程组的解可能很困难，

13、但是验求一个线性方程组的解可能很困难，但是验证一组解是否是方程组的解却很容易。证一组解是否是方程组的解却很容易。证比求易问题与证比求易问题与NP完全问题完全问题在计算复杂性领域中，将所有可以在多项式时在计算复杂性领域中，将所有可以在多项式时间内求解的问题称为间内求解的问题称为P类问题类问题，而将所有可以，而将所有可以在多项式时间内验证的问题称为在多项式时间内验证的问题称为NP类问题类问题。P=NP是否成立是计算科学和当代数学研究中是否成立是计算科学和当代数学研究中最大的悬而未决的问题之一。最大的悬而未决的问题之一。20世纪世纪70年代初，库克在证明了年代初，库克在证明了NP类中某些问类中某些问

14、题的复杂性与整个题的复杂性与整个NP类的复杂性有关，当这类的复杂性有关，当这些问题中的任何一个存在多项式时间算法，则些问题中的任何一个存在多项式时间算法，则所有这些所有这些NP类问题都是在多项式时间内可解类问题都是在多项式时间内可解决的，这些问题称为决的，这些问题称为NP完全问题完全问题。TSP问题与组合爆炸问题与组合爆炸 TSP问题（又称货郎担问题、邮递员问题、问题（又称货郎担问题、邮递员问题、售货员问题）是数学家克克曼于售货员问题）是数学家克克曼于19世纪初提出世纪初提出的一个数学问题，是指旅行家要旅行的一个数学问题，是指旅行家要旅行n个城市个城市然后回到出发城市，要求各个城市经历且仅经然

15、后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。历一次，并要求所走的路程最短。由于由于TSP问题有着貌似简单的表述、重要问题有着貌似简单的表述、重要的应用、以及和其他的应用、以及和其他NP完全问题的重要关系，完全问题的重要关系，它在近它在近200年的时间里强烈地吸引着计算机科年的时间里强烈地吸引着计算机科学工作者。学工作者。TSP问题与组合爆炸问题与组合爆炸8abdc23571否否 18adcba6否否 23adbca5是是 11acdba4否否 23acbda3是是 11abdca2否否 18abcda1是否最短是否最短路径长度路径长度路径路径序号序号 10城市的城市的T

16、SP问题有大约问题有大约180,000个可能解。个可能解。20城市的城市的TSP问题有大约问题有大约60,000,000,000,000,000个个可能解。可能解。50城市的城市的TSP问题有大约问题有大约1062个可能解，而一个行个可能解，而一个行星上也只有星上也只有1021升水。升水。TSP问题与组合爆炸问题与组合爆炸对于具有对于具有n个顶点的个顶点的TSP问题，可能的解有：问题，可能的解有：(n-1)!/2个。个。组合爆炸组合爆炸组合优化问题：寻找一个组合对象，比如一个组合优化问题：寻找一个组合对象，比如一个排列或一个组合，这个对象能够满足特定的约排列或一个组合，这个对象能够满足特定的约

17、束条件并使得某个目标函数取得极值。束条件并使得某个目标函数取得极值。无论从理论的观点还是实践的观点，组合优化无论从理论的观点还是实践的观点，组合优化问题都是计算领域中最难的问题，其原因是：问题都是计算领域中最难的问题，其原因是：（1）随着问题规模的增大，组合对象的数量增）随着问题规模的增大，组合对象的数量增长产生组合爆炸；长产生组合爆炸；（2）还没有一种已知算法能在可接受的时间内，）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。精确地求解绝大多数这类问题。图灵测试与人工智能图灵测试与人工智能提问者提问者回答者回答者A 回答者回答者B图灵测试与人工智能图灵测试与人工智能行为主

18、义（弱行为主义（弱AI）：不要求接受测试的思维机器）：不要求接受测试的思维机器在内部构造上与人脑相同，而只是从功能的角度在内部构造上与人脑相同，而只是从功能的角度来判定机器是否具有思维，也就是从行为角度对来判定机器是否具有思维，也就是从行为角度对机器思维进行定义。机器思维进行定义。符号主义（强符号主义（强AI）：认知是一种符号处理过程，）：认知是一种符号处理过程，人类思维过程也可以用某种符号来描述。人类思维过程也可以用某种符号来描述。由于人们对心理学和生物学的认识还很不成熟，由于人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正了解，更无法建立起人对人脑的结构还没有真正了解，更无法建

19、立起人脑思维完整的数学模型。因此，到目前为止，思脑思维完整的数学模型。因此，到目前为止，思维就是计算的思想没有实质性的突破。维就是计算的思想没有实质性的突破。图灵测试与人工智能图灵测试与人工智能 1994年年11月，美国科学家阿德勒曼教授发表了月，美国科学家阿德勒曼教授发表了论文论文解决组合问题的分子计算解决组合问题的分子计算。该论文论证了该论文论证了DNA（脱氧核糖核酸）计算技术（脱氧核糖核酸）计算技术的可行性，并用的可行性，并用DNA技术解决了一个简单的有向技术解决了一个简单的有向哈密顿回路问题。哈密顿回路问题。2002年，阿德勒曼教授应用年，阿德勒曼教授应用DNA技术解决了具技术解决了具有有200万种可能结果的有向哈密顿回路问题。万种可能结果的有向哈密顿回路问题。阿德勒曼教授的工作从一个侧面探讨了生命过阿德勒曼教授的工作从一个侧面探讨了生命过程就是一种计算的思想。程就是一种计算的思想。