算法设计与分析学习笔记

1、课堂关键字

• 算法分析与问题的计算复杂度

2、预习作业

第9章 NP完全性

（*）9.1 P类与NP类
        9.1.1 易解的问题与难解的问题
        9.1.2 判定问题
        9.1.3 NP类

（6）9.2 多项式实践变换与NP完全性
         9.2.1 多项式时间变换
         9.2.2 NP完全性及其性质
         9.2.3 Cook-Levin定理--第一个NP完全问题

        9.3 几个NP完全问题
（3）9.3.1 最大可满足性与三元可满足行
（2）9.3.2 定点覆盖、团与独立集
（1）9.3.3 哈密顿回路与货郎问题
（0）9.3.4 恰好覆盖
（5）9.3.5 子集和、背包、装箱与双机调度
（4）9.3.6 整数线性规划

按（座位号%7）的准备相关内容（PPT+讲解）
（*）：全员准备
%：“求余”运算