KIV/TI - Teoretická informatika
Z FAV wiki
Nejsou to úpně všechny otázky co se v testech objevují - seznam by potřeboval doplnit.
Obsah |
[editovat] Automaty
- 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.
[editovat] Jazyky a gramatiky
- 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.
[editovat] Teorie informace
- 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.
[editovat] Kódování a kódy
- 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.
[editovat] Výrokový počet
- 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.“.