“2015级--讨论记录 (第四学期)”的版本间的差异

来自问题求解
跳转至： 导航、 搜索
（→‎2017年02月23日 主题：线性规划 [课件]： 上传讨论课件）
 
（未显示2个用户的69个中间版本）
第1行： 第1行：
−
= 2017年02月23日 主题：线性规划 [[media:Lp-tutorial.pdf|[课件]]]=
+
= 2017年02月23日 主题：线性规划 =
−
* 习题讲解
 
−
** 线性规划的形式
 
−
** 线性规划中的对偶
 
−
** 使用线性规划建模最短路径问题
 
  
−
* 报告
+
[[media:Lp-tutorial.pdf|[习题讲解-线性规划]]]
−
** 证明：线性规划的可行区域是凸集 [[media:1 陆纪圆 凸集证明.pptx | [陆纪圆]]]
+
== 习题讲解 ==
−
** 证明 CLRS 引理 29.2 [[media:2 王睿 对引理29.2的证明.pptx | [王睿]]]
+
* 线性规划的形式
 +
* 线性规划中的对偶
 +
* 使用线性规划建模最短路径问题
  
−
* 问题
+
== 报告 ==
−
** 线性规划在 Game Theory 中的简单应用
+
* 证明：线性规划的可行区域是凸集 [[media:1 陆纪圆 凸集证明.pptx | [陆纪圆]]][[media:OpenTopic.LinProg1(葛一帆).pdf|[葛一帆]]]
 +
* 证明 CLRS 引理 29.2 [[media:2 王睿 对引理29.2的证明.pptx | [王睿]]][[media:Presentation-PDF(吴澄杰).pdf ‎|[吴澄杰]]]
  
−
= 2017年03月02日 主题：线性规划 [本次无新课件；见上次课件]=
+
== 问题 ==
−
* 习题讲解
+
* 线性规划在 Game Theory 中的简单应用
−
** 线性规划中的对偶 (Problem 29-1: Linear inequality feasibility problem)
 
  
−
* 报告
+
= 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 | [银加]]][[media:Correctness_of_prefixfunction-徐碧村.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 | [葛一帆]]][[media:张子谦2.pptx|[张子谦]]]
 +
 
 +
= 2017年05月18日 主题：近似算法 =
 +
 
 +
== 习题讲解 ==
 +
[[media:Approx-alg.pdf|习题讲解-近似算法]]
 +
* 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 [[media:邵仁杰 Example5.2.2.5 One-way Communication Protocol.pptx | [邵仁杰]]]
 +
 
 +
= 2017年05月22日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[王昊庭-吴建鑫-fine-grained image retrieval]]（暂时无法上传；待解决）
 +
* [[media:151220012-陈永恒-李宇峰-safe-ssr.pdf | 陈永恒-李宇峰-safe-ssr]]
 +
* [[media:151220037-何知涵-汪亮- approach to real-time activity recognition.pptx | 何知涵-汪亮-activity-recognition]]
 +
* [[media:151220176-周露-钱柱中-omniflow.pdf | 周露-钱柱中-omniflow]]
 +
 
 +
= 2017年05月25日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
RACOS 系列报告（俞扬）
 +
* [[media:151242011-葛一帆-俞扬-RACOS.pdf | 葛一帆-俞扬-RACOS]]
 +
* [[张子谦-俞扬-sequential random embeddings]] （暂时无法上传；待解决）
 +
* [[media:151220122-吴澄杰-高尉-Sequential Classification-based Optimization for Direct Policy Search.pdf | 吴澄杰-高尉-SRACOS]]
 +
* [[media:刘驭壬-俞扬-ASG.pptx | 刘驭壬-俞扬-ASG]]
 +
 
 +
= 2017年05月27日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[media:史子凡-李武军-Deep Cross-Modal Hashing.pptx | 史子凡-李武军-Deep Cross-Modal Hashing]]
 +
* [[media:凌弘毅-许畅-self-adaptive application verification.pptx | 凌弘毅-许畅-self-adaptive application verification]]
 +
* [[姚荣春-曾庆凯-integer-signedness-error]] （暂时无法上传；待解决）
 +
* [[吴一楠-曾庆凯-integer-overflow2buffer-overflow]] （暂时无法上传；待解决）
 +
 
 +
= 2017年06月01日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[media:高子腾-黎铭.pdf |  高子腾-黎铭-Sample-based software defect prediction with active and semi-supervised learning]]
 +
* [[media:邵仁杰-黎铭.pptx| 邵仁杰-黎铭-Learning Unified Features from Natural and Programming Languages for Locating Buggy Source Code]]
 +
* [[media:魏楠-张利军.pptx|魏楠-张利军-Stochastic Optimization for Kernel PCA]]
 +
 
 +
= 2017年06月07日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[media:Deep_Forest.pptx|蔡其志-周志华-Deep Forest: Towards an Alternative to Deep Neural Networks]]
 +
* [[media:徐碧村_deepMIML.pptx|徐碧村-周志华-DeepMIML Network]]
 +
* [[media:万子文.pptx|万子文-仲盛-We can track you if you take the metro]]
 +
* [[media:李家豪.pdf|李家豪-王崇骏-Don't Forget the Quantifiable Relationship between Words:Using Recurrent Neural Network for Short Text Topic Discovery]]
 +
 
 +
= 2017年06月12日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[media:凌嘉伟-黄书剑-PRIMT.pptx | 凌嘉伟-黄书剑-PRIMT]]
 +
* [[media:张天豪-李武军-SCOPE.pptx | 张天豪-李武军-SCOPE]]
 +
* [[media:王睿-瞿裕忠-AI Gaokao.pptx | 王睿-瞿裕忠-AI Gaokao]]
 +
* [[media:葛振兴-姜远-NeC4.5.pptx | 葛振兴-姜远-NeC4.5]]
 +
 
 +
= 2017年06月15日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[media:陆纪圆-黄书剑-Improved NMT with syntax-aware encoder and decoder.pptx | 陆纪圆-黄书剑-Improved NMT with syntax-aware encoder and decoder.pptx ]]
 +
* [[media:余晨宁-姜远-文本分类.pdf | 余晨宁-姜远-文本分类.pdf]]
 +
 
 +
= 2017年06月19日 主题：论文阅读报告（Undergraduate Seminars） =
 +
 
 +
* [[李奕萱-武港山-Object Proposals]] (暂时无法上传，待解决)
 +
* [[media:论文阅读报告（Undergraduate Seminars） 银加.pptx | 银加-王晓亮-分心步行预警系统]]
 +
* [[media:What_can_be_sampled_locally-.pdf | 钱洛文-尹一通-What can be sampled locally?]]

2018年5月10日 (四) 20:47的最新版本

目录

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

[习题讲解-线性规划]

习题讲解

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

报告

问题

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

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

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

习题讲解

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

报告

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

习题讲解

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

报告

问题

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理论

习题讲解

[习题讲解-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)

报告

2017年05月22日 主题：论文阅读报告（Undergraduate Seminars）

2017年05月25日 主题：论文阅读报告（Undergraduate Seminars）

RACOS 系列报告（俞扬）

2017年05月27日 主题：论文阅读报告（Undergraduate Seminars）

2017年06月01日 主题：论文阅读报告（Undergraduate Seminars）

2017年06月07日 主题：论文阅读报告（Undergraduate Seminars）

2017年06月12日 主题：论文阅读报告（Undergraduate Seminars）

2017年06月15日 主题：论文阅读报告（Undergraduate Seminars）

2017年06月19日 主题：论文阅读报告（Undergraduate Seminars）

取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2015级--讨论记录_(第四学期)&oldid=2551”