Předmět Teoretické základy informatiky (KMI / SZZI2)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / SZZI2 - Teoretické základy informatiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Optimalizační problémy, aproximační algoritmy, základní pojmy a příklady. Třídy NPO a PO, NP-těžké optimalizační problémy, příklady, vlastnosti. Problém minimálního pokrytí, aproximační algoritmus a jeho vlastnosti. Problém maximáního řezu, aproximační algoritmus a jeho vlastnosti. Problém pokrytí množiny (set cover), aproximační algoritmus a jeho vlastnosti. Pojmy PTAS, FPTAS, klasifikace problémů z NPO. Neaproximovatelnost, základní metody dokazování neaproximovatelnosti.Základní pojmy z pravděpodobnosti, pravděpodobnostní prostor, náhodná veličina, podmíněná pravděpodobnost. Pojem entropie, základní vlastnosti, jednoznačnost entropie. Sdružená a podmíněná entropie. Rozhodovací stromy a výběr dělicího atributu pomocí podmíněné entropie.Kódy a kódování, základní pojmy, jednoznačně dekódovatelné kódy, prefixové kódy, blokové kódy, test jednoznačné dekódovatelnosti. Kódování bez šumu, Kraftova a McMillanova nerovnost. Optimální kódy a Shannonova věta. Huffmanův kód, jeho optimalita. Kódy opravující a detekující chyby, Hammingova vzdálenost, minimální vzdálenost kódu, informační poměr, systematický kód. Binární lineární kódy, jejich příklady, pojem kontrolní matice. Hammingovy kódy. Lineární kódy, základní pojmy.Základní struktura překladače, typy překladačů, fáze překladu. Lexikální analýza: základní pojmy (vzory, lexémy, tokeny), činnost lexikálního analyzátoru (simulace, determinizace, rozpoznávání lexémů), minimalizace lexikálního analyzátoru. Bezkontextové gramatiky a jazyky: nejlevější a nejpravější derivace, jednoznačnost, eliminace nadbytečných a nedostupných neterminálů, normální formy (GNF, CNF). Úpravy bezkontextových gramatik: eliminace levé rekurze, levá faktorizace, pohlcení terminálního symbolu (řetězce). Nedeterministické syntaktická analýza: shora-dolů, zdola-nahoru, CYK algoritmus. Deterministická analýza shora-dolů: množiny First a Follow, zásobníkové automaty a jazyky třídy SLL(1) a LL(k). Deterministická analýza zdola-nahoru: zásobníkové automaty a jazyky tříd LR(0), SLR(1), LALR(1) a LR(1). Atributové gramatiky: sémantická pravidla, atributy (syntetizované a dědičné), S-atributové gramatiky, L-atributové gramatiky, konstrukce abstraktního derivačního stromu, metoda rekurzivního sestupu. Generování lineárního kódu: překlad do registrového a zásobníkového kódu, příklady překladů konstrukcí vyšších PJ.
Garant
prof. RNDr. Radim Bělohlávek, Ph.D., DSc.