《《算法设计与分析》教学大纲》由会员分享，可在线阅读，更多相关《《算法设计与分析》教学大纲（4页珍藏版）》请在金锄头文库上搜索。
1、372.133.1算法设计与分析教学大纲学分数 3 周学时 3+1课程名称：算法设计与分析英文名称：Design and Analysis of Algorithms 任课老师：朱洪 开课时间：2003 年 9月2004 年 1月学时：4 学时/周学分：4授课对象：复旦大学计算机系本科生课程性质：必修课授课教材：T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to Algorithms (the second edition). The MIT Press，中文名算法导论（第二版） （影
2、印版） ，高等教育出版社电子教案：http:/10.20.20.10先修课程：数据结构、离散数学、高等数学、概率论与数理统计课程概要：简单对困难 为什么我们要研究算法和复杂性理论？本节课介绍了 Insertion-Sort和 Merge-Sort两个算法，并比较了它们时间复杂度的优劣。 函数的增长 刻划时间复杂度的常用函数以及它们增长速度的比较，用到一些数学分析（或高等数学）的知识。最后，我们分析了 Merge-Sort算法的时间复杂度。 求解递归式 介绍了求解递归式的三种方法，证明了 Master Theorem。证明技巧就是递归树方法：先考虑 n恰好是 b的次幂的情形；再考虑一般情形。Ma
3、ster Theorem在以后的学习中经常用到，务必掌握。 矩阵计算 矩阵是科学计算不可缺少的工具，矩阵计算理论可参考 Golub和 von Loan的名著 Matrix Computation。本节介绍了矩阵乘法的 Strassen算法（用的是分治法） ，求解线性方程组的 LU算法和 LUP算法，矩阵求逆的算法。介绍了对称正定阵的许多有趣的性质。最后，证明了 Winograd定理和 Aho-Hopcroft-Ullman定理，该定理说矩阵乘法和矩阵求逆的时间复杂度相等。这是非常有趣的一节，充满了技巧。 概率分析与随机算法 除了以最坏情况的时间消耗作为衡量一个算法优劣的标准，我们也可以用平均时
4、间(相对于各种输入情况)消耗作为一个标准。如果一个算法在原有的输入数据之外，还在算法执行过程中加入随机性（因为真正理论意义下的随机数是不可能由计算机产生的，所以实际上用的是伪随机数） ，然后看算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少，虽然它的准确率略微降低。Heapsort Heapsort是一种比 Insertion-Sort和 Merge-Sort都有效的算法。Heap有许多有趣的性质，是一个重要的数据结构。 Quichsort及其他 分析了 Quicksort，Radixsort 和 Bucketsort的算法复杂度。 动态规划 首先，以 Assembly Line
5、Problem和 Matrix-chain Multiplication为例，给出动态规划算法。主要目的是直观地启发何时、如何使用动态规划算法。在介绍了动态规划算法的一般策略后，我们分析了求解最长公共子序列和最优二分搜索树的动态规划算法。另外还有 Hidden Markov Model (HMM)的 Viterbi算法，它在语音识别和切分/词性标注（自然语言处理）等有较好的应用。 线性规划 介绍了线性规划及其单纯形算法。线性规划是最优化理论中很重要的一部分，有着广泛的应用背景。单纯形法已经相当成熟，在线性规划的算法中实用性最强。也对近十年来发展的近似算法影响很大。 贪心法 （以背包问题为例）介
6、绍了贪心法与动态规划的关系以及使用贪心法必须满足的两个性质。介绍了 Huffman编码的贪心算法。贪心法什么时候能取到最优界并无一般理论，但对于求最大 weighted matroid（拟阵理论是 H. Whitney于 1935年提出的）我们有一个完美的结果贪心法可取到最优解。本节最后介绍了用贪心 matroid方法解决 unit-time task scheduling问题，很有趣。 图算法初步 介绍了广度优先和深度优先的图搜索算法及其性质。接着介绍了深度优先搜索的两个应用：拓扑排序和如何找出一个有向图的所有强连通分支。最小生成树 介绍了最小生成树的性质和 Kruskal算法和 Prim算
7、法。 多项式与快速 Fourier变换 两个 n次多项式相乘，用 FFT可将时间复杂度从 Theta(n2)降至Theta(nlog n)。需要一些代数学的知识，蛮有趣的。 数论算法 首先，概要性地介绍了初等数论的一些结果（譬如，Euler 定理和中国剩余定理）和它们在求解最大公约数（及其线性表示） 、不定方程、不定方程组等方面的应用，给出了相应的算法。第二部分介绍了公钥密码系统加密和数字签名的基本想法和 RSA算法。作为补充材料，最后介绍了素性检验和整数分解。 顺序统计量 如果存在异常样本点，中位数要比样本均值更有效。在统计学中，顺序统计量非常重要（例如，基于秩的统计推断） 。我们要解决的问
8、题是：给定 n个不等的实数，找出第 i小的那个。首先介绍一个随机算法，它的时间复杂度的期望是线性的。接着，我们给出一个确定性的算法，它在最坏的情形可达到线性。寻找顺序统计量的算法所需的比较次数介于 2n和 3n之间，但精确的系数至今未知。 串匹配 介绍了 Naive串匹配、Rabin-Karp 串匹配、基于有限自动机的串匹配和Knuth-Morris-Pratt串匹配算法并分析了它们的算法复杂度。要点：如果 pattern string与 text string部分匹配，则 pattern string向右最大滑动的步数与 pattern string自身结构有关。正是因为这个特点，KMP算法
9、分作两步：前处理和匹配。KMP 算法前处理的时间是 pattern string长度的线性函数，匹配的时间是 text string长度的线性函数。 平摊分析 在平摊分析里，执行时间不仅决定于什么操作，而且决定于操作执行时的数据结构，因此我们计算运行时间是整体地累计各种操作运行时间的总和，然后求平均。所以，也许某些操作的平摊时间比实际运行时间多算了，但是另外些操作的平摊时间比实际时间减少，累加起来，平摊时间不比实际执行时间少，但基本接近。 单源点的最短路径问题 问题：给定一个加权有向图 G和一个源点 s，对于 G中任意一点 v，求从s到 v的最短路径。我们介绍三个算法：Bellman-Ford
10、 算法，有向非循环图的单源点最短路径算法和 Dijkstra算法。最后，介绍如何利用Bellman-Ford算法判定差分约束方程组（线性规划中一类特殊的约束条件）是否有解。 任意点对间的最短路径问题 问题：给定一个加权有向图 G，求任意点对 u,v间的最短路径。首先，类比两个 n阶方阵的乘法，我们介绍一个动态规划算法。第二个算法是Floyd-Warshall算法，也可用于计算有向图的传递闭包。第三个算法（Johnson 算法）利用“单源点的最短路径”问题的 Bellman-Ford算法和 Dijkstra算法，处理稀疏图时要好于前两个算法。 最大流问题 问题：给定一个有向图，每条边都赋予一个非
11、负整数（表示承载能力） ，规定一个源点和一个终点，求解从源点到终点的最大流。我们介绍了Ford-Fulkerson方法，该方法也可用来求解最大二部图匹配问题。 排序网络 排序网络是一个并行算法，用于快速排序（时间复杂度为 O(log2 n)） 。计算几何学 介绍三个平面几何问题的算法。第一个问题是：给定一个线段的集合，判定其中任何两条线段是否相交。第二个问题是：给定平面上 n个点，求解覆盖它们的最小凸集（Graham 算法和 Jarvis算法） 。第三个问题是：给定平面上 n个点，求所有可能两点间的最小距离（1985 年，Shamos 用分治法解决，时间复杂度为 O(nlog n)） 。 NP
12、完全性 定义了 NP-completeness，介绍了如何证明一个决策问题（decision problem）是 NP-hard的。最后介绍了几个经典的 NP-complete问题。课程目标：1. 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。2. 培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。3. 鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。参考书及课外读物：0M.H. Alsuwaiyel (2003) Algorithms Design Techniques and Anal
13、ysis. World Scientific Publishing and Publishing House of Electronics Industry1. S. Baase and A. V. Celder (2000), Computer Algorithm: Introduction to Design and Analysis (the third edition). Addison Wesley Longman2. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to Al
14、gorithms (the second edition). The MIT Press3. E. Horowitz and S. Sahni（1978）, Fundamentals of Computer Algorithms, Computer Science Press, Pitman Inc.4. C. A. Shaffer (1997), Data Structure and Algorithm Analysis. Prentice-Hall, Inc. 中译本：数据结构与算法分析 ，张铭、刘晓丹，电子工业出版社（1998 年）5. Sartaj Shani(1999), Data
15、Structures, Algorithms, and Applications in C+ .Pren_tice-Hall，Inc. Homepage: http:/ ，汪诗林，机械工业出版社（2000 年）.6. H. S. Wilf (1994), Algorithm and Complexity. Draft of the internet edition at http:/www.cis.upenn.edu/wilf7. DEKnuth 著，管纪文译， 计算机程序设计技巧 ，国防工业出版社，第一卷（1978） ，第二卷（1982）8. 卢开澄（2000） ， 计算机算法导引 ，清华大学出版社9. 邹海明,余祥宣编（1996）,计算机算法基础 ，华中理工大学出版社10. http:/
