456-0335/02 – Vybrané partie teoretické informatiky (VPTI)
| Garantující katedra | Katedra informatiky | Kredity | 6 |
| Garant předmětu | prof. RNDr. Petr Jančar, CSc. | Garant verze předmětu | prof. RNDr. Petr Jančar, CSc. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 3 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2006/2007 | Rok zrušení | 2009/2010 |
| 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ě)
Projekt
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:
P. Jančar: pracovní text ke kursu
Doporučená literatura:
L. Kučera: Kombinatorické algoritmy, matem. seminář SNTL 18, Praha 1983
Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi: Complexity
and Approximation; Springer 1999
Clarke, Grumberg, Peled: Model Checking, MIT Press 1999
T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms; The MIT Press,
1990
Gibbons, Rytter: Efficient parallel algorithms; 1988, Cambridge Univ.Press,
J.Gruska: Foundation of Computing. International Thomson Computer Press 1997.
Gruska, Jozef: Quantum Computing, Mc Graw Hill 1999
Hromkovič J.: Communication complexity and parallel computing; Springer 1997
Lynch N.A.: Distributed Algorithms; Morgan Kaufmann 1996
Reisig, Rosenberg (eds.): Lectures on Petri nets I, II, Springer 1998
M. Sipser: Introduction to the Theory of Computation; PWS 1997
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Aproximační algoritmy, příslušné třídy složitosti.
(2 přednášky)
Pravděpodobnostní algoritmy, příslušné třídy složitosti.
(2 přednášky)
Paralelní algoritmy, příslušné třídy složitosti.
(2 přednášky)
Distribuované algoritmy; komunikační složitost.
(2 přednášky)
Kvantové výpočty, DNA computing.
(1 přednáška)
Konkurentní systémy, Petriho sítě.
(2 přednášky)
Verifikace systémů (mj. temporální logika, model checking).
(2 přednášky)
Cvičení:
Návrh a analýza konkrétních aproximačních algoritmů.
(2 cvičení)
Návrh a analýza konkrétních pravděpodobnostních algoritmů.
(2 cvičení)
Návrh a analýza konkrétních paralelních algoritmů.
(2 cvičení)
Návrh a analýza konkrétních distribuovaných algoritmů.
(2 cvičení)
Analýza vybraného kvantového či DNA algoritmu.
(1 cvičení)
Popis a analýza konkrétních konkurentních systémů.
(2 cvičení)
Specifikace vybraných vlastností systémů v temporální logice a algoritmy jejich ověření.
(2 cvičení)
Projekty:
Samostatné nastudování a písemné zpracování zadaného tématu,
zpravidla spojené s ústním referátem.
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