查看“2015级--讨论记录 (第四学期)”的源代码

= 2017年02月23日 主题：线性规划 =

[[media:Lp-tutorial.pdf|[习题讲解-线性规划]]]
== 习题讲解 ==
* 线性规划的形式
* 线性规划中的对偶
* 使用线性规划建模最短路径问题

== 报告 ==
* 证明：线性规划的可行区域是凸集 [[media:1 陆纪圆 凸集证明.pptx | [陆纪圆]]][[media:OpenTopic.LinProg1(葛一帆).pdf|[葛一帆]]]
* 证明 CLRS 引理 29.2 [[media:2 王睿 对引理29.2的证明.pptx | [王睿]]][[media:Presentation-PDF(吴澄杰).pdf ‎|[吴澄杰]]]

== 问题 ==
* 线性规划在 Game Theory 中的简单应用

= 2017年03月02日 主题：线性规划 =
[无新课件；见上次课件]
== 习题讲解 ==
* 线性规划中的对偶 (Problem 29-1: Linear inequality feasibility problem)

== 报告 ==
* 循环群非单位元讨论 [[media:循环群非单位元讨论-徐碧村.pptx|[徐碧村]]] [[media:循环群的生成元_魏楠.pptx|[魏楠]]]
* 交换群证明 [[media:交换群证明-陈永恒.pptx|[陈永恒]]]

= 2017年03月09日 主题：群论基础知识 =

== 习题讲解 ==
* 群与子群
* Abelian 群
* 二面体群（D_4 与它的10个子群）
* 循环群

== 报告 ==
* 2阶魔方背后的群论知识 [[media:Rubik's Cube-吴澄杰,陈永恒.pptx|[吴澄杰、陈永恒]]][[media:二阶魔方还原 吴一楠.pdf|[吴一楠]]]

== 问题 ==
* 置换群在 15-Puzzle 中的应用 [[media:An Analysis of the 15-Puzzle.pdf|[An Analysis of the 15-Puzzle.pdf]]] （''建议：根据所讲解的构造性证明做“15-Puzzle Solver”编程练习''）

= 2017年03月16日 主题：置换群 =

== 习题讲解 ==
* 循环群的子群 (TJ 4.35; P72)
* 二面体群的中心 (TJ 5.29; P90)
* 正四面体的旋转对称群 (TJ 5.16; P89)
* 立方体的旋转对称群 (TJ 5.5; P88)

== 报告 ==
* 群同态基本定理 [[media:群同态基本定理 (何知涵).pptx|[何知涵]]]
* 第二同构定理 [[media:万子文-第二同构定理.pdf|[万子文]]]

= 2017年03月23日 主题：群同构与群同态 =

[[media:Rotational-symmetries-tutorial.pdf|[习题讲解-旋转对称群]]]  [[media:Homomorphism-tutorial.pdf|[习题讲解-群同态]]]
== 习题讲解 ==
* 立方体的旋转对称群 (TJ 5.5; P88)
* 八阶群的结构 (TJ 9.11; P152)
* 群的消去律 (TJ 9.23; P153)
* 群的同构 (TJ 11.18; P113)

== 报告 ==
* 数学归纳法 [[media:数学归纳法-刘驭壬.pptx|[刘驭壬]]][[media:张子谦open topic.pdf|[张子谦]]]
* Euclid最大公约数算法正确性证明[[media:李奕萱-欧几里得算法.pdf|[李奕萱]]]

= 2017年03月30日 主题：数论基础 =

== 习题讲解 ==
[[media:4-5反馈.pptx | [习题讲解-数论基础]]]
* 数学归纳法 (TJ2.13, P32)
* 6n+1 形式的素数 (TJ2.29, P33)

== 报告 ==
* 整数相乘算法 [[media:周露-151220176.pdf|[周露]]][[media:151220030 高子腾.pdf|[高子腾]]]

= 2017年04月06日 主题：数论算法 =

== 习题讲解 ==
[[media:Number-theoretic-algs-tutorial.pdf | [习题讲解-数论算法 (with-pause)]]] [[media:Number-theoretic-algs-tutorial-handout.pdf | [习题讲解-数论算法 (no-pause)]]]
* 模运算消去律 (TC31.4-2)
* Euclid 算法复杂度 (TC31.2-5)
* 两两互素 (TC31.2-9)
* 中国剩余定理

== 报告 ==
* 密码算法实现 ([[media:Germany Cipher Encode 张天豪.pptx|[张天豪-加密]]] [[media:Germany Cipher Decode 陆纪圆.pptx | [陆纪圆-解密]]])（[[media:ADFGVX（李奕萱）.pdf|李奕萱-加密]][[media:ADFGVX_decipher.pdf|[蔡其志-解密]]]）
* 中国剩余定理 [[media:邵仁杰 151180107 中国剩余定理.pptx | [邵仁杰]]][[media:余晨宁_中国剩余定理.pdf|[余晨宁]]]

= 2017年04月13日 主题：密码算法 =

== 习题讲解 ==
[[media:4-7反馈.pdf|[习题讲解：密码算法]]]
*RSA的健壮性（习题TJ 7-12;TC 31.7-2,3）
*基于位运算的细粒度算法复杂度分析（TC Problem 31-2，31-3）
*素数判定与Carmichael数（TC 31.8-2）

== 报告 ==
* 距离定义 [[media:周露_距离定义.pdf | [周露]]] [[media:葛振兴.pdf|[葛振兴]]]
* 关于距离的想法 [[media:钱洛文_Distances_in_Hamming_space.pdf | [钱洛文]]][[media:A_new_distance（凌嘉伟）.pdf ‎|[凌嘉伟]]]

= 2017年04月20日 主题：代数编码 =

== 习题讲解 ==
[[media:Coding-theory-tutorial.pdf | [习题讲解-代数编码]]]
* 线性码性质 (TJ-8.18)
* 线性码性质 (TJ-8.19)
* Generator 矩阵不唯一 (TJ-8.7)
* Parity-check 矩阵不唯一 (TJ-8.11)
* 矩阵规模与纠错能力 (TJ-8.21; TJ-8.23)

== 报告 ==
* 字典序 [[media:凌弘毅_字典序.pptx | [凌弘毅]]][[media:字典序-李家豪.pdf|[李家豪]]]
* 介绍 SAT 与 Max-SAT [[media:SAT和MAX-SAT.pptx | [何知涵]]][[media:SAT and max-sat.pptx|[蔡其志]]]

= 2017年04月27日 主题：问题的形式化描述 =

== 习题讲解 ==
[[media:4-9反馈.pptx | [习题讲解-问题的形式化描述]]]
* 问题的形式化描述 (JH 2.3.1.7、2.3.1.8)
* Verifier for NP-C problems (JH 2.3.3.8)
* Super Mario Brothers is NP-Hard [[media:Eric_Demaine_Classic_Nintendo_Games_are_(Computationally)_Hard.pdf| [参考论文]]]
* Pseudo-polynomial time, Weak NP-C, Strong NP-C

== 报告 ==
* TSP问题难度证明 [[media:TSP-王睿.pptx | [王睿]]] [[media:TSP问题难度证明-万子文.pptx | [万子文]]]
* NP=VP [[media:刘驭壬 NP的等价定义.pptx | [刘驭壬]]] [[media:NP与VP-王昊庭.pdf | [王昊庭]]]

= 2017年05月04日 主题：NPC理论 =

== 习题讲解 ==
[[media:P-np.pdf | [习题讲解-NPC理论]]]
* Call subroutines (TC34.1-5)
* NP closure properties (TC 34.2-4)
* HAM-PATH is NP-complete (TC 34.5-6)
* HAM-CYCLE-LIST is in P (TC 34.2-3)
* G^3 is in HAM-CYCLE (TC 34.2-11)
* Tetris is NP-complete ([[media:Tetris_is_Hard,_Made_Easy_(Breukelaar).pdf|[参考论文]]])

== 报告 ==
* 前缀函数的正确性 [[media:银加 前缀函数计算的正确性.pptx | [银加]]]
* KMP算法的正确性 [[media:史子凡 Correctness of KMP algorithm.pptx | [史子凡]]]

= 2017年05月11日 主题：串匹配 =

== 习题讲解 ==
[[media:反馈4-11.pptx|习题讲解-串匹配]]
* Gap字符匹配算法 (TC 32.1-4)
* Gap字符匹配自动机 (TC 32.3-5)
* Rabin-Karp匹配算法扩展 (TC 32.2-3)
* 多模式匹配 (TC 32.3-4)

== 报告 ==
* Makespan问题的形式化描述 [[media:葛一帆_Makespan问题的形式化描述.pdf | [张天豪]]][[media:字符串匹配姚荣春.pdf|[姚荣春]]]
* Delta-TSP近似算法 [[media:张天豪 Delta-TSP近似算法.pptx | [葛一帆]]]