《算法设计与分析A》复习笔记

Author Avatar
source. 11月 22, 2018
  • 在其它设备中阅读本文章

哀吾生之须臾,羡长江之无穷。


本文为信息安全专业《算法设计与分析A》课程的复习方法、笔记。

复习 / 考试要点

把老师上课讲的每个知识点都吃透 + 反复练习。

平时及复习时要注意查缺补漏,不会的一定要向老师或同学询问,及时止损。

考试时要特别细心。

答题规范(套路):每题解答第一句话写上 XXXX 算法解决 XXX 问题,如:

动态规划法解决01背包问题

再开始作答。

保命战略:把每一步都写清楚(画清楚),这样如果中途出错还能拿点过程分,防止一分不得。

考试不难,即使不是上课讲过的内容一般也可以往上课讲过的内容上靠。

故遇到确实不会的题不要啥都不写,因为那样必然 0 分。

考得好不代表学得好(这一点对任何课都成立,同理成绩好不代表优秀)。

对于需要叙述的题,碰到那种既不好用自然语言也不好用编程语言描述的可以采用伪代码的形式。(此条废话

虽笔试不要求编程能力,但具备编程思想固然是一个优势。

第一章 概述

这章偏向概念,一般不会单独出题。时间复杂度可能结合后面章节的算法出题。

特别要注意一些非常经典的算法的时间复杂度的推导(如二分、归并排序等)。

img

img

img

img

第二章 分治

img

img

img

img

img

img

img

第三章 动态规划

这一章节为重中之重!

解答一般要具备最优解和最优值。

概念

img

img

矩阵连乘

img

img

img

流水作业调度

img

img

图像压缩

img

img

img

电路布线

img

img

0-1背包

img

最长公共子序列

img

img

第四章 贪心

活动安排问题

img

img

img

哈夫曼编码

img

单源最短路

img

最小生成树

img

img

第五、六章

回溯法

img

img

分支限界法(优先队列式)

img

img

禁止商用,非商业分享转载请注明来源。
本文链接:http://comydream.github.io/2018/11/22/algorithm-review/