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

1、372.133.1算法设计与分析教学大纲学分数3周学时3+1课程名称英文名称任课老师开课时间学时：4学时/周学分：4授课对象：复旦大学计算机系本科生课程性质：必修课授课教材：T.H.Cormen,C.IntroductiontoAlgorithms法导论（第二版）（影印版）电子教案：0E.Leiserson,R.L.Rivestand(thesecondedition).TheMITPress,高等教育出版社C.Stein(2001),中文名算先修课程课程概要数据结构、离散数学、高等数学、概率论与数理统计简单对困难函数的增长为什么我们要研究算法和复杂性理论？本节

2、课介绍了Merge-Sort两个算法，并比较了它们时间复杂度的优劣。刻划时间复杂度的常用函数以及它们增长速度的比较，Insertion-Sort和用到一些数学分析求解递归式（或高等数学）的知识。最后，我们分析了度。介绍了求解递归式的三种方法，证明了Merge-Sort算法的时间复杂MasterTheorem。证明技巧就是算法设计与分析DesignandAnalysisofAlgorithms朱洪hzhu2003年9月2004年1月递归树方法：先考虑n恰好是b的次嘉的情形；再考虑一般情形。MasterTheorem在以后的学习中经常用到，务必掌握。矩阵是科学计算不可缺少的工具，矩阵计算理论可参考

3、Golub和vonLoan的名著MatrixComputation。本节介绍了矩阵乘法的Strassen算法（用的是分治法），求解线性方程组的LU算法和LUP算法，矩阵求逆的算法。概率分析与随机算法HeapsortQuichsort及其他介绍了对称正定阵的许多有趣的性质。最后，证明了Winograd定理和Aho-Hopcroft-Ullman定理，该定理说矩阵乘法和矩阵求逆的时间复杂度相等。这是非常有趣的一节，充满了技巧。除了以最坏情况的时间消耗作为衡量一个算法优劣的标准,我们也可以用平均时间（相对于各种输入情况）消耗作为一个标准。如果一个算法在原有的输入数据之外，还在算法执行过程中加入随机性

4、（因为真正理论意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数），然后看算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，虽然它的准确率略微降低。Heapsort是一种比Insertion-Sort和Merge-Sort都有效的算法。Heap有许多有趣的性质，是一个重要的数据结构。分析了Quicksort,Radixsort和Bucketsort的算法复杂度。动态规划线性规划贪心法图算法初步最小生成树多项式与快速数论算法顺序统计量串匹配平摊分析首先，以AssemblyLineProblem和Matrix-chainMultiplication为例，给出动态规划算法。主

5、要目的是直观地启发何时、如何使用动态规划算法。在介绍了动态规划算法的一般策略后，我们分析了求解最长公共子序列和最优二分搜索树的动态规划算法。另外还有HiddenMarkovModel（HMM）的Viterbi算法，它在语音识别和切分/词性标注（自然语言处理）等有较好的应用。介绍了线性规划及其单纯形算法。线性规划是最优化理论中很重要的一部分，有着广泛的应用背景。单纯形法已经相当成熟，在线性规划的算法中实用性最强。也对近十年来发展的近似算法影响很大。（以背包问题为例）介绍了贪心法与动态规划的关系以及使用贪心法必须满足的两个性质。介绍了Huffman编码的贪心算法。贪心法什么时候能取到最优界并无一般

6、理论，但对于求最大weightedmatroid（拟阵理论是H.Whitney于1935年提出的）我们有一个完美的结果一一贪心法可取到最优解。本节最后介绍了用贪心matroid方法解决unit-timetaskscheduling问题，很有趣。介绍了广度优先和深度优先的图搜索算法及其性质。接着介绍了深度优先搜索的两个应用：拓扑排序和如何找出一个有向图的所有强连通分支。介绍了最小生成树的性质和Kruskal算法和Prim算法。Fourier变换两个n次多项式相乘，用FFT可将时间复杂度从Theta（nA2）降至Theta（nlogn）。需要一些代数学的知识，蛮有趣的。首先，概要性地介绍了初等数论

7、的一些结果（譬如，Euler定理和中国剩余定理）和它们在求解最大公约数（及其线性表示）、不定方程、不定方程组等方面的应用，给出了相应的算法。第二部分介绍了公钥密码系统加密和数字签名的基本想法和RSA算法。作为补充材料，最后介绍了素性检验和整数分解。如果存在异常样本点，中位数要比样本均值更有效。在统计学中，顺序统计量非常重要（例如，基于秩的统计推断）。我们要解决的问题是：给定n个不等的实数，找出第i小的那个。首先介绍一个随机算法，它的时间复杂度的期望是线性的。接着，我们给出一个确定性的算法，它在最坏的情形可达到线性。寻找顺序统计量的算法所需的比较次数介于2n和3n之间，但精确的系数至今未知。介绍

8、了Naive串匹配、Rabin-Karp串匹配、基于有限自动机的串匹配和Knuth-Morris-Pratt串匹配算法并分析了它们的算法复杂度。要点：如果patternstring与textstring部分匹配，贝Upatternstring向右最大滑动的步数与patternstring自身结构有关。正是因为这个特点，KMP算法分作两步：前处理和匹配。KM嘤法前处理的时间是patternstring长度的线性函数，匹配的时间是textstring长度的线性函数。在平摊分析里，执行时间不仅决定于什么操作，而且决定于操作执行时的数据结构，因此我们计算运行时间是整体地累计各种操作运行时间的总和，然后

9、求平均。所以，也许某些操作的平摊时间比实际运行时间多算了，但是另外些操作的平摊时间比实际时间减少，累加起来，平摊时间不比实际执行时间少，但基本接近。单源点的最短路径问题问题：给定一个加权有向图G和一个源点s,对于G中任意一点v,求从s到v的最短路径。我们介绍三个算法：Bellman-Ford算法，有向非循环图的单源点最短路径算法和Dijkstra算法。最后，介绍如何利用Bellman-Ford算法判定差分约束方程组（线性规划中一类特殊的约束条件）是否有解。任意点对间的最短路径问题问题：给定一个加权有向图G,求任意点对u,v间的最短路径。首先，类比两个n阶方阵的乘法，我们介绍一个动态规划算法。第

10、二个算法是Floyd-Warshall算法，也可用于计算有向图的传递闭包。第三个算法（Johnson算法）利用“单源点的最短路径”问题的Bellman-Ford算法和Dijkstra算法，处理稀疏图时要好于前两个算法。最大流问题问题：给定一个有向图，每条边都赋予一个非负整数（表示承载能力），规定一个源点和一个终点，求解从源点到终点的最大流。我们介绍了Ford-Fulkerson方法，该方法也可用来求解最大二部图匹配问题。排序网络计算几何学排序网络是一个并行算法，用于快速排序（时间复杂度为O（logA2n）。介绍三个平面几何问题的算法。第一个问题是：给定一个线段的集合，判定其中任何两条线段是否相

11、交。第二个问题是：给定平面上n个点，求解覆盖它们的最小凸集（Graham算法和Jarvis算法）。第三个问题是：给定平面上n个点，求所有可能两点间的最小距离（1985年，Shamos用分治法解决，时间复杂度为O（nlogn）。NP完全性定义了NP-completeness,介绍了如何证明一个决策问题（decisionproblem）是NP-hard的。最后介绍了几个经典的NP-complete问题。课程目标：1,通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。2.培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。3,鼓励学生运用算法

12、知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。参考书及课外读物：0.M.H.Alsuwaiyel(2003)AlgorithmsDesignTechniquesandAnalysis.WorldScientificPublishingandPublishingHouseofElectronicsIndustry1. S.BaaseandA.V.Celder(2000),ComputerAlgorithm:IntroductiontoDesignandAnalysis(thethirdedition).AddisonWesleyLongman2. T.H.Cormen

13、,C.E.Leiserson,R.L.RivestandC.Stein(2001),IntroductiontoAlgorithms(thesecondedition).TheMITPress3. E.HorowitzandS.Sahni(1978),FundamentalsofComputerAlgorithms,ComputerSciencePress,PitmanInc.4. C.A.Shaffer(1997),DataStructureandAlgorithmAnalysis.Prentice-Hall,Inc.中译本：数据结构与算法分析，张铭、刘晓丹，电子工业出版社(1998年)5. SartajShani(1999),DataStructures,Algorithms,andApplicationsinC+.Pren_tice-Hall,Inc.Homepage:http:据结构算法与应用C+语言描述，汪诗林，机械工业出版社(2000年).6.