算法设计与分析
算法设计与分析
4万+ 人选课
更新日期:2025/05/27
开课时间2024/09/03 - 2024/12/15
课程周期15 周
开课状态已结课
每周学时-
课程简介

本课程主要介绍算法设计与分析的基本方法以及算法复杂性理论基础。通过本课程的学习,要求学生理解并熟练掌握递归与分治法、贪心法、动态规划方法、回溯法、分支定界法,以及高级图论算法、线性规划算法等,理解并掌握算法复杂性的分析方法、NP完全性理论基础等计算复杂性的基本知识及完备性证明概要。

 

课程大纲
算法概述及复杂性理论(授课人:张德富,曾华琳;总时长:1小时32分)
1 问题
2 算法的概念
3 算法的正确性
4 算法的效率
5 问题的下界
算法分析方法(授课人:张德富;总时长:1小时37分)
1 概率分析
2 合计方法
3 记账方法
4 势能方法
5 实验分析
递归(授课人:张德富;总时长:1小时19分)
1 递归的算法思想
2 选择排序
3 生成排列
4 递归方程的求解
分治(上)(授课人:曾华琳;总时长:1小时31分)
1 算法思想
2 二分搜索
3 快速排序
4 归并排序
分治(下)与动态规划(上)(授课人:曾华琳;总时长:1小时35分)
1 残缺棋盘游戏
2 大整数乘法
3 矩阵乘法
4 动态规划引言
5 动态规划算法思想
6 矩阵链乘法问题
动态规划(中)(授课人:张德富,曾华琳;总时长:1小时38分)
1 最优二叉搜索树问题
2 最大字段和问题
3 装配线调度问题
4 最长公共子序列问题
动态规划(下)与贪心算法(上)(授课人:张德富;总时长:1小时33分)
1 0/1背包问题
2 动态规划的基本性质
3 贪心算法思想
4 任务选择问题(上)
贪心算法(下)(授课人:曾华琳;总时长:1小时49分)
1 任务选择问题(下)
2 背包问题
3 哈夫曼编码问题
4 任务选择实验
图算法(上)(授课人:张德富;总时长:1小时19分)
1 图的表示
2 宽度优先搜索
3 深度优先搜索
4 最小生成树问题--Kruskal算法
图算法(下)(授课人:张德富;总时长:1小时21分)
1最小生成树问题--Kruskal 与 Prim 比较
2 最短路径问题
3 单源最短路径问题
4 所有点对的最短路径问题
网络流与匹配(授课人:张德富;总时长:1小时38分)
1 最大流问题
2 最大流问题求解
3 最小费用流
回溯(授课人:曾华琳;总时长:1小时27分)
1 算法思想
2 货箱装载问题
3 0-1背包问题
4 着色问题
分支限界(授课人:曾华琳;总时长:1小时29分)
1 算法思想
2 装载问题
3 0/1背包问题
4 旅行商问题
NP完全理论(授课人:张德富;总时长:1小时31分)
1 判定问题
2 P和NP问题
3 NPC的定义
4 电路可满足性问题
5 NPC的证明