2012级--讨论记录 (第三学期)
来自问题求解
目录
2013年9月6日
- Bellman-Ford算法。
- Dijkstra算法。
-
最短路问题的应用：
- 差分约束问题：制作番茄炒蛋的时间表。
- 设备更新问题。
2013年9月13日
- 简单的动态规划法。
- Floyd-Warshall算法。
- Johnson算法。
-
多源最短路问题的应用。
- 选址问题。
- 最宽路问题：Schulze投票法。
2013年9月20日
- 最大/最小 点/边 独立/覆盖集，及其相互关系。
-
最大匹配算法。
- 增广路算法。
- Hopcroft-Karp算法。
- Edmonds算法。
-
独立/覆盖问题的应用。
- 教室分配问题。
- 公园选址问题。
- 剪纸问题。
2013年9月27日
-
连通度。
- 点/边连通度和k点/边连通，及分情况举例。
- 惠特尼定理，及分情况举例。
- 3-正则图点、边连通度相等的证明。
-
块。
- 块及其性质。
- 块-割点图及其性质。
- 块算法。
-
k连通图。
- x-y cut。
- Menger定理。
- 连通度和不交路之间的联系。
2013年10月11日
-
网络流。
- Menger's Theorem和Max-flow Min-cut Theorem当capacity是整数时的对应关系。
- 求二部图最大匹配的增广路算法和Ford-Fulkerson算法在求二部图最大匹配时的对应关系。
-
染色。
- 基本概念。
- 色数和团数之间的关系及举例。
- 建模：活动时间安排；数独求解；课程时间安排。
- 贪婪染色及其改进。
-
平面图。
- 基本概念（特别是planar graph和plane graph的区别）。
- face到outer face的转换。
- 图的可平面性和block的可平面性。
- 对偶图及其性质。
-
哈密尔顿圈。
- 欧拉回路和中国邮递员问题。
- 哈密尔顿圈和旅行商问题。
2013年10月18日
- 线性方程组求解。
-
矩阵求逆。
- 利用LUP分解求逆矩阵。
- 线性方程组求解的另一种方法。
- 最小二乘法。
- 求行列式。
2013年10月25日
2013年11月8日
-
多项式表示的转换。
- 定义。
- 运算时间比较。
- 转换：流程；DFT和FFT；FFT的基本思路；FFT的迭代实现。
-
群。
- 二维平面上的移动：群；阿贝尔群；子群；循环群。
- 赤道上的移动：循环群；阿贝尔群；子群。
- 人的位置：置换群；轮换；对换。
- 魔方：置换群；轮换；对换；子群；陪集。
2013年11月15日
- 环和域的概念。
-
环和域的例子。
- 自然数、整数、有理数、实数、复数。
- Gaussian integer。
- Z_n。
- 2x2实数矩阵。
- 实数多项式。
- 基于S的幂集构造一个环。
- 找子环：整数、Gaussian integer、Z_n、2x2实数矩阵、实数多项式、S的幂集。
2013年11月22日
- 良序原理：定义；用来证明莱曼引理。
- 逆、GCD和质数：CS2.2-5, CS2.2-22。
- Euclid's GCD algorithm：基本原理；base case；举例。
2013年11月29日
2013年12月6日
-
对称密钥加密和公开密钥加密。
- 优缺点：便利性；性能。
- 结合。
- RSA的原理。
-
数字签名。
- 作用：验证身份、完整性、不可否认性。
- 和加密/解密过程的区别。
- 身份验证的改进：随机数；CA。
- 完整性验证：与奇偶校验等方法的对比（安全性；数据量）；结合。
2013年12月13日
- 编/解码：校验/纠错与加/解密的区别。
-
奇偶校验。
- 与m+1奇偶校验码的联系和区别。
- Hamming code及其与m+1奇偶校验码的对比。
-
linear code。
- 线性子空间；矩阵的零空间。
- Linear code的好处：差错方便；距离计算简单。
-
查错和纠错。
- dmin的含义。
- dmin对H的要求。
- 最大编码率。
- 如何纠错。
2013年12月20日
- general linear group。
- special linear group：含义；几何意义；方向。
-
orthogonal group和isometry。
- 含义；几何意义。
- special orthogonal group。
- rotation和reflection的联系。
- symmetry group和wallpaper group：含义；和symmetry group的关系。
2013年12月27日
- naive：32.1-4及其变种。
-
rabin-karp。
- 从hash的角度理解；rolling hash；hash的副作用。
- 32.2-2；32.2-3。
-
自动机。
- 组成部分的表述。
- 粗细线的含义；32.3-3。
- invariant的含义与证明。
