计算机算法基础第一章教案资料.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《计算机算法基础第一章教案资料.ppt》由会员分享,可在线阅读,更多相关《计算机算法基础第一章教案资料.ppt(102页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、计算机算法基础第一章算法的应用n数据库中的检索n搜索引擎中的检索n公共密钥加密和数字签名技术n优化问题q最短路径q资源分配q章节安排n计算机算法基础,余祥宣、崔国华、邹海明著,华中科技大学出版社 n第一章 导引与基本数据结构 n第二章 分治法 n第三章 贪心方法 n第四章 动态规划 n第五章 检索与周游n第六章 回溯法n第七章 分枝-限界n第八章 NP-问题 预备知识n数学:集合、证明方法(直接、间接、反证、反例、归纳假设)、对数基础、FLOOR&CEILING函数、阶乘、递归关系n数据结构:链接表、图、树、二元树第一章 导引与基本数据结构1.1 算法的定义及特性1.什么是算法?一系列将问题的
2、输入转换为输出的计算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。2.算法的五个重要特性 确定性、能行性、输入、输出、有穷性1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。例:不符合确定性的运算n 5/0 n 将6或7与x相加n 未赋值变量参与运算2)能行性 算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在有限的时间内完成。例:整数的算术运算是“能行”的 实数的算术运算是“不能行”的3)输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合定义域(或值域)4)输出 一个算法产生一个或多个输出,这些输出是同输入有某种特定关
3、系的量。5)有穷性 一个算法总是在执行了有穷步的运算之后终止。计算过程:只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。n 准确理解算法和计算过程的区别:不能终止的计算过程:操作系统 算法是“可以终止的计算过程”算法的时效性:只能把在相当有穷步内终止的算法投 入到计算机上运行3.我们的主要任务 算法学习将涉及5个方面的内容:1)设计算法:创造性的活动 2)表示算法:思想的表示形式 3)确认算法:证明算法的正确性 程序的证明 4)分析算法:算法时空特性分析 5)测试程序:调试和作出时空分布图 本课程集中于学习算法的设计与分析。通过学习,掌握计算机算法设计和分析基本策略与方法,为
4、设计更复杂、更有效的算法奠定基础4.算法描述语言自然语言自然语言,数学语言数学语言,流程图流程图,程序设计语言等等程序设计语言等等.5.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计用科学规范的语言用科学规范的语言,对所求解的问题做准确的描述对所求解的问题做准确的描述.通过对问题的分析通过对问题的分析,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法.4)算法的正确性证明5)算法的程序实现6)算法分析证明算法对一切合法输入均能在有限次计
5、算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序.1.2 1.2 分析算法分析算法1.分析算法的目的 在于:通过对算法的分析,在把算法变成程序实际运行前,就知道为完成一项任务所设计的算法的好坏,从而运行好的算法,改进差的算法,避免无益的人力和物力浪费。算法分析是计算机领域的古老而前沿的课题。进行算法分析的基本技术:抽象2.重要的假设和约定1)计算机模型的假设n Turing机模型:计算机形式理论模型 n 通用计算机模型:单处理器 有足够
6、的“内存”能在固定的时间内存取数据单元2)计算的约定n确定使用什么样的运算及其执行时间。n从计算时间上,运算的分类:时间囿界于常数的运算:尽管每种运算的执行时间不同,但一般只花 一个固定量的时间(单位时间)就可完成。基本算术运算,如整数、浮点数的加、减、乘、除 字符运算 赋值运算 过程调用等2)计算的约定(续)计算的约定(续)其他运算:字符串操作:与字符串中字符的数量成正比 记录操作:与记录的属性数、属性类型等有关 特点:运算时间无定量 如何分析非时间囿界于常数的运算:分解成若干时间囿界于常数的运算。如:Tstring=Length(String)*tcharn算法的执行时间=Fi*tiq其中
7、,Fi是算法中用到的某种运算i的次数,ti是该运算执行一次所用的时间。3)工作数据集的选择n编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法,以了解算法的性能。n测试数据集的生成n作为算法分析的数据集:典型特征n作为程序性能测试的数据集:对执行指标产生影响的性质3.如何进行算法分析?对算法进行全面分析,可分两个阶段进行:n事前分析:就算法本身,通过对其执行性能的理论分析,得出关于算法特性时间和空间的一个特征 函数(、)与计算机物理软硬件没有 直接关系。n事后测试:将算法编制成程序后实际放到计算机上运行,收集其执行时间和空间占用等统计资料,进行 分析判断直接与
8、物理实现有关。1)事前分析n目的:试图得出关于算法执行特性的一种形式描 述,以“理论上”衡量算法的“好坏”。n如何给出反映算法执行特性的描述?最直接方法:统计算法中各种运算的执行情况,包括:运用了哪些运算 每种运算被执行的次数 该种运算执行一次所花费的时间等。算法的执行时间=Fi*tin频率计数 例:xx+y for i 1 to n do for i 1 to n do x x+y for j 1 to n do repeat x x+y repeat repeat (a)(b)(c)分析:(a):xx+y执行了1次 (b):xx+y执行了n次 (c):xx+y执行了n2次 定义:频率计数:
9、一条语句或一种运算在算法(或程序)体中的执行次数。算法2.7 插入分类 procedure INSERTIONSORT(A,n)/将A(1:n)中的元素按非降次序分类,n1/1 A(0)-/设置初始边界值 2 for j2 to n do/A(1:j-1)已分类/3 itemA(j);ij-1 4 while itemA(i)do /0ij/5 A(i+1)A(i);ii-1 6 repeat 7 A(i+1)item;8 repeat end INSERTIONSORT n(8,5,4,9)n(8,5,4,9)n(5,8,4,9)n(5,8,4,9)n(4,5,8,9)n(4,5,8,9)一
10、条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间n 如何刻画算法执行特性的形式描述实际执行时间受约于诸多实际因素,如机器类型、编程与语言、操作系统等,没有统一的描述模型。在事前分析中,只限于确定与所使用的机器及其他环境因素无关的频率计数,依此建立理论分析模型。n数量级 语句的数量级:语句的执行频率 例:1,n,n2 算法的数量级:算法所包含的所有语句的执 行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例:假如求解同一个问题的三个算法分别具有n,n2,n3数 量级。若n=10,则可能的执行时间将分别是10,100,1000个单 位时间与环境因素无关。n 计算时
11、间/频率计数的表示函数 通过事前分析给出算法计算时间(频率计数)的一个函数表示形式,一般记为与输入规模n有关的函数形式:f(n)注:最高次项与函数整体的关系n空间特性分析(略)2)事后测试n目的:运行程序,确定程序实际耗费的时间与空间,验证先前的分析结论包括正确性、执行性能等,比较、优化所设计的算法。n分析手段:作时、空性能分布图4.计算时间的渐近表示计算时间的渐近表示记:算法的计算时间为f(n)数量级限界函数为g(n)其中,n n是输入或输出规模的某种测度。n f(n)表示算法的“实际”执行时间与机器及语言有关。n g(n)是形式简单的函数,如nm,logn,2n,n!等。是事前分析中通过对
12、计算时间或频率计数统计分析所得的、与机器及语言无关的函数。以下给出算法执行时间:上界()、下界()、“平均”()的定义。1)上界函数)上界函数定义1 如果存在两个正常数c和n0,对于所有的nn0,有|f(n)|c|g(n)|则记作f(n)=(g(n)含义:n如果算法用n值不变的同一类数据在某台机器上运行时,所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。f(n)的数量级就是g(n)。n试图求出最小的g(n),使得f(n)=(g(n)。n多项式定理:定理1 若A(n)=amnm+a1n+a0是一个m次多项 式,则有A(n)=(nm)即:变量n的固定阶数为
13、m的任一多项式,与此多 项式的最高阶nm同阶。证明:取n0=1,当nn0时,有|A(n)|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|am-1|+|a0|)nm 令c=|am|+|am-1|+|a0|则,定理得证。n 计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。例:假设解决同一个问题的两个算法,它们都有n个输入,计算时间的数量级分别是n2和nlogn。则,n=1024:分别需要1048576和10240次运算。n=2048:分别需要4194304和22528次运算。分析:在n加倍的情况下,一个(n2)的算法
14、计算时间增长4 倍,而一个(nlogn)算法则只用两倍多一点的时间即 可完成。算法2.8 归并分类 procedure MERGESORT(low,high)/A(low:high)是一个全程数组,它含有high-low+10个待分类的元素/integer low,high if lowhigh then mid /计算中分点/call MERGESORT(low,mid)/在第一个子集合上分类(递归)/call MERGESORT(mid+1,high)/在第二个子集合上分类(递归)/call MERGE(low,mid,high)/归并已分类的两子集合/endif end MERGESOR
15、TMerge算法示例n(4,5,8,9)|(1,2,6,7)(1,2,4,5,6,7,8,9)q参数:low=1;high=8;mid=4q(4,5,8,9)|(1,2,6,7)hjjjjhh(14256789)j 算法分类(计算时间)算法分类(计算时间)多项式时间算法:可用多项式(函数)对其计算时间限界的算法。常见的多项式限界函数有:(1)(logn)(n)(nlogn)(n2)(n3)指数时间算法:计算时间用指数函数限界的算法 常见的指数时间限界函数:(2n)(n!)0。特殊形态的二元树n 满二元树:深度为k且有2k-1个结点的二元树 n完全二元树:一棵有n个结点深度为k的二元树,当它的结
16、点相当于深度为k的满二元树中编号为1到n的结点时,称该二元树是完全的。完全二元树的叶子结点至多出现在相邻的两级上。完全二元树的结点可以紧凑地存放在一个一维数组中(性质见引理1.2)。二元树的表示方法二元树的表示方法 1.数组表示法:对于完全二元树,空间效率好;其他二元树,要浪费大量空间 2.链表法:结构简单,有效。链表中每个结点有三个信息段,LCHILD,DATA和RCHILD 堆:堆是一棵完全二元树,它的每个结点的值至少和该结点的儿子们(如果存在的话)的值一样大(max-堆)(或小,min-堆)。二分检索树:二分检索树是一棵二元树,它或者为空,或者其每个结点含有一个可以比较大小的数据元素,且
17、有:的左子树的所有元素比根结点中的元素小;的右子树的所有元素比根结点中的元素大;的左子树和右子树也是二分检索树。注:二分检索树要求树中所有结点的元素值互异3.树的应用不相交集合的合并及搜索问题 n问题描述:q给定一个全集U,该集合包含n个元素q很明显该集合包含多个不相交的子集q某些应用需要实现这些不相交子集的合并、查找操作,并且这些操作最终可形成序列q如何高效率实现这些操作序列就是我们要解决的问题集合操作举例nn=10,U=1,2,3,4,5,6,7,8,9,10ns1=1,7,8,9;s2=2,5,10;s3=3,4,6n合并运算:s1s2=1,7,8,9,2,5,10n查找运算:元素4包含
18、在s1,s2,s3的哪个集合中?方法一位向量n方法一:位向量 n s1=1,0,0,0,0,0,1,1,1,0;n s2=0,1,0,0,1,0,0,0,0,1;n利用位运算可得出ns1s2=1,1,0,0,1,0,1,1,1,1n缺点:n很大,超过一个机器字长,而参与运算的集合的势很小时,运算与n成正比。方法二集合元素表 ns1=1,7,8,9;ns2=2,5,10n合并操作:|s1|+|s2|n查找操作:最坏为|n|方法三树 数据结构n字符数组U=1,2,3,4,5,6,7,8,9,10n子集s1=1,7,8,9;s2=2,5,10n则用数组Parent表示集合s1和s2:数组中记录的是节
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 算法 基础 第一章 教案 资料
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内