Algoritmy a grafy 2

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ů:

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2021 (VO)
• Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2021 (PS)
• Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2024 (VO)
• Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2024 (PS)