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

Algoritmy a grafy 2

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-AG2.21 Z,ZK 5 2P+2C česky
Garant předmětu:
Přednášející:
Cvičící:
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.21. 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:

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

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.

9. Fibonacciho haldy.

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

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

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

13. Geometrické algoritmy, konvexní obálka, zametací přímka.

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. Mareš M., Valla T. : Průvodce labyrintem algoritmů. CZ.NIC, 2017. ISBN 978-80-88168-22-5.

2. Diestel R. : Graph Theory (5th Edition). Springer, 2017. ISBN 978-3-662-53621-6.

3. West D. B. : Introduction to Graph Theory (2nd Edition). Prentice-Hall, 2001. ISBN 978-0130144003.

4. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. : Introduction to Algorithms (3rd Edition). MIT Press, 2016. ISBN 978-0262033848.

5. Matoušek J., Nešetřil J. : Kapitoly z diskrétní matematiky, čtvrté vydání,. Karolinum, 2010. ISBN 978-80-246-1740-4.

Poznámka:

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

Další informace:
https://courses.fit.cvut.cz/BI-AG2/
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 28. 3. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6704306.html