《第2章计算学科的基本问题概要》由会员分享，可在线阅读，更多相关《第2章计算学科的基本问题概要（34页珍藏版）》请在金锄头文库上搜索。
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); move(1, left, r
11、ight); 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)nO(1) 称为常数级称为常数级nO(logn) 称为对数级称为对数级nO(n) 称为线性级称为线性级nO(nc) 称为多项式级（称为多项式级（c为常数为常数)，如，如O(n2)nO(cn)称为指数级（称为指
14、数级（c为常数为常数)，如，如O(2n)nO(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难解性问题：当时间复杂性难解性问题：当时间复杂性多项式时多项式时nP类问题：可以在多项式时间内类问题：可以在多项式时间内求解求解的问题的问题nNP类问题：可以在多项式时间内类问题：可以在多项式时间内验证验证的问题的问题nP类问题采用的是类问题采用的是确定性算法确定性算法，NP类问题采用的类问题采用的是是非确定性算法非确定性算法（如通过猜算）。（如通过猜算）。PNP。oNP完全问题完全问题：NP=P？n是世界七大数学难题之一（首位）是世界七大数学难题之一（首位）o哈密顿路径问题：可以在多项式时间类哈密顿路径问题：可以在多
18、项式时间类判断判断一个回路一个回路是否是哈密顿回路，但目前没有多项式时间类算法直是否是哈密顿回路，但目前没有多项式时间类算法直接接求解求解出哈密顿回路。出哈密顿回路。3、计算学科中的其他典型科学问题（计算学科中的其他典型科学问题（1 1） 证比求易算法证比求易算法n求出求出48 770 428 433 377 171的一个真因子的一个真因子 n给出数进行验证：给出数进行验证：顺序算法顺序算法n多人参加验证：多人参加验证：并行算法并行算法n时间复杂性时间复杂性 空间复杂性空间复杂性n但并行运算也存在但并行运算也存在“瓶颈瓶颈”问题：问题：阿姆达尔定律阿姆达尔定律 1 Sp - （倍）（倍） 加速
19、能力加速能力 1 - f f + - pn设设f=1%, p ，Sp=100，最大，最大100倍倍o直觉上认为顺序算法解决不了的问题完全可以用并直觉上认为顺序算法解决不了的问题完全可以用并行算法来解决，并且，并行计算机系统求解问题的行算法来解决，并且，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题。这是一种误解。而解决难解性问题。这是一种误解。o阿姆达尔定律阿姆达尔定律说明：当将一个问题分解到多个处理说明：当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行器上解决时，由于算法中不可避免地存在必
20、须串行执行的操作，从而大大地限制了并行计算机系统的执行的操作，从而大大地限制了并行计算机系统的加速能力。加速能力。3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（2） 旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题n旅旅行行商商问问题题（Traveling Salesman Problem，TSP）：一一个个旅旅行行商商从从某某城城市市出出发发，必必须须经经过过每每个个城城市市一一次次切切仅仅一一次次，最最后后回回到到原原出出发发城城市市。如如何何确确定定一一条条最最短短的的路路线线，使使其其旅旅行行的的费费用最少。用最少。n是典型的是典型的NP完全问题完全问题：本质上难以
21、：本质上难以求解。求解。n是最有代表性的优化组合问题之一：是最有代表性的优化组合问题之一：割平面法与分支限界法相结合。割平面法与分支限界法相结合。旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题o如果有如果有3个城市个城市A、B和和C，则有，则有6种访问每个城市的次序：种访问每个城市的次序：ABC，ACB，BAC，BCA，CAB，CBA；如果有；如果有4个城个城市，则有市，则有24种次序，可以用阶乘来表示：种次序，可以用阶乘来表示：4！=24；若有；若有5个城市，则有个城市，则有5！=54！=120。o如果如果n个城市，则有个城市，则有n！；！；
22、20个城市：个城市：20！=1.2X1017。o即使用计算机来计算，这种急剧增长的数字也远远超过即使用计算机来计算，这种急剧增长的数字也远远超过计算资源的处理能力。计算资源的处理能力。Cook评论：评论：“如果有如果有100个城市，个城市，需要求出需要求出100！条路线的费用，没有哪一台计算机能够胜！条路线的费用，没有哪一台计算机能够胜任这一任务。打个比方，让太阳系中所有的电子以它旋任这一任务。打个比方，让太阳系中所有的电子以它旋转的频率来计算，就算太阳烧尽了也算不完。转的频率来计算，就算太阳烧尽了也算不完。”o组合路线数呈指数阶急剧增长组合路线数呈指数阶急剧增长组合爆炸问题组合爆炸问题。o将
23、将割平面法割平面法与与分支限界法分支限界法相结合，相结合，1998年科学家们成功年科学家们成功地解决了美国地解决了美国13509个城市之间的个城市之间的TSP问题，问题，o2001年又解决了德国年又解决了德国15112个城市之间的个城市之间的TSP问题。但问题。但这一工程代价也是巨大的：共使用了美国这一工程代价也是巨大的：共使用了美国Rice大学和普大学和普林斯顿大学之间网络互连的、由速度为林斯顿大学之间网络互连的、由速度为500MHz 的处理的处理器组成的器组成的110台计算机，所有计算机花费的时间之和为台计算机，所有计算机花费的时间之和为22.6年。年。o由于由于TSP会产生组合爆炸的问题
24、，因此寻找切实可行的会产生组合爆炸的问题，因此寻找切实可行的简化求解方法就成为问题的关键。简化求解方法就成为问题的关键。oTSP应用：钻孔调度问题，运输问题，后勤服务问题。应用：钻孔调度问题，运输问题，后勤服务问题。旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（3）o找零问题找零问题：设有不同面值的钞票，要求用最小数量的钞：设有不同面值的钞票，要求用最小数量的钞票给顾客找某数额的零钱。票给顾客找某数额的零钱。o背包问题背包问题：给定：给定n种物品和一个背包，要求在重量容量种物品和一个背包，要求在重量容量的限制下，使装入的物品总
25、价值最大。的限制下，使装入的物品总价值最大。o找零问题、背包问题等是一类可以用贪心法来处理的典找零问题、背包问题等是一类可以用贪心法来处理的典型问题。型问题。o贪心法贪心法：是一种传统的启发式算法，它采用逐步构造最：是一种传统的启发式算法，它采用逐步构造最优解的方法，即在算法的每个阶段，都作出在当时看上优解的方法，即在算法的每个阶段，都作出在当时看上去最好的决策，以获得最大的去最好的决策，以获得最大的“好处好处”；换言之，就是在；换言之，就是在每一个决策过程中都要尽可能的每一个决策过程中都要尽可能的“贪贪”，直到算法中的某，直到算法中的某一步不能继续前进时，算法才停止。一步不能继续前进时，算法
26、才停止。3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（4） 计算机资源管理计算机资源管理n生产者生产者消费者问题：使用资源，释放资源消费者问题：使用资源，释放资源o使用共享资源的多进程同步问题使用共享资源的多进程同步问题o使用使用“信号灯信号灯”的概念解决进程间的互斥的概念解决进程间的互斥n“哲学家共餐哲学家共餐”问题问题o程序并发执行时进程同步的程序并发执行时进程同步的问题：问题：“死锁死锁”和和“饥饿饥饿”o解决：并发程序语言、解决：并发程序语言、Petri网网 在计算学科诞生后，为解决人工智能中一些激烈争在计算学科诞生后，为解决人工智能中一些激烈争论的问题，图灵和西尔
27、勒又分别提出了能反映人工智能论的问题，图灵和西尔勒又分别提出了能反映人工智能本质特征的两个著名的哲学问题，即图灵测试和西尔勒本质特征的两个著名的哲学问题，即图灵测试和西尔勒的的“中文屋子中文屋子”。 沿着图灵等人对沿着图灵等人对“智能智能”的理解，人们在人工智能领的理解，人们在人工智能领域取得了长足的进展，其中，域取得了长足的进展，其中，“深蓝深蓝”战胜国际象棋大师卡战胜国际象棋大师卡斯帕罗夫就是一个很好的例证。斯帕罗夫就是一个很好的例证。3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（5） 人工智能中的哲学问题人工智能中的哲学问题 图灵测试（图灵测试（Turing Test
28、)n1950年，图灵提出：机器能思维吗？年，图灵提出：机器能思维吗？n一一个个人人在在不不接接触触对对象象的的情情况况下下，进进行行一一系系列列的的提提问问，如如果果他他根根据据这这些些回回答答无无法法判判断断对对象象是是人人还还是是机机器器，则这种计算机具有与人相当的智力。则这种计算机具有与人相当的智力。n模仿游戏的试验模仿游戏的试验称之为图灵测试称之为图灵测试 n人类思维的本质？思维就是计算。人类思维的本质？思维就是计算。n机机器器思思维维的的定定义义？从从功功能能的的角角度度来来判判定定机机器器是是否否能能思维，也就是从行为主义思维，也就是从行为主义这个角度对这个角度对“机器思维机器思维
29、”进进行定义。行定义。 西尔勒（西尔勒（J.R.Searle）的）的“中文屋中文屋”n1980年西尔勒在年西尔勒在行为科学和脑科学行为科学和脑科学杂志上发表杂志上发表论文，在文中他以自己为主角设计了一个中文屋子论文，在文中他以自己为主角设计了一个中文屋子的假想试验，反驳了强的假想试验，反驳了强AI的观点。的观点。n西尔勒给出的汉字符号与一个地道的中国人作出的西尔勒给出的汉字符号与一个地道的中国人作出的答案没什么不同。但是，我们能说西尔勒真的懂中答案没什么不同。但是，我们能说西尔勒真的懂中文吗？文吗？n结论：机器永远也不能结论：机器永远也不能代替大脑代替大脑形式化的计形式化的计算机仅有语法，没有
30、算机仅有语法，没有语义语义。人机博弈问题人机博弈问题n转折点：转折点：1997年年“深蓝（深蓝（Deep Blue)”与卡斯帕罗夫之战。与卡斯帕罗夫之战。 前者前者二胜一负三平战胜后者。深蓝由二胜一负三平战胜后者。深蓝由256（32 node*8）个专用处理）个专用处理器组成，每秒可计算器组成，每秒可计算2亿步棋。亿步棋。n使用博弈树搜索，寻找最佳解。国际象棋使用博弈树搜索，寻找最佳解。国际象棋10120个结点（棋局总个结点（棋局总数），中国象棋数），中国象棋10160个结点，围棋个结点，围棋10768个结点个结点难解性问题。难解性问题。n2006年在北京奥体中心进行的首届年在北京奥体中心进行
31、的首届“浪潮杯浪潮杯”中国象棋中国象棋“人机人机大战大战”，电脑胜出，电脑胜出。o 机器智力和人的智力是二回事。机器智力和人的智力是二回事。 o 人要在计算能力上超过机器是不现实的。人要在计算能力上超过机器是不现实的。o 人脑：最后最伟大的研究前沿人脑：最后最伟大的研究前沿是宇宙中已知的最复是宇宙中已知的最复 杂的物质。杂的物质。 詹母斯詹母斯.华生华生(James Watson)oGOTO语句的问题以及程序设计方法学语句的问题以及程序设计方法学n1968，Dijkstra首次提出首次提出“GOTO语句是有害的语句是有害的”n任何程序的逻辑结构都可用任何程序的逻辑结构都可用3种基本结构表示：种
32、基本结构表示： 顺序顺序 选择选择 循环循环n导致结构化程序设计导致结构化程序设计程序设计方法学程序设计方法学o网络协议的复杂性和分层结构：网络协议的复杂性和分层结构： 两军问题，两军问题，ISO/OSI参考模型，参考模型，TCP/IP协议协议ABABAPp3、计算学科中的其他典型科学问题（、计算学科中的其他典型科学问题（6）4、计算学科的主领域及其基本问题、计算学科的主领域及其基本问题o计算学科中的一些基本问题计算学科中的一些基本问题n计算过程的计算过程的能行与效率能行与效率问题问题n计算的正确性问题计算的正确性问题n计算的平台与环境问题计算的平台与环境问题o如何用科学哲学观点看待和解释如何
33、用科学哲学观点看待和解释nP=?NPn资源共享资源共享 哲学家共餐问题哲学家共餐问题n图灵测试图灵测试 人工智能人工智能n“中文屋子中文屋子” 机器永远代替不了人脑机器永远代替不了人脑n人机对弈人机对弈 智力与计算能力，智商（智力与计算能力，智商（IQ）与情商）与情商（EQ）数据、信息及其关系数据、信息及其关系o数据数据(Data)n数据是一组表示数量、行动和目标等事实数据是一组表示数量、行动和目标等事实(fact)的可鉴别的可鉴别的非随机符号。它可以是字母、数字或其它符号，也可以的非随机符号。它可以是字母、数字或其它符号，也可以是图形、图象、声音等。是图形、图象、声音等。o信息信息(Info
34、rmation)n物质状态发生变化的一种表征，通常指数据、消息物质状态发生变化的一种表征，通常指数据、消息(message)中的含义。它对接收者有用，对决策或行为有中的含义。它对接收者有用，对决策或行为有现实或潜在的价值。现实或潜在的价值。o知识知识(knowledge)n知识是人类积累的关于自然和社会的认识和经验的总和。知识是人类积累的关于自然和社会的认识和经验的总和。o抽象的概念抽象的概念n数据和信息的表示数据和信息的表示n数据、信息与知识的关系数据、信息与知识的关系数据与信息的关系数据与信息的关系生产过程生产过程成品成品数据处理数据处理数据数据原料原料信息信息 信息本身不是实体，必须通过
35、载体才能体现，但不随载体信息本身不是实体，必须通过载体才能体现，但不随载体的物理形式而变化。信息是加工过的数据，数据是信息的（符号）的物理形式而变化。信息是加工过的数据，数据是信息的（符号）载体。是载体。是“原料原料”和和“成品成品”的关系，如图，信息有相对性的关系，如图，信息有相对性. .媒体世界改头换面媒体世界改头换面o多媒体信息多媒体信息(Multimedia Information) n多媒体信息无所不在，这些信息包括文字、声音、多媒体信息无所不在，这些信息包括文字、声音、图形、图象、动画、视频等。图形、图象、动画、视频等。n多媒体信息技术的特性主要包括信息载体的多样化、多媒体信息技术
36、的特性主要包括信息载体的多样化、集成性和交互性。集成性和交互性。n好处：数据压缩与纠错好处：数据压缩与纠错o超媒体信息超媒体信息(Hypermedia Information) n超媒体通过链接方式将一些离散的信息单元或信息超媒体通过链接方式将一些离散的信息单元或信息节点节点(包括文本、图形、音频、视频、动画、图像包括文本、图形、音频、视频、动画、图像和可执行文档等和可执行文档等)连接在一起来表征信息。连接在一起来表征信息。n超媒体技术将多种媒体元素与超媒体技术将多种媒体元素与Web应用、远程协作、应用、远程协作、媒体信息广播和存储等结合在一起。媒体信息广播和存储等结合在一起。 作业：作业：P55 2.2，2.9课堂测验：课堂测验：程序的逻辑结构都程序的逻辑结构都可以用哪可以用哪3种基本结构表示种基本结构表示？作业：作业： 制作一个制作一个PPT，内容：，内容： 对问题进行抽象的一个实例对问题进行抽象的一个实例 每个班选每个班选3个学生上台讲，时间个学生上台讲，时间15分钟。分钟。
