Algoritmy a grafy 2
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:
- 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)