《2017算法设计及其高效实现教案.pdf》由会员分享，可在线阅读，更多相关《2017算法设计及其高效实现教案.pdf（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、安徽大学本科教学课程教案安徽大学本科教学课程教案课程名称：课程名称：算法设计及其高效实现算法设计及其高效实现课程代码：课程代码：开课单位：开课单位：安徽大学计算机科学与技术学院安徽大学计算机科学与技术学院授课教师：授课教师：职称职称/学位：学位：副教授副教授/博士博士开课时间：二一六至二一七学年第二学期开课时间：二一六至二一七学年第二学期第第1 1次课程教学方案次课程教学方案周次周次1教学教学第 1 章算法概述章节章节理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。目标目标掌握算法的计算复杂性概念。要求要求掌握算法渐近复杂性的数学表述。算法的计算复杂性概念。算法渐近复杂性的数学表述
2、。课时数课时数3重点重点难点难点教学教学方式方式媒体媒体资源资源课后课后作业作业课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：板板书书设设计计第第1 1次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容内容设计与手段内容设计与手段算法是什么，算法的具体实现。什么是程序，以及程序与算法的区别。算法是指解决问题的一种方法或一个过程。程序是算法用某种程序设计语言的具体实现。算法复杂性=算法所需要的计算机资源算法的时间复杂性 T(n)，算法的空间复杂性
3、 S(n)，其中 n 是问题的规模（输入大小）。O(g(n)=f(n)|存在正常数 c 和 n0 使得对所有 nn0，有：0 f(n)cg(n)(g(n)=f(n)|存在正常数 c 和 n0 使得对所有 n n0，有：0 cg(n)f(n)o(g(n)=f(n)|对于任何正常数 c0，存在正数和 n0 0 使得对所有 n n0 有：0 f(n)0，存在正数和 n0 0 使得对所有 n n0 有：0 cg(n)f(n)等价于f(n)/g(n)，asn。f(n)(g(n)g(n)o(f(n)归归纳纳总总结结理解算法，了解算法与程序之间的关系。懂得如何计算算法的复杂性，包括时间复杂度与空间复杂度。第
4、第2 2次课程教学方案次课程教学方案周次周次2教学教学第 1 章算法概述章节章节理解递归方程求解一般过程，掌握猜想法，迭代法。目标目标掌握主方法解递归方程要求要求迭代法、主方法重点重点理解递归方程和递归过程的关系。难点难点主要主要教学教学方式方式使用使用媒体媒体资源资源课后课后作业作业 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第2 2次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容内容设计与手段内容设计与
5、手段由上节了解的算法过程，理解一些具体的算法实现。理解递归方程求解一般过程，掌握猜想法，迭代法。掌握主方法解递归方程。用迭代法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。作为一个例子，考虑递归方程：接连迭代二次可将右端项展开为：由于对地板函数有恒等式：上式化简为：这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代i次后，将有：而且当时，方程解为T(n)=O(n)。用主方法为估计形如：T(n)=aT(n/b)+f(n)的递归方程解的渐近阶提供三个
6、可套用的公式，其中a1 和b1 是常数，f(n)是一个确定的正函数。该方程是一类分治法的时间复杂性所满足的递归关系，即一个规模为n 的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有该方程。归归纳纳总总结结通过具体例子来理解递归方程求解的一般过程。掌握了猜想法，迭代法等方法的算法流程。第第3 3次课程教学方案次课程教学方案周次周次3教学教学第1章 算法概述章节章节第 2 章递归与分治策略母函数求解
7、递归方程目标目标理解递归的概念。要求要求掌握设计有效算法的分治策略母函数方法重点重点理解递归方程和递归过程的关系难点难点如何针对一个具体问题设计一个有效的分治算法教学教学方式方式媒体媒体资源资源课后课后作业作业 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第3 3次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容用母函数求解递归方程理解递归的概念。掌握设计有效算法的分治策略给定满足一个给定递归的序列，可利用母函
8、数寻找依据 n 的 gn的闭形式，可通过下面四个步骤来获得 gn的闭形式。（1）写出依据序列的其他元素 gn 的单个方程，这个方程应对所有整数 n 成立，假设g-1=g-2=0。（2）用 zn乘方程两边，且在所有 n 上求和，左边给出和内容设计与手段内容设计与手段n，它是母函数 G(z)。g znn右边应进行操作，以致它变成涉及G(z)的某个其他表达式。（3）解产生的方程，取得G(z)的闭形式。（4）把 G(z)展成幂级数且读出 zn的系数，这是 gn的闭形式。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k 个子问题，
9、1m。从而使S1和S2分别位于直线 l 的左侧和右侧，且S=S1S2。由于 m 是 S 中各点 x 坐标值的中位数，因此S1和 S2中的点数大致相等。归归纳纳总总结结根据具体事例来理解 Strassen 矩阵乘法问题。了解到最接近点对问题的具体算法步骤。3第第6 6次课程教学方案次课程教学方案周次周次6教学教学第 3 章动态规划章节章节目标目标动态规划法要求要求重点重点掌握动态规法法的基本思想难点难点教学教学方式方式媒体媒体资源资源课后课后作业作业 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课
10、件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第6 6次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容学习新的算法。掌握动态规法法的基本思想。动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20 世纪 50 年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解
11、决这类过程优化问题的新方法动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，
12、称为多阶段决策问题。动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：1.阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,.,n 表示。2.状态状态(state)表示每个阶段开始时过程所处的自然状况。描述状态的变量称状态变量(statevariable)。变量允许取值的范围称允许状态集合(set of admissible states)。用 xk表示第 k 阶段的状态变量，它可以是一个数或一个向量。3.决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态
13、，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。4.策略决策组成的序列称为策略(policy)。5.状态转移方程6指标函数指标函数(objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k 到阶段 n 的指标函数用 Vkn(xk,pkn(xk)表示，k=1,2,.,n。能够用动态规划解决的问题的指标函数应具有可分离性，即 Vkn可表为 xk,uk,Vk+1 n的函数。7.最优策略和最优轨线理解了动态规划算法的具体思想。一个多阶段决策过程最优化问题的动态规划模型的具体表现。内容设计与手段内容设计与手段归归纳纳总总结
14、结第第7 7次课程教学方案次课程教学方案周次周次7教学教学第 3 章动态规划章节章节目标目标动态规划法要求要求重点重点掌握动态规法法的基本思想难点难点教学教学方式方式媒体媒体资源资源课后课后作业作业 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第7 7次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容内容设计与手段内容设计与手段基于理解动态规划算法。动态规划的问题中的最优化原理和无后效性。动态规划的实质是分治思
15、想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类 似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖 于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的(即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题 的解时，则难以通过局部的贪
16、心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共 的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个
17、显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后向性将
18、各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性设原问题的规模为 n，容易看出，当子问题树中的子问题总数是n 的超多项式函数，而不同的子问题数只是 n 的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。结合了上节，理解动态规划算法的具
19、体实现步骤以及其满足的条件，使用最优化原理和无后效性来优化动态规划算法。归归纳纳总总结结第第8 8次课程教学方案次课程教学方案周次周次8教学教学第 3 章动态规划章节章节目标目标通过实例理解动态规划法要求要求矩阵连乘积问题掌握动态规法法的基本思想重点重点难点难点教学教学方式方式媒体媒体资源资源课后课后作业作业 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第8 8次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容
20、内容设计与手段内容设计与手段通过上几节动态规划法的学习，用实例理解动态规划法。矩阵连乘积问题。给定 n 个矩阵A1,A2,An。其中 Ai与 Ai+1是可乘的，i=1,2,n-1。要求计算出这 n个矩阵的连乘积 A1A2An。下面我们来考虑用动态规划法解矩阵连乘积的最优计算次序问题。此问题是动态规划的典型应用之一。对于矩阵连乘积的最优计算次序问题，设计算Aij,1ijn，所需的最少数乘次数为mi,j，原问题的最优值为 m1,n。当 i=j 时，Aij=Ai为单一矩阵，无需计算，因此mi,i=0，i=1,2,n；当 ij 时，可利用最优子结构性质来计算 mi,j。事实上，若计算 Aij的最优次序
21、在 Ak和Ak+1之间断开，ikj，则：mi,j=mi,k+mk+1,j+pi-1pkpj由于在计算时我们并不知道断开点A 的位置，所以 A 还未定。不过 k 的位置只有 j-i个可能，即 ki,i+1,j-1。因此 k 是这 j-i 个位置中计算量达到最小的那一个位置。从而 mi,j可以递归地定义为：0i jmi,jminmi,kmk 1,j pi1pkpji jikjmi,j给出了最优值，即计算Aij所需的最少数乘次数。同时还确定了计算Aij的最优次序中的断开位置 k，也就是说，对于这个 k 有 mi,j=mi,k+mk+1,j+pi-1pkpj。若将对应于 mi,j的断开位置 k 记录在
22、 si,j中，则相应的最优解便可递归地构造出来。根据mi,j的递归定义，容易写一个递归程序来计算m1,n。稍后我们将看到，简单地递归计算2将耗费指数计算时间。然而，我们注意到，在递归计算过程中，不同的子问题个数只有(n)个。事实上，对于1ijn 不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有个。动态规划算法的一个变形是备忘录方法。与动态规划算法一样，备忘录方法用一个表格来保存已解决的子问题的答案，在再碰到该子问题时，只要简单地查看该子问题 的解答，而不必重新求解。不同的是，备忘录方法采用的是自顶向下的递归方式，而动态规划算法采用的是自底向上的非递归方式。我们看到，备忘
23、录方法的控制结 构与直接递归方法的控制结构相同，区别仅在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法解比用备忘录方法好。此时，动态规划算法没有任何多余的计算。同时，对于许多问题，常可 利用其规则的表格存取方式，来减少在动态规划算法中的计算时间和空间需求。当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题归归纳纳总总结结通过实例加深了对动态规划法的理解。理解了如何去解决矩阵连乘积问题。第第9 9次课程教学方案次课程教学方
24、案周次周次9教学教学第 3 章动态规划章节章节通过实例理解动态规划法目标目标最长公共子序列问题 LCS要求要求重点重点掌握动态规法法的基本思想难点难点主要主要教学教学方式方式使用使用媒体媒体资源资源作业作业或练或练习习 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第9 9次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课通过对动态规划法的理解。最长公共子序列问题 LCS。内容设计与手段内容设计与手段讲讲授授内内容容一个给定序列
25、的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X和 Y 的公共子序列。最长公共子序列(LCS)问题：给定两个序列X=和 Y=，要求找出 X 和 Y 的一个最长公共子序列。动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。最长公共子序列问题有最优子结构性质，因为我们有如下定理：定理:LCS 的最优子结构性质设序列 X=和 Y=的一个最长公共子序列Z=，则：若 xm=yn，则 zk=xm=yn且 Zk-1是 Xm-1和 Yn-1的最长公共子序列；若 xmyn且
26、 zkxm，则 Z 是 Xm-1和 Y 的最长公共子序列；若 xmyn且 zkyn，则 Z 是 X 和 Yn-1的最长公共子序列。其中 Xm-1=，Yn-1=，Zk-1=。由最长公共子序列问题的最优子结构性质可知，要找出X=和 Y=的最长公共子序列，可按以下方式递归地进行：当 xm=yn时，找出 Xm-1和 Yn-1的最长公共子序列，然后在其尾部加上 xm(=yn)即可得 X 和 Y 的一个最长公共子序列。当 xmyn时，必须解两个子问题，即找出 Xm-1和 Y 的一个最长公共子序列及 X 和 Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X 和 Y 的一个最长公共子序列。由此递归
27、结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X 和 Y的最长公共子序列时，可能要计算出 X 和 Yn-1及 Xm-1和 Y 的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和 Yn-1的最长公共子序列。与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用ci,j记录序列 Xi和 Yj的最长公共子序列的长度。其中Xi=，Yj=。当 i=0 或 j=0 时，空序列是 Xi和 Yj的最长公共子序列，故 ci,j=0。其他情况下，由定理可建立递归关系如下：容易写出一个计算 ci,j的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子
28、问题空间中，总共只有(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。归归纳纳总总结结了解最长公共子序列问题。通过使用动态规划算法可有效地解决最长公共子序列问题LCS。第第1010次课程教学方案次课程教学方案周次周次10教学教学第四章 贪心算法章节章节目标目标理解贪心算法的基本思想要求要求重点重点难点难点主要主要教学教学方式方式使用使用媒体媒体资源资源作业作业或练或练习习掌握贪心算法的基本思想课时数课时数3 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP
29、 课件 其他资源：板板书书设设计计第第1010次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容复习上章学习的动态规划算法思想。理解贪心算法的基本思想内容设计与手段内容设计与手段顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。对于一个具体的问题，怎么知
30、道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有 2 个重要的性质：贪心选择性质和最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2 类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?这是一个需要详细解释的问题。利用背包和 01 背包问题解释。对于 0-
31、1 背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1 背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1 背包问题借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。拟阵:拟阵 M 定义为满足下面 3 个条件的有序对(S,I)：(1)S 是非空有限集。(2)I 是 S 的
32、一类具有遗传性质的独立子集族，即若 BI，则 B 是 S 的独立子集，且 B的任意子集也都是 S 的独立子集。空集 必为 I 的成员。(3)I 满足交换性质，即若 AI,BI 且|A|B|，则存在某一元素 xB-A，使得 AxI。理解了什么事贪心算法，以及贪心算法的具体事例。掌握了贪心算法的基本思想。归归纳纳总总结结第第1111次课程教学方案次课程教学方案周次周次11教学教学第四章 贪心算法章节章节理解贪心算法的基本思想目标目标通过实例理解贪心算法的基本思想要求要求重点重点掌握贪心算法的基本思想难点难点如何对一个具体的问题设计贪心算法主要主要教学教学方式方式使用使用媒体媒体资源资源作业作业或练
33、或练习习 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第1111次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课讲讲授授内内容容理解贪心算法的基本思想通过实例理解贪心算法的基本思想内容设计与手段内容设计与手段活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源
34、。设有 n 个活动的集合 E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi,且 si fi。如果选择了活动 i，则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交，则称活动 i 与活动 j 是相容的。也就是说，当 sifj 或 sjfi 时，活动 i 与活动 j 相容。下面给出解活动安排问题的贪心算法GreedySelector:void GreedySelector(int n,Type s,Type f,bool A)A1=tr
35、ue;int j=1;for(int i=2;i=fj)Ai=true;j=i;else Ai=false;由于输入的活动以其完成时间的非减序排列，所以算法greedySelector 每次总是选择具有最早完成时间的相容活动加入集合A 中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy crit
36、erion）。从许多可以用贪心算法求解的问题中看到这类问题一般具有2 个重要的性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征通过实例理解了贪心算法
37、的基本思想。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。归归纳纳总总结结第第1212次课程教学方案次课程教学方案周次周次12教学教学章节章节目标目标复习要求要求重点重点难点难点主要主要教学教学方式方式使用使用媒体媒体资源资源作业作业或练或练习习 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源：课时数课时数3板板书书设设计计第第1212次教学活动设计次教学活动设计教学教学环节环节导导入入新新课课复习内容设计与手段内容设计与手段讲讲授授内内容容复习归归纳纳总总结结复习课程教案审核情况课程教案审核情况（新增专业课的教案应由教学系（教研室）主任或课程组负责人签署审核意见）主任/负责人签字：20年月日（新开课教师的教案应报院（系、部）教学委员会审定）院院（系、（系、部）部）教学委员教学委员会审定意会审定意见见教学委员会负责人签字：20年月日（新增专业课和新开课教师的教案均应报教学院长（主任）审批）教学院长（主任）签字：教学单位签章：20年月日教学系教学系（教（教研室）研室）或课或课程组审核程组审核意见意见院院（系、（系、部）部）审批意见审批意见