图算法
本课程介绍图论和复杂性理论的基本概念，然后介绍图上的算法，尤其是关于匹配和网络流的算法。
讲师
日期
2022年09月13日 至 12月29日
网站
修课要求
离散数学
课程大纲
(Tentative)
- Foundamental concepts: graphs, paths, walks, cycles, trees, isomorphism, adjacency matrix, complexity classes, reduction, completeness, …
- Matching: bipartite maximum matching, bipartite minimum-cost perfect matching, Primal-dual min-cost matching, online maching…
- Flow: max-flow min-cut theorem, Ford-Fulkerson and Edmonds-Karp algorithms, Dinitz's algorithm, Hopcroft-Karp algorithm, Menger's theorem…
- NP-complete problems: max-cut, independent set, …
- Approximate algorithms: vertex cover, max-cut, graph coloring, …
- Spectural graph theory: Courant-Fischer theorem, graph Laplacian, Cheeger's inequality, graph sparsification, …
- Foundamental concepts: graphs, paths, walks, cycles, trees, isomorphism, adjacency matrix, complexity classes, reduction, completeness, …
- Matching: bipartite maximum matching, bipartite minimum-cost perfect matching, Primal-dual min-cost matching, online maching…
- Flow: max-flow min-cut theorem, Ford-Fulkerson and Edmonds-Karp algorithms, Dinitz's algorithm, Hopcroft-Karp algorithm, Menger's theorem…
- NP-complete problems: max-cut, independent set, …
- Approximate algorithms: vertex cover, max-cut, graph coloring, …
- Spectural graph theory: Courant-Fischer theorem, graph Laplacian, Cheeger's inequality, graph sparsification, …
参考资料
1. Introduction to Graph Theory, by Douglas B. West.
2. Modern Graph Theory, by Bela Bollobas.
3. The Design and Analysis of Algorithms, by Dexter Kozen.
2. Modern Graph Theory, by Bela Bollobas.
3. The Design and Analysis of Algorithms, by Dexter Kozen.
听众
Graduate
视频公开
不公开
笔记公开
不公开
语言
中文
讲师介绍
蒋瀚如，现任BIMSA副研究员。他于2019年在中国科学技术大学获得计算机科学与技术博士学位。2019年至2020年间，在鹏城实验室量子计算研究中心担任助理研究员。主要研究方向包括程序设计语言理论、编译器的形式化验证以及量子计算中的程序语言问题。其研究成果多次发表于 PLDI、CAV、OOPSLA 等程序语言领域的顶尖国际会议及期刊，曾获 PLDI 2019 杰出论文奖。