Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Grafové algoritmy a základy teorie složitosti

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-GRA Z,ZK 5 2+2 česky
Přednášející:
Josef Kolář (gar.)
Cvičící:
Josef Kolář (gar.), Jiří Chludil
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.

2. Sousednost, souvislost, orientované grafy.

3. Silná souvislost, acyklické grafy, reprezentace grafů, procházení do šířky.

4. Procházení do hloubky, topologické uspořádání, silně souvislé komponenty.

5. Eulerovy grafy, dominující a nezávislé podmnožiny, barevnost, vzdálenost.

6. Stromy, kostry, kružnice, minimální kostry.

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

8. Algoritmy hledání nejkratších cest n -> n, planarita.

9. Toky v sítích, určení maximálního toku v síti.

10. Nejlevnější cirkulace, párování, řešení přiřazovací úlohy.

11. Stavový prostor úloh, prohledávání, heuristické hledání.

12. Turingovy stroje.

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

Osnova cvičení:

1. Indukce, rekurze, rekurence

2. Druhy stromů a jejich reprezentace, procházení stromů.

3. Vlastnosti grafů (izomorfismus, souvislost, komponenty, stupně uzlů).

4. Silná souvislost, rozklad na silné komponenty, topologické uspořádání.

5. Reprezentace a procházení grafu, použití.

6. Určení Eulerova tahu, úloha čínského listonoše, zadání semestrální práce.

7. Určování charakteristik (nezávislost, dominance, barevnost, cyklomatické číslo).

8. Stromy, kostry a minimální kostry.

9. Nejkratší cesty.

10. Nejkratší cesty, planarita, konzultace k semestrální úloze.

11. Maximální tok v síti, cirkulace, párování.

12. Algoritmy heuristického hledání.

13. 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:

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

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

Poznámka:

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:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 21. 3. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1122706.html