




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第9章 计算复杂性与NP理论9.1 多项式规约9.2 计算模型9.3 P和NP类问题9.4 NP完全问题2021/8/171第9章 计算复杂性与NP理论9.1 多项式规约2021/89.1 多项式规约规约:如果存在两个问题Q和Q,对于Q的任何一个实例q,都能找到Q的一个实例q,并能够将q的解a转换为q的解a,则称问题Q可以被归约到问题QQQqqaa2021/8/1729.1 多项式规约规约:如果存在两个问题Q和Q,对于Q的任9.1 多项式规约规约:如果存在两个问题Q和Q,对于Q的任何一个实例q,都能找到Q的一个实例q,并能够将q的解a转换为q的解a,则称问题Q可以被归约到问题Q多项式规约:可在
2、多项式时间内完成的规约QQqqaa2021/8/1739.1 多项式规约规约:如果存在两个问题Q和Q,对于Q的任9.1 多项式规约问题示例ax2 + bx + c = 0ax3 + bx2 + cx + d = 02021/8/1749.1 多项式规约问题示例ax2 + bx + c = 0a9.1 多项式规约问题示例G=最大独立集G=最小顶点覆盖V/C是G的最大独立集C是G的最小顶点覆盖2021/8/1759.1 多项式规约问题示例G=G=V/C9.2 计算模型形式语言与问题编码形式语言: 字母表 是符号的有限集合,上的语言L是由中的符号所组成的串的任意集合 = 0,1L1 = 0, 1,
3、10, 11, 100, 101, 110, 111, 1000, 1001L2 = 0, 10, 100, 110, 1000, 1010, 2021/8/1769.2 计算模型形式语言与问题编码 = 0,1L1 =9.2 计算模型形式语言与问题编码形式语言: 字母表 是符号的有限集合,上的语言L是由中的符号所组成的串的任意集合问题编码:问题Q的任意一个输入都会被编码为一个二进制串s。设问题的输入集合为I,其编码就是一个映射e: I 0,1*2021/8/1779.2 计算模型形式语言与问题编码2021/8/1779.2 计算模型形式语言与问题编码形式语言: 字母表 是符号的有限集合,上的语
4、言L是由中的符号所组成的串的任意集合问题编码:问题Q的任意一个输入都会被编码为一个二进制串s。设问题的输入集合为I,其编码就是一个映射e: I 0,1*问题算法:设A是问题Q的一个算法,那么A应当接受输入s,算法运行得到的结果记为A(s)。当Q是一个判定形式的问题,则对于任意输入A(s) yes, no2021/8/1789.2 计算模型形式语言与问题编码2021/8/1789.2 计算模型图灵机在当前方格中写入新字符读写头左移(L)、右移(R)或不动(S)改变状态控制器中的当前状态2021/8/1799.2 计算模型图灵机2021/8/1799.2 计算模型图灵机形式定义:一个七元组M =
5、(Q, , , b, , q0, F),其中Q是有限状态集,是字母表,是读写带上的字符集,b是空白字符(b但b),: Q QL,R,S是动作转移函数,q0Q是初始状态,FQ是终止状态集。2021/8/17109.2 计算模型图灵机2021/8/17109.2 计算模型图灵机M = (Q, , , b, , q0, F)将输入符号串s = a0a1an 依此填在纸带的第0,1, n号格子上,读写头指向第0号格子,机器处于状态q0当前状态qiF则停机把扫描到的符号xi传送到状态控制器,控制器再根据当前状态qi计算动作转移函数,并根据函数值决定下一步的操作2021/8/17119.2 计算模型图灵机
6、M = (Q, , , b, ,9.2 计算模型图灵机M = (Q, , , b, , q0, F)终止状态qa表示接受输入字符串,qr表示拒绝动作转移函数允许是一个部分函数,当(qi, xi)上无定义时也将停机2021/8/17129.2 计算模型图灵机M = (Q, , , b, ,9.2 计算模型图灵机M = (Q, , , b, , q0, F)问题:判断一个二进制串中有奇数个还是偶数个1qixiqi+1xi+1动作False0FalsebRTrue0TruebRFalse1TruebRTrue1FalsebRFalsebqr0STruebqa1S2021/8/17139.2 计算模型
7、图灵机M = (Q, , , b, ,9.2 计算模型图灵机M = (Q, , , b, , q0, F)k带图灵机: Qk Q(L,R,S)k2021/8/17149.2 计算模型图灵机M = (Q, , , b, ,9.2 计算模型图灵机M = (Q, , , b, , q0, F)k带图灵机不确定图灵机2021/8/17159.2 计算模型图灵机M = (Q, , , b, ,9.2 计算模型图灵机与可计算性设f是一个函数,如果能通过一个图灵机M来完成f的计算,则称f是部分可计算的;如果M能够完成f的计算,且对于f定义域上的任意一个输入s,M都能保证停机,则称f是可计算的,或者说f是一个
8、可计算函数。设L是一个语言,如果它能够被一个图灵机M接受,则称L是一个递归可枚举语言;如果M能够接受L,且对于输入sL,M都能保证停机,则称L是一个递归语言。2021/8/17169.2 计算模型图灵机与可计算性2021/8/17169.2 计算模型图灵机与可计算性称语言L1可被多项式时间归约到语言L2,如果存在一个多项式时间可计算的函数f: 0,1* 0,1*,其对任意的x 0,1*都有:x L1当且仅当x L22021/8/17179.2 计算模型图灵机与可计算性2021/8/17179.2 计算模型一个算法就是一个确定的、对任意合法输入都停机的图灵机对于每个长度为n的输入,如果图灵机M在
9、计算过程中的读写头移动次数不超过T(n),则称M是以T(n)为时间上界(简称时间界)的图灵机给定一个问题Q,如果存在一个时间界为T(n)的图灵机对其进行计算,则称Q的时间复杂度为T(n)2021/8/17189.2 计算模型一个算法就是一个确定的、对任意合法输入都停机9.3 P和NP类问题P类问题:存在多项式时间算法的计算问题能够用确定性图灵机在多项式时间界内求解的问题称为P类问题P = L 0,1*| 存在一个确定性图灵机M能够在多项式时间内接受LP2021/8/17199.3 P和NP类问题P类问题:存在多项式时间算法的计算问题NP9.3 P和NP类问题NP类问题能够用不确定性图灵机在多项式时间界内求解的问题称为NP类问题NP = L 0,1*| 存在一个不
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 球场租赁协议书范本
- 授权合作销售协议书
- 智慧乡村开发协议书
- 特价商品协议书模板
- 戒酒协议书手写模板
- 消防管道合并协议书
- 集训学校安全协议书
- 食堂承包协议书封面
- 师徒结对协议书课题
- 诊所护士就业协议书
- 温州市十校联合体2022-2023学年高二下学期期中联考化学试题含答案
- 企业员工爱岗敬业培训课件
- 数字美的智慧工业白皮书-2023.09
- 行政管理学教案
- 南京郑和外国语学校小升初数学期末试卷测试卷(含答案解析)
- 古扎拉蒂《计量经济学基础》(第5版)笔记和课后习题详解
- 2023年-2024年电子物证专业考试复习题库(含答案)
- 小学语文跨学科学习任务群学习任务设计策略
- 新人教版七年级下册语文现代文阅读理解及答案
- Matlab在信息光学中的应用课件
- 人教版小学语文1-6年级古诗词目录-按年级
评论
0/150
提交评论