FI:MA015 Grafové algoritmy - Informace o předmětu
MA015 Grafové algoritmy
Fakulta informatikypodzim 2012
- Rozsah
- 2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
- Vyučující
- doc. RNDr. Libor Polák, CSc. (přednášející)
Mgr. David Kruml, Ph.D. (cvičící) - Garance
- doc. RNDr. Libor Polák, CSc.
Fakulta informatiky
Kontaktní osoba: doc. RNDr. Libor Polák, CSc.
Dodavatelské pracoviště: Přírodovědecká fakulta - Rozvrh
- Čt 14:00–15:50 G101
- Rozvrh seminárních/paralelních skupin:
MA015/02: St 8:00–8:50 G125, D. Kruml
MA015/03: St 9:00–9:50 G125, D. Kruml - Předpoklady
- MB005 Základy matematiky ||( MB101 Lineární modely && MB102 Dif. a integrální počet )|| M005 Základy matematiky
Schopnost komunikace o základních matematických objektech a algoritmech. - 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í (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)
- Informatika (program FI, N-IN)
- 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
- Jsou prezentovány základní grafové algoritmy: průzkumy, hledání minimální kostry a rozličné algoritmy pro hledání nejkratších cest a maximálních toků v sítích. Ve všech případech dokazujeme korektnost a odhadujeme složitost.
- Osnova
- Elementární grafové algoritmy (reprezentace grafů, prohledávání do šířky, prohledávání do hloubky, topologické uspořádání, silně souvislé komponenty).
- Minimální kostry (růst minimální kostry, algoritmy Kruskala a Prima).
- Nejkratší cesty z jediného vrcholu (nejkratší cesty a relaxace, Dijkstrův algoritmus, Bellman-Fordův algoritmus, nejkratší cesty v orientovaných acyklických grafech).
- Nejkratší cesty mezi všemi dvojicemi vrcholů (nejkratší cesty a násobení matic, Floyd-Warshallův algoritmus, Johnsonův algoritmus pro řídké grafy).
- Maximální toky v sítích (sítě, Ford-Fulkersonova metoda, maximální párování v bipartitních grafech).
- Datové struktury pro grafové algoritmy (binární haldy, prioritní fronty, datové struktury pro systémy disjunktních množin).
- Literatura
- 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
- Jednou týdně klasická dvouhodinová přednáška. V navazujícím hodinovém semináři studenti referují řešení předem zadaných úloh.
- Metody hodnocení
- Zkouška je písemná. 30% bodů tvoří řešení konkrétní úlohy některým se známých algoritmů. Podstatná část je předpracovaná nová úloha. Studenti doplňují vynechané části algoritmu, demonstrují ho na konkrétních datech, dokazují jeho korektnost a odhadují složitost.
- Informace učitele
- http://www.math.muni.cz/~polak/grafy.html
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (podzim 2012, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2012/MA015