算法设计与分析
算法设计与分析课程
1
贪心算法，蛮力算法
问题求解的关键
建模：对输入参数和解给出形式化或半形式化的描述
设计算法：采用什么算法设计技术，正确性——是否对所有的实例都得到正确的解
分析算法——效率
目标函数，约束条件
运筹学
递归树是迭代的模型
1.1 问题的计算复杂度：排序问题
1.2 货郎问题与计算复杂度
1.3 算法及其时间复杂度
1.4 算法的伪码表示
1.5 算法的渐进的界
1.6 有关函数渐进的界的定理
1.7 几类重要的函数
2
2.1 序列求和的方法
2.2 递推方程与算法分析
2.3 迭代法求解递推方程
2.4 差消法求
2.5 递归树
2.6 主定理及其证明
2.7 主定理的应用
迭代推时间复杂度，不能使用定理的，可以使用递归树求解
3 分治算法的设计思想与分析方法
3.1 分治策略的设计思想
3.2 分治算法的一般描述和分析方法
二分检索
二分归并排序
Hanoi塔的递归算法
3.3 芯片测试
蛮力算法
