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

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