算法设计与分析教学大纲.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《算法设计与分析教学大纲.pdf》由会员分享,可在线阅读,更多相关《算法设计与分析教学大纲.pdf(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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 AlgorithmsIntroduction to Algorithms(the sec
2、ond edition).The MIT Press,中文名算法导论(第二版)(影印版),高等教育出版社 电子教案:http:/10.20.20.10 先修课程:数据结构、离散数学、高等数学、概率论与数理统计 课程概要:简单对困难 为什么我们要研究算法和复杂性理论?本节课介绍了 Insertion-Sort 和Merge-Sort 两个算法,并比较了它们时间复杂度的优劣。函数的增长 刻划时间复杂度的常用函数以及它们增长速度的比较,用到一些数学分析(或高等数学)的知识。最后,我们分析了 Merge-Sort 算法的时间复杂度。求解递归式 介绍了求解递归式的三种方法,证明了 Master Theo
3、rem。证明技巧就是递归树方法:先考虑 n 恰好是 b 的次幂的情形;再考虑一般情形。Master Theorem 在以后的学习中经常用到,务必掌握。矩阵计算 矩阵是科学计算不可缺少的工具,矩阵计算理论可参考Golub和von Loan的名著 Matrix Computation。本节介绍了矩阵乘法的 Strassen 算法(用的是分治法),求解线性方程组的 LU 算法和 LUP 算法,矩阵求逆的算法。介绍了对称正定阵的许多有趣的性质。最后,证明了 Winograd 定理和Aho-Hopcroft-Ullman 定理,该定理说矩阵乘法和矩阵求逆的时间复杂度相等。这是非常有趣的一节,充满了技巧。
4、概率分析与随机算法 除了以最坏情况的时间消耗作为衡量一个算法优劣的标准,我们也可以用平均时间(相对于各种输入情况)消耗作为一个标准。如果一个算法在原有的输入数据之外,还在算法执行过程中加入随机性(因为真正理论意义下的随机数是不可能由计算机产生的,所以实际上用的是伪随机数),然后看算法输出结果的概率平均值。随机算法往往比确定性算法计算时间少,虽然它的准确率略微降低。Heapsort Heapsort 是一种比 Insertion-Sort 和 Merge-Sort 都有效的算法。Heap 有许多有趣的性质,是一个重要的数据结构。Quichsort 及其他 分析了 Quicksort,Radixs
5、ort 和 Bucketsort 的算法复杂度。动态规划 首先,以 Assembly Line Problem 和 Matrix-chain Multiplication 为例,给出动态规划算法。主要目的是直观地启发何时、如何使用动态规划算法。在介绍了动态规划算法的一般策略后,我们分析了求解最长公共子序列和最优二分搜索树的动态规划算法。另外还有Hidden Markov Model(HMM)的 Viterbi 算法,它在语音识别和切分/词性标注(自然语言处理)等有较好的应用。线性规划 介绍了线性规划及其单纯形算法。线性规划是最优化理论中很重要的一部分,有着广泛的应用背景。单纯形法已经相当成熟,
6、在线性规划的算法中实用性最强。也对近十年来发展的近似算法影响很大。贪心法 (以背包问题为例)介绍了贪心法与动态规划的关系以及使用贪心法必须满足的两个性质。介绍了 Huffman 编码的贪心算法。贪心法什么时候能取到最优界并无一般理论,但对于求最大 weighted matroid(拟阵理论是H.Whitney 于 1935 年提出的)我们有一个完美的结果贪心法可取到最优解。本节最后介绍了用贪心 matroid 方法解决 unit-time task scheduling 问题,很有趣。图算法初步 介绍了广度优先和深度优先的图搜索算法及其性质。接着介绍了深度优先搜索的两个应用:拓扑排序和如何找出
7、一个有向图的所有强连通分支。最小生成树 介绍了最小生成树的性质和 Kruskal 算法和 Prim 算法。多项式与快速 Fourier 变换 两个 n 次多项式相乘,用 FFT 可将时间复杂度从 Theta(n2)降至Theta(nlog n)。需要一些代数学的知识,蛮有趣的。数论算法 首先,概要性地介绍了初等数论的一些结果(譬如,Euler 定理和中国剩余定理)和它们在求解最大公约数(及其线性表示)、不定方程、不定方程组等方面的应用,给出了相应的算法。第二部分介绍了公钥密码系统加密和数字签名的基本想法和 RSA 算法。作为补充材料,最后介绍了素性检验和整数分解。顺序统计量 如果存在异常样本点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 教学大纲
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内