实验教学日历(算法)

《实验教学日历(算法)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、西南大学本科实验教学日历（2010-2011学年1学期）课程名称算法分析与设计讲课教师曹严元实验辅导教师曹严元年级专业人数2008级软件工程1、2班填表时间2010.9指导实验学时9学时自主实验2学时计算机与信息科学学院实验室实验室（中心）主任签字实验教材（指导书）：（名称、编者、出版社）王晓东编著《计算机算法设计与分析》第三版北京电子工业出版社2009年5月王晓东编著《算法设计与实验题解》北京电子工业出版社2008年11月参考书目：AnanyLevitin,潘彦译《算法设计与分析基础》北京清华大学出版社2004年6月时间实验内容实验学时实验类型备注第3周从日至日第4

2、周从日至日第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、实现背包问题的贪

3、心算法4、实现最短路径的贪心算法（任选一个完成）2设计第13周从日至日1、实现n皇后问题的回溯算法，作时空复杂性分析。2、上机实现分派问题（问题描述如下：给n个人分派n件工作，COST(i,j)为把工作j分配给第i个人的成本，要求在给每个人分派一件不同工作的情况下使总成本最小）的求解并作时空复杂性分析。3、写一进行邮票问题求解的回溯算法，上机实现该算法并作时空复杂性分析。（任选一个完成）3设计第14周从日至日1、实现0/1背包问题的LC分枝—限界算法，要求使用大小固定的元组表示动态状态空间树，与0/1背包问题回溯算法做复杂性比较。2、实现货郎担问题的分枝—限界算法并与

4、货郎担问题的动态规划算法做复杂性比较比较。3、实现带有期限的作业排序的分枝—限界算法并与带有期限的作业排序贪心算法做复杂性比较。（任选一个完成）2设计自主实验第15周从日至日第16周从日至日第17周从日至日第周从日至日资源分配问题资源分配问题是考虑如何把有限资源分配给若干个工程的问题。假设资源总数为r，工程个数为n。给每项工程投入的资源不同，所获得的利润也不同。要求把总数为r的资源，分配给n个工程，以获得最大利润的分配方案。流水线作业调度问题假设在一条流水线上有n个作业，每个作业要求执行m个任务：T1i，T2i，…Tmi，i在1到n之间。任务Tji只能在设备Pj上执行

5、，j从1到m。假定对于任一作业i，在任务Tj-1,i没有完成以前，不能对任务Tji开始处理，而且同一台设备在任何时刻不能同时处理一个以上的任务。如果假设完成任务Tji所要求的时间是tji，j在1到m之间，i在1到n之间，那么如何将这nXm个任务分配给这m台设备，才能使这n个作业在以上要求下顺利完成？带有期限的作业排序应用贪心设计策略来解决操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题。假定只能在一台机器上处理N个作业，每个作业均可在单位时间内完成；又假定每个作业i都有一个截止期限di>0（它是整数），当且仅当作业i在它的期限截止以前被完成时，则获

6、得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

7、和X4归并成Y2，最后归并Y1和Y2而得到想要的分类文件。给出n个文件，则有许多种把这些文件成对地归并成一个单一分类文件的方法。不同的配对法要求不同的计算时间。问题是确定一个把n个已分类文件归并在一起的最优方法（即需要最少比较的方法）像刚才所描述的归并模式称为二路归并模式（每一个归并步包含两个文件的归并）。二路归并模式可以用二元归并树来表示。叶结点被画成方块形，表示已知的文件。这些叶结点称为外部结点。剩下的结点被画成圆圈，称为内部结点。每个内部结点恰好有两个儿子，表示把它的两个儿子所表示的文件归并而得到的文件。每个结点中的数字都是那个结点所表示的文件