Zima 2024
Prednášky a poznámky
| 1-AIN-105: Efektívne algoritmy a dátové štruktúry Zima 2024 Prednášky a poznámky |
|
Kontakt | Info | Domáce úlohy | Písomky a skúšky | Prednášky a poznámky | Predchádzajúce semestre
|
Na tejto stránke nájdete orientačný rozvrh semestra. Tento rozvrh
bude aktualizovaný vždy po skončení príslušného týždňa prednášok,
takisto budú pribúdať študijné materiály.
| ||
| Literatúra: | ||
|---|---|---|
| ||
| Týždeň 23.09.2024-27.09.2024 | |
|
P1: Administratíva. P2: Úvod. Analýza triediacich algoritmov. Asymptotická analýza, časová zložitosť / najhorší prípad, elementárne operácie, notácie O, Omega, Theta C: Porovnávanie a odhadovanie časovej zložitosti Literatúra: CLSR3:1.1-1.2,2.2-2.3,3.1; CLRS3:6 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Admin: [ PDF, 197 Kb ] Asymptotická analýza (prednáška): [ PDF, 154 Kb ] Analýza kódu (cvičenia): [ PDF, 241 Kb ] |
Asymptotická analýza (poznámky): [ PDF, 183 Kb ] Asymptotic Cheat Sheet: [ PDF, 56 Kb ] Theoretical Computer Science Cheat Sheet: [ PDF, 164 Kb ] |
| Týždeň 30.09.2024-04.10.2024 | |
|
P1: Prioritné fronty. Triedenie s prioritnými frontami. Halda. Lineárna konštrukcia haldy. P2: HeapSort. Pokročilé triedenia. Randomizovaný QuickSort. Stredná hodnota. Očakávaná časová zložitosť. Analýza časovej zložitosti QuickSortu. C: Porovnavanie zložitosti pomocou limity, Príklady na haldu Literatúra: CLRS3:6.3-6.4; CLRS3:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Administratíva: [ PDF, 197 Kb ] HeapSort (prednáška): [ PDF, 92 Kb ] QuickSort (prednáška): [ PDF, 44 Kb ] Haldy (cvičenia): [ PDF, 1175 Kb ] |
Prioritné fronty (poznámky): [ PDF, 172 Kb ] Pokročilé triedenia (poznámky): [ PDF, 193 Kb ] |
| Týždeň 07.10.2024-11.10.2024 | |
|
P1: Dolný odhad časovej zložitosti triedenia pomocou porovnaní.
Lineárne triedenia (counting sort, radix sort). P2:Slovníky. Implementácie pomocou polí a zoznamov. Binárne vyhľadávanie. Hašovacie tabuľky: hašovanie s otvorenou adresáciou, klasické hašovacie funkcie, univerzálne hašovacie funkcie, hašovanie s uzavretou adresáciou. C: pravdepodobnosti, aplikácie triedenia Literatúra: CLRS3:8.1-8.3; CLRS3:11 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Lineárne triedenia (prednáška): [ PDF, 55 Kb ] Hašovanie (prednáška): [ PDF, 57 Kb ] Triedenie (cvičenia): [ PDF, 407 Kb ] |
Pokročilé triedenia (poznámky): [ PDF, 193 Kb ] |
| Týždeň 14.10.2024-18.10.2024 | |
|
P1: Hašovacie tabuľky s dynamickou veľkosťou. Amortizovaná analýza časovej zložitosti. Binárne vyhľadávacie stromy. AVL stromy (definície, výška) P2: AVL stromy (vyvažovanie). Scapegoat stromy. C: Príklady na hašovanie a binárne vyhľadávacie stromy Literatúra: CLRS3:11; CLRS3:17.4; CLRS3: 12,13.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Binárne vyhľadávacie stromy (prednáška): [ PDF, 48 Kb ] AVL stromy, Scapegoat stromy (prednáška): [ PDF, 81 Kb ] Hašovanie, binárne vyhľadávacie stromy (cvičenie): [ PDF, 223 Kb ] |
Slovníky (poznámky): [ PDF, 258 Kb ] |
| Týždeň 21.10.2024-25.10.2024 | |
|
P1: Slovníky pre reťazce (trie, PATRICIA - komprimovaný trie). Vyhľadávanie v texte. Rabin-Karpov algoritmus. P2: Knuth-Morris-Prattov algoritmus. C: Vzorové riešenia DÚ1. Literatúra: CLRS3:32 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vyhľadávanie v texte (prednáška): [ PDF, 247 Kb ] Vyhľadávanie v texte (cvičenie): [ PDF, 103 Kb ] |
Vyhľadávanie v texte (poznámky): [ PDF, 205 Kb ] |
| Týždeň 28.10.2024-01.11.2024 | |
|
Greedy algoritmy. Problém výberu aktivít. Dokazovanie
správnosti greedy algoritmov. P2: Huffmanovo kódovanie. Literatúra: CLRS3:16.1; CLRS3:16.2; CLRS3:16.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Výber aktivít (prednáška): [ PDF, 122 Kb ] Huffmanovo kódovanie (prednáška): [ PDF, 96 Kb ] |
Výber aktivít, Huffman (video): [ linka ] Greedy algoritmy (poznámky): [ PDF, 221 Kb ] |
| Týždeň 04.11.2024-08.11.2024 | |
|
P: Zrušené. Samoštúdium: Kompresia textu: Lempel-Ziv-Welch. C: Dokazovanie správnosti greedy algoritmov (coin change problem, fractional knapsack, unit job scheduling, nákup zlata) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Greedy algoritmy (cvičenie): [ PDF, 114 Kb ] |
|
| Týždeň 11.11.2024-15.11.2024 | |
|
P: Dynamické programovanie. Rozmienanie peňazí. Najdlhšia spoločná podpostupnosť. C: Príklady na dynamické programovanie |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Dynamické programovanie (cvičenie): [ PDF, 105 Kb ] |
Dynamické programovanie (poznámky): [ PDF, 199 Kb ] |