imported>TCSseminar |
imported>TCSseminar |
| Line 1: |
Line 1: |
| {{Infobox
| | 截止2018.10.24 13:00，作业3已提交名单如下 |
| |name = Infobox
| | {| class="wikitable" |
| |bodystyle =
| | |171250623 || 姜勇刚 |
| |title = <font size=3>计算复杂性
| | |- |
| <br>Computational Complexity</font>
| | |DZ1733021 || 夏瑞 |
| |titlestyle =
| | |- |
| | | |DZ1833028 || 徐闽泽 |
| |image =
| | |- |
| |imagestyle =
| | |151220130 || 伍昱名 |
| |caption =
| | |- |
| |captionstyle =
| | |161250027 || 高忆 |
| |headerstyle = background:#ccf;
| | |- |
| |labelstyle = background:#ddf; | | |MP1733012 || 陆璐 |
| |datastyle = | | |- |
| | | |MF1833009 || 陈越 |
| |header1 =Instructor | | |- |
| |label1 = | | |DZ1833011 || 何雨橙 |
| |data1 = | | |} |
| |header2 = | |
| |label2 = | |
| |data2 = 姚鹏晖 | |
| |header3 = | |
| |label3 = Email | |
| |data3 = pyao@nju.edu.cn | |
| |header4 = | |
| |label4= Office | |
| |data4= 计算机系 502 | |
| |header5 = Class
| |
| |label5 =
| |
| |data5 =
| |
| |header6 = | |
| |label6 = Class meetings | |
| |data6 = Thursday, 10:10-12:00 <br> 仙I-204 | |
| |header7 = | |
| |label7 = Place | |
| |data7 = | |
| |header8 = | |
| |label8 = Office hours
| |
| |data8 = Thursday, 14:00-16:00 <br>计算机系 502
| |
| |header9 = Textbooks | |
| |label9 = | |
| |data9 = | |
| |header10 = | |
| |label10 =
| |
| |data10 = https://image.ibb.co/drYZEp/51_KWx_I1yyy_L.jpg
| |
| |header11 = | |
| |label11 = | |
| |data11 = Arora and Barak. <br>''Computational Complexity: A Modern Approach''.<br> Cambridge Univ Press, 2009. | |
| |header12 = Teaching Assistant | |
| |data13= 刘明谋
| |
| |label14=Email
| |
| |data14=liu.mingmou@smail.nju.edu.cn | |
| |label15=Office | |
| |data15=计算机系 412 | |
| |belowstyle = background:#ddf; | |
| |below =
| |
| }}
| |
| | |
| | |
| | |
| = Announcement =
| |
| * (2018/9/6) 新学期第一堂课。
| |
| | |
| | |
| = Course info =
| |
| * '''Instructor ''': 姚鹏晖 ([mailto:pyao@nju.edu.cn pyao@nju.edu.cn])
| |
| * '''Teaching assistant''': 刘明谋 ([mailto:liu.mingmou@smail.nju.edu.cn 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 =
| |
| * [https://www.amazon.com/dp/0521424267 Arora and Barak. Computational Complexity: A Modern Approach. Cambridge Univ Press, 2009.]
| |
| * [https://www.amazon.cn/dp/B007VXH70K/ Arora and Barak. 计算复杂性的现代方法. (英语). 世界图书出版公司. 2012.]
| |
| * [https://www.amazon.cn/dp/B018LW74IY/ Arora and Barak. 计算复杂性:现代方法. (中文翻译). 机械工业出版社. 2016.]
| |
| | |
| | |
| = Assignments =
| |
| * TBA
| |
| | |
| = Lecture Notes =
| |
| # 图灵机、计算复杂性类 P ([http://45.77.25.129:8000/lec1.pptx slides])
| |
| # NP 和 NP 完全问题
| |
| # 对角化方法
| |
| # 空间复杂度
| |
| # 多项式谱系
| |
| # 布尔线路
| |
| # 随机计算
| |
| # 交互证明
| |
| # 前沿课题介绍
| |