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

2013年9月6日

[课件下载]

1. Bellman-Ford算法。
2. Dijkstra算法。
3. 最短路问题的应用：
   • 差分约束问题：制作番茄炒蛋的时间表。
   • 设备更新问题。

2013年9月13日

[课件下载]

1. 简单的动态规划法。
2. Floyd-Warshall算法。
3. Johnson算法。
4. 多源最短路问题的应用。
   • 选址问题。
   • 最宽路问题：Schulze投票法。

2013年9月20日

[课件下载]

1. 最大/最小 点/边 独立/覆盖集，及其相互关系。
2. 最大匹配算法。
   • 增广路算法。
   • Hopcroft-Karp算法。
   • Edmonds算法。
3. 独立/覆盖问题的应用。
   • 教室分配问题。
   • 公园选址问题。
   • 剪纸问题。

2013年9月27日

[课件下载]

1. 连通度。
   • 点/边连通度和k点/边连通，及分情况举例。
   • 惠特尼定理，及分情况举例。
   • 3-正则图点、边连通度相等的证明。
2. 块。
   • 块及其性质。
   • 块-割点图及其性质。
   • 块算法。
3. k连通图。
   • x-y cut。
   • Menger定理。
   • 连通度和不交路之间的联系。

2013年10月11日

[课件下载]

1. 网络流。
   • Menger's Theorem和Max-flow Min-cut Theorem当capacity是整数时的对应关系。
   • 求二部图最大匹配的增广路算法和Ford-Fulkerson算法在求二部图最大匹配时的对应关系。
2. 染色。
   • 基本概念。
   • 色数和团数之间的关系及举例。
   • 建模：活动时间安排；数独求解；课程时间安排。
   • 贪婪染色及其改进。
3. 平面图。
   • 基本概念（特别是planar graph和plane graph的区别）。
   • face到outer face的转换。
   • 图的可平面性和block的可平面性。
   • 对偶图及其性质。
4. 哈密尔顿圈。
   • 欧拉回路和中国邮递员问题。
   • 哈密尔顿圈和旅行商问题。

2013年10月18日

[课件下载]

1. 线性方程组求解。
2. 矩阵求逆。
   • 利用LUP分解求逆矩阵。
   • 线性方程组求解的另一种方法。
3. 最小二乘法。
4. 求行列式。

2013年11月8日

[课件下载]

1. 多项式表示的转换。
   • 定义。
   • 运算时间比较。
   • 转换：流程；DFT和FFT；FFT的基本思路；FFT的迭代实现。
2. 群。
   • 二维平面上的移动：群；阿贝尔群；子群；循环群。
   • 赤道上的移动：循环群；阿贝尔群；子群。
   • 人的位置：置换群；轮换；对换。
   • 魔方：置换群；轮换；对换；子群；陪集。

2013年11月15日

[课件下载]

1. 环和域的概念。
2. 环和域的例子。
   • 自然数、整数、有理数、实数、复数。
   • Gaussian integer。
   • Z_n。
   • 2x2实数矩阵。
   • 实数多项式。
   • 基于S的幂集构造一个环。
3. 找子环：整数、Gaussian integer、Z_n、2x2实数矩阵、实数多项式、S的幂集。

2013年11月22日

[课件下载]

1. 良序原理：定义；用来证明莱曼引理。
2. 逆、GCD和质数：CS2.2-5, CS2.2-22。
3. Euclid's GCD algorithm：基本原理；base case；举例。