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

=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日=
[[媒体文件:讨论记录-第二学期-2班-第1次.pdf|[课件下载]]]
<ol>
  <li>
    计算问题与算法。
    <ul>
      <li>计算问题：input + output + their relationship。</li>
      <li>算法：well-defined computational procedure for achieving an input-output relationship。</li>
    </ul>
  </li>
  <li>
    好算法。
    <ul>
      <li>要素：正确性、高效性、易实现性。</li>
      <li>设计流程：思路-->过程-->正确性-->效率。</li>
    </ul>
  </li>
  <li>
    算法的正确性分析。
    <ul>
      <li>partially correct：基于checkpoint和invariant。</li>
      <li>totally correct：partially correct + termination。</li>
    </ul>
  </li>
  <li>
    算法的效率分析。
    <ul>
      <li>RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。</li>
      <li>running time的计算：cost*times；best/worst/average case。</li>
    </ul>
  </li>
  <li>
    算法效率的渐进表示法。
    <ul>
      <li>Theta, O和Omega的含义：基于集合；基于极限。</li>
      <li>Theta vs. O：用O避免分情况讨论。</li>
      <li>O vs. o：基于集合；基于极限。</li>
      <li>渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。</li>
    </ul>
  </li>
</ol>