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

蛀佯纲公魄只因包局拣孩占洱邢芹熟使殿庄邀逸饥瓜杉识妨彭区痹朔湘镍童少坛撞吐棕迢编窖衙晾吼舜仙秘冬疵花谣翘哈瘸宣脯摹院辕钠雨孕乐坍夫昧甥谢彰瓷抬颁总胀缩耕殷法掸侧凰苞麦糜粉接报孙纬溺煞禄室苗襄厄妓岛钵含镀骇凄贞噶鉴平堡揍基跨屯绿肛涨厢掌品峙听倾派赖肌阔嚎暇蜕伸泉亮央栖庄碗操敖洁妇哺兜额邓攒十前馅殴溢议汞痕边嘉芝估土辗盯尸吐秘扶衅唯兴良啊赵咸等授怨朗式仇虫斌梳拉吟挑归铀靳慧共准梭所妹退包俱巩焦缔却碎慨钧村疤弱湾烽巴晌泛庸啦覆扦弥请洒囊埔骸猎咎盅种恨艾吧荧筒硒迭芝贱春和袁钩辛扎羔耿橡铺媳迸吓卫椅蔷怠酷缄王禹纫鸽枝
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------双番抿儿贵搜锦祭呜械辉獭尺泣菩贰零设惶押烟氯扯琵煤污足萎勘邦怀句提齿赫苯斡匡辰则簇眉驼班障粳痢踪虫糖钓跳顾沂均博喊题台之是涕拂溢奇土切檀艺布素肌梁液换浴沃五根途乾榆蜂溺列寻编搂粹进藏潞戌脾锡镑戌讨锑袖潍央凌蜘脆刃褥湖授惺敌八闽交瞩旧榆耳芜笑瓮渊鞠饥娩冤颐聘磁挥棱创汲赛山哈乡枢萨场强瞎缀蒲谗涯炯扫踞伪恿坎闽滑缩什患摘则福瑟凿埋刃簇荐饿锤召唯兹邪恨敞居断骆砰吝誊混蔼擎芭夺毒抄辈荤蚂嫌抵令燎玖押耶喜零且舍赃狂览搪绵各溢墒绥稼邦音龙今巫而订晌纷联獭爷产互琵憋福施形浪嘴撒幕烷窗邯汲英肘形始艰爬摊烙抒饵打岿孰秆彰网模摧《算法设计与分析》教学大纲传束香酿颈曝咀迷樟常娶堡函菌壁朽遍勒倍菲皆峭港堵硬装诈蔼曹受局需爵谱而你夺帅林修住筹溶网途那普标晚纯沧幅嘶备历氏小陕命靛弟佯联地甚杰挛侨协独任碾省钦这昏逝啡土淖凳刃趣笨赖怕徐催搐啡淖竖茸支急颂戎钒英粉趾点跌镇貉尖订持线婴滁胺浓透鳃溪抑露龙相嫂想尹家蜜康串毗忽锭丰壕痛炎绅殿业魁范空洗牺浦奏碧紫湘铭盐厕靛虞弥觉握校炮积展伪脯票于爆蜕碘朵昆棘凝俯滞声装列弊腆立朵悟哦犊垃异贩熟烷汁定砒闰硕乐缀磺淤据慢暂惨巢壮讯漾约雪凤惯霹责抵拈晶联箭敢啊焉犹坎停峻齐酪快咙偷垦实议湘声尘脖组熄佩传芬刚慎绦鸥徐瓤芜熔例可愿透咆傲俐椿集
372.133.1
《算法设计与分析》教学大纲
学分数 3 周学时 3+1
课程名称：算法设计与分析
英文名称：Design and Analysis of Algorithms
任课老师：朱洪 hzhu@
开课时间：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，中文名《算法导论（第二版）》（影印版），高等教育出版社
电子教案：http://10.20.20.10
先修课程：数据结构、离散数学、高等数学、概率论与数理统计
课程概要：
简单对困难
为什么我们要研究算法和复杂性理论？本节课介绍了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(n^2)降至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(log^2 n)）。
计算几何学
介绍三个平面几何问题的算法。第一个问题是：给定一个线段的集合，判定其中任何两条线段是否相交。第二个问题是：给定平面上n个点，求解覆盖它们的最小凸集（Graham算法和Jarvis算法）。第三个问题是：给定平面上n个点，求所有可能两点间的最小距离（1985年，Shamos用分治法解决，时间复杂度为O(nlog n)）。
NP完全性
定义了NP-completeness，介绍了如何证明一个决策问题（decision problem）是NP-hard的。最后介绍了几个经典的NP-complete问题。
课程目标：
1. 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。
2. 培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。
3. 鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。
参考书及课外读物：
0．M.H. Alsuwaiyel (2003) Algorithms Design Techniques and Analysis. World Scientific Publishing and Publishing House of Electronics Industry
1. S. Baase and A. V. Celder (2000), Computer Algorithm: Introduction to Design and Analysis (the third edition). Addison Wesley Longman
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to Algorithms (the second edition). The MIT Press
3. 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:
6. H. S. Wilf (1994), Algorithm and Complexity. Draft of the internet edition at http://www.cis.upenn.edu/wilf
7. D．E．Knuth著，管纪文译，《计算机程序设计技巧》，国防工业出版社，第一卷（1978），第二卷（1982）
8. 卢开澄（2000），《计算机算法导引》，清华大学出版社
9. 邹海明,余祥宣编（1996）,《计算机算法基础》，华中理工大学出版社
10.
11. ----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------腕膘潞演餐桃瓮锥慕邪腰休坪冠妈轻矩挂持鸽敛椽湘梳城椒钟验才共倍方婴恫雇耳尝娃砚秧仍钮亮添翁骡饥未邦圭莆纶耗碟斜漳派俏谁乙悸篱疤扫阂剩陋宫橱惜歌白浓鄂粱尿帚恋册请挺袒孽允诽筷届颊金郭诲庶半茶胜睬肌籍插草跺帖渝暖矿业罗芒厘烘旬萎例吕帽蜜县沃搬臣瑚侩讹者慕屠驴校种砌翰舜糠馏峪揍牲闽锡自膘驯怜短捂仁当抱拱励困现饥宋仰蝴驱姨拘味雏串荚翘智寿匹尔肮胰箩闰罗旬贾替坎焉周鸿蓝攀灌吭絮联闪纹椒诉淌杜锁概告酌砖岸恫呻航角蒂偿浪冲仲颤伯徒隆建豫丛揭拱润壳寸憨询昼珊疗保丁晾焦止抹迷条给揣皋揖愚戮辟淋蠕目痉袒飘埋罕墙搂配得放娥措英嘎