FI:MA015 Graph Algorithms - Informace o předmětu
MA015 Graph Algorithms
Fakulta informatikypodzim 2023
- Rozsah
- 2/1/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
- Vyučující
- doc. Mgr. Jan Obdržálek, PhD. (přednášející)
- Garance
- doc. Mgr. Jan Obdržálek, PhD.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky - Rozvrh
- St 16:00–17:50 A218
- Rozvrh seminárních/paralelních skupin:
- Předpoklady
- IB002 Algoritmy a datové struktury ||( TYP_STUDIA ( N )&& FAKULTA ( FI ))
Knowledge of basic graph algorithms and datastructures. Specifically, students should already understand the following datastructures and algorithms: Graphs searching: DFS, BFS. Network flows: Ford-Fulkerson. Minimum spanning trees: at least one of Boruvka, Jarnik (Prim), Kruskal. Shortest paths: Bellman-Ford, Dijkstra. Datastructures: priority queues, heaps (incl. Fibonacci), disjoint set (union-find). - Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
- Mateřské obory/plány
- předmět má 26 mateřských oborů, zobrazit
- Cíle předmětu
- The course surveys important graph algorithms beyond those typically covered in basic algorithms and data structures courses. Chosen algorithms span most of the important application areas of graphs algorithms.
- Výstupy z učení
- At the end of the course students will:
- know and understand efficient algorithms for various graph problems, including: minimum spanning trees, network flows, (globally) minimum cuts, matchings (including the assignment problem);
- be able to prove correctness and complexity of these algorithms;
- be able to use dynamic programming to solve problems on tree-like graphs;
- learn a range of techniques useful for designing efficient algorithms and deriving their complexity. - Osnova
- Minimum Spanning Trees. Quick overview of basic algorithms (Kruskal, Jarník [Prim], Borůvka) and their modifications. Advanced algorithms: Fredman-Tarjan, Gabow et al. Randomized algorithms: Karger-Klein-Tarjan. Arborescenses of directed graphs, Edmond's branching algorithm.
- Flows in Networks. Revision - Ford-Fulkerson. Edmonds-Karp, Dinic's algorithm (and its variants), MPM (three Indians) algorithm. Modifications for restricted networks.
- Minimum Cuts in Undirected Graphs. All pairs flows/cuts: Gomory-Hu trees. Global minimum cut: node identification algorithm (Nagamochi-Ibaraki), random algorithms (Karger, Karger-Stein)
- Matchings in General Graphs. Basic algorithm using augmenting paths. Perfect matchings: Edmond's blossom algorithm. Maximum matchings. Min-cost perfect matching: Hungarian algorithm.
- Dynamic Algorithms for Hard Problems. Dynamic programming on trees and circular-arc graphs. Tree-width; dynamic programming on tree-decompositions.
- Graph Isomorphism. Colour refinement. Individualisation-refinement algorithms. Tractable classes of graphs.
- Literatura
- Výukové metody
- Lecture 2 hrs/week plus tutorial every other week.
- Metody hodnocení
- Written exam. To obtain A or B students also have to pass the second, oral part of the exam.
- Vyučovací jazyk
- Angličtina
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (podzim 2023, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2023/MA015