Název:

Grafové algoritmy

Zkratka:GAL
Ak.rok:2011/2012
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI-volitelný
IT-MGR-2MBS-volitelný
IT-MGR-2MGM-volitelný
IT-MGR-2MGM.-volitelný
IT-MGR-2MIN-volitelný
IT-MGR-2MIN.-volitelný
IT-MGR-2MIS-volitelný
IT-MGR-2MIS.-volitelný
IT-MGR-2MMI-volitelný
IT-MGR-2MMM2.povinný
IT-MGR-2MPS-volitelný
IT-MGR-2MPV-volitelný
IT-MGR-2MSK1.povinně volitelný - skupina M
Vyučovací jazyk:čeština
Informace veřejné:http://www.fit.vutbr.cz/study/courses/GAL/public/
Kredity:5 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:60150025
Garant:Meduna Alexander, prof. RNDr., CSc., UIFS
Přednášející:Křivka Zbyněk, Ing., Ph.D., UIFS
Cvičící:Křivka Zbyněk, Ing., Ph.D., UIFS
Zemek Petr, Ing., UIFS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav informačních systémů FIT VUT v Brně
Prerekvizity: 
Diskrétní matematika (IDA), UMAT
Formální jazyky a překladače (IFJ), UIFS
 
Cíle předmětu:
Seznámit se s grafy a grafovými algoritmy včetně jejich složitostí.
Anotace:
Předmět diskutuje různé reprezentace grafů v počítači a grafové algoritmy pro problémy typu prohledávání grafů (do hloubky, do šířky), topologické uspořádání grafů, komponenty grafů a silně souvislé komponenty, stromy a minimální kostry, nejkratší cesty z jednoho vrcholu do všech ostatních či ze všech vrcholů do všech ostatních, maximální tok a minimální řez, maximální párování v bipartitních grafech, Eulerovské grafy a barvení grafů. U všech algoritmů je kladen důraz na pochopení principů a na studium složitosti navržených algoritmů.
Požadované prerekvizitní znalosti a dovednosti:
Algoritmické myšlení.
Získané dovednosti, znalosti a kompetence:
Schopnost sestrojit algoritmus pro grafový problém a analyzovat jeho časovou a prostorovou složitost.
Osnova přednášek:
  1. Úvod do problematiky, složitost algoritmu, pojem a reprezentace grafu.
  2. Prohledávání grafu do šírky a do hloubky, dostupnost vrcholů.
  3. Topologické uspořádání vrcholů a hran, test acykličnosti grafu.
  4. Komponenty grafu, silně souvislé komponenty, příklady.
  5. Stromy, minimální kostry, Jarníkův a Borůvkův algoritmus.
  6. Růst minimální kostry, algoritmy Kruskala a Prima.
  7. Nejkratší cesty z jednoho vrcholu, Bellman-Fordův algoritmus, nejkratší cesta z jednoho vrcholu v orientovaných acyklických grafech.
  8. Dijkstrův algoritmus. Nejkratší cesty ze všech vrcholů.
  9. Nejkratší cesty a násobení matic, Floyd-Warshallův algorithmus.
  10. Toky a řezy v sítích, maximální tok, minimální řez, Ford-Fulkersonův algoritmus.
  11. Párování v bipartitních grafech, maximální párování.
  12. Eulerovské grafy a tahy, Hamiltonovské kružnice a cykly.
  13. Barvení grafů.
Osnova ostatní - projekty, práce:
  1. Řešení (a případně implementace) vybraných grafových problémů/úkolů a prezentace řešení (principy, složitost, důkazy, optimalizace).
Literatura referenční:
  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
  2. J. Demel, Grafy, SNTL Praha, 1988.
  3. J. Demel, Grafy a jejich aplikace, Academia, 2002. (Více o knize)
  4. R. Diestel, Graph Theory, Third Edition, Springer-Verlag, Heidelberg, 2000.
  5. J.A. McHugh, Algorithmic Graph Theory, Prentice-Hall, 1990.
  6. J.A. Bondy, U.S.R. Murty: Graph Theory, Graduate text in mathematics, Springer, 2008.
  7. J.L. Gross, J. Yellen: Graph Theory and Its Applications, Second Edition, Chapman & Hall/CRC, 2005.
  8. J.L. Gross, J. Yellen: Handbook of Graph Theory (Discrete Mathematics and Its Applications), CRC Press, 2003.
Literatura studijní:
  1. Text přednášek.
  2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 2002.
Kontrolovaná výuka:
Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů, závěrečná semestrální zkouška. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.
Průběžná kontrola studia:
Bodové hodnocení výsledků půlsemestrální zkoušky (max. 15 bodů) a vypracovaných projektů (max. 25 bodů).