查看“2012级--讨论记录 (第一学期)”的源代码
←
2012级--讨论记录 (第一学期)
跳转至:
导航
、
搜索
因为以下原因,您没有权限编辑本页:
您所请求的操作仅限于该用户组的用户使用:
用户
您可以查看与复制此页面的源代码。
=2012年9月27日= [[媒体文件:讨论记录-第一学期-2班-第1次.pdf|[课件下载]]] <ol> <li> 利用the list求解UD第1章问题1(找水平、垂直对称单词)。 <ul> <li>审题:分别水平、垂直翻转后不变,还是同时水平、垂直翻转后不变。</li> <li>plan:包括数据、算法两部分;未必每个字母都要对称(也可以翻转成为另一个字母);字典中的单词要先转为大写。</li> </ul> </li> <li> 将上述plan转换成计算机可理解的形式(输入、算法、输出)。 <ul> <li>输入:字典;字母及其是否对称。</li> <li>算法:描述的颗粒度要适中。</li> <li>输出:题目只要找一个单词,不是全部。</li> </ul> </li> <li> 要把大象装冰箱,总共分几步(小品视频)。 <ul> <li>问题的输入和算法的输入要匹配。</li> <li>算法要能处理异常输入。</li> </ul> <li> 算法-->C++程序(计算机仍然不能直接理解)-->机器语言。 </li> <li> 熟悉VC++编程环境。 </li> </ol> =2012年10月11日= [[媒体文件:讨论记录-第一学期-第2次.pdf|[课件下载]]] <ol> <li>C++程序设计(1)</li> </ol> =2012年10月18日= [[媒体文件:讨论记录-第一学期-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> <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> =2012年11月29日= [[媒体文件:讨论记录-第一学期-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> <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> =最后一次作业讲解= [[媒体文件:讨论记录-第一学期-2班-第14次.pdf|[课件下载]]]
返回至
2012级--讨论记录 (第一学期)
。
导航菜单
个人工具
登录
命名空间
页面
讨论
变种
视图
阅读
查看源代码
查看历史
更多
搜索
导航
首页
最近更改
随机页面
帮助
工具
链入页面
相关更改
特殊页面
页面信息