2012级--讨论记录 (第四学期)
来自问题求解
2014年2月21日
-
字母表、词、语言：
- 形式化定义。
- 实际应用：编码考试成绩；编码图片；编码视频。
- concatenation和subword的形式化定义。
- canonical ordering。
-
判定和优化问题：
- 判定问题的定义和例子。
- 优化问题的定义和例子。
-
P和NP：
- upper bound和lower bound。
- P、NP、NP-hard、NP-complete。
- 确定性和非确定性。
- NPO和PO。
2014年2月28日
- 判定问题和优化问题：优化问题向判定问题的转换。
-
P：
- P问题的几个特点。
- 编码：对讨论复杂性的影响；回避的手段。
- decide和accept的区别和联系。
-
NP：
- certificate及其验证。
- P和NP：可解 vs. 可验证；确定性 vs. 非确定性。
-
NP-C：
- 规约及其性质。
- 基于规约来定义NP-hard和NP-C。
- NP-C的证明方法和例子。
2014年3月14日
- Lowering Worst Case Complexity of Exponential Algorithms：3SAT和divide-and-conquer。
-
branch-and-bound：
- 提高效率的基本原理。
- 算法设计的几个重要方面：树的构造方法，树的搜索策略，子树中解的范围的估计，初始最优解的界。
- 典型问题：MAX-SAT，TSP，NNS，ILP，QAP。
2014年3月21日
-
local search的基本概念：
- feasible solution、specification、transformation、neighborhood、local optimum。
- total correctness的证明。
- 框架的可变环节：alpha、Neigh、beta。
- 各种策略：hill climbing；very large-scale neighborhood search及variable-depth search；multi-start methods及GRASP；Stochastic hill climbing；Tabu search。
- local search的性能：关键环节；exact polynomial-time searchable neighborhood。
- 应用：longest simple path、MAX-SAT、MAX-CL、MIN-VCP。
2014年3月28日
- 用0-1规划建模：0-1 KP；multiple KP；0-1 multidimensional KP；SCP；MS；MAX-SAT；facility location problem；WEIGHT-VCP；maximum matching；WEIGHT-CL；TSP。
-
rounding：
- 什么是一个好的rounding：可行；较优。
- rounding方法：舍入；迭代；随机。
- 广义的relaxation。
2014年4月4日
-
近似算法的基本概念：
- 定义。
- relative ration；approximation ratio；approximation algorithm。
- GMS的原理及其近似比的证明。
- PTAS、FPTAS及其区别。
- NPO的分类。
-
stability：
- 讨论stability的意义。
- distance function；ball；p-stable；stable。
- TSP中的distance；其它难问题中的distance。
- PTAS的stability。
-
dual approximation：
- 讨论dual approximation的意义。
- distance function；ball；approximation algorithm；dual PTAS；dual FTPAS。
- BIN-P中的distance；其它难问题中的distance。
2014年4月11日
- greedy和local search的异同。
- MIN-VCP：基本思路；近似比及举例；时间复杂度及数据结构。
- SCP：基本思路；近似比及举例；时间复杂度及数据结构；与MIN-VCP的区别。
- greedy算法的设计与分析：longest simple path；MAX-SAT；MAX-CL；MAX-CUT。
- MAX-CUT：基本思路；近似比及举例；时间复杂度及数据结构；与MIN-VCP的区别。
- local search算法的设计与分析：longest simple path；MAX-SAT；MAX-CL；MIN-VCP；SCP。
