计算机算法设计与分析第一章.ppt

* 计算机算法设计与分析 主讲教师：金英 The Design and Analysis of Computer Algorithms * 【参考教材】 王晓东,计算机算法设计与分析 (第4版) ,电子工业出版社，2012。 Thomas H.Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms (Second Edition), The MIT Press, 2013. [算法导论 （第三版）] 【课程基础】 本课程要求学生在学习之前已经熟练掌握C/C++程序设计，学习过高等数学、线性代数、离散数学、概率论与数理统计、数据结构等课程。 * 【主要教学内容】 设计算法及分析算法的理论、方法和技术； 可计算问题的算法设计与分析。 分为下述部分介绍： 算法概述 递归与分治策略 动态规划 贪心算法 回溯法 分支限界法 * 第一章：算法概述 * 70年代前 计算机科学基础的主题没有被清楚地认清 70年代 Knuth出版了 《The Art of Computer Programming》 以算法研究为主线确立了算法为计算机科学基础的重要主题 1974年获得图灵奖 70年代后 算法作为计算机科学核心推动了计算机科学技术飞速发展 算法是计算机科学的重要主题 第一节 算法在计算机科学中的地位 * 算法设计与分析 可计算理论 计算复杂性理论 计算机科学技术的体系 解决一个计算问题的过程 可计算否 能行可计算否 软件系统 用计算机语言实现算法 设计与分析算法 数据结构与程序设计 编译、OS、… * 可计算理论 计算模型 可计算问题/不可计算问题 计算模型的等价性--图灵/Church命题 计算复杂性理论 在给定的计算模型下研究问题的复杂性 固有复杂性 复杂性下界 平均复杂性 复杂性问题的分类: P=NP? 公理复杂性理论 * 算法设计和分析 设计算法的理论、方法和技术 分析算法的理论、方法和技术 计算机软件 系统软件 工具软件 应用软件 * 第二节 算法与程序 算法（Algorithm）的概念 通俗地讲 算法是指解决问题的一种方法或一个过程。 严格地讲 算法是由若干条指令组成的有穷序列,且满足下述性质： （1）输入: 有零个或多个由外部提供的量作为算法的 输入。 （2）输出: 算法产生至少一个量作为输出。 （3）确定性: 组成算法的每条指令是清晰的，无歧义的。 （4）有限性: 算法中每条指令的执行次数是有限的， 执行每条指令的时间也是有限的。 * 算法与程序的区别 程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的性质（4）----有限性。 例如: 操作系统，它是一个在无限循环中执行的程序，因而不是算法。可把操作系统的各种任务看成是一些单独的问题，每个问题由操作系统中的一个子程序通过特定的算法来实现。 算法描述 描述算法可以有多种形式。 本课程将用C/C++语言或伪代码描述算法。 * 算法复杂性的含义 一个算法的复杂性的高低体现在运行该算法所需的计算机资源（主要指时间和空间资源）的多少上。 第三节 算法复杂性分析 算法的复杂性主要分为: 时间复杂性 空间复杂性 算法的复杂性分析的用处途: 为求解一个问题选择最佳算法、最佳设备 * 随着计算机要解决的问题越来越复杂，规模越来越大，对求解这类问题的算法作复杂性分析具有特别重要的意义。 随着计算机技术的迅速发展，对空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强调时间复杂性的分析。 考虑时间复杂性的理由： 某些用户需要提供程序运行时间的上限（用户可接受的）； 所开发的程序需要提供一个满意的实时反应。 * 本课程考虑如下三种情况下的时间复杂度： 最坏情况；最好情况；平均情况。 时间复杂性的计算方法(即估算运行时间的方法) 加、减、乘、除、比较、赋值等操作，一般被看作是基本操作，并约定所用的时间都是一个单位时间；通过计算这些操作分别执行了多少次来确定程序总的执行步数。 一般地，一些关键操作执行的次数决定了算法的时间复杂度。 * 例1：二分查找算法 int bsearch(K,L,H) { if (HL) return(-1); else { mid=(L+H) /2; element=A[mid];