Leto 2017
Prednášky a poznámky
| 2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov Leto 2017 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ň 20.-24.2.2017 | |
|
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP. C: Opakovanie dynamického programovania (rozmieňanie mincí, najdlhšia spoločná podpostupnosť) Literatúra: CLRS3:35,35.2 alebo Par2:2.1-2.2,5.2; CLRS3:15,15.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Administratíva, úvod: [ PDF, 204 Kb ] |
Dynamické programovanie: [ PDF, 180 Kb ] |
| Týždeň 27.2.-3.3.2017 | |
|
P: Aproximačné algoritmy. k-aproximačné algoritmy (definícia). Aproximačné algoritmy pre vertex cover a set cover. C: dynamické programovanie pre TSP, 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ň 6.-10.3.2017 | |
|
P: Polynomiálne aproximačné schémy (PTAS). Problém batohu (pseudo-polynomiálne dynamické programovanie, 2-aproximačný algoritmus, PTAS) C: príklady jednoduchých aproximačných algoritmov 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ň 13.-17.3.2017 | |
|
P: PTAS pre bin packing C: Celočíselné lineárne programovania. 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ň 20.-24.3.2017 | |
|
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: Opakovanie pravdepodobnosti. Príklady kombinácie pravdepodobnostných a aproximačných algoritmov (očakávaný aproximačných faktor - MaxCut, MaxSAT) Literatúra: V:16.1 alebo CLRS3:35.4; V:14; V:16.3-16.4 |
| Týždeň 27.-31.3.2017 | |
|
P: Pravdepodobnostné algoritmy. Lineárny a očakávaný lineárny select. Las Vegas algoritmy, čas behu Las Vegas algoritmu. C: Základné techniky písania ILP Literatúra: CLRS3:7,9 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Select: [ PDF, 102 Kb ] |
|
| Týždeň 3.-7.4.2017 | |
|
P: Monte Carlo algoritmus pre testovanie prvočíselnosti. C: Efektívna reprezentácia množín - Hashovanie, Bloomove filtre Literatúra: CLRS3:31.8 alebo Par2:6.2,7.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Testovanie prvočíselnosti: [ PDF, 23 Kb ] |
|
| Týždeň 10.-14.4.2017 | |
|
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 Literatúra: MR:6.1; MR:7.1,7.2,7.4,7.6 alebo Par2:7.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Splniteľnosť formúl: [ PDF, 19 Kb ] |
Splniteľnosť formúl: [ PDF, 30 Kb ] |
| Týždeň 17.-21.4.2017 | |
|
Pon: Veľká noc C: Opakovanie pred midtermom. |
| Týždeň 24.-28.4.2017 | |
|
Midterm Str: Študentská vedecká konferencia |
| Týždeň 1.-5.5.2017 | |
|
Pon: Štátny sviatok Str: Pravdepodobnostné algoritmy pre najlacnejšiu kostru. Pia: Úvod do teórie zložitosti. Nedeterministické výpočty. Triedy P a NP. NP-ťažké a NP-úplné problémy. Redukcie. Príklad redukcie 3-SAT na Vertex Cover. Literatúra: MR:10.3; CLRS3:34 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Najlacnejšia kostra: [ PDF, 78 Kb ] |
NP-ťažkosť: [ PDF, 222 Kb ] |
| Týždeň 8.-12.5.2017 | |
|
Pon: Štátny sviatok Str: Príklady ďalších redukcií (rozmieňanie peňazí, subset sum) |
| Týždeň 15.-19.5.2017 | |
|
Pon: Zložitostné triedy aproximačných a pravdepodobnostných algoritmov. Redukcie - IS nemá PTAS, VC nemá PTAS. Str: Pravdepodobnostné dátové štruktúry (skip lists). Technika fingerprinting. Štv: Parametrická zložitosť. Parametrický algoritmus pre vrchlové pokrytie. Literatúra: MR:8.2; MR:7.1,7.2,7.4,7,6 alebo Par2:7.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Hierarchia zložitostných tried: [ PDF, 240 Kb ] Zhrnutie semestra: [ PDF, 466 Kb ] |
Fingerprinting: [ PDF, 42 Kb ] |
| Týždeň 22.-26.5.2017 | |
| Str: konzultačné hodiny pred skúškou |