查看“2012级--讨论记录 (第四学期)”的源代码

=2014年2月21日=
[[媒体文件:讨论记录-第四学期-2班-第1次.pdf|[课件下载]]]
<ol>
  <li>
    字母表、词、语言：
    <ul>
      <li>形式化定义。</li>
      <li>实际应用：编码考试成绩；编码图片；编码视频。</li>
      <li>concatenation和subword的形式化定义。</li>
      <li>canonical ordering。</li>
    </ul>
  </li>
  <li>
    判定和优化问题：
    <ul>
      <li>判定问题的定义和例子。</li>
      <li>优化问题的定义和例子。</li>
    </ul>
  </li>
  <li>
    P和NP：
    <ul>
      <li>upper bound和lower bound。</li>
      <li>P、NP、NP-hard、NP-complete。</li>
      <li>确定性和非确定性。</li>
      <li>NPO和PO。</li>
    </ul>
  </li>
</ol>

=2014年2月28日=
[[媒体文件:讨论记录-第四学期-2班-第2次.pdf|[课件下载]]]
<ol>
  <li>判定问题和优化问题：优化问题向判定问题的转换。</li>
  <li>
    P：
    <ul>
      <li>P问题的几个特点。</li>
      <li>编码：对讨论复杂性的影响；回避的手段。</li>
      <li>decide和accept的区别和联系。</li>
    </ul>
  </li>
  <li>
    NP：
    <ul>
      <li>certificate及其验证。</li>
      <li>P和NP：可解 vs. 可验证；确定性 vs. 非确定性。</li>
    </ul>
  </li>
  <li>
    NP-C：
    <ul>
      <li>规约及其性质。</li>
      <li>基于规约来定义NP-hard和NP-C。</li>
      <li>NP-C的证明方法和例子。</li>
    </ul>
  </li>
</ol>

=2014年3月14日=
[[媒体文件:讨论记录-第四学期-2班-第3次.pdf|[课件下载]]]
<ol>
  <li>Lowering Worst Case Complexity of Exponential Algorithms：3SAT和divide-and-conquer。</li>
  <li>
    branch-and-bound：
    <ul>
      <li>提高效率的基本原理。</li>
      <li>算法设计的几个重要方面：树的构造方法，树的搜索策略，子树中解的范围的估计，初始最优解的界。</li>
      <li>典型问题：MAX-SAT，TSP，NNS，ILP，QAP。</li>
    </ul>
  </li>
</ol>

=2014年3月21日=
[[媒体文件:讨论记录-第四学期-2班-第4次.pdf|[课件下载]]]
<ol>
  <li>
    local search的基本概念：
    <ul>
      <li>feasible solution、specification、transformation、neighborhood、local optimum。</li>
      <li>total correctness的证明。</li>
      <li>框架的可变环节：alpha、Neigh、beta。</li>
    </ul>
  </li>
  <li>各种策略：hill climbing；very large-scale neighborhood search及variable-depth search；multi-start methods及GRASP；Stochastic hill climbing；Tabu search。</li>
  <li>local search的性能：关键环节；exact polynomial-time searchable neighborhood。</li>
  <li>应用：longest simple path、MAX-SAT、MAX-CL、MIN-VCP。</li>
</ol>

=2014年3月28日=
[[媒体文件:讨论记录-第四学期-2班-第5次.pdf|[课件下载]]]
<ol>
  <li>用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。</li>
  <li>
    rounding：
    <ul>
      <li>什么是一个好的rounding：可行；较优。</li>
      <li>rounding方法：舍入；迭代；随机。</li>
    </ul>
  </li>
  <li>广义的relaxation。</li>
</ol>

=2014年4月4日=
[[媒体文件:讨论记录-第四学期-2班-第6次.pdf|[课件下载]]]
<ol>
  <li>
    近似算法的基本概念：
    <ul>
      <li>定义。</li>
      <li>relative ration；approximation ratio；approximation algorithm。</li>
      <li>GMS的原理及其近似比的证明。</li>
      <li>PTAS、FPTAS及其区别。</li>
    </ul>
  </li>
  <li>NPO的分类。</li>
  <li>
    stability：
    <ul>
      <li>讨论stability的意义。</li>
      <li>distance function；ball；p-stable；stable。</li>
      <li>TSP中的distance；其它难问题中的distance。</li>
      <li>PTAS的stability。</li>
    </ul>
  </li>
  <li>
    dual approximation：
    <ul>
      <li>讨论dual approximation的意义。</li>
      <li>distance function；ball；approximation algorithm；dual PTAS；dual FTPAS。</li>
      <li>BIN-P中的distance；其它难问题中的distance。</li>
    </ul>
  </li>
</ol>

=2014年4月11日=
[[媒体文件:讨论记录-第四学期-2班-第7次.pdf|[课件下载]]]
<ol>
  <li>greedy和local search的异同。</li>
  <li>MIN-VCP：基本思路；近似比及举例；时间复杂度及数据结构。</li>
  <li>SCP：基本思路；近似比及举例；时间复杂度及数据结构；与MIN-VCP的区别。</li>
  <li>greedy算法的设计与分析：longest simple path；MAX-SAT；MAX-CL；MAX-CUT。</li>
  <li>MAX-CUT：基本思路；近似比及举例；时间复杂度及数据结构；与MIN-VCP的区别。</li>
  <li>local search算法的设计与分析：longest simple path；MAX-SAT；MAX-CL；MIN-VCP；SCP。</li>
</ol>

=2014年4月27日=
<ol>
  <li>
    SKP的PTAS：
    <ul>
      <li>算法4.3.4.2的设计思路。</li>
      <li>为什么是SKP的PTAS。</li>
      <li>对于DIST为什么不是superstable；为什么不是KP_delta的PTAS。</li>
    </ul>
  </li>
  <li>
    KP的(F)PTAS：
    <ul>
      <li>算法4.3.4.7的设计思路。</li>
      <li>对于DIST为什么是superstable；为什么是KP的PTAS。</li>
      <li>算法4.3.4.11的设计思路。</li>
    </ul>
  </li>
  <li>
    Delta-TSP的常数近似算法：
    <ul>
      <li>算法4.3.5.1的设计思路及近似比证明。</li>
      <li>算法4.3.5.4的设计思路及近似比证明。</li>
    </ul>
  </li>
  <li>
    TSP问题的分类：
    <ul>
      <li>算法4.3.5.18的设计思路。</li>
      <li>对于dist为什么是stable；如何对TSP进行分类。</li>
      <li>p-strengthen triangle inequality如何对Delta-TSP进行分类。</li>
    </ul>
  </li>
</ol>

=2014年5月4日=
[[媒体文件:讨论记录-第四学期-第9次.pdf|[课件下载]]]
<ol>
  <li>dual approximation algorithms：利用BIN-P求解MS的宏观步骤。</li>
  <li>
    PTAS for MS：
    <ul>
      <li>BIN-P和MS的相互转化。</li>
      <li>利用BIN-P的解法求解MS：算法4.3.6.7。</li>
    </ul>
  </li>
  <li>
    dual PTAS for BIN-P：
    <ul>
      <li>步骤1：动态规划的递归式；算法4.3.6.1及其复杂度。</li>
      <li>步骤2：对输入的处理；算法4.3.6.2及其证明。</li>
      <li>步骤3：对输入的分类处理；算法4.3.6.4及其证明。</li>
    </ul>
  </li>
  <li>
    近似算法复习：
    <ul>
      <li>伪多项式算法。</li>
      <li>分支-界限算法。</li>
      <li>局部搜索算法。</li>
      <li>松弛算法。</li>
      <li>贪心算法。</li>
      <li>PTAS。</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>
  </li>
</ol>

=2014年5月16日=
[[媒体文件:讨论记录-第四学期-2班-第11次.pdf|[课件下载]]]
<ol>
  <li>
    random sampling：
    <ul>
      <li>定义。</li>
      <li>适用的问题类型。</li>
      <li>quadratic residues的适用性。</li>
    </ul>
  </li>
  <li>quadratic residues及其相关证明。</li>
  <li>SSSA是单边错Monte Carlo算法的证明及其使用的局限性。</li>
  <li>Miller-Rabin的基本原理。</li>
  <li>prime generation的基本原理及其证明。</li>
  <li>verifying matrix multiplication的单边错Monte Carlo算法。</li>
</ol>


=2014年5月23日=
[[媒体文件:讨论记录-第四学期-第12次.pdf|[课件下载]]]

=2014年5月30日=
[[媒体文件:讨论记录-第四学期-第13次.pdf|[课件下载]]]

=2014年6月6日=
[[媒体文件:讨论记录-第四学期-第14次.pdf|[课件下载]]]
<ol>
  <li>RSMS：要解决的问题；基本思路；近似比；效果。</li>
  <li>RRRMS：基本思路；到LP的规约；引理5.3.6.3的证明；效果。</li>
  <li>Schoening：要解决的问题；基本思路；时间复杂度；是单边Monte Carlo算法的原因。</li>
</ol>

=2014年6月13日=
[[媒体文件:讨论记录-第四学期-第15次.pdf|[课件下载]]]
<ol>
  <li>去随机追求的目标：概率vs.确定；计算代价。</li>
  <li>
    reduction of the probability space size：
    <ul>
      <li>通过降低变量独立性来减小概率空间的基本思路，及其具体实现（定理5.4.2.2）。</li>
      <li>利用定理5.4.2.2来减少一个随机算法的random bits并最终去随机，及其具体实现（对于MAX-EkSAT）。</li>
    </ul>
  </li>
  <li>
    conditional probabilities：
    <ul>
      <li>通过条件概率来去随机的基本思路：面向的问题；追求的目标；实现目标的方法/算法。</li>
      <li>算法的关键步骤（计算期望）及其具体实现（对于MAX-EkSAT和RSMS）。</li>
      <li>算法5.4.5.3、5.4.5.4、5.4.5.6要解决的问题。</li>
    </ul>
  </li>
</ol>