当前位置:首页 > 商业/管理/HR > 经营企划 > 《算法与数据结构》PPT课件
软件技术基础第4章算法与数据结构16学时软件技术基础算法与数据结构目的与要求:掌握算法与算法设计基本方法掌握数据结构的表示与基本操作重点与难点:算法描述方法及应用数据结构及其表示方法查找与排序算法设计本章要点软件技术基础算法与数据结构4.1算法及其表示4.2常用算法结构分析4.3数据结构及表示2学时4.4常用数据结构及表示(表、树、图)6学时4.5查找与排序4学时4.6文件与文件操作2学时4.7应用举例2学时本章内容2学时软件技术基础算法历史小知识算法的中文名称出自周髀算经;而英文名称Algorithm来自于9世纪波斯数学家比阿勒.霍瓦里松的名字al-Khwarizmi,因为比阿勒.霍瓦里松在数学上提出了算法这个概念。他写的书《al-jabrw’almuqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题是有条理的步骤。如果他能活到今天的话,他一定会被以他的名字而得名的方法的进展所感动。“算法”原为“algorism”,意思是阿拉伯数字的运算法则,在18世纪演变为“algorithm”。第一次编写算法是AdaByron于1842年为巴贝奇分析机编写求解解伯努利方程的程序,因此AdaByron被大多数人认为是世界上第一位程序员。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用软件技术基础4.1算法及其表示算法就是一种解题的方法,是解题过程的精确描述。算法是由若干条指令组成的有穷序列。即由有限条可完全执行的,有确切含义的指令(或命令,语句)所构成。算法通俗说法算法严格说法软件技术基础算法五大特征有穷性一个算法必须总是在执行有穷步后结束,且每一步都可在有穷时间内完成;确定性算法中的每一个指令比须有明确的含义,不能有二义性;可行性算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的;输入一个算法应有0个或多个输入;输出一个算法应有1个或多个输出。软件技术基础算法的表示•自然语言•流程图特定的表示算法的图形符号•伪语言包括程序设计语言的三大基本结构及自然语言的一种语言•类语言类似高级语言的表示,例如类PASCAL、类C语言算法的描述软件技术基础插入排序软件技术基础Insertion-Sort(A)1forj=1ton-12key=A[j]3i=j-14whilei=0andA[i]key5A[i+1]=A[i]6i=i-17A[i+1]=keyj=1j=2j=3j=4j=5245613245613245663245563244563224563124563A[0]A[1]A[2]A[3]A[4]A[5]软件技术基础算法的分析与评价1)正确性(Correctness)2)可读性(Readability)3)健壮性(robustness)4)高效率与低存储量算法的评价标准应具有容错处理功能。当输入非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。处理速度快;存储容量小。时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。算法的第一目的是为了阅读和交流;可读性有助于对算法的理解;可读性有助于对算法的调试和修改。•程序不含语法错误;•程序对几组输入数据•程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据;•程序对一切合法的输入数据能产生满足规格要求的结果软件技术基础算法的复杂性一个算法花费的时间与算法中语句的执行次数成正比,计算一个算法的时间复杂度一般用语句执行次数的数量级来衡量。数据结构中数据元素个数n称为问题的规模,当n不断变化时,语句的执行次数也会变化。时间复杂度空间复杂度问题的规模空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但一般讨论的是除正常占用内存开销外的辅助存储单元规模。时间或空间单位下数据的量的多少。空间单位一般规定为一个简单变量(如整型、实型等)所占存储空间的大小;时间单位则一般规定为执行一个简单语句(如赋值语句、判断语句等)所用时间。软件技术基础时间复杂度表示通常用“阶”“O(数量级)”来表示。常见的时间复杂度有:O(1)常数阶;O(logn)对数阶;O(n)线性阶;O(n^2)平方阶。例如:for(i=1;i=n;i++)for(j=1;j=i;j++)d[i][j]=data[i][j]+1;软件技术基础问题规模与时间复杂度的关系•一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做mathT(n)=\mathcal{O}(f(n))/math•因此,问题的规模n越大,算法执行的时间的增长率与f(n)的增长率正相关,称作渐进时间复杂度(AsymptoticTimeComplexity)。软件技术基础算法与建模算法/解题策略计算模型。常用三种计算模型:数学模型简单、准确,有成熟的计算方法。过程模拟模型处理日常事务问题算法的模型,模型简单易行。结构模型结点和边代表运算处理和输入/输出状态。有赖于常见模型结构分析——线性方程组人口预报——微分方程优化问题——线性规划、非线性规划震动问题——矩阵分析;特征值、特征向量信息管理——二维数据表下棋——人工智能(树型结构)交通管理——最佳道路选择(图型结构)软件技术基础4.2常用算法结构分析1.枚举2.搜索深度优先搜索广度优先搜索启发式搜索遗传算法1.哈夫曼编码2.树的遍历3.最短路径算法4.最小生成树算法5.最小树形图6.网络流算法7.匹配算法1.数值分析2.加密算法3.排序算法4.检索算法5.随机化算法算法的分类(一)基本算法(二)数据结构的算法(三)数论与代数算法(四)计算几何的算法(五)图论算法(六)动态规划(七)其他软件技术基础常用算法及举例•递归法•贪心法•迭代法•分治法•回溯法•动态规划法•分支界限法软件技术基础递归法基本思想递归法的出发点不放在初始条件上,而放在求解的目标上,从所求的未知项出发逐次调用本身的求解过程,直到递归的边界,即初始条件。而递推是从已知的初始条件出发。递归算法在可计算性理论中占有重要地位,它是算法设计的有力工具,对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识,只不过初学者要建立起递归概念不十分容易。软件技术基础递归法之计算3!初始条件:fact(1)=1,递推公式:fact(n)=n*fact(n-1)分析递归、递推过程软件技术基础递归法之TowerofHanoi软件技术基础过程:例1将一个盘子从A经B移动到C初始ABC一个步骤:将一个盘子从A移动到CABCABC软件技术基础例2将两个盘子从A经B移动到CABC过程三个步骤将一个盘子从A移动到B将一个盘子从A移动到C将一个盘子从B移动到C初始ABC软件技术基础例3将三个盘子从A经B移动到CABC怎么做?软件技术基础例3将三个盘子从A经B移动到C:Towers(3,A,C,B)Towers(2,A,B,C)Towers(1,A,C,B)Towers(2,B,C,A)软件技术基础voidTowers(intn,charSource,charTarget,charInterm){if(n==1)printf(“From%cto%c\n”,Source,Target);else{Towers(n-1,Source,Interm,Target);Towers(1,Source,Target,Interm);Towers(n-1,Interm,Target,Source);}}软件技术基础贪心法基本思想先依据题目的部分条件确定答案的范围,在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕,若每个情况使验证题目符合条件,则为本题的一个答案,若全部情况验证完毕后均不符合题目的条件,则题目无解。贪心算法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程。软件技术基础贪心算法之0/1背包问题•从剩余的物品中,选出可以装入背包的价值最大的物品•从剩下的物品中选择可装入背包的重量最小的物品•从剩余物品中选择可装入背包的pi/wi值最大的物品贪婪准则对容量为c的背包求解可行的背包装载。从n个物品中选取装入背包的物品,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。每件物品i的重量为wi,价值为pi。0/1背包问题软件技术基础迭代法•确定迭代公式,选取解的误差;•从事先估计的一个初始近似解出发,求另一个近似解;•循环处理实现迭代过程;•当相邻两次近似解之差的绝对值小于或等于给定误差,则认为最后一次得到的近似解即为问题的解。试想一下高次方程的求解软件技术基础分治法解一个复杂问题时,尽可能地把这个问题分解为较小部分,找出各个部分的解,然后再把各个部分的解组合成整个问题的解,这就是分治法。递归算法就是采用分治策略将问题分解为与原问题相似的子问题的分治法。复杂问题简单化,各个击破!!!软件技术基础回溯法回溯算法是所有搜索算法中最为基本的一种算法,采用了一种“走不通就掉头”的思想作为其控制策略,寻找可行解或所有解以及最优解。•确定起始状态值走第一步•确定下一步有几种可能•选一种可能,走下一步,记下可能与本步的特征•做完新一步应该做的事软件技术基础回溯法之八皇后问题•该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。•高斯认为有76种方案。•1854年在柏林的象棋杂志上不同的作者发表了40种不同的解•后来有人用图论的方法解出92种结果。软件技术基础动态规划法(dynamicprogramming)动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质:•最优子结构性质•子问题重叠性质软件技术基础动态规划法之拦截导弹•(问题来源:1999年全国青少年信息学(计算机)奥林匹克分区联赛高中组复赛试题第一题)某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,并依次输出被拦截的导弹飞来时候的高度。•样例:•INPUT•38920715530029917015865•OUTPUT•6(最多能拦截的导弹数)•38930029917015865软件技术基础分支界限法branch-and-bound过程Branch-Bound①QUEUE:=(s-s),g(s)=0;②LOOP:IFQUEUE=()THENEXIT(FAIL);③PATH:=FIRST(QUEUE),n:=LAST(PATH);④IFGOAL(n)THENEXIT(SUCCESS);⑤EXPAND(n)→{mi},计算g(mi)=g(n,mi),REMOVE(s-n,QUEUE),ADD(s-mi,QUEUE);⑥QUEUE中局部路径g值最小者排在前面;⑦GOLOOP;分支界限法是优先扩展当前具有最小耗散值分支路径的端节点n,其评价函数为f(n)=g(n)。该算法的基本思想很简单,实际上是建立一个局部路径(或分支)的队列表,每次都选耗散值最小的那个分支上的端节点来扩展,直到生成出含有目标节点的路径为止。软件技术基础4.3数据结构及表示(1)数据结构的概念(2)数据结构分类(3)数据的逻辑结构(4)数据的存储结构(5)数据存储结构分类(6)逻辑结构和存储结构的关系(7)数
本文标题:《算法与数据结构》PPT课件
链接地址:https://www.777doc.com/doc-4259540 .html