460-4115/01 – Vybrané partie teoretické informatiky (VPTI)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. Ing. Zdeněk Sawa, Ph.D.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník2Semestrletní
Jazyk výukyčeština
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
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ě)

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" (dostupný z web-stránky předmětu)

Doporučená literatura:

D. Kozen: Theory of computation, Springer 2006

Forma způsobu ověření studijních výsledků a další požadavky na studenta

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 Sharp-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 Sharp-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

Prezenční forma (platnost od: 2015/2016 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 45  20
        Zkouška Zkouška 55  6
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (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