2012级--讨论记录 (第四学期)

来自问题求解
Admin（讨论 | 贡献）2014年5月4日 (日) 20:33的版本

跳转至： 导航、 搜索

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月9日

[课件下载]

  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。
    • 稳定性。
    • 对偶近似算法。
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第四学期)&oldid=815”