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

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

2013年12月27日 (五) 12:21的最新版本

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年10月25日

[课件下载]

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；举例。

2013年11月29日

[课件下载]

2013年12月6日

[课件下载]

  1. 对称密钥加密和公开密钥加密。
    • 优缺点：便利性；性能。
    • 结合。
    • RSA的原理。
  2. 数字签名。
    • 作用：验证身份、完整性、不可否认性。
    • 和加密/解密过程的区别。
    • 身份验证的改进：随机数；CA。
    • 完整性验证：与奇偶校验等方法的对比（安全性；数据量）；结合。

2013年12月13日

[课件下载]

  1. 编/解码：校验/纠错与加/解密的区别。
  2. 奇偶校验。
    • 与m+1奇偶校验码的联系和区别。
    • Hamming code及其与m+1奇偶校验码的对比。
  3. linear code。
    • 线性子空间；矩阵的零空间。
    • Linear code的好处：差错方便；距离计算简单。
  4. 查错和纠错。
    • dmin的含义。
    • dmin对H的要求。
    • 最大编码率。
    • 如何纠错。

2013年12月20日

[课件下载]

  1. general linear group。
  2. special linear group：含义；几何意义；方向。
  3. orthogonal group和isometry。
    • 含义；几何意义。
    • special orthogonal group。
    • rotation和reflection的联系。
  4. symmetry group和wallpaper group：含义；和symmetry group的关系。

2013年12月27日

[课件下载]

  1. naive：32.1-4及其变种。
  2. rabin-karp。
    • 从hash的角度理解；rolling hash；hash的副作用。
    • 32.2-2；32.2-3。
  3. 自动机。
    • 组成部分的表述。
    • 粗细线的含义；32.3-3。
    • invariant的含义与证明。
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第三学期)&oldid=697”