形式语言与自动机第一讲精品文稿.ppt

形式语言与自动机第一讲东北师范大学计算机学院第1 页，本讲稿共41 页东北师范大学计算机学院课程介绍 授课类型Seminar&Lecture 授课时间(本学期)Per Weds 15:30-18:00?考核方式 笔试+平时成绩 授课语言基本中文第2 页，本讲稿共41 页东北师范大学计算机学院Outline for this course抽象模型 变种 对应语言 相当于程序或算法 备注自动机不确定 NFA 正则语言 3型If,case,goto,无变量（内存）无数组下推机 不确定下推机前后文无关语言，2型增加：堆栈。仍无变量（内存）无数组不确定线性界限下推机前后文有关语言1型 语言一定停机的图灵机XXX 的图灵机 多带,随机，有界递归语言族 增加数组，变量，内存保证了不会死循环图灵机0型，递归可枚举输入在语言外时，可能死循环，数学模型，简洁，易分析不要程序细节，易于分析本质第3 页，本讲稿共41 页东北师范大学计算机学院Outline today：计算的意义?“算法”与“好的算法”NP 完全性 如何处理NP 完全问题 新的计算模型与希望第4 页，本讲稿共41 页东北师范大学计算机学院 什么是可以计算的?什么是不可以 计算的?算法的意义第5 页，本讲稿共41 页东北师范大学计算机学院例1：可满足性（Satisfiability）问题 布尔变量集合 布尔变量 和 称为文字 子句集合 子句 是一些文字的析取（逻辑或）真值赋值 给定U 和C，是否存在满足C 的真值赋值？可满足：C 中所有的子句在 t 下为真 计算复杂度：第6 页，本讲稿共41 页东北师范大学计算机学院例2：货郎担问题（Traveling salesman problem)给定n 个城市，任意两个城市间有路相连，一个货郎从一个城市出发，不重复的遍历所有的城市并回到起点，求一条路程最短的路径。加权完全图，求Hamilton 圈，使得 计算复杂度：第7 页，本讲稿共41 页东北师范大学计算机学院指数灾难：计算量的指数增长第8 页，本讲稿共41 页东北师范大学计算机学院指数灾难能否避免？SAT 问题，货郎担问题，背包问题，图着色问题，最长路径问题，是否对于每个问题都有好的算法？什么是好的算法？什么是算法？第9 页，本讲稿共41 页东北师范大学计算机学院算法的定义 为实现某个任务而构成的简单指令集 有穷的计算良过程 通过有限多次运算可以决定的过程正确直观，非形式第10 页，本讲稿共41 页东北师范大学计算机学院算法的定义 希尔伯特第十问题（1900）设计一个算法来判断多项式是否有整数根 算法：通过有限多次运算可以决定的过程 Alan Turing&Alonzo Church（1936）图灵机程序 算法：图灵机程序 形式化的，精确的第1 1 页，本讲稿共41 页东北师范大学计算机学院图灵机（Turing Machine)带子可读可写 无限长的带子 读写头可左移右移 有限状态控制器1 1 1 1 1 1 0 0 0 0 0 0 0 B B B 1 第12 页，本讲稿共41 页东北师范大学计算机学院第13 页，本讲稿共41 页东北师范大学计算机学院图灵机（Turing Machine)TM运行由 确定:当前状态为q，所读字符为s，读写头不变，读写头左移一格，s 不变，读写头右移一格，s 不变，无定义，则停机 Church-Turing 论题：凡是可计算的过程都可用图灵机实现；第14 页，本讲稿共41 页东北师范大学计算机学院其他图灵机模型“实际的”的图灵机模型 单带图灵机（1TM）多带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界 所有“实际的”计算模型多项式时间等价第15 页，本讲稿共41 页东北师范大学计算机学院好的算法多项式时间算法 算法的时间复杂度 指数时间 多项式时间 为什么是多项式而不是其他函数？常见的组合算法大致可分以上两类 与计算模型无关性第16 页，本讲稿共41 页东北师范大学计算机学院 什么是算法？什么是好的算法？是否对于每个问题都有好的算法？第17 页，本讲稿共41 页