460-4065/04 – Teoretická informatika (TI)

Garantující katedraKatedra informatikyKredity6
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íPovinnostpovinný
Ročník2Semestrzimní
Jazyk výukyangličtina
Rok zavedení2022/2023Rok 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í
KOT06 Ing. Martin Kot, Ph.D.
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 3+3
kombinovaná Zápočet a zkouška 15+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: - umí vyhodnotit vhodnost a rozsah možného nasazení metod konečných automatů, bezkontextových gramatik apod. při řešení konkrétních problémů praxe a umí příslušná řešení vytvářet, analyzovat a porovnávat - je schopen analyzovat výpočtovou složitost problémů vyskytujících se v inženýrské praxi a navrhovat vhodné algoritmy pro jejich řešení - rozumí pojmům jako aproximační algoritmy, pravděpodobnostní algoritmy apod. a umí vyhodnotit možnosti jejich použití v konkrétních praktických kontextech

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Kurs prohlubuje a rozšiřuje teoretické základy v oblasti formálních jazyků, automatů, gramatik, výpočtových problémů a hlavně algoritmů a jejich složitosti, které student měl v základní formě nabýt v bakalářském studiu. Je také kladen speciální důraz na správné používání formalismu matematické logiky a důkazových technik.

Povinná literatura:

[1] Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007 (dostupná z web-stránky předmětu).

Doporučená literatura:

[2] Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997. [3] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997. [4] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009. [5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. [6] Kozen, D.: Theory of computation, Springer 2006. [7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001. [8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003. [9] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.

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

V průběhu semestru se bude psát zápočtová písemka. Každý student dále 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á písemnou 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

1. Úvod. Základní výpočetní modely (Turingovy stroje, stroje RAM, ...), připomenutí výpočetní složitosti algoritmu. 2. Třídy složitosti. Třídy P a NP, redukce mezi problémy NP-úplnost, klasické NP-úplné problémy. 3. Další třídy složitosti - PSPACE, EXPTIME, EXPSPACE, polynomiální hierarchie. 4. Algoritmicky nerozhodnutelné problémy, Riceova věta. 5. Pokročilejší techniky analýzy a návrhu algoritmů: amortizovaná složitost, složitost algoritmů v průměrném případě (pravděpodobnostní analýza). 6. Randomizované algoritmy, aproximační algoritmy. 7. Výpočetní složitost paralelních algoritmů: výpočetní modely pro paralelní algoritmy (PRAM). 8. Analýza výpočetní složitosti paralelních algoritmů, třída NC, souvislost s obvody (circuit complexity). 9. Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost. 10. Kolmogorov complexity. 11. Sémantika programovacích jazyků: formální popis sémantiky (operační sémantika, denotační sémantika). 12. Metody dokazování korektnosti programů. 13. Kvantové výpočty.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2022/2023 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 35 (35) 15
                Zápočtová písemka Písemka 20  10
                Referát Jiný typ úlohy 15  1
        Zkouška Zkouška 65  25 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 INF P angličtina Ostrava 2 povinný stu. plán
2023/2024 (N0613A140035) Informatika INF P angličtina Ostrava 2 povinný stu. plán
2023/2024 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P angličtina Ostrava 1 volitelný odborný stu. plán
2022/2023 (N0613A140035) Informatika INF P angličtina Ostrava 2 povinný stu. plán
2022/2023 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P angličtina Ostrava 1 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í.