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


Info | 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
 

Literatúra:

 
Týždeň 19.02.2024-23.02.2024
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
Literatúra: CLRS3:35,35.2
Slajdy:Poznámky a ďalšie materiály:
Administratíva, úvod (slajdy):PDF, 211 Kb ]
Problém obchodného cestujúceho (video):linka ]

Týždeň 26.02.2024-01.03.2024
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
Literatúra: CLRS3:35.1,35.3
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, 146 Kb ]

Týždeň 04.03.2024-08.03.2024
P: Polynomiálne aproximačné schémy. Problém batohu: 2-aproximačný algoritmus, pseudo-polynomiálne dynamické programovanie, FPTAS.
C: 3-APX bottleneck TSP, 2-APX single-machine scheduling
Literatúra: V:8.1,8.2
Slajdy:Poznámky a ďalšie materiály:
Problém batohu (slajdy):PDF, 95 Kb ]
Problém batohu (video):linka ]
K-center problem V:5.2, Metric Steiner tree V:3.1: pozri neskôr
Max-weight matching:linka ]
3/2 APX for TSP:linka ]

Týždeň 11.03.2024-15.03.2024
P: Balenie do krabíc (bin packing).
C: Bin packing - detaily brute force časti algoritmu. 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 (video):linka ]
ILP - dámy:PDF, 114 Kb ]
ILP - VC a TSP:PDF, 168 Kb ]
ILP demo:zip, 20 Kb ]
Solver SCIP:linka ]

Týždeň 18.03.2024-22.03.2024
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
Literatúra: V:14; V:16.3-16.4
Slajdy:Poznámky a ďalšie materiály:
LP vs. ILP (slajdy):PDF, 87 Kb ]
Aproximačné algoritmy pomocou ILP (video):linka ]

Týždeň 25.03.2024-29.03.2024
P: Zložitosť aproximačných algoritmov
Veľká noc - cvičenia odpadli
Literatúra: V:29.3,29.5

Týždeň 01.04.2024-05.04.2024
Veľká noc - prednáška odpadla
C:Základy pravdepodobnosti, náhodná premenná, linearita strednej hodnoty
Slajdy:Poznámky a ďalšie materiály:
Základy pravdepodobnosti + stredná hodnota:linka ]
Diskrétna náhodná premenná (kap. 4):linka ]

Týždeň 08.04.2024-12.04.2024
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: vzorové riešenia DÚ1, hashovanie, fingerprinting / Rabin-Karpov algoritmus
Literatúra: CLRS3:9; CLRS3:11 alebo MR:8.4-8.5
Slajdy:Poznámky a ďalšie materiály:
Problém výberu (slajdy):PDF, 102 Kb ]
Problém výberu (video):linka ]
Hash tables:linka ]
Hashing + Karp-Rabin:linka ]

Týždeň 15.04.2024-19.04.2024
Videoprednáška (namiesto prednášky): Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie náhodných veľkých prvočísel.
Študentská vedecká konferencia - cvičenia odpadnú
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ň 22.04.2024-26.04.2024
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: vzorové riešenia DÚ2, Markovova nerovnosť, random walks, markov chains
Literatúra: MR: 6.1
Slajdy:Poznámky a ďalšie materiály:
2-SAT a 3-SAT (slajdy):PDF, 19 Kb ]
2-SAT a 3-SAT (video):linka ]
Random Walk + 3-SAT analysis:PDF, 113 Kb ]

Týždeň 29.04.2024-03.05.2024
P: Pravdepodobnostné dátové štruktúry - skip lists, treaps
C: Markovova nerovnosť, random walks, markov chains
Literatúra: MR:8.2,8.3
Slajdy:Poznámky a ďalšie materiály:
Pravdepodobnostné dátové štruktúry (slajdy):PDF, 224 Kb ]
Pravdepodobnostné dátové štruktúry (video):linka ]
Markovova nerovnost:linka ]

Týždeň 06.05.2024-10.05.2024
P: Najlacnejšia kostra v lineárnom očakávanom čase
C: vzorové riešenia DÚ3, series-parallel graphs
Literatúra: MR:10.3
Slajdy:Poznámky a ďalšie materiály:
Najlacnejšia kostra (slajdy):PDF, 121 Kb ]
Najlacnejšia kostra (video):linka ]

Týždeň 13.05.2024-17.05.2024
pondelok výučba odpadne
Náhradná videoprednáška: Zložitostné triedy pravdepodobnostných algoritmov.
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.
Náhradná videoprednáška: Zhrnutie semestra
Literatúra: BB:12.6
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 ]
Zhrnutie semestra (slajdy):PDF, 179 Kb ]
Zhrnutie semestra (video):linka ]


Maintained by 2-AIN-205 personnel