Leto 2014
Prednášky a poznámky
| 2-AIN-205: Vybrané kapitoly z teoretickej informatiky (2) Leto 2014 Prednášky a poznámky |
|
Kontakt | Body | Základné informácie | Domáce úlohy | Písomky a skúšky | Prednášky a poznámky
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ň 17.-21.2.2014 | |
|
C: Opakovanie P, NP, NP-ťažkosť, TSP. Trieda NP a nedeterministické Turingove stroje. Certifikáty. P: Úvod, prehľad semestra, motivácia. 2-aproximačný algoritmus pre metrické TSP. 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, 171 Kb ] |
|
| Týždeň 24.-28.2.2014 | |
|
C: Backtracking, A* prehľadávanie, všeobecný TSP nie je k-aproximovateľný
pre žiadnu konštantu k P: Aproximačné algoritmy. k-aproximačné algoritmy. Aproximačné algoritmy pre vertex cover a set cover. 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, 91 Kb ] |
|
| Týždeň 3.-7.3.2014 | |
|
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) P: Polynomiálne aproximačné schémy (PTAS). PTAS pre problém batohu. 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: |
|---|---|
|
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ň 10.-14.3.2014 | |
|
C: Opakovanie pravdepodobnosti, stredné
hodnoty. Algoritmy s očakávanou k-aproximáciou. Pravedpodobnostná
metóda. P: PTAS pre bin packing. Literatúra: CLRS2:C; V:2.4; V:16.1 alebo CLRS2:35.4; V:9 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Definície PTAS: [ PDF, 63 Kb ] |
|
| Týždeň 17.-21.3.2014 | |
|
C: Celočíselné lineárne programovanie (ILP).
Riešenie TSP pomocou ILP. Používanie ILP solvera (SCIP). 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). Literatúra: V:14; V:16.3-16.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Bin packing, ILP: [ PDF, 108 Kb ] |
Solver SCIP: [ linka ] ILP demo: [ zip, 21 Kb ] |
| Týždeň 24.-28.3.2014 | |
|
C: Základné techniky písania ILP 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. Literatúra: V:29 alebo Par2:5.5 (oboje podstatne viac ako na prednáške) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Krátke zhrnutie príkladov z cvičení: [ PDF, 94 Kb ] |
|
| Týždeň 31.3.-4.4.2014 | |
|
C: Ťažko aproximovateľné problémy - redukcie. Opakovanie: Quicksort, podrobná analýza časovej zložitosti. P: Pravdepodobnostné algoritmy. Úvod do pravdepodobnostných algoritmov. Las Vegas algoritmy. Hľadanie mediána / problém výberu. Literatúra: CLRS2: 7; CLRS2: 9 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Problém výberu, časová zložitosť: [ PDF, 77 Kb ] |
|
| Týždeň 7.-11.4.2014 | |
|
C: Vzorové riešenia midtermu. Hľadanie podobných množín pomocou minhash-ov. 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. Literatúra: CLRS2: 31.8 alebo Par2: 6.2,7.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Testovanie prvočíselnosti: [ PDF, 23 Kb ] |
|
| Týždeň 14.-18.4.2014 | |
|
C: Technika fingerprinting. P: Pravdepodobnostné algoritmy pre problém splniteľnosti formúl. Literatúra: MR:7.1,7.2,7.4,7.6 alebo Par2: 7.2; MR:6.1 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Splniteľnosť formúl: [ PDF, 19 Kb ] |
|
| Týždeň 21.-25.4.2014 | |
| Vyučovanie odpadá - Veľká noc a Študentská vedecká konferencia |
| Týždeň 28.4.-2.5.2014 | |
|
C: Randomizované dátové štruktúry (skip lists, treaps) P: Pravdepodobnostné algoritmy pre najlacnejšiu kostru. Literatúra: MR:8.2,8.3; MR:10.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Minimálna kostra: [ PDF, 68 Kb ] |
|
| Týždeň 5.-9.5.2014 | |
|
C: dokončovanie predchádzajúcich tém 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. Literatúra: Par2: 3.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vrcholové pokrytie: [ PDF, 19 Kb ] |
|
| Týždeň 12.-16.5.2014 | |
| Zhrnutie semestra - metódy riešenia ťažkých problémov. | |
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Prehľad metód: [ PDF, 199 Kb ] |
|
| Týždeň 19.-23.5.2014 | |
|
Zložitosť. Rozšírený prehľad tried
zložitosti a ich hierarchií. Zložitostné triedy pravdepodobnostných a
aproximačných algoritmov. Literatúra: BB: 12.6 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Hierarchia zložitostných
tried: [ PDF, 240 Kb ] |
|