形式语言与自动机第一讲.ppt

《形式语言与自动机第一讲.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机第一讲.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言与自动机第一讲 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望课程介绍授课类型Seminar&Lecture授课时间(本学期)Per Weds 15:30-18:00?考核方式 笔试+平时成绩授课语言基本中文东北师范大学计算机学院Outline for this course抽象模型变种对应语言相当于程序或算法备注自动机自动机不确定 NFA正则语言正则语言 3型型If,case,goto,无变量（内存）无数组下推机下推机不确定下推不确定下推机机前后文无关前

2、后文无关语言，语言，2型型增加：堆栈。仍无变量（内存）无数组不确定线性不确定线性界限下推机界限下推机前后文有关前后文有关语言语言1型 语言一定停机的一定停机的图灵机图灵机XXX的图灵的图灵机机 多带多带,随随机，有界机，有界递归语言族增加数组，变量，内存保证了不会死循环图灵机图灵机0型，递归可枚举输入在语言外时，可能死循环，数学模型，简洁，易分析不要程序细节，易于分析本质东北师范大学计算机学院Outline today：计算的意义?“算法”与“好的算法”NP完全性如何处理NP 完全问题新的计算模型与希望东北师范大学计算机学院什么是可以计算的?什么是不可以 计算的?算法的意义算法的意义东北师范大

3、学计算机学院例1：可满足性（Satisfiability）问题布尔变量集合布尔变量 和 称为文字子句集合子句 是一些文字的析取（逻辑或）真值赋值给定U和C，是否存在满足C的真值赋值？可满足：C中所有的子句在 t 下为真计算复杂度：东北师范大学计算机学院例2：货郎担问题（Traveling salesman problem)给定n个城市，任意两个城市间有路相连，一个货郎从一个城市出发，不重复的遍历所有的城市并回到起点，求一条路程最短的路径。加权完全图，求Hamilton圈，使得计算复杂度：东北师范大学计算机学院指数灾难：计算量的指数增长东北师范大学计算机学院指数灾难能否避免？SAT问题，货郎担问

4、题，背包问题，图着色问题，最长路径问题，是否对于每个问题都有好的算法？什么是好的算法？什么是算法？东北师范大学计算机学院算法的定义为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程正确直观，非形式东北师范大学计算机学院算法的定义希尔伯特第十问题（1900）设计一个算法来判断多项式是否有整数根算法：通过有限多次运算可以决定的过程Alan Turing&Alonzo Church（1936）图灵机程序算法：图灵机程序形式化的，精确的东北师范大学计算机学院图灵机（Turing Machine)带子可读可写无限长的带子读写头可左移右移 有限状态控制器111 11100000

5、0 0BBB1东北师范大学计算机学院东北师范大学计算机学院图灵机（Turing Machine)TM运行由 确定:当前状态为q，所读字符为s ，读写头不变，读写头左移一格，s不变，读写头右移一格，s不变，无定义，则停机Church-Turing论题：凡是可计算的过程都可用图灵机实现；东北师范大学计算机学院其他图灵机模型“实际的”的图灵机模型单带图灵机（1TM）多带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界所有“实际的”计算模型多项式时间等价东北师范大学计算机学院好的算法多项式时间算法算法的时间复杂度指数时间多项式时间为什么是多项式而不是其他函数？常见的

6、组合算法大致可分以上两类与计算模型无关性东北师范大学计算机学院什么是算法？什么是好的算法？是否对于每个问题都有好的算法？东北师范大学计算机学院P类（Polynomial)判定问题：只有肯定和否定两种答案优化问题可以化作判定问题处理P类具有多项式时间算法的判定问题形成的计算复杂性类猜测TSP（Traveling salesman problem)不属于P（J.Edmonds 1965）东北师范大学计算机学院非确定型算法不现实的计算现实中的计算方式都是确定的解SAT问题的一个非确定型算法第一步：猜测一个变量的真值赋值；第二步：检查该赋值是否满足非确定型算法的计算时间：各种可能的计算过程的最短时间东

7、北师范大学计算机学院非确定型图灵机（NTM)猜想阶段验证阶段 有限状态控制器111 111000000 0BBB1猜想模块东北师范大学计算机学院NTM计算树计算过程：从根到叶节点的路径东北师范大学计算机学院东北师范大学计算机学院NP类(Nondeterministic Polynomial)NP问题：在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当东北师范大学计算机学院计算难度比较的标准难易是比较而言的多项式时间归约（Karp归约 1972)定义问题A多项式时间内转化为问

8、题B的特殊情况，则称A可多项式归约于B，记为转化时间为多项式对于A的输入I 的回答与其对应的B的输入 f(I)一致东北师范大学计算机学院NP完全与NP-hardNP完全问题：NP-hard问题：东北师范大学计算机学院NP完全问题第一个NP完全问题（Cook定理 1971）可满足性问题是NP完全问题六个NP完全问题（Karp 1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个东北师范大学计算机学院现在的估计如果 ，则指数灾难无法避免P=?NP（P-NP问题）问题）P=NPPNPCNP东北师范大学计算机学院如何处理NP完全问题 实际的问

9、题不会消失油井勘探问题移动通讯中的频率分配问题东北师范大学计算机学院并行计算以硬件设备换取时间存在着很多种并行计算模型理想模型PRAM可多项式时间解NP完全问题实际中效果不好处理器数目是受限的现实的代价：通讯，同步，分布式计算东北师范大学计算机学院算法的研究随机算法判定问题：以较大概率得到正确输出输出正确，但计算时间不定优化问题：输出解的性能不稳定以较大概率得到性能好的解东北师范大学计算机学院算法的研究完全算法利用某些策略减少计算量分支界限法（Branch and Bound）最坏情况时间复杂度是指数的近似算法不要最优，只求较优时间复杂度较低东北师范大学计算机学院算法的研究近似算法局部搜索遗传

10、算法模拟退火 东北师范大学计算机学院TSP问题实验结果（实验环境：PII450双CPU，256M内存,Turbo Linux 4.0）InstanceEAX-h+ILKPattern1名称Pcb442507782050778(0)57.0(0.005)2050778(0)13.11(0.10)Att532276862027686(0)36.14(0.01)2027686(0)51.52(0.026)Rat7838806208806(0)26.66(0.01)208806(0)46.32(0.019)Fl1577222492022249(0)589.1(0.95)2022249(0)97.4(0

11、.035)Pr23923780320378161(0)624.6(0.94)0378224(0)642.0(1.65)Fl379528772028783(0)1488.2(5.2)028788(0)1103.4(14.3)东北师范大学计算机学院新的计算模型生物计算DNA计算机量子计算量子计算机东北师范大学计算机学院DNA计算实验处理了7城市Hamilton路径问题 L.Adleman 1994 可以多项式时间解所有的NP问题Lipton R J 1995实验可以建立一个非确定型图灵机Smith W,Schweitzer A.1995东北师范大学计算机学院DNA计算的困难操作的复杂性单元操作的时

12、间代价高规模的限制处理的问题规模较小输入输出纠错的问题东北师范大学计算机学院量子计算量子计算思想的提出Richard Feynman 1982量子图灵机模型David Deutsch 1985Shor算法（Peter Shor 1994）多项式时间分解大数质因子Grover 算法（Grover L.K.1996）无序数据库的搜索：东北师范大学计算机学院量子计算的困难操作的复杂性单元操作的时间代价高规模的限制测量输出纠错的问题东北师范大学计算机学院行之有效的方法：算法研究东北师范大学计算机学院推荐阅读计算机和难解性：NP完全性理论导引（Michael R.Garey&David S.Johnson 1979)可计算性与计算复杂性导引 (张立昂）计算理论导引计算理论基础东北师范大学计算机学院谢谢大家！东北师范大学计算机学院