Vypracované otázky ke státnicím z okruhu Teoretická informatika a matematika

predikátová logika

formální jazyky

lineární algebra

popisná statistika

pravděpodobnost

evoluční algoritmy

• 1. Model a jazyk výrokové a predikátové logiky. Syntax jazyka, induktivní definice gramatiky jazyka, míry složitosti výrokové/predikátové formule.
  2. Splňování a pravdivost ve výrokové logice. Valuace výrokových proměnných a interpretace formulí, interpretační pravidla, Booleovy funkce. Metody sémantické analýzy výrokové formule: tabulková metoda, tablová metoda, sémantický strom, Quineův algoritmus. Modely a logické důsledky. Normální formy výrokových formulí. Klauzulární forma formulí.
  3. Splňování a pravdivost v predikátové logice. Interpretace predikátové formule: valuace proměnných, interpretační pravidla, pravdivost atomů. Normální formy predikátových formulí. Klauzulární tvar predikátové formule. Metody sémantické analýzy predikátové formule
  4. Dedukce ve výrokové a predikátové logice: modely a logické důsledky, teorie. Rozhodnutelnost splnitelnosti a platnosti výrokových a predikátových formulí. Rezoluční a tablová metoda rozhodování a jejich využití.
  5. Formální jazyky a jejich využití v informatice. Základní pojmy teorie formálních jazyků. Konečné automaty - deterministický, nedeterministický, zobecněný nedeterministický. Ekvivalence automatů, redukce, homomorfismus. Uzávěrové vlastnosti třídy jazyků rozpoznatelných KA. Regulární jazyky. Regulární výrazy. Kleeneho věta. Nerodova věta a charakterizace jazyků rozpoznatelných konečným automatem pomocí pravých kongruencí. Algoritmy transformace regulárních výrazů na konečné automaty. Použití regulárních jazyků v praxi.
  6. Bezkontextové gramatiky a jazyky, nevypouštějící gramatiky, redukované gramatiky. Regulární gramatiky. Lineární gramatiky. Normální formy. Kanonická odvození, derivační stromy. Věta o vkládání (tzv. pumping lemma). Zásobníkové automaty a jejich vztah k bezkontextovým jazykům. Determinismus vs. nedeterminismus. Uzávěrové vlastnosti třídy bezkontextových jazyků. Chomského hierarchie. Vztah gramatika-jazyk-automat v kontextu Chomského hierarchie. Využití bezkontextových jazyků v praxi.
  7. Časová a prostorová složitost algoritmů. Odhady a třídy složitosti. Zvládnutelné a nezvládnutelné problémy. Příklady problémů a jejich odhady složitosti. Nedeterministický Turingův stroj a jeho časová složitost. P-NP problém a jeho důsledky.
  8. Lineární algebra. Vektorové prostory: definice a příklady, lineární závislost vektorů, báze vektorového prostoru, lineární zobrazení vektorových prostorů, prostory se skalárním součinem. Matice a determinanty: definice a základní vlastnosti, algebra matic a determinantů, řešení soustavy lineárních algebraických rovnic.
  9. Kombinatorika. Variace, permutace, kombinace, kombinatorické principy, kombinační čísla.
  10. Logické funkce. Základní pojmy, logické formule, ekvivalence formulí, princip duality, rozklad logické funkce podle proměnných, funkcionální úplnost, funkcionální uzavřenost.
  11. Teorie grafů. Pojem grafu, isomorfismus grafů, reprezentace grafu, souvislost grafu, podgrafy, eulerovské grafy.
  12. Popisná statistika. Statistická data. Měření, veličiny, škály. Charakteristiky polohy, charakteristiky variability. Korelační koeficient. Statistické grafy - sloupcový graf, histogram, krabicový graf, bodový graf - příklady užití. Softwarové prostředky pro statistické zpracování dat.
  13. Pravděpodobnost. Náhodná veličina. Distribuční funkce. Rozdělení diskrétní a spojitá. Rovnoměrné spojité rozdělení a programové funkce pro generování pseudonáhodných čísel. Statistická indukce. Náhodný výběr. Bodové a intervalové odhady parametrů rozdělení. Testování hypotéz, chyby I. a II. druhu.
  14. Diskrétní kódy. Entropie zdroje zpráv, střední délka kódového slova, redundance. Kódy nejkratší délky - Huffmanova nebo Shannon-Fanova konstrukce kódu. Lineární kódy, Hammingova vzdálenost, hodnocení vlastností kódů. Systematické kódy, generující a kontrolní matice, Hammingovy kódy, cyklické kódy. Jak použijeme znalosti z kódování při konstrukci unikátních identifikátorů?
  15. Komprese dat. Klasifikace kompresních algoritmů. Hodnocení vlastností kompresních algoritmů. Principy a použití vybraného algoritmu bezeztrátové komprese (např. metoda opakování znaků, algoritmus LZ nebo LZW, aplikace Huffmanova kódu nebo aritmetické komprese). Principy a použití komprese pro rastrový obraz.
  16. Vysvětlete vybranou technologii softcomputingu (z následujícího seznamu) a ukažte její použití pro řešení aktuálních problémů:
  • Fuzzy logika: základní pojmy fuzzy logiky (fuzzy množiny, lingvistické proměnné, operace s fuzzy množinami, fuzzy pravidla).
  • Evoluční algoritmy: základní pojmy (fitness - kvalita jedince, křížení, mutace), princip řešení úloh evolučními algoritmy.
  • Neuronové sítě: základní pojmy (formální neuron, vnitřní potenciál, bias, přenosové funkce), topologie neuronových sítí principy adaptačních algoritmů (učení s učitelem, učení bez učitele).