Zima 2018
Prednášky a poznámky
| 1-AIN-105: Efektívne algoritmy a zložitosť Zima 2018 Prednášky a poznámky |
|
Kontakt | Body | 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ň 27.-31.9.2018 | |
|
P: Úvod. Bentleyho problém. C: Motivačný príklad - Hľadanie kostry v grafe Literatúra: Ben1:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Bentleyho problém: [ PDF, 63 Kb ] |
|
| Týždeň 1.-5.10.2018 | |
|
P: Formalizácia výpočtového modelu. Výpočtová zložitosť. 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: |
|---|---|
|
Zložitosť, Greedy algoritmy: [ PDF, 64 Kb ] |
Úvod, zložitosť: [ PDF, 148 Kb ] |
| Týždeň 8.-12.10.2018 | |
|
P: Výber aktivít (dôkaz). Huffmanove kódy C: Rozmieňanie peňazí (greedy algoritmy, kedy fungujú). Problém batohu so zlomkami. Ďalšie príklady na greedy algoritmy. Literatúra: CLRS3:16.3 (odlišný prístup k výkladu) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Výber aktivít, Huffmanov strom: [ PDF, 32 Kb ] |
Greedy algoritmy: [ PDF, 180 Kb ] Paper: Optimal bounds for the change-making problem: [ PDF, 681 Kb ] |
| Týždeň 15.-19.10.2018 | |
|
P: Dynamické programovanie. Úvod (lodičky s utečencami). Problém batohu s celými číslami. C: Memoizácia. Ďalšie príklady na greedy algoritmy a dynamické programovanie. 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) |
| Týždeň 22.-26.10.2018 | |
|
P: Najkratšia triangulácia. C: Ďalšie príklady na dynamické programovanie |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Najkratšia triangulácia: [ PDF, 24 Kb ] |
Dynamické programovanie: [ PDF, 184 Kb ] |
| Týždeň 29.10.-2.11.2018 | |
| Štátne sviatky, prednášky a cvičenia odpadnú |
| Týždeň 5.-9.11.2019 | |
|
P: Rozdeľuj a panuj. Násobenie veľkých čísel. Metódy riešenia rekurencií / Master theorem. C: Vzorové riešenia DÚ 1. Substitučná metóda na riešenie rekurencií. 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: |
|---|---|
|
Master theorem: [ PDF, 70 Kb ] |
|
| Týždeň 12.-16.11.2018 | |
|
P:
Najbližší pár bodov. Grafové algoritmy. Najkratšie cesty (Dijkstrov algoritmus). C: Najkratšie cesty - Floyd-Warshallov algoritmus. Literatúra: CLRS3:24.3,23 alebo BB:6.4,6.3; CLRS3:22.1-2 alebo BB:9.3-9.5 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Master theorem, najbližší pár bodov: [ PDF, 72 Kb ] Najkratšie cesty, minimálna kostra: [ PDF, 39 Kb ] |
Rozdeľuj a panuj: [ PDF, 269 Kb ] |
| Týždeň 19.-23.11.2018 | |
|
P:
Dijkstrov algoritmus (pokračovanie).
Najlacnejšie kostry (Kruskalov a Primov algoritmus). C: Hľadanie artikulácií. |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Grafové algoritmy: [ PDF, 274 Kb ] |
|
| Týždeň 26.-30.11.2018 | |
|
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: Netypické formulácie grafových problémov (príklady). Literatúra: CLRS3:34 alebo BB:12.5 alebo Par:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Triedy P a NP, nedeterminizmus: [ PDF, 21 Kb ] |
|
| Týždeň 3.-7.12.2018 | |
|
P: Cookova veta. Dokazovanie NP-ťažkosti, 3-SAT->VC. C: Rozhodovacie vs. optimalizačné problémy. Programovanie s nedeterminizmom. |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Cookova veta: [ PDF, 69 Kb ] |
NP-ťažké problémy: [ PDF, 222 Kb ] |
| Týždeň 10.-14.12.2018 | |
|
P: Vypočítateľné a nevypočítateľné problémy. RAM model. Churchova-Turingova téza. Problém zastavenia. C: Polynomiálne redukcie / dokazovanie NP-ťažkosti (COIN-CHANGING, SUBSET-SAM, Hamiltonovská kružnica a ďalšie problémy). NP-ťažké problémy vs. problémy v P |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
RAM model, redukcie: [ PDF, 90 Kb ] |
|
| Týždeň 17.-21.12.2018 | |
|
P: Turingova reducibilita. Univerzálny RAM. Ďalšie nevypočítateľné problémy. Zhrnutie semestra. C: RAM modely, vypočítateľnosť |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Univerzálny RAM, zhrnutie semestra: [ PDF, 90 Kb ] |
Vypočítateľnosť: [ PDF, 187 Kb ] |