计算复杂性 (Fall 2018): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>TCSseminar
Created page with "{{Infobox |name = Infobox |bodystyle = |title = <font size=3>计算复杂性 <br>Computational Complexity</font> |titlestyle = |image = |images..."
 
imported>TCSseminar
No edit summary
Line 60: Line 60:


= Announcement =
= Announcement =
* * (2018/9/6) 新学期第一堂课。
* (2018/9/6) 新学期第一堂课。




Line 81: Line 81:


= Lecture Notes =
= Lecture Notes =
# 图灵机、计算复杂性类 P ([https://1drv.ms/p/s!Aj3rgn6TWxE1hpFKdVGGFYb5wdMxDQ sides])
# 图灵机、计算复杂性类 P ([http://45.77.25.129:8000/lec1.pptx sides])
# NP 和 NP 完全问题
# NP 和 NP 完全问题
# 对角化方法
# 对角化方法

Revision as of 10:35, 13 September 2018

计算复杂性
Computational Complexity
Instructor
姚鹏晖
Email pyao@nju.edu.cn
Office 计算机系 502
Class
Class meetings Thursday, 10:10-12:00
仙I-204
Office hours Thursday, 14:00-16:00
计算机系 502
Textbooks
51_KWx_I1yyy_L.jpg
Arora and Barak.
Computational Complexity: A Modern Approach.
Cambridge Univ Press, 2009.
Teaching Assistant
刘明谋
Email liu.mingmou@smail.nju.edu.cn
Office 计算机系 412
v · d · e


Announcement

  • (2018/9/6) 新学期第一堂课。


Course info

  • Instructor : 姚鹏晖
  • Email: pyao@nju.edu.cn
  • Teaching assistant: 刘明谋
  • Email: liu.mingmou@smail.nju.edu.cn
  • Class meeting: Thursday, 10:10-12:00, 仙I-204.
  • Office hour: Thursday, 14:00-16:00, 计算机系 502.

Course materials


Assignments

  • TBA

Lecture Notes

  1. 图灵机、计算复杂性类 P (sides)
  2. NP 和 NP 完全问题
  3. 对角化方法
  4. 空间复杂度
  5. 多项式谱系
  6. 布尔线路
  7. 随机计算
  8. 交互证明
  9. 前沿课题介绍