UINSB01 Teoretická informatika

Filozoficko-přírodovědecká fakulta v Opavě
léto 2018
Rozsah
0/0. 0 kr. Ukončení: -.
Garance
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • 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.
Výukové metody
Přednáška s aktivizací
Přednáška s analýzou videozáznamu
Metody hodnocení
Závěrečná ústní zkouška
Informace učitele
Teoretické a praktické zvládnutí témat předmětu, podmínky budou upřesněny na začátku výuky.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2007, léto 2008, zima 2008, léto 2009, zima 2009, léto 2010, zima 2010, léto 2011, zima 2011, léto 2012, zima 2012, léto 2013, zima 2013, léto 2014, zima 2014, léto 2015, zima 2015, léto 2016, zima 2016, léto 2017, zima 2017, zima 2018, léto 2019, léto 2020.