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

《算法分析与设计1-数据结构基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析课程名称：DesignandAnalysisofAlgorithms主讲人：段友祥石油大学计算机与通信工程学院引言计算机科学与技术学科的研究内容简单说，计算机学科是研究机器进行信息表示和信息处理的科学。信息表示：（1）数字化:（2）可视化:（3）效率信息处理：（1）方法（2）效率想想看：是不是计算机所有的硬件和软件技术都属于这两个范畴？引言算法在计算机科学中的地位（1）算法是计算机科学基础的重要主题70年代后，算法作为计算机科学的核心推动了计算机科学技术的飞速发展70年代前，计算机科学基础的主题没有被清楚地认清。70年代

2、，Knuth出版了《TheArtofComputerProgramming》(三卷）,以各种算法研究为主线，确立了算法为计算机科学基础的重要主题，1974年获得图灵奖。引言算法在计算机科学中的地位（2）计算机科学的体系解决一个计算问题的过程：可计算否→能行可计算否→算法设计与分析→用计算机语言实现算法→软件系统可计算理论:·计算模型·可计算问题/不可计算问题·计算模型的等价性--图灵/Church命题什么是计算？计算机科学的本质：·直观地看，计算一般是指运用事先规定的规则，将一组数值变换为另一(所需的)数值的过程。·什么能被自动地有效

3、执行。引言算法在计算机科学中的地位（2）计算机科学的体系计算复杂性理论（能行否）·在给定的计算模型下研究问题的复杂性·上界·下界·平均·固有复杂性·复杂性问题的非类:P=NP?·抽象复杂性研究算法设计和分析·可计算问题的算法的设计与分析·设计算法的理论、方法和技术·分析算法的理论、方法和技术引言算法在计算机科学中的地位（3）算法设计与分析的意义计算机各领域的核心计算机工程特别是计算机软件工程的基础“一个受过良好的计算机科学知识训练的人知道如何处理算法，即构造算法、操纵算法、理解算法和分析算法。算法的知识远不是为了编写好的计算程序，它是

4、一种具有一般意义的智能工具，必定有助于对其他学科的理解，不论化学、语言学或者是音乐等”——D.E.Knuth(美国著名计算机科学家)“算法不仅是计算机学科的一个分支，它更是计算机科学的核心，而且可以毫不夸张地说，它和绝大多数科学、商业和技术都是相关的。”——《算法学—计算机的灵魂》DavidHarel引言计算机离不开软件，软件简单说就是程序，而程序的核心是算法。什么是算法？什么是程序？它们之间的关系？算法问题是计算机科学研究的核心问题之一！很多科学家在算法及其相关领域取得了创造性的成果——图灵奖（从1966年开始已经有50多位科学家获

5、得了这一殊荣。其中有1/3的获奖人是因为在算法和数据结构及其相关领域做出了杰出贡献而获奖的）了解一下这些“牛”人，看看他们的经历和突出成绩：1930，5，11–2002，8，6。荷兰计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。在1972年获得图灵奖，之后，他还获得过1974年AFIPSHarryGoodeMemorialAward、1989年ACMSIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACMPODC最具影响力论文奖。1972年，EdsgerW.Dijkstra因在编程语言方面的出

6、众表现而获奖。这个Dijkstra，就是那个提出“goto有害论”的Dijkstra，就是那个提出信号量和PV原语，解决了有趣的“哲学家聚餐”问题的Dijkstra，那个Dijkstra最短路径算法的创造者，第一个Algol60编译器的设计者和实现者，THE操作系统的设计者和开发者，那个与D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人。晚年疯狂的迷恋C++EdsgerDijkstra经典言论：1.编程的艺术就是处理复杂性的艺术。2.优秀的程序员很清楚自己的能力是有限的，所以他对待编程任务的态度是完全谦卑的，特别是，他们会

7、象逃避瘟疫那样逃避“聪明的技巧”。——1972年图灵奖演讲。3.计算机科学是应用数学最难的一个分支，所以如果你是一个蹩脚的数学家，最好留在原地，继续当你的数学家。4.我们所使用的工具深刻地影响我们的思考习惯，从而也影响了我们的思考能力。5.实际上如果一个程序员先学了BASIC，那就很难教会他好的编程技术了：作为一个可能的程序员，他们的神经已经错乱了，而且无法康复。6.就语言的使用问题：根本不可能用一把钝斧子削好铅笔，而换成十把钝斧子会使事情变成大灾难。7.简单是可靠的先决条件。Dijkstra在1968年发表的短文：GoToState

8、mentConsideredHarmful1938年12月7日，DonaldE.Knuth出生于美国威斯康星州密尔沃基市。让人眩目的履历：1974年，DonaldE.Knuth因在算法分析和编程语言设计方面的突出贡献设计