1、专业导论专业导论第第 4讲讲 计算学科的基础问题计算学科的基础问题吴伟民吴伟民计算学科的基本问题v首先介绍一个对问题进行抽象的典型实例 哥尼斯堡七桥问题。v然后，通过 “ 梵天塔 ” 问题和 “ 停机问题 ” 分别介绍学科中的可计算问题和不可计算问题。v从 “ 梵天塔 ” 问题再引出算法复杂性中的难解性问题、 P类问题和 NP类问题，证比求易算法， P NP是否成立的问题，旅行商问题与组合爆炸问题，找零问题、背包问题与贪婪算法。v要描述和实现算法，就要编写程序。 从 “ GOTO语句 ” 的争论，介绍程序设计中的结构问题； 以 “ 哲学家共餐 ” 问题为例，介绍计算机系统中的软硬件资源的管理问
2、题； 以 “ 两军问题 ” 为例介绍计算机网络的有关问题； 以 “ 图灵测试 ” 和 “ 中文屋子 ” 为例介绍人工智能的有关问题。v最后，给出计算机科学各主领域的基本问题。计算学科的基本问题4.1 引言v 科学研究从问题开始，或者说科学始于问题而科学研究从问题开始，或者说科学始于问题而非观察，尽管通过观察可以引出问题，但在观察非观察，尽管通过观察可以引出问题，但在观察时必定带有问题，带有预期的设想，漫无目的的时必定带有问题，带有预期的设想，漫无目的的观察是不存在的。观察是不存在的。v 人们对客观世界的认识过程正是一个不断提出人们对客观世界的认识过程正是一个不断提出问题和解决问题的过程，这个过
3、程反映的正是抽问题和解决问题的过程，这个过程反映的正是抽象、理论和设计象、理论和设计 3个过程之间的相互作用，它与个过程之间的相互作用，它与 3个过程在本质上是一致的。个过程在本质上是一致的。v 针对学科抽象第一的教学原则，我们先介绍一针对学科抽象第一的教学原则，我们先介绍一个对问题进行抽象的典型实例，即哥尼斯堡七桥个对问题进行抽象的典型实例，即哥尼斯堡七桥问题。然后再介绍计算学科的基本问题。问题。然后再介绍计算学科的基本问题。4.2哥尼斯堡七桥问题v 17世纪的东普鲁士有一座哥尼斯堡城 ， 城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城
4、共有 7座桥将 4个城区相连起来。v 通过这 7座桥到各城区游玩，问题 ： 寻找走遍这 7座桥的路径，要求过每座桥只许走一次，最后又回到原出发点。问题的抽象v 1736年，大数学家列昂纳德 欧拉（ L.Euler） 发表了关于 “ 哥尼斯堡七桥问题 ” 的论文 。 他 抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题了。欧拉回路v欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方法给出了三条判定规则 (判定每座桥恰好走过一次 ,不一定回到原点 , 即对欧拉路径的判定 )：v如果通奇数座桥的地方不止两个，满足
5、要求的路线是找不到的。v如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。v如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。v根据第 3点 ,可以得出 ,任一连通图存在欧拉回路的充分必要条件是所有顶点均有偶数度 .哈密尔顿回路问题v问题：在某个图 G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。v“ 哈密尔顿回路问题 ” 与 “ 欧拉回路问题 ” 的不同点 “ 哈密尔顿回路问题 ” 是访问每个结点一次，而“ 欧拉回路问题 ” 是访问每条边一次。 对图 G是否存在 “ 欧拉回路 ” 前面已给出充分必要条件，而对图 G是否存在 “ 哈密尔顿回路 ” 至今仍未找到满足该问题的充分必要条件。图论的形成和发展v欧拉的论文为图论的形成奠定了基础。v图论已广泛地应用于v计算学科v运筹学v信息论v控制论等学科v图论已成为我们对现实问题进行抽象的一个强有力的数学工具。v图论在计算学科中的作用越来越大，图论本身也得到了充分的发展。4.3 可计算问题与不可计算问题v 计算学科的问题，无非就是计算问题，从大的方面来说，分可计算问题与不可计算问题。可计算问题是存在算法可解的问题，不可计算问题是不存在算法可解的问题。v 为便于理解，下面，分别以梵天塔（ Hanoi，又译为汉诺）问题和停机问题来介绍可计算问题与不可计算问题。
