1. Do taneˇcn´ıho krouˇzku chod´ı 15 chlap˚ u a 20 d´ıvek. Kolik r˚ uzn´ ych p´ar˚ u z nich m˚ uˇzeme vytvoˇrit? 2. Ze sady 28 kostek domina vyt´ahnu dvˇe. Kolika zp˚ udoby to mohu prov´est tak, aby ony dvˇe kostiˇcky ˇsly k sobˇe pˇriloˇzit podle pravidel domina? ˇ ste jak 3. Kolik lich´ ych ˇctyˇrcifern´ ych ˇc´ısel lze vytvoˇrit z cifer 0, 1, 2, 3, 4? Reˇ pro pˇr´ıpad, kdy se cifry mohou, tak pro pˇr´ıpad, kdy se nemohou opakovat. 4. Tiket sazky m´a tˇrin´act ˇr´adk˚ u. S´azej´ıc´ı v kaˇzd´em ˇr´adku zaˇskrtne jednu z moˇznost´ı 0, 1 nebo 2. Kolika zp˚ usoby to m˚ uˇze prov´est? 5. Kolika zp˚ usoby lze pomoc´ı n prvkov´e abecedy vytvoˇrit slovo o k znac´ıch? P´ısmena se mohou opakovat, ”slovo” v˚ ubec nemus´ı b´ yt vysloviteln´e. (Variace k-t´e tˇr´ıdy z n prvk˚ u s opakov´ an´ım.) 6. Kolik pˇeticifern´ ych ˇc´ısel lze vytvoˇrit z cifer 1, 2, 3, 4, 5, 6, 7, 8? Vyj´adˇrete pomoc´ı faktori´al˚ u. Cifry se nesm´ı opakovat. 7. Kolika zp˚ usoby lze z n prvkov´e abecedy vybrat slova d´elky k, sloˇzen´a z r˚ uzn´ ych p´ısmen ? (Variace k-t´e tˇr´ıdy z n prvk˚ u bez opakov´ an´ı.) 8. Deset pˇr´atel se dohodne,ˇze bude chodit vˇzdy v nedˇeli do restaurace na obˇed k desetim´ıstn´emu stolu a pokaˇzd´e si sednou jinak. Jak dlouho jim bude trvat, neˇz vyˇcerpaj´ı vˇsechny moˇznosti? 9. Kolika zp˚ usoby lze pˇreh´azet poˇrad´ı prvk˚ u n-prvnkov´e mnoˇziny? (Permutace z n prvk˚ u.) 10. Kolika zp˚ usoby lze ze soutˇeˇze o 16 u ´ˇcastn´ıc´ıch vybrat a) medalisty b) tˇri sestupuj´ıc´ı? 11. Kolik existuje k prvkov´ ych podmnoˇzin n prvkov´e mnoˇziny? (Kombinace k-t´e tˇr´ıdy z n prvk˚ u.) 12. Dokaˇzte n´asleduj´ıc´ı vztahy pro kombinaˇcn´ı ˇc´ısla. n n n n n+1 n n n = + = + +. . .+ = 2n k n−k k k+1 k+1 0 1 n 13. Kolik existuje moˇzn´ ych tah˚ u Sportky bereme-li v u ´vahu i dodatkov´e ˇc´ıslo? 14. Kolik r˚ uzn´ ych slov lze vytvoˇrit ze slova abrakadabra? 15. Kolik r˚ uzn´ ych slov mohu vytvoˇrit z k-prvkov´e abecedy, jestliˇze prvn´ı prvek mus´ım pouˇz´ıt pr´avˇe n1 kr´at, druh´ y n2 kr´at atd. aˇz k-t´ y nk kr´at? (Permutace s opakov´ an´ım.) 1
16. Babiˇcka chce rozdˇelit sv´ ym ˇctyˇrem vnouˇck˚ um deset kobl´ıˇzk˚ u. zp˚ usoby to m˚ uˇze udˇelet, jestliˇze
Kolika
(a) Nem´a ˇz´adn´a omezen´ı. (b) Chce d´at kaˇzd´emu alespoˇ n jeden kob´ıˇzek usoby lze rozdˇelit k pˇredmˇet˚ u mezi n subjekt˚ u? (Kombinace 17. Kolika zp˚ k-t´e tˇr´ıdy z n prvk˚ u s opakov´ an´ım.) 18. Sestrojte graf relace a rozhodnˇete, jedn´a-li se o relaci reflexivn´ı, symetrickou, tranzitivn´ı ˇci antisymetrickou. (a) [x, y] ∈ RxR; y > x2 &y < 2x + 3 2
(b) [x, y] ∈ RxR; 1 ≤ x2 + y2 ≤ 4 (c) [x, y] ∈ RxR; −1 ≤ xy ≤ −2 (d) [x, y] ∈ RxR; y > x2 & y < 1 − x2 (e) [x, y] ∈ RxR; x ≤ y ≤ 2x & 1 ≤ x2 + y 2 ≤ 9 (f) [x, y] ∈ RxR; 1 ≤ |x| + |y| ≤ 2 (g) [x, y] ∈ RxR; x2 + y 2 ≤ 4 & |x| > |y| (h) [x, y] ∈ RxR; |x|.|y| ≤ 1 (i) [x, y] ∈ RxR; −1 ≤ x2 − y 2 ≤ 1 19. Najdˇete mnoˇzinu re´aln´ ych ˇc´ısel takovou, ˇze tato mnoˇzina vybaven´ a operac´ı a ⊕ b = a + b + ab tvoˇr´ı grupu. √ 20. Ukaˇzte, ˇze mnoˇzina kladn´ ych re´aln´ ych ˇc´ısel tvaru a + b 2, kde a, b ∈ Q vybaven´a operac´ı n´asoben´ı tvoˇr´ı grupu. ˇ ste v Z5 soustavu rovnic 21. Reˇ x1 + 2x2 + x3 + x4 + x5 2x1 + x2 + x3 + 2x4 + x5 x1 + 2x2 + 2x3 + 3x4 + 2x5 2x1 + x2 + 2x3 + 2x4 + 2x5
=1 =2 =1 =3
ˇ ste v Z7 soustavu rovnic 22. Reˇ x1 + 2x2 + 3x3 + 5x4 + x5 = 6 2x1 + x2 + 6x3 + 2x4 + x5 = 2 x1 + 2x2 + 5x3 + 3x4 + 2x5 = 1 2x1 + x2 + 4x3 + x4 + x5 = 3 2
23. Urˇcete hodnost matice modulo 5, 2 3 A= 3 3 3
pˇr´ıpadnˇe modulo 7. 2 3 4 1 1 2 2 1 1 1 2 0 2 1 4 1 1 2 2 1
24. Modulo 5 nebo 7 vypoˇctˇete determinant 2 1 1 1 1 1 3 1 3 1 1 1 1 1 0 2 0 1 1 3
1 1 1 1 4
25. Rozhodnˇete, zda n´asleduj´ıc´ı ˇc´ıseln´e mnoˇziny uspoˇr´adan´e dˇelitelnost´ı tvoˇr´ı svaz, v kladn´em pˇr´ıpadˇe rozhodnˇete, zda jde o svaz distributivn´ı ˇci komˇ d˚ plement´arn´ı, v z´aporn´em uvedte uvod. (a) M1 = {2, 3, 4, 12, 18, 24, 36, 72} (b) M2 = {1, 2, 3, 12, 18, 36} (c) M1 = {2, 4, 8, 16, 32, 64} (d) M2 = {1, 2, 3, 12, 18, 36} (e) M1 = {1, 3, 5, 7, 105, 210} (f) M2 = {2, 3, 4, 12, 18, 24, 36, 72} (g) M1 = {1, 5, 6, 12, 60} (h) M2 = {4, 8, 16, 24, 32, 64} (i) M1 = {1, 2, 3, 6, 7, 14, 21, 42} (j) M2 = {2, 3, 4, 12, 18, 24, 36, 72} (k) M1 = {1, 2, 5, 7, 10, 14, 35, 70} (l) M2 = {1, 3, 4, 24, 36, 72} 26. Zapiˇste n´asleduj´ıc´ı Booleovskou funkci v u ´pln´e disunktivn´ı a u ´pln´e konjunktivn´ı norm´aln´ı formˇe.
3
(a) A ∨ (B&C) ⇒ (A ⇔ (B ∨ C)) (b) (A&(B ∨ C)) ⇒ (A&(B ⇔ C)) (c) (A ⇒ (B&C)) ⇔ A&(B ∨ C) 27. Rozhodnˇete, zda n´asleduj´ıc´ı posloupnost je grafov´a, v kladn´em pˇr´ıpadˇe najdˇete patˇriˇcn´ y graf. (a) 7, 7, 6, 6, 5, 5, 5, 3, 2, 2 (b) 7, 5, 5, 5, 5, 4, 4, 3, 2, 2 28. Pro n8sleduj´ıc´ı frekvenˇcn´ı tabulky najdˇete optim´aln´ı Huffman˚ uv k´od, urˇcete jeho v´ahu a zak´odujte dan´e slovo (a) A - 25, B - 6, D - 10, E - 120, L - 12, M - 15, P - 8, R - 4 MADLA (b) A - 20, B - 6, D - 10, E - 20, L - 12, N - 15, P - 8, S - 4 BEDNA (c) A - 15, B - 6, D - 10, E - 20, M - 12, O - 15, L - 8, R - 12 MODLA (d) A - 25, D - 10, E - 10, L - 30, O - 15, I - 8, T - 4 LOLITA
4
29. Pro n´asleduj´ıc´ı grafy najdˇete (a) automorfismy (b) poˇcet koster (c) prostor kruˇznic (d) prostor ˇrez˚ u (e) poˇcty sled˚ u konkr´etn´ı d´elky
t
t
@
@
t
@
@
@ @t
@
@ @t
@ @t
t
t
J
J J
J
JJt
JJt
t @ @ @ @ @t
5
t
t
t
t
J J
JJt
t HH
HH HH
H
t t
t
Z
J JZ
J Z J
J Z J
Z
J J
J Z
ZJ
J ZJ Z Jt
Jt Z
t
t tJ
J
JJt
t HH J
J HHH
JJt HH
t
6
t
t
J J
JJt
t HH J
HH J HH
JJt H
t
t
A A A A t At A A A A A A A At t t A
t
t
J
J J J
J JJt t
t J J
J
J
J
JJt
J
t
7
t
t
t
Z
J JZ
J Z J
J Z J
Z
J J
J Z
ZJ
J ZJ Z Jt
Jt Z
t
t
t
H
J HH
H J
HH J Ht
t
J J
J J
J JJ Jt t
t t H H J
HH J
HHJ
t t Jt H JJ
J
Jt
30. Najdˇete w-distanˇcn´ı matici n´asleduj´ıc´ıch graf˚ u Ohodnocen´ı hran: w(1, 4) = 8, w(1, 5) = 2, w(1, 6) = 1, w(2, 1) = 4, w(2, 4) = 2, w(3, 2) = 6, w(3, 4) = 10, w(4, 2) = 2, w(5, 2) = 3, w(5, 4) = 12, w(6, 5) = 5
8
-t * 6 J
J
J
^t t
* ] J
J
t Jt t
t
t
H Y * ] H H J
H
HHJ Jt t
H Z } Z > Z ZZ ZZ Z Z ~ Z t
Ohodnocen´ı hran: w(1, 2) = 1, w(1, 3) = 1, w(1, 4) = 3, w(1, 5) = 3, w(2, 1) = 2, w(2, 3) = 4, w(2, 4) = 2, w(3, 4) = 4, w(3, 5) = 1, w(4, 5) = 2
9
t t k QQ 6 AK AK Q A Q A A Q A Q A t QAt A 3 A A A A A A AU t -At
Ohodnocen´ı hran: w(1, 2) = 4, w(1, 6) = 12, w(2, 3) = 1, w(2, 4) = 2, w(2, 6) = 6, w(3, 4) = 1, w(3, 6) = 4, w(4, 1) = 1, w(4, 5) = 1, w(4, 6) = 3, w(5, 6) = 1
10
31. Pomoc´ı Dijkstrova algoritmu najdˇete vzd´alenost vrchol˚ u u a v.
t P 1 tH P *Z >P @H S 7 HH Z P P j H qt P ZS@ P t @ Z S ZS@ BA Z @BA SZ BA @B AU SZ Rt @ ~ t SZ B S BN 6 w? S t t
(a) Ohodnocen´ı hran: w(u, 1) = 4, w(1, 2) = 5, w(2, 3) = 3, w(3, 4) = 4, w(4, 5) = 5, w(5, 6) = 4, w(6, v) = 3, w(u, 2) = 7, w(1, 3) = 6, w(2, 4) = 8, w(3, 5) = 6, w(4, 6) = 7, w(5, v) = 6, w(u, 3) = 12, w(1, 4) = 11, w(2, 5) = 13, w(3, 6) = 14, w(4, v) = 11
11
t P 1 tH P *Z >P @H S 7 HH Z P P j H qt P ZS@ P t @ Z S ZS@ BA Z @BA SZ BA @B AU SZ Rt @ ~ t SZ B S BN 6 w? S t t
(b)
12
32. Najdˇete nejkratˇs´ı moˇzn´e trv´an´ı n´asleduj´ıc´ıho projektu a urˇcete kritickou cestu.
(a)
ˇcinnost A B C D E F G H I J K L M N O P
doba 5 6 4 3 4 5 7 8 4 7 6 5 2 4 1 2
podm´ınka A,B B B B,C B,C D,E D,E,F,G D,E,F,G D,E,F,G H I,J K L,M
(b)
ˇcinnost A B C D E F G H I J K L
doba 3 4 7 3 4 6 2 5 4 6 5 4
podm´ınka A A B B D,E,F,G D,E,F D,E,F F G,H G,H,I,J
13
(c)
ˇcinnost A B C D E F G H I J K L
doba 7 4 2 2 3 5 6 5 2 4 3 4
podm´ınka A B B,C D,E,F E,F E,F G G,H,I I
14
