UINSB01 Theoretical Computer Science

Faculty of Philosophy and Science in Opava
Winter 2017
Extent and Intensity
0/0. 0 credit(s). Type of Completion: -.
Guaranteed by
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Syllabus (in Czech)
  • A1. Teorie formálních jazyků a automatů
    1. Gramatika, typy gramatik - Chomského hierarchie.
    2. Konečné automaty, ekvivalence deterministických a nedeterministických
    konečných automatů.
    3. Vztah mezi regulárními gramatikami a konečnými automaty.
    4. Zásobníkové automaty. Akceptování prázdným zásobníkem a koncovými stavy.
    5. Deterministické a nedeterministické zásobníkové automaty.
    6. Vztah zásobníkových automatů a bezkontextových gramatik.
    7. Bezkontextové gramatiky, normální tvary gramatik.
    8. Turingovy stroje a jazyky typu 0.
    A2. Teorie vyčíslitelnosti a složitosti
    1. Turingův stroj: definice, přijímání jazyků a výpočet funkcí. Univerzální Turingův stroj.
    2. Rekurzívní a rekurzívně spočetné jazyky. Souvislost s rozhodovacími problémy a jejich (ne)rozhodnutelností.
    3. Metoda diagonalizace a metoda redukce pro dokazování nerozhodnutelnosti, příklady jejich užití.
    4. Metoda redukce pro dokazování nerozhodnutelnosti, příklad jejího užití.
    5. Riceho věta a její důsledky.
    6. Časová a prostorová složitost výpočtu, třídy DTIME(f(n)), NTIME(f(n)), DSPACE(f(n)), NSPACE(f(n)) a jejich vzájemné vztahy.
    7. Stroj RAM, porovnání složitosti výpočtů na RAM a Turingově stroji.
    8. Základní složitostní třídy DLOG, NLOG, P, NP atd., definice a vzájemné vztahy.
    9. Třída NP, NP-úplnost, polynomiální redukce. NP úplné problémy.
    A3. Logika
    1. Výroková logika, syntax a sémantika jazyka výrokové logiky.
    2. Ekvivalence výrokových formulí. Normální formy výrokových formulí.
    3. Splnitelnost a platnost formule ve výrokové logice, rozhodování pomocí sémantického stromu, Quienův algoritmus, reduction ad absurdum, tablová metoda, rezoluční metoda, dedukce ve výrokové logice.
    4. Predikátová logika 1. řádu - jazyk predikátové logiky, term, formule, substituce, sémantika, splnitelná formule v interpretaci, pravdivá formule v interpretaci, splnitelná formule, tautologie, kontradikce.
    5. Obecná rezoluční metoda v predikátové logice - obecna? rezoluc?ni? metoda, klauzulární (Skolemova) forma, Skolemova funkce, Skolemova konstanta, prenexní tvar formule, Herbrandova procedura, Robinsonův unifikační algoritmus, Herbrandovo universum, zobecněné rezoluční odvozovací pravidlo.
    A4. Teorie grafů
    1. Grafy a jednoduché grafy, vrchol, hrana, stupeň vrcholu. Podgrafy, faktor, indukovaný podgraf, incidenční matice a matice sousednosti grafu.
    2. Sled, tah, cesta, cyklus, dosažitelnost, souvislost a vzdálenost v grafu, izomorfismus grafů
    3. Strom, kostra, les, bipartitní grafy, úplné bipartitní grafy, algoritmus nalezení minimální kostry grafu.
    4. Vrcholová a hranová souvislost grafů
    5. Párování a pokrytí grafů, úplné párování, popište nalezení úplného párování pomocí algoritmu hledající nesaturované alternující cesty.
    6. Hranové a vrcholové barvení grafů, dobré hranové a vrcholové barvení, chromatický index a chromatické číslo a jejich meze, skladovací problém.
    7. Planární a neplanární grafy, Eulerův vzorec, věta o 4 barvách, průsečíkové číslo
    8. Eulerovské a hamiltonovské grafy, problém obchodního cestujícího.
    9. Orientované grafy, ohodnocené grafy, prohledávání grafu, značkování, prohledávání do šířky, do hloubky, konstrukce cest.
Teaching methods
Interactive lecture
Lecture with a video analysis
Assessment methods (in Czech)
Závěrečná ústní zkouška
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
The course is also listed under the following terms Winter 2007, Summer 2008, Winter 2008, Summer 2009, Winter 2009, Summer 2010, Winter 2010, Summer 2011, Winter 2011, Summer 2012, Winter 2012, Summer 2013, Winter 2013, Summer 2014, Winter 2014, Summer 2015, Winter 2015, Summer 2016, Winter 2016, Summer 2017, Summer 2018, Winter 2018, Summer 2019, Summer 2020.
  • Enrolment Statistics (Winter 2017, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2017/UINSB01