Algoritmy a grafy 1

Garant předmětu:

Dušan Knop

Přednášející:

Dušan Knop, Michal Opler

Cvičící:

Suzan Catay, Michal Dvořák, Radek Hušek, Dušan Knop, Jitka Mertlová, Xuan Thang Nguyen, Michal Opler, Josef Erik Sedláček, Martin Slávik, José Gaspar Smutný, Ondřej Suchý, Ondřej Šofr, Tomáš Valla

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět pokrývá to nejzákladnější z efektivních algoritmů, datových struktur a teorie grafů, které by měl znát každý informatik.

Navazuje a částečně dále rozvíjí znalosti z předmětu BI-DML.21, ve kterém studenti získají znalosti a dovednosti z kombinatoriky nezbytné pro vyhodnocování časové a paměťové složitosti algoritmů. Dále předmět navazuje na BI-MA1.21, ve kterém ze zavádějí asymptotické odhady funkcí a zejména pak asymptotické značení.

Požadavky:

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost programovacího jazyka C++ (zhruba na úrovni vyučované v předmětech BI-PA1.21 a BI-PA2.21) a znalost základních pojmů z matematické analýzy a kombinatoriky (absolvování BI-DML.21 a BI-MA1.21 je doporučeno). Doporučujeme, aby student souběžně studoval BI-AAG.21 a BI-MA2.21.

Osnova přednášek:

1. Motivace a úvod do teorie grafů.

2. Základní definice a pojmy teorie grafů I.

3. Základní definice a pojmy teorie grafů II. Řadící algoritmy O(n^2).

4. Binární haldy. Nafukovací pole, amortizovaná složitost.

5. Binomiální haldy.

6. Operace a vlastnosti binárních vyhledávacích stromů, způsoby jejich vyvažování, podrobnější diskuze AVL stromů.

7. Randomizované algoritmy, základy pravděpodobnosti, hešování a strategie řešení kolizí.

8. Rekurzivní algoritmy a metoda Rozděl a panuj.

9. QuickSort. Dolní mez složitosti řazení v porovnávacím modelu. Speciální algoritmy řazení.

10. Dynamické programování.

11. Minimální kostra ohodnoceného grafu. Jarníkův a Kruskalův algoritmus a jejich implementace.

12. Algoritmy hledání nejkratších cest v ohodnoceném grafu.

Osnova cvičení:

1. Motivace a úvod do teorie grafů.

2. Základní definice a pojmy teorie grafů I.

3. Základní definice a pojmy teorie grafů II. Řadící algoritmy O(n^2).

4. Binární haldy. Nafukovací pole, amortizovaná složitost.

5. Binomiální haldy.

6. Vyhledávací stromy a jejich vyvažování.

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rozptylování (hešování) a vyhledávací tabulky.

9. Rekurzivní algoritmy a metoda Rozděl a panuj.

10. Semestrální písemka.

11. Dynamické programování.

12. Minimální kostry a nejkratší cesty v grafech.

Cíle studia:

Studenti se naučí techniky důkazů korektnosti jednotlivých základních algoritmů a techniky asymptotické matematiky pro určování jejich složitostí v nejlepším, nejhorším, či průměrném případě. Student rozumí prezentovaným algoritmům a datovým strukturám a je schopný je upravit a aplikovat pro příbuzné problémy.

Studijní materiály:

Česká literatura:

1. J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2010.

2. M. Mareš, T. Valla: Průvodce labyrintem algoritmů (2. vydání), CZ.NIC, Praha, 2022. https://knihy.nic.cz/

3. J. Demel: Grafy a jejich aplikace, vlastním nákladem, 2015. (dostupné v PDF z https://kix.fsv.cvut.cz/~demel/grafy/)

4. P. Hliněný: Základy teorie grafů pro (nejen) informatiky, skripta FI MUNI ke stažení z webu (https://is.muni.cz/do/rect/el/estud/fi/js10/grafy/Grafy-text10.pdf).

5. P. Kovář: Diskrétní matematika a úvod do teorie grafů - Řešené příklady k procvičeni, dostupné ke stažení (zadání https://homel.vsb.cz/~kov16/files/dim_priklady.pdf a řešení https://homel.vsb.cz/~kov16/files/dim_priklady_resene.pdf)

Anglicky psaná literatura

1. T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Fourth edition, MIT Press, 2022.

2. K. Mehlhorn, P. Sanders: Algorithms and Data Structures: The Basic Toolbox. Springer 2008.

Poznámka:

Další informace:

https://courses.fit.cvut.cz/BI-AG1

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Bc. specializace Informační bezpečnost, 2021 (povinný předmět programu)
• Bc. specializace Manažerská informatika, 2021 (povinný předmět programu)
• Bc. specializace Počítačová grafika, 2021 (povinný předmět programu)
• Bc. specializace Počítačové inženýrství, 2021 (povinný předmět programu)
• Bc. program, pro fázi studia bez specializace, 2021 (povinný předmět programu)
• Bc. specializace Webové inženýrství, 2021 (povinný předmět programu)
• Bc. specializace Umělá inteligence, 2021 (povinný předmět programu)
• Bc. specializace Teoretická informatika, 2021 (povinný předmět programu)
• Bc. specializace Softwarové inženýrství, 2021 (povinný předmět programu)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (povinný předmět programu)
• Bc. specializace Počítačové sítě a Internet, 2021 (povinný předmět programu)