资源描述：
《算法分析与计算复杂性理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1算法分析与计算复杂性理论2课程简介课程名称算法分析与计算复杂性理论AnalysisofAlgorithmsandTheoryofComputationalComplexity基本目的掌握组合算法设计的基本技术掌握算法分析的基本方法掌握计算复杂性理论的基本概念学习应用算法理论处理实际问题3课程内容顺序算法设计的基本技术分治策略动态规划回溯算法贪心法概率算法顺序算法分析的基本方法评价算法的标准算法复杂性的估计问题复杂性的下界算法分析的实例计算复杂性理论Turing机计算复杂性的概念NP完全性理论及其应用N
2、P完全理论的拓广预计进度安排内容学时内容学时1前言19Turing机22数学基础210计算复杂性理论23分治策略411NP完全性理论24动态规划412Cook定理15回溯与分支估界413NP完全性证明56贪心法414NP完全理论应用27概率算法315NP完全理论的拓广28算法分析技术616小结15教材与参考书1.AlgorithmDesign,JonKleinberg,EvaTardos,Addison-Wesley,清华大学出版社影印版，2006.2.IntroductiontoAlgorithms（
3、SecondEdtion）,ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,TheMITPress2001.高教出版社影印版，2002.3.计算机和难解性:NP完全性理论导引,M.R.加里,D.S.约翰逊,张立昂等译，科学出版社,1987.*4.计算复杂性导论，堵丁柱，葛可一，王洁，高教出版社2002.*5.LimitstoParallelComputation:P-CompletenessTheory,RaymondGreenlaw,H.JamesHo
4、over,WalterL.Ruzzo,OxfordUniversityPress,1995.学习安排成绩评定：小论文：结合研究工作，50%期末笔试：50%7引言:理论上的可计算与现实上的可计算算法研究的重要性理论上的可计算——可计算性理论现实上的可计算——计算复杂性理论8投资问题问题：m元钱，投资给n个项目，效益函数fi(x)，表示第i个项目投入x元钱的效益，i=1,2,…,n.如何分配每个项目的钱数使得总效益最大？采用什么算法？效率怎样？令xi是第i个项目的钱数9蛮力算法的代价Stirling公式：非
5、负整数解的个数估计：蛮力算法——穷举法代价太大能否利用解之间的依赖关系找到更好的算法？结论：需要算法设计技术10T(n)=2T(n1)+1，T(1)=1，ABC思考：是否存在更好的解法？Reve难题：Hanoi塔变种，柱数增加，允许盘子相等.其他变种：奇偶盘号分别放置解得T(n)=2n11秒移1个，64个盘子要多少时间？（5000亿年）Hanoi塔问题11其他问题搜索问题输入：排好序的数组L，x输出：x是否在L中？如果在输出它的下标排序问题输入：n个数输出：按递增顺序排好的n
6、个数选择问题输入：n个数的集合S，正整数k（1kn)输出：S中第k小的数需要：现有的算法中哪个算法最好？是否存在更有效的算法？12Algorithm+DataStructure=Programming好的算法提高求解问题的效率节省存储空间需要解决的问题问题寻找求解算法算法设计技术算法算法的评价算法分析技术算法类问题复杂度的评价问题复杂性分析问题类能够求解的边界计算复杂性理论13算法研究的重要性算法设计与分析技术在计算机科学与技术领域有着重要的应用背景算法设计分析与计算复杂性理论的研究是计算机
7、科学技术的核心研究领域1966-2005期间，Turing奖获奖50人，其中10人以算法设计，7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖计算复杂性理论的核心课题“P=NP?”是本世纪7个最重要的数学问题之一通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用14理论上的可计算：可计算性理论研究目标确定什么问题是可计算的，即存在求解算法合理的计算模型已有的：递归函数、Turing机、演算、Post系统等条件：计算一个函数只要有限条指令每条指令可以由模型中的有限个计
8、算步骤完成指令执行的过程是确定的核心论题：Church-Turing论题如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的可计算性是不依赖于计算模型的客观性质15算法至少具有指数时间：理论上可计算——难解的多项式时间的算法：现实上可计算——多项式时间可解的对数多项式时间的算法：高度并行可解的理论上可计算理论上不可计算现实可计算高度并行可计算理论上与现实上的可计算性16计算复杂性理论内容算法复杂度——算法所使用的时
