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

来自问题求解
跳转至： 导航、 搜索
（→‎2班）
 
（未显示同一用户的24个中间版本）
第1行： 第1行：
 
=2012年9月27日=
 
=2012年9月27日=
−
==1班==
 
−
<ol>
 
−
  <li></li>
 
−
</ol>
 
−
 
−
==2班==
 
 
[[媒体文件:讨论记录-第一学期-2班-第1次.pdf|[课件下载]]]
 
[[媒体文件:讨论记录-第一学期-2班-第1次.pdf|[课件下载]]]
 
<ol>
 
<ol>
第39行： 第33行：
 
=2012年10月11日=
 
=2012年10月11日=
 
[[媒体文件:讨论记录-第一学期-第2次.pdf|[课件下载]]]
 
[[媒体文件:讨论记录-第一学期-第2次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>C++程序设计(1)</li>
 +
</ol>
  
 
=2012年10月18日=
 
=2012年10月18日=
−
==1班==
+
[[媒体文件:讨论记录-第一学期-2班-第3次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    理解Cantor定理。
 +
    <ul>
 +
      <li>幂集的含义。</li>
 +
      <li>证明的思路。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    Implication的陈述方法。
 +
    <ul>
 +
      <li>中英文术语的对应。</li>
 +
      <li>直译与意译。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    Exercise 2.8。
 +
    <ul>
 +
      <li>真值表的应用。</li>
 +
      <li>形式化问题时的命题选择。</li>
 +
    </ul>
 +
  </li>
 +
  <li>求解Knights and Knaves：命题的形式化（特别是等价运算符的使用）。</li>
 +
  <li>
 +
    合取/析取范式的化简。
 +
    <ul>
 +
      <li>可合取分量的选择：只有一个变元前的正反符号不同。</li>
 +
      <li>编程：循环的使用（特别是循环的条件）。</li>
 +
    </ul>
 +
  </li>
 +
  <li>量词与集合：命题形式化的全面性与准确性。</li>
 +
  <li>proof in cases方法的正确性：命题的形式化。</li>
 +
  <li>扑克牌魔术的原理：将问题形式化为数学归纳法可解的形式（特别是确定n的含义）。</li>
 +
  <li>表达式的范式表示：数学归纳法证明中要确保能覆盖n+1时的所有可能性。</li>
 +
</ol>
 +
 
 +
=2012年10月23日=
 +
[[媒体文件:讨论记录-第一学期-第4次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>C++程序设计(2)</li>
 +
</ol>
 +
 
 +
=2012年11月2日=
 +
[[媒体文件:讨论记录-第一学期-2班-第5次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    不用递归实现second-visit-traversal。
 +
    <ul>
 +
      <li>方法1：引入“返回父节点”操作。</li>
 +
      <li>方法2：运用堆栈。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    走迷宫的算法。
 +
    <ul>
 +
      <li>（没有回路的）迷宫可表示为树。</li>
 +
      <li>走迷宫可表示为树的遍历。</li>
 +
    </ul>
 +
  </li>
 +
  <li>树节点的逐层输出：运用队列（操作受限的数组）。</li>
 +
  <li>
 +
    对战tic-tac-toe的算法。
 +
    <ul>
 +
      <li>下每一步棋的目的：最大化获胜概率。</li>
 +
      <li>结果最完美的算法：穷举所有可能性。</li>
 +
      <li>所有可能性的表示方法：树。</li>
 +
      <li>下每一步棋的获胜概率的计算：叶子节点的分布。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 
 +
=2012年11月8日=
 +
[[媒体文件:讨论记录-第一学期-2班-第6次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    “选择排序”算法的流程图：自顶向下解决问题的思路。
 +
    <ul>
 +
      <li>先绘制外层循环。</li>
 +
      <li>再绘制内层循环。</li>
 +
    </ul>
 +
  </li>
 +
  <li>子程序（函数）的四个作用及举例。</li>
 +
  <li>
 +
    所有C++变量名构成的语言：
 +
    <ul>
 +
      <li>对应的BNF：自顶向下解决问题的思路；递归定义的多种写法。</li>
 +
      <li>*对应的有穷状态自动机。</li>
 +
      <li>利用有穷状态自动机检查句子的合法性。</li>
 +
      <li>*利用有穷状态自动机对不合法的句子提出修改建议。</li>
 +
    </ul>
 +
  </li>
 +
  <li>C++变量声明语句对应的BNF：自顶向下解决问题的思路。</li>
 +
</ol>
 +
 
 +
=2012年11月16日=
 +
[[媒体文件:讨论记录-第一学期-第7次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>C++程序设计(3)</li>
 +
</ol>
 +
 
 +
=2012年11月22日=
 +
[[媒体文件:讨论记录-第一学期-2班-第8次.pdf|[课件下载]]]
 
<ol>
 
<ol>
−
   <li></li>
+
   <li>
 +
    编译型语言 vs. 解释型语言。
 +
    <ul>
 +
      <li>编译型的优势：运行效率、知识产权保护。</li>
 +
      <li>解释型的优势：跨平台、交互性。</li>
 +
    </ul>
 +
  </li>
 +
  <li>用C语言来编写一个C语言编译器自身的绝大部分：递增实现。</li>
 +
  <li>包含于 vs. 属于。</li>
 +
  <li>
 +
    自顶向下证明集合相关的命题。
 +
    <ul>
 +
      <li>if and only if的分治。</li>
 +
      <li>集合相等的分治（包含于）。</li>
 +
    </ul>
 +
  </li>
 +
  <li>下标集、幂集、笛卡尔乘积、关系的含义。</li>
 
</ol>
 
</ol>
  
−
==2班==
+
=2012年11月29日=
−
[[媒体文件:讨论记录-第一学期-2班-第3次.pdf|[课件下载]]]
+
[[媒体文件:讨论记录-第一学期-2班-第9次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>关系的性质：自反、反自反、对称、反对称、强反对称、传递、等价。</li>
 +
  <li>
 +
    关系的转换。
 +
    <ul>
 +
      <li>反对称-->强反对称：去掉(x,x)。</li>
 +
      <li>问题10.6：对称+传递-->自反？x在关系中不出现（即找不到y）。</li>
 +
    </ul>
 +
  </li>
 +
  <li>等价关系（和等价类）、划分及其一一对应：关系/集合的内涵和外延。</li>
 +
  <li>
 +
    界、极值和确界的比较。
 +
    <ul>
 +
      <li>数量。</li>
 +
      <li>是否在集合中。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    序。
 +
    <ul>
 +
      <li>举例：集合上的“包含”关系是偏序；实数上的“大于等于”关系是全序。</li>
 +
      <li>哈斯图：偏序哈斯图的必要条件是无回路（自回路除外）；全序哈斯图的核心是一条有向路径。</li>
 +
    </ul>
 +
  </li>
 +
  <li>从数学归纳法推导well-ordering principle of N。</li>
 +
</ol>
 +
 
 +
=2012年12月6日=
 +
[[媒体文件:讨论记录-第一学期-2班-第10次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    函数。
 +
    <ul>
 +
      <li>基本术语：定义域、陪域、值域、单射、满射、双射。</li>
 +
      <li>举例：单射非满射；满射非单射；双射。</li>
 +
    </ul>
 +
  </li>
 +
  <li>函数相等：从集合的角度定义。</li>
 +
  <li>
 +
    函数相关的证明。
 +
    <ul>
 +
      <li>求解函数值域的思路。</li>
 +
      <li>证明函数是双射的思路。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    函数的复合。
 +
    <ul>
 +
      <li>复合与单射/满射的关系。</li>
 +
      <li>举例：f单射、g单射；f单射、g非单射、g◦f单射；f满射、g满射；f非满射、g满射、g◦f满射；f双射、g双射。</li>
 +
    </ul>
 +
  </li>
 +
  <li>恒等函数的性质证明：well-defined；one-to-one；onto；its own inverse（根据函数相等的定义）。</li>
 +
  <li>
 +
    函数的像。
 +
    <ul>
 +
      <li>f-1(y)和f-1({y})的区别：反函数值和反像。</li>
 +
      <li>Exercise 16.4的反例。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 
 +
=2012年12月13日=
 +
[[媒体文件:讨论记录-第一学期-2班-第11次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>数独程序设计答辩。</li>
 +
</ol>
 +
 
 +
=2012年12月20日=
 +
[[媒体文件:讨论记录-第一学期-第12次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    算法方法的应用（0-1背包问题）。
 +
    <ul>
 +
      <li>穷举搜索：通过位串（二进制数）实现子集的穷举。</li>
 +
      <li>带剪枝的穷举搜索。</li>
 +
      <li>贪心：定义性价比；局部最优。</li>
 +
      <li>动态规划：定义子问题；全局最优。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    程序设计中的错误。
 +
    <ul>
 +
      <li>语言错误。</li>
 +
      <li>逻辑错误：语义错误（=和==的混用）；算法错误。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    算法的正确性。
 +
    <ul>
 +
      <li>部分正确：if终止then正确（特例：一个死循环程序）。</li>
 +
      <li>终止。</li>
 +
      <li>完全正确：部分正确+终止。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    算法正确性的一般证明手法。
 +
    <ul>
 +
      <li>部分正确：基于checkpoint的局部证明。</li>
 +
      <li>终止：递减量的收敛。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    算法正确性的证明。
 +
    <ul>
 +
      <li>选择排序算法：先证内循环、后证外循环，即as-you-go verification。</li>
 +
      <li>汉诺塔问题的迭代算法：数学归纳法，分奇偶情况讨论。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    计算机辅助的算法正确性证明。
 +
    <ul>
 +
      <li>interactive verification：计算机辅助的交互式证明。</li>
 +
      <li>proof checking：计算机自动证明。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 
 +
=2012年12月27日=
 +
[[媒体文件:讨论记录-第一学期-2班-第13次.pdf|[课件下载]]]
 
<ol>
 
<ol>
−
   <li></li>
+
   <li>
 +
    等势和有限集合。
 +
    <ul>
 +
      <li>等势的本质：双射。</li>
 +
      <li>证明集合有限和求解集合的势之间的联系：都是找m。</li>
 +
      <li>有限集合的子集是有限集合的证明：找双射。</li>
 +
    </ul>
 +
  </li>
 +
  <li>从Exercise 20.13不能推出Z+是有限集合：任意大和无穷大的区别。</li>
 +
  <li>
 +
    从有限集合到无限集合。
 +
    <ul>
 +
      <li>证明集合无限的基本思路：不是有限。</li>
 +
      <li>N是无限集合的证明：反证法+鸽巢原理。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    可数集合。
 +
    <ul>
 +
      <li>可数无限集合的本质：双射到N。</li>
 +
      <li>定理证明中的双射构造：N的子集；NxN；Q。</li>
 +
      <li>可数集合的子集是可数集合的证明：找双射。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    不可数集合。
 +
    <ul>
 +
      <li>证明集合不可数的基本思路：不是可数。</li>
 +
      <li>R是不可数集合的证明：反证法+构造法。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    Metric。
 +
    <ul>
 +
      <li>Metric函数的四个特征。</li>
 +
      <li>集合的距离函数：|(A union B) \ (A intersection B)|，即编辑距离。</li>
 +
    </ul>
 +
  </li>
 
</ol>
 
</ol>
 +
 +
=最后一次作业讲解=
 +
[[媒体文件:讨论记录-第一学期-2班-第14次.pdf|[课件下载]]]

2013年1月11日 (五) 23:02的最新版本

2012年9月27日

[课件下载]

  1. 利用the list求解UD第1章问题1（找水平、垂直对称单词）。
    • 审题：分别水平、垂直翻转后不变，还是同时水平、垂直翻转后不变。
    • plan：包括数据、算法两部分；未必每个字母都要对称（也可以翻转成为另一个字母）；字典中的单词要先转为大写。
  2. 将上述plan转换成计算机可理解的形式（输入、算法、输出）。
    • 输入：字典；字母及其是否对称。
    • 算法：描述的颗粒度要适中。
    • 输出：题目只要找一个单词，不是全部。
  3. 要把大象装冰箱，总共分几步（小品视频）。
    • 问题的输入和算法的输入要匹配。
    • 算法要能处理异常输入。
  4. 算法-->C++程序（计算机仍然不能直接理解）-->机器语言。
  5. 熟悉VC++编程环境。

2012年10月11日

[课件下载]

  1. C++程序设计(1)

2012年10月18日

[课件下载]

  1. 理解Cantor定理。
    • 幂集的含义。
    • 证明的思路。
  2. Implication的陈述方法。
    • 中英文术语的对应。
    • 直译与意译。
  3. Exercise 2.8。
    • 真值表的应用。
    • 形式化问题时的命题选择。
  4. 求解Knights and Knaves：命题的形式化（特别是等价运算符的使用）。
  5. 合取/析取范式的化简。
    • 可合取分量的选择：只有一个变元前的正反符号不同。
    • 编程：循环的使用（特别是循环的条件）。
  6. 量词与集合：命题形式化的全面性与准确性。
  7. proof in cases方法的正确性：命题的形式化。
  8. 扑克牌魔术的原理：将问题形式化为数学归纳法可解的形式（特别是确定n的含义）。
  9. 表达式的范式表示：数学归纳法证明中要确保能覆盖n+1时的所有可能性。

2012年10月23日

[课件下载]

  1. C++程序设计(2)

2012年11月2日

[课件下载]

  1. 不用递归实现second-visit-traversal。
    • 方法1：引入“返回父节点”操作。
    • 方法2：运用堆栈。
  2. 走迷宫的算法。
    • （没有回路的）迷宫可表示为树。
    • 走迷宫可表示为树的遍历。
  3. 树节点的逐层输出：运用队列（操作受限的数组）。
  4. 对战tic-tac-toe的算法。
    • 下每一步棋的目的：最大化获胜概率。
    • 结果最完美的算法：穷举所有可能性。
    • 所有可能性的表示方法：树。
    • 下每一步棋的获胜概率的计算：叶子节点的分布。

2012年11月8日

[课件下载]

  1. “选择排序”算法的流程图：自顶向下解决问题的思路。
    • 先绘制外层循环。
    • 再绘制内层循环。
  2. 子程序（函数）的四个作用及举例。
  3. 所有C++变量名构成的语言：
    • 对应的BNF：自顶向下解决问题的思路；递归定义的多种写法。
    • *对应的有穷状态自动机。
    • 利用有穷状态自动机检查句子的合法性。
    • *利用有穷状态自动机对不合法的句子提出修改建议。
  4. C++变量声明语句对应的BNF：自顶向下解决问题的思路。

2012年11月16日

[课件下载]

  1. C++程序设计(3)

2012年11月22日

[课件下载]

  1. 编译型语言 vs. 解释型语言。
    • 编译型的优势：运行效率、知识产权保护。
    • 解释型的优势：跨平台、交互性。
  2. 用C语言来编写一个C语言编译器自身的绝大部分：递增实现。
  3. 包含于 vs. 属于。
  4. 自顶向下证明集合相关的命题。
    • if and only if的分治。
    • 集合相等的分治（包含于）。
  5. 下标集、幂集、笛卡尔乘积、关系的含义。

2012年11月29日

[课件下载]

  1. 关系的性质：自反、反自反、对称、反对称、强反对称、传递、等价。
  2. 关系的转换。
    • 反对称-->强反对称：去掉(x,x)。
    • 问题10.6：对称+传递-->自反？x在关系中不出现（即找不到y）。
  3. 等价关系（和等价类）、划分及其一一对应：关系/集合的内涵和外延。
  4. 界、极值和确界的比较。
    • 数量。
    • 是否在集合中。
  5. 序。
    • 举例：集合上的“包含”关系是偏序；实数上的“大于等于”关系是全序。
    • 哈斯图：偏序哈斯图的必要条件是无回路（自回路除外）；全序哈斯图的核心是一条有向路径。
  6. 从数学归纳法推导well-ordering principle of N。

2012年12月6日

[课件下载]

  1. 函数。
    • 基本术语：定义域、陪域、值域、单射、满射、双射。
    • 举例：单射非满射；满射非单射；双射。
  2. 函数相等：从集合的角度定义。
  3. 函数相关的证明。
    • 求解函数值域的思路。
    • 证明函数是双射的思路。
  4. 函数的复合。
    • 复合与单射/满射的关系。
    • 举例：f单射、g单射；f单射、g非单射、g◦f单射；f满射、g满射；f非满射、g满射、g◦f满射；f双射、g双射。
  5. 恒等函数的性质证明：well-defined；one-to-one；onto；its own inverse（根据函数相等的定义）。
  6. 函数的像。
    • f-1(y)和f-1({y})的区别：反函数值和反像。
    • Exercise 16.4的反例。

2012年12月13日

[课件下载]

  1. 数独程序设计答辩。

2012年12月20日

[课件下载]

  1. 算法方法的应用（0-1背包问题）。
    • 穷举搜索：通过位串（二进制数）实现子集的穷举。
    • 带剪枝的穷举搜索。
    • 贪心：定义性价比；局部最优。
    • 动态规划：定义子问题；全局最优。
  2. 程序设计中的错误。
    • 语言错误。
    • 逻辑错误：语义错误（=和==的混用）；算法错误。
  3. 算法的正确性。
    • 部分正确：if终止then正确（特例：一个死循环程序）。
    • 终止。
    • 完全正确：部分正确+终止。
  4. 算法正确性的一般证明手法。
    • 部分正确：基于checkpoint的局部证明。
    • 终止：递减量的收敛。
  5. 算法正确性的证明。
    • 选择排序算法：先证内循环、后证外循环，即as-you-go verification。
    • 汉诺塔问题的迭代算法：数学归纳法，分奇偶情况讨论。
  6. 计算机辅助的算法正确性证明。
    • interactive verification：计算机辅助的交互式证明。
    • proof checking：计算机自动证明。

2012年12月27日

[课件下载]

  1. 等势和有限集合。
    • 等势的本质：双射。
    • 证明集合有限和求解集合的势之间的联系：都是找m。
    • 有限集合的子集是有限集合的证明：找双射。
  2. 从Exercise 20.13不能推出Z+是有限集合：任意大和无穷大的区别。
  3. 从有限集合到无限集合。
    • 证明集合无限的基本思路：不是有限。
    • N是无限集合的证明：反证法+鸽巢原理。
  4. 可数集合。
    • 可数无限集合的本质：双射到N。
    • 定理证明中的双射构造：N的子集；NxN；Q。
    • 可数集合的子集是可数集合的证明：找双射。
  5. 不可数集合。
    • 证明集合不可数的基本思路：不是可数。
    • R是不可数集合的证明：反证法+构造法。
  6. Metric。
    • Metric函数的四个特征。
    • 集合的距离函数：|(A union B) \ (A intersection B)|，即编辑距离。

最后一次作业讲解

[课件下载]

取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第一学期)&oldid=429”