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

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.21 Z,ZK 5 2P+2C česky
Přednášející:
Radek Hušek
Cvičící:
Radek Hušek, Michal Opler
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/
Rozvrh na zimní semestr 2022/2023:
Rozvrh není připraven
Rozvrh na letní semestr 2022/2023:
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:347
Opler M.
09:15–10:45
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
místnost T9:347
Opler M.
11:00–12:30
(přednášková par. 1
paralelka 102)

Dejvice
NBFIT učebna
St
Čt
místnost T9:343
Hušek R.
11:00–12:30
(přednášková par. 1
paralelka 103)

Dejvice
NBFIT učebna
místnost T9:155
Hušek R.
12:45–14:15
(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 6. 2. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6704306.html