2012级--讨论记录 (第四学期)

2014年2月21日

[课件下载]

1. 字母表、词、语言：
   • 形式化定义。
   • 实际应用：编码考试成绩；编码图片；编码视频。
   • concatenation和subword的形式化定义。
   • canonical ordering。
2. 判定和优化问题：
   • 判定问题的定义和例子。
   • 优化问题的定义和例子。
3. P和NP：
   • upper bound和lower bound。
   • P、NP、NP-hard、NP-complete。
   • 确定性和非确定性。
   • NPO和PO。

2014年2月28日

[课件下载]

1. 判定问题和优化问题：优化问题向判定问题的转换。
2. P：
   • P问题的几个特点。
   • 编码：对讨论复杂性的影响；回避的手段。
   • decide和accept的区别和联系。
3. NP：
   • certificate及其验证。
   • P和NP：可解 vs. 可验证；确定性 vs. 非确定性。
4. NP-C：
   • 规约及其性质。
   • 基于规约来定义NP-hard和NP-C。
   • NP-C的证明方法和例子。

2014年3月14日

[课件下载]

1. Lowering Worst Case Complexity of Exponential Algorithms：3SAT和divide-and-conquer。
2. branch-and-bound：
   • 提高效率的基本原理。
   • 算法设计的几个重要方面：树的构造方法，树的搜索策略，子树中解的范围的估计，初始最优解的界。
   • 典型问题：MAX-SAT，TSP，NNS，ILP，QAP。

2014年3月21日

[课件下载]

1. local search的基本概念：
   • feasible solution、specification、transformation、neighborhood、local optimum。
   • total correctness的证明。
   • 框架的可变环节：alpha、Neigh、beta。
2. 各种策略：hill climbing；very large-scale neighborhood search及variable-depth search；multi-start methods及GRASP；Stochastic hill climbing；Tabu search。
3. local search的性能：关键环节；exact polynomial-time searchable neighborhood。
4. 应用：longest simple path、MAX-SAT、MAX-CL、MIN-VCP。

2014年3月28日

[课件下载]

1. 用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。
2. rounding：
   • 什么是一个好的rounding：可行；较优。
   • rounding方法：舍入；迭代；随机。
   • 广义的relaxation。