Algoritmy a grafy 2

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)