算法设计-1

《算法设计-1》由会员分享，可在线阅读，更多相关《算法设计-1（48页珍藏版）》请在金锄头文库上搜索。

1、,算法设计与分析 Design and Analysis of Computer Algorithm,计算机学院信息安全系毕方明,第一章 算法概述,第二章 递归与分治策略,第三章 动态规划,第四章 贪心算法,第五章 回朔法,第六章 分支限界法,第七章 概率算法,算法设计与分析 目录,参考书,计算机算法设计与分析（第四版） ，王晓东著，电子工业出版社，2013年计算机算法基础（第三版），余祥宣等著，华中理工大学出版社，2003年计算机算法导引设计与分析，卢开澄著，清华大学出版社，1996年计算机算法设计与分析，卢开澄，中国铁道出版社，1998年Introduction to Algorithms

2、（第二版 影印版），Thomas H. Cormen著，高等教育出版社,算法设计与分析,课程考核安排,实验、作业、课堂回答问题（30%）闭卷考试（70%）附加题 包含一个算法的动画（+10%） 算法尽量不要相同 题目可以为实现书中的程序,算法设计与分析,算 法 概 述,Algorithm Introduction,第一章,介绍算法设计的基本概念及算法分析的方法和准则.,算法设计与分析,学习要点:,算法设计与分析,理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C+语言描述算法的方法。,7,一系列将问题的输入转换为输出的计

3、算或操作步骤。,2. 计算机算法与人工算法,算法设计与分析 算法概述,1.1 算法 Algorithm1. 算法定义,有些问题没有计算机算法.,有些问题计算机算法与人工算法不同.,(1)输 入： 有外部提供的量作为算法的输入。(2)输 出： 算法产生至少一个量作为输出。(3)确定性：definiteness 组成算法的每条指令是清晰，无歧义的。(4)有限性：finiteness 算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,3.计算机算法的一般特征,8,算法设计与分析 算法概述,数值型算法:算法中的基本运算为算术运算.,非数值型算法:算法中的基本运算为逻辑运算.,串行算法:

4、串行计算机上执行的算法.,并行算法:并行计算机上执行的算法.,从处理方式上,6. 算法分类,从解法上,5.算法描述语言,1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移.,4.算法的三个要素,自然语言,数学语言,流程图,程序设计语言等等.,9,算法设计与分析 算法概述,7.问题的求解过程,2)建立数学模型,1)问题的陈述,3)算法设计,4)算法的正确性证明,5)算法的程序实现,6)算法分析,用科学规范的语言,对所求解的问题做准确的描述.,通过对问题的分析,找出其中的所有操作对象及操作对象之间

5、的关系并用数学语言加以描述.,根据数学模型设计问题的计算机求解算法.,证明算法对一切合法输入均能在有限次计算后产生正确输出.,对执行该算法所消耗的计算机资源进行估算.,将算法正确地编写成机器语言程序.,10,算法设计与分析 算法概述,8.算法与程序、数据结构的关系,过程：算法+数据结构程序对象：对象+消息程序侧重点不同 数据的结构，直接影响算法的选择和效率。,11,数据的逻辑结构,数据的存储结构,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,散列存储,索引存储,串及数组,数据的运算：检索、排序、插入、删除、修改等,算法设计与分析 算法概述

6、,8.算法与程序、数据结构的关系,12,算法设计与分析 算法概述,8.算法与程序、数据结构的关系,与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。,高级程序设计语言（C, C+）,数据结构,算法设计与分析,13,广播操图解是广播操的算法;菜谱是做菜的算法；歌谱是一首歌曲的算法；空调说明书是空调使用的算法等,What？,算法设计与分析 算法概述,8.算法与程序、数据结构的关系,14,例1：给出求1+2+3+4+5的一个算法。,算法1 按照逐

7、一相加的程序进行。,第一步 计算1+2,得到3；,第二步 将第一步中的运算结果3与3相加,得到6；,第三步 将第二步中的运算结果6与4相加,得到10；,第四步 将第三步中的运算结果10与5相加,得到15。,算法设计与分析 算法概述,8.算法与程序、数据结构的关系,15,第一步 取n=5;,第二步 计算,第三步 输出运算结果。,算法设计与分析 算法概述,8.算法与程序、数据结构的关系,16,例2：三个牧师和三个野人过河，只有一条能装下两人的船，在河的任一边或者船上，若野人人数大于牧师人数，那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河算法呢？,第一步 两个野人先过河，一个野人回来；,第二

8、步 再两个野人过河，一个野人回来；,第三步 两个牧师过河，一个野人和一个牧师回来；,第四步 两个牧师过河，一个野人回来；,第五步 两个野人过河，一个野人回来；,第六步 两个野人过河。,算法设计与分析 算法概述,17,现代科学研究的三大支柱,研究算法,算法设计与分析 算法概述,18,本课程为计算机学科本科生的专业课。,How to study？,通过该课程的学习，对计算机常用算法有一个全 盘的了解，掌握通用算法的一般设计方法。,学会对算法的时间和空间复杂性进行分析，掌握提高算法效率的方法和途径。(评价有效算法),算法设计与分析 算法概述,8.算法与程序、数据结构的关系,19,算法设计与分析 算法

9、概述,1.2 算法复杂性分析1.复杂性的计量,显然,它与问题的规模,算法的输入数据及算法本身有关.,将时间复杂性和空间复杂性分别考虑,并用T和S表示.则 T=T(N,I,A) S=S(N,I,A) 将A隐含在函数名中,则 T=T(N,I,A) 简化为T=T(N,I),算法的复杂性:算法执行所需的时间和空间的数量.,令 N:问题的规模 I:输入数据 A:算法本身 则算法的复杂性 C=F (N,I,A),设一台抽象计算机提供的元运算有k种,分别记作O1 ,Ok 设这些元运算每执行一次所需时间分别为t1 , t2,tk ,设算法A中用到Oi的次数为 ei, i=1,k,则 ei= ei(N,I ),

10、T=T(N,I)=,20,算法设计与分析 算法概述 算法的复杂性,最好情况:Tmin(N) = T(N,I) = = =最坏情况:Tmax(N) = T(N,I) = = = 平均情况:Tavg(N) = =,例 题1-1,其中 DN:规模为N的所有合法输入的集合 I*: DN中达到Tmax (N)的一个输入 : DN中达到Tmin (N)的一个输入 P(I): 出现输入为I的概率,算法设计与分析,已知不重复且从小到大排列的m个整数的数组A1.m,m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得Ai=c.找不到返回0.,function search(c) i:=1; a wh

11、ile Aic and i=L do t (logm+2) i:=(L+U)div2; (a+s+d)(logm+1) if c=Ai t (logm+1)then found:=true aelse if cAi t (logm+1) then L:=i+1 (s+a)(logm+1) else U:=i-1 if found then b-search:=i else b-search:=0 a ,23,算法设计与分析 算法概述 算法的复杂性,2 复杂性的渐进性态 1).渐进性态,设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在一个函数 使得当n ,有 (T(n)- ) / T(n)0称 是T(n)当 n 时的渐进性态或 渐进复杂性.,在数学上,T(n)与 有相同的最高阶项.可取 为略去T(n)的低阶项后剩余的主项.当n充分大时我们用 代替T(n)作为算法复杂性的度量,从而简化分析.,