2-AIN-205: Vybrané kapitoly z teoretickej informatiky (2)
Leto 2015
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ň 16.-20.2.2015
P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP.
C: Backtracking, A* prehľadávanie, všeobecný TSP nie je k-aproximovateľný pre žiadnu konštantu k
Literatúra: CLRS2:34.1-34.2,35.2 alebo Par2:2.1-2.2,5.2
Slajdy:Poznámky a ďalšie materiály:
Administratíva, úvod:PDF, 170 Kb ]

Týždeň 24.-28.2.2014
P: Aproximačné algoritmy. k-aproximačné algoritmy. Aproximačné algoritmy pre vertex cover a set cover.
C: Príklady k-aproximačných algoritmov (výber z problémov: metrický Steinerov strom, nezávislá množina jednotkových štvorcov, dominujúce jednotkové kružnice, najkratší superstring)
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 ]
Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI:PDF, 578 Kb ]
NC-Approximation Schemes fo NP- and PSPACE-Hard Problems for Geometric Graphs:PDF, 303 Kb ]

Týždeň 2.-6.3.2015
P: Polynomiálne aproximačné schémy (PTAS). PTAS pre problém batohu.
C: Opakovanie pravdepodobnosti, stredné hodnoty. Algoritmy s očakávanou k-aproximáciou. Pravedpodobnostná metóda.
Literatúra: V:3.1.1,7; 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ň 9.-13.3.2015
P: PTAS pre bin packing.
C: Celočíselné lineárne programovanie (ILP). Riešenie TSP pomocou ILP. Používanie ILP solvera (SCIP).
Literatúra: CLRS2:C; V:2.4; V:16.1 alebo CLRS2:35.4; V:9
Slajdy:Poznámky a ďalšie materiály:
Solver SCIP:linka ]
ILP demo:zip, 21 Kb ]

Týždeň 16.-20.3.2015
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: Základné techniky písania ILP
Literatúra: V:14; V:16.3-16.4

Týždeň 23.-27.3.2015
P: Ťažko aproximovateľné problémy a redukcie. Neaproximovateľnosť všeobecného TSP. Základný problém: MAX-3-SAT. Príklad: nezávislá množina nemá PTAS. Rozostup-vytvárajúce a rozostup-zachovávajúce redukcie.
, C: Ťažko aproximovateľné problémy - redukcie. Opakovanie: Quicksort, podrobná analýza časovej zložitosti.
Literatúra: V:29 alebo Par2:5.5 (oboje podstatne viac ako na prednáške)

Týždeň 30.3.-3.4.2015
P: Pravdepodobnostné algoritmy. Úvod do pravdepodobnostných algoritmov. Las Vegas algoritmy. Hľadanie mediána / problém výberu.
C: Veľká noc
Literatúra: CLRS2: 7; CLRS2: 9
Slajdy:Poznámky a ďalšie materiály:
Problém výberu, časová zložitosť:PDF, 102 Kb ]

Týždeň 6.-10.4.2015
P: Monte Carlo algoritmy. Miller-Rabinov algoritmus na testovanie prvočíselnosti. Generovanie náhodného prvočísla. Vzťah medzi Las Vegas a Monte Carlo algoritmami.
C: Efektívna reprezentácia množín - Bloomov filter
Literatúra: CLRS2: 31.8 alebo Par2: 6.2,7.4

Týždeň 13.-17.4.2015
P: Pravdepodobnostné algoritmy pre problém splniteľnosti formúl.
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, 30 Kb ]
Fingerprinting:PDF, 42 Kb ]

Týždeň 20.-24.4.2015
Vyučovanie odpadá - Študentská vedecká konferencia
C: Randomizované dátové štruktúry (skip lists, treaps)
Literatúra: MR:8.2,8.3

Týždeň 28.4.-2.5.2015
P: Pravdepodobnostné algoritmy pre najlacnejšiu kostru. C: Náhodné prechádzky a Markovova nerovnosť
Literatúra: MR:10.3
Slajdy:Poznámky a ďalšie materiály:
Najlacnejšia kostra:PDF, 78 Kb ]

Týždeň 4.-8.5.2015
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ň 11.-15.5.2015
Zložitosť. Rozšírený prehľad tried zložitosti a ich hierarchií. Zložitostné triedy pravdepodobnostných a aproximačných algoritmov.
C: Dokončovanie predchádzajúcich tém
Literatúra: BB: 12.6
Slajdy:Poznámky a ďalšie materiály:
Hierarchia zložitostných tried:PDF, 240 Kb ]

Týždeň 18.-22.5.2015
Zhrnutie semestra - metódy riešenia ťažkých problémov.
C: nebude
Slajdy:Poznámky a ďalšie materiály:
Prehľad metód:PDF, 168 Kb ]


Maintained by 2-AIN-205 personnel