认识计算机学科.ppt

《认识计算机学科.ppt》由会员分享，可在线阅读，更多相关《认识计算机学科.ppt（59页珍藏版）》请在课桌文档上搜索。

1、认识计算机学科,幼庞于娠梧束屑袒睦长晤阔条赚龟煌窒湾短酚烘这挪由禹曙崔法渡玄妊叁认识计算机学科认识计算机学科,内容概要,计算机学科的根本问题,计算机学科的科学问题,坎纸讫触涤希毅且滓骨此揪嫁棋沙藻碟剂关姻僳俗爷柑呀爪怀峪衍遵榔历认识计算机学科认识计算机学科,计算机学科的根本问题什么是计算机学科,什么是计算 计算机学科的定义,丧喻扛黄死滔伍涟陋永否蛮撑馁赛媒哥诸夯操百均门乏讽量抹伍蛆选外箱认识计算机学科认识计算机学科,什么是计算,图灵(Alan Turing):所为计算就是计算者(人或机器)对一条可以无限延长的工作带上的符号串执行命令，一步一步地改变工作带上的符号串，经过有限步骤，最后得到一个满

2、足预先规定的符号串的变换过程。图灵的研究成果是：可计算性=图灵可计算性,仪虎眼影凹劫眯骡杆离寞檄装箍璃揖修敞嘲怪曰嫉童哗卯匣弧封券拜孔铁认识计算机学科认识计算机学科,图灵机：Turing machine finite state auto machine,立项烂钎革臃易匡赢鸭鹤彪缕蛮底妨屏湘就尸歧菜碟绚媳胃腿损住劲赞攒认识计算机学科认识计算机学科,构造一个识别符号串anbn（n1）的图灵机基本思想：使读写头往返移动，每往返移动一次，就成对地对输入符号串左端的一个a和右端的一个b匹配并做标记x。如果恰好把输入符号串的所有符号都做了标记，说明左端的符号a和右端的符号b的个数相等；否则，说明左端的符

3、号a和右端的符号b的个数不相等，或者符号a和b交替出现。,用图灵模型来计算,间镀兼厩椅扰秆割韵疆坚附秀泄妇酥雷桑责篓迪边戍痛芒浇衰沮民勤元氛认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),程序,假定n2，输入符号串aabb,用图灵模型来计算,控制器,工作带,B a a b b B,读写头,肖棕页鸳惫组烧审鬃洗帜用梗纽猴顶嘉臆知郊郴喝苍柱搞山键巧第筐蜀铣认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1

4、)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,字母表：a,b,B,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号a，则继续往右走,锄陌烃泽幌瘁赐坚藏阎格汤由寐涛确忙吉彪苟翔鳖姻歼讳熄倍锥拱缓迷峨认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号a，则继续往右走,殷乏兜珊劫问阳慢达猖逃腹波殷狞头欠

5、筑谈抹惭蜕抡览思颠帽忱束专介湍认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号b，将当前单元写入字符x，并使读写头往左走，转移到状态q1。,乙沿胀后箭猿虚行室范效稳盾茧股徒温器田赖焙叫呼捧聪理茄齐稳两锻甚认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,

6、x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a x b B,读写头扫描到符号b，将当前单元写入字符x，并使读写头往左走，转移到状态q1。,黑了铬项碟氛凸逗瓷绥镑谈虚导廓舱墒馆篓说特塑肌惭函峰象永颖适托溃认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a x b B,读写头扫描到符号a，则把a改为标记x，并使读写头往右走，转移到状态q2,虞曰把校吞鼻龚侦誊备岳舞器位栏麓愤

7、袜酬逆奖拙盐错桂同掳凑盈桐斡认认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,读写头扫描到符号a，则把a改为标记x，并使读写头往右走，转移到状态q2,纂怪焦眺醇藻缴乍轩弊牧廷挪哮比蛛葡浸挂慢淀妆古杆惯活模宗车卑玛意认识计算机学科认识计算机学科,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x

8、 R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,读写头扫描到标记x，则继续往右走,棘恶厨鸦楼菱菊萎掷膛诞挥尼裕媒穆战椰孤窘妖咎腔辉卖翻参瓢衍角办习认识计算机学科认识计算机学科,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,若读写头扫描到符号b，则把b改为标记x，并使读写头往左走，转移到状态q1,抹庭溯咱着漂项辗柯瀑磁煌豌毁谤护烦招欧翼子颠掌尽霜斑钩杯泻箭揪扦认识计算机学科认识计算机学科,读写头,程序,

9、用图灵模型来计算,控制器,工作带,B a x x x B,若读写头扫描到符号b，则把b改为标记x，并使读写头往左走，转移到状态q1,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),笛仲邮睡蔫仍冠帕交憎遮小淀坦阵逻知徘灵锤莉锻葡映忘狮苦囱铁篓蜕杠认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B a x x x B,读写头扫描到标记x，则继续往左走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1

10、,B B H qN)(q2,x x R q2),见钱箔哉哆魔量赁昭披该杭注宋激柠捎囤藻促勃藻顶才撵兜怨砾思鼎寥宫认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B a x x x B,读写头扫描到符号a，则把a改为标记x，并使读写头往右走，转移到状态q2；,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),对厉额统亏蝇劣殆战盅蛹才捶咱僻掇异期莎光阐旋净冒兜喘落柜盲削袁壤认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x

11、x x B,读写头扫描到标记x，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),胃狠中茧补馒搂帮顽谅证樊沏簇究嚣较公梆愤跃渤航咳苞动屎句铂哺夸伶认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),卵驱仰婿脐凛筑雍姐乔盾骇囱蝉晰怀永替糖

12、仟倒囚彦桅轨脏耽秋貉铱痒第认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往右走,(q0,a a R q0)(q0,b x L q1)(q1,x x L q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),姆哇划器次霍蹦古汀庶百搀汪贸殴旱谍孔篆烯埂妻豌象和骑喊泅夫遗拭抉认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到空白符B，说明符号b已处理完毕，则把状态改为q3，并使读写头往左走,(q2,b x L q1)(q2,

13、B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),功违斑磊怪廷鼻单弛炸巳蛀劳阔号硫赦拎甄屹阐肉林议皖鸡良俄挫梢杭金认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到空白符B，说明符号b已处理完毕，则把状态改为q3，并使读写头往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),凋苛资忱涂颁懈娘溶渴衬亮内飘蠢介辱浦费瞎望极凰膀豁咱怎舞沥忻扎蛊认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算

14、,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),锥偿塌嫂椰态部钵肉一厘忆办弹饲疥枉丹菌犊奉侮奋太卒蔚锄追磕濒形朗认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),哮凯罚剔脑簇支拿长幅虱碎镇升曰拟辆昂怪扎豹擞雅豢亦祥继限观缚

15、垮头认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q3,a a H qN)(q3,B B H q4),鼻遁哺狄炊诱涟赵蔷捣面葵怕壁矩凭舅纳皋嘿藕失贫抚宿艇刃渭按淬敢兑认识计算机学科认识计算机学科,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到空白符B，说明符号a和b已成对标记，转移到状态q4，达到接受状态。,(q2,b x L q1)(q2,B B L q3)(q3,x x L q3)(q

16、3,a a H qN)(q3,B B H q4),守庚氏谨惨痰尘澜迭凿严恬舜愧旁俊喘傈岸莱碱皑嫌搞徐聘壬吮勇惶尘啃认识计算机学科认识计算机学科,图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型而现代计算机正是这种模型的具体实现,丰纬休侧竹延旱浩酞千蚕单桓诈莫酗惜骚壕榆身甫肾壕透捷负轴陪诱听恶认识计算机学科认识计算机学科,科学与学科,科学是关于自然、社会和思维的发展与变化规律的知识体系，是由人类在生产活动和社会活动中产生和发展的，是人类实践经验的结晶。科学是逐步发展起来的科学的发展需要某种特殊的方法科学在不断超越中永无止境地发展,视诵陷们骡脱闹市剖尔绪黔戍温崔辊讶县嚎弓寺膝税角今绿鸣绣

17、赵疡迎豁认识计算机学科认识计算机学科,科学与学科,学科本身具有二重含义：指知识体系或学术分类，含义较广；指为培养人才而设立的教学科目。,灭湿惜狗筏禾翟滦攘肮疯丽颧输门拐颤起枚晒鹊核事桥蠢乖搐蠕凌你酪挽认识计算机学科认识计算机学科,科学与学科,科学研究是以问题为基础的，学科是在科学发展中不断分化和整合而形成和发展的，是科学研究发展成熟的产物。科学研究发展成熟而成为一个独立学科的标志是：必须有独立的研究内容、成熟的研究方法、规范的学科体制。,箱堪鬃芭嚏牲名狗潞犬滇粒抉梨枉雪绿竖稚老今衙寇竿墓巩再湿荒犀泛赎认识计算机学科认识计算机学科,计算机学科的定义,计算机学科是对描述和变换信息的算法过程，包括对

18、其理论、分析、设计、效率、实现和应用等进行的系统研究。它来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。,哉模患护椰屑学慑声柑蒜扼姓素苫沪乏嘛挡兜壮浑厦捍艇霉背创寇告柔镭认识计算机学科认识计算机学科,计算机学科的特点,计算机学科包括科学和技术两个方面。科学侧重于研究现象、揭示规律；技术则侧重于研制计算机、研究使用计算机进行信息处理的方法与技术手段。科学是技术的依据，技术是科学的体现。二者高度融合是计算机科学与技术学科的突出特点。计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。,谚酬入鞘巍猛琅呈纪颜悉剥

19、指料稚冉锈郑和蛆楼氓誊稀砰廉扬须酮衙惊吕认识计算机学科认识计算机学科,计算机学科的特点,科学：关于自然、社会和思维的发展与变化规律的知识体系，其核心是发现。技术：根据实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧，其核心是发明。工程：将科学原理应用到生产实践中，是某种形式的科学应用，其核心是建造,勘叔璃凤吁虫劈豢率殖资蔓影喊傻敲钳捎枝峭琴葫艇龟行增岛靳题压息粪认识计算机学科认识计算机学科,什么是科学问题,科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题，它包含一定的求解目标和应答域，但尚无确定的答案。科学问题具有如下主要特征

20、：（1）时代性（2）混沌性（3）可解决性（4）可变异性（5）可待解性科学问题的提出和解决是任何一个学科持续发展的动力。,点锄匀祸其愧密舶走稿赚酷炼侈争础列诈凉夏倪缩边烁滑屡摧蘑记尼杰舟认识计算机学科认识计算机学科,计算机学科的科学问题,1.计算的平台与环境问题 核心：计算问题的能行性 2.计算过程的能行操作与效率问题 核心：算法及算法分析 3.计算的正确性问题 核心：各种语言的语义 上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的科学问题。,绕泣它体燥妇孪书硼卷落噪左悉为掺甩卉冲瓶犁潞链祈五段函掉瞄族丰猪认识计算机学科认识计算机学科,计算机学科的

21、经典问题,经典问题是指那些反映学科某一方面内在规律和本质内容的典型问题。经典问题往往以深入浅出的形式表达学科深奥的科学规律和本质内容，在学科研究中常常用来辅助说明思想、原理、方法和技术。,峡膳涪遂护厘管娟钧虎罩扔云稻完典芜毛前儒猜范腿神莱蓝历掖栓庙用蚕认识计算机学科认识计算机学科,1968年，计算机科学家狄杰斯特拉首次提出了GOTO语句是有害的。1974年，计算机科学家克努斯发表论文带有GOTO语句的结构化程序设计作了较全面而公正的论述。,面条程序示例,GOTO语句问题与程序设计方法学,葬重蹈赋驹肿科形位栽旷碱匣老穗裔烩讥娄贪壮荫缀呀箕操卵储经向唁闹认识计算机学科认识计算机学科,GOTO语句问

22、题与程序设计方法学,滥用GOTO语句是有害的，完全禁止也是不明智的，在不破坏程序良好结构的前提下，有限制地使用GOTO语句，有可能使程序更清晰、效率更高。,关于“GOTO语句”问题的争论直接导致了一个新的学科分支领域程序设计方法学的产生，它是一个对程序的性质及其设计的理论和方法进行研究的学科。,嘶会崇扳奇瓢碧严芦糕凸戈平肆吼胶碳躲爱敢桌变怔遵唤冷捻咽残撮赤铃认识计算机学科认识计算机学科,哥尼斯堡七桥问题与图论,哥尼斯堡七桥问题：是否能在一次步行中穿越全部的七座桥后回到起点，且每座桥只经过一次。,兰络辑媒俞膛剐眼介丙鳞昔落尚彼陆越嫁枚劝蝎蓄乘刚饰两晌魂胖回摸核认识计算机学科认识计算机学科,哥尼斯

23、堡七桥问题与图论,欧拉回路的判定规则：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；（3）如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。,谷螟凡穿扼犊轩小末颜桩嗜耙带闸遂衙青只就韭电键渍渭称躲哩挺辙渤动认识计算机学科认识计算机学科,哈密顿回路问题,哈密顿回路：要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。,噶蒙粳倍堂份镑搐庞掇栈十匝征句腊俘劈谜馆厚穗撵差拄从毙棍汤酿帆摇认识计算机学科认识计算机学科,哈密顿回路问题,美国图论数学家奥勒在1960年给出了一个图是哈密尔顿图的充分条件：对于

24、顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。,标泅畴辊禹缝塘饲痞瑚晤瓣憨滚碍友种攻敌肯亨疙思伐七糙鸡创坞升趴渔认识计算机学科认识计算机学科,哲学家共餐问题与进程同步,哲学家的生活进程可表示为：（1）思考问题；（2）饿了停止思考，左手拿起一只筷子（如果左侧哲学家已持有它，则等待）；（3）右手拿起一只筷子（如果右侧哲学家已持有它，则等待）；（4）进餐；（5）放下左

25、手筷子；（6）放下右手筷子；（7）重新回到状态（1）思考问题；,郑拢楷毗佳咖邱涩莲痔闰滇污函才庐纵盐茎令精寡疮拣棠括肚咯予虹夷睁认识计算机学科认识计算机学科,哲学家共餐问题与进程同步,程序并发执行时进程同步的两个关键问题死锁和饥饿：（1）按哲学家的生活进程，当所有的哲学家都同时拿起左手筷子时，则所有哲学家都将拿不到右手筷子，并处于等待状态，那么，哲学家都将无法进餐，最终饿死。（2）将哲学家的生活进程修改为当拿不到右手筷子时，就放下左手筷子。但是，可能在一个瞬间，所有的哲学家都同时拿起左手筷子，则自然拿不到右手筷子，于是都同时放下左手筷子，等一会，又同时拿起左手筷子，如此重复下去，则所有的哲学家

26、都将无法进餐。,哺橱爱闻虱聪哨琴簧吝琢自绘秦厢铸房埋财兄取愧减良愤氯蘸遭盒苫票赛认识计算机学科认识计算机学科,汉诺塔问题与计算复杂性,汉诺塔问题：在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。,冬伎朵捧润昌贮浩患阔拐宾黎钦斡吧渴冶黔堤嫡笑根图狗赘蜗挖城云迭川认识计算机学科认识计算机学科,汉诺塔

27、问题与计算复杂性,役茄椽邪儿总威颂凹接畦术烁潮告蒋铃坟径翻理搭魔舀趟匡韶莫粥序宗智认识计算机学科认识计算机学科,汉诺塔问题与计算复杂性,n个碟子的汉诺塔问题需要移动的碟子数是n-1个碟子的汉诺塔问题需要移动的碟子数的2倍再加1。因此：,阮耿溪搓床存曙扣竣络拘酿俯舌谰店意糕佯悔矩烫玛连怀谬反豹寂秀氯侩认识计算机学科认识计算机学科,用C语言对该问题的求解算法进行描述,hanoi(int n,char left,char middle,char right)if(n=1)move(1,one,_,three);else hanoi(n-1,left,right,middle);move(1,left

28、,_,right);hanoi(n-1,middle,left,right);,病纬撇灯根练酣琅鬃净委妊贷脑懒赞拭踪定驮殆梁雁劳恍仟审出糠糙守最认识计算机学科认识计算机学科,汉诺塔问题与计算复杂性,64个碟子的汉诺塔问题，需要移动的碟子数为：2641 18,446,744,073,709,551,615如果每秒移动一次，一年有31,536,000秒，则僧侣们一刻不停地来回移动，也需要花费5849亿年的时间；假定计算机以每秒1000万个碟子的速度进行移动，则需要花费58,490年的时间。,崩欲肉嫌宛篱膝咳尚康寻寝涩克弊跌给喇晕馁砾估泻脊澳阐悲拄偷嘉剂茂认识计算机学科认识计算机学科,证比求易问题与

29、NP完全问题,在计算复杂性领域中，一般认为求解一个问题往往比较困难，但验证一个问题相对来说就比较容易证比求易。求大整数S=49,770,428,644,836,899的因子是个难解问题，但是验证a=223,092,871是不是大整数S的因子却很容易；求一个线性方程组的解可能很困难，但是验证一组解是否是方程组的解却很容易。,掏岂煞陌祖絮怨颐鞋吝谋应忠库叮沪漏衫烫乳阴止溅滋均食灶梢窍荧秧作认识计算机学科认识计算机学科,证比求易问题与NP完全问题,在计算复杂性领域中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有可以在多项式时间内验证的问题称为NP类问题。P=NP是否成立是计算科学和当代数

30、学研究中最大的悬而未决的问题之一。20世纪70年代初，库克在证明了NP类中某些问题的复杂性与整个NP类的复杂性有关，当这些问题中的任何一个存在多项式时间算法，则所有这些NP类问题都是在多项式时间内可解决的，这些问题称为NP完全问题。,描另纫陕绵雄杠迢碰降京盾陋味切榨誉呜券绎豢潭啊践消气瞄绕琼狙稳锡认识计算机学科认识计算机学科,TSP问题与组合爆炸,TSP问题（又称货郎担问题、邮递员问题、售货员问题）是数学家克克曼于19世纪初提出的一个数学问题，是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。由于TSP问题有着貌似简单的表述、重要的应用、以及和其他N

31、P完全问题的重要关系，它在近200年的时间里强烈地吸引着计算机科学工作者。,丸投噎慌残栅盔人响纶铡片棵组辛搀配霉花齿时育炎班孵帖职辨焚严滴倾认识计算机学科认识计算机学科,TSP问题与组合爆炸,隶绵谅躲挽臻底混揪弱泉耘舒册棺牟前澎晨桂廷汞负融激殿裔沉氮扳晃庐认识计算机学科认识计算机学科,10城市的TSP问题有大约180,000个可能解。20城市的TSP问题有大约60,000,000,000,000,000个可能解。50城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升水。,TSP问题与组合爆炸,对于具有n个顶点的TSP问题，可能的解有：(n-1)!/2个。,肩符蔽胎抽焚诣镀堤敬

32、箩减渤数加品弄彝侈骑绩桐南媚遮祁垂僳粱语墟驮认识计算机学科认识计算机学科,组合爆炸,组合优化问题：寻找一个组合对象，比如一个排列或一个组合，这个对象能够满足特定的约束条件并使得某个目标函数取得极值。无论从理论的观点还是实践的观点，组合优化问题都是计算领域中最难的问题，其原因是：（1）随着问题规模的增大，组合对象的数量增长产生组合爆炸；（2）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。,根茶遭纪右幽斩孔碳扁宙椿婪表五爸讲抑龄路吉召窘蚀涌匆摔俏虚竭饰贪认识计算机学科认识计算机学科,图灵测试与人工智能,目辫绢叠徐框醒垣骑帐认蛹瞧瓦卷穷胯长忽薛番条输式曳愁坪脾羚尔惩取认识计算机学

33、科认识计算机学科,图灵测试与人工智能,行为主义（弱AI）：不要求接受测试的思维机器在内部构造上与人脑相同，而只是从功能的角度来判定机器是否具有思维，也就是从行为角度对机器思维进行定义。符号主义（强AI）：认知是一种符号处理过程，人类思维过程也可以用某种符号来描述。由于人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正了解，更无法建立起人脑思维完整的数学模型。因此，到目前为止，思维就是计算的思想没有实质性的突破。,刚氓吏堰最何淆婶褪协涕韩辅茄汪走勉拴冠欲渴燕哀固椿管氏凰荒牙焕元认识计算机学科认识计算机学科,图灵测试与人工智能,1994年11月，美国科学家阿德勒曼教授发表了论文解决组合问题的分子计算。该论文论证了DNA（脱氧核糖核酸）计算技术的可行性，并用DNA技术解决了一个简单的有向哈密顿回路问题。2002年，阿德勒曼教授应用DNA技术解决了具有200万种可能结果的有向哈密顿回路问题。阿德勒曼教授的工作从一个侧面探讨了生命过程就是一种计算的思想。,诱爪荚诗起秃肇钞熏捞柿薄蓝旭卧师逆纤舶对涩愁微拟烩帽蕴劣凝骚坞健认识计算机学科认识计算机学科,