“2012级--讨论记录 (第四学期)”的版本间的差异

来自问题求解
跳转至： 导航、 搜索
（以“=2014年2月21日= [课件下载] <ol> <li> 字母表、词、语言： <ul> <li>形式...”为内容创建页面）
 
（→‎2014年2月21日）
第25行： 第25行：
 
       <li>确定性和非确定性。</li>
 
       <li>确定性和非确定性。</li>
 
       <li>NPO和PO。</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>
 
     </ul>
 
   </li>
 
   </li>
 
</ol>
 
</ol>

2014年2月28日 (五) 16:19的版本

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的证明方法和例子。
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第四学期)&oldid=749”