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

来自问题求解
Admin讨论 | 贡献2013年4月12日 (五) 14:22的版本 2013年4月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。
    • 作用:猜测运行时间;直接证明运行时间。
    • 构建的步骤:中间节点;叶子节点;每层的和;层数;总合。

2013年3月22日

[课件下载]

  1. induction, recursion, recurrences。
    • induction、recursion和recurrences的两两关系。
    • well-ordering principle和induction的关系:反证法+well-ordering principle=induction。
    • top-down比bottom-up的优势:思路更直接;不用证明构建的完备性;base case更直接。
  2. first-order constant coefficient linear recurrence。
    • 结论的来源:通过递推展开来猜测。
    • 结论的证明:数学归纳法。
  3. the master theorem的证明:基于递归树的时间复杂度分析。

2013年3月29日

[课件下载]

  1. probability。
    • 从集合的角度理解sample space, element, event。
    • 区分probability weight和probability,并基于probability weight理解probability distribution function的三个条件。
    • uniform probability distribution的意义:probability-->counting。
  2. the principle of inclusion and exclusion:基于Venn图解释公式。
  3. conditional probability。
    • 基于Venn图解释conditional probability和独立性。
    • independent trials process和tree diagram。
  4. random variable:理解random variable, expected value, additivity of expectation。

2013年4月7日

[课件下载]

  1. indicator random variable:原理与应用。
  2. 随机化。
    • expected running time vs. average-case running time:随机算法 vs. 一般算法的所有输入。
    • 随机数生成方法:计算方法;物理方法。
    • 数组随机排序方法:permute-by-sorting;randomize-in-place。
  3. 计算expected running time的方法:定义;indicator random variable;线性性质;条件期望。
  4. probability distributions and variance。
    • distribution function vs. cumulative distribution function:点和区间。
    • variance及其来源。

2013年4月12日

[课件下载]

  1. 快速排序。
    • 正确性证明:loop invariant;递归程序正确性的归纳证明。
    • 运行时间:worst-case;best-case;average-case。
    • 随机化的快速排序:随机化的意义;期望运行时间。
  2. 线性时间排序算法。
    • 基于比较的排序:运行时间的下界。
    • counting sort:stable;从左往右扫描的改法;对输入的要求及缺点。
    • radix sort:从高位开始排序的改法;分解的灵活性;对输入的要求。
    • bucket sort:最优运行时间。
  3. 选择问题:找最大、最小元;随机化的选择算法;确定性的选择算法。