课程号：

TS196008

课程名：

高效算法

英文课程名：

Algorithmic Efficiency

开课单位：

本科生院

授课教师：

Professor Dr.Petra Mutzel

责任教师：

助理教师：

学分/学时：

1/16

选课年级：

大二起

选课专业：

计算机科学、工程专业

教师简介（中英文）：

Mutzel教授出生于1964年，在奥格斯堡大学分别学习过经济数学、数学和计算机科学，毕业于1990年。之后她分别在柏林自由大学数学方向和科隆大学计算机方向读博，1994年在科隆大学获得博士学位。在马克思普朗克研究所和海德堡大学担任助教之后，1999年成为维也纳工业大学教授，2004受到多特蒙德工业大学召唤，成为计算机学院计算机算法教授和专业主任。Mutzel教授的科研成果呈现在众多专业刊物、会议和文献中，受到广泛引用，并在化工信息学、生物信息学、考古、国土规划等多个领域获得应用。

Professor Mutzel was born in 1964 and studied economic mathematics, mathematics and computer science at the University of Augsburg. He graduated in 1990. She then went to the mathematics direction of the Free University of Berlin and the computer direction of the University of Cologne, and received her Ph.D. from the University of Cologne in 1994. After teaching at the Max Planck Institute and the University of Heidelberg, he became a professor at the Technical University of Vienna in 1999 and was summoned by the Dortmund University of Technology in 2004 to become a professor and director of computer algorithms at the School of Computer Science. Professor Mutzel's research results are widely used in many professional publications, conferences and literatures, and have been applied in many fields such as chemical informatics, bioinformatics, archaeology, and land planning.

课程简介（中英文）：

课程内容：

我们研究基本图形问题的图算法，例如与计算机（高度）相关的图形组件，解决二分匹配问题，以及计算网络中的最大流量（和s-t Min Cut）。 我们将分析关于算法的运行时间和正确性。 本课程的重点是研究图形问题的各种算法和分析技术。

1. 介绍 (第1课)

2. 基础图遍历算法(BFS, DFS) (第2课)

2. 寻找图形中的强连通分量 (第3课)

3. 最短路径算法 (Dijkstra, Bellman/Ford) (第4、5课)

3. 图形匹配 (第6、7课)

4. 网络中的最大流量(介绍、Ford and Fulkerson的算法、最大流最小割定理、Dinic 算法、Malhotra et al. 算法、Goldberg-Trajan 算法) (所有算法都包含运行时分析) (第8-11、13课)

5. 摊销分析 (第12、14课)

6. Stoer-Wagner 的最小切割算法 (第15、16课)

We study graph algorithms for basic graph problems such as computing (strongly) connected components of a graph, solving the bipartite matching problem, and computing a maximal flow (and s-t Min Cut) in a network. We will analyse the algorithms with respect to running time and correctness. The focus in this course is to study various algorithmic and analysis techniques for graph problems.

1. Introduction (1)

2. Basic Graph Traversal Algorithms (BFS, DFS) (2)

2. Finding Strong Connected Components of a graph (3)

3. Shortest Path Algorithms (Dijkstra, Bellman/Ford) (4/5)

3. Graph Matching (6/7)

4. Maximal Flows in Networks (Introduction, Algorithm by Ford and Fulkerson, Max-Flow-Min-Cut Theorem, Dinic Algorithm, Malhotra et al. Algorithm, Goldberg-Trajan Algorithm) (all algorithms with runtime analysis) (8-11,13)

5. Amortized Analysis (12,14)

6. Min Cut Algorithm by Stoer-Wagner (15,16)

先修课程：

编程基础、基础算法知识、算法分析、基础数据结构