1-AIN-105: Efektívne algoritmy a zložitosť
Zima 2015
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ň 21.-25.9.2015
P: Úvod. Bentleyho problém.
C: Jednoduché algoritmické problémy.
Literatúra: Ben1:7
Slajdy:Poznámky a ďalšie materiály:
Bentleyho problém:PDF, 542 Kb ]

Týždeň 28.9.-2.10.2015
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ň 5.-9.10.2015
P: Huffmanove kódy
C: Rozmieňanie peňazí (greedy algoritmy, kedy fungujú). Problém batohu so zlomkami.
Literatúra: CLRS3:16.3 (odlišný prístup k výkladu)
Slajdy:Poznámky a ďalšie materiály:
Greedy algoritmy:PDF, 180 Kb ]

Týždeň 12.-16.10.2015
P: Dynamické programovanie. Všeobecný algoritmus rozmieňania peňazí. Najdlhšia spoločná podpostupnosť.
C: Problém batohu s celými číslami (dynamické programovanie). 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)
Slajdy:Poznámky a ďalšie materiály:
Rozmieňanie peňazí, najdlhšia spoločná podpostupnosť:PDF, 75 Kb ]

Týždeň 19.-23.10.2015
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, 180 Kb ]

Týždeň 26.-30.10.2015
P: Rozdeľuj a panuj. Merge sort. Metódy riešenia rekurencií / Master theorem.
C: Použitie Master theorem. Násobenie veľkých čísel (rozdeľuj a panuj algoritmus)
Literatúra: BB:4.7,7.1-7.4 alebo Par:2.1
Slajdy:Poznámky a ďalšie materiály:
Rozdeľuj a panuj:PDF, 70 Kb ]

Týždeň 2.-6.11.2015
P: Master theorem (dôkaz). Najbližší pár bodov.
C: Opakovanie asymptotík. Otázky a odpovede pred midtermom.
Literatúra: CLRS3:4.4-4.6,33.4
Slajdy:Poznámky a ďalšie materiály:
Master theorem, najbližší pár bodov:PDF, 72 Kb ]
Rozdeľuj a panuj:PDF, 269 Kb ]

Týždeň 9.-13.11.2015
P: Grafové algoritmy. Najkratšie cesty (Dijkstrov algoritmus). Najlacnejšie kostry (Kruskalov algoritmus).
C: Reprezentácia grafov a vplyv na zložitosť. Dátová štruktúra union/find-set v Kruskalovom algoritmus. Prehľadávanie do šírky a do hĺbky (opakovanie)
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:
Najkratšie cesty, minimálna kostra:PDF, 39 Kb ]

Týždeň 16.-20.11.2015
P: Hľadanie artikulácií. Netypické formulácie grafových problémov (príklady).
C: Floyd-Warshallov algoritmus. Primov algoritmus.
Literatúra: CLRS3:22.5; CLRS3:25 alebo BB:8.5
Slajdy:Poznámky a ďalšie materiály:
Artikulácie, ďalšie problémy:PDF, 75 Kb ]
Grafové algoritmy:PDF, 274 Kb ]

Týždeň 23.-27.11.2015
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: Rozhodovacie vs. optimalizačné problémy. Programovanie s nedeterminizmom.
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, 94 Kb ]

Týždeň 30.11.-4.12.2015
P: Cookova veta. Dokazovanie NP-ťažkosti, 3-SAT->VC.
C: Polynomiálne redukcie / dokazovanie NP-ťažkosti (COIN-CHANGING, SUBSET-SAM, Hamiltonovská kružnica a ďalšie problémy)
Slajdy:Poznámky a ďalšie materiály:
Cookova veta:PDF, 101 Kb ]
NP-ťažké problémy:PDF, 222 Kb ]

Týždeň 7.-11.12.2015
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
Slajdy:Poznámky a ďalšie materiály:
RAM model, redukcie:PDF, 155 Kb ]

Týždeň 14.-18.12.2015
P: Turingova reducibilita. Univerzálny RAM. Ďalšie nevypočítateľné problémy. Zhrnutie semestra.
C: RAM modely, vypočítateľnosť, opakovanie
Slajdy:Poznámky a ďalšie materiály:
Univerzálny RAM, zhrnutie semestra:PDF, 123 Kb ]
Vypočítateľnosť:PDF, 187 Kb ]


Maintained by 1-AIN-105 personnel