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

Algoritmy a grafy 2

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-AG2 Z,ZK 5 2+2 česky
Předmět nesmí být zapsán současně s:
Grafové algoritmy a základy teorie složitosti (BI-GRA)
Přednášející:
Ondřej Suchý (gar.)
Cvičící:
Ondřej Suchý (gar.), Václav Blažej, Radovan Červený, Josef Malík, Štěpán Plachý, Tomáš Valla
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Předmět představuje základní algoritmy a koncepty teorie grafů v návaznosti na úvod probraný v povinném předmětu BI-AG1. Probírá také pokročilejší datové struktury a amortizovanou analýzu složitosti. Zahrnuje i velmi lehký úvod do aproximačních algoritmů.

Požadavky:

Předpokládají se znalosti teorie grafů, grafových algoritmů, datových struktur a amortizované analýzy v rozsahu BI-AG1. V některých přednáškách dále se využívají základní znalosti z předmětů BI-ZMA, BI-LIN nebo BI-ZDM.

Osnova přednášek:

1. Havlova věta, DFS strom, 2-souvislost, algoritmus hledání mostů

2. Hledání silně souvislých komponent, charakterizace 2-souvislých grafů.

3. Sítě, toky v sítích, Fordův-Fulkersonův algoritmus.

4. k-souvislost, Fordova-Fulkersonova věta, Mengerova věta.

5. Párování, hledání párování v bipartitních grafech, Hallova věta a její důsledky.

6. Rovinné grafy, nakreslení grafu, Eulerova formule a její důsledky, Kuratowského věta.

7. Duál nakreslení rovinného grafu, multigrafy, Barvení grafů, first-fit algoritmus, věta o pěti barvách, Mycielskiho konstrukce.

8. Hledání vzdáleností mezi všemi dvojicemi vrcholů, Floyd-Warshallův algoritmus, využití Dijkstrova algoritmu, Fibonacciho haldy.

9. (a,b)-stromy, B-stromy, univerzální hešování.

10. Eulerovské grafy, prostor eulerovských podgrafů grafu.

11. Hamiltonovské grafy, problém obchodní cestující, aproximační algoritmy.

12. Geometrické algoritmy, konvexní obálka, sweepline.

Osnova cvičení:

1. Opakování znalostí z BI-AG1

2. Havlova věta, 2-souvislost, DFS-strom

3. Hledání silně souvislých komponent, charakterizace bipartitních grafů

4. Sítě, toky v sítích, Ford-Fulkersonův algoritmus

5. k-souvislost, Mengerova věta, Ford-Fulkersonova věta

6. Párování, hledání párování v bipartitních grafech, Hallova věta a její důsledky.

7. Rovinné grafy, nakreslení grafu, Eulerova formule a její důsledky, Kuratowského věta.

8. Duál nakreslení rovinného grafu, multigrafy, barvení grafů, first-fit algoritmus, věta o pěti barvách.

9. Hledání vzdáleností mezi všemi dvojicemi vrcholů, Floyd-Warshallův algoritmus, využití Dijkstrova algoritmu, Fibonacciho haldy

10. Zápočtová písemka

11. B-stromy, univerzální hešování, Eulerovské grafy, prostor eulerovských podgrafů grafu

12. Hamiltonovské grafy, problém obchodní cestující, aproximační algoritmy

Cíle studia:

Cílem studia je seznámit se s nejdůležitějšími pojmy a vztahy teorie grafů, grafovými algoritmy a datovými strukturami, které nebyly probrány v kurzu BI-AG1. Dále je cílem pochopit složitější amortizované analýzy a získat základní představu o aproximačních a geometrických algoritmech.

Studijní materiály:

[1] M. Mareš, T. Valla: Průvodce labyrintem algoritmů, CZ.NIC, Praha, 2017. https://knihy.nic.cz/

[2] T. Valla, J. Matoušek: Kombinatoriky a grafy I., Skripta, KAM MFF UK, Praha, 2008.

[3] P. Kovář: Teorie grafů, učební text, 2016.

[4] J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, čtvrté vydání, Karolinum, 2010.

[5] J. Kolář: Teoretická Informatika, Česká informatická společnost, Praha, 2004.

[6] J. Demel: Grafy a jejich aplikace, vlastním vydáním, Praha, 2015.

[7] P. Hliněný: Základy Teorie Grafů pro (nejen) informatiky, skripta FI MU, Brno, 2010.

[8] Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Introduction to Algorithms, 3rd Edition, MIT Press, 2009.

[9] K. Mehlhorn, P. Sanders: Algorithms and Data Structures: The Basic Toolbox, Springer Berlin Heidelberg, 2008.

[10] D. B. West: Introduction to Graph Theory, Second edition, Prentice Hall, 2001.

[11] R. Diestel: Graph Theory, 5th edition, Springer-Verlag, Berlin, 2017.

Poznámka:

2+2

Další informace:
https://courses.fit.cvut.cz/BI-AG2/
Rozvrh na zimní semestr 2018/2019:
Rozvrh není připraven
Rozvrh na letní semestr 2018/2019:
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
místnost T9:343
Plachý Š.
11:00–12:30
(přednášková par. 1
paralelka 102)

Dejvice
NBFIT učebna
Út
místnost TH:A-1442
Červený R.
09:15–10:45
(přednášková par. 1
paralelka 103)

Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Malík J.
11:00–12:30
(přednášková par. 1
paralelka 104)

Thákurova 7 (FSv-budova A)
St
místnost TH:A-1242
Suchý O.
09:15–10:45
(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
Čt
místnost T9:155
Suchý O.
14:30–16:00
(přednášková par. 1)
Dejvice
Posluchárna

Předmět je součástí následujících studijních plánů:
Platnost dat k 19. 3. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet3458206.html