2014年6月13日 (五) 16:31的最新版本

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方法：舍入；迭代；随机。
3. 广义的relaxation。

2014年4月4日

[课件下载]

1. 近似算法的基本概念：
   • 定义。
   • relative ration；approximation ratio；approximation algorithm。
   • GMS的原理及其近似比的证明。
   • PTAS、FPTAS及其区别。
2. NPO的分类。
3. stability：
   • 讨论stability的意义。
   • distance function；ball；p-stable；stable。
   • TSP中的distance；其它难问题中的distance。
   • PTAS的stability。
4. dual approximation：
   • 讨论dual approximation的意义。
   • distance function；ball；approximation algorithm；dual PTAS；dual FTPAS。
   • BIN-P中的distance；其它难问题中的distance。

2014年4月11日

[课件下载]

1. greedy和local search的异同。
2. MIN-VCP：基本思路；近似比及举例；时间复杂度及数据结构。
3. SCP：基本思路；近似比及举例；时间复杂度及数据结构；与MIN-VCP的区别。
4. greedy算法的设计与分析：longest simple path；MAX-SAT；MAX-CL；MAX-CUT。
5. MAX-CUT：基本思路；近似比及举例；时间复杂度及数据结构；与MIN-VCP的区别。
6. local search算法的设计与分析：longest simple path；MAX-SAT；MAX-CL；MIN-VCP；SCP。

2014年4月27日

1. SKP的PTAS：
   • 算法4.3.4.2的设计思路。
   • 为什么是SKP的PTAS。
   • 对于DIST为什么不是superstable；为什么不是KP_delta的PTAS。
2. KP的(F)PTAS：
   • 算法4.3.4.7的设计思路。
   • 对于DIST为什么是superstable；为什么是KP的PTAS。
   • 算法4.3.4.11的设计思路。
3. Delta-TSP的常数近似算法：
   • 算法4.3.5.1的设计思路及近似比证明。
   • 算法4.3.5.4的设计思路及近似比证明。
4. TSP问题的分类：
   • 算法4.3.5.18的设计思路。
   • 对于dist为什么是stable；如何对TSP进行分类。
   • p-strengthen triangle inequality如何对Delta-TSP进行分类。

2014年5月4日

[课件下载]

1. dual approximation algorithms：利用BIN-P求解MS的宏观步骤。
2. PTAS for MS：
   • BIN-P和MS的相互转化。
   • 利用BIN-P的解法求解MS：算法4.3.6.7。
3. dual PTAS for BIN-P：
   • 步骤1：动态规划的递归式；算法4.3.6.1及其复杂度。
   • 步骤2：对输入的处理；算法4.3.6.2及其证明。
   • 步骤3：对输入的分类处理；算法4.3.6.4及其证明。
4. 近似算法复习：
   • 伪多项式算法。
   • 分支-界限算法。
   • 局部搜索算法。
   • 松弛算法。
   • 贪心算法。
   • PTAS。
   • 稳定性。
   • 对偶近似算法。

2014年5月9日

[课件下载]

1. 随机算法的基本概念：从图灵机的角度理解随机算法。
2. 随机算法的时间复杂度：两种时间复杂度的计算方式及其存在的问题。
3. Las Vegas算法：和Monte Carlo算法的区别；两种定义的区别。
4. One-way communication protocol：
   • 直观含义。
   • Choice及其Las Vegas解法的直观含义。
   • Las Vegas解法的改造。
5. Monte Carlo算法：
   • one/two-sided-error Monte Carlo算法。
   • Monte Carlo算法的使用方式。
   • unbounded-和two-sided error Monte Carlo算法的区别。
6. 随机优化算法：
   • randomized delta-approximation和randomized delta-expected approximation算法之间的关系。
   • RPTAS及其与PTAS之间的区别。
7. 随机算法的设计范式：
   • Foiling an adversary。
   • Abundance of witnesses (& fingerprinting)。
   • Random sampling (& relaxation and random rounding)。

2014年5月16日

[课件下载]

1. random sampling：
   • 定义。
   • 适用的问题类型。
   • quadratic residues的适用性。
2. quadratic residues及其相关证明。
3. SSSA是单边错Monte Carlo算法的证明及其使用的局限性。
4. Miller-Rabin的基本原理。
5. prime generation的基本原理及其证明。
6. verifying matrix multiplication的单边错Monte Carlo算法。

2014年5月23日

[课件下载]

2014年5月30日

[课件下载]

2014年6月6日

[课件下载]

1. RSMS：要解决的问题；基本思路；近似比；效果。
2. RRRMS：基本思路；到LP的规约；引理5.3.6.3的证明；效果。
3. Schoening：要解决的问题；基本思路；时间复杂度；是单边Monte Carlo算法的原因。

2014年6月13日

[课件下载]

1. 去随机追求的目标：概率vs.确定；计算代价。
2. reduction of the probability space size：
   • 通过降低变量独立性来减小概率空间的基本思路，及其具体实现（定理5.4.2.2）。
   • 利用定理5.4.2.2来减少一个随机算法的random bits并最终去随机，及其具体实现（对于MAX-EkSAT）。
3. conditional probabilities：
   • 通过条件概率来去随机的基本思路：面向的问题；追求的目标；实现目标的方法/算法。
   • 算法的关键步骤（计算期望）及其具体实现（对于MAX-EkSAT和RSMS）。
   • 算法5.4.5.3、5.4.5.4、5.4.5.6要解决的问题。