1-AIN-105: Efektívne algoritmy a zložitosť
Zima 2018
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ň 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í.

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

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. Polynomiálne redukcie / dokazovanie NP-ťažkosti (COIN-CHANGING, SUBSET-SAM, Hamiltonovská kružnica a ďalšie problémy)

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: NP-ťažké problémy vs. problémy v P

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ť


Maintained by 1-AIN-105 personnel