算法课件Introduction.docVIP

【算法设计与分析】教学参考书： Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein：算法导论 （MIT第2版，比第一版增加了随机算法、线性规划） 高教社影印本（标价68元），潘金贵等翻译了该书。 现代计算机常用数据结构和算法（潘金贵等，南大出版社） 是Cormen 等3人书第一版的编译 M. H. Alsuwaiyel（沙特人）： Algorithms: Design Techniques and Analysis （电子工业出版社影印本，方世昌等翻译） Aho，Hopcroft，Ullman： The Design and Analysis of Computer Algorithms (1974版影印本，电力出版社，有中译本) Aho，Hopcroft，Ullman： 数据结构与算法（1983年版影印本，清华出版社） Concrete Mathematics（具体数学） A Foundation for Computer Science (Second Edition) Ronald L. Graham（ATT Bell Laboratories）， Donald E. Knuth（Stanford University）， Oren Patashnik（Stanford） R.C.Lee, S.S.Tseng, Y.T.Tsai：算法设计与分析导论 （王卫东译，机械工业出版社，2007） Anany Levitin：算法设计与分析基础 （潘彦译，清华出版社，2007） 卢开澄： 组合数学算法与分析（上、下册）（清华出版社） 王晓东：计算机算法设计与分析（电子工业出版社） 引言 算法设计与分析课程的主要讲授内容： 1、在计算机应用中经常遇到的问题和求解的算法。 2、设计算法的基本原理、技巧以及算法复杂性的分析 （包括分治法、动态规划法、集合上的算法、随机算法等）。 3、若干基本的计算模型（Turing机、递归函数等）。 4、与NP-完全性概念相关的理论和算法。 算法设计与分析课程的目的： 使学员在非数值计算方法的层面上具备抽象描述、 解决实际问题的能力，学会运用算法设计与分析的典型 方法进行算法的设计，具备分析算法效率的能力。 算法在CS中占有重要地位的一个体现—— 有超过1/3的Turing奖获奖者（22/57）， 其成果与算法有关。 图灵奖于 1966年开始设立，是ACM（美国计算机协会） 在计算机科学技术领域中所授予的最高奖项。 E.g.： 1972，Edsger W.Dijkstra （原在美Burroughs公司，2002年去世）： 求最短路径的Dijkstra算法，PV操作，结构化程序设计， “goto有害”等。Dijkstra的一些名言： 编程的艺术就是处理复杂性的艺术。 优秀的程序员很清楚自己的能力是有限的，所以他对待编程任务的态度是完全谦卑的，特别是，他们会象逃避瘟疫那样逃避 “聪明的技巧”。 ——1972年图灵奖演讲 我们所使用的工具深刻地影响着我们的思考习惯，从而也影响了我们的思考能力。实际上，如果一个程序员先学了BASIC，那就很难教会他好的编程技术了：作为一个可能的程序员，他们的神经已经错乱了，而且无法康复。对编程语言的比喻：根本不可能用一把钝斧子削好铅笔，而换成十把钝斧子会把事情变成大灾难。 简单是可靠的先决条件。 计算机能不能思考？ 这个问题就好象‘潜水艇能不能游泳’一样。 当年轻的科学家问他如何选择研究课题时， 他回答：“只做你能做的事。” 1974，Donald E.Knuth（stanford）： 多卷算法巨著（算法最早的奠基人之一）， 现代“算法”与“数据结构”名词及内涵的提出， KMP算法，LR(k)文法，Tex编辑器等。 1976，Michael O.Rabin（以色列）( Dana S.Scott（英）师兄弟：（导师A.Church） 非确定有穷自动机的提出、判定问题等。 Rabin：计算复杂性概念的雏形、随机算法的思想奠定、 寻找及判定素数算法，单向函数等。 Scott: 语义学等。 1978，Robert W.Floyd（美）：算法 （求最短路径的Floyd动态规划算法，Heap-sort算法等）， 编译及优化（优先文法等），程序正确性证明等。 1980，C. Anthony R.Hoare（英）： 1983年ACM评出的1/4世纪中最有影响的25篇论文： Hoare与Dijkstra有两篇入选（其余