456-0335/02 – Vybrané partie teoretické informatiky (VPTI)

Garantující katedraKatedra informatikyKredity6
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník2Semestrzimní
Jazyk výukyčeština
Rok zavedení2006/2007Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAN59 prof. RNDr. Petr Jančar, CSc.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+0

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

Prezenční forma (platnost od: 2006/2007 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 30 (30) 15
                Projekt Projekt 30  15
        Zkouška Zkouška 70  25
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2009/2010 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku