已阅读5页,还剩36页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
东北师范大学计算机学院 形式语言与自动机第一讲 从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 无序数据库的搜索 东北师范大学计算机学院 量子计算的困难 操作的复杂性单元操作的时间代价高规模的限制测量输
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 超剂量用药规范2026
- 2026中煤绿能科技(北京)有限公司所属企业招聘13人笔试备考题库与答案解析
- 2026新疆昌吉州呼图壁县五工台镇农业发展服务中心招聘安置公益性岗位人员1人笔试备考题库与答案解析
- 2026年重庆医科大学附属大足医院招聘编外人员笔试备考题库与答案解析
- 2026年杭州医学院第二批公开招聘工作人员10人考试参考试题及答案解析
- 2026新疆新星人才发展有限公司面向社会招聘会计1人笔试备考题库与答案解析
- 2026江苏扬州市邗江区招聘社区工作者8人考试参考题库及答案解析
- 海晏县寄宿制民族中学2026年秋季学期临时聘用教师招聘笔试备考题库与答案解析
- 祥云县妇幼保健院2026年就业见习人员招录(10人)笔试备考题库及答案解析
- 2026河北大学化学与材料科学学院招聘管理助理和教学助理笔试备考题库与答案解析
- 云南交投集团招聘笔试真题汇编库2026
- 2025-2026学年姜堰市四下数学期中达标检测模拟试题含答案
- 2026产前筛查诊断人员资质考试历年参考题库含答案详解
- 《城市轨道交通工程浅层气地质勘察规范编制说明》
- 公路工程梁板运输与架设(架桥机、吊车)专项施工方案
- 慢性创伤性骨髓炎清创时机专家共识(2026版)
- 2026年秋季学期新编小学五年级上册道德与法治教案 (全册)
- 2026秋小学新版苏教版数学四年级上册☆ 度量衡的故事《度量衡的发展》教学设计
- 2026年劳动保障协理员考试模拟卷及答案
- 5.1《人口与人种》课件(共30张)人教版地理七年级上册
- GB/T 6104.3-2026工业车辆术语第3部分:附件和部件
评论
0/150
提交评论