FI:MA015 Grafové algoritmy - Informace o předmětu

MA015 Grafové algoritmy

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í)
Alexandru Popa, Ph.D. (cvičící)
Mgr. David Kruml, Ph.D. (pomocník)

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

Po 14:00–15:50 D2

• Rozvrh seminárních/paralelních skupin:

MA015/01: St 12:00–12:50 C525, A. Popa
MA015/02: St 13:00–13:50 A319, A. Popa
MA015/03: St 14:00–14:50 A218, A. Popa
MA015/04: Po 16:00–16:50 B410, L. Polák

Předpoklady

MB005 Základy matematiky ||( MB101 Lineární modely && MB102 Dif. a integrální počet )||( PřF:M1120 Diskrétní matematika )||PROGRAM(N-IN)||PROGRAM(N-AP)
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)
• 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

Studenti hluboce porozumí řadě základních algoritmů týkajících se prohledávání v grafech, koster, nejkratších cest. Budou schopni navrhovat vlastní korektní algoritmy a odhadovat jejich složitosti.

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 2014, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2014/MA015