2016级--小班讨论 (第四学期)

2018年3月7日

[课件下载]

1. 字母表、词、语言。
2. 判定和优化问题。
3. P和NP。

2018年3月14日

[课件下载]

1. 判定问题和优化问题。
2. P。
3. NP。
4. NP-hard与NPC。

2018年3月21日

[课件下载]

1. 伪多项式时间算法。
2. strongly NP-hard。
3. 参数化。

2018年3月28日

[课件下载]

1. Lowering Worst Case Complexity of Exponential Algorithms。
2. branch-and-bound。

2018年4月4日

[课件下载]

1. local search的基本概念。
2. hill climbing。
3. very large-scale neighborhood search。
4. multi-start methods。
5. stochastic hill climbing。
6. tabu search。
7. local search的性能。
8. 应用。

2018年4月11日

[课件下载]

1. 用0-1规划建模。
2. rounding。
3. 广义的relaxation。

2018年4月18日

[课件下载]

1. 近似算法的基本概念。
2. stability。

2018年4月25日

[课件下载]

1. greedy vs. local search。
2. MIN-VCP。
3. SCP。
4. MAX-CUT。
5. greedy和local search。

2018年5月2日

[课件下载]

1. 4.3.4.1。
2. 4.3.4.2(用于SKP)。
3. 4.3.4.2(用于KP)。
4. 4.3.4.7。
5. 4.3.4.11。

2018年5月9日

[课件下载]

1. 算法4.3.5.1。
2. 算法4.3.5.4。
3. 算法4.3.5.18。

2018年5月16日

[课件下载]

1. dual approximation algorithms。
2. dual PTAS for BIN-P。
3. PTAS for MS。
4. (近似)算法复习。

2018年5月23日

[课件下载]

1. 随机算法的基本概念。
2. Las Vegas算法。
3. Monte Carlo算法。
4. 随机优化算法。
5. 随机算法的设计范式。

2018年5月30日

[课件下载]

1. random sampling and Las Vegas。
2. abundance of witnesses and one-sided-error Monte Carlo。

2018年6月6日

[课件下载]

1. NEQ-POL。
2. NEQ-1BP。
3. 重访Rabin-Karp。

2018年6月13日

[课件下载]