Leto 2023
Prednášky a poznámky
| 2-AIN-205: Algoritmické riešenie ťažkých problémov Leto 2023 Prednášky a poznámky |
|
Info | Domáce úlohy | 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ň 13.02.2023-17.02.2023 | |
|
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, 198 Kb ] Problém obchodného cestujúceho (video): [ linka ] |
Cvičenie 1: [ PDF, 404 Kb ] |
| Týždeň 20.02.2023-24.02.2023 | |
|
Video namiesto prednášky: Ú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, branch-and-bound algoritmus 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, 292 Kb ] |
| Týždeň 27.02.2023-03.03.2023 | |
|
Video namiesto prednášky: 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, 92 Kb ] Problém batohu (video): [ linka ] |
|
| Týždeň 06.03.2023-10.03.2023 | |
|
P: Balenie do krabíc (bin packing). C: 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ň 13.03.2023-17.03.2023 | |
|
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: |
|---|---|
|
Aproximačné algoritmy pomocou ILP (video): [ linka ] |
Triky pre písanie celočíselných lineárnych programov: [ PDF, 135 Kb ] |
| Týždeň 20.03.2023-24.03.2023 | |
|
P: Zložitosť aproximačných algoritmov 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. Literatúra: V:29.3,29.5; CLRS3:9 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Zložitosť aproximačných algoritmov (video): [ linka ] Problém výberu (video): [ linka ] |
|
| Týždeň 27.03.2023-31.03.2023 | |
|
C:Cvičenia neboli C:Základy pravdepodobnosti, náhodná premenná, linearita strednej hodnoty |
| Týždeň 03.04.2023-07.04.2023 | |
|
P: Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie náhodných veľkých prvočísel. C: riešenia DÚ1, randomizované algoritmy Literatúra: CLRS3:31.8 alebo MR:14.6 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Testovanie prvočíselnosti (slajdy): [ PDF, 23 Kb ] Testovanie prvočíselnosti (video): [ linka ] |
|
| Týždeň 10.04.2023-14.04.2023 | |
|
Veľká noc, prednášky a cvičenia odpadnú Náhradná videoprednáška: 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 |
|
| 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ň 17.04.2023-21.04.2023 | |
|
Náhradná videoprednáška: Pravdepodobnostné dátové štruktúry - skip lists, treaps C: hashovanie, rolling hash, Bloomov filter 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ň 24.04.2023-28.04.2023 | |
|
P: Najlacnejšia kostra v lineárnom očakávanom čase C: ukážka DÚ2, markovová nerovnosť, random walk, markov chain 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 ] |
|
| Týždeň 01.05.2023-05.05.2023 | |
|
pondelok výučba odpadne Náhradná videoprednáška: Zložitostné triedy pravdepodobnostných algoritmov. C: ukážka DÚ3, series-parallel graphs 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 ] |
|
| Týždeň 08.05.2023-12.05.2023 | |
|
pondelok výučba odpadne 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. Zhrnutie semestra |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
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 ] |
|