“2017级--小班讨论 (第四学期)”的版本间的差异

• 2017-3-final-exam.pdf
• 4-0-exam-scan

• 无

• Robbins' Theorem on SCC Orientation
• Linear-time algorithm to find an odd-length cycle in a directed graph

 不仅仅是判断有无，而是要找出一个（如果存在）有向奇圈。

• 4-1-lp-1-scan

• Pivot 操作

1. 殷兆恒
2. 黄秉焜

• 饲养成本问题

1. 周涛
2. 孙旭东

• Chapter 7 of "Algorithms"（算法概论）By Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani

 更深刻地理解 Simplex Method 与 Duality 理论

• Chapter 8 of "Introduction to Linear Algebra (4th Edition)" By Gilbert Strang

 初读不易理解；再读也不易理解; 一旦理解，受益匪浅。

• 4-1-lp-2-scan

• “移动”群之一

1. 肖江
2. 李顶为

• “移动”群之二

1. 谢乃容
2. 郑奘巍

• Section 8.7 of "Combinatorial Optimization" by Christos H. Papadimitriou, Kenneth Steiglitz

 Linear-inequality Feasibility 问题

• 4-2-cyclic-group-scan

• 二阶魔方

1. 姜勇刚
2. 张灵毓

• 置换与逆序

1. 刘寒
2. 吕云哲

• 无

• 4-3-dihedral-group-scan

• 群第二同构定理

1. 凌晨宇
2. 马常风

• 问题10中的结论

1. 李博文
2. 鄢振宇

• Dihedra Group (by Keith Conrad)

 关于 Dihedra Group 的更多内容

• 4-4-direct-product
• 4-4-direct-product-handout
• 4-4-direct-product-scan

• KMP 正确性

1. 丁保荣
2. 张天昀

• 字典树

1. 彭翔宇
2. 杜星亮

• 4-5-polyhedral-group-I
• 4-5-polyhedral-group-I-handout
• 4-5-polyhedral-group-I-scan

• 4-5-polyhedral-group-II
• 4-5-polyhedral-group-II-handout

• 无

• Subgroups of S4

 S4 的所有子群以及它们之间错综复杂的关系

• 4-grouptheory-isomorphism
• 4-grouptheory-isomorphism-handout
• 4-grouptheory-isomorphism-scan

• Peano 公理

1. 何润雨
2. 殷天润

• 乘法算法

1. 裴一凡
2. 戴若石

• On Cancellation in Groups

 什么时候消去律成立?

• 4-6-basic-number-theory-scan

• 加密、解密算法

1. 袁彦
2. 张廷昊

• 中国剩余定理

1. 徐臣
2. 张梓悦

• Strong Duality for a Special Class of Integer Programs (Meyer 1977)

 从“对偶”的角度看待 GCD

• 4-7-number-theoretic-algorithms-scan

• 各种“花式”距离

1. 裴明亮
2. 谢逸

• 编码率

1. 何伟
2. 杨欣然

• 无

• 4-8-rsa
• 4-8-rsa-handout

• 无

• New Directions in Cryptography (1976)

 提出密钥交换协议与公开密钥加密系统的革新性的论文

• RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

 RSA 关于 RSA 的论文。

• Attacks on RSA Cryptosystem (math.boisestate.edu)

 RSA 使用不当，容易遭致攻击。

• 无

• 4-9-coding
• 4-9-coding-handout

• Turing Machine

1. 李凯旭
2. 兰兆炜

• SAT

1. 陶绍诚
2. 匡舒磊

• A Mathematical Theory of Communication (Shannon 1948)

• 4-11-p-np-I
• 4-11-p-np-I-handout

• NP 定义

1. 董杨静
2. 桑百惠

• TSP is in NPC

1. 刘恩萌
2. 毛一鸣

• Reducibility Among Combinatorial Problems (Karp 1972）

 经典论文。21 个 NPC 问题。

• 4-11-p-np-II
• 4-11-p-np-II-handout

• Δ-TSP

1. 高天朗
2. 王腾

• SCP

1. 毕秋宇
2. 梁宇方

• The History and Status of the P versus NP Question (STOC92, Michael Sipser)

 Godel's Letter