Zima 2014
Prednášky a poznámky
| 2-AIN-105: Vybrané kapitoly z teoretickej informatiky Zima 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 | 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ň 22.-28.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, 59 Kb ] |
|
| Týždeň 29.9.-5.10.2013 | |
|
P: Formalizácia výpočtového modelu. Výpočtová zložitosť. Asymptotiky. 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ť: [ PDF, 42 Kb ] |
Poznámky: úvod a zložitosť: [ PDF, 148 Kb ] |
| Týždeň 6.-12.10.2013 | |
|
P: Greedy algoritmy. Problém výberu aktivít. 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: |
|---|---|
|
Greedy algoritmy, výber aktivít, Huffmanove kódy: [ PDF, 32 Kb ] |
Poznámky: Greedy algoritmy: [ PDF, 180 Kb ] |
| Týždeň 13.-19.10.2013 | |
|
P: 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: |
|---|---|
|
Poznámky: Dynamické programovanie: [ PDF, 180 Kb ] |
|
| Týždeň 20.-26.10.2014 | |
|
P: Najkratšia triangulácia. Rozdeľuj a panuj. 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, 262 Kb ] |
|
| Týždeň 27.10.-2.11.2014 | |
|
P: Metódy riešenia rekurencií / Master theorem. Najbližší pár bodov. C: Riešenie rekurencií pomocou substitučnej metódy a 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, 244 Kb ] |
Poznámky: Rozdeľuj a panuj: [ PDF, 269 Kb ] |
| Týždeň 3.-9.11.2014 | |
|
P: Master theorem (dôkaz), Najbližší pár bodov. Literatúra: CLRS2:4.4,33.4 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Rozdeľuj a panuj: [ PDF, 244 Kb ] |
|
| Týždeň 10.-16.11.2014 | |
|
P: Rektorské voľno.
C: Grafy a grafové algoritmy:reprezentácia grafu, prehľadávanie do šírky a hĺbky, artikulácie.
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: |
|---|---|
|
Poznámky: Grafové algoritmy: [ PDF, 274 Kb ] |
|
| Týždeň 18.-24.11.2013 | |
|
P: midterm C: Grafy pokr.: Najkratšie cesty - Dijkstrov algoritmus. Najlacnejšie kostry - Kruskalov algoritmus. Formulovanie problémov ako úlohy na grafoch Literatúra: BB:9.5,8.5,6.3 alebo CLRS2:22.3 |
| Týždeň 24.11.-30.11.2014 | |
|
P: Rozhodovacie vs. optimalizačné problémy,.
Nedeterministické výpočty. Triedy problémov P a 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? Literatúra: BB:12.5 alebo CLRS2:34 alebo Par1:7 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
Nedeterminizmus,P,NP: [ PDF, 233 Kb ] |
|
| Týždeň 1.-7.12.2014 | |
|
P: NP-úplné problémy. Cookova veta. Dokazovanie NP-ťažkosti, 3-SAT->VC. C: Ukážky polynomiálnych redukcií. Literatúra: BB:12.5 alebo CLRS2:22.3 |
|
| Slajdy: | Poznámky a ďalšie materiály: |
|---|---|
|
NP-ťažké problémy: [ PDF, 239 Kb ] |
Poznámky: NP-ťažké problémy: [ PDF, 222 Kb ] |
| Týždeň 8.-14.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, 322 Kb ] |
|
| Týždeň 15.-21.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, 297 Kb ] |
Poznámky: Vypočítateľnosť: [ PDF, 187 Kb ] |