图灵系列讲座.ppt

图灵系列讲座 东南大学邓建明 简单介绍以下内容 一 图灵 图灵奖及图灵奖获得者二 计算模型 图灵机等三 算法基本概念与NP完全性理论 一 图灵 图灵奖及图灵奖获得者简介 1912年6月23日 出生于英国伦敦 1931年 1934年 在英国剑桥大学国王学院学习 1932年 1935年 研究量子力学 概率论和逻辑学 1935年 由于独立发现中心极限定理 获Smith奖年仅23岁被选为剑桥大学国王学院院士 1936年 研究可计算性理论 提出 图灵机 构想 1936年 1938年 主要在美国普林斯顿大学做博士研究 研究内容涉及逻辑学 代数和数论等领域 1938年 1939年 返回剑桥从事研究工作 并应邀加入英国政府破译二战德军密码的工作 1940年 1942年 作为主要参与者和贡献者之一 在破译纳粹德国通讯密码的工作上成就杰出 并成功破译了德军U 潜艇密码 为扭转二战盟军的大西洋战场战局立下汗马功劳 AlanTuring生平简介 1943年 1945年 担任英美密码破译部门的总顾问 1945年 应邀在英国国家物理实验室从事计算机理论研究工作 1946年 此时图灵在计算机和程序设计原始理论上的构思和成果 已经确定了他的理论开创者的地位 由于图灵的杰出贡献 他被英国皇室授予OBE爵士勋衔 1947年 1948年 主要从事计算机程序理论的研究 并同时在神经网络和人工智能领域做出开创性的理论研究 1948年 应邀加入英国曼彻斯特大学从事研究工作 担任曼彻斯特大学计算实验室副主任 1949年 成为世上第一位把计算机实际用于数学研究的科学家 1950年 发表论文 计算机器与智能 提出著名的 图灵测试 理论 为后来的人工智能科学提供了开创性的构思 AlanTuring生平简介 1951年 提出生物增长的非线性理论 年仅39岁即被选为英国皇家学会会员 1952年 保守愚昧和冷战的时代 警察得知图灵与同性朋友密切交往的消息之后 有同性恋倾向的图灵被逮捕入狱 在法庭审判过程中 图灵明确告知人们 自己没有做错什么事 当时为了避免被判刑入狱 图灵被迫选择了为期一年的雌性激素注射的所谓 治疗 才得以重新返回研究工作 1953年 1954年 继续在生物和物理学等方面的研究 被迫承受对同性恋倾向的 治疗 致使原本热爱体育运动的图灵在身心上受到极大的伤害 1954年6月7日 42岁的图灵死在床上 床头有一个咬了一半的 在氰化物溶液中浸泡过的苹果 警方调查结论是自杀 一代英灵 就此过早离去 成为人类科学史上的一大遗憾 AlanTuring生平简介 AlanTuring 1912 23June Birth Paddington nearWestminsterCathedral London1931 34 UndergraduateatKing sCollege CambridgeUniversity1932 35 Study Quantummechanics probability logic1936 TheTuringmachine computability universalmachine1936 38 PrincetonUniversity Ph D Logic algebra numbertheory1938 39 ReturntoCambridge IntroducedtoGermanEnigmaciphermachine1939 40 TheBombe machineforEnigmadecryption1939 42 BreakingofU boatEnigma savingbattleoftheAtlantic AlanTuring 1943 45 ChiefAnglo Americancryptoconsultant Electronicwork 1945 NationalPhysicalLaboratory London1946 Computerandsoftwaredesignleadingtheworld 1947 48 Programming neuralnets andartificialintelligence1948 ManchesterUniversity1949 Firstseriousmathematicaluseofacomputer1950 TheTuringTestformachineintelligence1951 ElectedFRS Non lineartheoryofbiologicalgrowth1952 Arrestedasahomosexual lossofsecurityclearance1953 54 Unfinishedworkinbiologyandphysics1954 7June Death suicide bycyanidepoisoning Wilmslow Cheshire 有关Turing的一些佚事 两次报考剑桥三圣学院 TrinityCollege 最负盛名 未被录取 只好进了剑桥国王学院 King sCollege 攻读数学 不善言辞 有些木讷害羞 常咬指甲 在剑桥大学是一个衣着随便 不打领带的著名教授 妇孺皆知的怪才 患过敏性鼻炎 遇花粉流鼻涕不止 所以戴防毒面具骑车上班 招摇过市 成为剑桥大学的一大奇观 自行车掉链不修理 发现链条总是踏到一定的圈数时下滑 骑车时特别留心计算 能做到在链条下滑前一刹那戛然停车 后来在脚踏板旁装了一个小巧的机械计数器 到圈数时就停 歇口气换换脑子 再重新运动起来 怕英国失败把积蓄换成银子埋藏起来 二战后却忘了埋藏处 40岁时因同性恋被法院传讯 grossindecency AlanTuring的主要贡献 24岁提出了图灵机理论31岁参与Colossus的研制 二战时英国破解德国通讯密码的计算机 核心成员 33岁时构思了仿真系统35岁提出了自动程序设计的概念38岁设计了 图灵测试 39岁提出了关于生物增长的非线性理论有 计算机之父 人工智能之父 破译之父 等美誉 有人甚至认为他的贡献及对未来世界的影响几乎可与牛顿 爱因斯坦等巨人比肩 AlanTuring纪念馆 Enigma TuringTest 人工智能的试金石 1950年图灵提出用来判断计算机是否能够思考的方案 该年 图灵发表了里程碑式的论文 计算机能思考吗 第一次提出 机器思维 的概念 他逐条反驳了机器不能思维的各种论点 并做出了肯定的回答 他指出 最好的人工智能研究应该着眼于为机器编制程序 而不是制造机器 图灵测试的方法 提问人通过一种特殊的方式 提出各种问题 分别由一个人或一台机器进行回答 与提问人隔绝 如果经过相当多次数的提问 提问人辨别不出与他交流的对象是人还是机器 则可认为这部机器有智能 有科学家认为 20年后计算机能够轻松有效的通过各种形式的图灵测试 25年之内就会宣布计算机拥有了意识 TuringAward 目前由Intel公司和Google公司赞助 奖金为250 000美元 TuringAward 被公认为是计算机科学界的诺贝尔奖 最高奖项奖励在计算机科学技术研究中做出了创造性贡献 推动了计算机科学技术发展的杰出科学家1966年开始由ACM设立 美国计算机协会 1947年成立 与IEEEComputerSociety并列为计算机界最著名的两大国际学术组织 用Turing的名字来命名该奖 以纪念伟人对于计算机科学技术发展的功绩 通常每年1名获奖者 偶尔2名 同方向 02年3名 RSA 07年3名 设计错误自动化发现方法 虽未明确规定 但授奖较偏重于计算机科学理论和软件技术方面作出贡献的杰出科学家截止到2010年共发奖45届 共有57位科学家获奖唯一华人获奖者是姚期智 AndrewYao 美籍 2000年 Turing奖获得者的领域分布 姚期智在家中 2000年图灵奖获得者姚期智 祖藉湖北孝感 1946年12月24日出生于上海幼年随父母移居台湾 1967年毕业于台湾大学之后赴美国深造 1972年获哈佛大学物理学博士学位1975年获UIUC 伊利诺大学香槟分校 计算机科学博士学位 物理师从SheldonLeeGlashow 计算机师从C L Liu 曾先后在麻省理工学院 斯坦福大学 加州大学伯克利分校等美国高等学府从事教学和研究1986年至2004年6月任普林斯顿大学计算机科学系教授2004年9月正式加盟清华大学高等研究中心任全职教授他是美国国家科学院院士 中国科学院外籍院士 美国人文及科学院院士 1966 1970图灵奖获得者 1966A J Perlis PhD MIT Prof Yale wasProfatCMU deceased 因在新一代编程技术和编译架构方面的贡献而获奖 ALGOL语言和计算机科学的 催生者 1967MauriceV Wilkes PhD Cambridge Prof Cambridge因设计 研制出世界上第一台程序实现完全在内存的存储程序式计算机EDSAC而获奖 1968RichardW Hamming PhD UIUC Prof NavalPostgraduateSchool wasatBell deceased 因在计数方法 自动编码系统 检测及纠正错码方面的贡献而获奖 1969MarvinMinsky PhD Princeton Prof MIT因对人工智能的贡献被授予图灵奖 创立了框架理论 有 人工智能之父 之誉 1970J H Wilkinson BS Cambridge staff NationalPhysicalLaboratory London因在利用数值分析方法来促进高速数字计算机 ACE计算机 的应用方面的研究而获奖 1971JohnMcCarthy PhD Princeton Prof Stanford因对人工智能的贡献被授予图灵奖 LISP语言的发明人 亦有 人工智能之父 之誉 1972EdsgerW Dijkstra PhD UAmsterdam Prof UTAustin因在算法 编程语言方面的出众表现而获奖 1973CharlesW Bachman staff Honeywell因在数据库方面的杰出贡献而获奖 有 网状数据库之父 之誉 1974DonaldE Knuth PhD Caltech Prof Stanford因设计和完成TEX 一种创新的具有很高排版质量的文档制作工具 而被授予该奖 经典巨著 计算机程序设计的艺术 作者 1975AllenNewell PhD Stanford Prof CMU deceased 和HerbertA Simon PhD Chicago Prof CMU deceased 因在人工智能 人类识别心理和表处理的基础研究而获奖 人工智能符号主义学派的创始人 1971 1975图灵奖获得者 1976 1980图灵奖获得者 1976MichaelO Rabin PhD Princeton Prof Harvard和DanaS Scott PhD Princeton Prof CMU因他们的论文 有穷自动机与它们的决策问题 中所提出的非确定性有穷自动机这一很有价值的概念而获奖 1977JohnBackus BS Columbia staff IBM因对可用的高级编程系统设计有深远和重大的影响而获奖 FORTRAN和BNF的发明者 1978RobertW Floyd BS Chicago Prof Stanford因其在软件编程的算法方面的影响 并开创了包括剖析理论 编程语言的语义 自动程序检验 自动程序合成和算法分析在内的多项计算机子学科而获奖 前后断言法的创始人 1979KennethE Iverson因对程序设计语言理论 互动式系统及发明APL的贡献而获奖 1980C AnthonyR Hoare Prof Oxford nowatMicrosoft 因对程序设计语言的定义和设计所做的贡献而获奖 1981 1985图灵奖获得者 1981EdgarF Codd PhD Michigan staff IBM因在数椐库管理系统理论和实践方面的贡献而获奖 关系数据库之父 1982StevenA Cook PhD Harvard Prof UToronto因奠定了NP Completeness理论的基础而获奖 1983KenThompson MS Berkeley staff Bell Labs和DennisM Ritchie PhD Harvard staff Bell Labs在类属操作系统理论 特别是发明C和UNIX操作系统并推广而获奖 1984NiklausWirth PhD Berkeley Prof ETHZurich因开发了EULER ALGOL W MODULA和PASCAL一系列崭新的计算语言而获奖 结构化程序设计之父 1985RichardM Karp PhD Harvard Prof Berkeley因对算法理论的贡献而获奖 三栖学者 分枝限界法的创始人 1986 1990图灵奖获得者 1986JohnE Hopcroft PhD Stanford Prof CornellandRobertE Tarjan PhD Stanford Prof Princeton算法及数据结构的设计和分析中所取得的决定性成果而获奖 1987JohnCocke staff IBMRISC概念的首创者 因在面向对象的编程语言和相关编程技巧方面的贡献而获奖 1988IvanE Sutherland PhD MIT staff Sun因在计算机图形学方面的贡献而获奖 有 计算机图形学之父 之美誉 1989WilliamV Kahan PhD UToronto Prof Berkeley因在数值分析方面的贡献而获奖 他是浮点计算领域的专家 1990FernandoJ Corbato PhD MIT Prof MIT因在开发大型多功能 可实现时间和资源共享的计算系统 如CTSS和Multics方面的贡献而获奖 分时系统实现的核心人物 1991 1994图灵奖获得者 1991RobinMilner Prof Cambridge wasatUEdinburgh 因在可计算的函数的逻辑 LCF 标准元语言ML和并行理论 CCS 这三个方面的贡献而获奖 1992ButlerLampson PhD Berkeley staff Microsoft因在个人分布式计算机系统 包括操作系统 方面的贡献而获奖 1993JurisHartmanis PhD Caltech Prof Cornell和RichardE Stearns PhD Princeton Prof SUNYAlbany因奠定了计算复杂性理论的基础而获奖 1994RajReddy PhD Stanford Prof CMU和EdwardFeigenbaum PhD CMU Prof Stanford 因对大型人工智能系统的开拓性研究而获奖 1995 1999图灵奖获得者 1995ManuelBlum PhD MIT Prof Berkeley因奠定了计算复杂性理论的基础和在密码术及程序校验方面的贡献而获奖 1996AmirPnueli PhD WeizmannInstitute Prof NYU计算中引入Temporal逻辑和对程序及系统检验的贡献被获奖 1997DouglasEngelbart PhD Berkeley staff SRI提出互动式计算概念并创造出实现该概念的重要技术而获奖 1998JamesGray PhD Berkeley staff Microsoft因在数据库和事务处理方面的突出贡献而获奖 1999FrederickP Brooks Jr PhD Harvard Prof UNC因对计算机体系结构和操作系统以及软件工程做出了里程碑式的贡献 2000 2002图灵奖获得者 2000AndrewChi ChihYao PhD UIUC Prof Princeton因对计算理论做出了诸多根本性的重大贡献 图灵奖自创立以来获得该奖项的首位华裔学者 全球华人的骄傲 2001Ole JohanDahl andKristenNygaard Profs UOslo因他们在设计编程语言SIMULAI和SIMULA67时产生的基础性想法 这些想法是面向对象技术的肇始 2002RonaldL Rivest PhD Stanford MIT AdiShamir PhD Weizmann LeonardM Adelman PhD Berkeley USC他们在公共密匙算法上所做杰出贡献 RSA算法是当前在互联网传输 银行以及信用卡产业中被广泛使用的安全基本机制 2003 2005图灵奖获得者 2003AlanKay PhD Utah HPLabs wasatXeroxPARC 发明第一个完全面向对象的动态计算机程序设计语言Smalltalk 2004VintonG Cerf RobertE Kahn Forpioneeringworkoninternetworking includingthedesignandimplementationoftheInternet sbasiccommunicationsprotocols TCP IP andforinspiredleadershipinnetworking 由于在互联网方面开创性的工作 这包括设计和实现了互联网的基础通讯协议 TCP IP 以及在网络方面卓越的领导 2005PeterNaur由于在设计Algol60程序设计语言上的贡献 Algol60语言定义清晰 是许多现代程序设计语言的原型 2006 2007图灵奖获得者 2006FrancesElizabethAllen对于优化编译器技术的理论和实践做出的先驱性贡献 这些技术为现代优化编译器和自动并行执行打下了基础 有史以来第一位获得图灵奖的女性 2007EdmundM Clarke EAllenEmerson JosephSifakis由于他们开发模型检测技术 并使之成为一个广泛应用在硬件和软件工业中非常有效的算法验证技术所做的奠基性贡献 DDJ则将三人的贡献称为 在发现计算机硬件和软件中设计错误的自动化方法方面的工作 2008 2009图灵奖获得者 2008BarbaraLiskovForcontributionstopracticalandtheoreticalfoundationsofprogramminglanguageandsystemdesign especiallyrelatedtodataabstraction faulttolerance anddistributedcomputing 对编程语言和系统设计的实践与理论基础 尤其是数据抽象 容错和分布式计算方面的贡献 有史以来第二位女性图灵奖得主 2009CharlesThackerForthepioneeringdesignand realizationofthefirstmodernpersonalcomputertheAltoatXeroxPARCandseminalinventionandcontributionstolocalareanetworks includingtheEthernet multiprocessorworkstations snoopingcachecoherenceprotocols andtabletpersonalcomputers 与计算理论有关的图灵奖获得者 1 1972 E W Dijkstra 美Burroughs公司 求最短路径的Dijkstra算法 PV操作 结构化程序设计 goto有害 等 1974 D E Knuth stanford 算法最早的奠基人之一 现代 算法 与 数据结构 等名词及内涵的提出 KMP算法 多卷算法巨著的作者 LR k 文法 Tex编辑器等 1976 M O Rabin 以色列人 D S Scott 英国人 师兄弟 导师A Church 非确定有穷自动机的提出 判定问题等 Rabin 计算复杂性概念的雏形 随机算法的思想奠定 寻找及判定素数算法 单向函数等 Scott 语义学等 1978 R W Floyd Stanford Heap sort算法 求最短路径的Floyd动态规划算法等 编译及优化 优先文法等 程序正确性证明等 与计算理论有关的图灵奖获得者 2 1980 C A R Hoare Oxford nowatMicrosoft 程序设计 发明CASE While语句等 Quick sort算法 数据通信等 1983年ACM评出的1 4世纪中最有影响的25篇论文 Hoare与Dijkstra有两篇入选 其余人只有一篇 1982 S A Cook 加Toronto大学 NP 完全 概念的提出与理论的奠定 算法复杂性等 1984 N Wirth 瑞士苏黎世高工 程序 算法 数据结构 结构化程序设计分 创始人 ExtendedBNF等 Pascal之父 1985 R M Karp UC Berkeley 计算机系 数学系 工业工程运筹学系 三栖教授 哈佛文学士 理学硕士 数学博士 分枝限界法的创始人 与Held Rabin Karp子串匹配算法 求网络最大流的Edmonds Karp算法 NP 完全理论 Karp规约等 随机算法 并行算法等 与计算理论有关的图灵奖获得者 3 1986 J E Hopcroft Cornell R E Tarjan Princeton 图论算法 e g 深度优先算法 连通性 平面图判定 数据结构Hopcroft 形式语言与自动机名著作者 与Ullman 算法名著作者 与Aho Ullman 算法好坏的衡量尺度 渐进时间复杂性 2 3树 机器人等 Tarjan D E Knuth的博士生 集合的Union find算法 平摊分析 持久性数据结构及各种数据结构 e g 动态树 八字型 树 自调整结构 1993 J Hartmanis Cornell R E Stearns Albany 计算复杂性理论的主要奠基人 系统化的理论体系及命名 Hartmanis Hartmanis矩阵乘法 Hartmanis快速离散傅立叶变换 Stearns 首先提出将上下文无关文法理论应用于编译器设计等 与计算理论有关的图灵奖获得者 4 1995 M Blum UC Berkeley 计算复杂性理论 受M O Rabin到MIT演讲的启发 e g Blum测度等 复杂性理论应用 e g 密码学 软件工程 2000 AndrewYao 姚期智 Princeton 现在清华 计算复杂性 量子计算 密码学 e g 单向函数 通信理论等 2002 RonaldL Rivest AdiShamir LeonardM Adelman 公共密钥算法 RSA算法是当前在互联网传输 银行以及信用卡产业中被广泛使用的安全基本机制 到目前为止的56位获奖者中至少有19位主要或曾经从事与计算理论有关的研究 与计算理论有关的图灵奖获得者 5 EdsgerWybeDijkstra RichardWesleyHamming 34 34 与计算理论有关的图灵奖获得者 6 35 35 与计算理论有关的图灵奖获得者 7 NiklausWirth StephenA Cook 未来计算 JamesGray的12个目标 1 可伸缩性 创造一种软件和硬件的体系结构 可以扩展一百万倍 即 某个具体应用的存储和处理能力可以通过添加资源而自动地提高一百万倍 也就是说处理同一问题速度提高一百万倍或用同样的时间可以处理规模扩大一百万倍的问题 这里 自动地 是指 除了加入资源 用户用不着做任何其他干预 如重新编程 对系统配置进行调整 2 通过图灵测试能力 建造计算机系统 其通过图灵测试的概率至少为30 3 听写能力 机器的听写水平应能达到或相当于使用母语的人的听写水平 4 诵读能力 机器的文本诵读水平应能达到或相当于用母语的人的诵读水平 5 视觉能力 能够像人那样识别目标和运动状态 6 记忆能力 能够像人那样记录下他所看到和听到的一切 而且在需要时能够迅速提取任何一个纪录 7 智能资料存储处理系统 建立一个系统 对于一个给定的文本语料库 关于所存储的文本的任何问题都能够回答 可以对库中任一段文本做出摘要 回答和摘要的准确程度和速度相当于该领域的专家水平 对于音乐 图像 艺术作品及视频节目也能达到同样的水准 未来计算 JamesGray的12个目标 8 远程临场感 模拟一个地方的场景 使你感觉就好像是在现场听见和看见所发生的一切 远程观察 模拟某人出席另一地点的活动 就好像某人在现场一样 与在现场的人士互相交流 远程参与 9 无故障系统 建造一个系统 每天可供上百万人使用 而管理它只需要一个非全时工作人员 10 具有安全性的系统 保证第9项的系统只向得到授权的人士提供服务 任何未得到授权的人都无法使该系统中断业务 存储于系统中的信息也不会被窃取 而且必须严格证明确实获得了以上各项性能 11 随时可用性 保证该系统在每一百年内中断工作的时间不超过1秒 即可用度达到99 999999 而且必须严格证明确实达到了这一指标 12 自动编程工具 建造一种需求描述语言或用户界面 具有如下功能 a 使人可以很容易地表述其设计 比现有语言容易1000倍 b 计算机可以直接进行编译 c 可以描述任何应用 具有完备性 系统应该能对具体应用需求进行推理 对例外情况和不完备需求能提出疑问 但不能因此而导致其使用变得困难起来 二 计算模型简介 TuringMachine 1 1936年 AlanTuring提出一个问题 什么是计算 什么问题是可计算的 Turing认为计算是一个人拿一支笔在一张纸上进行的操作 输入是眼睛看到的符号 根据脑中的规则在纸上擦掉或写上一些符号 再用眼睛看下面的符号 根据规则进行擦写的工作 重复上述工作 直到这个人认为可以结束为止 此时 最后写下的符号就是所要的结果 特点 在这个 计算 过程中 只用到了有穷多个符号 TuringMachine 2 Turing希望有这样一种机器 通过某种一般的机械步骤 在原则上能够一个接一个地解决所有的数学问题 Turing根据前述的过程构造出了一个理想化的计算装置 该计算模型可用来计算所有能够想象得到的可以计算的函数 TuringMachine 3 这个计算模型有一条带子 带子相当于一张纸 带子上有无穷多个方格 每个方格中可以写给定有穷符号表中的一个字符 有一个读写头 读相当于用眼睛来看 写相当于擦或写 还有一个有穷状态控制器FSC 相当于人脑 FSC根据当前读到的符号 相当于眼睛看到的 和自己当前的状态 相当于人脑的决策 决定三件事 TuringMachine 4 FSC根据当前读到的符号 相当于眼睛看到的 和自己当前的状态 相当于人脑的决策 决定三件事 改变读写头当前所指的字母 相当于在纸上改写一些符号 改变 或不改变 自己当前的状态 准备下一步的计算 使读写头左移或右移或不动 相当于改变眼睛看到的范围 注意如何把一般问题抽象成为数学模型的过程 TuringMachine 5 Turing发现该模型可以实现非常复杂的计算 Turing称 凡是Turing机可以计算的问题就是可计算的 否则就是不可计算的 此断言是否过于武断 是否有其它计算模型的计算范围比Turing机的计算范围更大 由此引出可计算性理论的深入研究 丘奇 图灵论题 1 Church TuringThesis 任何合理的计算模型都是相互等价的 计算范围相同 讨论是由Turing引出的 结论是由Church下的 合理 单位时间内可以完成的工作量 有一个多项式的上限 不合理举例 任意多道的并行计算 由于有 任何 二字 故无法进行证明 但迄今为止所有被提出的合理计算模型均满足该论题 丘奇 图灵论题 2 Church最初认为 直觉上的可计算应该是递归函数可计算 但后来发现递归函数可计算的范围与Turing可计算的范围相同 后经研究又发现Post系统 演算等计算模型的计算范围也相同 由此推想其它合理的计算模型的计算范围也是相同的 Church TuringThesis更严格一些应为 合理的计算模型均等价于Turing机的计算范围或其子集 丘奇 图灵论题 3 Church TuringThesis说明了可计算性本身是不依赖于具体模型的客观存在 由于Turing最先揭示了计算的本质 故计算机科学的最高奖被命名为Turing奖 Turing机的形式有多种 除单带双向Turing机之外 还有单带单向Turing机 多带双向Turing机 多带单向Turing机等 已经证明 这些Turing机模型的计算能力 在多项式意义下 相同 图例 k带单向Turing机 多带Turing机在讨论问题时方便一些 相当于有多行 单带机相当于只有一行 e g 325 678 40 160 2400 350 1400 2100 3000 12000 180000 k带单向Turing机的 转移函数 与单带双向Turing机类似 有一个有穷状态控制器FSC FSC根据当前读到的符号和自己当前的状态决定三件事 1 改变 或不改变 自己当前的状态 2 改变 或不改变 任一个或全部的读写头当前所指的字母 3 使任一个或全部的读写头左移或右移或不动 若状态 读写头当前所指字母 读写头位置均不改变 则Turing机自动停机 故通常3项中至少有1项改变 以上动作的内容均由 转移函数决定 k带单向Turing机的形式描述 七元组 Q T I b q0 qf Q 由有穷多个状态的构成集合 状态通常用小写q表示 T 带符号的集合 有限个带符号 I 输入符号的集合 包含在带符号集合T中 b 表示空白的特殊符号 在T中而不在I中 q0 表示初始状态 qf 表示最后的 或接受 状态 转移函数 Q Tk Q T L R S k各种Turing机的主要的区别就在于它的转移函数 k带Turing机的 转移函数形式 各种Turing机的主要的区别就在于它的转移函数 但不同的Turing机 函数不同 实现的功能有可能会相同 识别回文 正反读均相同的01串 的双带Turing机 转移函数的图表示 输入串为01110时的部分执行情况 该双带Turing机的执行 1 在 转移函数d的图表示中 左面括号中的两个字符分别代表第一和第二条带上读写头当前所注视的字符 右面括号中的前两个字符分别代表要在两条带上写的新字符 后两个字符分别代表两个读写头是否要左移 右移还是保持不动 L 代表左移 R 代表右移 S 代表保持不动 该双带Turing机的执行情况 在初始状态q0 带2最左边格子中应为空白 b 如带1当前是0或1 则带1头不动 带2最左边格子打上 X 后右移一格 进入q1状态准备复写 若如带1当前是空白 b 则进入q5状态接受 若如带1当前是其它符号 则停机 不接受 该双带Turing机的执行 2 在q1状态 主要是执行将带1内容复写到带2上的操作 如带1当前是0或1 则将其复写到带2上 带1 带2头右移一格 仍停留在q1状态 不断执行复写 如带1当前是空白 b 输入串读完 则带1头不动 带2头左移一格 进入q2状态 在q2状态 主要是执行将带2头不断左移的操作 直到最左边格子 如带2当前是0或1而不是 X 则不断左移带2的读写头 带1头保持不动 直到带2上出现 X 为止 此时带1头左移一格 带2头右移一格 进入q3状态准备比较 该双带Turing机的执行 3 在q3状态 执行比较 若带1 带2当前字符 0或1 相同 则带2头右移一格进入q4状态 带1 带2头不同时移动是为了防止带1头从最左端脱落 若带1 带2当前字符不同 则停机 不接受 在q4状态 只要带2当前字符不是空白 b 串尚未比较完 则带1头左移一格 回到q3状态准备下一次比较 若带2当前字符是空白 b 说明比较结束 输入串的确是回文 进入q5状态接受 语言接受器 函数计算装置 Turing机可以从两个不同的角度来看 本质是一样的 既可以作为语言接受器 也可以作为计算某个函数f x1 x2 xn 的装置 Turing机T0接受的符号串 从T0第一条带最左端的格子开始放输入串的符号 每格一个符号 且k个读写头都处于最左端 若从指定的初始状态q0起 T0作一系列动作后进入接受状态qf 则称该输入符号串被T0所接受 Turing机T0接受的语言 由所有被T0接受的符号串所组成的集合 Turing机T0可计算函数f的定义 设T0开始工作前k个读写头都处于最左端 f是某个n元函数 定义域为D 若对任一 1 2 n D i是具体的数 将字符串 1 2 n b作为T0的输入后 也可以不用 而用其它分隔符 从指定的初始状态q0起 T0作一系列动作后进入最终状态qf 且此时指定输出带从最左端起到空白为止的值恰好等于f 1 2 n 则称T0可计算f Turing机与确定性有穷自动机 Turing机作为语言接受器与确定性有穷自动机的区别 DFA可视为双带单向Turing机的特例 与一般的Turing机的区别在于它的读写头 只能右移 不能左移或停止不动 即不能来回移动和进行擦写 Turing机的计算能力比DFA强的原因就在于Turing机有来回扫描和改写的能力 但是可以证明 只允许来回扫描而不允许改写 或只允许改写而不允许来回扫描 只能单向移动 的Turing机 其能够计算的对象的范围与DFA能够计算的对象的范围相同 Turing机执行情况的瞬时描述 InstaneousDescriptions ID k带Turing机的ID用来描述执行过程中的每一个执行情况 格局 它是一个k元组 1 2 k 其中每个 i形为xqy q表示当前状态 第i条带上的内容为xy y后面的空白部分省略 第i个带头当前正注视着y最左边的一个字符 y为空串时 表示带头i当前注视的是空白 b e g D 01110q2 q2 01110 是42页图第2行最右方所示情况的瞬时描述 初始时的瞬时描述D1为 q0a1a2 an q0 q0 q0 k 1条带为空 然后根据转移函数表 可得D2 D3 Dm 记为 D1 D2 Dm 若初始或最后的ID中的q为qf 则称TM接受字符串a1a2 an Turing机的ID序列与描述Turing机的状态图序列是等价的 三 算法基本概念与NP完全性理论简介 什么是算法 目前尚无标准定义 大多数人使用Knuth的描述 算法是由若干条指令组成的有穷序列 具有下列五个特性 确定性 每条指令都是明确的 无二义的 反例 将3或4与x相加 能行性 每条指令都必须是能够执行的 反例 计算1 0 计算 的精确值 输入 允许有0个或多个输入量 取自特定的集合 输出 产生一个或多个输出 它 们 与输入量之间存在着某种特定的关系 有穷性 每一条指令执行的次数都是有穷的 即不会永远执行下去 什么是算法 有穷指令序列若满足Knuth提出的上述5条 则通常称之为算法 只满足前4条而不满足第5条的有穷指令序列通常称之为计算过程 只要不停电 机器不坏 计算过程就可以永远执行下去 死循环 但这种可以永远执行的计算过程并不是毫无用处 e g OS就是计算过程 算法研究的几个主要步骤 设计 要根据不同的处理对象设计出高质量的算法 这是算法研究的基础 表示 如何能使得算法的表示简明扼要 写出的算法要保证能在计算机上实现 确认 对所有合法的输入 所给算法都要能得到正确的结果 对所有不合法的输入 算法都要能够正确应对 分析 预计算法能在什么样的环境中有效地运行 在最坏 最好和平均情况下具有什么样的时间复杂度 还需要比较解决同一问题的不同算法各自的优缺点 实现和测试 将所给的算法编程实现 通过各种测试来检查所给算法是否是正确的 软件及程序的测试是一个很值得探索的研究领域 评价算法的五个主要方面 正确性 评价算法的首要因素 由于不正确的算法不但无益 而且有害 所以评价算法时首先要看该算法是否正确 最好是用理论的 即数学证明的方法 程序正确性证明 方法的关键是要找出恰当的命题来表达所研究的算法 程序内容 但目前程序正确性证明的能力还很有限 到现在还没有通用的 简捷方便的证明方法 当无法用数学方法进行程序正确性证明时 则只能通过测试去检查程序的正确性 评价算法的五个主要方面 通过测试去检查程序的正确性 一般是把程序分为相互独立的部分 确认各个部分的程序确实完成了我们所期待的任务 必要时须采用逐条验证的方法 但测试一般做不到穷尽所有的可能输入 而在实际中恰恰是测试时未想到的点上出问题 E g 美国的几次导弹发射失败均是因为程序上的原因 而不是机械 物理上的原因 健壮性 算法 程序不仅对正确的输入要能计算出正确的结果 对不正确的输入也要能够应对处理 非正确输入在应用中是免不了的 评价算法的五个主要方面 简单性 算法 程序的可读性好 易调试 改进 高效性 时间 空间复杂度较小 特别是时间复杂度 具体表现就是运行速度快 占用内存少 简单性与高效性之间有时会发生冲突 要根据不同的研究对象作出权衡 一般来说 研究算法的人注重高效性 而做产品的人注重简单性 最优性 证明自己所给算法是解决同一类问题中最好的 要做到这一点 就需要找出解决某类问题的算法的时间复杂度下界 即解决该类问题的任何一个算法至少需要的时间复杂度 算法效率的衡量尺度 最初人们用计算所需要的时间来衡量一个算法的效率 但不同的机器相互之间无法比较 故需要用独立于具体计算机的客观衡量标准 问题的规模 基本运算 算法的计算量函数 问题的规模 大小 size 一个或多个整数 作为输入数据量的测度 E g a 数表的长度 数据项的个数 问题 在一个数据表中寻找X b 矩阵的最大维数 阶数 问题 求两个实矩阵相乘的结果 输入规模通常用n来表示 也可有两个以上的参数 如c 图中的顶点数和边数 图论中的问题 基本运算 解决给定问题时占支配地位的运算 一般一种 偶尔 2种 e g a 在一个表中寻找数据元素x x与表中的一个项进行比较b 两个实矩阵的乘法 实数的乘法 及加法 C AB则有cij aikbkjc 将一个数表进行排序 表中的两个数据项进行比较通常情况下 讨论一个算法优劣时 我们只讨论基本运算的执行次数 因为它是占支配地位的 而其它的运算可以忽略不计 用输入规模的某个函数来表示算法的基本运算量 这个表示基本运算量的函数称为算法的时间复杂性 度 用T n 或T n m 等 来表示 渐近时间复杂性 复杂度 当输入规模趋于极限情形时 相当大 的时间复杂性 复杂度表示渐进时间复杂性 复杂度的三个记号T n O f n 若存在c 0 和正整数n0 1 使得当n n0时 总有T n c f n 给出了算法时间复杂度的上界 不可能比c f n 更大 e g T n 3n3 2n2 取c 5 n0 1 f n n3 则当n n0 1 时 有3n3 2n2 5n3 T n O n3 T n f n 若存在c 0 和正整数n0 1 使得当n n0时 存在无穷多个n 使得T n c f n 成立 给出了算法时间复杂度的下界 复杂度不可能比c f n 更小 e g T n 3n3 2n2 取c 3 n0 1 f n n3 则当n n0 1 时 有3n3 2n2 3n3 T n n3 渐近时间复杂性 复杂度 T n f n 若存在c1 c2 0 和正整数n0 1 使得当n n0时 总有T n c1 f n 且有无穷多个n 使得T n c2 f n 成立 即 T n O f n 与T n f n 都成立 既给出了算法时间复杂度的上界 也给出了下界 e g T n 3n3 2n2 c1 5 取c2 3 n0 1 f n n3 则当n n0 1 时 有3n3 2n2 5n3及3n3 2n2 3n3 无穷多个 T n n3 多项式时间与指数时间 渐进 时间复杂度主要有多项式时间和指数时间两种 E g T n 5n T n 3nlogn T n 4n3 T n 2n T n m 2 n m 等多项式时间的算法与指数时间的算法有着本质的不同 E g 设某台计算机每秒可做109次基本运算 n 60算法1算法2算法3算法4算法5算法6nn2n3n52n3n 复杂度 6 10 7s3 6 10 5s2 16 10 3s0 13min 3 66世纪1 3 1014世纪 运算时间 两个结论 1 多项式时间的算法互相之间虽有差距 一般可以接受 2 指数量级时间的算法对于较大的n没有实用价值 最坏与平均情况时间复杂度 最坏情况时间复杂度 规模为n的所有实例中 基本运算执行次数最多的实例所对应的时间复杂度 e g 在一个顺序表中寻找数据元素x顺序查找 最坏情况为O n 二分查找 最坏情况为O logn 平均情况时间复杂度 规模为n的所有实例的时间复杂度的平均值 一般均假设所有实例以等概率出现 e g 在一个顺序表中寻找数据元素x顺序查找 平均情况仍为O n 二分查找 平均情况仍为O logn 目前尚无多项式时间算法的问题 可以分为三种类型 1 绝不可能有多项式时间算法 如河内塔问题 已经证明至少需要搬动2n 1次 2 可能有多项式时间算法 但由于研究得不够彻底 目前尚未找到 如线性规划问题 最简单的算法是单纯形法 但单纯形法被证明最坏时间复杂度是指数 有段时期人们一直以为线性规划没有多项式时间算法 但俄罗斯卡其扬教授与印度卡玛卡教授先后发现了求解线性规划的多项式时间算法 卡其扬 椭球法 卡玛卡 内点法 前者早 后者效率高 3 很可能没有多项式时间算法 如发现 包括证明某个问题不存在多项式时间算法 则将举世震惊 发现者必得图灵奖 e g 1等分割问题 Partitioning 若集合 i1 i2 in 中的ij均为正整数 n 2 这些ij允许相同 问是否存在一种分划 将诸ij分成两部分 使得两部分数的和相等 例 2 3 4 6 7 1 1 1 4 e g 2Hamilton回路问题 HC 任给一个无向图G 问是否存在一条回路 它经过G中的每个点一次且仅一次 H回路 e g 3可满足性问题 SAT 任给一个含n个命题变元s1 s2 sn的合取范式F 问是否存在一组真值指派 令s1 1 s2 2 sn n i或为0或为1 使得F的值为1 True e g s1 s2 3 4 1 s2 s1 2 s3 是一个合取范式 e g 4团集问题 CLIQUE 任给一个无向图G 问G中是否有k 团 k个顶点的团集 团集 点的集合 满足 任两点之间均有边相连 以上4个问题均是判定问题 目前尚无多项式时间算法的问题 设S是一个集合 若某个判定问题A的所有解均属于S 则S中的一个元素称为问题A的一个证书 certificate S被称为是A的证书所构成的集合 e g 1SAT问题 给定一个n元的布尔表达式f x1 x2 xn 则n元组 1 2 n i或为0或为1 已确定 为该问题的一个证书 从 0 0 0 到 1 1 1 共2n个证书故 S 2n 若f x1 x2 xn 可满足 则使f x1 x2 xn 为1的n元组含在其中 e g 2k 团问题 给定无向图G V E 顶点集V的任何一个k顶点子集V 就是k 团问题的一个证书 每个V 作为一个元素构成S 这样的子集共有