KIV/TI - Teoretická informatika
Z FAV wiki
(Rozdíly mezi verzemi)
(Založena nová stránka: Připravuje se... :)) |
|||
| Řádka 1: | Řádka 1: | ||
| − | + | Nejsou to úpně všechny otázky co se v testech objevují - seznam by potřeboval doplnit. | |
| + | |||
| + | |||
| + | == 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. | ||
| + | |||
| + | |||
| + | == 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. | ||
| + | |||
| + | |||
| + | == 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. | ||
| + | |||
| + | |||
| + | == 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. | ||
| + | |||
| + | |||
| + | == 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.“. | ||
Verze z 20. 9. 2011, 20:22
Nejsou to úpně všechny otázky co se v testech objevují - seznam by potřeboval doplnit.
Obsah |
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.
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.
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.
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.
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.“.
