2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov
Leto 2021
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ň 15.-19.2.2021
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, 205 Kb ]
Problém obchodného cestujúceho (video): [ linka ]
 Cvičenie 1: [ PDF, 404 Kb ]

Týždeň 22.2.-26.2.2021
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
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ň 1.-5.3.2021
P: Polynomiálne aproximačné schémy. Problém batohu: 2-aproximačný algoritmus, pseudo-polynomiálne dynamické programovanie, FPTAS.
C: 2-APX maximum matching, 2-APX maximum independent set of unit-height rectangles, 2-APX minimum makespan scheduling
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ň 8.-12.3.2021
P: Balenie do krabíc (bin packing).
C: 2-APX k-centers problem, Celočíselné lineárne programovanie (ILP) - dámy, vrcholové pokrytie, obchodný cestujúci.
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ň 15.-19.3.2021
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: Triky pre písanie celočíselných lineárnych programov
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ň 22.-26.3.2021
P: Zložitosť aproximačných algoritmov
C: Stredné hodnoty, linearita strednej hodnoty. Problém MAX-CUT.
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: Hashovanie a univerzálne rodiny hashovacích funkcií, testovanie rovnosti reťazcov.
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: Ukážka DU1, Rabin-Karp (rolling hash) algorithmus, Bloomov filter
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): pozri neskôr

Týždeň 12.-16.4.2021
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: Markovova nerovnosť, náhodné prechádzky, Markovové reťazce, S->T connectivity problém s O(log n) pamäťou
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 ]

Týždeň 19.-23.4.2021
P: Pravdepodobnostné dátové štruktúry - skip lists, treaps
C: Študentská vedecká konferencia
Literatúra: MR:8.2,8.3
Slajdy:Poznámky a ďalšie materiály:
Pravdepodobnostné dátové štruktúry (slajdy): [ PDF, 216 Kb ]
Pravdepodobnostné dátové štruktúry (video): [ linka ]

Týždeň 26.-30.4.2021
P: Najlacnejšia kostra v lineárnom očakávanom čase
C: Ukážka DU2, NP-ťažkosť a redukcie
Literatúra: MR:10.3
Slajdy:Poznámky a ďalšie materiály:
Najlacnejšia kostra (slajdy): [ PDF, 162 Kb ]
Najlacnejšia kostra (video): [ linka ]
 Cvičenie 10: [ PDF, 222 Kb ]

Týždeň 3.-7.5.2021
P: Zložitostné triedy pravdepodobnostných algoritmov. Parametrická zložitosť. Problémy riešiteľné so zafixovaným parametrom (Fixed Parameter Tractable Algorithms). Vrcholové pokrytie. Cesta s práve k vrcholmi.
Literatúra: BB:12.6, Par2:3.2
Slajdy:Poznámky a ďalšie materiály:
Zložitostné triedy pravdepodobnostných algoritmov (slajdy): [ PDF, 86 Kb ]
Zložitostné triedy pravdepodobnostných algoritmov (video): [ linka ]
Problémy riešiteľné so zafixovateľným parametrom (slajdy): [ PDF, 110 Kb ]
Problémy riešiteľné so zafixovateľným parametrom (video): [ linka ]

Týždeň 10.-14.5.2021
P: Zhrnutie semestra
Slajdy:Poznámky a ďalšie materiály:
Zhrnutie semestra (slajdy): [ PDF, 179 Kb ]
Zhrnutie semestra (video): [ linka ]

Maintained by 2-AIN-205 personnel