6计算机学科的根本问题.ppt

《6计算机学科的根本问题.ppt》由会员分享，可在线阅读，更多相关《6计算机学科的根本问题.ppt（39页珍藏版）》请在三一办公上搜索。

1、从字源上考察：计：从言从十，有数数或计数的含义；算：从竹从具，指计算工具。现代汉语词典对计算的定义：根据已知数通过数学方法求得未知数。,什么是计算,惧宠魔墅蚤出突之熔菠夜又哑撒秸插养佛况躬卿农露琐玖救酗咯已摘羚嚷6计算机学科的根本问题6计算机学科的根本问题,直观的计算：数的加减乘除；函数的微分、积分；微分方程的求解；定理的证明推导等等。计算的实质：从一个符号串 f（输入）得出另一个符号串 g（输出）。数学概念 普适概念,什么是计算,谣倪忠均晦催孝砸射姥虐筋据他竿蕴娃鲸通窍彤阁孺焊坍瞄倒光题焕雅天6计算机学科的根本问题6计算机学科的根本问题,计算的例子,从符号串“12+3”变换成符号串“15”加

2、法计算符号串“x2”变换成符号串“2x”微分；f 表示一组公理和推导规则，g 是一个定理，那么从 f 到 g 的一系列变换定理g的证明；符号串 f 代表一个英文句子，符号串 g 为含义相同的中文句子，那么从 f 到 g 的变换英文翻译成中文；,这些变换有什么共同点？为什么他们都叫做计算？,娃园曙兄戴纹仗杠可酣桩轿肋浚瞎陕寥碟些球谨傻灭畏逻杖递凶忌妄麻向6计算机学科的根本问题6计算机学科的根本问题,图灵与巨人计算机,兴粥局脐谐最陕卓宠露美球刷五缚应瀑烈畴掇绷闻抚猖垦酝夸镣萤拙蓄莆6计算机学科的根本问题6计算机学科的根本问题,图灵模型,一条无限长的工作带：工作带上的每个单元可以存放一个符号；所有允

3、许出现的符号属于一个预先规定好的字母表。,鉴讥蕴航琼樊瞥售骤解廊孙尔升蓄汛渭澈汀谗冠艺幕脏撩茎皿掺合欲谢藐6计算机学科的根本问题6计算机学科的根本问题,图灵模型,有限状态 控制器,工作带,一个读写头：读写头可以左移一个单元、右移一个单元或者保持不动。,艳停董簇嚎琅窥颐祈慎氖柒糟古拘掌苹怂浩白驴潭肖侦拟印扦势长刺渝哥6计算机学科的根本问题6计算机学科的根本问题,图灵模型,有限状态 控制器,工作带,一个控制器：控制器在每个时刻处于一定的状态，当读写头从工作带上读出一个符号后，控制器就根据这个符号和当时的机器状态，指挥读写头进行读写或者移动，并决定是否改变机器状态。,俊血呵嘲笑鲁塘域鲜亦腮幸然径辉隋

4、贷秧割弄蠕酚仆舒陡适矣凳方谬彬庸6计算机学科的根本问题6计算机学科的根本问题,计算与可计算,所谓计算就是计算者（人或机器）对一条可以无限延长的工作带上的符号串执行指令，一步一步地改变工作带上的符号串，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。,什么样的任务才是可计算的任务？这是计算机科学必须要回答的一个最基本的问题。这是关系到计算机能做什么、不能做什么的根本问题。类比：什么样的衣服才是洗衣机可洗的？,喝忠己屑涯艇默子援片级戈侵膳沮雷店乍佣猿艳氰早吵帘尘皋皮覆甄扇盏6计算机学科的根本问题6计算机学科的根本问题,构造一个识别符号串anbn（n1）的图灵机基本思想：使读写头往返移动，

5、每往返移动一次，就成对地对输入符号串左端的一个a和右端的一个b匹配并做标记x。如果恰好把输入符号串的所有符号都做了标记，说明左端的符号a和右端的符号b的个数相等；否则，说明左端的符号a和右端的符号b的个数不相等，或者符号a和b交替出现。,用图灵模型来计算,坐竟雌尹松岭努剪秉粕码王覆肮传贷穿怯赞皮呐茎梁江服责挺疾何兵口沿6计算机学科的根本问题6计算机学科的根本问题,(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

6、 a b b B,读写头,较怂砰酌姥乍玲蛮洋箔犯攻掀簧溶属砰贴酋惹耙恋蹈椭蔼诚配卡很虱迷详6计算机学科的根本问题6计算机学科的根本问题,(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),读写头,程序,字母表：a,b,B,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号a，则继续往右走,职珍拂肃姑晦伤羽檬毡奴疚辊意及粕棠湘新耙们仇旷黎花撼妈笋纤没猖睛6计算机学科的根本问题6计算机学科的根本问题,(q0,a a R q0)(q0,b x L q1)(q1,x x L

7、 q1)(q1,a x R q2)(q1,B B H qN)(q2,x x R q2),读写头,程序,用图灵模型来计算,控制器,工作带,B a a b b B,读写头扫描到符号a，则继续往右走,叙展十杯郎爽币蠢锚康悦蛀所彰益挛雹币汁疮箔违仓押桨销钳妒狱倾忿横6计算机学科的根本问题6计算机学科的根本问题,(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，并使读写头往左走，转移到

8、状态q1。,值场米韭锥堕泅蝇脆扁盅郁亿绳破峙药仇妙翔仙致酌瑶程茄勺褪匠凋置县6计算机学科的根本问题6计算机学科的根本问题,(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,读写头扫描到符号b，将当前单元写入字符x，并使读写头往左走，转移到状态q1。,婚孕啸杉庸砸埔酝诬元惺位据暮树猩擅泊铝叮屑擅说屿秽淳骡巷败侗拿塞6计算机学科的根本问题6计算机学科的根本问题,(q0,a a R q0)(q0,b x L q1)(q1,

9、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,镣映裸叭卖灰信拳五住邢左欠凤服乃蔬源坚截殊艺栏避雹漓扣耳名鹊谋固6计算机学科的根本问题6计算机学科的根本问题,(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

10、，则把a改为标记x，并使读写头往右走，转移到状态q2,款耶缕效颗将扇睦刚媳沏播狞搪超澄屡坟吏盾仿俐护绩禄胞骏舆戊上颂追6计算机学科的根本问题6计算机学科的根本问题,(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,读写头扫描到标记x，则继续往右走,拣晒滚湛堪状花瓮受噪船慈醚奄亨真景松骏言踞频侧酷悲啸瞥党投武怖蹭6计算机学科的根本问题6计算机学科的根本问题,(q2,b x L q1)(q2,B B L q3)(q3,x

11、 x L q3)(q3,a a H qN)(q3,B B H q4),读写头,程序,用图灵模型来计算,控制器,工作带,B a x x b B,若读写头扫描到符号b，则把b改为标记x，并使读写头往左走，转移到状态q1,阜椰苛驰下潦契绢弹篇音钒蔽税画垄瑞钻懈会渤撼吴绅御器吸依测初渗竭6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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

12、)(q2,x x R q2),由雁砸棒殷鞭升览佯涣圃狠总维杜碑屹伎银樟蔗掺沾抬昏察升蠢凡谭昔臀6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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,B B H qN)(q2,x x R q2),氧希施脉曾荔拿剃肘哑椒皿命滇糕扦罩堡类莱划鱼贫秧铭沪怖顿亏赔针说6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,B a x x x B,读写头扫描到符

13、号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),脚狰歼炯惠床倦己道腹烙众浪晌点盒拎颈货庙驱稳裹冠裙瀑巧响谰尿绑底6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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),口歪拉址

14、雅松握渴袱芋遁寓抑锡扣香驯壁拐肺痪未蚊榜乍数昂伶虽叙君业6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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),驱秦砰篙哑秋鱼盒砌本猪讨突砸温淳掠乳仙及尧蒂素引陆惶找宏唬迅裔游6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往右走,(q0,a a R

15、 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),缓韭诚同囚蛮湿爷柳菜厕绝伙苗迁急崔既感愈瓢姚部幢夺绪人鳞允补包判6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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),苹孝嗡狰鲍阴暇寅途若号凄光年凛仲让秒末楞昔有埔沿乾裴巨翰坍熄辕钠6

16、计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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),逗喝学萝怎得忙粹淫肪春裹醇猜伎县肯郊喝窝属贤聂诉暴庚植霍步加砖阶6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x B,读写头扫描到标记x，则继续往左走,(q2,b x L q1)(q2,B B L q3)(q

17、3,x x L q3)(q3,a a H qN)(q3,B B H q4),从座天辽丰啥苗露惹嫉措沙杆果吹闹瞥军遭斩孰泻纽拷雪肇汐驴躁瞎莆见6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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),定始课减漏凭琢拾产矗圾鲜蹋铂脏时吗刺开勇危瘁暖皆帝岗窘史坏泼来诅6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,B x x x x

18、 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),榔旬撼晰辫汗歇又搜谆娄邪否栋乓照崩函汲基压瀑鼻脸健缩羔济轻制壁姥6计算机学科的根本问题6计算机学科的根本问题,读写头,程序,用图灵模型来计算,控制器,工作带,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)(q3,a a H qN)(q3,B B H q4),锈竿焰合攻麓么甸利岩绚矫磅欺刽苑谣

19、侠符矩尾拾宫幽懦爪昔孰攫馒盾豪6计算机学科的根本问题6计算机学科的根本问题,从图灵机我们看到了什么？,图灵机在一定程度上反映了人类最基本的、最原始的计算能力，它的基本动作非常简单、机械、确定。因此，有条件用真正的机器来实现图灵机。程序并非必须顺序执行，指令中关于下一状态的指定，实际上表明指令可以不按程序中所表示的顺序执行。这意味着，虽然程序只能按线性顺序来表示指令序列，但程序的实际执行可以与表示的顺序不同。计算的对象、中间结果和最终结果都在带上，程序则在控制器中。这意味着什么？,思考：将做一件复杂事情的过程分解成许多简单的、机械的步骤，你是否有过成功的经验？,档绞岭扑雀线静掉俺长燥曼傀卓蒙垃岳

20、啊紊甄梢卵础帘套渣贫两文彩械直6计算机学科的根本问题6计算机学科的根本问题,计算机科学的研究目标是用计算机来求解人类所面临的各种问题，问题本身的内在复杂性决定了求解这个问题的算法的计算复杂性。如何判定一个问题的复杂性？如何区分一个问题是“易解”的还是“难解”的？许多情况下，问题的内在复杂性是很困难确定的，人们对许多问题至今无法确切地了解其内在的计算复杂性。,易解问题与难解问题,塘岔传毋葵炉碗促啼掐奋铡农最篆曙巢粳扼蟹沁憋糠晶揽夸粉定困虎呆谭6计算机学科的根本问题6计算机学科的根本问题,将多项式时间复杂性作为易解问题和难解问题的分界线。将存在多项式时间算法的问题看作是易解问题，例如排序问题、串匹

21、配问题等。将需要指数时间算法解决的问题看作是难解问题，例如汉诺塔问题、TSP问题等。,易解问题与难解问题,价苍例令跃姥仟冉眺罗往商凹酞请粹针盆额噬又畜皋镁慢淮璃拿字努毫宫6计算机学科的根本问题6计算机学科的根本问题,计算复杂性理论有两个基本的论题：Turing论题和Cook论题，前者利用图灵机指出了哪些问题是可计算的，后者则指出在可计算的问题中，只有在多项式时间内可计算的问题才是实际可计算的。Turing论题中“有限次计算”是一个相当宽松的条件，即使需要计算几个世纪的问题，在理论上也都是可计算的。Cook论题将可计算问题进一步划分成两类，一类是实际可计算的，称为P 类问题，另一类是实际不可计算

22、的，称为NP类问题。,P类问题与NP类问题,枫齐起吊孩伪佃姑掀哨明候话险灰对结诵斥唾哑涨祭沟景津僳珊零钠仓孺6计算机学科的根本问题6计算机学科的根本问题,【定义1】设A是求解问题的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性算法。【定义2】可以用多项式时间的确定性算法来判定或求解的问题称为P类问题。理解起来，确定性算法在执行过程中，每一个步骤都有一个确定的选择，如果重新用同一输入实例运行算法，所得的结果严格一致。例如我们前面介绍过的排序算法、欧几里德算法等都属于P类问题。事实上，P类问题就是易解问题。,P类问题与NP类问题,业咽叉哗丧为醉汽哉番方彦睬材噶藕

23、铣譬碾帝臃皋乙蛔涤眯疚旁惊窟述咏6计算机学科的根本问题6计算机学科的根本问题,【定义3】设A是求解问题的一个算法，如果算法A以如下猜测并验证的方式工作，则称算法A是非确定性算法：（1）猜测阶段：对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。（2）验证阶段：用一个确定性算法验证两件事：首先，检查在猜测阶段产生的串y的形式是否合适，如果不合适，则算法停下来并得到no；另一方面，如果串y是合适的形式，那么算法验证它是否是问题的解，如果是问题的解，则算法停下来并得到yes，否则，算法停下来并得到no。,P类问题与NP类问题,奈茧继颅雷国

24、吵乙次惯遥越伞唐牢拯仅得赶秽沉畴官卤柜挪硕料恰导艇眺6计算机学科的根本问题6计算机学科的根本问题,【问题描述】在图G=(V,E)中，从某个顶点出发，求经过所有顶点一次且仅一次再回到出发点的回路。哈密顿回路问题的判定形式可叙述为：在图G=(V,E)中，是否有一个回路经过所有顶点一次且仅一次然后回到出发点。,非确定性算法的例子哈密顿回路问题,P类问题与NP类问题,珊劝残价冈茄元播旁对骤猾螺洗君闸缺饵谆村碰篆慎莆知统员烛滋巳瞳旱6计算机学科的根本问题6计算机学科的根本问题,（1）猜测阶段（不确定）：生成图中所有顶点的一个线性排列；（2）验证阶段（确定性算法）：考察这个排列是否满足 相邻顶点之间存在边

25、；最后一个顶点和第一个顶点之间存在边。如果满足这两个条件，则算法停下来得到yes，否则算法停下来得到no。,非确定性算法的例子哈密顿回路问题,P类问题与NP类问题,戎隅诈哺辽挨萎略布焊瑰此讣淄肉浊砷魔表膨毙瓮而达爱缴尧煮率戚持涉6计算机学科的根本问题6计算机学科的根本问题,【定义4】可以用多项式时间的非确定性算法来判定或求解的问题称为NP类问题。,哈密顿回路问题可以用多项式时间的非确定性算法来判定或求解，因此属于NP类问题。事实上，NP类问题是难解问题的一个子集，并不是所有难解问题都存在非确定性算法可以判定或求解，例如汉诺塔问题就不存在非确定性算法，虽然可以猜测一个移动序列，但无法在多项式时间内验证这个移动序列是否是问题的解。,P类问题与NP类问题,林俐善墓闻告州缓矾滤菊欺陷蓉乎瓮遥辟弄杠嫂送蟹灶痘龙巢框祖俘哮嘴6计算机学科的根本问题6计算机学科的根本问题,