计算理论基础课件_Introduction

1、Elements of the Theory of ComputationIntroductionTextbooknElements of the Theory of Computation (Harry R. Lewis/ Christos H. Papadimitriou)Why this CourseAutomata (第二章第二章：Finite-state Machine, 第三第三章章：Pushdown Automata, 第四章第四章：Turing Machines)Computability (第五章第五章: Undecidability)Complexity (第六章第六章:

2、Computational; 第七章第七章 : NP-completeness)Mathematic Preliminaries (第一章第一章 : Sets, Relations and Language) 也就是从形式化、逻辑和数学的角度去了解也就是从形式化、逻辑和数学的角度去了解计算机的能力与局限性是什么？计算机的能力与局限性是什么？主要了解理论计算机科学的如下基本问题主要了解理论计算机科学的如下基本问题与计算理论有关的问题与计算理论有关的问题n什么是计算？什么是计算？n什么是可以计算的？什么是可以计算的？n什么是计算的形式化描述？什么是计算的形式化描述？在计算机出现之前：机械计算在计算

3、机出现之前：机械计算n结绳为数（结绳为数（在拉丁语中，在拉丁语中，“计算计算”的单词的单词Calculus，其本意就是用于计算的小石子）其本意就是用于计算的小石子）n算盘算盘n1642年，年仅年，年仅19岁的法国科学家布雷兹岁的法国科学家布雷兹帕斯卡借鉴了帕斯卡借鉴了珠算原理，发明了机械计算机；珠算原理，发明了机械计算机；n德国科学家格特弗里德德国科学家格特弗里德莱布尼兹改进了前者的设计，莱布尼兹改进了前者的设计，发明了发明了“步进式计算机步进式计算机”，能够进行乘、除和平方的，能够进行乘、除和平方的计算。计算。n20世纪初，英国剑桥大学数学教授世纪初，英国剑桥大学数学教授Babbage前瞻性

4、地前瞻性地提出计算机领域的一个重要思想：人类有可能设计出提出计算机领域的一个重要思想：人类有可能设计出一种机械装置，完成一系列计算，并把信息转化为一种机械装置，完成一系列计算，并把信息转化为数数字字，用机器对它们进行处理。，用机器对它们进行处理。 什么是可以计算的什么是可以计算的) 3,(nRZYXZYXnnn费马声称当费马声称当n2n2时，就找不到满足时，就找不到满足x xn n +y+yn n = z= zn n的整数解的整数解费马定理费马定理计算的验证形式计算的验证形式n数据测试数据测试n形式化测试形式化测试C. Antony R. HoareHoare 逻辑逻辑完成形式化证明的杰出工作

5、，但是仍旧存在困完成形式化证明的杰出工作，但是仍旧存在困难（本书介绍的内容基本属于形式化问题）难（本书介绍的内容基本属于形式化问题）近代计算技术的起源近代计算技术的起源 图灵的伟大贡献：图灵的伟大贡献： Turing !计算机界以他的名字命名了计算机界以他的名字命名了“图灵奖图灵奖”，从从1966年每年颁授一次，被誉为计算机年每年颁授一次，被誉为计算机界的界的“诺贝尔奖！诺贝尔奖！”任何事物的产生均有理论准备，任何事物的产生均有理论准备，计算机的产生也不例外计算机的产生也不例外20世纪初几个有关计算的热点研世纪初几个有关计算的热点研究：究：n德国大数学家希尔伯特（德国大数学家希尔伯特（DHil

6、lbert）1928年提出著名的年提出著名的“希尔伯特纲领希尔伯特纲领”，认为数学是认为数学是完备（完备（Completeness）和和一一致（致（Consistency）的，可以由数学本的，可以由数学本身去证明。身去证明。n所有属于自然数集合的数均属于自然数所有属于自然数集合的数均属于自然数集合（集合（完备完备）n所有不属于自然数集合的数均不属于自所有不属于自然数集合的数均不属于自然数集合（然数集合（一致一致）证明本身是一个计算过程，如何寻找一个证明本身是一个计算过程，如何寻找一个自动机进行证明？自动机进行证明？寻找能够替代人智慧工作的机械或装寻找能够替代人智慧工作的机械或装置置！Godel

7、的贡献的贡献n19311931年，年，“希尔伯特纲领希尔伯特纲领”被奥地利逻被奥地利逻辑学家哥德尔（辑学家哥德尔（K KGodelGodel）用用递归函数递归函数（Recursive）理论推翻，他认为没有一理论推翻，他认为没有一种公理系统可以导出数论中所有的真实种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。命题，除非这种系统本身就有悖论。Gdels Theorem has been used to argue that a computer can never be as smart as a human being because the extent of its kn

8、owledge is limited by a fixed set of axioms, whereas people can discover unexpected truths . 图灵的设想图灵的设想n天才的图灵设想：天才的图灵设想：能否有这样一台机器能否有这样一台机器，通过某种一般的机械步骤，能在原则，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。上一个接一个地解决所有的数学问题。19361936年图灵发表一篇著名的论文论数年图灵发表一篇著名的论文论数字计算在判决难题中的应用。他提出字计算在判决难题中的应用。他提出了一种十分简单但运算能力极强的理想了一种十分简单但运

9、算能力极强的理想计算装置，用它来计算所有能想象得到计算装置，用它来计算所有能想象得到的可计算函数。的可计算函数。计算表格计算表格Let me seeWrite Here一个一般的计算过程一个一般的计算过程程序程序数据数据图灵机：现代计算机的理论模型图灵机：现代计算机的理论模型 两端无限长的纸带两端无限长的纸带控制器（控制器（读写或计算）读写或计算）与现代计算机相同与现代计算机相同之处：之处：程序与数据程序与数据混合混合在一起，由控在一起，由控制器控制执行制器控制执行与现代计算机与现代计算机不同：不同：内存无内存无限大！没有考限大！没有考虑输入与输出虑输入与输出！（所有信息！（所有信息都在子带上

10、）都在子带上）图灵对可计算的定义：图灵对可计算的定义：n被求解问题需要形式化；被求解问题需要形式化；n必须设计一个算法；必须设计一个算法；n算法需要有合理的复杂度（空间与时间算法需要有合理的复杂度（空间与时间复杂度）复杂度）可计算工具不只是计算机可计算工具不只是计算机nrecursive function(Godel-Herbrand,1934) n-Calculus(Church-Kleene,1932-1934) nTuring machine(Alan Turing 1936) 已经证明：如上三种计算工具功能是等效的已经证明：如上三种计算工具功能是等效的！为什么只是图灵机成为现代计算为什

11、么只是图灵机成为现代计算机理论基础机理论基础n是物理机械平台，而非数学逻辑平台是物理机械平台，而非数学逻辑平台n当时工艺机械达到了设计这种机械平台当时工艺机械达到了设计这种机械平台的能力！的能力！图灵对计算机智能的思考图灵对计算机智能的思考n“计算机会思考么？计算机会思考么？”，这样的问题是，这样的问题是没有什么意义的。没有什么意义的。 （图灵，（图灵，1950年）年）n但是我们可以通过如下测试去判断计算但是我们可以通过如下测试去判断计算机是否有智能？机是否有智能？图灵测试图灵测试哪个答案是计算哪个答案是计算机回答的呢？机回答的呢？计算机有智能么？计算机有智能么？n目前没有任何程序通过图灵测试

12、？目前没有任何程序通过图灵测试？n国际象棋冠军的确败在了国际象棋冠军的确败在了“深蓝深蓝”手下手下n计算机强于快速搜索；人脑强于归纳推计算机强于快速搜索；人脑强于归纳推理理人机大战人机大战卡斯帕罗夫卡斯帕罗夫 VS 深蓝深蓝那个时候，我感觉我的面前有种新的智慧！那个时候，我感觉我的面前有种新的智慧！能改行下围棋吗？能改行下围棋吗？2个回合以后个回合以后 位置变化位置变化 国际象棋国际象棋 约约150万种万种 围棋围棋 16亿种亿种7个回合以后个回合以后 位置变化位置变化 国际象棋国际象棋 3514 种种 围棋围棋 20014 种种与深蓝同等速度的围棋电脑每与深蓝同等速度的围棋电脑每下一子需要想

13、下一子需要想一年半一年半时间！时间！结论：脑功能有着独特的功能特点，脑功能的认识将使结论：脑功能有着独特的功能特点，脑功能的认识将使人工智能研究取得的革命性突破。人工智能研究取得的革命性突破。图灵测试仍然是一个热点！图灵测试仍然是一个热点！nCAPTCHA 是是Completely Automated Public Turing Test to Tell Computers and Humans Apart （全自动区分计算机和人类全自动区分计算机和人类的图灵测试）的简称。一个的图灵测试）的简称。一个CAPTCHA是任是任何一个能区分计算机和人类的程序。何一个能区分计算机和人类的程序。n n这

14、种程序必须能生成并评价人类能很容易通这种程序必须能生成并评价人类能很容易通过但计算机却通不过的测试。这个要求本身过但计算机却通不过的测试。这个要求本身就是悖论，因为这意味着一个就是悖论，因为这意味着一个CAPTCHA必必须能生成一个它自己不能通过的测试。须能生成一个它自己不能通过的测试。 CAPTCHA项目项目n著名的计算机专家著名的计算机专家Blum夫妇在卡内基夫妇在卡内基-梅隆大梅隆大学（学（CMU）领导；领导；n美国计算机学会（美国计算机学会（ACM）由于由于Manuel Blum奠奠定了定了计算复杂性理论的基础和在密码术及程序计算复杂性理论的基础和在密码术及程序校验方面校验方面的贡献，

15、把的贡献，把1995年度的图灵奖颁给了年度的图灵奖颁给了Manuel Blumn2001年，在美国国家科学基金年，在美国国家科学基金1.56亿美元亿美元IT研研究拨款中（中国国家自然科学基金当年资助为究拨款中（中国国家自然科学基金当年资助为7千千7百万人民币），百万人民币），CMU得到了得到了2400万美元万美元而在而在CMU的总共的总共14个受资助项目中，最大个受资助项目中，最大的一个是得到的一个是得到550万美元的万美元的“CAPTCHA项目项目”。Blum一家三口（一家三口（Manuel Blum与与Lenore Blum的儿子麻省理工学院博士的儿子麻省理工学院博士Avrim Blum也

16、也在此和父母并肩战斗）均是此项目的研究人员在此和父母并肩战斗）均是此项目的研究人员。中国也十分重视理论计算机科学中国也十分重视理论计算机科学研究研究n上下文无关语言的递归函数理论的后续上下文无关语言的递归函数理论的后续研究研究 （2003年国家自然科学基金面上项年国家自然科学基金面上项目）目）n计算机科学技术的基础理论（计算机科学技术的基础理论（ 2003年国年国家自然科学基金杰出基金）家自然科学基金杰出基金）自动计算时代开始，我们这门课自动计算时代开始，我们这门课程是研究自动计算开始时的一些程是研究自动计算开始时的一些有趣事情有趣事情堪称计算机界堪称计算机界 “诺贝尔奖诺贝尔奖”所所纪念的人

17、：图灵纪念的人：图灵 ！Turing!本书内容介绍本书内容介绍第一章第一章: Sets, Relations and Languages主要讲述了离散数学中的集合运算主要讲述了离散数学中的集合运算引入了语言这个概念引入了语言这个概念如何去形式化描述出一个语言的性质？如何去形式化描述出一个语言的性质？所有所有a和和b出现相同次数的语言：出现相同次数的语言：e,ab,ba,aabb,语言是可以枚举的么？语言是可以枚举的么？本书内容介绍本书内容介绍第二章第二章: Finite Automata什么是计算机？什么是计算机？第二章开始的自动机理论则给出了明确第二章开始的自动机理论则给出了明确回答回答Kinds of Automata第二章第二章: Finite AutomataKinds of Automata第三章第三章: Context-free Languages （Pushdown Automata）Kinds of Automata第四章第四章: Turing Machi