..:: Martin Kot ::..

Introduction to theoretical computer science

English version of this subpage is under construction

Study text

13.02.2013	Úvod do teoretické informatiky: logika, množiny, matematická notace (autor: Ing. Zdeněk Sawa, Ph.D.) - základní výukový text pro oblast logiky, tento text ještě není zcela hotov, v průběhu semestru bude dále doplňován a rozšiřován
07.02.2013	Výukový text k teorii jazyků a automatů a k vyčíslitelnosti a složitosti. Výukový text vznikl v letech, kdy předmět neobsahoval matematickou logiku. Ne vše z něj tedy bude skutečně probráno.
07.02.2013	Animace - seznam animací k předmětům Teoretická informatika a Úvod do teoretické informatiky. Jde o animace vytvořené v rámci bakalářských a diplomových prací, animace, které byly součástí přednášek (trochu doplněné, aby dávaly smysl i samostatně bez výkladu), a některé zcela nové.
04.03.2013	Přehled pravidlel — přehled odvozovacích pravidel pro výrokovou a predikátovou logiku

Study text

07.02.2013	Rozšířená verze výukového textu (pro studenty s hlubším zájmem o danou problematiku).
13.02.2013	Logika pro informatiky (autor: doc. RNDr. Marie Duží, CSc.) — výukový text k logice, v rámci předmětu UTI bude probírána pouze část učiva z tohoto textu

Exercises

07.02.2013	Příklady na 1. cvičení - množiny, relace, funkce, ...
15.02.2013	Příklady na 2. cvičení - důkazy sekventů se spojkami konjunkce a disjunkce
25.02.2013	Příklady na 3. cvičení - důkazy sekventů, formule výrokové logiky
04.03.2013	Příklady na 4. cvičení - tabulková metoda pro výrokovou logiku, ekvivalence formulí ve výrokové logice
18.03.2013	Příklady na 5. cvičení - normální formy formulí výrokové logiky, predikátová logika
18.03.2013	Příklady na 6. cvičení - predikátová logika, formální jazyky
27.03.2013	Příklady na 7. cvičení - jazykové operace, regulární výrazy, konečné automaty
04.04.2013	Příklady na 8. cvičení - konečné automaty (deterministické i nedeterministické a převody mezi nimi)
12.04.2013	Příklady na 9. cvičení - bezkontextové gramtiky
15.04.2013	Příklady na 10. cvičení - stroj RAM
02.05.2013	Příklady na 11. cvičení - Turingovy stroje, asymptotická notace pro porovnání růstu funkcí
02.05.2013	Příklady na 12. cvičení - časová složitost algoritmu
02.05.2013	Příklady na 13. cvičení - třídy problémů PTIME a NPTIME

Lectures - slides

15.02.2013	Úvod, matematické důkazy
25.02.2013	Logické spojky, syntaxe a sémantika výrokové logiky
04.03.2013	Syntaxe a sémantika výrokové logiky, ekvivalentní úpravy
18.03.2013	Normální formy formulí výrokové logiky, syntaxe a sémantika predikátové logiky
18.03.2013	Dedukční systém pro predikátovou logiku 1. řádu, úvod do formálních jazyků
27.03.2013	Jazykové operace, regulární výrazy, konečné automaty
04.04.2013	Operace na automatech, nedeterministické konečné automaty, převod regulárních výrazů na konečné automaty
12.04.2013	Bezkontextové gramatiky
12.04.2013	Problémy a algoritmy, stroj RAM
02.05.2013	Turingovy stroje, výpočetní složitost algoritmů, asymptotická notace

Combined form of study - slides

21.03.2013	Příklady na 2. cvičení s ukázkovými řešeními některých příkladů - důkazy sekventů se spojkami konjunkce a disjunkce
21.03.2013	Příklady na 3. cvičení s ukázkovými řešeními některých příkladů - důkazy sekventů, formule výrokové logiky
21.03.2013	Příklady na 4. cvičení s ukázkovými řešeními některých příkladů - tabulková metoda pro výrokovou logiku, ekvivalence formulí ve výrokové logice
21.03.2013	Příklady na 5. cvičení s ukázkovými řešeními některých příkladů - normální formy formulí výrokové logiky, predikátová logika
21.03.2013	Příklady na 6. cvičení s ukázkovými řešeními některých příkladů - predikátová logika, formální jazyky
27.03.2013	Příklady na 7. cvičení s ukázkovými řešeními některých příkladů - jazykové operace, regulární výrazy, konečné automaty
04.04.2013	Příklady na 8. cvičení s ukázkovými řešeními některých příkladů - konečné automaty (deterministické i nedeterministické a převody mezi nimi)
21.05.2013	Příklady na 9. cvičení s ukázkovými řešeními některých příkladů - bezkontextové gramtiky
21.05.2013	Příklady na 10. cvičení s ukázkovými řešeními některých příkladů - stroj RAM
21.05.2013	Příklady na 11. cvičení s ukázkovými řešeními některých příkladů - Turingovy stroje, asymptotická notace pro porovnání růstu funkcí
21.05.2013	Příklady na 12. cvičení s ukázkovými řešeními některých příkladů - časová složitost algoritmu
21.05.2013	Příklady na 13. cvičení s ukázkovými řešeními některých příkladů - třídy problémů PTIME a NPTIME