实验学时:18
序号 教学内容 课堂讲授 习题课 讨论课 上机实验
1 算法引论 4
2 递归与分治策略 6 2
8
3 贪心算法 4
4 动态规划 4
4
5 回溯法 5
6
6 分支限界法 5
7 NP完全性理论简介 2 2 2
合计 36 18
五、实验内容及安排
《算法设计与分析》课程是一门理论与实践性并重的课程,它不仅要求掌握学习算法设计的主要策略方法,而且还要掌握算法设计的实现.
本课程实验目的是验证、巩固和补充课堂讲授的理论知识.培养学生初步具备独立设计算法和对给定算法进行复杂性分析的能力,为实际工作打下基础.
实验的安排和要求是:用程序实现经典算法,学习算法设计的主要策略方法、原理并根据实例加以调试,培养动手设计、分析和综合实验结果以及撰写实验报告的能力.在实验中养成严肃认真的治学态度和踏实细致、实事求是的作风. 实验内容如下:
序号实验名称 内容提要 学时 每组
人数 类型 开出
要求
1 分治与递归
对多项式乘积、循环赛、棋盘覆盖、Strassen矩阵乘积等问题任选其一,设计或理解算法,实现软件.并对乘积问题的计算时间进行分析. 8 1 设计 必做
2 动态规划
资源分配、0/1背包问题等问题任选其一,设计算法,实现软件,并分析算法正确性. 4 1 验证 必做
2 回溯
N后问题、迷宫问题等问题任选其一,设计算法,实现软件,分析其复杂度. 6 1~2 综合 必做
合计 18
六、成绩考核方法
本课程的考核分为平时作业成绩、实验成绩以及期末考试成绩三大部分,其中期末考试以卷笔试为主.总成绩按以下公式计算:
总成绩=(平时成绩+实验成绩)*(30%~40%)+期末成绩*(70%~60%)
七、教材及主要参考书
1.教材
郑宗汉,郑晓明 算法设计与分析 清华大学出版社
2.主要参考书:
[1] 潘彦译([美] Anany Levitin),算法设计与分析基础(Introduction to Design and Analysis of Algorithms),清华大学出版社,2004.6
[2] 王晓东,计算机算法设计与分析(第2版),电子工业出版社,2004.7
执笔人:张艳/2010.9 审核人:王华民 /2010.9

上一页