460-4043/01 – 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í
Odkaz na webhttp://www.cs.vsb.cz/jancar/VPTI/vpti.htmJazyk výukyčeština
Rok zavedení2010/2011Rok zrušení2014/2015
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.
MEC059 Ing. Ondřej Meca
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 "Vybrané partie teoretické informatiky"

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

Způsob průběžné kontroly znalostí během semestru

E-learning

Další požadavky na studenta

Další požadavky na studenta nejsou kladeny.

Minimální znalostní požadavky

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: 2010/2011 zimní semestr, platnost do: 2014/2015 letní 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
                Referát Jiný typ úlohy 30  15
        Zkouška Zkouška 70  25
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (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