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

东北师范大学计算机学院 形式语言与自动机第一讲 从DFA到TM 从正则语言到自然语言 殷明浩ymh 东北师范大学计算机学院 课程介绍 授课类型Seminar Lecture授课时间 本学期 PerWeds15 30 18 00 考核方式笔试 平时成绩授课语言基本中文 东北师范大学计算机学院 Outlineforthiscourse 东北师范大学计算机学院 Outlinetoday 计算的意义 算法 与 好的算法 NP完全性如何处理NP完全问题新的计算模型与希望 东北师范大学计算机学院 什么是可以计算的 什么是不可以计算的 算法的意义 东北师范大学计算机学院 例1 可满足性 Satisfiability 问题 布尔变量集合布尔变量和称为文字子句集合子句是一些文字的析取 逻辑或 真值赋值给定U和C 是否存在满足C的真值赋值 可满足 C中所有的子句在t下为真计算复杂度 东北师范大学计算机学院 例2 货郎担问题 Travelingsalesmanproblem 给定n个城市 任意两个城市间有路相连 一个货郎从一个城市出发 不重复的遍历所有的城市并回到起点 求一条路程最短的路径 加权完全图 求Hamilton圈 使得计算复杂度 东北师范大学计算机学院 指数灾难 计算量的指数增长 东北师范大学计算机学院 指数灾难能否避免 SAT问题 货郎担问题 背包问题 图着色问题 最长路径问题 是否对于每个问题都有好的算法 什么是好的算法 什么是算法 东北师范大学计算机学院 算法的定义 为实现某个任务而构成的简单指令集有穷的计算良过程通过有限多次运算可以决定的过程 正确 直观 非形式 东北师范大学计算机学院 算法的定义 希尔伯特第十问题 1900 设计一个算法来判断多项式是否有整数根算法 通过有限多次运算可以决定的过程AlanTuring AlonzoChurch 1936 图灵机程序算法 图灵机程序形式化的 精确的 东北师范大学计算机学院 图灵机 TuringMachine 带子可读可写无限长的带子读写头可左移右移 东北师范大学计算机学院 东北师范大学计算机学院 图灵机 TuringMachine TM运行由确定 当前状态为q 所读字符为s 读写头不变 读写头左移一格 s不变 读写头右移一格 s不变 无定义 则停机Church Turing论题 凡是可计算的过程都可用图灵机实现 东北师范大学计算机学院 其他图灵机模型 实际的 的图灵机模型单带图灵机 1TM 多带图灵机 kTM 随机存取机 RAM 实际的 单位时间内完成的工作量有一个多项式上界所有 实际的 计算模型多项式时间等价 东北师范大学计算机学院 好的算法 多项式时间算法 算法的时间复杂度指数时间多项式时间为什么是多项式而不是其他函数 常见的组合算法大致可分以上两类与计算模型无关性 东北师范大学计算机学院 什么是算法 什么是好的算法 是否对于每个问题都有好的算法 东北师范大学计算机学院 P类 Polynomial 判定问题 只有肯定和否定两种答案优化问题可以化作判定问题处理P类具有多项式时间算法的判定问题形成的计算复杂性类猜测TSP Travelingsalesmanproblem 不属于P J Edmonds1965 东北师范大学计算机学院 非确定型算法 不现实的计算现实中的计算方式都是确定的解SAT问题的一个非确定型算法第一步 猜测一个变量的真值赋值 第二步 检查该赋值是否满足非确定型算法的计算时间 各种可能的计算过程的最短时间 东北师范大学计算机学院 非确定型图灵机 NTM 猜想阶段验证阶段 猜想模块 东北师范大学计算机学院 NTM计算树 计算过程 从根到叶节点的路径 东北师范大学计算机学院 东北师范大学计算机学院 NP类 NondeterministicPolynomial NP问题 在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当 东北师范大学计算机学院 计算难度比较的标准 难易是比较而言的多项式时间归约 Karp归约1972 定义问题A多项式时间内转化为问题B的特殊情况 则称A可多项式归约于B 记为转化时间为多项式对于A的输入I的回答与其对应的B的输入f I 一致 东北师范大学计算机学院 NP完全与NP hard NP完全问题 NP hard问题 东北师范大学计算机学院 NP完全问题 第一个NP完全问题 Cook定理1971 可满足性问题是NP完全问题六个NP完全问题 Karp1972 3SAT 3DM VC 团 HC 划分更多的NP完全问题1979年 300多个1998年 2000多个 东北师范大学计算机学院 现在的估计 如果 则指数灾难无法避免 P NP P NP问题 P NP 东北师范大学计算机学院 如何处理NP完全问题 实际的问题不会消失 油井勘探问题移动通讯中的频率分配问题 东北师范大学计算机学院 并行计算 以硬件设备换取时间存在着很多种并行计算模型理想模型PRAM可多项式时间解NP完全问题实际中效果不好处理器数目是受限的现实的代价 通讯 同步 分布式计算 东北师范大学计算机学院 算法的研究 随机算法判定问题 以较大概率得到正确输出输出正确 但计算时间不定优化问题 输出解的性能不稳定以较大概率得到性能好的解 东北师范大学计算机学院 算法的研究 完全算法利用某些策略减少计算量分支界限法 BranchandBound 最坏情况时间复杂度是指数的近似算法不要最优 只求较优时间复杂度较低 东北师范大学计算机学院 算法的研究 近似算法局部搜索遗传算法模拟退火 东北师范大学计算机学院 TSP问题实验结果 实验环境 PII450双CPU 256M内存 TurboLinux4 0 东北师范大学计算机学院 新的计算模型 生物计算DNA计算机量子计算量子计算机 东北师范大学计算机学院 DNA计算 实验处理了7城市Hamilton路径问题L Adleman1994可以多项式时间解所有的NP问题LiptonRJ1995实验可以建立一个非确定型图灵机SmithW SchweitzerA 1995 东北师范大学计算机学院 DNA计算的困难 操作的复杂性单元操作的时间代价高规模的限制处理的问题规模较小输入输出纠错的问题 东北师范大学计算机学院 量子计算 量子计算思想的提出RichardFeynman1982量子图灵机模型DavidDeutsch1985Shor算法 PeterShor1994 多项式时间分解大数质因子Grover算法 GroverL K 1996 无序数据库的搜索 东北师范大学计算机学院 量子计算的困难 操作的复杂性单元操作的时间代价高规模的限制测量输