Zima 2026
Prednášky a poznámky
| 1-AIN-105: Efektívne algoritmy a dátové štruktúry Zima 2026 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: | ||
|---|---|---|
| ||
| Cheat sheets | ||
| Týždeň 21.09.2026-25.09.2026 | |
|
P1: Administratíva. Úvod do zložitosti. Analýza triediacich algoritmov. Asymptotická analýza, časová zložitosť / najhorší prípad, elementárne operácie P2: notácie O, Omega, Theta. Prioritné fronty. Pojem abstraktný dátový typ. Triedenie s prioritnými frontami. Halda. C: Určovanie časovej zložitosti kódov, porovnávanie funkcii, netriviálne operácie 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, 217 Kb ] Asymptotická analýza (prednáška): [ PDF, 166 Kb ] Prioritné fronty (prednáška): [ PDF, 84 Kb ] Výpočtová zložitosť (cvičenia): [ PDF, 70 Kb ] |
Asymptotická analýza (poznámky): [ PDF, 183 Kb ] |
| Týždeň 28.09.2026-02.10.2026 | |
|
P1: Halda a operácie s haldou. Lineárna konštrukcia haldy. HeapSort. P2: Pokročilé triedenia. Randomizovaný QuickSort. Stredná hodnota. Očakávaná časová zložitosť. Analýza časovej zložitosti QuickSortu. C: Princíp fungovania haldy, modifikácia haldy, abstraktný dátový typ prioritná fronta Literatúra: MV:4.1,4.2; MV:10.7,11.1,11.2; CLRS3:6.3-6.4; CLRS3:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
HeapSort (prednáška): [ PDF, 291 Kb ] QuickSort (prednáška): [ PDF, 62 Kb ] Haldy (cvičenia): [ PDF, 538 Kb ] |
Prioritné fronty (poznámky): [ PDF, 172 Kb ] |
| Týždeň 05.10.2026-09.10.2026 | |
|
P1: Dolný odhad časovej zložitosti triedenia pomocou porovnaní. Lineárne triedenia (counting sort, radix sort).
Slovníky. Implementácie pomocou polí a zoznamov.
Hašovacie tabuľky. Kolízie.
P2: Reťazenie. Klasické hašovacie funkcie. Univerzálne hašovacie funkcie. Otvorená adresácia. Double hashing. Hašovacie tabuľky s dynamickou veľkosťou. C: pravdepodobnosti, aplikácie triedenia Literatúra: MV:3.3; MV:3.4; MV:11.3-11.5; CLRS3:8.1-8.3; CLRS3:11 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Lineárne triedenia (prednáška): [ PDF, 98 Kb ] Hašovanie (prednáška): [ PDF, 60 Kb ] Triedenie (cvičenia): [ PDF, 191 Kb ] |
Pokročilé triedenia (poznámky): [ PDF, 193 Kb ] |
| Týždeň 12.10.2026-16.10.2026 | |
|
P1: Amortizovaná zložitosť.
Binárne vyhľadávacie stromy. AVL stromy (definície, výška) P2: AVL vyvažovanie. Scapegoat stromy. C: Príklady na hašovanie a binárne vyhľadávacie stromy Literatúra: MV:9.1 (Amortizacia); MV:8.1,8.2 (BVS+AVL); MV:9.4 (Scapegoat); 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 ] Scapegoat stromy (prednáška): [ PDF, 154 Kb ] Hašovanie, binárne vyhľadávacie stromy (cvičenie): [ PDF, 42 Kb ] |
Slovníky (poznámky): [ PDF, 258 Kb ] |
| Týždeň 19.10.2026-23.10.2026 | |
|
P1:
Slovníky pre reťazce (trie, PATRICIA - komprimovaný trie).
Vyhľadávanie v texte.
Rabin-Karpov algoritmus.
Vyhľadávanie pomocou konečných automatov. P2: Knuth-Morris-Prattov algoritmus. Sufixové stromy C: Vzorové riešenia DÚ1. Vyhľadávanie v texte. Literatúra: CLRS3:32 |
| Týždeň 26.10.2026-30.10.2026 | |
|
P1: Greedy algoritmy. Problém výberu aktivít. Dokazovanie
správnosti greedy algoritmov. P2: Huffmanovo kódovanie. C: odpadnú. Literatúra: BB:6; CLRS3:16.1; CLRS3:16.2; CLRS3:16.3 |
| Týždeň 02.11.2026-06.11.2026 | |
|
P1: Dynamické programovanie. Rozmienanie peňazí. Problém batohu. P2: Najdlhšia spoločná podpostupnosť. Najkratšia triangulácia. C: Greedy algoritmy. Literatúra: BB:8.2,8.4;CLRS:15.3,15.4 |
| Týždeň 09.11.2026-13.11.2026 | |
|
P1: Rozdeľuj a panuj. Násobenie veľkých čísel.
Master theorem. P2: Najbližší pár bodov. C: Príklady na dynamické programovanie. Vzorové riešenia DÚ2. Literatúra: BB:4.7,7.1-7.4; CLRS3:4.4-4.6; CLRS3:33.4 |
| Týždeň 16.11.2026-20.11.2026 | |
|
P1: Utorok 17.11 bez prenášky (Medzinárodný deň študentstva) P2: Základné grafové algoritmy. Grafová terminológia, reprezentácia grafov, BFS, DFS. C: Memoizácia. Príprava na midterm. Literatúra: CLRS3:22.1-22.3 |
| Týždeň 23.11.2026-27.11.2026 | |
|
P1: Hľadanie najkratších ciest: Floyd-Warshallow algoritmus, Dijkstrov algoritmus P2: Streda bez prenášky (Dekanské voľno: užite si MatFyz Connections) C: Rozdeľuj a panuj. Rekurencie. Vzorové riešenia DÚ3. Literatúra: CLRS3:25.2; CLRS3:24.3 |
| Týždeň 30.11.2026-04.12.2026 | |
|
P1: Najlacnejšie kostry: Kruskalov algoritmus, ADT disjunktné množiny / UNION-FINDSET dátová štruktúra P2: Primov algoritmus, grafové algoritmy ako black box riešenia C: Grafové algoritmy. Literatúra: CLRS3:23;CLRS3:21 |
| Týždeň 07.12.2026-11.12.2026 | |
|
P1: NP-ťažké a NP-úplné problémy. Problém obchodného cestujúceho.
Rozhodovacie vs. optimalizačné problémy. Nedeterministické výpočty.
Trieda P a trieda NP. Problémy SAT, 3-SAT, VC, CLIQUE, HAM a nedeterministické
polynomiálne algoritmy na ich riešenie. P2: Polynomiálne redukcie. Ukážky (HAM na TSP, 3-SAT na VC). C: Najlacnejšie kostry. Literatúra: CLRS3:23;CLRS3:34 alebo BB:12.5 |
| Týždeň 14.12.2026-18.12.2026 | |
|
P1: Cookova veta (formulácia). NP-ťažké a NP-úplné problémy. Zhrnutie semestra C: Nedeterminizmus, rozhodovacie problémy, triedy P a NP. Vzorové riešenia DÚ4. |