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

2014年2月21日

[课件下载]

1. 字母表、词、语言：
   • 形式化定义。
   • 实际应用：编码考试成绩；编码图片；编码视频。
   • concatenation和subword的形式化定义。
   • canonical ordering。
2. 判定和优化问题：
   • 判定问题的定义和例子。
   • 优化问题的定义和例子。
3. P和NP：
   • upper bound和lower bound。
   • P、NP、NP-hard、NP-complete。
   • 确定性和非确定性。
   • NPO和PO。