2017年4月27日 (四) 17:36的版本

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

[习题讲解-线性规划]

习题讲解

• 线性规划的形式
• 线性规划中的对偶
• 使用线性规划建模最短路径问题

报告

• 证明：线性规划的可行区域是凸集 [陆纪圆][葛一帆]
• 证明 CLRS 引理 29.2 [王睿][吴澄杰]

问题

• 线性规划在 Game Theory 中的简单应用

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

[无新课件；见上次课件]

习题讲解

• 线性规划中的对偶 (Problem 29-1: Linear inequality feasibility problem)

报告

• 循环群非单位元讨论 [徐碧村] [魏楠]
• 交换群证明 [陈永恒]

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

习题讲解

• 群与子群
• Abelian 群
• 二面体群（D_4 与它的10个子群）
• 循环群

报告

• 2阶魔方背后的群论知识 [吴澄杰、陈永恒][吴一楠]

问题

• 置换群在 15-Puzzle 中的应用 [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)

报告

• 群同态基本定理 [何知涵]
• 第二同构定理 [万子文]

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

[习题讲解-旋转对称群] [习题讲解-群同态]

习题讲解

• 立方体的旋转对称群 (TJ 5.5; P88)
• 八阶群的结构 (TJ 9.11; P152)
• 群的消去律 (TJ 9.23; P153)
• 群的同构 (TJ 11.18; P113)

报告

• 数学归纳法 [刘驭壬][张子谦]
• Euclid最大公约数算法正确性证明[李奕萱]

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

习题讲解

[习题讲解-数论基础]

• 数学归纳法 (TJ2.13, P32)
• 6n+1 形式的素数 (TJ2.29, P33)

报告

• 整数相乘算法 [周露][高子腾]

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

习题讲解

[习题讲解-数论算法 (with-pause)] [习题讲解-数论算法 (no-pause)]

• 模运算消去律 (TC31.4-2)
• Euclid 算法复杂度 (TC31.2-5)
• 两两互素 (TC31.2-9)
• 中国剩余定理

报告

• 密码算法实现 ([张天豪-加密] [陆纪圆-解密])（李奕萱-加密[蔡其志-解密]）
• 中国剩余定理 [邵仁杰][余晨宁]

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

习题讲解

[习题讲解：密码算法]

• RSA的健壮性（习题TJ 7-12;TC 31.7-2,3）
• 基于位运算的细粒度算法复杂度分析（TC Problem 31-2，31-3）
• 素数判定与Carmichael数（TC 31.8-2）

报告

• 距离定义 [周露] [葛振兴]
• 关于距离的想法 [钱洛文][凌嘉伟]

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

习题讲解

[习题讲解-代数编码]

• 线性码性质 (TJ-8.18)
• 线性码性质 (TJ-8.19)
• Generator 矩阵不唯一 (TJ-8.7)
• Parity-check 矩阵不唯一 (TJ-8.11)
• 矩阵规模与纠错能力 (TJ-8.21; TJ-8.23)

报告

• 字典序 [凌弘毅][李家豪]
• 介绍 SAT 与 Max-SAT [何知涵][蔡其志]

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

习题讲解

[习题讲解-问题的形式化描述]

• 问题的形式化描述 (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 [参考论文]
• Pseudo-polynomial time, Weak NP-C, Strong NP-C

报告

• TSP问题难度证明 [王睿] [万子文]
• NP=VP [刘驭壬] [王昊庭]