Grafové algoritmy a základy teorie složitosti

Přednášející:

Josef Kolář (gar.)

Cvičící:

Josef Kolář (gar.), Jiří Chludil, Petr Matyáš

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:

Rozsah=prednasky+proseminare+cviceni:2p+2c

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út	místnost T9:302 Chludil J. 09:15–10:45 (přednášková par. 1 paralelka 101) Dejvice NBFIT učebnamístnost T9:302 Chludil J. 11:00–12:30 (přednášková par. 1 paralelka 102) Dejvice NBFIT učebnamístnost T9:302 Chludil J. 12:45–14:15 (přednášková par. 1 paralelka 103) Dejvice NBFIT učebnamístnost T9:346 Chludil J. 14:30–16:00 (přednášková par. 1 paralelka 104) Dejvice NBFIT učebna
St	místnost T9:302 Matyáš P. 09:15–10:45 (přednášková par. 1 paralelka 105) Dejvice NBFIT učebnamístnost T9:302 Matyáš P. 11:00–12:30 (přednášková par. 1 paralelka 106) Dejvice NBFIT učebnamístnost T9:302 Matyáš P. 12:45–14:15 (přednášková par. 1 paralelka 107) Dejvice NBFIT učebnamístnost T9:302 Matyáš P. 14:30–16:00 (přednášková par. 1 paralelka 108) Dejvice NBFIT učebna
Čt	místnost T9:155 Kolář J. 16:15–17:45 (přednášková par. 1) Dejvice Posluchárna
Pá

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

• Teoretická informatika - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět oboru)
• Počítačové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět oboru)
• Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět oboru)
• Informační systémy a management - verze pro ty, kteří se zapsali v roce 2009 a 2010 (VO)
• Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2009 a 2010 (VO)
• Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2011 a 2012 (VO)
• Informační systémy a management - verze pro ty, kteří se zapsali v roce 2011 a 2012 (VO)
• Počítačové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět oboru)
• Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět oboru)
• Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět oboru)