“2012级--讨论记录 (第二学期)”的版本间的差异
来自问题求解
| （未显示同一用户的1个中间版本） | |||
| 第361行： | 第361行： | ||
[[媒体文件:讨论记录-第二学期-2班-第15次.pdf|[课件下载]]] | [[媒体文件:讨论记录-第二学期-2班-第15次.pdf|[课件下载]]] | ||
<ol> | <ol> | ||
| − | <li> | + | <li>用图来建模问题。</li> |
| + | <li>图的集合表示。 | ||
<ul> | <ul> | ||
| − | <li> | + | <li>无向图：函数；multiset。</li> |
| − | <li> | + | <li>有向图：函数；multiset。</li> |
| − | |||
</ul> | </ul> | ||
</li> | </li> | ||
| − | <li> | + | <li>图论中的术语。</li> |
| + | </ol> | ||
| + | |||
| + | =2013年6月21日= | ||
| + | [[媒体文件:讨论记录-第二学期-2班-第16次.pdf|[课件下载]]] | ||
| + | <ol> | ||
| + | <li>图的计算机表示。 | ||
<ul> | <ul> | ||
| − | <li> | + | <li>方法与优缺点：Two-dimensional array；List of lists；Dictionary of keys；Coordinate list；Yale format。</li> |
| − | <li> | + | <li>结合使用。</li> |
</ul> | </ul> | ||
</li> | </li> | ||
| − | <li> | + | <li>图的搜索。 |
| + | <ul> | ||
| + | <li>BFS：三种颜色的含义；BFS-tree的构建。</li> | ||
| + | <li>DFS：子孙关系的三个充要条件；SCC算法的原理。</li> | ||
| + | </ul> | ||
| + | </li> | ||
| + | <li>最小生成树：Kruskal及其实现；Prim及其实现；拟阵。</li> | ||
</ol> | </ol> | ||
2013年6月21日 (五) 12:40的最新版本
目录
2013年3月1日
-
计算问题与算法。
- 计算问题：input + output + their relationship。
- 算法：well-defined computational procedure for achieving an input-output relationship。
-
好算法。
- 要素：正确性、高效性、易实现性。
- 设计流程：思路-->过程-->正确性-->效率。
-
算法的正确性分析。
- partially correct：基于checkpoint和invariant。
- totally correct：partially correct + termination。
-
算法的效率分析。
- RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。
- running time的计算：cost*times；best/worst/average case。
-
算法效率的渐进表示法。
- Theta, O和Omega的含义：基于集合；基于极限。
- Theta vs. O：用O避免分情况讨论。
- O vs. o：基于集合；基于极限。
- 渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。
2013年3月8日
- 加法和乘法原理的应用：识别元素；识别不相交的集合。
-
列表、置换和子集。
- 列表：本质是函数。
- 置换：本质是双射函数。
- k-元素置换：本质是列表。
- k-元素子集：也可以看作函数。
- 双射在counting中的作用：元素个数不变，但更容易计算。
- 等价关系在counting中的作用：等价类大小相同时，可以做除法。
2013年3月15日
-
maximum-subarray problem。
- divide、conquer和combine在这个算法中分别如何体现。
- 找max-crossing-subarray的方式与brute-force不同，从而节约操作。
- 运行时间的递归表示。
- 利用recursion tree来猜测运行时间的渐进表示法。
- 利用substitution或master theorem来证明。
-
substitution证明的一些细节。
- 为低阶项保留余量。
- 恰当运用替换。
-
recursion tree。
- 作用：猜测运行时间；直接证明运行时间。
- 构建的步骤：中间节点；叶子节点；每层的和；层数；总合。
2013年3月22日
-
induction, recursion, recurrences。
- induction、recursion和recurrences的两两关系。
- well-ordering principle和induction的关系：反证法+well-ordering principle=induction。
- top-down比bottom-up的优势：思路更直接；不用证明构建的完备性；base case更直接。
-
first-order constant coefficient linear recurrence。
- 结论的来源：通过递推展开来猜测。
- 结论的证明：数学归纳法。
- the master theorem的证明：基于递归树的时间复杂度分析。
2013年3月29日
-
probability。
- 从集合的角度理解sample space, element, event。
- 区分probability weight和probability，并基于probability weight理解probability distribution function的三个条件。
- uniform probability distribution的意义：probability-->counting。
- the principle of inclusion and exclusion：基于Venn图解释公式。
-
conditional probability。
- 基于Venn图解释conditional probability和独立性。
- independent trials process和tree diagram。
- random variable：理解random variable, expected value, additivity of expectation。
2013年4月7日
- indicator random variable：原理与应用。
-
随机化。
- expected running time vs. average-case running time：随机算法 vs. 一般算法的所有输入。
- 随机数生成方法：计算方法；物理方法。
- 数组随机排序方法：permute-by-sorting；randomize-in-place。
- 计算expected running time的方法：定义；indicator random variable；线性性质；条件期望。
-
probability distributions and variance。
- distribution function vs. cumulative distribution function：点和区间。
- variance及其来源。
2013年4月12日
- 快速排序。
- 正确性证明：loop invariant；递归程序正确性的归纳证明。
- 运行时间：worst-case；best-case；average-case。
- 随机化的快速排序：随机化的意义；期望运行时间。
- 线性时间排序算法。
- 基于比较的排序：运行时间的下界。
- counting sort：stable；从左往右扫描的改法；对输入的要求及缺点。
- radix sort：从高位开始排序的改法；分解的灵活性；对输入的要求。
- bucket sort：最优运行时间。
- 选择问题：找最大、最小元；随机化的选择算法；确定性的选择算法。
2013年4月19日
- dynamic set：含义；基本操作。
- linked list。
- 支持的操作：search, insert, delete。
- insert/delete的抽象实现。
- 基于数组的具体实现：多数组；单数组。
- dynamic set操作的实现。
- stack。
- 支持的操作：test-empty, push, pop。
- 具体实现：基于数组；基于链表。
- dynamic set操作的实现。
- queue。
- 支持的操作：test-empty, enqueue, dequeue。
- 具体实现：基于数组；基于链表。
- dynamic set操作的实现。
- rooted tree。
- 与linked list的异同。
- left-child, right-sibling representation的抽象实现。
- dynamic set操作的实现。
- allocating and freeing objects。
- 意义。
- free list的本质：基于linked list实现的stack。
- service several linked lists with a single linked list的优缺点。
2013年4月26日
- heap、heapsort、priority queue：各算法的作用、基本原理、正确性证明、运行时间。
- 分层抽象。
- priority queue <-- heap <-- array。
- tree <-- binary tree <-- array。
- 优缺点：更简单的正确性证明 vs. 更复杂的运行时间分析。
- tree的前序、中序、后序遍历。
- 其它ADT：union-find；dictionary。
- single-linkage agglomerative clustering。
- 最终hierarchy的保存：binary out-tree。
- hierarchy的计算过程：priority queue (+ dictionary)。
- 计算过程的监控：union-find。
2013年5月3日
- dictionary。
- 操作；用途。
- direct-address table：原理；优缺点。
- hash table：原理；优缺点。
- collision。
- expected number of items per location。
- expected number of empty locations。
- expected number of collisions。
- collision resolution。
- chaining：原理；运行时间；优缺点。
- open addressing：原理；三种实现方式的区别；运行时间；优缺点。
- 降低alpha的方式：扩容。
- perfect hashing：原理；运行时间；优缺点。
- hash function。
- 目标：simple uniform hashing；depends on all the bits of the key；fast。
- 应对蓄意构造的坏情况：choose the hash function randomly。
2013年5月10日
- binary search trees。
- 操作；用途。
- 各操作：原理；正确性。
- binary search tree vs. hash table：运行时间；前后继；范围搜索；排序；对输入的要求（hash function vs. total order）；重hash。
- red-black trees。
- 平衡性及其原因。
- rotation的性质。
- 插入和删除的宏观思路。
2013年5月17日
- dynamic programming。
- 面向的问题：优化。
- 适用的问题：有最优子结构。
- 有用的问题：子问题重复。
- 代价：空间换时间。
- dynamic programming的运行时间。
- 性能要素：子问题数量；每个子问题中的决策数量。
- 计算方法：top-down vs. bottom-up。
- 问题实例及其四步骤。
- rod cutting。
- matrix-chain multiplication。
- unweighted shortest/longest simple path。
- longest common subsequence。
- optimal binary search trees。
2013年5月24日
- greedy algorithms。
- 基本原理。
- greedy-choice property和optimal substructure。
- 效率高于动态规划：计算的子问题少。
- 实例：activity-selection和Huffman codes。
- amortized analysis。
- 与average-case analysis的异同：per operation vs. per algorithm; worst-case vs. average-case。
- aggregate analysis：按行计算改为按列计算。
- accounting method：在别处分摊代价。
- potential function：全局集中的代价寄存；从accounting method的角度理解potential function。
- 实例：stack operations; incrementing a binary counter; table expansion和contraction。
2013年5月31日
- union-find的应用。
- connected component。
- how many tables。
- the suspects。
- union-find的实现。
- linked-list representation及其改进：weighted-union heuristic。
- disjoint-set forests及其改进：union by rank；path compression。
- single-linkage agglomerative clustering的实现：优先队列+并查集+树。
2013年6月7日
- 用图来建模问题。
- 图的集合表示。
- 无向图：函数；multiset。
- 有向图：函数；multiset。
- 图论中的术语。
2013年6月21日
- 图的计算机表示。
- 方法与优缺点：Two-dimensional array；List of lists；Dictionary of keys；Coordinate list；Yale format。
- 结合使用。
- 图的搜索。
- BFS：三种颜色的含义；BFS-tree的构建。
- DFS：子孙关系的三个充要条件；SCC算法的原理。
- 最小生成树：Kruskal及其实现；Prim及其实现；拟阵。
