2013级--讨论记录 (第四学期)

2015年3月12日

1. • 反馈群与拉格朗日定理作业

2015年3月19日

[课件下载]

1. • 反馈数论基础作业
   • gcd的概念
   • 素数的概念
   • 梅森素数
   • 4k-1型和6k+1型的素数

2015年3月26日

[课件下载]

1. • 反馈数论算法作业：
   • 基本乘法和除法
   • Euclid算法
   • 互素的概念
   • 中国人剩余定理
   • 模指数运算

2015年4月2日

[课件下载]

1. • 反馈密码算法作业
   • 单字母表加密系统
   • RSA密码系统
   • Euclid算法的分析

2015年4月9日

[课件下载]

1. • 反馈群编码作业
   • 检错和纠错能力
   • 线性编码的性质
   • 基本矩阵和生成矩阵

2015年4月16日

[课件下载]

1. • 反馈字符串匹配算法作业
   • Naive String Matching
   • Rabin-Karp String Matching
   • String Matching based on Automata

2015年4月23日

1. • 反馈问题的形式化描述(JH）作业
   • Verifier的概念
2. 讨论：证明Minimum Makespan Scheduling问题是NPC。
   • Partition <_{p} MS, by restriction
   • 3DM <_{p} Partition
   • 3SAT <_{p} 3DM

2015年5月8日

1. • 习题反馈：（规约的传递性、NP的定义、2-SAT问题的解法（传递闭包或者SCG)、证明Hamiltonian Path问题是NPC问题）

2015年5月15日

1. • 习题反馈：（证明Graham算法的2近似性、距离函数的概念、稳定性的概念）