“2015级--讨论记录 (第四学期)”的版本间的差异
来自问题求解
小 （→习题讲解） |
（+串匹配主题） |
||
| 第138行： | 第138行： | ||
* 前缀函数的正确性 [[media:银加 前缀函数计算的正确性.pptx | [银加]]] | * 前缀函数的正确性 [[media:银加 前缀函数计算的正确性.pptx | [银加]]] | ||
* KMP算法的正确性 [[media:史子凡 Correctness of KMP algorithm.pptx | [史子凡]]] | * KMP算法的正确性 [[media:史子凡 Correctness of KMP algorithm.pptx | [史子凡]]] | ||
| + | |||
| + | = 2017年05月11日 主题：串匹配 = | ||
| + | |||
| + | == 习题讲解 == | ||
| + | [习题讲解-串匹配]（待上传） | ||
| + | * Gap字符匹配算法 (TC 32.1-4) | ||
| + | * Gap字符匹配自动机 (TC 32.3-5) | ||
| + | * Rabin-Karp匹配算法扩展 (TC 32.2-3) | ||
| + | * 多模式匹配 (TC 32.3-4) | ||
| + | |||
| + | == 报告 == | ||
| + | * Makespan问题的形式化描述 [[media:葛一帆_Makespan问题的形式化描述.pdf | [张天豪]]] | ||
| + | * Delta-TSP近似算法 [[media:张天豪 Delta-TSP近似算法.pptx | [葛一帆]]] | ||
2017年5月15日 (一) 10:25的版本
目录
[隐藏]2017年02月23日 主题：线性规划
习题讲解
- 线性规划的形式
- 线性规划中的对偶
- 使用线性规划建模最短路径问题
报告
问题
- 线性规划在 Game Theory 中的简单应用
2017年03月02日 主题：线性规划
[无新课件；见上次课件]
习题讲解
- 线性规划中的对偶 (Problem 29-1: Linear inequality feasibility problem)
报告
2017年03月09日 主题：群论基础知识
习题讲解
- 群与子群
- Abelian 群
- 二面体群（D_4 与它的10个子群）
- 循环群
报告
问题
- 置换群在 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)
报告
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)
报告
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
报告
2017年05月04日 主题：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 ([参考论文])
报告
2017年05月11日 主题：串匹配
习题讲解
[习题讲解-串匹配]（待上传）
- Gap字符匹配算法 (TC 32.1-4)
- Gap字符匹配自动机 (TC 32.3-5)
- Rabin-Karp匹配算法扩展 (TC 32.2-3)
- 多模式匹配 (TC 32.3-4)
