Garant:Přednášející:
- doc. Ing. Zdeněk Sawa, Ph.D. (místnost: EA413, e-mail: zdenek.sawa@vsb.cz)
Cvičící:
- doc. Ing. Zdeněk Sawa, Ph.D.
Tutor pro studenty v kombinované formě studia:
- Mgr. Pavla Dráždilová, Ph.D.
- Ing. Martin Kot, Ph.D.
- Mgr. Marek Menšík, Ph.D.
- doc. Ing. Zdeněk Sawa, Ph.D.
- Ing. Martin Kot, Ph.D.
- 23.3.2025: Zápočtová písemka se bude psát v následujících termínech:
- Studenti v prezenční formě studia — v týdnu od 14. dubna 2025 do 17. dubna 2025 na cvičeních
- Studenti v kombinované formě studia — na tutoriálu v pátek 25. dubna 2025 v 10:45
Tutor: Ing. Martin Kot, Ph.D (místnost: EA413, e-mail: martin.kot@vsb.cz)
Cílem předmětu je seznámit studenty se základy následujících oblastí teoretické informatiky:
- teorie formálních jazyků a automatů,
- vyčíslitelnost a složitost.
Předběžný program přednášek:
- Úvod. Čím se zabývá teoretická informatika (algoritmy, algoritmické problémy, formální jazyky, ...). Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích.
- Regulární výrazy. Deterministické konečné automaty (DKA). Konstrukce konečných automatů. Některé jazykové operace na DKA.
- Nedeterministické konečné automaty (NKA). Převod NKA na DKA. Jazykové operace na NKA. Vztah mezi regulárními výrazy a konečnými automaty.
- Bezkontextové gramatiky a jazyky.
- Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM).
- Algoritmy. Churchova-Turingova teze. Korektnost algoritmů. Dokazování korektnosti algoritmů.
- Výpočetní složitost algoritmů. Asymptotická notace. Analýza výpočetní složitosti konkrétních algoritmů.
- Algoritmicky nerozhodnutelné problémy (např. halting problem).
- Složitost problémů. Třídy složitosti (především třídy P a NP). Převody mezi problémy. NP-úplné problémy.
- Konkrétní příklady NP-úplných problémů a převodů mezi problémy.
Písemka
V průběhu semestru se bude psát zápočtová písemka, za kterou bude možno získat až 24 bodů, přičemž minimem nutným pro získání zápočtu je 12 bodů.
Zápočtová písemka se bude psát na některém cvičení. Konkrétní datum bude v průběhu semestru ještě upřesněno.
Pro studenty, kteří ze závažných důvodů (např. nemoc) nemohli písemku psát, bude vypsán náhradní termín.
Studenti, kteří ze zápočtové písemky nezískají potřebných 12 bodů, budou mít možnost získat body na zápočet v opravné písemce. Opravná písemka však bude pouze za 20 bodů, ze kterých stále bude nutné získat minimálně 12 bodů. (Body na zápočet budou v tom případě počítány podle opravné písemky.)
Aktivita na cvičení
Za aktivitu na cvičení je možné získat až 6 bodů, přičemž nutným minimem pro získání zápočtu jsou 3 body.
Podmínky pro získání zápočtu
Pro získání zápočtu je nutné získat ze zápočtové písemky minimálně 12 bodů a za aktivitu na cvičení minimálně 3 body.
Studenti, kteří předmět opakují a v loňském roce získali zápočet, si mohou zvolit jednu z následujících dvou možností:
- Nechat si zápočet zapsat s počtem bodů získaným loni.
- Absolvovat celý předmět znovu.
Studenti, kteří buď
- mají zápočet z loňska uznaný a zapsaný v Edisonu, ale nechtějí ho uznat, nebo
- mají nárok na uznání zápočtu z loňska a chtějí ho uznat, ale nemají ho zapsaný v Edisonu
musí o tom, že zápočet chtějí nebo nechtějí uznat, informovat svého cvičícího nejpozději během prvních dvou týdnů semestru. Na pozdější žádosti o uznání nebo neuznání zápočtu nebude brán zřetel.
Studenti, kteří zápočet chtějí uznat a mají ho již v Edisonu zapsaný, nemusí dělat nic.
Studentům, kteří předmět opakují, ale nemají uznaný zápočet z loňska, žádné body z loňska uznány nebudou a musí vše absolvovat znovu.
Za zkoušku bude možné získat až 70 bodů. Zkouška bude probíhat písemnou formou.
Zkouška se bude skládat ze dvou částí věnovaných následujícím oblastem, přičemž za každou část je možné získat až 35 bodů:
- teorie formálních jazyků a automatů
- vyčíslitelnost a složitost
Pro absolvolvování zkoušky je nutné získat z každé z těchto částí minimálně 12 bodů.
Pro studenty 3. ročníku, kteří předmět opakují a budou chtít jít letos ke státnicím, bude vypsán předtermín. Obsah zkoušky v předtermínu bude stejný jako u zkoušek v řádných termínech.
- Studenti by měli chodit na cvičení připraveni.
- Na webových stránkách k předmětu budou předem zveřejňována zadání příkladů na cvičení. Předpokládá se, že každý student se předem sám pokusí tyto příklady vyřešit a na cvičení se pak budou řešit především různé nejasnosti a případné problémy, na které studenti při samostatném řešení narazí.
- Studenti jsou povinni si na cvičení nosit zadání příkladů (buď vytištěná nebo v elektronické podobě), aby se během cvičení nemuseli zdržovat jejich opisováním.
- Cvičení neslouží jako náhrada přednášek! Nebudou tedy na nich znovu vysvětlovány základní pojmy z přednášek, neboť se předpokládá, že studenti tyto pojmy již z přednášek znají. Cvičení budou zaměřena na řešení příkladů a objasňování případných nejasností.
Výukové texty
- Úvod do teoretické informatiky (autor: prof. RNDr. Petr Jančar, CSc.) — základní výukový text pro oblasti jazyků a automatů a vyčíslitelnosti a složitosti
- Úvod do teoretické informatiky: algoritmy (verze z 5.1.2021) (autor: doc. Ing. Zdeněk Sawa, Ph.D.) — výukový text pro oblast algoritmů, tento text ještě není zcela hotov, v průběhu semestru bude dále doplňován a rozšiřován
Přednášky
Zde se budou v průběhu semestru postupně objevovat slidy z přednášek pro školní rok 2024/2025.
- 1. přednáška
Téma: Úvod. Čím se zabývá teoretická informatika (algoritmy, algoritmické problémy, formální jazyky, ...). Formalní jazyky. Operace na slovech a na jazycích.
Slidy: česky, anglicky
- 2. přednáška
Téma: Regulární výrazy. Deterministické konečné automaty. Jazykové operace na konečných automatech.
Slidy: česky, anglicky
- 3. přednáška
Téma: Nedeterministické konečné automaty. Vztah mezi regulárními výrazy a konečnými automaty. Neregulární jazyky.
Slidy: česky, anglicky
- 4. přednáška
Téma: Bezkontextové gramatiky.
Slidy: česky, anglicky
- 5. přednáška
Téma: Zásobníkové automaty.
Slidy: česky, anglicky
- 6. přednáška
Téma: Turingovy stroje. Chomského hierarchie.
Slidy: česky, anglicky
- 7. přednáška
Téma: Výpočetní modely. Varianty Turingových strojů. Stroje RAM.
Slidy: česky, anglicky
- 8. přednáška
Téma: Algoritmy. Churchova-Turingova teze. Dokazování korektnosti algoritmů.
Slidy: česky, anglicky
Zadání příkladů na cvičení
Zde se budou v průběhu semestru postupně objevovat zadání příkladů na cvičení pro školní rok 2023/2024:
Animace
- Animace — animace ilustrující některá témata probíraná v předmětu UTI
Videa s přednáškami
- Odkaz na YouTube kanál s nahranými přednáškami z let 2020 a 2021: videa na YouTube
Další texty
- Teoretická informatika (autor: prof. RNDr. Petr Jančar, CSc.) — výukový text pro oblasti jazyků a automatů a vyčíslitelnosti a složitosti pro studenty magisterského studia pro předmět Teoretická informatika, jedná se o rozšířenou verzi textu pro UTI, je určen studentům s hlubším zájmem o problematiku
- Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
- Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
- Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
- Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
- Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997.