计算机081-4算法设计与分析课程教学计划(教学日历).doc

周数 6 周学时 4+2 总学时 36 课堂教学 24 学时 实验课 12 学时其它（ ） 学时 课 程 教 学 计 划院系 计算机学院 专业 计算机 班级 08 1-4 2010-2011 学年 第 1 学期 课程 主讲 助课 采用 名称 算法分析与设计 教师 毛钧 教师 教材 算法设计与分析（第2版） 上课周次及时间课堂教学（包括讲课、习题课、课堂讨论、测验等）实验课其它（实习、课程设计、课外作业等）备注学时教学内容（教学大纲章、节和题目名称）学时实验内容学时内容第 12 周11月24日2第1章 算法引论1.1 算法与程序1.2 表达算法的抽象机制1.3 描述算法1.4 算法复杂性分析习题17第12 周11月26日2第2章 递归与分治策略2.1 递归的概念2.2 分治法的基本思想2.3 二分搜索技术2.4 大整数的乘法2.5 Strassen矩阵乘法2实验环境与课程意义第13周12月1日22.6 棋盘覆盖322.7 合并排序342.8 快速排序372.9 线性时间选择392.10 最接近点对问题432.11 循环赛日程表53习题54第13周12月3日2第3章 动态规划3.1 矩阵连乘问题目 录算法设计与分析(第2版)3.2 动态规划算法的基本要素3.3 最长公共子序列3.4 凸多边形最优三角剖分3.5 多边形游戏2循环赛日程表问题第14周12月8日23.6 图像压缩3.7 电路布线3.8 流水作业调度3.9 0-1背包问题3.10 最优二叉搜索树习题102第14周12月10日2第4章 贪心算法4.1 活动安排问题4.2 贪心算法的基本要素4.2.1 贪心选择性质4.2.2 最优子结构性质4.2.3 贪心算法与动态规划算法的差异4.3 最优装载4.4 哈夫曼编码4.4.1 前缀码4.4.2 构造哈夫曼编码4.4.3 哈夫曼算法的正确性2流水作业调度问题第15周12月15日24.5 单源最短路径4.6 最小生成树4.7 多机调度问题4.8 贪心算法的理论基础习题141第15周12月17日2第5章 回溯法5.1 回溯法的算法框架5.2 装载问题5.3 批处理作业调度5.4 符号三角形问题5.5 n后问题5.6 0|1背包问题5.7 最大团问题5.8 图的m着色问题5.9 旅行售货员问题5.10 圆排列问题5.11 电路板排列问题5.12 连续邮资问题5.13 回溯法的效率分析2多机调度问题习题191第16周12月22日2第6章 分支限界法6.1 分支限界法的基本思想6.2 单源最短路径问题6.3 装载问题6.4 布线问题6.5 0|1背包问题6.6 最大团问题6.7 旅行售货员问题6.8 电路板排列问题6.9 批处理作业调度习题238第16周12月24日2第7章 概率算法7.1 随机数7.2 数值概率算法7.3 舍伍德算法7.4 拉斯维加斯算法7.5 蒙特卡罗算法2旅行售货员问题习题273第17周12月29日2第8章 NP完全性理论8.1 计算模型8.2 P类与NP类问题8.3 NP完全问题8.4 一些典型的NP完全问题第9章 近似算法9.1 近似算法的性能9.2 顶点覆盖问题的近似算法9.3 旅行售货员问题近似算法9.4 集合覆盖问题的近似算法9.5 子集和问题的近似算法习题323第17周12月31日2第10章 算法优化策略10.1 算法设计策略的比较与选择10.2 动态规划加速原理10.3 问题的算法特征10.4 优化数据结构10.5 优化搜索策略第11章 在线算法设计11.1 在线算法设计的基本概念11.2 页调度问题11.3 势函数分析11.4 k服务问题11.5 Steiner树问题11.6 在线任务调度11.7 负载平衡2蒙特卡洛算法和近似算法习题388习题407第 周 月 日第 周 月 日第 周 月 日第 周 月 日第 周 月 日第 周 月 日第 周 月 日第 周 月 日第 周 月 日系（教研室）主任： 签字 院（系）领导： 签字 制定日期： 2 010年 9月 9 日说明：本表由任课教师负责填写，一式三份，一份留教师自用，一份交系（教研室），一份送教学研究科。