计算机数学二.pptVIP

一个合理的编码方案要求能合理反映出问题实例的大小,通常要求有简洁性(conciseness) 和可解码性(decodability) 可解码性是指对问题例子的任一特定组成部分或分量，我们总能指定一有效的算法，它可从任何给定的已经被编码的例子中来提取出对那个分量的一个描述. 数学：“一对一”的映射 编码策略的简洁性意味着它满足下列两个条件： (i) 一个实例的编码应是简洁的,而不应该被某些不必要的信息或符号充斥或拉长; (ii) 例子中所出现的数字应统一用二进制、十进制或任何大于1的数为固定基来表示. 如果一个结论对语言L[∏，e]成立，则我们称其在编码e下对判定问题∏也成立。 注：就是讲任一实例的编码属于L[∏，e]，当且仅当该实例是yes的 一旦我们弄清楚了判定问题与语言间的对应关系，我们将交替地使用这两个术语而不加区别。 数理逻辑学家提出了种种机构? 计算模型: 递归函数Godel(1931), Kleene(1936) l演算Church及Kleene Post系统Post(1943) Turing Turing(1936), Post(1936) 只有当一个DTM程序 M对于所有∑*中字符串均停机，我们才称其为一个算法（Algorithm）。 称一个DTM程序 M在编码策略ｅ下解决判定问题∏，如果Ｍ对于∑*中字符串均停机，且ＬＭ＝Ｌ［∏,ｅ] 前述例子对｛０，１｝都停机，因此其为一个算法。　 思考题 1. 设计一个DTM程序，判断一个数是否是偶数？ 2. 设计一个DTM程序，判断一个数是否能被八整除？ 3.设计一个DTM程序，判断一个数是否能被三整除？？？ 令 输入长度函数f(length)，Length: DΠ →Z+ ＤＴＭ程序Ｍ所能识别的言记为ＬＭ＝｛ｘ∈∑＊｜Ｍ accept ｘ｝ 称一个DTM程序 M在编码策略ｅ下求解判定问题∏，如果Ｍ对于∑*中字符串均停机，且ＬＭ＝Ｌ［∏，ｅ］ 只有当一个DTM程序 M对于所有∑*中字符串均停机，我们才称其为一个算法（Algorithm） 通俗讲：算法是指可以用来求解某一问题，带一般性的一步一步的过程。 说一个算法解决了某一问题，即是对任意实例输入都能得到精确的答案。 P 类问题的定义不依赖于编码策略ｅ； Ｐ类问题的定义也不依赖于DTM计算模型； 今后我们直接说判定问题∏是否属于P类，而不必再提及计算模型，语言及编码策略。 最小生成树，最短路，最大匹配等都属于Ｐ类。 … 1 q0 1 0 0 0 b … b 1 b 1 0 0 0 b … b 1 b 1 0 0 0 b … b 1 b 1 0 0 0 b … b 1 b 1 0 0 0 b … b 1 b 1 0 0 0 b … b 1 b 1 0 0 0 b … b 1 b 1 0 b 0 b … b 1 b 1 0 b b b … b b q0 q0 q0 q0 q0 q1 q2 qY q 0 1 b q0 (q0,0,R) (q0,1,R) (q1,b,L) q1 (q2,b,L) (q3,b,L) (qN,b,L) q2 (qY,b,L) (qN，b,L) (qN,b,L) q3 (qN,b,L) (qN,b,L) (qN,b,L) 一个带有输入字符表∑的DTM程序Ｍ接受(accept)ｘ∈∑＊，当且仅当其作用于ｘ时，停机于qY状态。 ＤＴＭ程序Ｍ所能识别的语言记为 　ＬＭ＝｛ｘ∈∑＊｜Ｍ accept ｘ｝ 当ｘ∈∑＊－ＬＭ时，Ｍ的计算要么停机于ｑＮ，要么永不停机。 例 被４整除性判定 Instance ：正整数Ｎ 　Question:　N 能被４整除吗？ 将Ｎ写成二进制形式，Ｎ被４整除当且仅当二进制后两位为零。 上例中的ＤＴＭ程序Ｍ为判定一个数被４整除问题的一个算法。 DTM程序的时间复杂性 DTM程序M对输入x的计算时间：程序从开始到停机为止所运行的步数。 一个对所有x∈∑*均停机的DTM程序M，其时间复杂性函数定义为, TM:Z+→Z+, TM(n)=max{m|存在一个x∈Σ*, |x|=n, M对输入x的计算时间为m} 即TM(n)为计算长为n的字符串所需的最大时间。 若存在多项式p使得TM(n)≤p(n),对于任意n∈Z+,成立，则称M为多项式时间DTM程序。 P类问题 P类问题定义为： P={L| 存在多项式时间DTM程序M使得L[Π,e]=LM} 判定问题∏∈P， 若存在多项式时间ＤＴＭ程序Ｍ，其可以在编码ｅ下求解∏，即 L[∏，e]∈Ｐ, 　或者L[∏]∈Ｐ。 * * 计算复杂性导论：NP-完全性 鲁红亮 Email:luhongliang@mail.xjtu.edu.cn Cell phone:理科楼404