计算理论

南昌航空大学信息工程学院计算机应用技术系1计算理论TheoryofComputation第0章课程简介南昌航空大学信息工程学院计算机应用技术系2教师：刘琳岚办公地点：D511电话：[phone]QQ：765693987E-mail：[e-mail]指导老师第0章课程简介南昌航空大学信息工程学院计算机应用技术系3任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？什么是计算机科学的基础？什么是计算机科学的基本问题？诸如什么是形式语言？什么是计算？什么是能计算的？什么是不能计算的？什么是算法？如何评价算法？什么样的算法是可行的？这些问题能否判定？这又引出什么是可判定的？什么是不可判定的？这些问题就是计算理论要讨论的问题。课程的引入第0章课程简介南昌航空大学信息工程学院计算机应用技术系4计算理论：就是研究理论计算机的科学。理论计算机：是研究计算机的理论模型，研究计算机的本质，也就是把计算机看成一个数学系统。(因为计算机科学的基本思想和模型在本质上是数学－－离散的。)课程的性质－－计算机科学的理论课第0章课程简介南昌航空大学信息工程学院计算机应用技术系5课程重点内容：计算理论的三个传统核心领域形式语言与自动机理论：研究计算的数学模型的定义和性质；正则文法与有限自动机(正则语言)上下文无关文法与下推自动机(上下文无关语言)图灵机(递归可枚举语言)可计算性理论：研究计算和可计算性概念、研究各种计算模型及其等价性、研究不可计算性即不可解性；计算复杂性理论：研究实际上的不可计算性、研究P和NP问题。时间复杂性、空间复杂性。可计算性理论、计算复杂性理论需要对计算机给出一个准确的定义，而形式语言与自动机理论允许使用计算的形式化定义，所以是学习计算理论的起点。课程的内容第0章课程简介南昌航空大学信息工程学院计算机应用技术系6是什么将上述三个领域（自动机、可计算性、计算复杂性）联系在一起？－－计算机的基本能力和局限性是什么？什么是计算？什么是可以计算的？什么是计算的形式化描述？课程的核心：从形式化、逻辑和数学的角度去了解计算机的能力与局限性是什么？TheoryofComputation第0章课程简介南昌航空大学信息工程学院计算机应用技术系7计算是一种将单一或复数之输入值转换为单一或复数之结果的一种思考过程。计算的定义有许多种使用方式，有相当精确的定义，例如：使用各种算法进行的“算术”，也有较为抽象的定义，如：在一场竞争中“策略的计算”或是“计算”两人之间关系的成功机率。什么是计算？第0章课程简介南昌航空大学信息工程学院计算机应用技术系8计算不仅是数学的基础技能，而且是整个自然科学的工具：在学校学习时必须掌握计算这一个基本生存技能；在科研中，必须运用计算攻关完成课题研究；在国民经济，计算机及电子等行业取得突破发展都必须在数学计算的基础上。因此计算在基础教育，各学科的广泛应用，高性能计算等先进技术方面都是主要方法。计算中的关系第0章课程简介南昌航空大学信息工程学院计算机应用技术系9广义的计算包括：数学计算，逻辑推理，文法的产生式，集合论的函数，组合数学的置换，变量代换，图形图像的变换，数理统计等；人工智能解空间的遍历，问题求解，图论的路径问题，网络安全，代数系统理论，上下文表示感知与推理，智能空间等；数字系统设计（例如逻辑代数），软件程序设计（文法），机器人设计，建筑设计等设计问题。英文中的计算为“Calculation”，来自拉丁文中的“Calculus”，指的是算盘上用来计算的小石头。广义的计算第0章课程简介南昌航空大学信息工程学院计算机应用技术系10母系氏族社会后期，即旧石器時代的后期,结绳为数；东汉、南北朝/元明/唐（清明上河图），算盘;1642年，年仅19岁的法国科学家布雷兹·帕斯卡借鉴了珠算原理，发明了机械计算机;德国科学家格特弗里德·莱布尼兹发明了“步进式计算机”，能够进行乘、除和平方的计算;20世纪初，英国剑桥大学教授Babbage前瞻性地提出：人类有可能设计出一种机械装置，完成一系列计算，并把信息转化为数字，用机器对它们进行处理。在计算机出现之前：机械计算第0章课程简介南昌航空大学信息工程学院计算机应用技术系1120世纪前半叶，数学家哥德尔、图灵、丘奇发现－－一些基本问题不能用计算机来解决：确定一个数学命题是真是假？17世纪，费马(大)定理：当整数n2时，关于自然数x,y,z的不定方程无正整数解：xn+yn=zn。什么是可以计算的？解析几何、微积分、概率论、数论、光学第0章课程简介南昌航空大学信息工程学院计算机应用技术系12费马(大)定理的证明：二十世纪电脑发展以后，许多数学家用电脑计算可以证明这个定理,当n为很大时是成立的。用现代的电子计算机只能证明：当n小于等于4100万时，费马大定理是正确的。1983年，电脑专家斯洛文斯基借助电脑运行5782秒证明当n为286243-1时费马定理是正确的(*286243-1大约为25960位数)。1994年9月19日，威利斯(AndrewWiles)与他的学生终于交出完整无瑕的解答，数学界的梦魇终於结束。1997年6月，威利斯在德国哥庭根大学领取了佛尔夫斯克尔奖。只需证明x４+y４=z４和xp+yp=zp(p为奇质数)都没有整数解计算的验证形式？－－形式化问题第0章课程简介南昌航空大学信息工程学院计算机应用技术系13形式化证明的先驱：图灵奖获得者C.AntonyR.Hoare教授以及Hoare逻辑。1969年发表了论文“计算机程序的公理基础”提出了名为Hoare逻辑的形式系统理论。这个系统的用途是为了使用严格的数理逻辑推理计算机程序的正确性提供一组逻辑规则。设计了形式化语言（CommunicatingSequentialProcesses,CSP）用以描述并发进程相互作用。1980年获得ACM设立的计算机界最高奖——图灵奖:由于在编程语言的定义和设计方面的基础性贡献。本课程的内容基本属于形式化问题。计算的验证形式？第0章课程简介南昌航空大学信息工程学院计算机应用技术系14图灵的伟大贡献：Turing!AlanTuring,1912.6.23-1954.6.7天才的图灵设想－－能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。真正的人工智能之父，早在1941年就开始考虑“机器智能”问题。世界上第一台计算机ENIAC1946年2月诞生于美国宾夕法尼亚大学莫尔学院。但学术界公认，电子计算机的理论和模型是由英国数学家图灵在此前10年即1936年发表的一篇论文。近代计算技术的起源第0章课程简介南昌航空大学信息工程学院计算机应用技术系15图灵的伟大贡献：Turing!“OnComputableNumberswithanApplicationtotheEntscheidungsproblem.”“论可计算数及其在判定问题中的应用。”——ProceedingsoftheLondonMathSociety2(42),1936,pp.173-198.提出一种十分简单但运算能力极强的理想计算装置，用它来计算所有能想象得到的可计算函数。图灵机不是一种具体的机器，而是一种思想模型。近代计算技术的起源第0章课程简介南昌航空大学信息工程学院计算机应用技术系16图灵命题：图灵1936年的传世论文《论可计算数及其在判定问题中的应用》主要是回答德国大数学家希尔伯特在1900年提出的著名的“23个数学难题”之中的第10个，问题涉及逻辑的完备性，即是不是所有的数学问题在逻辑上都是可解的。这篇论文说，有些数学问题是不可解的。自动计算机的理论模型是在该论文中提出的，这种抽象模型可以把推理化作一系列简单的机械动作,被称作为图灵机的模型,有许多等价描述。歪打正着，图灵机模型到上世纪60年代却转变成用来说明可计算能力的模型。为纪念该文发表30周年，1966年设立“图灵奖”,以纪念这位计算机科学理论的奠基人。图灵命题第0章课程简介南昌航空大学信息工程学院计算机应用技术系17姚期智(AndrewChi-ChihYao)：1967年获得台湾大学物理学士学位；1972年获得美国哈佛大学物理博士学位；1975年获得美国伊利诺依大学计算机科学博士学位；1975年至1986年曾先后在MIT数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授；1986年至2004年在普林斯顿大学计算机科学系担任WiliamandEdnaMacaleer工程与应用科学教授；2004年起在清华大学任全职教授。2000年图灵奖得主，美国科学院院士，美国科学与艺术学院院士，中科院外籍院士复杂性理论、随机理论、密码学以及通信复杂性。获图灵奖的华人－－姚期智第0章课程简介南昌航空大学信息工程学院计算机应用技术系18图灵机：一条双向可无限延长的、被分成一个个方格的磁带,格里写有符号一个有限状态控制器一个读写磁头图灵机的动作由五元组确定：q,b,a,m,q’其中，q和q’为控制器的当前状态和下一状态；b和a为方格中的原有符号和修改后的符号，m指示磁头移动方向，或左或右或停。由状态和符号确定的工作过程称图灵机程序。图灵机邱奇－图灵论题图灵论题：凡是可计算的函数都可以用图灵机计算。邱奇论题：任何计算，如果存在一有效过程，它就能够被图灵机实现。第0章课程简介南昌航空大学信息工程学院计算机应用技术系19图灵机－－现代计算机的理论模型与现代计算机相同之处：程序与数据混合在一起，由控制器控制执行。与现代计算机不同：内存无限大！没有考虑输入与输出！（所有信息都在子带上）图灵机第0章课程简介南昌航空大学信息工程学院计算机应用技术系20冯·诺依曼（1903-1957）计算机由控制器、运算器、存储器、输入设备和输出设备组成。基本原理：存储程序（StoredProgram）并按地址顺序执行。控制器按照程序顺序，逐条把指令和数据从存储器中取出并加以执行，自动完成由程序所描述的处理工作。冯·诺伊曼结构的计算机第0章课程简介南昌航空大学信息工程学院计算机应用技术系21冯·诺依曼结构的计算机计算机的核心包括运算器和控制器在内的中央处理单元(CPU)。计算机系统是由软硬件组成的多级层次结构，由微程序级、一般机器级、操作系统级、汇编语言级、高级语言级组成。从此，人们把CPU和操作系统看作计算机的“核”。冯·诺伊曼结构的计算机裸机系统软件中间件应用软件第0章课程简介南昌航空大学信息工程学院计算机应用技术系22冯·诺依曼结构的计算机：在每一个层次上都能够进行程序设计。高级语言程序设计过程是“分析问题—建立数学模型—选择数据结构—设计算法—编程—编译器逐层向下编译成为机器可执行代码由机器运行”的过程。软件=程序+文档=算法+数据+文档程序设计和软件工程第0章课程简介南昌航空大学信息工程学院计算机应用技术系23互联网之父VintonG.Cerf（1943-）美国国家研究推进机构CNRI董事长RobertE.Kahn（1938-）Google公司副总裁兼首席互联网顾问因为在TCP/IP协议方面所取得的杰出成就，他们在2004年荣膺图灵奖，2005年获得美国总统颁发的总统自由勋章。第0章课程简介南昌航空大学信息工程学院计算机应用技术系24万维网之父TimBerners-Lee（1955-）伯纳斯.李将超文本引入互联网，创建万维网协议HTTP和HTML,2004年成为全球最大的技术类奖——千年技术奖的首位获奖者，现任万维网联盟(）主席。第0章课程简介南昌航空大学信息工程学院计算机应用技术系25维基之父LawrenceSanger（1968-）JimmyWales（1966-）Wikipedia2001年1月15日正式问世，目前世界上最大的Wiki系统，“让世界上