460-4115/02 – 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ýukyanglič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 20+20
kombinovaná Zápočet a zkouška 14+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:

[1] P. Jančar: pracovní text ke kursu "Vybrané partie teoretické informatiky" (dostupný z web-stránky předmětu)

Doporučená literatura:

[2] Kozen, D.: Theory of computation, Springer 2006 [3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. [4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. [5] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003. [6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.

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

Každý student v průběhu semestru vypracuje referát na zadané téma z oblasti teoretické informatiky, který bude prezentovat. Předmět je zakončen zkouškou. Tato zkouška probíhá ústní formou.

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 #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 #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ůMax. počet pokusů
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 3
Rozsah povinné účasti: Účast na cvičeních je povinná a je kontrolována. S rozsahem povinné účastí seznámí studenty garant předmětu na začátku semestru.

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Splnění všech povinných úkolů v individuálně dohodnutých termínech. Rozsah účasti na cvičeních si student na začátku semestru dohodne s garantem předmětu.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2024/2025 (N0613A140035) Informatika TI P angličtina Ostrava 2 povinně volitelný typu B stu. plán
2023/2024 (N0613A140035) Informatika TI P angličtina Ostrava 2 povinně volitelný typu B stu. plán
2023/2024 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P angličtina Ostrava 2 volitelný odborný stu. plán
2022/2023 (N0613A140035) Informatika TI P angličtina Ostrava 2 povinně volitelný typu B stu. plán
2022/2023 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P angličtina Ostrava 2 volitelný odborný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P angličtina Ostrava 2 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P angličtina Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P anglič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 angličtina Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K anglič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 angličtina Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P anglič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 angličtina Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K anglič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 angličtina Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K anglič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 anglič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 angličtina Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K anglič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 anglič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 angličtina Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P angličtina Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K anglič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 anglič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 anglič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

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.