搜索
【算法设计与分析】教学参考书：ThomasH.Cormen，CharlesE.Leiserson，RonaldL.Rivest，CliffordStein：算法导论（MIT第2版，比第一版增加了随机算法、线性规划）高教社影印本（标价68元），潘金贵等翻译了该书。现代计算机常用数据结构和算法（潘金贵等，南大出版社）是Cormen等3人书第一版的编译M.H.Alsuwaiyel（沙特人）：Algorithms:DesignTechniquesandAnalysis（电子工业出版社影印本，方世昌等翻译）Aho，Hopcroft，Ullman：TheDesignandAnalysisofComputerAlgorithms(1974版影印本，电力出版社，有中译本)Aho，Hopcroft，Ullman：数据结构与算法（1983年版影印本，清华出版社）ConcreteMathematics（具体数学）AFoundationforComputerScience(SecondEdition)RonaldL.Graham（AT&TBellLaboratories），DonaldE.Knuth（StanfordUniversity），OrenPatashnik（Stanford）R.C.Lee,S.S.Tseng,Y.T.Tsai：算法设计与分析导论（王卫东译，机械工业出版社，2007）AnanyLevitin：算法设计与分析基础（潘彦译，清华出版社，2007）卢开澄：组合数学算法与分析（上、下册）（清华出版社）王晓东：计算机算法设计与分析（电子工业出版社）引言算法设计与分析课程的主要讲授内容：1、在计算机应用中经常遇到的问题和求解的算法。2、设计算法的基本原理、技巧以及算法复杂性的分析（包括分治法、动态规划法、集合上的算法、随机算法等）。3、若干基本的计算模型（Turing机、递归函数等）。4、与NP-完全性概念相关的理论和算法。算法设计与分析课程的目的：使学员在非数值计算方法的层面上具备抽象描述、解决实际问题的能力，学会运用算法设计与分析的典型方法进行算法的设计，具备分析算法效率的能力。算法在CS中占有重要地位的一个体现——有超过1/3的Turing奖获奖者（22/57），其成果与算法有关。图灵奖于1966年开始设立，是ACM（美国计算机协会）在计算机科学技术领域中所授予的最高奖项。E.g.：1972，EdsgerW.Dijkstra（原在美Burroughs公司，2002年去世）：求最短路径的Dijkstra算法，PV操作，结构化程序设计，“goto有害”等。Dijkstra的一些名言：编程的艺术就是处理复杂性的艺术。优秀的程序员很清楚自己的能力是有限的，所以他对待编程任务的态度是完全谦卑的，特别是，他们会象逃避瘟疫那样逃避“聪明的技巧”。——1972年图灵奖演讲我们所使用的工具深刻地影响着我们的思考习惯，从而也影响了我们的思考能力。实际上，如果一个程序员先学了BASIC，那就很难教会他好的编程技术了：作为一个可能的程序员，他们的神经已经错乱了，而且无法康复。对编程语言的比喻：根本不可能用一把钝斧子削好铅笔，而换成十把钝斧子会把事情变成大灾难。简单是可靠的先决条件。计算机能不能思考？这个问题就好象‘潜水艇能不能游泳’一样。当年轻的科学家问他如何选择研究课题时，他回答：“只做你能做的事。”1974，DonaldE.Knuth（stanford）：多卷算法巨著（算法最早的奠基人之一），现代“算法”与“数据结构”名词及内涵的提出，KMP算法，LR(k)文法，Tex编辑器等。1976，MichaelO.Rabin（以色列）DanaS.Scott（英）师兄弟：（导师A.Church）非确定有穷自动机的提出、判定问题等。Rabin：计算复杂性概念的雏形、随机算法的思想奠定、寻找及判定素数算法，单向函数等。Scott:语义学等。1978，RobertW.Floyd（美）：算法（求最短路径的Floyd动态规划算法，Heap-sort算法等），编译及优化（优先文法等），程序正确性证明等。1980，C.AnthonyR.Hoare（英）：1983年ACM评出的1/4世纪中最有影响的25篇论文：Hoare与Dijkstra有两篇入选（其余人只有一篇）。算法的代表作：Quick-sort算法，程序设计（CASE、While语句等），数据通信等。1982，StevenA.Cook（加Toronto大学）：“NP-完全”概念的提出与理论的奠定，算法复杂性。1984，NiklausWirth（瑞士苏黎世高工）：“程序=算法+数据结构”，结构化程序设计创始人，“Pascal之父”,数据结构，ExtendedBNF等。1985，RichardM.Karp（UC-Berkeley）：计算机系、数学系、工业工程与运筹学系“三栖教授”，哈佛文学士、理学硕士、数学博士。分枝限界法的创始人（与Held），Rabin-Karp子串匹配算法，求网络最大流的Edmonds-Karp算法，NP-完全理论（Karp规约等），随机算法，并行算法等。1986，JohnE.Hopcroft(Cornell)RobertE.Tarjan（Princeton）：图论算法（深度优先、广度优先算法，连通性、平面图判定，etc.），各种数据结构Hopcroft：与Aho、Ullman合著经典算法书，与Ullman合著经典名著：形式语言与自动机。算法好坏的衡量尺度（渐进时间复杂性），2-3树，机器人研究等。Tarjan：D.E.Knuth的博士生，集合的Union-find算法，平摊分析，持久性数据结构及各种数据结构（e.g.动态树、”八字型”树，自调整结构）1993，JurisHartmanis(Cornell)&RichardE.Stearns(Albany)：计算复杂性理论的主要奠基人：系统化的理论体系及命名。Hartmanis：Hartmanis矩阵乘法，Hartmanis快速离散傅立叶变换Stearns：首先提出将上下文无关文法理论应用于编译器设计等。1995，ManuelBlum（UC-Berkeley，CMU）：计算复杂性理论（受M.O.Rabin到MIT演讲的启发），e.g.Blum测度等；复杂性理论应用（e.g.密码学、软件工程）。2000，AndrewYao（姚期智）：唯一华裔图灵奖获得者计算复杂性，量子计算，密码学（e.g.单向函数）、通信理论等。2002，RonaldL.Rivest，AdiShamir，LeonardM.Adelman：公共密钥算法（RSA算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制）.2007，EdmundClarke（美），AllenEmerson（美），JosephSifakis（法）1981年，分别提出了模型检测（ModelChecking）的最初概念，开发了一套用于判断硬件和软件设计的理论模型是否满足规范的方法，此外，当系统检测失败时，还能利用它确定代码中问题存在的位置。2010，LeslieG.Valiant（英）主要贡献之一是PAC模型（ProbablyApproximatelyCorrect，概率近似正确），该模型可解决信息分类的问题，可最大限度地降低泛化带来的错误，对于机器学习、人工智能（如自然语言处理、笔迹识别、机器视觉等）都产生了重要影响。Valiant的代数计算机论是对计算复杂性理论的关键贡献。它建立了一个理解框架，可高效地完成代数公式的求值运算，并提出了#P-completeness的概念。他在1979年提出的上下文无关分析算法，至今仍然是最快算法之一。此外，Valiant还为并行与分布式计算作出了重要的贡献，包括1990年提出的著名的BSP并行模型。算法好坏的衡量尺度最初，用所需要的计算时间来衡量一个算法的好坏，但不同的机器相互之间无法比较，故需要用独立于具体计算机的客观衡量标准。—问题的规模，基本运算，算法的计算量函数。问题的规模（大小，size）：一个或多个整数，作为输入数据量的测度。E.g.：a、数表的长度（数据项的个数），（问题：在一个数据表中寻找X）b、矩阵的最大维数（阶数）（问题：求两个实矩阵相乘的结果）输入规模通常用n来表示，也可有两个以上的参数，如c、图中的顶点数和边数（图论中的问题）基本运算：解决给定问题时占支配地位的运算（一般一种，偶尔≥2种）e.g.：a、在一个表中寻找数据元素x——x与表中的一个项进行比较b、两个实矩阵的乘法——实数的乘法（及加法）C=AB则cij=∑aikbkjc、将一个数表进行排序——表中的两个数据项进行比较通常情况下，讨论一个算法优劣时，我们只讨论基本运算的执行次数——因为它是占支配地位的，而其它的运算可以忽略不计。用输入规模的某个函数来表示算法的基本运算量：这个表示基本运算量的函数称为算法的时间复杂性（度），用T(n)（或T(n,m)等）来表示。E.g.：T(n)=5n，T(n)=3n*logn，T(n)=4n3，T(n)=2n，T(n,m)=2(n+m)等渐近时间复杂性：当输入规模趋于极限情形时（相当大）的时间复杂性表示时间渐进复杂性的三个记号1、T(n)=O(f(n))：若存在c0，和正整数n0≥1，2、使得当n≥n0时，总有T(n)≤c*f(n)。（给出了算法时间复杂度的上界，不可能比c*f(n)更大）e.g.T(n)=3n3+2n2，取c=5，n0=1，f(n)=n3，则当n≥n0(=1)时，有3n3+2n2≤5n3.∴T(n)=O(n3)3、T(n)=Ω(f(n))：若存在c0，和正整数n0≥1，使得4、当n≥n0时，存在无穷多个n，使得T(n)≥c*f(n)成立。（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小）e.g.T(n)=3n3+2n2，取c=3，n0=1，f(n)=n3，则当n≥n0(=1)时，有3n3+2n2≥3n3，∴T(n)=Ω(n3)5、T(n)=(f(n))：若存在c1,c20，和正整数n0≥1，6、使得当n≥n0时，总有T(n)≤c1*f(n)，7、且有无穷多个n，使得T(n)≥c2*f(n)成立，即：T(n)=O(f(n))与T(n)=Ω(f(n))都成立。（既给出了算法时间复杂度的上界，也给出了下界）e.g.T(n)=3n3+2n2，c1=5，取c2=3，n0=1，f(n)=n3，则当n≥n0(=1)时，有3n3+2n2≤5n3及3n3+2n2≥3n3（无穷多个），∴T(n)=(n3)多项式时间与指数时间设每秒可做某基本运算109次，n=60算法1算法2算法3算法4算法5算法6复杂度nn2n3n52n3n运算时6*10-8s3.6*10-6s2.16*10-4s0.013min.3.66世纪1.3*1013两个结论：世纪1多项式时间的算法互相之间虽有差距，一般可以接受。2指数量级时间的算法对于较大的n无实用价值。最坏情况时间复杂性：规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。e.g.：在一个顺序表中寻找数据元素x顺序查找：最坏情况为O(n)；二分查找：最坏情况为O(logn)。平均情况时间复杂性：规模为n的所有输入的算法时间复杂度的平均值（一般均假设每种输入情况以等概率出现）。e.g.：在一个顺序表中寻找数据元素x顺序查找：平均情况仍为O(n)；二分查找：平均情况仍为O(logn)。