2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov
Leto 2022
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ň 14.-18.2.2022
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP
C: Príklady, kde 2-APX TSP dáva zlé výsledky, backtracking, Bellman-Held-Karp O(2^n.n^2) algoritmus, branch and bound algoritmus
Literatúra: CLRS3:35,35.2 alebo Par2:2.1-2.2,5.2
Slajdy:Poznámky a ďalšie materiály:
Administratíva, úvod (slajdy):PDF, 198 Kb ]
Problém obchodného cestujúceho (video):linka ]

Týždeň 21.2.-25.2.2022
P: Úvod do aproximačných algoritmov. Vrcholové pokrytie (2-aproximácia). Pokrytie množinami (O(log n)-aproximácia).
C: Dôkaz neaproximovateľnosti všeobecného TSP, redukcia všeob. TSP na metric TSP a prečo nezachováva aproximačný pomer, metrické Steinerové stromy 2-APX, 2-APX maximum matching
Literatúra: CLRS3:35.1,35.3 alebo Par2:4.2.2,4.2.5
Slajdy:Poznámky a ďalšie materiály:
Pokrývanie množinami (slajdy):PDF, 276 Kb ]
Pokrývanie množinami (video):linka ]
Cvičenie 2:PDF, 292 Kb ]

Týždeň 28.2.-4.3.2022
P: Polynomiálne aproximačné schémy. Problém batohu: 2-aproximačný algoritmus, pseudo-polynomiálne dynamické programovanie, FPTAS.
C: 2-APX minimum makespan scheduling, 2-APX maximum independent set of unit-height rectangles
Literatúra: V:8.1,8.2 alebo Par2:4.2.4
Slajdy:Poznámky a ďalšie materiály:
Problém batohu (slajdy):PDF, 92 Kb ]
Problém batohu (video):linka ]
Cvičenie 3:PDF, 276 Kb ]

Týždeň 7.-11.3.2022
P: Balenie do krabíc (bin packing).
C: 4-APX 2D HP problem, 3/2-APX metric TSP, 2-APX k-centers
Literatúra: V:9
Slajdy:Poznámky a ďalšie materiály:
Balenie do krabíc (slajdy):PDF, 141 Kb ]
Balenie do krabíc (video):linka ]
kcenters:PDF, 99 Kb ]
ILP - dámy:PDF, 114 Kb ]
ILP - VC a TSP:PDF, 168 Kb ]
ILP demo:zip, 20 Kb ]
Solver SCIP:linka ]

Týždeň 14.-18.3.2022
P: 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).
C: Lineárne programovanie, Triky pre písanie celočíselných lineárnych programov, ILP VC
Literatúra: V:14; V:16.3-16.4
Slajdy:Poznámky a ďalšie materiály:
Aproximačné algoritmy pomocou ILP (slajdy):PDF, 141 Kb ]
Aproximačné algoritmy pomocou ILP (video):linka ]
Triky pre písanie celočíselných lineárnych programov:PDF, 135 Kb ]

Týždeň 21.-25.3.2022
P: Zložitosť aproximačných algoritmov
C: DU1, ILP VC, ILP TSP
Literatúra: V:29.3,29.5
Slajdy:Poznámky a ďalšie materiály:
Zložitosť aproximačných algoritmov:PDF, 168 Kb ]
Zložitosť aproximačných algoritmov (video):linka ]

Týždeň 29.3.-2.4.2021
P: 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.
C: Základy pravdepodobnosti, Stredné hodnoty, linearita strednej hodnoty.
Literatúra: CLRS3:9
Slajdy:Poznámky a ďalšie materiály:
Problém výberu (slajdy):PDF, 155 Kb ]
Problém výberu (video):linka ]

Týždeň 5.-9.4.2021
P: Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie náhodných veľkých prvočísel.
C: Randomizované algoritmy, testovanie rovnosti súborov, Max-cut, Max-EkSAT
Literatúra: CLRS3:31.8 alebo MR:14.6
Slajdy:Poznámky a ďalšie materiály:
Testovanie prvočíselnosti (slajdy):PDF, 173 Kb ]
Testovanie prvočíselnosti (video):linka ]

Týždeň 25.-29.4.2022
P: 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.
C: midterm, Hashovanie a univerzálne rodiny hashovacích funkcií.
Literatúra: CLRS3:11 alebo MR:8.4-8.5; MR: 6.1
Slajdy:Poznámky a ďalšie materiály:
2-SAT a 3-SAT (slajdy):PDF, 190 Kb ]
2-SAT a 3-SAT (video):linka ]


Maintained by 2-AIN-205 personnel