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

来自问题求解
跳转至： 导航、 搜索
（以“=2013年3月1日= [课件下载] <ol> <li> xxx。 <ul> <li>xxx。</li> <li>xxx。</...”为内容创建页面）
 
（→‎2013年3月1日）
第3行： 第3行：
 
<ol>
 
<ol>
 
   <li>
 
   <li>
−
     xxx。
+
     计算问题与算法。
 
     <ul>
 
     <ul>
−
       <li>xxx。</li>
+
       <li>计算问题：input + output + their relationship。</li>
−
       <li>xxx。</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>
 
     </ul>
 
   </li>
 
   </li>
 
</ol>
 
</ol>

2013年2月28日 (四) 22:11的版本

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。
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第二学期)&oldid=444”