Zima 2013
Prednášky a poznámky
| 2-AIN-105: Vybrané kapitoly z teoretickej informatiky Zima 2013 Prednášky a poznámky |
|
Kontakt | 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ň 23.-29.9.2013 | |
|
P: Úvod. Bentleyho problém. C: Jednoduché efektívne algoritmy. Literatúra: Ben1:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Bentleyho problém: [ PDF, 60 Kb ] |
Priklady z cvičení: [ PDF, 86 Kb ] Riešenia: [ PDF, 135 Kb ] |
| Týždeň 30.9.-6.10.2013 | |
|
P: Formalizácia výpočtového modelu. Výpočtová zložitosť. Asymptotiky. Greedy algoritmy. Problém výberu aktivít (začiatok). C: Asymptotiky. Príklady odhadu zložitosti jednoduchých pseudokódov. Literatúra: BB:2,3.1-3.3,4.1-4.4 alebo Par:1.1-1.4 alebo CLRS2:1-3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Zložitosť, Greedy algoritmy: [ PDF, 38 Kb ] |
Poznámky: úvod a zložitosť: [ PDF, 157 Kb ] Priklady z cvičení: [ PDF, 106 Kb ] Riešenia: [ PDF, 159 Kb ] |
| Týždeň 7.-13.10.2013 | |
|
P: Problém výberu aktivít (pokračovanie). Huffmanove kódy C: Greedy rozmieňanie peňazí - kedy funguje a kedy nie?, príklady greedy algoritmov Literatúra: BB:6 (odlišné príklady) alebo Par:2.3 (odlišné príklady) alebo CLRS2:16 (odlišný prístup k výkladu) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Výber aktivít, Huffmanove kódy: [ PDF, 33 Kb ] |
Poznámky: Greedy algoritmy: [ PDF, 194 Kb ] Príklady z cvičení: [ PDF, 103 Kb ] Riešenia: [ PDF, 120 Kb ] |
| Týždeň 14.-20.10.2013 | |
|
P: Huffmanove kódy (dokončenie).
Dynamické programovanie. Všeobecný algoritmus na rozmieňanie peňazí. C: Memorizácia, príklady dynamické programovanie Literatúra: BB:8.1-8.3 alebo Par:2.2 (odlišné príklady) alebo CLRS2:15.1-15.3 (odlišné príklady) |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Huffmanove kódy, dynamické programovanie: [ PDF, 75 Kb ] |
Poznámky: Dynamické programovanie: [ PDF, 193 Kb ] Príklady z cvičení: [ PDF, 60 Kb ] Riešenia: [ PDF, 97 Kb ] |
| Týždeň 21.-27.10.2013 | |
|
P: Najdlhšia spoločná podpostupnosť.
Najkratšia triangulácia. C: Ďalšie príklady na dynamické programovanie Literatúra: CLRS2:15.4, nepokryté: najkratšia triangulácia |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Dynamické programovanie (pokr.): [ PDF, 61 Kb ] |
Príklady z cvičení (+riešenia): [ PDF, 144 Kb ] |
| Týždeň 28.10.-3.11.2013 | |
|
P: Rozdeľuj a panuj. Merge sort. Metódy riešenia rekurencií / Master theorem. Literatúra: BB:4.7,7.1-7.4 alebo Par:2.1 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Rozdeľuj a panuj: [ PDF, 70 Kb ] |
Poznámky: Rozdeľuj a panuj: [ PDF, 300 Kb ] |
| Týždeň 4.-10.11.2013 | |
|
P: Master theorem (dôkaz), Najbližší pár bodov. C: Riešenie rekurencií pomocou substitučnej metódy a Master theorem Literatúra: CLRS2:4.4,33.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Rozdeľuj a panuj (pokr.): [ PDF, 85 Kb ] |
|
| Týždeň 11.-17.11.2013 | |
|
P: Grafové algoritmy. Opakovanie základných pojmov z teórie grafov. Prehľadávanie do hĺbky. Hľadanie
artikulácií. C: Strassenov algoritmus, Lineárny výber k-teho prvku Literatúra: BB:5.4-5.5 alebo CLRS2:B.4,22.1, BB:9.3 alebo CLSR2:22.2 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Grafové algoritmy: [ PDF, 52 Kb ] |
Poznámky: Grafové algoritmy: [ PDF, 303 Kb ] |
| Týždeň 18.-24.11.2013 | |
|
P: Hľadanie artikulácií (pokr.). Najkratšie cesty - Dijkstrov algoritmus. Najlacnejšie kostry - Kruskalov algoritmus. C: Formulovanie problémov ako úlohy na grafoch Literatúra: BB:9.5,8.5,6.3 alebo CLRS2:22.3 alebo Par1:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Grafové algoritmy (pokr.): [ PDF, 41 Kb ] |
|
| Týždeň 25.11.-1.12.2013 | |
|
P: NP-ťažké problémy. Problém obchodného
cestujúceho. Rozhodovacie problémy. Trieda problémov P. Nedeterminizmus.
Trieda problémov NP. C: Ukážky programovania s nedeterminizmom. Prečo niektoré problémy (napr. KNAPSACK) nie sú v P aj keď ich vieme riešiť dynamickým programovaním? Ukážky polynomiálnych redukcií. Literatúra: BB:12.5 alebo CLRS2:34 alebo Par1:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
NP-ťažké problémy: [ PDF, 57 Kb ] |
|
| Týždeň 2.-8.12.2013 | |
|
P: Cookova veta. Dokazovanie NP-ťažkosti, 3-SAT->VC. C: Rozmieňanie peňazí je NP-ťažké. Ako to keď máme algoritmus dynamického programovania? Ďalšie redukcie. Literatúra: BB:12.5 alebo CLRS2:22.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
NP-ťažké problémy: [ PDF, 101 Kb ] |
Poznámky: NP-ťažké problémy: [ PDF, 245 Kb ] |
| Týždeň 9.-15.12.2013 | |
|
P: Vypočítateľné a nevypočítateľné problémy.
RAM model. Churchova-Turingova téza. Problém zastavenia. C: Jemná hranica medzi P a NP-ťažkými problémami: 2-SAT vs 3-SAT, 2-farbenie vs. 3-farbenie, Eulerovská vs. Hamiltonovská kružnica; ukážky vypočítateľných a nevypočítateľných funkcií Literatúra: Par1:4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vypočítateľnosť: [ PDF, 155 Kb ] |
|
| Týždeň 16.-22.12.2013 | |
|
P: Turingova reducibilita. Univerzálny RAM. Ďalšie
nevypočítateľné problémy. Zhrnutie semestra. C: Otázky a odpovede |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Vypočítateľnosť (pokr.): [ PDF, 123 Kb ] |
Poznámky: Vypočítateľnosť: [ PDF, 198 Kb ] |