Algoritmy a grafy 1
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| BI-AG1.21 | Z,ZK | 5 | 2P+2C | česky |
- 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 2023/2024:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Rozvrh na letní semestr 2023/2024:
- 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)