FI:MA015 Graph Algorithms - Informace o předmětu
MA015 Graph Algorithms
Fakulta informatikypodzim 2018
- 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í)
Mgr. Bc. Tomáš Janík (cvičící)
RNDr. Bc. Dominik Velan, Ph.D. (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 17. 9. až Po 10. 12. Po 16:00–17:50 D3
- Rozvrh seminárních/paralelních skupin:
MA015/01: Po 17. 9. až Po 10. 12. každé sudé pondělí 10:00–11:50 A319, D. Velan
MA015/02: Po 17. 9. až Po 10. 12. každé liché pondělí 10:00–11:50 A319, D. Velan
MA015/03: každý sudý čtvrtek 12:00–13:50 A320, J. Obdržálek
MA015/04: každý lichý čtvrtek 12:00–13:50 A320, 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 datastructures and algorithms: Graphs searching: DFS, BFS. Network flows: Ford-Fulkerson, Golderg (push-relabel). Minimum spanning trees: Boruvka, Jarnik (Prim), Kruskal. Shortest paths: Bellman-Ford, Dijkstra. Datastructures: 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
- Aplikovaná informatika (program FI, N-AP)
- Bezpečnost informačních technologií (angl.) (program FI, N-IN)
- Bezpečnost informačních technologií (program FI, N-IN)
- Bioinformatika (program FI, N-AP)
- Informační systémy (program FI, N-IN)
- Informatika (angl.) (program FI, D-IN4)
- Informatika (program FI, D-IN4)
- Matematická informatika (program FI, B-IN)
- Paralelní a distribuované systémy (program FI, N-IN)
- Počítačová grafika (program FI, N-IN)
- Počítačové sítě a komunikace (program FI, N-IN)
- Počítačové systémy a technologie (angl.) (program FI, D-IN4)
- Počítačové systémy a technologie (program FI, D-IN4)
- Počítačové systémy (program FI, N-IN)
- Programovatelné technické struktury (angl.) (program FI, N-IN)
- Programovatelné technické struktury (program FI, N-IN)
- Služby - výzkum, řízení a inovace (angl.) (program FI, N-AP)
- Služby - výzkum, řízení a inovace (program FI, N-AP)
- Sociální informatika (program FI, B-AP)
- Teoretická informatika (program FI, N-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, N-SS) (2)
- Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
- Zpracování obrazu (program FI, N-AP)
- 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
- 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.
- Graph Isomorphism. Colour refinement. Individualisation-refinement algorithms. Tractable classes of graphs.
- Dynamic Algorithms for Hard Problems. Dynamic programming on trees and circular-arc graphs. Tree-width; dynamic programming on tree-decompositions.
- Branching and Kernelization Algorithms for Hard Problems. Bounded search trees. Kernelization.
- Literatura
- Výukové metody
- Lecture 2 hrs/week plus 2hr tutorial each 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 2018, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2018/MA015