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

1、方式言语与自动机第一讲从DFA到TM,从正那么言语到自然言语殷明浩/auto.htm 课程引见授课类型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 完全问题新的计算模型与希望 什么是可以计算的? 什么是不可以 计算的?算法的意义算法的意义例1：可满足性Satisfiability问题 布尔变量集合 布尔变量 和 称为文字 子句集合 子句 是一些文字的析取逻辑

3、或 真值赋值 给定U和C，能否存在满足C的真值赋值？ 可满足：C中一切的子句在 t 下为真 计算复杂度：,.,21nuuuU ,.,21mcccC jujuic,:FTUt)2(nO例2：货郎担问题Traveling salesman problem) 给定n个城市，恣意两个城市间有路相连，一个货郎从一个城市出发，不反复的遍历一切的城市并回到起点，求一条路程最短的途径。 加权完全图， ， ，求Hamilton圈，使得 计算复杂度： ),(EVG nV | REW :)(min)()(iCehCWewCWhhC) !(nO指数灾难：计算量的指数增长0 0200200400400600600800

4、80010001000120012001 13 35 57 79 9指数增指数增长长线性增线性增长长指数灾难能否防止？ SAT问题，货郎担问题，背包问题，图着色问题，最长途径问题， 能否对于每个问题都有好的算法？ 什么是好的算法？ 什么是算法？算法的定义 为实现某个义务而构成的简单指令集 有穷的计算良过程 经过有限多次运算可以决议的过程正确直观，非方式算法的定义 希尔伯特第十问题1900 设计一个算法来判别多项式能否有整数根 算法：经过有限多次运算可以决议的过程 Alan Turing & Alonzo Church1936 图灵机程序 算法：图灵机程序 方式化的，准确的演算图灵机Turing

5、 Machine) 带子可读可写 无限长的带子 读写头可左移右移 有限形状控制器111 111000000 0BBB1图灵机Turing Machine) TM运转由 确定:当前形状为q，所读字符为s ，读写头不变， ， ，读写头左移一格，s不变， ，读写头右移一格，s不变， 无定义，那么停机 Church-Turing论题：凡是可计算的过程都可用图灵机实现；),(),(qssq),(),(qLsq),(),(qRsq),(sqssqqqqqq其他图灵机模型 “实践的的图灵机模型 单带图灵机1TM 多带图灵机kTM 随机存取机RAM “实践的 单位时间内完成的任务量有一个多项式上界 一切“实践

6、的计算模型多项式时间等价好的算法多项式时间算法 算法的时间复杂度 指数时间 多项式时间 为什么是多项式而不是其他函数？ 常见的组合算法大致可分以上两类 与计算模型无关性 什么是算法？ 什么是好的算法？ 能否对于每个问题都有好的算法？P类Polynomial) 断定问题：只需一定和否认两种答案 优化问题可以化作断定问题处置 P类 具有多项式时间算法的断定问题构成的计算复杂性类 猜测TSPTraveling salesman problem)不属于PJ.Edmonds 1965非确定型算法 不现实的计算 现实中的计算方式都是确定的 解SAT问题的一个非确定型算法 第一步：猜测一个变量的真值赋值；

7、第二步：检查该赋值能否满足 非确定型算法的计算时间： 各种能够的计算过程的最短时间非确定型图灵机NTM) 猜测阶段 验证阶段 有限形状控制器111 111000000 0BBB1猜测模块NTM计算树计算过程：从根到叶节点的途径NP类(Nondeterministic Polynomial ) NP问题： 在非确定型图灵机上多项式时间可解的问题 在确定型图灵机上多项式时间可验证的问题 P类包含于NP类中 NP类问题在确定图灵机上指数时间可解 非确定型图灵机和确定型图灵机的计算才干相当计算难度比较的规范 难易是比较而言的 多项式时间归约Karp归约 1972) 定义 问题A多项式时间内转化为问题B

8、的特殊情况，那么称A可多项式归约于B，记为 转化时间为多项式 对于A的输入I 的回答与其对应的B的输入 f(I) 一致BApNP完全与NP-hard NP完全问题： NP-hard问题：pqNPqNPpNPCpp有,. 2;. 1:pqNPqhardNPpp有,:NP完全问题 第一个NP完全问题Cook定理 1971 可满足性问题是NP完全问题 六个NP完全问题Karp 1972) 3SAT，3DM，VC，团，HC，划分 更多的NP完全问题 1979年：300多个 2019年：2000多个如今的估计假设 ，那么指数灾难无法防止NPP P=?NP P-NP问题问题P=NPPNPCNP如何处置NP

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

10、验结果实验环境：PII450双CPU，256M内存, Turbo Linux 4.0 optbestn)(mean)(tmeantbestn)(mean)(tmeantInstanceEAX-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.9

11、5)2022249(0)97.4(0.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 2019 实验可以建立一个非确定型图灵机 Smith W, Schweitzer A. 2019DNA计算的困难 操作的复杂性 单元操作的时间代价高 规模的限制 处置的问题规模较小 输入输出 纠错的问题量子计算 量子计算思想的提出 Richard Feynman 1982 量子图灵机模型 David Deutsch 1985 Shor算法Peter Shor 1994 多项式时间分解大数质因子 Grover 算法Grover