7. a 8. cvičení z MB154, podzim 2021
Příklad 1. Projděte příklady z vnitrosemestrálky.
Příklad 2. Množinu čtyř slov chceme přenášet binárním kódem (rozpoznávajícím, poté) opravujícím jednoduché chyby. Jakou nejmenší délku slov (chceme pro všechna slova stejnou) můžeme mít? Udejte příklad takových čtyřech slov.
U toho jsme se zasekli na dost dlouho, bavili jsme se o grafech, vzdálenosti v grafech, tj. vysvětloval jsem Hammingovu vzdálenost, atd.
Příklad 3. Pomocí lineárního kódu daného maticí
/l 1 0\
1 0 1
1 0 0
0 1 o
V° 0 v
zakódujte zprávu 101.
Příklad 4. Určete všechna kódová slova (3, 2)-kódu generovaného polynomem x + 1.
Příklad 5. Určete generující matici polynomiálního kódu z předchozího příkladu.
Příklad 6. Určete generující matici a matici kontroly parity (7, 2)-kódu generovaného polynomem x5 + x4 + x2 + 1. Dekódujte přijaté slovo 00101111 za předpokladu, že při přenosu došlo k nejmenšímu možnému množství chyb.
Příklad 7. Určete generující matici a matici kontroly parity (7,4)-kódu generovaného polynomem x3 + x + 1. Dekódujte přijaté slovo 100| 1001 za předpokladu, že při přenosu došlo k nejmenšímu možnému množství chyb. Dekódujte přijaté slovo 10110110 za předpokladu, že při přenosu došlo k nejmenšímu možnému množství chyb.
Příklad 8. Určete počet řešení rovnice
x + y + z = 2021
v N (resp. v N0).
Příklad 9. Kolika způsoby můžeme číslo 22500000 napsat jako
(a) součin dvou přirozených čísel,
(b) součin tří přirozených čísel.
Příklad 10. Kamarádi Alice, Bob, Cecílie, David a Ema jdou spolu do kina. V kině si sednou do řady vedle sebe. Kolika způsoby si můžou posedat, pokud chtějí, aby
(a) Bob seděl vedle Cecílie,
(b) David neseděl vedle Alice,
(c) nastaly obě možnosti (a) i (b) současně.
i
2
Příklad 11. Kolika způsoby se může rozesadit 5 osob v pětimístném autě, když jen dva lidé mají řidičský průkaz? Kolika způsoby se může rozesadit 20 cestujících a 2 řidiči v 25-místném minibuse?
Příklad 12. Výsledné pořadí týmů 1. ligy se ztratilo, našlo se pouze relativní pořadí všech 7 týmů z Cech a relativní pořadí všech 6 týmů z Moravy. Kolika způsoby lze z těchto částečných údajů sestavit pořadí 1. ligy?
Jedná se o shuffle a je to jen kombinační číslo, ale bylo by fajn, kdyby to studenti viděli.
Příklad 13. Na kolik oblastí může nejvýš rovinu rozdělit n kružnic?
an = 1, 2,4, 8,..., přičemž další člen je 14, což je docela hezké. Indukcí: n-tá kružnice může protnout všechny předchozí v 2 • (n — 1) bodech (nedokazujte; platí pro n > 2), které ji dělí na 2 • [n — 1) oblouků, přičemž každý z nich dělí jednu z předchozích oblastí na dvě, takže an = an_i + 2 • [n — 1), dostaneme an = n2 — n + 2 pro n > 1.
Příklad 14. V šatně si 4 návštěvníci odložili své kabáty a klobouky. Nešťastnou náhodou všechny klobouky spadly na zem. Satnářka chce klobouky opět pověsit, ale protože si nepamatuje, který patří komu, pověsí je k jednotlivým kabátům zcela náhodně. Kolika způsoby může klobouky pověsit, tak aby alespoň jeden návštěvník dostal svůj klobouk.