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

来自问题求解
Admin讨论 | 贡献2013年10月18日 (五) 12:21的版本 2013年10月18日

跳转至: 导航搜索

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. 求行列式。