Grafové algoritmy a základy teorie složitosti

Předmět BIK-GRA nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BI-AG2 (vztah je symetrický)

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Studenti získají základní přehled o používání grafových modelů v informatice, se zaměřením především na algoritmické otázky a řešení grafových problémů. Zahrnuta jsou rovněž další témata, která tento přehled doplňují o specifické aplikace nebo postupy (toky v sítích, heuristické hledání, aproximační algoritmy) nebo se týkají obecnější problematiky algoritmické řešitelnosti a složitosti úloh (Turingovy stroje, NP úplné problémy).

Požadavky:

Předpokládá se znalost základních abstraktních datových typů, jejich efektivní implementace a použitelnost při řešení grafových problémů na úrovni předmětu BI-EFA. Studenti by měli pasivně zvládat základní důkazové postupy známé z povinných matematických předmětů (důkaz úplnou indukcí, důkaz sporem, konstruktivní důkaz) a vedle návrhu nového či modifikace známého algoritmu by měli být schopni provést jeho analýzu složitosti.

Osnova přednášek:

1. Grafové modely, neorientované grafy, izomorfismus. Sousednost, souvislost, orientované grafy.

2. Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty.

3. Eulerovy grafy, dominující a nezávislé podmnožiny, barevnost, vzdálenost. Stromy, kostry, kružnice, minimální kostry.

4. Nejkratší cesty, algoritmy hledání nejkratších cest 1 -> n. Algoritmy hledání nejkratších cest n -> n, planarita.

5. Toky v sítích, určení maximálního toku v síti. Nejlevnější cirkulace, párování, řešení přiřazovací úlohy.

6. Stavový prostor úloh, prohledávání, heuristické hledání. Turingovy stroje.

7. Třídy složitosti, NP-úplné problémy. Aproximační algoritmy.

Osnova cvičení:

1. Indukce, rekurze, rekurence Druhy stromů a jejich reprezentace, procházení stromů. Vlastnosti grafů (izomorfismus, souvislost, komponenty, stupně uzlů). Silná souvislost, rozklad na silné komponenty, topologické uspořádání. Reprezentace a procházení grafu, použití. Určení Eulerova tahu, úloha čínského listonoše, zadání semestrální práce. Určování charakteristik (nezávislost, dominance, barevnost, cyklomatické číslo).

2. Stromy, kostry a minimální kostry. Nejkratší cesty. Nejkratší cesty, planarita, konzultace k semestrální úloze. Maximální tok v síti, cirkulace, párování. Algoritmy heuristického hledání. Turingovy stroje.

Cíle studia:

Grafové modely a odpovídající grafové algoritmy patří k základní informatické výbavě, která má řadu aplikací v infromatice i mimo ni. Cílem předmětu je rozvinout schopnosti rozpoznat, jaký grafový model odpovídá určité konkrétní úloze a jakým algoritmem je možné tuto úlohu řešit, a dále naučit určovat či odhadovat meze algoritmické složitosti a hranice praktické řešitelnosti jistých typů úloh.

Studijní materiály:

Kolář, J. ''Teoretická informatika''. Praha: Česká informatická společnost, 2000. ISBN 80-900853-8-5.

Demel, J. ''Grafy a jejich aplikace''. Praha: Academia, 2002. ISBN 80-200-0990-6.

Kolář, J. ''Theoretical Computer Science''. Praha: ČVUT, 1998. ISBN 80-01-01788-5.

Cormen, T. H., Leiserson, C. E., Rivest, R. L. ''Introduction to Algorithms''. The MIT Press, 2001. ISBN 0262032937.

Sedgewick, R. ''Algorithms in Java, Part 5: Graph Algorithms (3rd Edition)''. Addison-Wesley Professional, 2003. ISBN 0201361213.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-FIP/

https://courses.fit.cvut.cz/BI-GRA/

Opozdicům:

Dvojici předmětů EFA + GRA lze uznat, jestliže student úspěšně absolvuje dvojici předmětů AG1 + AG2. Student o to může požádat na studijním oddělení.

Student, kterému chybí předmět GRA si musí zapsat předmět AG2 a podrobit se rozdílové zkoušce.

Opakujícím studentům, kterým byl uznán předmět GRA, si musí zapsat předmět AG2 a požádat u uznání zápočtu.

Další informace:

https://courses.fit.cvut.cz/BI-GRA/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, kombi., 2015 - 2020 (VO)
• Bc. obor Bezpečnost a informační technologie, kombi., 2015 - 2019 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, kombi., 2015 - 2020 (volitelný předmět)
• Bc. obor Bezpečnost a informační technologie, kombinovaná forma studia, 2020 (volitelný předmět)