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. Logika. Logické spojky.
  2. Syntaxe a sémantika výrokové logiky.
  3. Ekvivalentní úpravy. Predikátová logika.
  4. Predikátová logika.
  5. Formální jazyky – základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Konečné automaty.
  6. Konstrukce konečných automatů. Nedeterministické konečné automaty.
  7. Převod nedeterministických konečných automatů na deterministické. Regulární výrazy.
  8. Bezkontextové gramatiky a jazyky.
  9. Algoritmy a algoritmické problémy.
  10. Asymptotická notace. Složitost algoritmů.
  11. Složitost problémů. Třídy složitosti. Převody mezi problémy. NP-úplné problémy.
  12. Algoritmicky nerozhodnutelné 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ž 22 bodů, přičemž minimem nutným pro získání zápočtu je 7 bodů.

Písemka se bude skládat ze dvou částí:

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 7 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 14 bodů, ze kterých stále bude nutné získat minimálně 7 bodů. (Body na zápočet budou v tom případě počítány podle opravné písemky.)

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ě 7 bodů.

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ž 78 bodů. Zkouška bude probíhat písemnou formou.

Zkouška se bude skládat ze tří částí věnovaných následujícím oblastem, přičemž za každou část je možné získat až 26 bodů:

Pro absolvolvování zkoušky je nutné získat z každé z těchto částí minimálně 10 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


Slidy z přednášek

Zde se budou v průběhu semestru postupně objevovat slidy z přednášek pro školní rok 2013/2014.
  • 1. přednáška
    – úvod, výroková logika, logické spojky
    česky, anglicky
  • 2. přednáška
    – syntaxe a sémantika výrokové logiky, ekvivalentní úpravy
    česky, anglicky
  • 3. přednáška
    – normální formy formulí, logické vyplývání
    česky, anglicky
  • 4. přednáška
    – rezoluční metoda, predikátová logika
    česky, anglicky
  • 5. přednáška
    – syntaxe a sémantika predikátové logiky
    česky, anglicky
  • 6. přednáška
    – predikátová logika (dokončení)
    česky, anglicky
  • 7. přednáška
    – formální jazyky, regulární výrazy
    česky, anglicky
  • 8. přednáška
    – deterministické konečné automaty
    česky, anglicky
  • 9. přednáška
    – nedeterministické konečné automaty, převod regulárních výrazů na konečné automaty
    česky, anglicky
  • 10. přednáška
    – bezkontextové gramatiky
    česky, anglicky
  • 11. přednáška
    – algoritmy a algoritmické problémy, korektnost algoritmu
    česky, anglicky
  • 12. přednáška
    – výpočetní složitost algoritmů, asymptotická notace
    česky, anglicky
  • 13. přednáška
    – analýza výpočetní složitosti algoritmů
    česky, anglicky
Kompletní slidy z přednášek ze školního roku 2013/2014: česky, anglicky

Slidy z přednášek ze školního roku 2012/2013: č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 2013/2014:

Animace


Další texty


Další literatura


Zpět