“2012级--讨论记录 (第四学期)”的版本间的差异
来自问题求解
第210行: | 第210行: | ||
<li>稳定性。</li> | <li>稳定性。</li> | ||
<li>对偶近似算法。</li> | <li>对偶近似算法。</li> | ||
+ | </ul> | ||
+ | </li> | ||
+ | </ol> | ||
+ | |||
+ | |||
+ | =2014年5月9日= | ||
+ | [[媒体文件:讨论记录-第四学期-第10次.pdf|[课件下载]]] | ||
+ | <ol> | ||
+ | <li>随机算法的基本概念:从图灵机的角度理解随机算法。</li> | ||
+ | <li>随机算法的时间复杂度:两种时间复杂度的计算方式及其存在的问题。</li> | ||
+ | <li>Las Vegas算法:和Monte Carlo算法的区别;两种定义的区别。</li> | ||
+ | <li> | ||
+ | One-way communication protocol: | ||
+ | <ul> | ||
+ | <li>直观含义。</li> | ||
+ | <li>Choice及其Las Vegas解法的直观含义。</li> | ||
+ | <li>Las Vegas解法的改造。</li> | ||
+ | </ul> | ||
+ | </li> | ||
+ | <li> | ||
+ | Monte Carlo算法: | ||
+ | <ul> | ||
+ | <li>one/two-sided-error Monte Carlo算法。</li> | ||
+ | <li>Monte Carlo算法的使用方式。</li> | ||
+ | <li>unbounded-和two-sided error Monte Carlo算法的区别。</li> | ||
+ | </ul> | ||
+ | </li> | ||
+ | <li> | ||
+ | 随机优化算法: | ||
+ | <ul> | ||
+ | <li>randomized delta-approximation和randomized delta-expected approximation算法之间的关系。</li> | ||
+ | <li>RPTAS及其与PTAS之间的区别。</li> | ||
+ | </ul> | ||
+ | </li> | ||
+ | <li> | ||
+ | 随机算法的设计范式: | ||
+ | <ul> | ||
+ | <li>Foiling an adversary。</li> | ||
+ | <li>Abundance of witnesses (& fingerprinting)。</li> | ||
+ | <li>Random sampling (& relaxation and random rounding)。</li> | ||
</ul> | </ul> | ||
</li> | </li> | ||
</ol> | </ol> |
2014年5月9日 (五) 16:30的版本
目录
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。
2014年4月27日
-
SKP的PTAS:
- 算法4.3.4.2的设计思路。
- 为什么是SKP的PTAS。
- 对于DIST为什么不是superstable;为什么不是KP_delta的PTAS。
-
KP的(F)PTAS:
- 算法4.3.4.7的设计思路。
- 对于DIST为什么是superstable;为什么是KP的PTAS。
- 算法4.3.4.11的设计思路。
-
Delta-TSP的常数近似算法:
- 算法4.3.5.1的设计思路及近似比证明。
- 算法4.3.5.4的设计思路及近似比证明。
-
TSP问题的分类:
- 算法4.3.5.18的设计思路。
- 对于dist为什么是stable;如何对TSP进行分类。
- p-strengthen triangle inequality如何对Delta-TSP进行分类。
2014年5月4日
- dual approximation algorithms:利用BIN-P求解MS的宏观步骤。
-
PTAS for MS:
- BIN-P和MS的相互转化。
- 利用BIN-P的解法求解MS:算法4.3.6.7。
-
dual PTAS for BIN-P:
- 步骤1:动态规划的递归式;算法4.3.6.1及其复杂度。
- 步骤2:对输入的处理;算法4.3.6.2及其证明。
- 步骤3:对输入的分类处理;算法4.3.6.4及其证明。
-
近似算法复习:
- 伪多项式算法。
- 分支-界限算法。
- 局部搜索算法。
- 松弛算法。
- 贪心算法。
- PTAS。
- 稳定性。
- 对偶近似算法。
2014年5月9日
- 随机算法的基本概念:从图灵机的角度理解随机算法。
- 随机算法的时间复杂度:两种时间复杂度的计算方式及其存在的问题。
- Las Vegas算法:和Monte Carlo算法的区别;两种定义的区别。
-
One-way communication protocol:
- 直观含义。
- Choice及其Las Vegas解法的直观含义。
- Las Vegas解法的改造。
-
Monte Carlo算法:
- one/two-sided-error Monte Carlo算法。
- Monte Carlo算法的使用方式。
- unbounded-和two-sided error Monte Carlo算法的区别。
-
随机优化算法:
- randomized delta-approximation和randomized delta-expected approximation算法之间的关系。
- RPTAS及其与PTAS之间的区别。
-
随机算法的设计范式:
- Foiling an adversary。
- Abundance of witnesses (& fingerprinting)。
- Random sampling (& relaxation and random rounding)。