一、课程简介：
计算复杂性理论是计算机科学中研究各类问题计算复杂性的分支学科，它使用数学方法对计算中所需的各种资源的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。该课程首先介绍计算复杂性理论的概述、一些计算问题和逻辑，然后详细介绍时间复杂性、NP-完备性、空间复杂性等，最后简单介绍电路复杂性、多项式谱系、随机计算、计数复杂性、扩张图和去随机等。
二、傅育熙教授简介：
傅育熙，1992年获英国曼彻斯特大学计算机博士学位，1994年起在上海交通大学计算机系任职，现为上海交通大学特聘教授。研究领域为理论计算机科学，研究内容涉及程序理论、并发理论、等价性验证、可达性理论、交互理论。是国家杰出青年基金获得者、上海市优秀学科带头人。2000-2009年任上海交通大学计算机系主任，2001-2013年任上海交通大学软件学院院长。学术兼职有：上海高校软件理论研究中心主任、国务院学位委员会第六届学科评议组成员（2010-2014）、上海市计算机学会理事长（2015-2018）、教育部计算机类专业教学指导委员会副主任（2013-2017，2018-2022）。是Mathematical Structures in Computer Science的编委。
傅育熙教授的《计算复杂性理论》课程获得“2019年度高校计算机专业优秀教师奖励计划”。
三、时间安排：
授课日期 |
授课时间 |
上课地点 |
2021.3.5（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.6（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.12（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.13（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.19（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.20（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.26（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.3.27（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.2（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.3（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.9（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.10（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.16（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.17（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.23（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.4.23（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.5.7（周五） |
14:30-16:55 |
信息科学与工程学院院楼624 |
2021.5.8（周六） |
14:30-16:55 |
信息科学与工程学院院楼624 |
注：部分上课时间可能与课表不符，以实际通知为准
四、校内联系人：
联系人：宋勃升老师（16680468519）
欢迎广大博士生、硕士生、高年级本科生及青年教师现场参与！
