Leto 2016
Prednášky a poznámky
| 2-AIN-205: ARTP: Algoritmické riešenie ťažkých problémov Leto 2016 Prednášky a poznámky |
|
Kontakt | Body | 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ň 15.-19.2.2016 | |
|
P: štrajk učiteľov C: Dynamické programovanie (príklady: rozmieňanie mincí, najdlhšia spoločná podpostupnosť) Literatúra: CLRS3:15,15.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Dynamické programovanie: [ PDF, 180 Kb ] |
|
| Týždeň 22.-26.2.2016 | |
|
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP. C: Odhadovanie zložitosti algoritmov, dynamické programovanie pre TSP, neaproximovateľnosť všeobecného TSP 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, 203 Kb ] |
|
| Týždeň 29.2.-4.3.2016 | |
|
P: Aproximačné algoritmy. k-aproximačné algoritmy (definícia).
Aproximačné algoritmy pre vertex cover a set cover. C: Príklady jednoduchých aproximačných algoritmov. Literatúra: Par2:3.3-3.4; CLRS2: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ň 7.-11.3.2016 | |
|
P: Polynomiálne aproximačné schémy (PTAS). Príklad: problém batohu (pseudo-polynomiálne dynamické programovanie, PTAS) C: Celočíselné lineárne programovanie. Ilustrácia na TSP. Riešenie pomocou knižnice SCIP. 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 ] |
Solver SCIP: [ linka ] ILP demo: [ zip, 21 Kb ] |
| Týždeň 14.-18.3.2016 | |
|
P: PTAS pre bin packing C: Exhaustívne prehľadávanie pre špeciálny bin packing. Základné techniky písania ILP Literatúra: V:9 |
| Týždeň 21.-25.3.2016 | |
|
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: Veľká noc - rektorské alebo dekanské voľno Literatúra: V:16.1 alebo CLRS3:35.4; V:14; V:16.3-16.4 |
| Týždeň 28.3.-1.4.2016 | |
|
P: Pravdepodobnostné algoritmy. Lineárny a očakávaný lineárny select. Las Vegas algoritmy, čas behu Las Vegas algoritmu. 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: CLRS3:7,9 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Select: [ PDF, 102 Kb ] |
|
| Týždeň 4.-8.4.2016 | |
|
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ň 11.-15.4.2016 | |
|
P: Vzťah Las Vegas a Monte Carlo algoritmov. Markovova nerovnosť. Náhodné
pochôdzky. Riešenie 2-SAT pomocou pravdepodobnostného algoritmu. C: Technika fingerprinting 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 ] Fingerprinting: [ PDF, 42 Kb ] |
| Týždeň 18.-22.4.2016 | |
|
P: Študentská vedecká konferencia C: Príklady na náhodné pochôdzky, riešenie 3-SAT |
| Týždeň 25.-29.4.2016 | |
|
P: Najlacnejšia kostra C: Pravdepodobnostné dátové štruktúry (skip lists) Literatúra: MR:10.3; MR:8.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Najlacnejšia kostra: [ PDF, 78 Kb ] |
|
| Týždeň 2.-6.5.2016 | |
|
P: Ú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. C: Príklady ďalších redukcií (rozmieňanie peňazí, subset sum) Literatúra: BB:12.6 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
NP ťažkosť a redukcie: [ PDF, 222 Kb ] |
|
| Týždeň 9.-13.5.2016 | |
|
P: Zložitostné triedy aproximačných algoritmov. Redukcie - IS nemá PTAS, VC nemá PTAS. C: Hranice medzi P a NP-ťažkými problémami (2SAT vs. 3SAT, 2-coloring vs 3-coloring, Hamiltonovská kružnica vs. Eulerovská cesta a pod.) |
| Týždeň 16.-20.5.2016 | |
|
P: Zložitostné triedy pravdepodobnostných algoritmov. Opakovanie semestra C: Parametrická zložitosť (parametrický algoritmus pre vrchlové pokrytie) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Hierarchia zložitostných
tried: [ PDF, 240 Kb ] Prehľad metód: [ PDF, 168 Kb ] |
|