开发工具:
文件大小: 3mb
下载次数: 0
上传时间: 2010-06-21
详细说明： 可计算性与复杂性——周长林 李占山 编 目录 第一部分 预备知识 第一章 导 引……………………………………………………………….1 1.1集合的概念与相关运算………………………………………..2 1.2关系…………………………………………………………..3 1.2.1关系的基本概念及其性质………………………………...3 1.2.2等价关系…………………………………………………...7 1.2.3部分序关系………………………………………………...7 1.3映射…………………………………………………………..8 1.4定义、定理及其基本的证明技术……………………………..9 1.5字符串与语言…………………………………………………..10 第二部分可计算性理论 第二章 可计算函数…………………………………………………………11 2.1程序设计语言................................................................................11 2.2无条件转移和赋值的消去.......................................................... ..15 2.3可计算函数....................................................................................16 3.4习题与问题....................................................................................19 第三章 递归函数............................................................................................20 3.1复合递归与取极小算子..............................................................20 3.2原始递归函数..............................................................................22 3.3原始递归谓词和原始递归集合..................................................25 3.4受囿取极小值..............................................................................29 3.5部分递归函数递归函数及其可计算性......................................35 3.6习题与问题..................................................................................39 第四章 Post-Turing程序和Turing机...........................................................41 4.1Post-Turing程序...........................................................................41 4.2可计算性与P-T可计算性..........................................................44 4.3广义Post-Turing 机.................................................................50 4.4Turing机.......................................................................................54 4.5Post-Turing程序的数字编码.......................................................60 4.6一通用程序.................................................................................63 4.7迭代定理.....................................................................................69 4.8习题与问题.................................................................................71 第五章 半可计算性.......................................................................................72 5.1半可计算谓词和半可计算集合.................................................72 5.2半可计算的一些封闭性.............................................................77 5.3半可计算与可计算性.................................................................83 5.4习题与问题.................................................................................89 第六章 半图厄系统.......................................................................................90 6.1半图厄系统.................................................................................90 6.2用半图厄系统模拟图灵机...........................................................91 6.3半图厄系统和半可计算集合.......................................................94 6.4判定问题.......................................................................................96 6.5习题与问题...................................................................................99 第七章 图灵机.................................................................................................100 7.1引言...............................................................................................100 7.2图灵机模型...................................................................................101 7.3图灵机的变形...............................................................................104 7.3.1双向无限带........................................................................104 7.3.2多带图灵机........................................................................106 7.3.3非确定图灵机....................................................................108 7.3.4多维图灵机........................................................................109 7.3.5多头图灵机........................................................................110 7.3.6离线图灵机........................................................................111 7.4习题...............................................................................................111 第三部分 计算复杂性 第八章 计算复杂性理论................................................................................113 8.1复杂性定义..................................................................................113 8.1.1空间复杂度.......................................................................113 8.1.2时间复杂度.......................................................................113 8.1.3关于时间和空间复杂度函数的特殊假定.......................114 8.1.4非确定时间和空间复杂度...............................................114 8.1.5复杂性类...........................................................................116 8.2 线性加速、带压缩和带数目的减少.....................................116 8.2.1带压缩...............................................................................116 8.2.2对于空间复杂性类的带数目的减少...............................117 8.2.3线性加速...........................................................................117 8.2.4对于时间复杂性类的带数目的减少...............................119 8.3 谱系定理...................................................................................123 8.3.1空间谱系...........................................................................124 8.3.2时间谱系...........................................................................127 8.4复杂性量度间的关系................................................................128 8.5 转换引理和非确定谱系...........................................................131 8.5.1 转换引理..........................................................................131 8.5.2一个非确定空间谱系.......................................................133 8.6 一般复杂性量度的性质：间隙定理、加速定理和并定理..134 8.6.1加速定理............................................................................136 8.6.2并定理................................................................................138 8.7 公理化复杂性理论....................................................................141 8.7.1Blum公理...........................................................................142 8.7.2复杂性量度间的递归关系................................................143 8.8习题与问题....................................................................................144 第九章 NP完全问题简介................................................................................145 9.1 P类和NP类..................................................................................145 9.1.1可在多项式时间内解答的问题............................................145 9.1.2非确定型多项式时间............................................................145 9.1.3 NP完全问题..........................................................................146 9.2多项式时间和空间.........................................................................147 9.3 某些NP完全问题.........................................................................150 9.3.1可满足性问题........................................................................150 9.3.2可满足性问题是NP完全的.................................................151 9.3.3 NP－完全的受限可满足性问题...........................................153 9.3.4其他NP完全问题.................................................................156 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
