Zima 2020
Prednášky a poznámky
| 1-AIN-105: Efektívne algoritmy a zložitosť Zima 2020 Prednášky a poznámky |
|
Kontakt | Základné informácie | 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.
U prednášok uvádzame zoznam kapitol, ktoré najviac pokrývajú učivo. Prezentácia materiálu v rámci prednášok sa obvykle nezhoduje s prezentáciou v učebniciach. Uvedené kapitoly by mali hlavne slúžiť ako doplňujúci materiál pre samoštúdium.
| Týždeň 21.-25.9.2020 | |
|
P: Úvod. Bentleyho problém. C: Kruskalov algoritmus a union/find-set Literatúra: Ben1:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 65 Kb ] |
Poznámky: Úvod, zložitosť: [ PDF, 148 Kb ] |
| Týždeň 28.9.-2.10.2020 | |
|
P: Formalizácia výpočtového modelu (elementárna operácia), výpočtová zložitosť problému, základné asymptotiky. Greedy algoritmy. Problém výberu aktivít C: Porovnávanie a odhadovanie časovej zložitosti Literatúra: BB:2,3.1-3.4,4.1-4.4 alebo Par:1.1-1.4 alebo CLRS3:1-3 BB:6 (odlišné príklady) alebo Par:2.3 (odlišné príklady) alebo CLRS3:16.1-16.2 (odlišný prístup k výkladu) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 64 Kb ] |
Cvičenia: príklady kódu: [ Text, 2 Kb ] Asymptotiky: [ PDF, 56 Kb ] |
| Týždeň 5-9.10.2020 | |
|
P: Výber aktivít (dôkaz). Huffmanove kódy C: Dokazovanie správnosti greedy algoritmov - Change-making problem, Fractional knapsack problem Literatúra: CLRS3:16.3 (odlišný prístup k výkladu) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 66 Kb ] Videoprednáška: [ linka ] |
Poznámky: Greedy algoritmy: [ PDF, 82 Kb ] Whiteboard - coins: [ png, 31 Kb ] Whiteboard - knapsack: [ png, 33 Kb ] |
| Týždeň 12-16.10.2020 | |
|
P: Dynamické programovanie. Úvod (lodičky s utečencami). Problém batohu s celými číslami. C: coin changing problem, weighted activity selection problem Literatúra: BB:8.1-8.3 alebo Par:2.2 (odlišné príklady) alebo CLRS3:15.1-15.4 (odlišné príklady) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 57 Kb ] Videoprednáška: [ linka ] |
Cvičenie: dynamické programovanie: [ PDF, 159 Kb ] |
| Týždeň 19.-24.10.2020 | |
|
P: Najkratšia triangulácia. C: Grid path problem, Wine selling problem, Maximum size square submatrix with all 1s |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 54 Kb ] Videoprednáška: [ linka ] |
Poznámky: Dynamické programovanie: [ PDF, 184 Kb ] Cvičenie: Dynamické programovanie: [ PDF, 46 Kb ] |
| Týždeň 26.-30.10.2020 | |
|
P: Rozdeľuj a panuj. Násobenie veľkých čísel.
Metódy riešenia rekurencií / Master theorem. C: Riešenie rekurencií - stromová metóda, substitučná metóda a master theorem Literatúra: BB:4.7,7.1-7.4 alebo Par:2.1, CLRS3:4.4-4.6,33.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 79 Kb ] Videoprednáška: [ linka ] |
|
| Týždeň 2.-6.11.2020 | |
|
P: Master theorem (dôkaz). Najbližší pár bodov. C: Pokračovanie substitúcie a master theorem, ukážka riešenia du1 Literatúra: CLRS3:4.6; CLRS3:33.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 66 Kb ] Videoprednáška: [ linka ] |
Poznámky: Rozdeľuj a panuj: [ PDF, 269 Kb ] |
| Týždeň 9.-13.11.2020 | |
|
P: Grafové algoritmy. Najkratšie cesty (Dijkstrov algoritmus). C: Najkratšie cesty - Floyd-Warshallov algoritmus. Literatúra: CLRS3:22.1; CLRS3:24.3 alebo BB:6.4; CLRS3:25.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 60 Kb ] Videoprednáška: [ linka ] |
|
| Týždeň 16.-20.11.2020 | |
|
P: Minimálna kostra (Kruskalov algoritmus). Hľadanie artikulácií. C: Primov algoritmus - dôkaz, ukážka riešenia du2, aplikácie grafových algoritmov Literatúra: CLRS3:23; CLRS3:22.3,22.5 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 79 Kb ] Videoprednáška: [ linka ] |
Poznámky: Grafové algoritmy: [ PDF, 274 Kb ] |
| Týždeň 23.-27.11.2020 | |
|
P: NP-ťažké problémy. Problém obchodného cestujúceho. Rozhodovacie problémy. Trieda problémov P. Nedeterminizmus. Trieda problémov NP. C: ukážka riešenia du3.1, grafové aplikácie - cestovné poriadky, formulácia nedeterministického algoritmu TSP-D a jeho použitia na riešenie TSP Literatúra: CLRS3:34 alebo BB:12.5 alebo Par:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 79 Kb ] Videoprednáška: [ linka ] |
|
| Týždeň 30.11.-4.12.2020 | |
|
P: Cookova veta. Dokazovanie NP-ťažkosti, 3-SAT->VC. C: Subset-sum je NP-úplný- dôkaz (nedeterministický algoritmus + redukcia 3-SAT na Subset-sum) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 75 Kb ] Videoprednáška: [ linka ] |
Poznámky: NP-ťažké problémy: [ PDF, 222 Kb ] |
| Týždeň 7.-11.12.2020 | |
|
P: Vypočítateľné a nevypočítateľné problémy. RAM model. Churchova-Turingova téza. Problém zastavenia. Turingova reducibilita. C: Ukážky riešení du3.2, du3.3, du4, Coin-changing je NP-úplný - dôkaz |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 93 Kb ] Videoprednáška: [ linka ] |
|
| Týždeň 14.-18.12.2020 | |
|
P: Univerzálny RAM. Ďalšie nevypočítateľné problémy. Zhrnutie semestra. C: 2-SAT vs. 3-SAT, Post Correspondence Problem |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prezentácia: [ PDF, 90 Kb ] Videoprednáška: [ linka ] |
Vypočítateľnosť: [ PDF, 187 Kb ] |
