计算理论基础课件-Introduction..

ElementsoftheTheoryofComputationIntroductionTextbookElementsoftheTheoryofComputation(HarryR.Lewis/ChristosH.Papadimitriou)WhythisCourseAutomata(第二章：Finite-stateMachine,第三章：PushdownAutomata,第四章：TuringMachines)Computability(第五章:Undecidability)Complexity(第六章:Computational;第七章:NP-completeness)MathematicPreliminaries(第一章:Sets,RelationsandLanguage)也就是从形式化、逻辑和数学的角度去了解计算机的能力与局限性是什么？主要了解理论计算机科学的如下基本问题与计算理论有关的问题什么是计算？什么是可以计算的？什么是计算的形式化描述？在计算机出现之前：机械计算结绳为数（在拉丁语中，“计算”的单词Calculus，其本意就是用于计算的小石子）算盘1642年，年仅19岁的法国科学家布雷兹·帕斯卡借鉴了珠算原理，发明了机械计算机；德国科学家格特弗里德·莱布尼兹改进了前者的设计，发明了“步进式计算机”，能够进行乘、除和平方的计算。20世纪初，英国剑桥大学数学教授Babbage前瞻性地提出计算机领域的一个重要思想：人类有可能设计出一种机械装置，完成一系列计算，并把信息转化为数字，用机器对它们进行处理。什么是可以计算的)3,,,(nRZYXZYXnnn费马声称当n2时，就找不到满足xn+yn=zn的整数解费马定理计算的验证形式数据测试形式化测试C.AntonyR.HoareHoare逻辑完成形式化证明的杰出工作，但是仍旧存在困难（本书介绍的内容基本属于形式化问题）近代计算技术的起源图灵的伟大贡献：Turing!计算机界以他的名字命名了“图灵奖”，从1966年每年颁授一次，被誉为计算机界的“诺贝尔奖！”任何事物的产生均有理论准备，计算机的产生也不例外20世纪初几个有关计算的热点研究：德国大数学家希尔伯特（D．Hillbert）1928年提出著名的“希尔伯特纲领”，认为数学是完备（Completeness）和一致（Consistency）的，可以由数学本身去证明。所有属于自然数集合的数均属于自然数集合（完备）所有不属于自然数集合的数均不属于自然数集合（一致）证明本身是一个计算过程，如何寻找一个自动机进行证明？寻找能够替代人智慧工作的机械或装置！Godel的贡献1931年，“希尔伯特纲领”被奥地利逻辑学家哥德尔（K．Godel）用递归函数（Recursive）理论推翻，他认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。Gödel'sTheoremhasbeenusedtoarguethatacomputercanneverbeassmartasahumanbeingbecausetheextentofitsknowledgeislimitedbyafixedsetofaxioms,whereaspeoplecandiscoverunexpectedtruths...图灵的设想天才的图灵设想：能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。1936年图灵发表一篇著名的论文《论数字计算在判决难题中的应用》。他提出了一种十分简单但运算能力极强的理想计算装置，用它来计算所有能想象得到的可计算函数。计算表格LetmeseeWriteHere一个一般的计算过程程序数据图灵机：现代计算机的理论模型两端无限长的纸带控制器（读写或计算）与现代计算机相同之处：程序与数据混合在一起，由控制器控制执行与现代计算机不同：内存无限大！没有考虑输入与输出！（所有信息都在子带上）图灵对可计算的定义：被求解问题需要形式化；必须设计一个算法；算法需要有合理的复杂度（空间与时间复杂度）可计算工具不只是计算机recursivefunction(Godel-Herbrand,1934)λ-Calculus(Church-Kleene,1932-1934)Turingmachine(AlanTuring1936)已经证明：如上三种计算工具功能是等效的！为什么只是图灵机成为现代计算机理论基础是物理机械平台，而非数学逻辑平台当时工艺机械达到了设计这种机械平台的能力！图灵对计算机智能的思考“计算机会思考么？”，这样的问题是没有什么意义的。（图灵，1950年）但是我们可以通过如下测试去判断计算机是否有智能？图灵测试哪个答案是计算机回答的呢？计算机有智能么？目前没有任何程序通过图灵测试？国际象棋冠军的确败在了“深蓝”手下计算机强于快速搜索；人脑强于归纳推理人机大战－卡斯帕罗夫VS深蓝那个时候，我感觉我的面前有种新的智慧！能改行下围棋吗？2个回合以后位置变化国际象棋约150万种围棋16亿种7个回合以后位置变化国际象棋3514种围棋20014种与深蓝同等速度的围棋电脑每下一子需要想一年半时间！！结论：脑功能有着独特的功能特点，脑功能的认识将使人工智能研究取得的革命性突破。图灵测试仍然是一个热点！CAPTCHA是CompletelyAutomatedPublicTuringTesttoTellComputersandHumansApart（全自动区分计算机和人类的图灵测试）的简称。一个CAPTCHA是任何一个能区分计算机和人类的程序。这种程序必须能生成并评价人类能很容易通过但计算机却通不过的测试。这个要求本身就是悖论，因为这意味着一个CAPTCHA必须能生成一个它自己不能通过的测试。CAPTCHA项目著名的计算机专家Blum夫妇在卡内基-梅隆大学（CMU）领导；美国计算机学会（ACM）由于ManuelBlum奠定了计算复杂性理论的基础和在密码术及程序校验方面的贡献，把1995年度的图灵奖颁给了ManuelBlum2001年，在美国国家科学基金1.56亿美元IT研究拨款中（中国国家自然科学基金当年资助为7千7百万人民币），CMU得到了2400万美元——而在CMU的总共14个受资助项目中，最大的一个是得到550万美元的“CAPTCHA项目”。Blum一家三口（ManuelBlum与LenoreBlum的儿子麻省理工学院博士AvrimBlum也在此和父母并肩战斗）均是此项目的研究人员。中国也十分重视理论计算机科学研究上下文无关语言的递归函数理论的后续研究（2003年国家自然科学基金面上项目）计算机科学技术的基础理论（2003年国家自然科学基金杰出基金）自动计算时代开始，我们这门课程是研究自动计算开始时的一些有趣事情堪称计算机界“诺贝尔奖”所纪念的人：图灵！Turing!本书内容介绍第一章:Sets,RelationsandLanguages主要讲述了离散数学中的集合运算引入了语言这个概念如何去形式化描述出一个语言的性质？所有a和b出现相同次数的语言：{e,ab,ba,aabb,…,}语言是可以枚举的么？本书内容介绍第二章:FiniteAutomata什么是计算机？第二章开始的自动机理论则给出了明确回答KindsofAutomata第二章:FiniteAutomataKindsofAutomata第三章:Context-freeLanguages（PushdownAutomata）KindsofAutomata第四章:TuringMachinesTuringMachinesareformalversionofalgorithms:InotherwordsNocomputableprocedurewillbeconsideredanalgorithmunlessitcanbepresentedasaTuringMachine乔姆斯基（Chomsky）对语言的分类第五章Undecidability第六章第七章ComputationalComplexityNP-completeness