KIV/TI - Teoretická informatika

Z FAV wiki

Verze z 26. 11. 2016, 14:12; 162.219.176.204 (diskuse)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)

Přejít na: navigace, hledání

Nejsou to úpně všechny otázky co se v testech objevují - seznam by potřeboval doplnit.

Obsah

Definujte řetězec w akceptovaný nedeterministickým rozpoznávacím automatem.
S pomocí zobecněné přechodové funkce definujte řetězec w zamítnutý deter. rozpoznávacím automatem.
Uveďte alespoň 3 oblasti, kde se používají automatové modely.
Uveďte definici deterministického rozpoznávacího automatu. Vysvětlete význam všech použitých symbolů.
Uveďte definici deterministického klasifikačního automatu. Vysvětlete význam všech použitých symbolů.
Uveďte definici Mooreova a Mealyho konečného automatu. Vysvětlete význam všech použitých symbolů.
Uveďte definici nedeterministického konečného automatu. Vysvětlete význam všech použitých symbolů.
Vysvětlete rozdíl mezi klasifikačním a rozpoznávacím automatem.
Vysvětlete rozdíl mezi Mooreovým a Mealyho konečným automatem.
Vysvětlete rozdíl mezi přechodovou a výstupní funkcí konečného automatu.
Vysvětlete rozdíl mezi přechodovou funkcí deterministického a nedeterministického konečného automatu.

Co je regulární množina nad abecedou A?
Definujte pojem jazyk akceptovaný automatem.
Definujte pojem jazyk generovaný gramatikou.
Definujte pojem přímé přepsání řetězce w na řetězec z.
Formulujte základní úlohu teorie jazyků.
Jaké znáte způsoby popisu formálního jazyka?
Kdy je gramatika v regulárním tvaru?
Obecně popište tvar pravidel gramatiky typu 2. Uveďte konkrétní pravidlo, které je typu 2 a přitom není typu 3.
Uveďte a vysvětlete definici jazyka v množinovém pojetí.
Uveďte alespoň 3 oblasti, kde se používá formální jazyk.
Vysvětlete rozdíl mezi uzávěrem a iterací množiny.

Co říká Mc Millanova věta?
Co znamená, že kód opravuje t-násobné chyby? Kdy je kód schopen opravovat t-násobné chyby?
Definujte diskrétní zdroj informace bez paměti a jeho redundanci, střední entropii.
Formulujte a vysvětlete podmínku jednoznačné dekódovatelnosti.
Jakou minimální Hammingovu vzdálenost musí mít kód, aby mohl opravovat t-násobné chyby?
Uveďte alespoň 3 důvody, proč se používá kódování.
Zformulujte Kraftovu nerovnost. O čem vypovídá?
Znázorněte všechny přijímací strategie, které lze použít u kódu s minimální Hammingovou vzdáleností 6.

Co mají společného Hammingovy a Golayovy kódy?
Jak kontroluje příjemce systematického cyklického kódu přijatou značku?
Jak počítá příjemce lineárního kódu syndrom, na čem tento syndrom závisí?
Jak se provádí kódování informační části u systematického cyklického kódu s generujícím polynomem g(x).
Jaký minimální počet kontrolních prvků musí mít kód, umožňující při kódování k-prvkových informačních částí opravy jednoduchých chyb?
K čemu se používají Hammingovy a Golayovy kódy?
Uveďte rozměr a vlastnosti kontrolní matice H lineárního kódu.
Uveďte stupeň a vlastnosti generujícího polynomu cyklického kódu.

Co to znamená, že je systém axiómů úplný a bezesporný?
Formulujte pravidlo Modus Ponens, k čemu se používá?
Jaký je rozdíl mezi formulací, která není splnitelná a kontradikcí?
Jaký je rozdíl mezi tautologií a splnitelnou formulí?
Kolik existuje různých logických funkcí 3 proměnných?
Zformulujte podmínky, které musí být splněny, aby bylo platné „Formule B logicky plyne z formulí A1,A2,A3.“.