1-AIN-105: Efektívne algoritmy a zložitosť
Zima 2019
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ň 23.-29.9.2019
P: Úvod. Bentleyho problém.
C: Rôzne jednoduché algoritmy
Literatúra: Ben1:7
Slajdy:Poznámky a ďalšie materiály:
Bentleyho problém: [ PDF, 63 Kb ]

Týždeň 30.9.-6.10.2019
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ň 7.-13.10.2019
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ň 14.-20.10.2019
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)

Maintained by 1-AIN-105 personnel