实验教学日历(算法).docVIP

西南大学本科实验教学日历（ 2010-2011 学年 1 学期）课程名称 算法分析与设计 讲课教师 曹严元 实验辅导教师 曹严元 年级专业人数 2008级软件工程1、2班 填表时间 2010.9 指导实验学时 9 学时 自主实验 2 学时计算机与信息科学 学院 实验室实验室（中心）主任签字 实验教材（指导书）：（名称、编者、出版社）王晓东编著计算机算法设计与分析 第三版 北京 电子工业出版社 2009年5月王晓东编著算法设计与实验题解北京 电子工业出版社 2008年11月参考书目：Anany Levitin, 潘彦译 算法设计与分析基础 北京 清华大学出版社 2004年6月时间实验内容实验学时实验类型备注第3周从 日至 日第4周从 日至 日第5周从 日至 日第6周从 日至 日第7周从 日至 日第8周从 日至 日第9周从 日至 日第10周从 日至 日1、用分治策略写出并实现，二分法检索算法。2、实现一个“由底向上”的归并分类算法，要求取消栈空间的需要。3、实现斯特拉森矩阵乘法4、棋盘覆盖（任选一个完成）2设计第11周从 日至 日1、实现资源分配的动态规划算法。2、实现矩阵连乘的动态规划算法3、实现最长公共子序列的动态规划算法4、实现电路布线的动态规划算法5、实现m=2的流水线作业调度动态规划算法。（任选一个完成）2设计第12周从 日至 日1、用贪心法实现带有期限作业排序的快速算法。2、实现K元归并树贪心算法3、实现背包问题的贪心算法4、实现最短路径的贪心算法（任选一个完成）2设计第13周从 日至 日1、实现n皇后问题的回溯算法，作时空复杂性分析。2、上机实现分派问题（问题描述如下：给n个人分派n件工作，COST(i,j)为把工作j分配给第i个人的成本，要求在给每个人分派一件不同工作的情况下使总成本最小）的求解并作时空复杂性分析。3、写一进行邮票问题求解的回溯算法，上机实现该算法并作时空复杂性分析。（任选一个完成）3设计第14周从 日至 日1、实现0/1背包问题的LC分枝限界算法，要求使用大小固定的元组表示动态状态空间树，与0/1背包问题回溯算法做复杂性比较。2、实现货郎担问题的分枝限界算法并与货郎担问题的动态规划算法做复杂性比较比较。3、实现带有期限的作业排序的分枝限界算法并与带有期限的作业排序贪心算法做复杂性比较。（任选一个完成）2设计自主实验第15周从 日至 日第16周从 日至 日第17周从 日至 日第 周从 日至 日资源分配问题资源分配问题是考虑如何把有限资源分配给若干个工程的问题。假设资源总数为r，工程个数为n。给每项工程投入的资源不同，所获得的利润也不同。要求把总数为r的资源，分配给n个工程，以获得最大利润的分配方案。流水线作业调度问题假设在一条流水线上有n个作业，每个作业要求执行m个任务：T1i，T2i，Tmi，i在1到n之间。任务Tji 只能在设备Pj 上执行，j从1到m。假定对于任一作业i，在任务Tj-1,i没有完成以前，不能对任务Tji开始处理，而且同一台设备在任何时刻不能同时处理一个以上的任务。如果假设完成任务Tji所要求的时间是tji，j在1到m之间，i在1到n之间，那么如何将这nXm个任务分配给这m台设备，才能使这n个作业在以上要求下顺利完成？带有期限的作业排序应用贪心设计策略来解决操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题。假定只能在一台机器上处理N个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di0（它是整数），当且仅当作业i在它的期限截止以前被完成时，则获得pi的效益。这个问题的一个可行解是这N个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成。可行解的效益值是J中这些作业的效益之和，即p。具有最大效益值的可行解就是最优解。K元归并树两个分别包含n个和m个记录的已分类文件可以在O（n+m）时间内归并在一起而得到一个分类文件。当要把两个以上的已分类文件归并在一起时，可以通过成对地重复归并已分类的文件来完成。例如：假定X1,X2,X3,X4是要归并的文件，则可以首先把X1和X2归并成文件Y1，然后将Y1和X3归并成Y2，最后将Y2和X4归并，从而得到想要的分类文件；也可以先把X1和X2归并成Y1，然后将X3和X4归并成Y2，最后归并Y1和Y2而得到想要的分类文件。给出n个文件，则有许多种把这些文件成对地归并成一个单一分类文件的方法。不同的配对法要求不同的计算时间。问题是确定一个把n个已分类文件归并在一起的最优方法（即需要最少比较的方法）像刚才所描述的归并模式称为二路归并模式（每一个归并步包含两个文件的归并）。二路归并模式可以用二元归并树来表示。叶结点被画成方块形，表示已知的文件。这些叶结点称为外部结点。剩下的结点被画成圆圈，称为内部结点。每个内部结点恰好有两个儿子，表示把它的两个儿子所表示的文件归并而得到的文件。每个结点中的数字都是那个结点所表示的文件的长度（记录数）。一个i级结点在距离根为i-1的地方，在i级结点上的文件的记录都要移动i-1次。如果di是由根到代表文件Fi的外部结点的距离，qi是Fi的长度，则这颗二元归并树的记录移动总量是。这个和数叫做这颗树的带权外部路径长度。一个最优二路归并模式与一颗具有最小权外部路径的二元树相对应。生成归并树的贪心方法也适用于K路归并的情况。相应的归并树是一颗K元树。所有的内部结点的度数必须为K，所以对于n的某些值，就不与K元归并树相对应。例如：当K=3时，就不存在具有n=2个外部结点的K元归并树。所以有必要引进一定量的“虚”外部结点。每一个虚外部结点被赋以0值的qi。这个虚值不会影响所产生的K元树的带权外部路径长度。货郎担问题令G=（V,