Zpět

Úvod do teoretické informatiky

Garant: Přednášející: Cvičící: Tutor pro studenty v kombinované formě studia:

Aktuální informace

Informace pro studenty v kombinované formě studia

Tutor: Ing. Martin Kot, Ph.D (místnost: EA413, e-mail: martin.kot@vsb.cz)

Náplň předmětu

Cílem předmětu je seznámit studenty se základy následujících oblastí teoretické informatiky:

Předběžný program přednášek:

  1. Ú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.
  2. Regulární výrazy. Deterministické konečné automaty (DKA). Konstrukce konečných automatů. Některé jazykové operace na DKA.
  3. 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.
  4. Bezkontextové gramatiky a jazyky.
  5. Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM).
  6. Algoritmy. Churchova-Turingova teze. Korektnost algoritmů. Dokazování korektnosti algoritmů.
  7. Výpočetní složitost algoritmů. Asymptotická notace. Analýza výpočetní složitosti konkrétních algoritmů.
  8. Algoritmicky nerozhodnutelné problémy (např. halting problem).
  9. 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.
  10. Konkrétní příklady NP-úplných problémů a převodů mezi problémy.

Požadavky na zápočet

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í:

Studenti, kteří buď

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.

Zkouška

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ů:

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.

Cvičení

Materiály

Výukové texty

Přednášky

Zde se budou v průběhu semestru postupně objevovat slidy z přednášek pro školní rok 2023/2024.
  • 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

  • 9. přednáška
    Téma: Výpočetní složitost algoritmů. Asymptotická notace.
    Slidy: česky, anglicky

Kompletní slidy z přednášek ze školního roku 2022/2023: č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

Videa s přednáškami

Další texty

Další literatura

Zpět