Leto 2026
Prednášky a poznámky
| 2-AIN-205: Algoritmické riešenie ťažkých problémov Leto 2026 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ň 16.02.2026-20.02.2026 | |
|
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 |
| Týždeň 23.02.2026-27.02.2026 | |
|
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 |
| Týždeň 02.03.2026-06.03.2026 | |
|
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 k-centers, metric Steiner tree, 1.5-APX TSP Literatúra: V:8.1,8.2; tutorials: V:5.2,3.1 |
| Týždeň 09.03.2026-13.03.2026 | |
|
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 |
| Týždeň 16.03.2026-20.03.2026 | |
|
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 |
| Týždeň 23.03.2026-27.03.2026 | |
|
P: Zložitosť aproximačných algoritmov C: Základy pravdepodobnosti, náhodná premenná, linearita strednej hodnoty Literatúra: V:29.3,29.5 |
| Týždeň 30.03.2026-03.04.2026 | |
|
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: Veľká noc, cvičenia odpadnú Literatúra: CLRS3:9; CLRS3:11 alebo MR:8.4-8.5 |
| Týždeň 06.04.2026-10.04.2026 | |
|
P: Veľká noc, prednáška odpadne C: randomizované algoritmy |
| Týždeň 13.04.2026-17.04.2026 | |
|
P: Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie náhodných veľkých prvočísel. C: hashovanie, fingerprinting / Rabin-Karpov algoritmus Literatúra: CLRS3:31.8 alebo MR:14.6 |
| Týždeň 20.04.2026-24.04.2026 | |
|
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ť, random walks, Markov chains Literatúra: MR: 6.1 |
| Týždeň 27.04.2026-01.05.2026 | |
|
P: Pravdepodobnostné dátové štruktúry - skip lists, treaps C: Literatúra: MR:8.2,8.3 |
| Týždeň 04.05.2026-08.05.2026 | |
|
P: Najlacnejšia kostra v lineárnom očakávanom čase C: Literatúra: MR:10.3 |
| Týždeň 11.05.2026-15.05.2026 | |
|
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. C: Maximum independent sets on trees and series-parallel graphs, treewidth, tree decomposition, treewidth of series-parallel graphs, treewidth of trees, tree decomposition of trees |
| Týždeň 18.05.2026-22.05.2026 | |
|
P: Zložitostné triedy pravdepodobnostných algoritmov. Zhrnutie semestra Literatúra: BB:12.6 |