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 ] |
| Týždeň 18.11.2024-22.11.2024 | |
|
P: Problém batohu. Najkratšia triangulácia. Rozdeľuj a panuj. Násobenie veľkých čísel. Master theorem. C: Midterm riešenia Literatúra: BB:4.7,7.1-7.4; CLRS3:4.4-4.6; CLRS3:33.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Master theorem (prednáška): [ PDF, 166 Kb ] Najbližší pár bodov (prednáška): [ PDF, 123 Kb ] |
Násobenie čísel, Master theorem (video): [ linka ] Master theorem - dôkaz, Najbližší pár bodov (video): [ linka ] Rozdeľuj a panuj (poznámky): [ PDF, 287 Kb ] |
| Týždeň 25.11.2024-29.11.2024 | |
|
P1: Najbližší pár bodov.Základné grafové algoritmy.
Grafová terminológia, reprezentácia grafov, BFS, DFS. P2: Hľadanie najkratších ciest: Floyd-Warshallow algoritmus, Dijkstrov algoritmus C: Rekurencie Literatúra: CLRS3:22.1-22.3; CLRS3:25.2; CLRS3:24.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Úvod do grafov (prednáška): [ PDF, 245 Kb ] Rekurencie a rozdeľuj a panuj (cvičenie): [ PDF, 147 Kb ] |
Grafy (poznámky): [ PDF, 291 Kb ] Dijkstrov algoritmus (video): [ linka ] |
| Týždeň 02.12.2024-06.12.2024 | |
|
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 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Kruskalov algoritmus, UNION/FIND-SET (prednáška): [ PDF, 63 Kb ] Primov algoritmus, blackbox riešenia (prednáška): [ PDF, 56 Kb ] Rekurencie a rozdeľuj a panuj (cvičenie): [ PDF, 147 Kb ] |
Kruskalov algoritmus, prehľadávanie do hĺbky (video): [ linka ] |
| Týždeň 09.12.2024-13.12.2024 | |
|
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: grafové algoritmy Literatúra: CLRS3:23;CLRS3:34 alebo BB:12.5 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Nedeterministické výpočty: [ PDF, 305 Kb ] Grafové algoritmy (cvičenie): [ PDF, 131 Kb ] |
Triedy P a NP (video): [ linka ] NP ťažké problémy (poznámky): [ PDF, 239 Kb ] |
| Týždeň 16.12.2024-20.12.2024 | |
|
P1: Cookova veta (formulácia). NP-ťažké a NP-úplné problémy. Zhrnutie semestra C: grafové algoritmy, opakovanie |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Zhrnutie semestra: [ PDF, 235 Kb ] Grafové algoritmy, dynamické programovanie, NP-ťažké problémy: [ PDF, 84 Kb ] |
Cookova veta, dokazovanie NP ťažkosti (video): [ linka ] |