FI:MA015 Graph Algorithms - Informace o předmětu
MA015 Graph Algorithms
Fakulta informatikypodzim 2024
- 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 - Předpoklady
- IB002 Algoritmy a datové struktury ||( TYP_STUDIA ( N )&& FAKULTA ( FI ))
Knowledge of basic datastructures (e.g priority queues, heaps, graph representations), graph algorithms (e.g. DFS, BFS) and their correctness. Basic complexity theory (e.g. O-notation, classes P/NP/PSPACE, hardness and completeness). - 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
- Informatika (program FI, B-INF) (2)
- 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 2 hrs tutorial every other week.
- Metody hodnocení
- Combined written and oral exam.
- Vyučovací jazyk
- Angličtina
- Další komentáře
- Předmět je vyučován každoročně.
Výuka probíhá každý týden.
- Statistika zápisu (nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2024/MA015