[工学]计算机算法概述.ppt

教材： 算法设计与分析 吕国英主编 清华大学出版社 参考书： 计算机算法基础 余祥宣等编 华中科大出版社 算法设计与分析 王晓东编 清华大学出版社 计算机算法导引——设计与分析 卢开澄编 清华大学出版社 国外教材 算法导论（第二版 影印版）Introduction to Algorithms(Second Edition ) （美）Thomas H.Cormen等 高等教育出版社 计算机程序设计艺术（英文影印版）（1-3卷精装全套）The Art of Computer Programming Volumes 1-3 Boxed Set （美）Donald E.Knuth 清华大学出版社 与其他课程的关系 例2：三个牧师和三个野人过河，只有一条能装下两人的船，在河的任一边或者船上，若野人人数大于牧师人数，那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河算法呢？ 学习目标：“用计算机求解问题” 一般计算机对现实问题无能为力，需要人类对问题抽象化、形式化后才能去机械的执行。 1.1 算法 1. 什么是算法？ 算法是解一确定类问题的任意一种特殊的方法。 在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词： 算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。 2. 算法的五个重要特性 确定性、能行性、输入、输出、有穷性/有限性 3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域 计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 准确理解算法和计算过程的区别： 不能终止的计算过程：操作系统 算法是“可以终止的计算过程”。 算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行。 算法和程序 程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现 任何一种程序设计语言都可以实现任何一个算法 算法的有穷性意味着不是所有的计算机程序都是算法 1.2 算法描述 算法 = 控制结构 + 原操作 表示算法的语言主要有： 自然语言 流程图 盒图 PAD图 伪代码 计算机程序设计语言 1．自然语言 自然语言是人们日常所用的语言。 自然语言描述算法的缺点： ①自然语言的歧义性易导致算法执行的不确定性。 ②自然语言语句一般太长导致描述的算法太长。 ③当算法中循环和分支较多时就很难清晰表示。 ④不便翻译成程序设计语言理解的语言。 2．流程图 3．盒图（NS流程图） （1）盒图具有以下优点： ① 层次感强、嵌套明确。 ② 支持自顶向下、逐步求精。 ③ 容易转换成高级语言源算法。 PAD图的主要优点： ①设计出来的算法必是结构化的。 ②PAD图描绘的算法结构清晰。 ③用PAD图表现的算法逻辑，易读、易懂、易记。 ④容易用软件工具自动将PAD图转换成高级语言源算法。 ⑤既可用于表示算法逻辑，也可用于描绘数据结构。 ⑥支持自顶向下、逐步求精。 缺点：由于是图形符号书写、编辑、录入不方便。 例： 5．伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此书写方便，格式紧凑，易于理解，便于用计算机程序设计语言实现。 如：类SPARKS/类C/类C＋＋ 6．程序设计语言的缺点： ① 算法的基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的，当算法的逻辑流程较为复杂时这个问题就变得更加严重。 ② 特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决。 ③ 要花费大量的时间去熟悉和掌握某种特定的程序设计语言。 ④ 要求描述计算步骤的细节而忽视算法的本质。 ⑤ 需要考虑语法细节，而扰乱算法设计的思路。 ⑥ 考虑到程序设计语言不断更新，不适于描述算法。 算法设计一般不用程序设计语言直接描述。 本书中的算法描述约定 采用类似C语言的伪代码描述法 顺序结构：以“；”结束 选择结构：if,switch 循环结构：for,while, do…wh