重庆大学《计算复杂性及算法分析》课程内容纲要(总)

《重庆大学《计算复杂性及算法分析》课程内容纲要(总)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算复杂性及算法分析课程内容纲要主要参考书:1.主要参考书12.主耍参考书23.主要参考书34.主要参考书4J.E.Hopcroft等〈自动机理论，语言和计算导论〉D.E.KnuthVID.E.KnuthV3G&K&P

2、要参考书1-第8章-8.2,8.3,8・4;第10章-10.1主要内容是介绍图灵机.以及P与NP的一些相关概念第二讲（4学时）主要参考书1-第10章-10.1,10.2主要内容是介绍NP完全问题,Cook定理的证明第三讲（4学时）主要参考书2-第1章-1.2.1,1.2.3,1.2.5,1.2.6,1.2.&1.2.9算法分析所会用到许多数学知识，高老师在1.2中给出了一些介绍.为了简洁我们引用这里的内容.更好的选择是主要参考书4第四讲（4学时）主要参考书2■第1章-1.2.10一个算法的分析，和数学有关的分析第五讲（4学时）主要参考书2-第1章-1.3.3对排列的应用，和程序有关的分

3、析第六讲（4学时）主要参考书2-第1章-2.3.4.1,2.3.4.5树的基本数学性质：克希霍夫定律一种一般的程序执行时间估算的方法，以及以后要研究的内容屮经常要出现的内容:通路长第七讲（4学时）主要参考书3-第5章-5.3,5.3.1最优排序（一）复习（2学时）第一讲（4学时）主要参考书1第8章-8.2,8.3,8.4;10.1主要内容是介绍图灵机以及P和NP的一些概念•为介绍Cook定理做准备计算复杂性和算法分析是两个内容•关于计算复杂性我们以介绍Cook定理为界；关于算法分析我们以介绍G.D.Knuth的一些实际分析例子为界.这一讲介绍图灵计算模型.以及一些与NP完全问题有关的内

4、容.目的是引出Cook的第一个NPC问题的证明.由此可以对图灵模型和NPC问题有一个入门的认识.0.难解问题比判定问题更为普遍，所以我们把计算复杂性的主要介绍定在难解问题上1•有穷状态自动机，（DFA主要参考书1-31页,2.2.1,33页，图2-4,NFA主要参考书1-37页,2.3.1,图2-9）.主要涉及确定与不确定的概念2.从编译原理课程上下文无关文法的分析引出下推自动机（PDA主要参考书1-6.1.2,6.1.4）.主要涉及形式化定义，分析（也称计算）过程的瞬时描述和ID3.确定性图灵机.一种非常简单的计算模型，图灵机.相比之下,C程序的状态太复杂，不能给出可以理解的形式证明

5、.参见主要参考书1第8章-&2,&2.24.图灵机的瞬时描述.ID的内容（主要参考书1第8章-&2.3）介绍一个图灵机的识别例子，仔细的研读这个例子，形成对图灵机的感性认识•还有一个自己认为成立的图灵机的计算例子.2+3=5.具体可表示为B110111B转变成B11111B.从而完成1进制的2+3二5.在主要参考书1第八章-8.2.4给出了一个做减法的例子•其行为特征类似•构造图灵机并不是一件容易的事情，主要参考书1-&2.4给出了一种较为容易理解的状态转移图•并不难理解，可以从状态转移表得到，类似YFA,不过添加了一些图灵机必要的内容.5.发明了不确定性图灵机，它不是一种真实的计算机

6、，仅仅是一个计算模型，而H现阶段也不可能实现，但是并不妨碍我们用它来思考•充分多的转移分支保证了恰当方式描述的问题得以充分的遍历•有些在DTMM上没有得到多项式解的问题可以在这样的计算模型上得到多项式吋间解.可以这样解决的问题被称为NP问题.也就是非确定性多项式时间解•说到底,DTMM和难题们ZHIJIAN的关系就想是用定理来解决问题还是用搜索来解决问题.6•停机概念:没有移动就是停机了•接受状态一定可以等价于停机状态，但是不接受不一定停机•这个与语言有关，也与判定问题有关，不属于我们约定的内容•停机与接受没有直接的关系，但是停机对复杂度有关.7.非确定性图灵机非确定性图灵机拥有想象中

7、的并行处理能力.如果对树进行搜索,NTMM只需要最长树支的时间，但是树有指数阶的节点.参见主要参考书1第八章-8.4.48•实际工作中更容易碰到的是难解问题•例如求解H回路，调度问题•主要参考书1第10章-8・2.读一下这一段话应该很有帮助.9.由于对这样的问题没有充分的解决方法，所以写不出来确定的图灵模型•一个搜索过程与非确定性图灵模型极为相似.如果我们假设我们有搜索分支那么多的处理器，于是我们就有了一个并行的问题解决能力•本来在串行搜索上需