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

来自问题求解
Admin讨论 | 贡献2013年3月7日 (四) 20:12的版本 2013年3月8日

跳转至: 导航搜索

2013年3月8日

[课件下载]

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

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。