“2013级--讨论记录 (第三学期)”的版本间的差异

来自问题求解
跳转至: 导航搜索
2014年9月17日
Wu讨论 | 贡献
2015年1月5日
 
(未显示同一用户的41个中间版本)
第1行: 第1行:
 
=2014年9月5日=
 
=2014年9月5日=
[[媒体文件:*.pdf‎|[课件下载]]]
 
[[媒体文件:*.pdf.pdf‎|[课件下载]]]
 
 
<ol>
 
<ol>
 
<li>
 
<li>
 
<ul>
 
<ul>
 
<li>
 
<li>
tbd
+
讨论最长公共子串问题(LCS)(用于衡量两个序列的相似性)
 
</li>
 
</li>
 +
 +
<li>
 +
讨论最优二分搜索树问题(给定关键字的概率,建立最优二分搜索树,使得搜索的期望代价最小)
 +
</li>
 +
 +
</ul>
 +
</ol>
 +
 +
=2014年9月12日=
 +
[[媒体文件:问题与反馈9-12.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
讨论动态规划习题(子问题图中节点数和边数的计算、是否具有最优子结构的问题、求最长单调递增序列的问题)
 +
</li>
 +
<li>
 +
讨论构建最优前缀码(Huffman Codes)的算法的原理(如何证明问题具有最优子结构)
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年9月17日=
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
并查集在路径压缩和按秩合并两种方法下操作的均摊分析证明。
 +
</li>
 +
<li>
 +
试举使用并查集解题的例子。
 +
(1)堆栈合并
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年9月22日=
 +
[[媒体文件:问题与反馈9-22.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
贪心策略的作业反馈(最优子结构、贪心选择属性、简单的均摊分析练习)
 +
</li>
 +
<li>
 +
Havel-Hakimi定理的证明(度序列的可图化的充分必要条件)
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年9月28日=
 +
[[媒体文件:问题与反馈9-29.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
并查集的作业反馈
 +
</li>
 +
 +
</ul>
 +
</ol>
 +
 +
=2014年10月10日=
 +
[[媒体文件:问题与反馈10-10.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
图的基本概念作业反馈
 +
</li>
 +
<li>
 +
讨论:Prim算法和Kruskal算法的正确性分析(CZ的证明和TC的证明)
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年10月15日=
 +
[[媒体文件:问题与反馈10-15.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
图的计算机表示及遍历(BFS,DFS,拓扑排序,计算强连通分支)
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年10月22日=
 +
[[媒体文件:问题与反馈10-22.pdf|[课件下载]]]
 +
<ol>
 
<li>
 
<li>
tbd
+
<ul>
 +
<li>
 +
树的性质
 +
</li>
 +
<li>
 +
讨论:如何找出所有的最短路径树
 
</li>
 
</li>
 
</ul>
 
</ul>
 
</ol>
 
</ol>
  
=2014年9月10日=
+
=2014年11月3日=
[[媒体文件:*.pdf‎|[课件下载]]]
+
[[媒体文件:问题与反馈11-3.pdf|[课件下载]]]
[[媒体文件:*.pdf.pdf‎|[课件下载]]]
 
 
<ol>
 
<ol>
 
<li>
 
<li>
 
<ul>
 
<ul>
 
<li>
 
<li>
tbd
+
反馈:单源最短路径算法习题(Bellman-Ford, DAG-Shortest-Path, Dijkstra)
 
</li>
 
</li>
 
<li>
 
<li>
tbd
 
 
</li>
 
</li>
 
</ul>
 
</ul>
 
</ol>
 
</ol>
  
=2014年9月5日=
+
=2014年11月12日=
[[媒体文件:*.pdf‎|[课件下载]]]
+
[[媒体文件:问题与讨论11-12.pdf|[课件下载]]]
[[媒体文件:*.pdf.pdf‎|[课件下载]]]
 
 
<ol>
 
<ol>
 
<li>
 
<li>
 
<ul>
 
<ul>
 
<li>
 
<li>
tbd
+
反馈:多源最短路径算法习题(Floyd-Warshall, John's Algorithm)
 +
</li>
 +
<li>
 
</li>
 
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年11月21日=
 +
[[媒体文件:问题与反馈11-21.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:图的连通度衡量
 +
</li>
 +
<li>
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年11月26日=
 +
[[媒体文件:问题与反馈11-26.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:欧拉图、Hamilton图的概念
 +
</li>
 +
<li>
 +
讨论:(11月28日)连通分支、团的概念及求最小连通分支和最大团的算法
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年12月3日=
 +
[[媒体文件:反馈与讨论12-3.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:匹配、完美匹配、因子图的概念
 +
</li>
 +
<li>
 +
讨论:(12月5日)网络流算法的应用举例
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年12月10日=
 +
[[媒体文件:反馈与讨论12-10.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:图的偏距、半径、直径、中心、外围、边界等概念
 +
</li>
 +
<li>
 +
讨论:(12月12日)Brooks定理的证明
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年12月17日=
 +
[[媒体文件:问题与反馈12-17.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:流网络、剩余网络、增广路径、Ford-Fulkerson算法等,26章习题。
 +
</li>
 +
<li>
 +
讨论:(12月19日)
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年12月24日=
 +
[[媒体文件:问题与反馈12-24.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:可平面图和图着色。
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2014年12月31日=
 +
[[媒体文件:问题与反馈12-31.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 +
<li>
 +
反馈:矩阵计算习题反馈,LU分解,LUP分解,正定矩阵的性质
 +
</li>
 +
</ul>
 +
</ol>
 +
 +
=2015年1月5日=
 +
[[媒体文件:问题与反馈1-5.pdf|[课件下载]]]
 +
<ol>
 +
<li>
 +
<ul>
 
<li>
 
<li>
tbd
+
反馈:线性规划习题(Simplex算法)。
 
</li>
 
</li>
 
</ul>
 
</ul>
 
</ol>
 
</ol>

2015年1月4日 (日) 11:10的最新版本

2014年9月5日

    • 讨论最长公共子串问题(LCS)(用于衡量两个序列的相似性)
    • 讨论最优二分搜索树问题(给定关键字的概率,建立最优二分搜索树,使得搜索的期望代价最小)

2014年9月12日

[课件下载]

    • 讨论动态规划习题(子问题图中节点数和边数的计算、是否具有最优子结构的问题、求最长单调递增序列的问题)
    • 讨论构建最优前缀码(Huffman Codes)的算法的原理(如何证明问题具有最优子结构)

2014年9月17日

    • 并查集在路径压缩和按秩合并两种方法下操作的均摊分析证明。
    • 试举使用并查集解题的例子。 (1)堆栈合并

2014年9月22日

[课件下载]

    • 贪心策略的作业反馈(最优子结构、贪心选择属性、简单的均摊分析练习)
    • Havel-Hakimi定理的证明(度序列的可图化的充分必要条件)

2014年9月28日

[课件下载]

    • 并查集的作业反馈

2014年10月10日

[课件下载]

    • 图的基本概念作业反馈
    • 讨论:Prim算法和Kruskal算法的正确性分析(CZ的证明和TC的证明)

2014年10月15日

[课件下载]

    • 图的计算机表示及遍历(BFS,DFS,拓扑排序,计算强连通分支)

2014年10月22日

[课件下载]

    • 树的性质
    • 讨论:如何找出所有的最短路径树

2014年11月3日

[课件下载]

    • 反馈:单源最短路径算法习题(Bellman-Ford, DAG-Shortest-Path, Dijkstra)

2014年11月12日

[课件下载]

    • 反馈:多源最短路径算法习题(Floyd-Warshall, John's Algorithm)

2014年11月21日

[课件下载]

    • 反馈:图的连通度衡量

2014年11月26日

[课件下载]

    • 反馈:欧拉图、Hamilton图的概念
    • 讨论:(11月28日)连通分支、团的概念及求最小连通分支和最大团的算法

2014年12月3日

[课件下载]

    • 反馈:匹配、完美匹配、因子图的概念
    • 讨论:(12月5日)网络流算法的应用举例

2014年12月10日

[课件下载]

    • 反馈:图的偏距、半径、直径、中心、外围、边界等概念
    • 讨论:(12月12日)Brooks定理的证明

2014年12月17日

[课件下载]

    • 反馈:流网络、剩余网络、增广路径、Ford-Fulkerson算法等,26章习题。
    • 讨论:(12月19日)

2014年12月24日

[课件下载]

    • 反馈:可平面图和图着色。

2014年12月31日

[课件下载]

    • 反馈:矩阵计算习题反馈,LU分解,LUP分解,正定矩阵的性质

2015年1月5日

[课件下载]

    • 反馈:线性规划习题(Simplex算法)。