算法导论课件第16讲NP完全性
64页1、NP-Completeness,2,NP-Completeness,- Computability - Analysis of Algorithms - NP-Completeness,3,Analysis of Algorithm,For many problems, there may be several competitive algorithms. Which one should I use?,Analysis of algorithms. framework for comparing algorithms and prediction performance. case study: sorting,Computational complexity. framework for studying intrinsic difficulty of problems.,4,图灵机,1936年图灵提出了一个抽象计算模型 图灵机,并用它来精确定义可计算函数。图灵机的基本思想是模拟人用纸笔进行数学运算的过程,这个运算过程可分解为下面两种简单的动作: 1.在纸上写或擦除某个符号; 2
2、.把注意力从纸的一个位置移动到另一个位置。 在每个阶段将由执行运算的人决定下一步的动作,而他的决定依赖于此人当前所关注的是纸上哪个位置的符号,以及此人当前思维的状态。,5,Turing Machine,6,Deterministic Turing Machine,定义 一台图灵机由一个八元组所组成 TM = ( Q, T, I, , b, q0, qaccept , qreject ) 其中 Q:一个有限状态集; T:一个有限符号集(字母表); I:输入字符集,I T; b:空符,bTI; :QT 的子集Q(TL, R, S),即转移函数或有限状态控制函数,其中L, R表示读写头左移或右移,S表示读写头原地不动; q0:表示初始状态; qaccepr:表示终止(接受)状态; qreject:表示拒绝状态。 这里规定是单值映射,所以也称为确定型图灵机。,7,一个例子,例:设TM =(0,1,10,11,0,1,“ ”(空格), 0,1, 0),做一个以1的个数表示数值的整数加法运算,在磁带上的数据设为0000001110110000,就是3+2的意思。转移函数定义如下: 0,0 0,0R
3、 0,1 1,1R 1,0 10,1R 1,1 1,1R 10,0 11,0L 10,1 10,1R 11,0 E 11,1 0,0S 在 xx,y aa,bb 中,xx是当前状态,y是当前格子的值,aa是程序下一步的状态,b是当前格的修改值。例如第一行指令 0,0 0,0R,意思就是如果机器读到格子的值是0,就将其仍变成0,状态变为0,读写头向右移动一格。最后两行中的E代表错误,S代表停机。,8,图灵机的格局序列(粗体的字符表示读写头的当前位置),9,其他类型的图灵机,双向无限带图灵机。其带子向左向右都是无限长的,与确定型图灵机基本模型不同的是,它的带子没有左端、带头永远不会走出两端。 多带多头图灵机。它具有一个有穷控制器,k个带头和k条带子,每条带子都是双向无穷的,并且各带头在操作时相互独立,除改写带符、左右移动外,还可以保持不动。 非确定型图灵机。这种类型的图灵机具有一个有限控制器和一条单向无限带,对于一个给定的状态,机器的下一动作可以有穷多个选择,每个选择包括一个新状态,一个要打印的带符号和一个带头移动方向。,10,非确定型图灵机,定义: 一个非确定型图灵机(NDTM)由下述八
4、元组给出: NDTM = (Q,T,I,b,q0,qaccept,qreject) 其中Q, T, I, b, q0 和qr 的定义与确定型图灵机的相同,唯一的区别在于状态控制函数(转移函数)。 非确定型图灵机的状态控制函数 给出的下一个动作不是唯一确定的,即为多值映射,它的值域是一个有穷集合A。因此非确定型图灵机在下一时刻的动作可以有多种选择。在处理问题时,对于(q1, al, , ak)的多个值,非确定型图灵机对于其中任意一个值都存在一个格局序列可以推导下去,只要其中有一种可以到达终止状态qaccept ,就说该问题是可以处理的(输入字符串被接受或函数是可计算的)。,11,Overview of showing problems to be NP-complete,在证明一个问题为NP完全问题时,要依赖于三个关键概念: - 判定问题与最优化问题 - 归约 - 第一个完全问题,12,Decision problems vs. optimization problems,Many problems of interest are optimization problems, in wh
《算法导论课件第16讲NP完全性》由会员E****分享,可在线阅读,更多相关《算法导论课件第16讲NP完全性》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页