2017算法设计及其高效实现教案

安徽大学本科教学课程教案<X14tiI

f行号瞥诚课程名称： 算法设计及其高效实现课程代码： 开课单位： 安徽大学计算机科学与技术学院授课教师： 职^/学位： 副教授/博士 开课时间：二。一六至二。一七学年第二学期

周次1 课时数3教学章节第1章算法概述目标要求理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。重点难点算法的计算复杂性概念。算法渐近复杂性的数学表述。教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计

教学环节内容设计与手段导入新课算法是什么，算法的具体实现。什么是程序，以及程序与算法的区别。讲授内容算法是指解决问题的一种方法或一个过程。程序是算法用某种程序设计语言的具体实现。算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)，算法的空间复杂性S(n)，其中n是问题的规模(输入大小)。O(g(n))={f(n)1存在正常数c和n0使得对所有n>n0，有：0<f(n)<cg(n)}Q(g(n))={f(n)1存在正常数c和n0使得对所有n>n0，有：0<cg(n)<f(n)}o(g(n))={f(n)1对于任何正常数c>0，存在正数和n0>0使得对所有n>n0有：0<f(n)<cg(n)}等价于f(n)/g(n)-0，asn-8。3(g(n))={f(n)1对于任何正常数c>0，存在正数和n0>0使得对所有n>n0有：0<cg(n)<f(n)}等价于f(n)/g(n)8—，asn8—。f(n)e3(g(n))og(n)go(f(n))归纳总结理解算法，了解算法与程序之间的关系。懂得如何计算算法的复杂性，包括时间复杂度与空间复杂度。

周次2 课时数3教学章节第1章算法概述目标要求理解递归方程求解一般过程，掌握猜想法，迭代法。掌握主方法解递归方程重点难点迭代法、主方法理解递归方程和递归过程的关系。主要教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 使用媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计教学

环节导入教学

环节导入新课讲授内容内容设计与手段由上节了解的算法过程，理解一些具体的算法实现。理解递归方程求解一般过程，掌握猜想法，迭代法。掌握主方法解递归方程。用迭代法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。作为一个例子，考虑递归方程：『3=3翼快，43十甩接连迭代二次可将右端项展开为：=«+货值/44支/4j/4J)=«+货［累/4」+［题/4j/4j+3T(［LL^Mj/由于对地板函数有恒等式:|］_胤/邛上_|=［同/冼J上式化简为：=屋+3(［甩/4」+3(^/42J+3T(［«J43j))这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代i次后，将有:了⑻二厘+对题+卜尔判+…+%卜/屋_|+打…))时，『⑻=^+丸盟/4卜如/42J++/43J+---+如/4]J+灯⑼)…方程解为T(n)=O(n)。用主方法为估计形如：T(n)=aT(n/b)+f(n)的递归方程解的渐近阶提供三个可套用的公式，其中aN1和bN1是常数，f(n)是一个确定的正函数。该方程是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有该方程。通过具体例子来理解递归方程求解的一般过程。掌握了猜想法，迭代法等方法的算法流程。归纳总结周次3 课时数3教学章节第1章算法概述第2章递归与分治策略目标要求母函数求解递归方程理解递归的概念。掌握设计有效算法的分治策略重点难点母函数方法理解递归方程和递归过程的关系如何针对一个具体问题设计一个有效的分治算法教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计

教学环节内容设计与手段导入新课用母函数求解递归方程理解递归的概念。掌握设计有效算法的分治策略讲授内容给定满足一个给定递归的序列＜gn＞，可利用母函数寻找依据n的gn的闭形式，可通过下面四个步骤来获得gn的闭形式。(1)写出依据序列的其他元素gn的单个方程，这个方程应对所有整数n成立，假设g-1=g-2=・・.=0。(2)用z乘方程两边，且在所有n上求和，左边给出和 g&，它是母函数G(z)。n w〃右边应进行操作，以致它变成涉及G(z)的某个其他表达式。(3)解产生的方程，取得G(z)的闭形式。(4)把G(z)展成幂级数且读出Zn的系数，这是gn的闭形式。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1＜kWn，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。它的一般的算法设计模式如下：Divide-and-Conquer(P)if|P|Wn0thenreturn(ADHOC(P))将P分解为较小的子问题P1,P2,…，Pkfori-1tokdoyi-Divide-and-Conquer(Pi) △递归解决PiT-MERGE(y1,y2,...,yk) 1 △合并子问题return(T)但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡出出即c%g)子问题的思想，它几乎总是比子问题规模不等的做法要好。归纳总结知道如何使用母函数求解递归方程。可以设计有效算法的分治策略。

周次4 课时数3教学章节第二章递归与分治策略目标要求快速排序、大整数乘法重点难点根据实例理解分治法。分治法的问题分解和合并。教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计教学

环节

导

入教学

环节

导

入

新

课内容设计与手段理解快速排序、大整数乘法算法的实现分治法的问题分解和合并。讲授内容快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算1S」]就已排好序。设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，由此，X=A2n/2+B，Y=C2n/2+D。X=AB Y=CDn/2位n/2位 哂位n/2位这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD ⑴如果按式⑴计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式⑴中的加号)，此外还要做2次移位(分别对应于式⑴中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有：了⑴=1皿…”㈤⑵由此可得T(n)=O(n2)。因此，用⑴式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式：XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)虽然，式⑶看起来比式⑴复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。由此可得：产)=11s3X3(4)用解递归方程的套用公式法(主方法)马上可得其解为T(n)=O(nlog3)=O(m59)。归纳归纳总结通过例子了解了大整数乘法算法的实现

第上次课程教学方案周次5 课时数3教学章节第二章递归与分治策略目标要求Strassen矩阵乘法、最接近点对问题重点难点根据实例理解分治法。分治法的问题分解和合并。教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计教学

环节

导

入

新

课内容设计与手段教学

环节

导

入

新

课内容设计与手段Strassen矩阵乘法问题。最接近点对问题若A和B是2个nXn的矩阵，则它们的乘积C=AB同样是一个nXn的矩阵。A和B的乘积矩阵C中的元素C[i,j]定义为：讲授内容啡"卜士题1热]矶如用立二1若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素C[i,j],需要做n个乘法和n-1次加法。因此，求出矩阵C的n2个元素所需的计算时间为0(^)。60年代末，Strassen采用分治技术，将计算2个n阶矩阵乘积所需的计算时间改进到O(niog7)=0(n2.i8)。首先，我们还是需要假设n是2的幂。将矩阵A,B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个子矩阵都是n/2Xn/2的方阵。由此可将方程C=AB重写为：C21 C22(2)⑶(2)⑶⑷

个常数。因此，CiiABJAMiC12=A11b12+A12B22C21=A21b11+A22B212个n/2Xn/2矩阵的加法显然可以在c*m/4时间内完成，这里c是上述分治法的计算时间耗费T(n)应该满足:丁⑵=b* 0=附界＞2这个递归方程的解仍然是T(n)=O(n3)。因此，该方法并不比用原始定义直接计算更有效。最接近点对问题的提法是:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。此时S中的点为平面上的点，它们都有2个坐标值x和丫。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2,我们选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将5分割为S1={p£S|pxWm}和S2={p£S|px〉m}。从而使51和S2分别位于直线l的左侧和右侧，且S=S1US2。由于m"是S中各点x坐标值的中位数，因此S：和s2中的点数大致相等。 12归纳总结根据具体事例来理解Strassen归纳总结周次6 课时数3教学章节第3章动态规划目标要求动态规划法重点难点掌握动态规法法的基本思想教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计

教学环节内容设计与手段导入新课学习新的算法。掌握动态规法法的基本思想。讲授内容动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleof0Ptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—一动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：.阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用卜=1,2,..»表示。.状态状态於=@=6)表示每个阶段开始时过程所处的自然状况。描述状态的变量称状态变量(statevariable)。变量允许取值的范围称允许状态集合於6=ofadmissiblestates)。用*卜表示第k阶段的状态变量，它可以是一个数或一个向量。.决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。.策略决策组成的序列称为策略80反丫)。.状态转移方程6指标函数指标函数。勿Zc机e加碇而力是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用丫叁风鼻口风力表示，k=1,2,…,n。能够用动态规划解决的问题的指标函数应具有可分离性即Vk可表为xk，uk，Vk+1的函数。.最优策略和最优轨线归纳总结理解了动态规划算法的具体思想。一个多阶段决策过程最优化问题的动态规划模型的具体表现。

周次7 课时数3教学章节第3章动态规划目标要求动态规划法重点难点掌握动态规法法的基本思想教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计

教学环节内容设计与手段导入新课基于理解动态规划算法。动态规划的问题中的最优化原理和无后效性。讲授内容动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若千个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质.无后向性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性又称为无后效性。.子问题的重叠性设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。归纳总结结合了上节，理解动态规划算法的具体实现步骤以及其满足的条件，使用最优化原理和无后效性来优化动态规划算法。

周次8 课时数3教学章节第3章动态规划目标要求通过实例理解动态规划法矩阵连乘积问题重点难点掌握动态规法法的基本思想教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 课后作业板书设计

教学环节内容设计与手段导入新课通过上几节动态规划法的学习，用实例理解动态规划法。矩阵连乘积问题。讲授内容给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2，…,n-1。要求计算出这n个矩阵的连乘积A1A「・An。下面我们来考虑用动态规划法解矩阵连乘积的最优计算次序问题。此问题是动态规划的典型应用之一。对于矩阵连乘积的最优计算次序问题，设计算AJWiWjWn,所需的最少数乘次数为i…jm[i,j],原问题的最优值为m[1,n]。当i=j时，A.=A.为单一矩阵，无需计算，因此m[i,i]=0,i=1,2，…,n；当i<j时，可利用最优子结构性质来计算m[i,j]。事实上，若计算Ai…j.的最优次序在Ak和Ak+1之间断开，iWk<j,则：m[i,j]=m[i,k]+m[k+1,j]+pi^pkpj由于在计算时我们并不知道断开点A的位置，所以人还未定。不过k的位置只有j-i个可能，即k£{i,i+1,…，j-1}。因此k是这j-i个位置中计算量达到最小的那一个位置。从而m[i,j]可以递归地定义为：..J 0 i=jm",j]—<min{m[i,k]+m[k+1,j]+ppp}i<j[i<k<j i-1kjm[i,j]给出了最优值，即计算Ai…j.所需的最少数乘次数。同时还确定了计算Ai…j.的最优次序中的断开位置k,也就是说，对于这个k有m[i,j]=m[i,k]+m[k+1,j]+日“巴。若将对应于m[i,j]的断开位置k记录在s[i,j]中，则相应的最优解便可递归地构造出来。根据m[i,j]的递归定义，容易写一个递归程序来计算m[1,n]。稍后我们将看到，简单地递归计算将耗费指数计算时间。然而，我们注意到，在递归计算过程中，不同的子问题个数只有9S）个。事实上，对于1WiWjWn4同的有序对（1门）对应于不同的子问题。因此，不同子问题的个数最多只有个。动态规划算法的一个变形是备忘录方法。与动态规划算法一样，备忘录方法用一个表格来保存已解决的子问题的答案，在再碰到该子问题时，只要简单地查看该子问题的解答，而不必重新求解。不同的是，备忘录方法采用的是自顶向下的递归方式，而动态规划算法采用的是自底向上的非递归方式。我们看到」，备忘录方法的控制结构与直接递归方法的控制结构相同，区别仅在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法解比用备忘录方法好。此时，动态规划算法没有任何多余的计算。同时，对于许多问题，常可利用其规则的表格存取方式，来减少在动态规划算法中的计算时间和空间需求。当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题归纳总结通过实例加深了对动态规划法的理解。理解了如何去解决矩阵连乘积问题。第9次课程教学方案周次9 课时数3教学章节第3章动态规划目标要求通过实例理解动态规划法最长公共子序列问题LCS重点难点掌握动态规法法的基本思想主要教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 使用媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 作业或练习板书设计教学环节内容设计与手段导入新课通过对动态规划法的理解。最长公共子序列问题LCS。讲授内容一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列讲授内容一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列(LCS)问题：给定两个序列X=<x1,x2,…，xm〉和Y=<y1,y2,…，yn>,要求找出X和Y的一个最长公共子序列。 12 " 12n动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。最长公共子序列问题有最优子结构性质，因为我们有如下定理：定理：LCS的最优子结构性质设序列X=<x1,x2，…，Xm>和Y=<yi,丫2,，yn〉的一个最长公共子序列Z=<z1，z2，…，zk〉，则：若xm=yn,则Uzk=xm=若xmwyn且zkwxi若xmWyn且zkWy其中Xm-i=<xi,少…，:yn且Zk1是Xm1和Yn1的最长公共子序列；则Z是41和Y的最长公共子序列；,，则Z是?和Yn-1的最长公共子序列。Xm/，Yn-1=<y1，丫2，…，，-1〉，"勺◎由最长公共子序列问题的最优子结构性质可知，要找出X=<x1,，zk-i〉。%，…，x〉和Y=<y1,yn〉的最长公共子序列，可按以下方式递归地进行：当xm二yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上x(=y)即可得X和Y的一个最长公共子序列。当xWy时，必须解两个子问题，即找出X和Y的一个最长公共子序列及X和Y的一个最长公共m-1n-1子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn1及Xm1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm1和丫；的最长公共子序列。yj〉。当i=0或j=0时，空序列是X定理可建立递归关系如下：fo与矩阵连乘积最优计算次序问题类似:我们来建立子问题的最优值的递归关系。用c[i，j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1，x2，…，xiyj〉。当i=0或j=0时，空序列是X定理可建立递归关系如下：fo和Yj的最长公共子序列，故c[i，j]=0。其他情况下，由当f=口我=0时-1J-1]+1m招(亡瓦-1J-1]+1m招(亡瓦j-1]国[工-L用)容易写出一个计算c[i，j]的递归算法当山》口且巧.u打时但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有O(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。归纳归纳总结通过使用动态规划算法可有效地解决最长公共子序列问题LCS。

周次10 课时数3教学章节第四章贪心算法目标要求理解贪心算法的基本思想重点难点掌握贪心算法的基本思想主要教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 使用媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 作业或练习板书设计

教学环节内容设计与手段导入新课复习上章学习的动态规划算法思想。理解贪心算法的基本思想讲授内容顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢？这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解？是否能用动态规划算法求解的问题也能用贪心算法求解?这是一个需要详细解释的问题。利用背包和0—1背包问题解释。对于0T背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。拟阵：拟阵M定义为满足下面3个条件的有序对⑸I)：(1)S是非空有限集。(2)1是S的一类具有遗传性质的独立子集族，即若Bel,则B是S的独立子集，且B的任意子集也都是S的独立子集。空集0必为I的成员。⑶I满足交换性质，即若AeI,BeI且|A|<|B|,则存在某一元素xeB-A,使得AU{x}eI。归纳总结理解了什么事贪心算法，以及贪心算法的具体事例。掌握了贪心算法的基本思想。

周次11 课时数3教学章节第四章贪心算法目标要求理解贪心算法的基本思想通过实例理解贪心算法的基本思想重点难点掌握贪心算法的基本思想如何对一个具体的问题设计贪心算法主要教学方式■课堂讲授 口小组活动 口实验演示 □难点答疑 口提问□作业讲评 口实践教学 口考试测验 口其他活动 使用媒体资源□文字教材 ■电子教案 口录像材料 口录音材料 口直播课堂□CAI课件 口IP课件 口其他资源： 作业或练习板书设计

教学环节内容设计与手段导入新课理解贪心算法的基本思想通过实例理解贪心算法的基本思想讲授内容活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争^一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动