Os. číslo: Jméno a příjmení: Datum:

1. Vysvětlete rozdíl mezi rozpoznávacím automatem a klasifikačním automatem. (3b)

2. Uveďte definici Moorova konečného automatu. Vysvětlete význam všech použitých symbolů. (5b)

3. Vysvětlete rozdíl mezi uzávěrem množiny a iterací množiny. (2b)

4. Formulujte základní úlohu teorie jazyků. (3b)

5. Obecně popište tvar pravidel gramatik typu 2. Uveďte konkrétní pravidlo, které je pravidlem gramatiky typu 2 a přitom není pravidlem gramatiky typu 3. (3b)

6. Definujte pojem „přímé přepsání řetězce w na řetězec z“. (5b)

7. S pomocí zobecněné přechodové funkce definujte řetězec w zamítnutý deterministickým rozpoznávacím automatem. (2b)

8. Kdy je gramatika typu 3 v regulárním tvaru? (3b)

9. Definujte diskrétní zdroj informace bez paměti a jeho střední entropii. (2b)

10. Uveďte alespoň tři důvody, proč se používá kódování. (2b)

11. Zformulujte Kraftovu nerovnost. O čem vypovídá? (5b)

12. Znázorněte všechny přijímací strategie, které lze použít u kódu s minimální Hammingovou vzdáleností 6. (2b)

13. Co znamená, že kód objevuje t-násobné chyby? (3b)

14. Uveďte rozměr a vlastnosti kontrolní matice H lineárního kódu. (2b)

15. Jak počítá příjemce lineárního kódu syndrom, na čem tento syndrom závisí? (2b)

16. 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?. (2b)

17. Jak se provádí kódování informační části u systematického cyklického kódu s generujícím mnohočlenem g(x). (5b)

18. Jaký je rozdíl mezi tautologií a splnitelnou formulí? (2b)

19. Kolik existuje různých logických funkcí tří proměnných? (2b)

20. Zformulujte podmínky, které musí být splněny, aby bylo platné tvrzení „Formule B logicky vyplývá z množiny formulí A1 , A2 , A3 “ (5b)

P1: Sestrojte deterministický klasifikační automat, který bude klasifikovat občany ČR podle rodného čísla do následujících tříd:

A …….. muži, kteří v roce 2005 dosáhnou věku nejméně 18 a nejvýše 60 let

B …….. ženy, kteří v roce 2005 dosáhnou věku nejméně 20 a nejvýše 40 let

C …….. ostatní muži

D …….. ostatní ženy

Předpokládejte, že vstupní řetězec reprezentuje občana mladšího než 100 let. (20b.)

P2: Je dán systematický kód (8,4) s následujícími kontrolními rovnicemi:

z1 = u2 + u3 + u4

z2 = u1 + u2 + u3

z3 = u1 + u3 + u4

z4 = u1 + u2 + u4

a) vytvořte matice G a H tohoto kódu

b) zakódujte informační část u = [1,1,0,1]^T

c) ukažte detekci chyby při chybovém vektoru e = [1,1,0,0,0,0,0,0]^T

d) jaké chyby maximální násobnosti je tento kód schopen opravovat a jaké detekovat (nikoli současně)? Zdůvodněte!