算法基础课程大纲.

Presentation on theme: "算法基础课程大纲."— Presentation transcript:

1 算法基础课程大纲

2 第一讲 算法入门 内容提要： 课程学习背景 算法分析基础 算法设计策略之——分治法 两个例子：“插入排序”和“归并排序” 2019/5/30

3 第二讲 函数增长 内容提要： 渐近记号 定义：O, Ω, Θ, o, ω 证明例子 常用函数 级数求和 2019/5/30
第二讲 函数增长 内容提要： 渐近记号 定义：O, Ω, Θ, o, ω 证明例子 常用函数 级数求和 从数学角度介绍渐近符号及递归解法. 2019/5/30

4 第三讲 递归式 内容提要： 代换法 迭代法 递归树法 主方法 介绍一些解递归式的一些方法,对分析递归算法有用. 2019/5/30

5 第四讲 递归和分治策略 内容提要： 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧；
第四讲 递归和分治策略 内容提要： 通过例子理解递归的概念； 掌握设计有效算法的分治策略； 通过几个范例学习分治策略设计技巧； Merge sort Binary Search Powering a number Fibonacci number Multiplication of two matrices VLSI layout Multiplication of two numbers Finding Minimum and Maximum Majority problem (多数问题) 循环赛日程表 5

6 第五讲 概率分析与随机算法 内容提要： 雇用问题 指示器随机变量 随机算法 在线雇用问题 2019/5/30

7 第六讲 排序 内容提要： 排序问题 堆排序算法 快速排序算法 线性时间排序 排序算法比较 2019/5/30 7

8 第七讲 顺序统计学 内容提要： 最小值和最大值 以期望线性时间做选择 最坏情况线性时间的选择 2019/5/30

9 第八讲 红黑树及其扩张 内容提要： 红黑树性质 红黑树的操作 红黑树的扩张 2019/5/30

10 第九讲 动态规划 内容提要： 理解动态规划算法概念 掌握动态规划算法要素 掌握设计动态规划算法的步骤 通过范例学习动态规划算法设计策略
第九讲 动态规划 内容提要： 理解动态规划算法概念 掌握动态规划算法要素 掌握设计动态规划算法的步骤 通过范例学习动态规划算法设计策略 2019/5/30

11 第十讲 贪心算法 内容提要： 理解贪心算法的概念 掌握贪心算法的基本要素 理解贪心算法与动态规划算法的差异 通过范例学习贪心算法设计策略
2019/5/30

12 第十一讲 回溯法 内容提要： 理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 通过应用范例学习回溯法的设计策略 子集树算法框架
第十一讲 回溯法 内容提要： 理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 子集树算法框架 排列树算法框架 通过应用范例学习回溯法的设计策略 2019/5/30

13 第十二讲 分支限界法 内容提要： 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 通过应用范例学习分支限界法的设计策略
第十二讲 分支限界法 内容提要： 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架 （1）队列式(FIFO)分支限界法 （2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略 2019/5/30

14 第十三讲 随机算法 内容提要： 理解产生伪随机数的算法 掌握数值随机化算法的设计思想 掌握蒙特卡罗算法的设计思想
第十三讲 随机算法 内容提要： 理解产生伪随机数的算法 掌握数值随机化算法的设计思想 掌握蒙特卡罗算法的设计思想 掌握拉斯维加斯算法的设计思想 掌握舍伍德算法的设计思想 2019/5/30

15 第十四讲 有关数论算法 内容提要： 初等数论概念 最大公约数 模运算和模线性方程 中国余数定理 2019/5/30

16 第十六讲 NP完全性理论与近似算法 内容提要： 理解RAM，RASP和图灵机计算模型 理解非确定性图灵机的概念 理解P类与NP类语言的概念
理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题 （2）旅行售货员问题 （3）集合覆盖问题 （4）子集和问题

17 第十六讲 排序网络 内容提要： 比较网络 0-1原理 双调排序网络 合并网络 排序网络 2019/5/30