MA015 Graph Algorithms

Fakulta informatiky
podzim 2015
Rozsah
2/1. 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í)
Frédéric Dupont Dupuis, Ph.D. (cvičící)
Mgr. Bc. Tomáš Janík (cvičící)
prof. RNDr. Petr Hliněný, Ph.D. (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Po 12:00–13:50 D2
  • Rozvrh seminárních/paralelních skupin:
MA015/T01: St 23. 9. až Út 22. 12. St 13:00–14:35 106, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
MA015/01: každé liché pondělí 10:00–11:50 C525, F. Dupont Dupuis
MA015/02: každé sudé pondělí 10:00–11:50 C525, F. Dupont Dupuis
MA015/03: každý lichý pátek 8:00–9:50 C511, F. Dupont Dupuis
MA015/04: každý sudý pátek 8:00–9:50 C511, F. Dupont Dupuis
MA015/05: každé liché pondělí 16:00–17:50 A319, J. Obdržálek
MA015/06: každé sudé pondělí 16:00–17:50 A319, J. Obdržálek
Předpoklady
MB005 Základy matematiky ||( MB101 Lineární modely && MB102 Dif. a integrální počet )||( MB201 Lineární modely B && MB102 Dif. a integrální počet )||( MB101 Lineární modely && MB202 Dif. a integrální počet B )||( MB201 Lineární modely B && MB202 Dif. a integrální počet B )||( PřF:M1120 Diskrétní matematika )||PROGRAM(N-IN)||PROGRAM(N-AP)
Knowledge of basic graph algorithms, to the extent covered by the course IV003 Algorithms and Data Structures II. Specifically, students should already understand the following algorithms: Graphs searching: DFS, BFS. Network flows: Ford-Fulkerson, Golderg (push-relabel). Minimum spanning trees: Boruvka, Jarnik (Prim), Kruskal. Shortest paths: Bellman-Ford, Dijkstra.
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
Cíle předmětu
At the end of the course students will under know and understand important graph algorithms beyond the reach of standard algorithms and data structures courses. Covered algorithms span most of the important application areas of graphs algorithms. The students also should be able to choose an algorithm best suited for a given task, modifying it when necessary, and estimate its complexity.
Osnova
  • Cover problems: vertex cover, dominating set, feedback vertex set, feedback arc set. Parameterized complexity of algorithms.
  • Dynamic algorithms on tree-like structures: algorithms for trees, graphs of bounded tree-width, path-width, clique-width, oriented tree-like graphs.
  • Graph isomorphism: trees, planar graphs, general-case heuristics (colour coding).
  • Planar drawing and testing: path addition method, PQ/SPQR trees, Boyer-Myrwold algorithm.
  • Network flows: Edmonds-Karp algorithm. Dinic's algorithm and its modifications (e.g. unit capacities, integer capacities). Three Indians algorithm. Minimum-cost flow algorithms.
  • Shortest paths: A* algorithm, reach-based algorithms, hub labelling, hierarchical decompositions, distance oracles.
  • Spanning trees: modifications of Borůvka's and Jarnik§s algorithm for particular input instances (e.g. planar graphs). Steiner trees.
  • Cuts (non-flow based algorithms): Gomory-Hu trees, globally minimum cut, Nagamochi-Ibaraki algorithm, randomized algorithms (Karger-Stein).
Literatura
    doporučená literatura
  • MAREŠ, Martin. Krajinou grafových algoritmů. Pracovní verze. ITI, 2015. URL info
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Výukové metody
Lecture 2 hrs/week plus 2hr tutorial each other week.
Metody hodnocení
Written exam.
Vyučovací jazyk
Angličtina
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2003, podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.