算法分析第一章导论

《算法分析第一章导论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1主讲教师：孙成敏suncm@jlu.edu.cn2015年3月---2015年6月计算机算法设计与分析2课程设置类别：专业必修课学分：3学分理论学时：48习题课学时：8开课周数：1-14周3基本内容导引（第一、二章）基本的算法设计策略分治法（第四章）贪心方法（第五章）动态规划（第六章）回溯法（第八章）分支－限界法（第九章）基本算法分析方法NP-难度和NP-完全问题（第十章）4学习目标掌握基本的算法设计方法掌握进行算法分析的基本方法（时间、空间复杂度分析）灵活运用基本的算法设计方法，解决实际问题5

2、参考书目计算机算法设计与分析王晓东电子工业计算机算法设计与分析苏德富电子工业8问：“交给你的问题，解决方法想出来了吗？”答：“我找不到一个有效的方法来解决它，因为这样的方法是不存在的。”要证明一个问题不存在有效的方法，往往比寻找一种有效方法更难。9问：“交给你的问题，解决方法想出来了吗？”答：“我找到了一方法来解决它，理论上可实现的，但是以我们目前的力量实现它是不可能的。”方法消耗的资源太大了。问题解决的好吗？10现实世界的两个问题问题能解决吗？(可计算性)问题解决的好吗？(计算复杂性)11可计算

3、性研究的范畴计算机虽然神通广大，还是在人的控制下工作。计算机并非什么都能做，有的事情理论上它根本做不了。讨论哪些事计算机能做，哪些事计算机做不了，属于可计算性理论研究的范畴。12一个满足可计算性的问题26个英文字母全排列，它的排列数为26！≈4×1026以每年365天计算，共有365×24×3600＝3.1536×107秒。以每秒能完成107个排列的超高速电子计算机来做这项工作，需要4×1026/(3.1536×107×107)≈1.2×1012年（千亿年）。13有一些问题虽然在理论上能够由计算机

4、解决，但因其算法占用资源太多而无法实际完成，因此需要选择其他算法或改进算法。要知道算法的优劣好坏，就要对算法需要多少计算时间和存储空间做定量的分析。算法分析研究的范畴迄今为止，已有20%左右的计算机科学家因其在计算复杂性方面的研究工作而获得图灵奖。14本课程的计算机本课程指的计算机是和图灵机计算能力等价的、冯诺伊曼体系结构计算机，即确定性图灵机。量子计算机是非确定性图灵机，其算法和计算复杂性完全不同。15几个典型的非数值计算问题巡回推销员问题n皇后问题背包问题16巡回推销员问题[动态规划]设有n个

5、城市，已知任意两城市间之距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。试一试求出最短路径。17n皇后问题[回溯法]这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、竖向和斜向都能走步和吃子，问在nn格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。当n很大时，问题很难。对于n8，现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n4，试一试。18背包问题有一旅行者

6、要从3种物品中选取不超过50公斤重的行李随身携带，要求总价值最大。物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重30千克，价值120元。[动态规划]物品不可分割的前提下，求总价值最大。[贪心算法]物品可以分割的前提下，求总价值最大。19发展历史D.Knuth《TheArtofComputerProgramming》A.V.Aho,J.Hopcroft,J.Ullman《TheDesignandAnalysisofcomputerAlgothms》ThomasH.Cormen

7、,CharlesE.Leiserson,RonaldL.Rivest《IntroductiontoAlgorithms》20第二章导引与基本数据结构2.1算法2.2分析算法及数学基础2.3用SPARKS语言写算法2.4基本数据结构（略）212.1算法什么是算法算法的重要特性计算过程与算法的区别问题的求解过程算法学习的基本内容22什么是算法算法是解决一确定类问题的任意一种特殊的方法。数值计算方法非数值计算方法算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。求解数值

8、问题，插值计算、数值积分等。求解非数值问题，主要进行判断比较。23算法的五个重要特性确定性：每一种运算必须要有确切的定义，无二义性；能行性：运算都是基本运算，原则上能在有限时间内完成；输入：有0个或多个输入；输出：一个或多个输出；有穷性：在执行了有穷步运算后终止；仅仅有穷还不够，还要在现代计算机上有效才行。24计算过程与算法的区别计算过程可以不满足算法的性质(5)有穷性。例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。程序算法