计算机算法设计与分析

课程编码：085400M04006T 英文名称：Algorithms Design and Analysis 课时：60 学分：3.00 课程属性：专业核心课 主讲教师：詹博华等

此课程为智能科学与技术专业研究生的专业核心课程，同时也可以作为相关专业研究生的选修课程。算法处于计算机科学的核心，研究如何在尽可能少的时间和空间开销下解决特定的问题。常见的问题包括搜索、排序、优化、以及图的遍历和寻找最短路径等。我们将探讨针对这些问题的算法设计和分析。此外，我们将研究计算复杂性类，包括NP难问题的定义，以及NP难问题的近似求解方法。

离散数学和数据结构

第一章 课程概述 2.0学时
第1节 Overview
第二章 基础算法 16.0学时
第1节 Foundations (Big-O notation)
第2节 Divide and conquer
第3节 Heapsort and priority queues
第4节 Quicksort and linear-time sorting
第5节 Selection
第6节 Hash tables
第三章 高级算法分析 12.0学时
第1节 Red-black trees
第2节 B-Trees
第3节 Dynamic Programming
第4节 Greedy algorithms
第四章 图论算法 21.0学时
第1节 Amortized analysis
第2节 Review of elementary graph algorithms
第3节 Shortest path algorithms
第4节 Network flow
第5节 Linear programming
第五章 NP难问题和近似方法 9.0学时
第1节 NP Completeness
第2节 Approximation algorithms

詹博华，中科院软件所副研究员，硕士生导师，中科院“百人计划”获得者。主要研究方向为交互式定理证明、证明自动化、嵌入式系统的建模和验证等。使用Isabelle开发了auto2证明自动化工具，以及算法和数据结构验证、形式化数学、量子程序验证等工作。研究成果发表于CAV、IJCAR、TACAS、CADE、ITP、ICFEM等形式化方法领域的主要会议和Journal of Automated Reasoning等期刊。

吴志林，中科院软件所研究员，博士生导师，2020年度CCF-IEEE CS青年科学家获得者。主要研究方向为自动推理、软件形式验证、自动机理论等。曾在LICS、POPL、CAV等形式化验证领域的国际权威学术期刊与会议上发表30余篇论文。近五年负责装发预研项目、国家自然科学基金面上项目并作为技术骨干参与多项国家重点研发计划项目。

David Jansen，中国科学院软件研究所副研究员。曾任奈梅亨大学终身助理教授，研究领域包括概率模型验证、并发理论，在ICALP、TACAS、CONCUR等领域著名会议发表50余篇学术论文，近五年负责多项中科院外籍专家项目，中国科学院大学讲授模型检验相关课程。