Zima 2022
Prednášky a poznámky
| 1-AIN-105: Efektívne algoritmy a dátové štruktúry Zima 2022 Prednášky a poznámky |
|
Info | Domáce úlohy | Prednášky a poznámky
|
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ň 19.09.2022-23.09.2022 | |
|
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: |
|---|---|
|
Úvod, asymptotická analýza, administratíva (prednáška): [ PDF, 63 Kb ] Haldy (prednáška): [ PDF, 23 Kb ] Analýza kódu (cvičenia): [ PDF, 149 Kb ] |
Asymptotická analýza (poznámky): [ PDF, 171 Kb ] Asymptotic Cheat Sheet: [ PDF, 56 Kb ] Theoretical Computer Science Cheat Sheet: [ PDF, 164 Kb ] |
| Týždeň 26.09.2022-30.09.2022 | |
|
P1: 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: |
|---|---|
|
HeapSort (prednáška): [ PDF, 48 Kb ] QuickSort (prednáška): [ PDF, 41 Kb ] Haldy (cvičenia): [ PDF, 1175 Kb ] |
Prioritné fronty (poznámky): [ PDF, 163 Kb ] |
| Týždeň 03.10.2022-07.10.2022 | |
|
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, 50 Kb ] Hašovanie (prednáška): [ PDF, 57 Kb ] Triedenie (cvičenia): [ PDF, 436 Kb ] |
Pokročilé triedenia (poznámky): [ PDF, 182 Kb ] |
| Týždeň 10.10.2022-14.10.2022 | |
|
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, 208 Kb ] |
Slovníky (poznámky): [ PDF, 251 Kb ] |
| Týždeň 17.10.2022-21.10.2022 | |
|
P1: Slovníky pre reťazce (trie, PATRICIA - komprimovaný trie). Vyhľadávanie v texte. Rabin-Karpov algoritmus. Vyhľadávanie s pomocou deterministického konečného automatu. P2: Knuth-Morris-Prattov algoritmus. Sufixové stromy. C: Vzorové riešenia DÚ1. Sufixové stromy. Literatúra: CLRS3:32 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vyhľadávanie v texte (prednáška): [ PDF, 208 Kb ] Vyhľadávanie v texte (cvičenie): [ PDF, 128 Kb ] |
Vyhľadávanie v texte (poznámky): [ PDF, 195 Kb ] |
| Týždeň 24.10.2022-28.10.2022 | |
|
P1: 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, 99 Kb ] Huffmanovo kódovanie (prednáška): [ PDF, 40 Kb ] Greedy algoritmy (cvičenie): [ PDF, 123 Kb ] |
Výber aktivít, Huffman (video): [ linka ] Greedy algoritmy (poznámky): [ PDF, 208 Kb ] |
| Týždeň 30.10.2022-04.11.2022 | |
|
P1: Kompresia textu: Lempel-Ziv-Welch.
Dynamické programovanie. Rozmieňanie peňazí. P2: Problém batohu. C: Opakovanie na midterm, vzorové riešenie DÚ2 Literatúra: BB:8.2;CLRS3:15.3;BB:8.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
LZW, mincovka (prednáška): [ PDF, 73 Kb ] Problém batohu (prednáška): [ PDF, 93 Kb ] Opakovanie na midterm (cvičenie): [ PDF, 207 Kb ] |
Dynamické programovanie (video): [ linka ] |
| Týždeň 06.11.2022-11.11.2022 | |
|
P1: Najdlhšia spoločná podpostupnosť. P2: Najkratšia triangulácia. C: Príklady na dynamické programovanie Literatúra: CLRS3:15.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Najdlhšia spoločná podpostupnosť, Najkratšia triangulácia: [ PDF, 111 Kb ] Dynamické programovanie (cvičenie): [ PDF, 110 Kb ] |
Najkratšia triangulácia (video): [ linka ] Dynamické programovanie (poznámky): [ PDF, 189 Kb ] |
| Týždeň 13.11.2022-18.11.2022 | |
|
P1: Rozdeľuj a panuj. Násobenie veľkých čísel.
Master theorem. P2: Dôkaz master theorem. Najbližší pár bodov. C: cvičenia odpadli Literatúra: BB:4.7,7.1-7.4; CLRS3:4.4-4.6,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, 275 Kb ] |
| Týždeň 20.11.2022-25.11.2022 | |
|
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.2022-02.12.2022 | |
|
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: 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, 281 Kb ] |
| Týždeň 04.12.2022-09.12.2022 | |
|
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álny algoritmy na ich riešenie. P2: Definícia NP-ťažkých a NP-úplných problémov. Polynomiálne redukcie. Cookova veta (formulácia). Redukcia z HAM na TSP-D. Redukcia z 3-SAT na VC. C: grafové algoritmy Literatúra: 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, 164 Kb ] |
Triedy P a NP (video): [ linka ] Cookova veta, dokazovanie NP ťažkosti (video): [ linka ] NP ťažké problémy (poznámky): [ PDF, 229 Kb ] |
| Týždeň 11.12.2022-16.12.2022 | |
|
P1: Zhrnutie semestra C: vzorové riešenia DÚ4, grafové algoritmy, opakovanie |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Zhrnutie semestra: [ PDF, 219 Kb ] Grafové algoritmy (cvičenie): [ PDF, 109 Kb ] Opakovanie (cvičenie): [ PDF, 82 Kb ] |
|