Zima 2023
Prednášky a poznámky
| 1-AIN-105: Efektívne algoritmy a dátové štruktúry Zima 2023 Prednášky a poznámky |
|
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ň 18.09.2023-22.09.2023 | |
|
P1: Úvod. Analýza triediacich algoritmov. Asymptotická analýza, časová zložitosť / najhorší prípad, elementárne operácie, notácie O, Omega, Theta P2: Prioritné fronty. Triedenie s prioritnými frontami. Halda. 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: |
|---|---|
|
Asymptotická analýza (prednáška): [ PDF, 154 Kb ] Haldy (prednáška): [ PDF, 84 Kb ] Analýza kódu (cvičenia): [ PDF, 310 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ň 25.09.2023-29.09.2023 | |
|
P1: Administratíva. Lineárna konštrukcia haldy. HeapSort. Pokročilé triedenia. Randomizovaný QuickSort. P2: 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, 121 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 ] |
| Týždeň 02.10.2023-06.10.2023 | |
|
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, 436 Kb ] |
Pokročilé triedenia (poznámky): [ PDF, 193 Kb ] |
| Týždeň 09.10.2023-13.10.2023 | |
|
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, 263 Kb ] |
| Týždeň 16.10.2023-20.10.2023 | |
|
P1: Scapegoat stromy (pokr.). Slovníky pre reťazce (trie, PATRICIA - komprimovaný trie). Vyhľadávanie v texte. Rabin-Karpov algoritmus. P2: Vyhľadávanie s pomocou deterministického konečného automatu. 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, 133 Kb ] |
Vyhľadávanie v texte (poznámky): [ PDF, 205 Kb ] |
| Týždeň 23.10.2023-27.10.2023 | |
|
P1: Sufixové stromy.
Greedy algoritmy. Problém výberu aktivít. Dokazovanie
správnosti greedy algoritmov. P2: Huffmanovo kódovanie. C: Dokazovanie správnosti greedy algoritmov (coin change problem, fractional knapsack, unit job scheduling, nákup zlata) 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 ] Greedy algoritmy (cvičenie): [ PDF, 124 Kb ] |
Výber aktivít, Huffman (video): [ linka ] Greedy algoritmy (poznámky): [ PDF, 208 Kb ] |
| Týždeň 30.10.2023-03.11.2023 | |
|
P1: Kompresia textu: Lempel-Ziv-Welch.
Dynamické programovanie. Rozmieňanie peňazí. Pamiatka zosnulých Literatúra: BB:8.2;CLRS3:15.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
LZW, mincovka (prednáška): [ PDF, 81 Kb ] |
|
| Týždeň 06.11.2023-10.11.2023 | |
|
P1: Problém batohu. P2: Najdlhšia spoločná podpostupnosť. Najkratšia triangulácia. C: Vzorové riešenia DÚ2. Príklady na dynamické programovanie Literatúra: BB:8.4;CLRS3:15.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Problém batohu (prednáška): [ PDF, 93 Kb ] Najdlhšia spoločná podpostupnosť, Najkratšia triangulácia: [ PDF, 111 Kb ] Dynamické programovanie (cvičenie): [ PDF, 126 Kb ] |
Dynamické programovanie (video): [ linka ] Dynamické programovanie (poznámky): [ PDF, 199 Kb ] Najkratšia triangulácia (video): [ linka ] |
| Týždeň 13.11.2023-17.11.2023 | |
|
P1: Rozdeľuj a panuj. Násobenie veľkých čísel.
Master theorem. P2: Dôkaz master theorem. Najbližší pár bodov. Deň boja za slobodu a demokraciu 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ň 20.11.2023-24.11.2023 | |
|
P1: Základné grafové algoritmy.
Grafová terminológia, reprezentácia grafov, BFS, DFS. P2: Hľadanie najkratších ciest: Floyd-Warshallow algoritmus, Dijkstrov algoritmus C: Vzorové riešenia DÚ3 a midtermu 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 ] Najkratšie cesty (prednáška): [ PDF, 59 Kb ] |
Dijkstrov algoritmus (video): [ linka ] |
| Týždeň 27.11.2023-01.12.2023 | |
|
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: Vzorové riešenia DÚ4. Rekurencie, rozdeľuj a panuj 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 ] Grafy (poznámky): [ PDF, 291 Kb ] |
| Týždeň 04.12.2023-08.12.2023 | |
|
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ň 11.12.2023-15.12.2023 | |
|
P1: Cookova veta (formulácia). NP-ťažké a NP-úplné problémy P2: 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 ] |