460-4115/01 – Vybrané partie teoretické informatiky (VPTI)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 2 | Semestr | letní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2015/2016 | Rok zrušení | |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu např.:
- umí vyhodnotit vhodnost a rozsah možného nasazení aproximačních algoritmů a pravděpodobnostních algoritmů při řešení praktických problémů a umí příslušné algoritmy navrhovat,analyzovat a srovnávat
- umí exaktně vysvětlit další pojmy a metody vybraných pokročilých partií teoretických základů informatiky
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Kurs seznamuje s vybranými metodami a výsledky některých pokročilých partií teoretické informatiky, např. z oblasti aproximačních algoritmů, pravděpodobnostních algoritmů, verifikace konkurentních systémů aj.
Povinná literatura:
[1] P. Jančar: pracovní text ke kursu "Vybrané partie teoretické informatiky"
(dostupný z web-stránky předmětu)
Doporučená literatura:
[2] Kozen, D.: Theory of computation, Springer 2006
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[5] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Každý student v průběhu semestru vypracuje referát na zadané téma z oblasti teoretické informatiky, který bude prezentovat.
Předmět je zakončen zkouškou. Tato zkouška probíhá ústní formou.
E-learning
Další požadavky na studenta
Další požadavky na studenty nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Šifrovací algoritmus RSA, problém prvočíselnosti, související algebraické základy.
2. Millerův-Rabinův test prvočíselnosti a jeho korektnost.
3. Randomizované komunikační protokoly a důkazy jejich korektnosti.
4. Interaktivní protokoly, speciálně pro problém #SAT (počet pravdivostních ohodnocení, při nichž je zadaná booleovská formule pravdivá).
5. Důkazy bez úniku informace (zero-knowledge proofs).
6. Pravděpodobnostně ověřitelné důkazy (PCP, probabilistically checkable proofs).
7. Aproximační algoritmy, např. pro Max-3-SAT, množinové pokrytí, (pod)problému TSP (obchodního cestujícího).
8. Plně polynomiální aproximační schémata.
9. Důkazy neaproximovatelnosti konkrétních optimalizačních problémů.
10. Automaty a logika na nekonečných slovech (bězích reaktivních systémů). Užití u verifikace systémů (model checking).
Cvičení (na tabulové učebně):
1. Návrh implementace konkrétních částí algoritmu RSA.Procvičení pojmu grupa a konečné těleso v souvislosti s problémem
prvočíselnosti.
2. Důkazy lemmat pro korektnost Millerova-Rabinova testu prvočíselnosti.
3. Analýza konkrétního randomizovaného komunikačního protokolu.
4. Běhy interaktivního protokolu pro problém #SAT na konkrétních instancích.
5. Analýza protokolů autentizace bez úniku informace.
6. Důkazy částí tzv. PCP teorému.
7. Návrh a analýza konkrétních aproximačních algoritmů.
8. Analýza plně polynomiálního aproximačního schématu pro problém batohu.
9. Diskuse důkazu neaproximovatelnosti problému maximální kliky v grafu.
10. Překlad formulí vyjadřujících vlastnosti běhů konkrétních systémů do formy automatů.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky