查看“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>