2015级--讨论记录 (第四学期)
来自问题求解
目录
- 1 2017年02月23日 主题：线性规划
- 2 2017年03月02日 主题：线性规划
- 3 2017年03月09日 主题：群论基础知识
- 4 2017年03月16日 主题：置换群
- 5 2017年03月23日 主题：群同构与群同态
- 6 2017年03月30日 主题：数论基础
- 7 2017年04月06日 主题：数论算法
- 8 2017年04月13日 主题：密码算法
- 9 2017年04月20日 主题：代数编码
- 10 2017年04月27日 主题：问题的形式化描述
- 11 2017年05月04日 主题：NPC理论
- 12 2017年05月11日 主题：串匹配
- 13 2017年05月18日 主题：近似算法
- 14 2017年05月22日 主题：论文阅读报告（Undergraduate Seminars）
- 15 2017年05月25日 主题：论文阅读报告（Undergraduate Seminars）
- 16 2017年05月27日 主题：论文阅读报告（Undergraduate Seminars）
- 17 2017年06月01日 主题：论文阅读报告（Undergraduate Seminars）
- 18 2017年06月07日 主题：论文阅读报告（Undergraduate Seminars）
- 19 2017年06月12日 主题：论文阅读报告（Undergraduate Seminars）
- 20 2017年06月15日 主题：论文阅读报告（Undergraduate Seminars）
- 21 2017年06月19日 主题：论文阅读报告（Undergraduate Seminars）
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)
报告
2017年05月18日 主题：近似算法
习题讲解
- Approximation Classes (补充)
- Makespan 问题的 List-Scheduling 算法 (JH 4.2.1.4)
- Makespan 问题的 Sorting-Scheduling 算法 (JH 4.2.1.5)
- Makespan 问题的 PTAS 算法 (补充)
- Stability of Approximation (JH 4.2.3.3, JH 4.2.3.4, JH 4.2.3.5)
报告
- One-way Communication Protocol [邵仁杰]
2017年05月22日 主题：论文阅读报告（Undergraduate Seminars）
- 王昊庭-吴建鑫-fine-grained image retrieval（暂时无法上传；待解决）
- 陈永恒-李宇峰-safe-ssr
- 何知涵-汪亮-activity-recognition
- 周露-钱柱中-omniflow
2017年05月25日 主题：论文阅读报告（Undergraduate Seminars）
RACOS 系列报告（俞扬）
2017年05月27日 主题：论文阅读报告（Undergraduate Seminars）
- 史子凡-李武军-Deep Cross-Modal Hashing
- 凌弘毅-许畅-self-adaptive application verification
- 姚荣春-曾庆凯-integer-signedness-error （暂时无法上传；待解决）
- 吴一楠-曾庆凯-integer-overflow2buffer-overflow （暂时无法上传；待解决）
2017年06月01日 主题：论文阅读报告（Undergraduate Seminars）
- 高子腾-黎铭-Sample-based software defect prediction with active and semi-supervised learning
- 邵仁杰-黎铭-Learning Unified Features from Natural and Programming Languages for Locating Buggy Source Code
- 魏楠-张利军-Stochastic Optimization for Kernel PCA
2017年06月07日 主题：论文阅读报告（Undergraduate Seminars）
- 蔡其志-周志华-Deep Forest: Towards an Alternative to Deep Neural Networks
- 徐碧村-周志华-DeepMIML Network
- 万子文-仲盛-We can track you if you take the metro
- 李家豪-王崇骏-Don't Forget the Quantifiable Relationship between Words:Using Recurrent Neural Network for Short Text Topic Discovery
