课程编号：1022114 总学时：32 学分：2
开课学期：秋季 开课学院：EECS 授课语言：中文
适用学科/专业：电子科学与技术/集成电路工程
课程类别：专业学位课 考核方式：考试
成绩评定：平时成绩，占比30%(其中思政成绩占比5%)；小组展示成绩，占20%；期末考试成绩，占比50%。
主要教学方式：
-
讲授
-
讨论
-
专题讲座
-
案例分析
-
自学
| 章节 | 标题 | 教学内容 | 学时分配 |
|---|---|---|---|
| 1 | 绪论 | 算法概念、性质及意义；问题求解流程；算法的例子与描述；复杂性的概念与计算；算法复杂性的渐近性态的数学表述；渐近阶的求解方法 | 2 |
| 2 | 递归与分治策略 | 递归的概念；递归方程构建的思想；阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题的递归算法分析；分治法的基本思想；二分查找、大整数的乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、循环赛日程表问题的算法分析 | 4 |
| 3 | 动态规划 | 动态规划算法的思想、特征和步骤；矩阵连乘积问题分析；动态规划算法的基本要素；备忘录的方法；0-1背包问题分析；最长公共子序列、最大子段和问题分析 | 8 |
| 4 | 贪心算法 | 贪心算法的概念、思想；贪心算法的基本要素；贪心算法的理论基础；背包问题分析；活动安排、最优装载问题分析；最小生成树的Prim、Kruskal算法；单源最短路径的Dijkstra算法 | 4 |
| 5 | 回溯法与分支限界法 | 回溯法的概念、思想和步骤；子集数、排列树、搜索树的构造；N后问题、着色问题分析；分支限界的概念、思想和步骤；0-1背包问题分析；作业调度问题 | 8 |
| 6 | 随机算法与智能算法 | 随机算法概述；蒙特卡罗算法；拉斯维加斯算法；舍伍德算法；蒙特卡罗算法、拉斯维加斯算法、舍伍德算法算的比较与应用；智能算法概述；遗传算法；模拟退火算法 | 6 |
主要参考书目：
| 名称 | 编者 | 出版社 | 版次 | 出版时间 |
|---|---|---|---|---|
| 《计算机算法设计与分析》 | 王晓东 | 电子工业出版社 | 第5版 | 2018.8 |
| 算法导论 （原书：Introduction to Algorithms，第3版） | T.H. Cormen, C.E. Leiserson等著，殷建平，徐云等译 | 机械工业出版社 | 第3版 | 2012.12 |
| 算法概论 （原书：Algorithms） | S. Dasgupta, C. Papadimitriou等著，王沛，唐扬斌等译 | 清华大学出版社 | 第1版 | 2008.7 |
| 算法设计 （原书：Algorithm Design） | J. Kleinberg, É. Tardos著，张立昂，屈婉玲译 | 清华大学出版社 | 第1版 | 2007.3 |
