Leto 2018
Prednášky a poznámky
| 2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov Leto 2018 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ň 19.-23.2.2018 | |
|
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP C: Backtracking. O(2^n.n^2) algoritmus pre TSP. A* orezávanie. 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: [ PDF, 205 Kb ] |
A*: [ linka ] |
| Týždeň 26.2.-2.3.2018 | |
|
P: Úvod do aproximačných algoritmov. Vrcholové pokrytie (2-aproximácia). Pokrytie množinami (O(log n)-aproximácia). C: Opakovanie odhadovania zložitosti. Neaproximovateľnosť všeobecného TSP. Literatúra: CLRS3:35.1,35.3 alebo Par2:4.2.2,4.2.5 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vertex cover, Set cover: [ PDF, 276 Kb ] |
|
| Týždeň 5.-9.3.2018 | |
|
P: Polynomiálne aproximačné schémy. Problém batohu (FPTAS). C: Jednoduché aproximačné algoritmy (metrické Steinerove stromy, párenie, neprekrývajúce sa obdĺžniky s výškou 1) Literatúra: V:8.1,8.2 alebo Par2:4.2.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Problém batohu: [ PDF, 92 Kb ] |
|
| Týždeň 12.-16.3.2018 | |
|
P: Bin packing (PTAS). C: Detaily a zložitosť prehľadávanie možností pre bin packing. Celočíselné lineárne programovanie. Príklady: vrcholové pokrytie, TSP. Riešenie pomocou knižnice SCIP Literatúra: V:9 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Solver SCIP: [ linka ] ILP demo: [ zip, 21 Kb ] |
|
| Týždeň 19.-22.3.2018 | |
|
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 |
| Týždeň 26.-30.3.2018 | |
|
C: Opakovanie pravdepodobnosti (jednoduché príklady, stredná hodnota) Aproximačné algoritmy kombinované s náhodnými číslami (MaxCut, MaxSat), Veľká noc Literatúra: CLRS3:C; V:2.4; C:16.1 alebo CLRS3:35.4 |
| Týždeň 2.-6.4.2018 | |
|
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, fingerprinting Literatúra: CLRS3:7,9; MR:7.1,7.2,7.4,7.6 alebo Par2:7.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Problém výberu: [ PDF, 102 Kb ] |
|
| Týždeň 9.-13.4.2018 | |
|
P: Monte Carlo algoritmy. Rabin-Millerov algoritmus na testovanie prvočíselnosti. Generovanie veľkých prvočísel. C: Pravdepodobnostné dátové štruktúry (skip lists, treaps) Literatúra: CLRS3:31.8 alebo MR:14.6 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Testovanie prvočíselnosti: [ PDF, 23 Kb ] |
|
| Týždeň 16.-20.4.2018 | |
|
P: prednáška odpadne C: opakovanie pred midtermom / vzorové riešenie domácich úloh |
| Týždeň 23.-27.4.2018 | |
|
P: Vzťah Las Vegas a Monte Carlo algoritmov. Markovova nerovnosť. Náhodné
pochôdzky. Riešenie 2-SAT pomocou pravdepodobnostného algoritmu. C: Príklady na náhodné pochôdzky, riešenie 3-SAT, Bloom filtre Literatúra: MR:6.1 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Splniteľnosť formúl: [ PDF, 19 Kb ] |
Splniteľnosť formúl: [ PDF, 30 Kb ] |
| Týždeň 30.4.-2.5.2018 | |
|
P: Najlacnejšia kostra v lineárnom očakávanom čase C: Opakovanie teórie zložitosti (P, NP, NP-ťažké, NP-úplné, redukcie) Literatúra: MR:10.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Najlacnejšia kostra: [ PDF, 78 Kb ] |
|
| Týždeň 7.-11.5.2018 | |
|
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: FPT algoritmy pre nezávislú množinu, sériovo-paralelné grafy a stromová dekompozícia Literatúra: Par2:3.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vrcholové pokrytie: [ PDF, 16 Kb ] |
|
| Týždeň 14.-18.5.2018 | |
|
C: vzorové riešenia domácich úloh, midtermu
P: Zložitostné triedy pravdepodobnostných a aproximačných algoritmov Literatúra: BB:12.6 |