《算法设计与分析》教学大纲

《《算法设计与分析》教学大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、372.133.1《算法设计与分析》教学大纲学分数3周学时3+1课程名称：算法设计与分析英文名称：DesignandAnalysisofAlgorithms任课老师：朱洪hzhu@fudan.edu.cn开课时间：2003年9月～2004年1月学时：4学时/周学分：4授课对象：复旦大学计算机系本科生课程性质：必修课授课教材：T.H.Cormen,C.E.Leiserson,R.L.RivestandC.Stein(2001),IntroductiontoAlgorithms(thesecondedition).TheMITPress，中

2、文名《算法导论（第二版）》（影印版），高等教育出版社电子教案：http://10.20.20.10先修课程：数据结构、离散数学、高等数学、概率论与数理统计课程概要：简单对困难为什么我们要研究算法和复杂性理论？本节课介绍了Insertion-Sort和Merge-Sort两个算法，并比较了它们时间复杂度的优劣。函数的增长刻划时间复杂度的常用函数以及它们增长速度的比较，用到一些数学分析（或高等数学）的知识。最后，我们分析了Merge-Sort算法的时间复杂度。求解递归式介绍了求解递归式的三种方法，证明了MasterTheorem。证明技巧就

3、是递归树方法：先考虑n恰好是b的次幂的情形；再考虑一般情形。MasterTheorem在以后的学习中经常用到，务必掌握。矩阵计算矩阵是科学计算不可缺少的工具，矩阵计算理论可参考Golub和vonLoan的名著MatrixComputation。本节介绍了矩阵乘法的Strassen算法（用的是分治法），求解线性方程组的LU算法和LUP算法，矩阵求逆的算法。介绍了对称正定阵的许多有趣的性质。最后，证明了Winograd定理和Aho-Hopcroft-Ullman定理，该定理说矩阵乘法和矩阵求逆的时间复杂度相等。这是非常有趣的一节，充满了技巧

4、。概率分析与随机算法除了以最坏情况的时间消耗作为衡量一个算法优劣的标准，我们也可以用平均时间(相对于各种输入情况)消耗作为一个标准。如果一个算法在原有的输入数据之外，还在算法执行过程中加入随机性（因为真正理论意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数），然后看算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，虽然它的准确率略微降低。HeapsortHeapsort是一种比Insertion-Sort和Merge-Sort都有效的算法。Heap有许多有趣的性质，是一个重要的数据结构。Quichsort及其他

5、分析了Quicksort，Radixsort和Bucketsort的算法复杂度。动态规划首先，以AssemblyLineProblem和Matrix-chainMultiplication为例，给出动态规划算法。主要目的是直观地启发何时、如何使用动态规划算法。在介绍了动态规划算法的一般策略后，我们分析了求解最长公共子序列和最优二分搜索树的动态规划算法。另外还有HiddenMarkovModel(HMM)的Viterbi算法，它在语音识别和切分/词性标注（自然语言处理）等有较好的应用。线性规划介绍了线性规划及其单纯形算法。线性规划是最优化

6、理论中很重要的一部分，有着广泛的应用背景。单纯形法已经相当成熟，在线性规划的算法中实用性最强。也对近十年来发展的近似算法影响很大。贪心法（以背包问题为例）介绍了贪心法与动态规划的关系以及使用贪心法必须满足的两个性质。介绍了Huffman编码的贪心算法。贪心法什么时候能取到最优界并无一般理论，但对于求最大weightedmatroid（拟阵理论是H.Whitney于1935年提出的）我们有一个完美的结果——贪心法可取到最优解。本节最后介绍了用贪心matroid方法解决unit-timetaskscheduling问题，很有趣。图算法初步介

7、绍了广度优先和深度优先的图搜索算法及其性质。接着介绍了深度优先搜索的两个应用：拓扑排序和如何找出一个有向图的所有强连通分支。最小生成树介绍了最小生成树的性质和Kruskal算法和Prim算法。多项式与快速Fourier变换两个n次多项式相乘，用FFT可将时间复杂度从Theta(n^2)降至Theta(nlogn)。需要一些代数学的知识，蛮有趣的。数论算法首先，概要性地介绍了初等数论的一些结果（譬如，Euler定理和中国剩余定理）和它们在求解最大公约数（及其线性表示）、不定方程、不定方程组等方面的应用，给出了相应的算法。第二部分介绍了公钥

8、密码系统加密和数字签名的基本想法和RSA算法。作为补充材料，最后介绍了素性检验和整数分解。顺序统计量如果存在异常样本点，中位数要比样本均值更有效。在统计学中，顺序统计量非常重要（例如，基于秩的统计推断）。我