算法分析与设计1-数据结构基础.ppt

《算法分析与设计1-数据结构基础.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计1-数据结构基础.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析课程名称：DesignandAnalysisofAlgorithms主讲人：段友祥主讲人：段友祥石油大学计算机与通信工程学院石油大学计算机与通信工程学院引言计算机科学与技术学科的研究内容计算机科学与技术学科的研究内容简单说，计算机简单说，计算机学科学科是研究机器进行信息表示和信息处理的是研究机器进行信息表示和信息处理的科学。科学。信息表示：信息表示：（1）数字化）数字化:（2）可视化）可视化:（3）效率）效率信息处理：信息处理：（1）方法）方法（2）效率）效率想想看：是不是计算机所有想想看：是不是计算机所有的硬件和软件技术都属于这的硬件和软件技术都属于这两个范畴？两

2、个范畴？引言算法在计算机科学中的地位算法在计算机科学中的地位（1）算法是计算机科学基础的重要主题）算法是计算机科学基础的重要主题70年代后，算法作为计算机科学的核心推动了计算机年代后，算法作为计算机科学的核心推动了计算机科学技术的飞速发展科学技术的飞速发展70年代前，计算机科学基础的主题没有被清楚地认清。年代前，计算机科学基础的主题没有被清楚地认清。70年代，年代，Knuth出版了出版了TheArtofComputerProgramming(三卷）三卷）,以各种算法研究为主线，确以各种算法研究为主线，确立了算法为计算机科学基础的重要主题，立了算法为计算机科学基础的重要主题，1974年获得图年获

3、得图灵奖。灵奖。引言算法在计算机科学中的地位算法在计算机科学中的地位（2）计算机科学的体系）计算机科学的体系解决一个计算问题的过程：解决一个计算问题的过程：可计算否可计算否能行可计算否能行可计算否算法设计与分析算法设计与分析用计用计算机语言实现算法算机语言实现算法软件系统软件系统可计算理论可计算理论:计算模型计算模型可计算问题可计算问题/不可计算问题不可计算问题计算模型的等价性计算模型的等价性-图灵图灵/Church命题命题什么是计算？计算机科学的本质：什么是计算？计算机科学的本质：直观地看，计算一般是指运用事先规定的规则，直观地看，计算一般是指运用事先规定的规则，将一组数值变换为另一将一组数

4、值变换为另一(所需的所需的)数值的过程。数值的过程。什么能被自动地有效执行。什么能被自动地有效执行。引言算法在计算机科学中的地位算法在计算机科学中的地位（2）计算机科学的体系）计算机科学的体系计算复杂性理论（能行否）计算复杂性理论（能行否）在给定的计算模型下研究问题的复杂性在给定的计算模型下研究问题的复杂性上界上界下界下界平均平均固有复杂性固有复杂性复杂性问题的非类复杂性问题的非类:P=NP?抽象复杂性研究抽象复杂性研究算法设计和分析算法设计和分析可计算问题的算法的设计与分析可计算问题的算法的设计与分析设计算法的理论、方法和技术设计算法的理论、方法和技术分析算法的理论、方法和技术分析算法的理论

5、、方法和技术引言算法在计算机科学中的地位算法在计算机科学中的地位（3）算法设计与分析的意义）算法设计与分析的意义计算机各领域的核心计算机各领域的核心计算机工程特别是计算机软件工程的基础计算机工程特别是计算机软件工程的基础“一个受过良好的计算机科学知识训练的人知道如何处理一个受过良好的计算机科学知识训练的人知道如何处理算法，即构造算法、操纵算法、理解算法和分析算法。算法的算法，即构造算法、操纵算法、理解算法和分析算法。算法的知识远不是为了编写好的计算程序，它是一种具有一般意义的知识远不是为了编写好的计算程序，它是一种具有一般意义的智能工具，必定有助于对其他学科的理解，不论化学、语言学智能工具，必

6、定有助于对其他学科的理解，不论化学、语言学或者是音乐等或者是音乐等”D.E.Knuth(美国著名计算机科学家美国著名计算机科学家)“算法不仅是计算机学科的一个分支，它更是计算机科学算法不仅是计算机学科的一个分支，它更是计算机科学的核心，而且可以毫不夸张地说，它和绝大多数科学、商业和的核心，而且可以毫不夸张地说，它和绝大多数科学、商业和技术都是相关的。技术都是相关的。”算法学算法学计算机的灵魂计算机的灵魂DavidHarel引言计算机离不开软件，软件简单说就是程序，而程序的核计算机离不开软件，软件简单说就是程序，而程序的核心是算法。心是算法。什么是算法？什么是算法？什么是程序？什么是程序？它们之

7、间的关系？它们之间的关系？算法问题是计算机科学研究的核心问题之一！算法问题是计算机科学研究的核心问题之一！很多科学家在算法及其相关领域取得了创造性的成果很多科学家在算法及其相关领域取得了创造性的成果图灵奖（从图灵奖（从1966年开始已经有年开始已经有50多位科学家获得了这一多位科学家获得了这一殊荣。其中有殊荣。其中有1/3的获奖人是因为在算法和数据结构及其相关的获奖人是因为在算法和数据结构及其相关领域做出了杰出贡献而获奖的）领域做出了杰出贡献而获奖的）了解一下这些了解一下这些“牛牛”人，看看他们的经历和突出成人，看看他们的经历和突出成绩：绩：1930，5，112002，8，6。荷兰计算机科学家

8、，毕业就职于荷兰荷兰计算机科学家，毕业就职于荷兰Leiden大学，早大学，早年钻研物理及数学，而后转为计算学。在年钻研物理及数学，而后转为计算学。在1972年获得年获得图灵奖，图灵奖，之后，他还获得过之后，他还获得过1974年年AFIPSHarryGoodeMemorialAward、1989年年ACMSIGCSE计算计算机科学教育教学杰出贡献奖、以及机科学教育教学杰出贡献奖、以及2002年年ACMPODC最具影响力论文奖。最具影响力论文奖。1972年，年，EdsgerW.Dijkstra因在编程语言方面的出众表现因在编程语言方面的出众表现而获奖。而获奖。这个这个Dijkstra，就是那个提出

9、，就是那个提出“goto有害论有害论”的的Dijkstra，就是那个提出信，就是那个提出信号量和号量和PV原语，解决了有趣的原语，解决了有趣的“哲学家聚餐哲学家聚餐”问题的问题的Dijkstra，那个，那个Dijkstra最短路径算法的创造者，第一个最短路径算法的创造者，第一个Algol60编译器的设计者和实现者，编译器的设计者和实现者，THE操作系统的设计者和开发者，那个与操作系统的设计者和开发者，那个与D.E.Knuth并称为我们这个时并称为我们这个时代最伟大的计算机科学家的人。代最伟大的计算机科学家的人。晚年疯狂的迷恋晚年疯狂的迷恋C+EdsgerDijkstra经典言论：经典言论：1.

10、编程的艺术就是处理复杂性的艺术。编程的艺术就是处理复杂性的艺术。2.优秀的程序员很清楚自己的能力是有限的，所以他对待编程任务的态优秀的程序员很清楚自己的能力是有限的，所以他对待编程任务的态度是完全谦卑的，特别是，他们会象逃避瘟疫那样逃避度是完全谦卑的，特别是，他们会象逃避瘟疫那样逃避“聪明的技巧聪明的技巧”。1972年图灵奖演讲。年图灵奖演讲。3.计算机科学是应用数学最难的一个分支，所以如果你是一个蹩脚的数计算机科学是应用数学最难的一个分支，所以如果你是一个蹩脚的数学家，最好留在原地，继续当你的数学家。学家，最好留在原地，继续当你的数学家。4.我们所使用的工具深刻地影响我们的思考习惯，从而也影

11、响了我们的我们所使用的工具深刻地影响我们的思考习惯，从而也影响了我们的思考能力。思考能力。5.实际上如果一个程序员先学了实际上如果一个程序员先学了BASIC，那就很难教会他好的编程技术，那就很难教会他好的编程技术了：作为一个可能的程序员，他们的神经已经错乱了，而且无法康复。了：作为一个可能的程序员，他们的神经已经错乱了，而且无法康复。6.就语言的使用问题：根本不可能用一把钝斧子削好铅笔，而换成十把就语言的使用问题：根本不可能用一把钝斧子削好铅笔，而换成十把钝斧子会使事情变成大灾难。钝斧子会使事情变成大灾难。7.简单是可靠的先决条件。简单是可靠的先决条件。Dijkstra在在1968年发表的短文

12、：年发表的短文：GoToStatementConsideredHarmful1938年年12月月7日，日，DonaldE.Knuth出生于美国威斯康出生于美国威斯康星州密尔沃基市。让人眩目的履历：星州密尔沃基市。让人眩目的履历：1974年，年，DonaldE.Knuth因在算法分析和编程语言设计方面因在算法分析和编程语言设计方面的突出贡献设计和完成的突出贡献设计和完成TEX(一种创新的具有很高排版质量的一种创新的具有很高排版质量的文档制作工具文档制作工具)而被授予图灵奖而被授予图灵奖。1956年进入俄亥俄州克利夫兰的凯斯理工学院（现并年进入俄亥俄州克利夫兰的凯斯理工学院（现并入凯斯西储大学），

13、学习入凯斯西储大学），学习物理物理。1957年大学一年级暑假在学校打工，接触到当时很先年大学一年级暑假在学校打工，接触到当时很先进的进的IBM650计算机，对其产生浓厚的兴趣。计算机，对其产生浓厚的兴趣。1958年改学年改学数学数学，并从此与计算机结缘。，并从此与计算机结缘。1960年毕业，因为成绩过于出色，校方打破惯例，年毕业，因为成绩过于出色，校方打破惯例，Knuth被同时授予学士和硕士学位。随后进入加州理被同时授予学士和硕士学位。随后进入加州理工学院数学系。工学院数学系。1963年取得博士学位，并留校任助理教授。年取得博士学位，并留校任助理教授。1964-1967年，兼任美国计算机协会刊

14、物年，兼任美国计算机协会刊物程序设计语言程序设计语言编辑。编辑。1966年升为副教授。年升为副教授。1968年任教于斯坦福大学计算机科学系，正教授。同年，开始撰写著名的年任教于斯坦福大学计算机科学系，正教授。同年，开始撰写著名的计算机程序设计艺术计算机程序设计艺术一书。一书。1968年年计算机程序设计艺术计算机程序设计艺术第一卷第一卷基本算法基本算法出版。出版。1969年，第二卷年，第二卷半数字化算法半数字化算法出版。出版。1971年获首届美国计算机协会格蕾丝年获首届美国计算机协会格蕾丝赫柏奖。赫柏奖。1973年，第三卷年，第三卷排序与搜索排序与搜索出版。同年还出版了第一卷的第二版。出版。同年

15、还出版了第一卷的第二版。1974年，荣获图灵奖，是历史上最年轻的获奖者。年，荣获图灵奖，是历史上最年轻的获奖者。1975年当选为美国国家科学院院士。年当选为美国国家科学院院士。1976年出版第二卷第二版时采用了计算机排版技术。但是，当时的计算机年出版第二卷第二版时采用了计算机排版技术。但是，当时的计算机排版与活字排版效果相差甚远，而且前后两卷的字体、版式和文本格式等排版与活字排版效果相差甚远，而且前后两卷的字体、版式和文本格式等都不一致。非常失望的都不一致。非常失望的Knuth暂停了第二卷第二版的出版，决心自己设暂停了第二卷第二版的出版，决心自己设计一个比活字排版更加优美和适用的排版软件，这就

16、是后来的计一个比活字排版更加优美和适用的排版软件，这就是后来的TeX。1977年年5月开始构造后来被称为月开始构造后来被称为TeX的文字处理系统，他研究了古今的排的文字处理系统，他研究了古今的排版技术，把其中最优越的部分引入版技术，把其中最优越的部分引入TeX中，连中，连TeX中的字体中的字体（METAFONT）全部都是他自行设计的。）全部都是他自行设计的。同年，访问中国三周，行前姚储枫给他起了个中文名字：高德纳。（姚储同年，访问中国三周，行前姚储枫给他起了个中文名字：高德纳。（姚储枫，姚期智的夫人枫，姚期智的夫人)1978-1979年研究计算机排版软件，并荣获美国总统卡特授予的科学金奖年研究

17、计算机排版软件，并荣获美国总统卡特授予的科学金奖。1980年获国际电子电气工程师协会计算机学会麦可道尔奖。同年，成为英年获国际电子电气工程师协会计算机学会麦可道尔奖。同年，成为英国计算机学会会员。国计算机学会会员。1981年当选为美国工程院院士。年当选为美国工程院院士。1982年使用自己设计的年使用自己设计的TeX软件和字体，软件和字体，Knuth如愿出版了如愿出版了计算机程序计算机程序设计艺术设计艺术的第二卷第二版。之后，的第二卷第二版。之后，Knuth还不遗余力地改进还不遗余力地改进TeX，并在，并在TeX的稳定性上下了很大功夫。在基本式样没有改变的情况下，的稳定性上下了很大功夫。在基本式

18、样没有改变的情况下，TeX第第3版版又追加了很多功能。又追加了很多功能。9月，公布了月，公布了DVI驱动程序。同年，成为国际电子电驱动程序。同年，成为国际电子电气工程师协会荣誉会员，并获计算机先锋奖。气工程师协会荣誉会员，并获计算机先锋奖。1984年，艾迪生年，艾迪生-韦斯利公司出版韦斯利公司出版Knuth教授的教授的TheTeXbook，该书成，该书成为最权威的为最权威的TeX参考书。参考书。1985年，将年，将TeX的默认字体由美国现代改为计算机现代的默认字体由美国现代改为计算机现代。1986年荣获美国数学学会的斯蒂尔奖。年荣获美国数学学会的斯蒂尔奖。1987年获纽约科学研究会奖。年获纽约

19、科学研究会奖。1988年获富兰克林奖。年获富兰克林奖。1989年，因其对软件理论的贡献获年，因其对软件理论的贡献获J.D.Warnier奖。奖。1990年，斯坦福大学授予他计算机科学艺术教授的称号。年，斯坦福大学授予他计算机科学艺术教授的称号。1991年，年，3:16圣经文本阐释圣经文本阐释一书出版，他试图用分层随机抽样的方法一书出版，他试图用分层随机抽样的方法对圣经进行分析。对圣经进行分析。1992年退休，但还是斯坦福大学和牛津大学的客座教授。他这么早退休的原年退休，但还是斯坦福大学和牛津大学的客座教授。他这么早退休的原因，就是因为研究开发因，就是因为研究开发TeX系统延误了编写出版系统延误

20、了编写出版计算机程序设计技巧计算机程序设计技巧这这部书，他估计还要花部书，他估计还要花20年来完成。目前此书前三卷已出版，第四卷正在出版。年来完成。目前此书前三卷已出版，第四卷正在出版。预计要出到第七卷。预计要出到第七卷。1993年宣布不再对年宣布不再对TeX和和METAFONT进行更新。进行更新。1994年获瑞典皇家科学院克努特奖。年获瑞典皇家科学院克努特奖。1995年获国际电子电气工程师协会的纽曼奖和以色列的科学与艺术哈维奖。年获国际电子电气工程师协会的纽曼奖和以色列的科学与艺术哈维奖。1996年年11月，由于发明先进的排版技术荣获京都先进技术奖（日本最高终身月，由于发明先进的排版技术荣获

21、京都先进技术奖（日本最高终身成就奖，奖金约成就奖，奖金约46万美元，被称为日本的诺贝尔奖）。万美元，被称为日本的诺贝尔奖）。1997年对年对计算机程序设计技巧计算机程序设计技巧前三卷作了修订。前三卷作了修订。2001年国际天文学联合会把两年前发现的第年国际天文学联合会把两年前发现的第21656号小行星命名为号小行星命名为“Knuth”。2003年当选英国皇家学会的外籍院士。年当选英国皇家学会的外籍院士。2004年年计算机程序设计技巧计算机程序设计技巧前三卷再版发行。前三卷再版发行。2005年年11月月19日，从瑞士联邦苏黎士高等理工学院校长手中接过荣誉博士证日，从瑞士联邦苏黎士高等理工学院校长

22、手中接过荣誉博士证书。书。现在，正在编写现在，正在编写计算机程序设计技巧计算机程序设计技巧其余几卷。其余几卷。Knuth教授是法国、挪威和德国科学院的外籍院士；还是牛津大学等十几所教授是法国、挪威和德国科学院的外籍院士；还是牛津大学等十几所大学的荣誉博士。大学的荣誉博士。1、著作、著作计算机程序设计艺术计算机程序设计艺术是与牛顿的是与牛顿的自然哲学的数学原理自然哲学的数学原理等书一起，被评为等书一起，被评为“世界历史上最伟大的十种科学著作世界历史上最伟大的十种科学著作”之之一。一。突出贡献突出贡献:比尔比尔.盖茨曾说，盖茨曾说，“如果你认为你是一名真正优秀的程序员，就去读第如果你认为你是一名真

23、正优秀的程序员，就去读第一卷，确定可以解决其中所有的问题。一卷，确定可以解决其中所有的问题。”“如果你能读懂整套书的话，请给我发一份你的简历。如果你能读懂整套书的话，请给我发一份你的简历。”依依Knuth本人所讲，本人所讲，计算机程序设计艺术计算机程序设计艺术是他毕生最重要的事业，是他毕生最重要的事业，其目的是其目的是“组织和总结所知道的计算机方法的相关知识，并打下坚实的数学、组织和总结所知道的计算机方法的相关知识，并打下坚实的数学、历史基础历史基础”。Knuth撰写的前三卷被翻译成多种语言，到撰写的前三卷被翻译成多种语言，到1976年为止，已卖年为止，已卖出超过一百万册。他目前正全神贯注地编

24、写第四卷，他期望第四卷的篇幅约出超过一百万册。他目前正全神贯注地编写第四卷，他期望第四卷的篇幅约为为2000页，并分为三个独立的章节。为了完成丛书的其余部分，页，并分为三个独立的章节。为了完成丛书的其余部分，Knuth现在现在进入了一种引退的状态，全身心地投入这项工作。进入了一种引退的状态，全身心地投入这项工作。Knuth说，一般说来，他说，一般说来，他更喜欢在一段时间内集中精神完成一项工作，正像他自己在书中提出的：按更喜欢在一段时间内集中精神完成一项工作，正像他自己在书中提出的：按“一批一批”的模式。的模式。2、编译程序、编译程序编译程序能够实现高级语言和二进制机器语言之间的翻译。编译程序能

25、够实现高级语言和二进制机器语言之间的翻译。二十世纪六十年代初期，二十世纪六十年代初期，Knuth教授致力于这方面的研究，虽教授致力于这方面的研究，虽然现代的软件已经可以使其变的简单一些，但编写编译程序仍然现代的软件已经可以使其变的简单一些，但编写编译程序仍被认为是一项极为困难的工作。被认为是一项极为困难的工作。Knuth教授在这方面最著名的教授在这方面最著名的成就是成就是LR(k)分析分析的研究，那是一个能使确定一串字符文法规则的研究，那是一个能使确定一串字符文法规则的过程更加顺畅的值得注目的方法。的过程更加顺畅的值得注目的方法。突出贡献突出贡献:3、属性文法、属性文法在编译程序的工作之后，在

26、编译程序的工作之后，Knuth教授走上了形式上定义程教授走上了形式上定义程序语言意义、语义的研究道路。他建立起一个更加经济的方法序语言意义、语义的研究道路。他建立起一个更加经济的方法去通译联合规则，他把这种方法称作去通译联合规则，他把这种方法称作“属性规则属性规则”。该方法创。该方法创立的同时，计算机科学的子域被称作立的同时，计算机科学的子域被称作“属性文法属性文法”。4、算法、算法也许也许Knuth教授在计算机科学领域最原创的贡献就是他对教授在计算机科学领域最原创的贡献就是他对于算法的分析。算法是编写一个程序，使之能去完成一项任务于算法的分析。算法是编写一个程序，使之能去完成一项任务的基础，

27、例如搜索或分类等。在加利福尼亚理工学院时，的基础，例如搜索或分类等。在加利福尼亚理工学院时，Knuth教授在一个毕业生的协作下，开发了用来探究数学公理教授在一个毕业生的协作下，开发了用来探究数学公理推论的推论的Knuth-Bendix算法。算法。1968年，年，Knuth教授在斯坦福，和教授在斯坦福，和他的一个学生开发了他的一个学生开发了Knuth-Morris-Pratt算法，该法则使计算机算法，该法则使计算机在文章中搜索一串字符的过程更加连贯。他所著的在文章中搜索一串字符的过程更加连贯。他所著的计算机程计算机程序设计艺术序设计艺术是一个详尽的算法实践和科学的概观。是一个详尽的算法实践和科学

28、的概观。突出贡献突出贡献:5、数字化排版、数字化排版“数学书籍和杂志已经不像从前那样漂亮了。数学书籍和杂志已经不像从前那样漂亮了。”Knuth教授教授在一篇早期关于数学排版的文章中这样写道。由于对计算机排在一篇早期关于数学排版的文章中这样写道。由于对计算机排版的校样的低质量感到无法忍受，版的校样的低质量感到无法忍受，Knuth教授从他史诗性的七教授从他史诗性的七卷集巨著的编写过程中拿出了十年时间，来开发一个高质量的卷集巨著的编写过程中拿出了十年时间，来开发一个高质量的计算机排版系统。其间，计算机排版系统。其间，Knuth开发了两个用于文件排版和字开发了两个用于文件排版和字体生成的软件系统，这两

29、个系统现在已被世界大多数出版社运体生成的软件系统，这两个系统现在已被世界大多数出版社运用。它们分别是用。它们分别是TeX，用于出版业的科学排版，和，用于出版业的科学排版，和“优美文章优美文章”的产品：的产品：METAFONT，一个字体生成程序。，一个字体生成程序。突出贡献突出贡献:6、结构化文件和文章性程式语言、结构化文件和文章性程式语言Knuth教授的排版研究，引领他发明了文件构造的两种语教授的排版研究，引领他发明了文件构造的两种语言和一个方法论，叫作言和一个方法论，叫作“文章性程式语言文章性程式语言”。语言分别是。语言分别是WEB和和CWEB，它们促进了程序编写向，它们促进了程序编写向“文

30、学作品，是用来阅读的文学作品，是用来阅读的”这个方向发展。这两种语言的结合，一种是文件格式化，另这个方向发展。这两种语言的结合，一种是文件格式化，另一种是程序设计，这就使程序员能够同时创建两个不同的系统一种是程序设计，这就使程序员能够同时创建两个不同的系统程序，一个面向人，另一个面向机器。当一条过程清楚地描述程序，一个面向人，另一个面向机器。当一条过程清楚地描述程序并促进其维护时，另外一个则产生一个机器可执行的程序。程序并促进其维护时，另外一个则产生一个机器可执行的程序。这些工作就是这些工作就是Knuth教授在实现其使程序设计为读者易懂、甚教授在实现其使程序设计为读者易懂、甚至感觉漂亮的目标的

31、过程中，在计算机领域里所做出的巨大贡至感觉漂亮的目标的过程中，在计算机领域里所做出的巨大贡献。献。突出贡献突出贡献:M.O.Rabin（以色列），以色列），D.S.Scott（英国），英国），1976年。发表年。发表著名的计算复杂性方面的论文著名的计算复杂性方面的论文“FiniteautomataandTheirDecisionproblem”“在该研究论文中，提出了非确定性在该研究论文中，提出了非确定性(自动机自动机)机器的观点。机器的观点。在计算理论科学研究中，非确定性被证明是一个非常重要的在计算理论科学研究中，非确定性被证明是一个非常重要的概念。概念。Scott和和Rabin的这篇经典文

32、章成为这个领域后续研究的这篇经典文章成为这个领域后续研究的基石。的基石。”M.O.Rabin今年今年10月份受邀到清华讲学月份受邀到清华讲学DanaStewartScott(1932)MichaelOserRabin(1931)RobertWFloyd（美国）（美国）1978年。在算法分析和程序设计正年。在算法分析和程序设计正确性证明领域有开创性工作。（确性证明领域有开创性工作。（弗洛伊德算法弗洛伊德算法）RobertW.Floyd(06/08/193609/25/2001)“授授予予RobertW.Floyd图图灵灵奖奖以以表表彰彰其其在高效和可靠性软件设计方法学在高效和可靠性软件设计方法学

33、领域的显著影响；表彰其在下列计算领域的显著影响；表彰其在下列计算机科学重要分支的奠基性的贡献：机科学重要分支的奠基性的贡献：(词词法法)分析理论，编程语言语义，自动程分析理论，编程语言语义，自动程序验证，自动程序综合生成和算法分序验证，自动程序综合生成和算法分析。析。”C.A.R.Hoare（英国），英国），1980年。在程序设计和算法方面做年。在程序设计和算法方面做出突出贡献，发明出突出贡献，发明QUICKSORT算法。算法。C.AntonyR.Hoare(1/11/1934)Hoare对程序设计语言的主要贡献为：对程序设计语言的主要贡献为：HoareLogic,快速排序算法快速排序算法(Q

34、uicksort)和和CSP(CommunicationSequentialProcesses)S.A.Cook（加拿大），加拿大），1982年。复杂性理论和年。复杂性理论和NP完全问题。完全问题。“ThecomplexityofTheoremProvingProcedures”（COOK定理定理）StephenArthurCook(1939)“授予授予StephenA.Cook图灵奖以表彰其图灵奖以表彰其对我们深刻理解计算复杂性的开创性的对我们深刻理解计算复杂性的开创性的贡献。贡献。Cook的开创性文章，的开创性文章，1971年发表年发表在在ACMSIGACTSymposiumontheTh

35、eoryofComputing,“TheComplexityofTheoremProvingProcedures”,揭开了揭开了计算复杂性中计算复杂性中NP完全性的研究。在此基完全性的研究。在此基础上的关于础上的关于NP完全性问题的本质和边界完全性问题的本质和边界的研究与探讨的研究与探讨成为过去十年来计算机科成为过去十年来计算机科学最活跃和重要的研究领域之一。学最活跃和重要的研究领域之一。”N.Wirth（瑞士），瑞士），1984年，年，因开发了因开发了EULER、ALGOL-W、MODULA和和PASCAL一系列崭新的计算语言而获奖。一系列崭新的计算语言而获奖。NiklausWirth(02

36、/15/1934)“授予授予NiklausWirth图灵奖以表彰其图灵奖以表彰其开开发了一系列的计算机程序语言，发了一系列的计算机程序语言，EULER,ALGOL-W,MODULEA和和PASCAL。PASCAL语言被用在计算机程序语言教学语言被用在计算机程序语言教学上具有重要的意义，并为将来的计算机语上具有重要的意义，并为将来的计算机语言，系统和结构设计提供了一个基础。言，系统和结构设计提供了一个基础。”NiklausWirth：算法：算法+数据结构数据结构=程序程序爱因斯坦：爱因斯坦：E=MC2R.M.Karp（美国），美国），1985年。组合优化算法、网络流有效年。组合优化算法、网络流有

37、效算法、随机算法和算法、随机算法和NP完全性等。发表论文完全性等。发表论文“Reducibilityamongcombinatorialproblems”2008年曾到国内讲学，年曾到国内讲学，今年今年10月份受邀到清华讲学。月份受邀到清华讲学。“授授予予RichardM.Karp图图灵灵奖奖以以表表彰彰其在其在算法理论方面的持续性的算法理论方面的持续性的贡献，其中包括在网络流贡献，其中包括在网络流(networkflow)和其他组合优化问题领域的高效和其他组合优化问题领域的高效算法的研究，在多项式时间可计算性算法的研究，在多项式时间可计算性算法方面，特别是对算法方面，特别是对NP完全理论的贡

38、完全理论的贡献。献。Karp引入了现已经成为标准方法引入了现已经成为标准方法的用来证明一个问题是否是属于的用来证明一个问题是否是属于NP完完全。全。Karp的方法使得许多理论和实际的方法使得许多理论和实际问题被确认为从可计算性角度而言是问题被确认为从可计算性角度而言是复杂的或困难的。复杂的或困难的。”RichardManningKarp,(1935-).J.E.Hopcroft和他的学生和他的学生R.E.Tarjan（美国），美国），1986年。发明年。发明了一种非常重要的数据结构及其算法。了一种非常重要的数据结构及其算法。著作自动机理论.语言和计算导论国内有出版今年今年10月份受邀到清华讲学

39、月份受邀到清华讲学JohnE.Hopcroft(10/07/1939)“授予授予JohnE.Hopcroft图灵奖以表彰图灵奖以表彰其在其在数据结构和算法设计与分析领域数据结构和算法设计与分析领域的重要的基础性的贡献。的重要的基础性的贡献。”J.Hartmanis和和R.E.Steams（美国），美国），1993年。在计算复杂性年。在计算复杂性领域作出卓越贡献。领域作出卓越贡献。JurisHartmanis(07/07/1928)Stearns与与Hartmanis合作的关于计算复杂合作的关于计算复杂性方面的经典论文：性方面的经典论文：Hartmanis,J.,andStearns,R.E.O

40、nthecomputationalcomplexityofalgorithms.Trans.Amer.Math.Soc.117(1965),285306.M.Blum（美国），美国），1995年。在计算复杂性、密码学算法、年。在计算复杂性、密码学算法、程序验证技术等方面取得重要成绩。程序验证技术等方面取得重要成绩。布卢姆是受以色列学者拉宾布卢姆是受以色列学者拉宾（M.O.Rabin）的启发而开始这方面的研究的）的启发而开始这方面的研究的ManuelBlum(04/26/1938)姚期智（姚期智（AndrewChi-ChihYao，美籍华人，美籍华人，1946-），），2000年，因为其对计算理

41、论做出了诸多年，因为其对计算理论做出了诸多“根本性的、意义重大的根本性的、意义重大的”贡献贡献(其中包括产生伪随机数的复杂性理论，密码系统和其中包括产生伪随机数的复杂性理论，密码系统和通讯复杂性等通讯复杂性等)。他是迄今为止获得他是迄今为止获得“图灵奖图灵奖”的唯一亚裔的唯一亚裔计算机科学家。计算机科学家。AndrewChi-ChihYao(姚期智姚期智)(12/24/1946)RonaldL.Rivest，AdiShamir和和LeonardAdelman.2002年。年。国际上最具影响力的公钥密码算法国际上最具影响力的公钥密码算法“RSA”的创始人。的创始人。AdiShamir2009年受

42、邀国内讲学。年受邀国内讲学。LeonardM.Adleman(12/31/1945)RonaldL.Rivest(1947)AdiShamir(1952)“授予授予RonaldL.Rivest,AdiShamir,LeonardM.Adleman图灵图灵奖以表彰其奖以表彰其使得公钥密码技术在实际中应用中的创造性贡献。使得公钥密码技术在实际中应用中的创造性贡献。”KayAlan，2003年。因发明第一个完全面向对象的动态计年。因发明第一个完全面向对象的动态计算机程序设计语言算机程序设计语言Smalltalk。至理名言：。至理名言：预测未来的最好方预测未来的最好方法是创造它法是创造它。AlanKa

43、y(05/17/1940)“授予授予AlanKay图灵奖以表彰其图灵奖以表彰其对当代对当代面向对象编程语言根本点的先驱性的思面向对象编程语言根本点的先驱性的思想，领导研发队伍开发了想，领导研发队伍开发了SmallTalk语言，语言，和其对个人计算的基础性的贡献。和其对个人计算的基础性的贡献。”PeterNaur，2005年，表彰他在设计年，表彰他在设计Algol60语言上的贡献。语言上的贡献。由于其定义的清晰性，由于其定义的清晰性，Algol60成为了许多现代程序设计语言成为了许多现代程序设计语言的原型。在语法描述中广泛使用的的原型。在语法描述中广泛使用的BNF范式，其中的范式，其中的“N”便

44、是来自便是来自PeterNaur的名字。的名字。PeterNaur(10/25/1928)“授予授予PeterNaur图灵奖以表彰其图灵奖以表彰其对对Algol60编程语言的设计与定义，对编译编程语言的设计与定义，对编译器设计和计算机编程领域的理论与实践的器设计和计算机编程领域的理论与实践的基础性贡献。基础性贡献。”2007年度图灵奖授予年度图灵奖授予EdmundM.Clarke、EAllenEmerson和和JosephSifakis三位科学家，表彰他们开发模型检测技术，三位科学家，表彰他们开发模型检测技术，并使之成为一个广泛应用在硬件和软件工业中非常有效的算并使之成为一个广泛应用在硬件和软

45、件工业中非常有效的算法验证技术所做的奠基性贡献。法验证技术所做的奠基性贡献。EdmundM.Clarke2009年受年受邀国内讲学邀国内讲学EdmundClarke（07/27/1945）EAllenEmersonJosephSifakis(1946)“授予授予JosephSifakis等图灵奖以表彰其等图灵奖以表彰其对目前在硬件和软件对目前在硬件和软件领域被广泛使用的模型检查发展成为一个重要的，高效的验证领域被广泛使用的模型检查发展成为一个重要的，高效的验证技术所做出的杰出贡献。技术所做出的杰出贡献。”2008年度图灵奖授予麻省理工学院（年度图灵奖授予麻省理工学院（MIT）女教授芭芭拉）女教

46、授芭芭拉利利斯科夫斯科夫(BarbaraLiskov)，表彰她在计算机程序语言设计方面，表彰她在计算机程序语言设计方面的开创性工作。的开创性工作。“利斯科夫在基础计算机科学领域取得了最利斯科夫在基础计算机科学领域取得了最重要的开创性进展，她的卓越成就不仅得到学术界的赞叹，重要的开创性进展，她的卓越成就不仅得到学术界的赞叹，也在日常生活中得到了广泛的应用。当你使用也在日常生活中得到了广泛的应用。当你使用e-mail、在线查、在线查看银行账单或使用看银行账单或使用GOOGLE时，其中就涉及到了她的研究。时，其中就涉及到了她的研究。”每一位图灵奖得主都有一段精彩的、让人敬佩的、值得每一位图灵奖得主都

47、有一段精彩的、让人敬佩的、值得IT业者追寻的足迹和故事，希望同学们能读读，相信你会增加对业者追寻的足迹和故事，希望同学们能读读，相信你会增加对专业的兴趣和学习、研究的动力！专业的兴趣和学习、研究的动力！BarbaraLiskov（1939-）美国第一位计算机科学女博士，有史以来美国第一位计算机科学女博士，有史以来第二位女性图灵奖得主（第一位是第二位女性图灵奖得主（第一位是2006年年得奖的得奖的FrancesAllen）。“对编程语言对编程语言和系统设计的实践与理论基础，尤其是数和系统设计的实践与理论基础，尤其是数据抽象、容错和分布式计算方面的贡献据抽象、容错和分布式计算方面的贡献”。“良好的

48、良好的信息组织信息组织和和优秀的优秀的算法算法是软件开发是软件开发的基础和保障！的基础和保障！”程序=数据结构+算法（NiklausWirth）参考书目：1、IntroductiontoAlgorithmsSecondEdition美美ThomasH.Cormen,C.E.Leiserson,R.L.Rivest2、APracticalIntroductiontoDataStructuresandAlgorithmAnalysisSecondEdition美美CliffordA.Shaffer3、TheDesignandAnalysisofComputerAlgorithms美美AlfredV

49、.Aho,JohnE.Hopceoft,JeffreyD.Ullman4、算法设计与分析算法设计与分析王晓东编著王晓东编著清华大学出版社清华大学出版社5、计算机算法：设计和分析引论计算机算法：设计和分析引论美美SaraBaase著著复旦大学出版社复旦大学出版社6、算法与数据结构算法与数据结构傅清祥，王晓东著，电子工业出版社傅清祥，王晓东著，电子工业出版社7、DataStructures,Algorithms,andApplicationsinC+美美SartajSahni机械工业出版社机械工业出版社建议：建议：1、2、3至少应读一本原版的教材！至少应读一本原版的教材！教学方式：课堂课堂讲授；讲

50、授；查阅和阅读文献或参考资料（课下自己完成）；查阅和阅读文献或参考资料（课下自己完成）；讨论、交流（同学们讲为主）讨论、交流（同学们讲为主）上机实习（课下自己完成）；上机实习（课下自己完成）；考核方式：笔试（笔试（70%）实习报告（源码实习报告（源码+文档材料）（文档材料）（30%）内容提要：第第一部分：数据结构基础（概述）一部分：数据结构基础（概述）一般数据结构一般数据结构高级数据结构高级数据结构第二部分：算法基础（概述）第二部分：算法基础（概述）问题及算法问题及算法算法的特征算法的特征第三部分：算法分析技术第三部分：算法分析技术数学基础数学基础一般分析方法一般分析方法第四部分：算法设计设计