456-0335/01 – Vybrané partie teoretické informatiky (VPTI)
| Garantující katedra | Katedra informatiky | Kredity | 5 |
| 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 | povinně volitelný |
| Ročník | 3 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2003/2004 | Rok zrušení | 2006/2007 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | 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
Další studijní materiály
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
Pravděpodobnostní algoritmy, příslušné třídy složitosti
Paralelní algoritmy, příslušné třídy složitosti
Distribuované algoritmy; komunikační složitost
Kvantové výpočty, DNA computing
Konkurentní systémy, Petriho sítě
Verifikace systémů (mj. temporální logika, model checking)
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
Předmět neobsahuje žádné hodnocení.