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

来自问题求解
跳转至： 导航、 搜索
（→‎2013年3月8日）
第1行： 第1行：
−
=2013年3月8日=
 
−
[[媒体文件:讨论记录-第二学期-2班-第2次.pdf|[课件下载]]]
 
−
<ol>
 
−
  <li>加法和乘法原理的应用：识别元素；识别不相交的集合。</li>
 
−
  <li>
 
−
    列表、置换和子集。
 
−
    <ul>
 
−
      <li>列表：本质是函数。</li>
 
−
      <li>置换：本质是双射函数。</li>
 
−
      <li>k-元素置换：本质是列表。</li>
 
−
      <li>k-元素子集：也可以看作函数。</li>
 
−
    </ul>
 
−
  </li>
 
−
  <li>双射在counting中的作用：元素个数不变，但更容易计算。</li>
 
−
  <li>等价关系在counting中的作用：等价类大小相同时，可以做除法。</li>
 
−
</ol>
 
−
 
 
=2013年3月1日=
 
=2013年3月1日=
 
[[媒体文件:讨论记录-第二学期-2班-第1次.pdf|[课件下载]]]
 
[[媒体文件:讨论记录-第二学期-2班-第1次.pdf|[课件下载]]]
第54行： 第37行：
 
       <li>O vs. o：基于集合；基于极限。</li>
 
       <li>O vs. o：基于集合；基于极限。</li>
 
       <li>渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。</li>
 
       <li>渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年3月8日=
 +
[[媒体文件:讨论记录-第二学期-2班-第2次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>加法和乘法原理的应用：识别元素；识别不相交的集合。</li>
 +
  <li>
 +
    列表、置换和子集。
 +
    <ul>
 +
      <li>列表：本质是函数。</li>
 +
      <li>置换：本质是双射函数。</li>
 +
      <li>k-元素置换：本质是列表。</li>
 +
      <li>k-元素子集：也可以看作函数。</li>
 +
    </ul>
 +
  </li>
 +
  <li>双射在counting中的作用：元素个数不变，但更容易计算。</li>
 +
  <li>等价关系在counting中的作用：等价类大小相同时，可以做除法。</li>
 +
</ol>
 +
 +
=2013年3月15日=
 +
[[媒体文件:讨论记录-第二学期-2班-第3次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    maximum-subarray problem。
 +
    <ul>
 +
      <li>divide、conquer和combine在这个算法中分别如何体现。</li>
 +
      <li>找max-crossing-subarray的方式与brute-force不同，从而节约操作。</li>
 +
      <li>运行时间的递归表示。</li>
 +
      <li>利用recursion tree来猜测运行时间的渐进表示法。</li>
 +
      <li>利用substitution或master theorem来证明。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    substitution证明的一些细节。
 +
    <ul>
 +
      <li>为低阶项保留余量。</li>
 +
      <li>恰当运用替换。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    recursion tree。
 +
    <ul>
 +
      <li>作用：猜测运行时间；直接证明运行时间。</li>
 +
      <li>构建的步骤：中间节点；叶子节点；每层的和；层数；总合。</li>
 
     </ul>
 
     </ul>
 
   </li>
 
   </li>
 
</ol>
 
</ol>

2013年3月14日 (四) 20:12的版本

2013年3月1日

[课件下载]

  1. 计算问题与算法。
    • 计算问题：input + output + their relationship。
    • 算法：well-defined computational procedure for achieving an input-output relationship。
  2. 好算法。
    • 要素：正确性、高效性、易实现性。
    • 设计流程：思路-->过程-->正确性-->效率。
  3. 算法的正确性分析。
    • partially correct：基于checkpoint和invariant。
    • totally correct：partially correct + termination。
  4. 算法的效率分析。
    • RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。
    • running time的计算：cost*times；best/worst/average case。
  5. 算法效率的渐进表示法。
    • Theta, O和Omega的含义：基于集合；基于极限。
    • Theta vs. O：用O避免分情况讨论。
    • O vs. o：基于集合；基于极限。
    • 渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。

2013年3月8日

[课件下载]

  1. 加法和乘法原理的应用：识别元素；识别不相交的集合。
  2. 列表、置换和子集。
    • 列表：本质是函数。
    • 置换：本质是双射函数。
    • k-元素置换：本质是列表。
    • k-元素子集：也可以看作函数。
  3. 双射在counting中的作用：元素个数不变，但更容易计算。
  4. 等价关系在counting中的作用：等价类大小相同时，可以做除法。

2013年3月15日

[课件下载]

  1. maximum-subarray problem。
    • divide、conquer和combine在这个算法中分别如何体现。
    • 找max-crossing-subarray的方式与brute-force不同，从而节约操作。
    • 运行时间的递归表示。
    • 利用recursion tree来猜测运行时间的渐进表示法。
    • 利用substitution或master theorem来证明。
  2. substitution证明的一些细节。
    • 为低阶项保留余量。
    • 恰当运用替换。
  3. recursion tree。
    • 作用：猜测运行时间；直接证明运行时间。
    • 构建的步骤：中间节点；叶子节点；每层的和；层数；总合。
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第二学期)&oldid=454”