实验教学日历(算法).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是要归并的文件，则可以