PLIN006 cvičení, jaro 2011
Př. 1
Nakreslete grafy a určete stupně jednotlivých vrcholů:
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {{1, 2}, {1, 4}, {2, 3}, {3, 4}, {2, 4}}
∙ 𝑉 = {𝑤, 𝑥, 𝑦, 𝑧}, 𝐸 = {{𝑤, 𝑥}, {𝑥, 𝑦}, {𝑦, 𝑧}}
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {{1, 2}}
∙ 𝑉 = {1, 2}, 𝐸 = ∅
∙ 𝑉 = ∅, 𝐸 = ∅
Které z nich jsou souvislé, které z nich jsou stromy? Vyjádřete tyto grafy jako
relace.
Př. 2
Nakreslete a zapište množinovým zápisem následující grafy:
∙ úplný graf na 4 vrcholech
∙ úplný graf na 3 vrcholech
∙ úplný graf na 2 vrcholech
∙ úplný graf na 1 vrcholu
∙ úplný graf na 6 vrcholech
∙ kružnici na 6 (resp. 5, 4, 3, 2, 1) vrcholech
∙ cestu na 6 (resp. 5, 4, 3, 2, 1) vrcholech
∙ graf, který má stupně vrcholů postupně 2, 3, 3, 2
∙ graf, který má stupně vrcholů postupně 3, 3, 4, 4, 4
∙ graf, který má stupně vrcholů postupně 2, 4, 4, 2
Najděte v těchto grafech největší kliky, největší cykly a nejdelší cesty.
1
PLIN006 cvičení, jaro 2011
Př. 3
Které z následujících grafů jsou izomorfní? Najděte isomorfismy, případně
určete, proč grafy izomorfní nejsou.
Př. 4
Najděte nejdelší cesty a cykly v následujících grafech:
2
PLIN006 cvičení, jaro 2011
Př. 5
Nakreslete následující orientované grafy:
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {(1, 2), (1, 4), (2, 3), (3, 4), (2, 4)}
∙ 𝑉 = {𝑤, 𝑥, 𝑦, 𝑧}, 𝐸 = {(𝑤, 𝑥), (𝑥, 𝑦), (𝑧, 𝑦), (𝑤, 𝑧)}
∙ 𝑉 = {1, 2, 3, 4}, 𝐸 = {(1, 2)}
∙ 𝑉 = {1, 2}, 𝐸 = ∅ Najděte v těchto grafech největší cykly a nejdelší
cesty.
Př. 6
V následujících grafech najděte minimální kostry a nejkratší cesty mezi
vybranými dvojicemi vrcholů. Nejprve „selským rozumem”, poté použijte
Kruskalův a Dijkstrův algoritmus.
3
PLIN006 cvičení, jaro 2011
Př. 7
V orientovaném grafu z předchozího cvičení najděte silně souvislé kompo-
nenty.
Př. 8
Naprogramujte Kruskalův a Dijkstrův algoritmus v Pythonu.
Př. 9
Zapište v jazyce logiky vlastnosti, které musí splňovat pravděpodobnostní
rozložení.
Př. 10
Vyjádřete funkčním zápisem a grafem rozložení pravěpodobnosti při hodu
kostkou.
Př. 11
Mějme následující statistický soubor (výška lidí ve skupině):
160, 160, 160, 170, 170, 180, 180, 180, 190, 210
Nakreslete graf pravděpodobnostního rozložení výšky lidí na základě tohoto
souboru. Jaká je pravděpodobnost, že člověk bude vyšší než 185?
4
PLIN006 cvičení, jaro 2011
Nakreslete graf distribuční funkce pro statistický soubor výše.
Př. 12
Hážeme dvakrát po sobě kostkou. Poprvé padlo 5. Jaká je pravděpodobnost,
že padne součet větší než 8? Použijte vzorec podmíněné pravděpodobnosti.
Př. 13
Mějme následující údaje o skupině lidí:
ID Výška (cm) Váha (kg)
1 180 80
2 170 90
3 190 60
4 190 80
5 180 80
6 190 90
Mějme člověka, o kterém víme, že měří 190 cm. Jaká je pravděpodobnost,
že jeho váha bude alespoň 80 kg? (Předpokládejme, že naše data jsou
reprezentativní. (Kterému zákonu tento náš předpoklad odporuje?))
Př. 14
Dokažte Bayesův vzorec.
Př. 15
Všichni chlapci nosí kalhoty, polovina dívek nosí také kalhoty (druhá
polovina nosí sukně :) ). Vidíme z dálky člověka, který má kalhoty. Jaká je
pravděpodobnost, že je to chlapec?
Př. 16
Mějme následující text a předpokládejme, že pro dané účely je to reprezentativní
vzorek:
Stát má stát na straně pro stát vhodné. Stát na straně občanů je pro stát
obvykle nevýhodné. Nicméně stát by se mohl stát poctivějším.
Jaká je pravděpodobnost, že slovo „stát” (bez rozlišení velikosti písmen)
je sloveso (podst. jméno), pokud:
5
PLIN006 cvičení, jaro 2011
∙ neuvažujeme žádnou informaci o kontextu
∙ slovo „stát” stojí na začátku věty
∙ předchozí slovo je předložka
∙ následující slovo obsahuje právě dvě písmena
Př. 17
Máme podezření, že hrací kostka není vyvážená, ale že na ní častěji padají
šestky. Máme v úmyslu kostku sérií 20 pokusů vyzkoušet. Kolikrát musí
padnout šestka, aby se naše podezření statisticky potvrdilo s možností chyby
méně než 1 %?
Závěrečné opakování:
Př. 18
Ze 4 pokusů padla na hrací kostce 4x (3x, ...) šestka. Na základě toho
jsme usoudili, že kostka není vyvážená (pravděpodobnost, že padne šestka, je
větší než 1/6). Jaká je pravděpodobnost, že jsme se spletli?
Př. 19
Vytvořte bigramový model znaků pro frázi: „Šel do lesa”.
Př. 20
Zapište zkrácenou notací:
∙ 𝑎1 + 𝑎2 + 𝑎3 + ... + 𝑎 𝑛
∙ (𝑎1 + 1) * (𝑎2 + 1) * (𝑎3 + 1) * ... * (𝑎 𝑛 + 1)
∙ (𝑎1 + 1) * (𝑎2 + 2) * (𝑎3 + 3) * ... * (𝑎 𝑛 + 𝑛)
∙ (𝑎1 + 1) * (𝑎2 + 4) * (𝑎3 + 9) * ... * (𝑎 𝑛 + 𝑛 𝑛
)
6
PLIN006 cvičení, jaro 2011
Př. 21
Nakreslete graf distribuční funkce pro výsledky hodu vyváženou kostkou.
Př. 22
Zapište v jazyce predikátové logiky:
∙ prázdná množina je podmnožinou čehokoli
∙ pro všechny prvky prázdné množiny platí, že nejsou prvkem prázdné
množiny
∙ axiomy pravděpodobnostní distribuce
Př. 23
Navrhněte datový soubor (např. o velikosti 10 prvků), jehož distribuce
bude přibližně odpovídat:
∙ uniformnímu rozložení
∙ normálnímu rozložení
∙ Zipfovu rozložení
Př. 24
Spočitejte entropii výsledku hodu třemi mincemi (Entropie =
∑︀
𝑥∈𝑋 𝑝(𝑥)𝑙𝑜𝑔2 𝑝(𝑥))
7