高级算法设计与分析  081202M04003H

学期:2020—2021学年(春)第二学期 | 课程属性:专业核心课 | 任课教师:孙晓明,田国敬,蔡少伟,夏盟佶
授课时间: 星期一,第5、6、7 节
授课地点: 教一楼109
授课周次: 1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20
课程编号: 081202M04003H 课时: 60 学分: 3.00
课程属性: 专业核心课 主讲教师:孙晓明,田国敬,蔡少伟,夏盟佶 助教:
英文名称: Advanced Algorithm - Design and Analysis 召集人:

教学目的、要求

本课程为计算机学科研究生的专业核心课。本课程讲授和讨论当代算法前沿研究领域的主要思想和关键技术。主要内容有近似算法、搜索算法、随机算法、量子算法、全息算法、工程应用算法等。
    通过本课程的学习,希望学生能了解信息时代算法前沿研究领域,了解算法研究最新研究成果,掌握基本思想和关键技术,培养学生计算机理论与应用的学科研究能力。

预修课程

计算机算法设计与分析,线性代数

教 材

教材:
(1) S. Arora, A Graduate Course is Algorithm Design and Analysis 
(2) R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995
(3) Vijay V. Vazirani, Approximation Algorithms, Springer, 2001
(4) Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

主要内容

第一章  随机算法简介
1.1 生日悖论
1.2 快速排序算法
1.3 矩阵乘积验证
1.4 Markov,Chebyshev不等式
1.5 随机采样
 
第二章  随机算法复杂性类
2.1 RP, co-RP
2.2 ZPP, BPP
2.3 ZPP=RP∩co-RP
2.4 Monte Carlo, Las Vegas算法

第三章  球盒模型
3.1 生日悖论与球盒模型
3.2 Chernoff bounds
3.3 Load balancing

第四章  期望方法与代数化
4.1 3SAT
4.2 MAX-CUT
4.3 Fingerprint方法
4.4 Schwartz-Zippel引理
4.5 多项式恒等验证

第五章  素数判定
5.1 欧拉函数与欧拉定理
5.2 中国剩余定理
5.3 素数判定的BPP算法
5.4 素数判定的co-RP算法

第六章  组合优化问题与建模
6.1 组合优化问题
6.2 NP难问题
6.3 常用模型和通用求解器

第七章  局部搜索
7.1 局部搜索基础概念
7.2 常见的局部搜索算法
7.3 局部搜索技术
7.4 局部搜索分析
7.5 局部搜索案例学习

第八章  图问题的归约规则
8.1 顶点覆盖问题的归约规则
8.2 最大加权团问题的归约规则
8.3 图着色问题的归约规则

第九章  PCP定理
9.1 代数化
9.2 局部检测
9.3 证明与验证

第十章  计数问题
10.1 CSP与#CSP问题
10.2 #P困难性
10.3 复杂性二分定理

第十一章  张量网络与全息归约
11.1 张量网络基本概念与运算律
11.2 基变换及其在计数问题算法中的应用

第十二章  完美匹配
12.1 行列式、积和式与完美匹配
12.2 完美匹配数目的算法
12.3 函数集合在张量网络结合下的封闭性

第十三章  量子力学引论
13.1 线性代数
13.2 量子力学基本假设
13.3 密度算子

第十四章  量子线路
14.1 单量子比特运算
14.2 受控运算
14.3 通用量子门

第十五章  因子分解算法
15.1 量子傅里叶变换
15.2 相位估计
15.3 量子求阶算法
15.4 因子分解算法

第十六章  量子搜索算法
16.1 量子黑盒
16.2 Grover迭代
16.3 量子搜索算法

参考文献

(1) Amy N. Langville and Carl D. Meyer, Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton Univ. press, 2006
(2) Sanjeev Arora, Boaz Barak, Computational Complexity, Cambridge Univ press, 2010
(3) Giuliano Benenti, Giulio Casati and Giuliano Strini, Principles of Quantum Computation and Information, World Scientific, 2004.
(4) 部分章节相关研究论文