第2章计算学科基本问题2015

1、第第2章章 计算学科的基本问题计算学科的基本问题内容提要内容提要n 对问题进行抽象的一个实例对问题进行抽象的一个实例n 可计算问题与不可计算问题可计算问题与不可计算问题n 计算学科中的其他典型科学问题计算学科中的其他典型科学问题n 计算学科的主领域及其基本问题计算学科的主领域及其基本问题1、对问题进行抽象的一个实例、对问题进行抽象的一个实例哥尼斯堡七桥问题哥尼斯堡七桥问题 17世纪在哥尼斯堡城世纪在哥尼斯堡城 ( 今俄罗斯今俄罗斯加里宁格勒加里宁格勒 ) 的普莱格尔河上有的普莱格尔河上有 7 座座桥，将河中的两个岛和河岸连结，城桥，将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提中

2、的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍出了一个问题：能否一次走遍 7 座桥，座桥，而每座桥只许通过一次，最后仍回到而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著起始地点。这就是七桥问题，一个著名的图论问题。名的图论问题。 七桥问题也困绕着哥尼斯堡大学的学生们，七桥问题也困绕着哥尼斯堡大学的学生们，在屡遭失败之后，他们请当时在屡遭失败之后，他们请当时28岁的著名数学岁的著名数学家家欧拉欧拉解决这个问题。解决这个问题。 哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉图欧拉图对现实问题的抽象对现实问题的抽象 欧拉解决问题采用了欧拉解决问题采用了“数学模型数学模型”法。法。

3、欧拉认为，既然岛与陆地是靠桥来接连的，欧拉认为，既然岛与陆地是靠桥来接连的，那么不妨把那么不妨把4片陆地缩小（抽象）成片陆地缩小（抽象）成4个点，个点，并把七座桥表示（抽象）成并把七座桥表示（抽象）成7条边，从而得条边，从而得到了七桥问题的模拟图，这样当然未改变到了七桥问题的模拟图，这样当然未改变问题的实质，于是人们试图一次无重复地问题的实质，于是人们试图一次无重复地走过走过7座桥的问题就等价于一笔画出模拟图座桥的问题就等价于一笔画出模拟图型的问题。型的问题。欧拉经过三种抽象：欧拉经过三种抽象：o 具体事物抽象成几何对象具体事物抽象成几何对象o 实际关系抽象成几何关系实际关系抽象成几何关系o

4、问题的要求抽象成一笔画的条件问题的要求抽象成一笔画的条件 是否存在是否存在 “欧拉欧拉 回路回路” 通过这种抽象，显现出问题的本质，将实际问题转化通过这种抽象，显现出问题的本质，将实际问题转化成数学问题，使研究的对象和对象间的关系准确无误地表成数学问题，使研究的对象和对象间的关系准确无误地表述出来，就可以先在已有的数学方法、理论中寻求解法。述出来，就可以先在已有的数学方法、理论中寻求解法。在现有方法、理论中还未有解法时，就促使人们去寻找新在现有方法、理论中还未有解法时，就促使人们去寻找新的数学方法和理论，甚至开拓出数学新的分支和领域。的数学方法和理论，甚至开拓出数学新的分支和领域。 欧拉对欧拉

5、对“七桥问题七桥问题”的研究是图论研究的开始，同时也的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。为拓扑学的研究提供了一个初等的例子。哈密尔顿回路问题哈密尔顿回路问题 哈密尔顿图起源于一种游戏，英国数学家哈哈密尔顿图起源于一种游戏，英国数学家哈密尔顿于密尔顿于1859年提出的年提出的“周游世界游戏周游世界游戏”。用一个。用一个正十二面体的正十二面体的20个顶点代替个顶点代替20个城市个城市(图图1，同构，同构于一个平面图，图于一个平面图，图2)，要求沿着正十二面体的棱，要求沿着正十二面体的棱从一个城市出发，经过每个城市恰好一次，然后从一个城市出发，经过每个城市恰好一次，然后

6、回到出发点，称为回到出发点，称为哈密尔顿回路哈密尔顿回路。 抽象：抽象：在任一给定的图中，在任一给定的图中，能不能找到这样的路径，即从一能不能找到这样的路径，即从一点出发不重复地走过所有的结点点出发不重复地走过所有的结点（不必通过图中每一条边），最（不必通过图中每一条边），最后又回到原出发点。后又回到原出发点。哈密尔顿回路问题哈密尔顿回路问题 该问题进一步被发展成为所谓的该问题进一步被发展成为所谓的“货郎担问题货郎担问题”或或“旅行货郎问题旅行货郎问题”TSP，即，即赋权汉密尔顿回路最小化赋权汉密尔顿回路最小化问题问题。这两个问题成为数学史上著名的难题，而后者在。这两个问题成为数学史上著名的难

7、题，而后者在工程优化、现场管理等现实生活中有重要作用。以电站工程优化、现场管理等现实生活中有重要作用。以电站建设为例，如何使若干供货点的总运费最小，施工现场建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权汉密尔顿如何使供货时间最短等等，最终都归结为赋权汉密尔顿问题。问题。哈密尔顿回路问题与欧拉回路问题哈密尔顿回路问题与欧拉回路问题o “哈密尔顿回路问题哈密尔顿回路问题”与与“欧拉回路问题欧拉回路问题”十分相似，但却十分相似，但却是完全不同的两个问题。是完全不同的两个问题。“哈密尔顿回路问题哈密尔顿回路问题”是访问除是访问除原出发结点以外的原出发结点以外的

8、每个结点每个结点一次且仅一次，而一次且仅一次，而“欧拉回欧拉回路问题路问题”是访问是访问每条边每条边一次且仅一次。一次且仅一次。o 对任一给定的图是否存在对任一给定的图是否存在“欧拉回路欧拉回路”，欧拉已给出了充，欧拉已给出了充分必要条件分必要条件(P23)；而对任一给定的图是否存在；而对任一给定的图是否存在“哈密尔哈密尔顿回路顿回路”，至今仍未找到满足该问题的充分必要条件。，至今仍未找到满足该问题的充分必要条件。2、可计算问题与不可计算问题、可计算问题与不可计算问题梵天塔（又称汉诺塔）问题梵天塔（又称汉诺塔）问题 在印度有这么一个古老的传说：印度教的天神梵天在创造地球在印度有这么一个古老的传

9、说：印度教的天神梵天在创造地球时建了一座神庙，神庙里竖有时建了一座神庙，神庙里竖有3根宝石柱子。梵天将根宝石柱子。梵天将64个直径大小个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，即所谓梵天塔。天神让庙里的僧侣们将第一根柱子上成一座金塔，即所谓梵天塔。天神让庙里的僧侣们将第一根柱子上的的64个盘子借助第个盘子借助第2根柱子全部移到第根柱子全部移到第3根柱子上，将整个塔迁移。根柱子上，将整个塔迁移。迁移时满足以下迁移时满足以下3条规则：条规则： 每次只能移动一个盘子；每次只能移动一个盘子； 盘子只能在三根

10、柱子上来回移动，不能放在他处；盘子只能在三根柱子上来回移动，不能放在他处； 在移动过和中，三根柱子上的盘子必须始终保持大盘在下，在移动过和中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。小盘在上。 天神说：天神说：“当这当这64个盘子全部移到第三根柱子上后，世界末日个盘子全部移到第三根柱子上后，世界末日就要到了就要到了”。 ？算法：算法：C语言描述语言描述hanoi(int n, char left, char middle, char right) if(n=1) move(1, left, right); else hanoi(n-1, left, right, middle); mo

11、ve(1, left, right); hanoi(n-1, middle, left, right); 当当n=64时，移动次数时，移动次数=？花费时间？花费时间=？ h(n)=2h(n-1)+1 = 2(2h(n-2)+1)+1=22h(n-2)+2+1 = 23h(n-3)+22+2+1 =2nh(0)+2n-1+22+2+1 = 2n-1+22+2+1=2n-1需要移动盘子的次数为：需要移动盘子的次数为： 264-1=18446744073709551615o假定假定每秒移动一次每秒移动一次，一年有，一年有31536000秒，则僧侣们秒，则僧侣们 一刻不停地来回搬动，也需要花费大约一刻

12、不停地来回搬动，也需要花费大约5849亿年亿年的时间。的时间。o假定计算机以假定计算机以每秒每秒1000万万个盘子的速度进行搬迁，则需要花费个盘子的速度进行搬迁，则需要花费大约大约58490年年的时间。的时间。o梵天塔问题算法的时间复杂度可以用一个指数函数梵天塔问题算法的时间复杂度可以用一个指数函数O(2n)来表示，来表示，显然，当显然，当n很大时，计算机是无法处理的。当算法的时间复杂很大时，计算机是无法处理的。当算法的时间复杂度的表示函数是一个多项式，则可以处理。度的表示函数是一个多项式，则可以处理。o一个问题求解算法的时间复杂度大于多项式（如指数函数）时，一个问题求解算法的时间复杂度大于多

13、项式（如指数函数）时，算法的执行时间将随算法的执行时间将随n的增加而急剧增长，以致即使是中等规的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，在计算复杂性中将这一类问题称为模的问题也不能求解出来，在计算复杂性中将这一类问题称为难解性问题。难解性问题。o理论上可以计算的问题，实际上并不一定能行。理论上可以计算的问题，实际上并不一定能行。梵天塔问题梵天塔问题o 算法复杂性的数量级算法复杂性的数量级(Order)n O(1) 称为常数级称为常数级n O(logn) 称为对数级称为对数级n O(n) 称为线性级称为线性级n O(nc) 称为多项式级（称为多项式级（c为常数为常数)，如，如O(

14、n2)n O(cn)称为指数级（称为指数级（c为常数为常数)，如，如O(2n)n O(n!) 称为阶乘级称为阶乘级当时间复杂性当时间复杂性多项式时，算法的执行时间随多项式时，算法的执行时间随n增加而急剧增长。增加而急剧增长。o 可计算问题：存在算法可解的问题可计算问题：存在算法可解的问题o 不可计算的问题：不存在可解算法的问题不可计算的问题：不存在可解算法的问题 一个不可计算的问题：停机问题，一个不可计算的问题：停机问题，P32 这个问题是由图灵提出的一个不可解问题，即无法这个问题是由图灵提出的一个不可解问题，即无法在有限的时间内得到解的问题。停机问题就是能否设计在有限的时间内得到解的问题。停

15、机问题就是能否设计一个算法，判断任意一个程序是否会在有限的时间之内一个算法，判断任意一个程序是否会在有限的时间之内结束运行。或者说，能否找到这样结束运行。或者说，能否找到这样一个测试程序，它能购判断出任意一个测试程序，它能购判断出任意的程序在接收了输入并执行后能不的程序在接收了输入并执行后能不能自动终止。能自动终止。一个不可计算的问题：停机问题一个不可计算的问题：停机问题证明：证明： 设停机问题有解，即：存在过程设停机问题有解，即：存在过程H(P, I)可以给出程序可以给出程序P在输入在输入I的情况下是否可停机。假设若的情况下是否可停机。假设若P在输入在输入I时可停机，时可停机，H输出输出“停

16、机停机”，反之输出反之输出“死循环死循环”，即可导出矛盾：，即可导出矛盾： 显然，程序本身可以被视作数据，因此它可以被作为输入，故显然，程序本身可以被视作数据，因此它可以被作为输入，故H应该可以判定当将应该可以判定当将P作为作为P的输入时，的输入时，P是否会停机。我们设过程是否会停机。我们设过程K(P)的流程如下：首先调用的流程如下：首先调用H(P, P)，如果，如果H(P, P)输出输出“死循环死循环”，则则K(P)停机，反之停机，反之K(P)死循环。即死循环。即K(P)做与做与H(P, P)的输出相反的的输出相反的动作。动作。 因此，因此，H不是总能给出正确答案，故而不存在解决停机问题的不

17、是总能给出正确答案，故而不存在解决停机问题的方法。方法。o 难解性问题、难解性问题、P类问题和类问题和NP类问题类问题n 难解性问题：当时间复杂性难解性问题：当时间复杂性多项式时多项式时n P类问题：可以在多项式时间内类问题：可以在多项式时间内求解求解的问题的问题n NP类问题：可以在多项式时间内类问题：可以在多项式时间内验证验证的问题的问题n P类问题采用的是类问题采用的是确定性算法确定性算法，NP类问题采用的类问题采用的是非确定性算法是非确定性算法（如通过猜算）。（如通过猜算）。PNP。o NP完全问题完全问题：NP=P？n 是世界七大数学难题之一（首位）是世界七大数学难题之一（首位）o

18、哈密顿路径问题：可以在多项式时间类哈密顿路径问题：可以在多项式时间类判断判断一个回一个回路是否是哈密顿回路，但目前没有多项式时间类算路是否是哈密顿回路，但目前没有多项式时间类算法直接法直接求解求解出哈密顿回路。出哈密顿回路。3、计算学科中的其他典型科学问题（计算学科中的其他典型科学问题（1 1） 证比求易算法证比求易算法n 求出求出48 770 428 433 377 171的一个真因子的一个真因子 n 给出数进行验证：给出数进行验证：顺序算法顺序算法n 多人参加验证：多人参加验证：并行算法并行算法n 时间复杂性时间复杂性 空间复杂性空间复杂性n 但并行运算也存在但并行运算也存在“瓶颈瓶颈”问

19、题：问题：阿姆达尔定律阿姆达尔定律 1 Sp - （倍）（倍） 加速能力加速能力 1 - f f + - pn 设设f=1%, p ，Sp=100，最大，最大100倍倍o 直觉上认为顺序算法解决不了的问题完全可以用并直觉上认为顺序算法解决不了的问题完全可以用并行算法来解决，并且，并行计算机系统求解问题的行算法来解决，并且，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题。这是一种误解。而解决难解性问题。这是一种误解。o 阿姆达尔定律阿姆达尔定律说明：当将一个问题分解到多个处理说明：当将一个问题分解到多个处理器上解决

20、时，由于算法中不可避免地存在必须串行器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的执行的操作，从而大大地限制了并行计算机系统的加速能力。加速能力。3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（2） 旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题n 旅行商问题旅行商问题（Traveling Salesman Problem，TSP）：一个旅行商从某）：一个旅行商从某城市出发，必须经过每个城市一次切城市出发，必须经过每个城市一次切仅一次，最后回到原出发城市。如何仅一次，最后回到原出发城市。如何确定一条最短的路线，使其旅行的费确定一条最

21、短的路线，使其旅行的费用最少。用最少。n 是典型的是典型的NP完全问题完全问题：本质上难以：本质上难以求解。求解。n 是最有代表性的优化组合问题之一：是最有代表性的优化组合问题之一：割平面法与分支限界法相结合。割平面法与分支限界法相结合。旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题o 如果有如果有3个城市个城市A、B和和C，则有，则有6种访问每个城市的次序：种访问每个城市的次序：ABC，ACB，BAC，BCA，CAB，CBA；如果有；如果有4个城个城市，则有市，则有24种次序，可以用阶乘来表示：种次序，可以用阶乘来表示：4！=24；若有；若有

22、5个城市，则有个城市，则有5！=54！=120。o 如果如果n个城市，则有个城市，则有n！；！；20个城市：个城市：20！=1.2X1017。o 即使用计算机来计算，这种急剧增长的数字也远远超过即使用计算机来计算，这种急剧增长的数字也远远超过计算资源的处理能力。计算资源的处理能力。Cook评论：评论：“如果有如果有100个城市，个城市，需要求出需要求出100！条路线的费用，没有哪一台计算机能够！条路线的费用，没有哪一台计算机能够胜任这一任务。打个比方，让太阳系中所有的电子以它胜任这一任务。打个比方，让太阳系中所有的电子以它旋转的频率来计算，就算太阳烧尽了也算不完。旋转的频率来计算，就算太阳烧尽

23、了也算不完。”o 组合路线数呈指数阶急剧增长组合路线数呈指数阶急剧增长组合爆炸问题组合爆炸问题。o 将将割平面法割平面法与与分支限界法分支限界法相结合，相结合，1998年科学家们成功年科学家们成功地解决了美国地解决了美国13509个城市之间的个城市之间的TSP问题，问题，o 2001年又解决了德国年又解决了德国15112个城市之间的个城市之间的TSP问题。但问题。但这一工程代价也是巨大的：共使用了美国这一工程代价也是巨大的：共使用了美国Rice大学和普大学和普林斯顿大学之间网络互连的、由速度为林斯顿大学之间网络互连的、由速度为500MHz 的处理的处理器组成的器组成的110台计算机，所有计算机

24、花费的时间之和为台计算机，所有计算机花费的时间之和为22.6年。年。o 由于由于TSP会产生组合爆炸的问题，因此寻找切实可行的会产生组合爆炸的问题，因此寻找切实可行的简化求解方法就成为问题的关键。简化求解方法就成为问题的关键。o TSP应用：钻孔调度问题，运输问题，后勤服务问题。应用：钻孔调度问题，运输问题，后勤服务问题。旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（3）o 找零问题找零问题：设有不同面值的钞票，要求用最小数量的钞：设有不同面值的钞票，要求用最小数量的钞票给顾客找某数额的零钱。票给顾客找某数额的零钱。o 背包问

25、题背包问题：给定：给定n种物品和一个背包，要求在重量容量种物品和一个背包，要求在重量容量的限制下，使装入的物品总价值最大。的限制下，使装入的物品总价值最大。o 找零问题、背包问题等是一类可以用贪心法来处理的典找零问题、背包问题等是一类可以用贪心法来处理的典型问题。型问题。o 贪心法贪心法：是一种传统的启发式算法，它采用逐步构造最：是一种传统的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段，都作出在当时看上优解的方法，即在算法的每个阶段，都作出在当时看上去最好的决策，以获得最大的去最好的决策，以获得最大的“好处好处”；换言之，就是在；换言之，就是在每一个决策过程中都要尽可能的每一个决

26、策过程中都要尽可能的“贪贪”，直到算法中的某，直到算法中的某一步不能继续前进时，算法才停止。一步不能继续前进时，算法才停止。3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（4） 计算机资源管理计算机资源管理n 生产者生产者消费者问题：使用资源，释放资源消费者问题：使用资源，释放资源o 使用共享资源的多进程同步问题使用共享资源的多进程同步问题o 使用使用“信号灯信号灯”的概念解决进程间的互斥的概念解决进程间的互斥n “哲学家共餐哲学家共餐”问题问题o 程序并发执行时进程同步的程序并发执行时进程同步的问题：问题：“死锁死锁”和和“饥饿饥饿”o 解决：并发程序语言、解决：并发程序语

27、言、Petri网网 在计算学科诞生后，为解决人工智能中一些激烈争在计算学科诞生后，为解决人工智能中一些激烈争论的问题，图灵和西尔勒又分别提出了能反映人工智能论的问题，图灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学问题，即图灵测试和西尔勒本质特征的两个著名的哲学问题，即图灵测试和西尔勒的的“中文屋子中文屋子”。 沿着图灵等人对沿着图灵等人对“智能智能”的理解，人们在人工智能领的理解，人们在人工智能领域取得了长足的进展，其中，域取得了长足的进展，其中，“深蓝深蓝”战胜国际象棋大师卡战胜国际象棋大师卡斯帕罗夫就是一个很好的例证。斯帕罗夫就是一个很好的例证。3、计算学科中的其他典型科学

28、问题（、计算学科中的其他典型科学问题（5） 人工智能中的哲学问题人工智能中的哲学问题 图灵测试（图灵测试（Turing Test)n 1950年，图灵提出：机器能思维吗？年，图灵提出：机器能思维吗？n 一个人在不接触对象的情况下，进行一系列的提问，一个人在不接触对象的情况下，进行一系列的提问，如果他根据这些回答无法判断对象是人还是机器，如果他根据这些回答无法判断对象是人还是机器，则这种计算机具有与人相当的智力。则这种计算机具有与人相当的智力。n 模仿游戏的试验模仿游戏的试验称之为图灵测试称之为图灵测试 n 人类思维的本质？思维就是计算。人类思维的本质？思维就是计算。n 机器思维的定义？从功能的

29、角度来判定机器是否能机器思维的定义？从功能的角度来判定机器是否能思维，也就是从行为主义思维，也就是从行为主义这个角度对这个角度对“机器思维机器思维”进进行定义。行定义。 西尔勒（西尔勒（J.R.Searle）的）的“中文屋中文屋”n 1980年西尔勒在行为科学和脑科学杂志上发表年西尔勒在行为科学和脑科学杂志上发表论文，在文中他以自己为主角设计了一个中文屋论文，在文中他以自己为主角设计了一个中文屋子的假想试验，反驳了强子的假想试验，反驳了强AI的观点。的观点。n 西尔勒给出的汉字符号与一个地道的中国人作出西尔勒给出的汉字符号与一个地道的中国人作出的答案没什么不同。但是，我们能说西尔勒真的的答案没

30、什么不同。但是，我们能说西尔勒真的懂中文吗？懂中文吗？n 结论：机器永远也不能结论：机器永远也不能代替大脑代替大脑形式化的计形式化的计算机仅有语法，没有算机仅有语法，没有语义语义。人机博弈问题人机博弈问题n 转折点：转折点：1997年年“深蓝（深蓝（Deep Blue)”与卡斯帕罗夫之战。与卡斯帕罗夫之战。 前者前者二胜一负三平战胜后者。深蓝由二胜一负三平战胜后者。深蓝由256（32 node*8）个专用处理）个专用处理器组成，每秒可计算器组成，每秒可计算2亿步棋。亿步棋。n 使用博弈树搜索，寻找最佳解。国际象棋使用博弈树搜索，寻找最佳解。国际象棋10120个结点（棋局总个结点（棋局总数），中

31、国象棋数），中国象棋10160个结点，围棋个结点，围棋10768个结点个结点难解性问题。难解性问题。n 2006年在北京奥体中心进行的首届年在北京奥体中心进行的首届“浪潮杯浪潮杯”中国象棋中国象棋“人机人机大战大战”，电脑胜出，电脑胜出。o 机器智力和人的智力是二回事。机器智力和人的智力是二回事。 o 人要在计算能力上超过机器是不现实的。人要在计算能力上超过机器是不现实的。o 人脑：最后最伟大的研究前沿人脑：最后最伟大的研究前沿是宇宙中已知的最复是宇宙中已知的最复 杂的物质。杂的物质。 詹母斯詹母斯.华生华生(James Watson)o GOTO语句的问题以及程序设计方法学语句的问题以及程序

32、设计方法学n 1968，Dijkstra首次提出首次提出“GOTO语句是有害的语句是有害的”n 任何程序的逻辑结构都可用任何程序的逻辑结构都可用3种基本结构表示：种基本结构表示： 顺序顺序 选择选择 循环循环n 导致结构化程序设计导致结构化程序设计程序设计方法学程序设计方法学o 网络协议的复杂性和分层结构：网络协议的复杂性和分层结构： 两军问题，两军问题，ISO/OSI参考模型，参考模型，TCP/IP协议协议ABABAPp3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（6）4、计算学科的主领域及其基本问题、计算学科的主领域及其基本问题o 计算学科中的一些基本问题计算学科中的一

33、些基本问题n 计算过程的计算过程的能行与效率能行与效率问题问题n 计算的正确性问题计算的正确性问题n 计算的平台与环境问题计算的平台与环境问题o 如何用科学哲学观点看待和解释如何用科学哲学观点看待和解释n P=?NPn 资源共享资源共享 哲学家共餐问题哲学家共餐问题n 图灵测试图灵测试 人工智能人工智能n “中文屋子中文屋子” 机器永远代替不了人脑机器永远代替不了人脑n 人机对弈人机对弈 智力与计算能力，智商（智力与计算能力，智商（IQ）与情）与情商（商（EQ）数据、信息及其关系数据、信息及其关系o数据数据(Data)n数据是一组表示数量、行动和目标等事实数据是一组表示数量、行动和目标等事实(fact)的可鉴别的可鉴别的非随机符号。它可以是字母、数字或其它符号，也可的非随机符号。它