Algoritmy a grafy 2
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
BI-AG2 | Z,ZK | 5 | 2P+2C | česky |
- Vztahy:
- Předmět BI-AG2 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BI-GRA (vztah je symetrický)
- Předmět BI-AG2 nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BIK-GRA (vztah je symetrický)
- 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. 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.
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] 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:
-
Informace o předmětu a výukové materiály naleznete na 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ů:
-
- Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (VO, volitelný předmět)
- Bc. obor Bezpečnost a informační technologie, 2015-2020 (volitelný předmět)
- Bc. obor Teoretická informatika, 2015-2020 (povinný předmět oboru)
- Bc. obor Počítačové inženýrství, 2015-2020 (volitelný předmět)
- Bc. obor Informační systémy a management, 2015-2020 (volitelný předmět)
- Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (volitelný předmět)
- Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (volitelný předmět)
- Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (volitelný předmět)
- Bc. obor Znalostní inženýrství, 2018-2020 (volitelný předmět)
- Bc. program, pro fázi studia bez specializace, 2021 (volitelný předmět)
- Bc. program, pro fázi studia bez specializace, 2024 (volitelný předmět)