Leto 2015
Prednášky a poznámky
| 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 ] |
|