2-AIN-205, Leto 2020: Prednášky a poznámky

2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov
Leto 2020
Prednášky a poznámky

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.

[CLRS3] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (3rd ed.), MIT Press 2009, ISBN 978-02620338448
V knižnici signatúra I-INF-C-21
[Par2] Pardubská: Vybrané kapitoly z teoretickej informatiky (2) (pomocné text y k prednáške), 2012
[V] Vazirani: Approximation Algorithms, Springer 2001, ISBN 978-3540653677
V knižnici signatúra I-INF-V-13
[MR] Motwani, Raghavan: Randomized Algorithms, Cambridge University Press 2005, ISBN 978-0521474658
V knižnici signatúra I-INF-M-27
Nekompletné predbežné videá - len pre potrebu študentov predmetu

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 17.-21.2.2020
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP Literatúra: CLRS3:35,35.2 alebo Par2:2.1-2.2,5.2
Administratíva, úvod: [ PDF, 205 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 24.2.-28.2.2020
C: Backtracking. O(2^n.n^2) algoritmus pre TSP. Orezávanie za pomoci dolných odhadov. Príklady, kde algoritmus pre 2-APX TSP dáva zlé výsledky. P: Úvod do aproximačných algoritmov. Vrcholové pokrytie (2-aproximácia). Pokrytie množinami (O(log n)-aproximácia). Literatúra: CLRS3:35.1,35.3 alebo Par2:4.2.2,4.2.5
Vertex cover, Set cover: [ PDF, 276 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 2.-6.3.2020
C: Neaproximovateľnosť všeobecného TSP. Príklady aproximačných algoritmov (párenie). P: Polynomiálne aproximačné schémy. Problém batohu: 2-aproximačný algoritmus, pseudo-polynomiálne dynamické programovanie, FPTAS. Literatúra: V:8.1,8.2 alebo Par2:4.2.4
Problém batohu: [ PDF, 92 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 9.-13.3.2020
C (samoštúdium): Ďalšie príklady aproximačných algoritmov. P (samoštúdium): Balenie do krabíc (bin packing). Literatúra: V:9
Balenie do krabíc (slajdy): [ PDF, 141 Kb ] Balenie do krabíc (video): [ linka ]	Cvičenie - zadania: [ PDF, 52 Kb ] Cvičenie - návodné úlohy: [ PDF, 41 Kb ] Cvičenie - hinty: [ PDF, 46 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 16.-20.3.2020
C (samoštúdium): Celočíselné lineárne programovanie (ILP). P (samoštúdium): Aproximačné algoritmy pomocou ILP relaxácie. Váhované vrcholové pokrytie (2-aproximačný algoritmus). MAX-SAT (očakávaný 3/4-aproximačný algoritmus). Literatúra: V:14; V:16.3-16.4
Aproximačné algoritmy pomocou ILP (slajdy): [ PDF, 141 Kb ] Aproximačné algoritmy pomocou ILP (video): [ linka ]	Celočíselné lineárne programovanie: [ PDF, 114 Kb ] Solver SCIP: [ linka ] ILP demo: [ zip, 20 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 23.-27.3.2020
C (samoštúdium): Triky pre písanie celočíselných lineárnych programov P (samoštúdium): Zložitosť aproximačných algoritmov Literatúra: V:29.3,29.5
Zložitosť aproximačných algoritmov: [ PDF, 168 Kb ] Zložitosť aproximačných algoritmov (video): [ linka ]	Triky pre písanie celočíselných lineárnych programov: [ PDF, 135 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 30.3.-3.4.2020
C (samoštúdium): TSP challenge (viď úlohy) P (samoštúdium): Pravdepodobnostné algoritmy. Problém výberu / hľadania mediánu: Lineárny a očakávaný lineárny algoritmus. Las Vegas algoritmy, čas behu Las Vegas algoritmu. Literatúra: CLRS3:9
Problém výberu (slajdy): [ PDF, 155 Kb ] Problém výberu (video): [ linka ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 6.-10.4.2020
C: Stredné hodnoty, linearita strednej hodnoty. Problém MAX-CUT. P (samoštúdium): Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie náhodných veľkých prvočísel. Literatúra: CLRS3:31.8 alebo MR:14.6
Testovanie prvočíselnosti (slajdy): [ PDF, 173 Kb ] Testovanie prvočíselnosti (video): [ linka ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 13.-17.4.2020
C: Hashovanie a univerzálne rodiny hashovacích funkcií. P (samoštúdium): Vzťah Las Vegas a Monte Carlo algoritmov. Markovova nerovnosť. Náhodné pochôdzky. Riešenie 2-SAT a 3-SAT pomocou pravdepodobnostného algoritmu. Literatúra: CLRS3:11 alebo MR:8.4-8.5; MR: 6.1
2-SAT a 3-SAT (slajdy): [ PDF, 190 Kb ] 2-SAT a 3-SAT (video): [ linka ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 20.-24.4.2020
C: náhodné pochôdzky, Markovova nerovnosť P (samoštúdium): Pravdepodobnostné dátové štruktúry - skip lists, treaps Literatúra: MR:8.2,8.3
Pravdepodobnostné dátové štruktúry (slajdy): [ PDF, 216 Kb ] Pravdepodobnostné dátové štruktúry (video): [ linka ]	Poznámky z cvičení: [ HTML, 133 Kb ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 27.4.-1.5.2020
C: Metóda fingerprinting P: Najlacnejšia kostra v lineárnom očakávanom čase Literatúra: MR:10.3
Najlacnejšia kostra (slajdy): [ PDF, 162 Kb ] Najlacnejšia kostra (video): [ linka ]

Slajdy:	Poznámky a ďalšie materiály:
Týždeň 11.-15.5.2020
C: Vzorové riešenia domácich úloh 1-3 P: Zložitostné triedy pravdepodobnostných algoritmov Literatúra: BB:12.6
Zložitostné triedy pravdepodobnostných algoritmov (slajdy): [ PDF, 86 Kb ] Zložitostné triedy pravdepodobnostných algoritmov (video): [ linka ]

Týždeň 4.-8.5.2020
P: Parametrická zložitosť. Problémy riešiteľné so zafixovaným parametrom (Fixed Parameter Tractable Algorithms). Vrcholové pokrytie. Cesta s práve k vrcholmi.

Maintained by 2-AIN-205 personnel