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

算法的研究东北师范大学计算机学院利用某些策略减少计算量完全算法1不要最优，只求较优时间复杂度较低近似算法3分支界限法（BranchandBound）最坏情况时间复杂度是指数的2东北师范大学计算机学院形式语言与自动机第一讲——从DFA到TM,从正则语言到自然语言殷明浩ymh课程介绍东北师范大学计算机学院SeminarLecture授课类型PerWeds15:30-18:00?授课时间(本学期)笔试+平时成绩考核方式基本中文授课语言04030201东北师范大学计算机学院Outlineforthiscourse抽象模型变种对应语言相当于程序或算法备注自动机不确定NFA正则语言3型If,case,goto,无变量（内存）无数组下推机不确定下推机前后文无关语言，2型增加：堆栈。仍无变量（内存）无数组不确定线性界限下推机前后文有关语言1型语言一定停机的图灵机XXX的图灵机多带,随机，有界递归语言族增加数组，变量，内存保证了不会死循环图灵机0型，递归可枚举输入在语言外时，可能死循环，数学模型，简洁，易分析不要程序细节，易于分析本质Outlinetoday：东北师范大学计算机学院0102030405NP完全性“算法”与“好的算法”如何处理NP完全问题计算的意义?新的计算模型与希望算法的意义东北师范大学计算机学院01什么是可以计算的?02什么是不可以计算的?例1：可满足性（Satisfiability）问题布尔变量集合布尔变量和称为文字子句集合子句是一些文字的析取（逻辑或）123654计算复杂度：给定U和C，是否存在满足C的真值赋值？可满足：C中所有的子句在t下为真真值赋值例2：货郎担问题

（Travelingsalesmanproblem)给定n个城市，任意两个城市间有路相连，一个货郎从一个城市出发，不重复的遍历所有的城市并回到起点，求一条路程最短的路径。加权完全图，，，求Hamilton圈，使得计算复杂度：指数灾难：计算量的指数增长东北师范大学计算机学院指数灾难能否避免？01SAT问题，货郎担问题，背包问题，图着色问题，最长路径问题，……是否对于每个问题都有好的算法？什么是好的算法？什么是算法？02算法的定义东北师范大学计算机学院正确直观，非形式为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程算法的定义东北师范大学计算机学院希尔伯特第十问题（1900）设计一个算法来判断多项式是否有整数根算法：通过有限多次运算可以决定的过程AlanTuringAlonzoChurch（1936）图灵机程序算法：图灵机程序形式化的，精确的图灵机（TuringMachine)带子可读可写无限长的带子读写头可左移右移有限状态控制器1111110000000BBB1…………东北师范大学计算机学院图灵机（TuringMachine)TM运行由确定:当前状态为q，所读字符为s，读写头不变，，，读写头左移一格，s不变，，读写头右移一格，s不变，无定义，则停机Church-Turing论题：凡是可计算的过程都可用图灵机实现；其他图灵机模型东北师范大学计算机学院“实际的”的图灵机模型单带图灵机（1TM）多带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界所有“实际的”计算模型多项式时间等价好的算法——多项式时间算法东北师范大学计算机学院指数时间多项式时间算法的时间复杂度01常见的组合算法大致可分以上两类与计算模型无关性为什么是多项式而不是其他函数？02213什么是算法？什么是好的算法？是否对于每个问题都有好的算法？P类 （Polynomial) 东北师范大学计算机学院02判定问题：只有肯定和否定两种答案优化问题可以化作判定问题处理P类具有多项式时间算法的判定问题形成的计算复杂性类猜测TSP（Travelingsalesmanproblem)不属于P（J.Edmonds1965）01非确定型算法东北师范大学计算机学院现实中的计算方式都是确定的01不现实的计算03各种可能的计算过程的最短时间非确定型算法的计算时间：02猜测一个变量的真值赋值