FPF:UINSB01 SZZk Teoretická informatika - Informace o předmětu

UINSB01 Teoretická informatika

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

• Informatika a výpočetní technika (program FPF, B1801 Inf) (2)
• Informatika (dvouoborové) (program FPF, B1803 InDO)

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

• Statistika zápisu (zima 2017, nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2017/UINSB01