课程大纲

课程大纲

高级算法设计与分析

课程编码:081202M04003H 英文名称:Advanced Algorithm - Design and Analysis 课时:60 学分:3.00 课程属性:专业核心课 主讲教师:孙晓明等

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

预修课程
计算机算法设计与分析,线性代数

大纲内容
第一章 具体名称 15学时 孙晓明
第1节 生日悖论
第2节 利用随机性设计算法
第3节 矩阵乘法的快速验证
第4节 Markov、Chebyshev不等式
第5节 随机复杂性类(RP、BPP、ZPP)
第6节 Mente Carlo算法与Las Vagas算法
第7节 球盒模型
第8节 Chernoff Bounds
第9节 负载均衡问题
第10节 费马小定理与费马测试
第11节 素数判定的BPP算法
第12节 素数判定的RP算法
第13节 完美匹配的代数化算法
第14节 期望方法与去随机化
第15节 LP+rounding技术
第二章 启发式算法 15学时 孙晓明
第1节 组合优化问题与模型
第2节 局部搜索算法
第3节 预处理方法
第三章 计数问题及其算法 15学时 孙晓明
第1节 CSP与#CSP问题
第2节 #P困难性
第3节 复杂性二分定理之一
第4节 复杂性二分定理之二
第5节 张量网络基本概念与运算律之一
第6节 张量网络基本概念与运算律之二
第7节 张量网络基本概念与运算律之三
第8节 基变换在斐波那契门中的应用
第9节 基变换在布尔函数线性检测的应用
第10节 基变换在计数问题构件中的应用
第11节 基变换在容斥原理与匹配数目中的应用
第12节 基变换的其他应用
第13节 行列式、积和式与完美匹配
第14节 完美匹配数目的算法
第15节 函数集合在张量网络结合下的封闭性
第四章 量子算法 15学时 孙晓明
第1节 量子计算中的线性代数
第2节 谱分解定理
第3节 量子力学基本假设
第4节 单比特量子门
第5节 控制量子门
第6节 通用量子门
第7节 量子傅里叶变换
第8节 量子相位估计
第9节 量子Shor算法
第10节 量子黑盒
第11节 量子Deutsch-Jozsa算法
第12节 量子Grover算法
第13节 期末考试

参考书
1、 Randomized Algorithms R. Motwani; P. Raghavan 1995年8月 Cambridge Univ. Press

课程教师信息
孙晓明,中科院计算所研究员。主要研究领域为算法与计算复杂性、量子计算、社交网络算法等。曾获基金委首批优青资助,入选中组部首批万人计划青年拔尖人才,中国密码学会优秀青年奖、密码创新二等奖。目前担任CCF理论专委会副主任,学工委主任助理,密码学会密码数学专委会委员和青工委委员,国际学术会议COCOON指导委员会委员,还担任《软件学报》,《计算机研究与发展》,《JCST》等杂志编委和《中国科学:信息科学》青年编委。
蔡少伟,1986年生,中国科学院软件研究所计算机科学国家重点实验室研究员,博士生导师,分别从北京大学获计算机软件与理论博士学位和澳大利亚Griffith大学IIIS研究所获博士学位。主要研究方向为组合优化算法与逻辑自动推理,在NP难问题和逻辑问题的求解算法上长期处于国际领先,保持多个NP难问题挑战实例的世界求解纪录。获RoboCup中国机器人大赛一等奖,“布尔逻辑可满足性算法比赛”(SAT Challenge 2012)的”Best Solver Award”,获联合逻辑大会奥林匹克(FLOC)银牌(2014年)和金牌(2018年),“全球运筹优化挑战赛—车辆运输智能调度”优胜奖等。发表论文50余篇,半数以上均为CCF A类期刊会议论文,一篇论文被人工智能顶级期刊Artificial Intelligence评为近五年最受欢迎论文。长期担任国际人工智能顶级会议IJCAI、AAAI的程序委员会委员,以及SCI期刊Frontiers of Computer Sciences的Junior Associate Editor。
夏盟佶,中科院软件所研究员。2008年获得博士学位,研究算法与计算复杂性,主要是计数复杂性和张量网络。