“2013级--讨论记录 (第四学期)”的版本间的差异
来自问题求解
（→2015年5月8日） |
（→2015年5月8日） |
||
| （未显示同一用户的4个中间版本） | |||
| 第99行： | 第99行： | ||
</li> | </li> | ||
</ol> | </ol> | ||
| + | |||
=2015年5月8日= | =2015年5月8日= | ||
| + | [[媒体文件:问题与反馈5-8.pdf|[课件下载]]] | ||
<ol> | <ol> | ||
<li> | <li> | ||
<ul> | <ul> | ||
<li> | <li> | ||
| − | + | 规约的传递性 | |
| + | </li> | ||
| + | <li> | ||
| + | NP的定义 | ||
| + | </li> | ||
| + | <li> | ||
| + | 2-SAT问题的解法（传递闭包或者SCG) | ||
| + | </li> | ||
| + | <li> | ||
| + | 证明Hamiltonian Path问题是NPC问题 | ||
</li> | </li> | ||
</ul> | </ul> | ||
| 第112行： | 第123行： | ||
=2015年5月15日= | =2015年5月15日= | ||
| + | [[媒体文件:问题与反馈5-15.pdf|[课件下载]]] | ||
<ol> | <ol> | ||
<li> | <li> | ||
<ul> | <ul> | ||
<li> | <li> | ||
| − | + | 证明Graham算法的2近似性 | |
| + | </li> | ||
| + | <li> | ||
| + | 距离函数的概念 | ||
| + | </li> | ||
| + | <li> | ||
| + | 稳定性的概念 | ||
</li> | </li> | ||
</ul> | </ul> | ||
</ol> | </ol> | ||
2015年5月18日 (一) 10:32的最新版本
目录
2015年3月12日
-
- 反馈群与拉格朗日定理作业
2015年3月19日
-
- 反馈数论基础作业
- gcd的概念
- 素数的概念
- 梅森素数
- 4k-1型和6k+1型的素数
2015年3月26日
-
- 反馈数论算法作业：
- 基本乘法和除法
- Euclid算法
- 互素的概念
- 中国人剩余定理
- 模指数运算
2015年4月2日
-
- 反馈密码算法作业
- 单字母表加密系统
- RSA密码系统
- Euclid算法的分析
2015年4月9日
-
- 反馈群编码作业
- 检错和纠错能力
- 线性编码的性质
- 基本矩阵和生成矩阵
2015年4月16日
-
- 反馈字符串匹配算法作业
- Naive String Matching
- Rabin-Karp String Matching
- String Matching based on Automata
2015年4月23日
-
- 反馈问题的形式化描述(JH）作业
- Verifier的概念
- 讨论：证明Minimum Makespan Scheduling问题是NPC。
- Partition <_{p} MS, by restriction
- 3DM <_{p} Partition
- 3SAT <_{p} 3DM
2015年5月8日
-
- 规约的传递性
- NP的定义
- 2-SAT问题的解法（传递闭包或者SCG)
- 证明Hamiltonian Path问题是NPC问题
2015年5月15日
-
- 证明Graham算法的2近似性
- 距离函数的概念
- 稳定性的概念
