Na této stránce se dozvíte informace, ke cvičení, které v letním semestru 2008/2009 vedu.
Vyskytuji se v místnosti 125 na Malé Straně, ale nikoli příliš často ani pravidelně. Takže pokud se mne rozhodnete navštívit osobně, ať už kvůli odevzdání příkladů, konzultaci, nebo zapsání zápočtu, je více než vhodné se předem domluvit mejlem (suchy@kam).
Většinu září budu pravděpodobně mimo Prahu, pravděpodobně nebudu mít příliš přístup k internetu, takže pravděpodobně nebudu opravovat příklady a a v některých termínech určitě nebudu fyzicky k zastižení. Doporučuji všem studentům, kteří chtějí získat zápočet, aby tak učinili do konce srpna.
Vzhledem k tomu, že je o moje cvičení zvýšený zájem a příslušné místnosti nejsou nafukovací (neměli byste kde sedět na písemku), je nutné se na cvičení zapsat pomocí Grupíčku.
Vždy se snažte, ať je z řešení poznat (raději to tam napište), co děláte, jak to děláte (které věty jste použili apod.), proč to děláte a kolik to vyšlo. Výsledky je třeba zdůvodnit, i když to není explicitně napsáno. Samotný výsledek má mizivou bodovou hodnotu.
| Číslo příkladu | Zadání | Body |
|---|
| 1.1 | Student udělá určitou chybu v příkladu 1.1 s pravděpodobností p. Tato pravděpodobnost je samozřejmně zcela nezávislá na tom zda tuto chybu udělají ostatní studenti, neboť studenti řeší domácí úkoly samostatně!!!
a)Adam a Bedřich tento příklad řeší, jaká je pravděpodobnost, že nikdo z nich chybu neudělá?
b)Jaká je střední hodnota počtu udělaných chyb řeší-li příklad všech n studentů z kruhu?
c)Víme-li, že jeden konkrétní student z kruhu tuto chybu udělal (nechci jmenovat), jaká je pravděpodobnost, že ji udělá ještě někdo další?
Řešte vždy nejdříve obecně a pak pro p = 0,1 a n = 20.
| 3 |
| 1.2 | Ve hře štastných deset jsou postupně z osudí náhodně taženy míčky s čísly 1,2,...,80. Vytažené míčky se už do osudí nevracejí.
a)Jaká je pravděpodobnost, že součin prvních dvou tažených čísel bude 16?
Označme jev z bodu a) jako jev A. Označme jako jev B, že jako první byl tažen míček s číslem 1. B' je doplněk B. Určete podmíněnou pravděpodobnost jevu A,
b)nastal-li jev B, tj. P(A|B).
c)nenastal-li jev B ,tj. P(A|B').
| 3 |
| 1.3 | Podobně jako v předchozím příkladě losojume míčky, tentokrát jen s čísly 1 až 6. Určete střední hodnotu součinu čísel na prvních dvou vytažených míčcích.
Hint: možnosti, které nenastávají, do součtu přičtěte a zase odečtěte.
| 2 |
| 2.série |
| 3.série |
| 4.1 | Kombinatoricky dokažte, že pro každé 0 <= k <= (n-1)/2 platí, že počet (k+1)-prvkových podmnožin n-prvkové množiny je aspoň počet k-prvkových podmnožin n-prvkové množiny (t.j. dokažte to bez využití toho, že příslušný počet podmnožin je n! /(k!(n-k)!). | 2 |
| 4.2 | Nechť X = {-23, -22, ..., 186} a nechť množina Y vznikne z množiny X tak, že z ní vyškrtáme všechny násobky čísel 6,9,15,18,24,30. Zjistěte, kolik prvků obsahuje množina Y. | 2 |
| 4.3 | O přirozeném čísle n řekneme, že je bezčtvercové pokud n není dělitelné číslem k2, pro žádné k ≥ 2 přirozené. Zjistěte kolik bezčtvercových čísel se nachází v intervalu 134, 135, ..., 522. | 3 |
| 5.1 | Pomocí vhodné kombinatorické interpretace a použitím principu inkluze a exkluze spočítejte následující sumu pro n,m,j přirozené a n ≤ j ≤ m + n (t.j. vyjádřete tuto sumu jako nějaký výraz, který už dále nebude obsahovat sumu)
 | 4 |
| 5.2 | Spočítejte počet surjektivních ("na") zobrazení z množiny X do množiny Y, kde |X| = n a |Y| = m (a příslušný výraz se pokuste upravit do co nejjednoduššího tvaru). | 3 |
| 5.3 | Kolika způsoby můžeme rozsadit n manželských párů okolo kruhového stolu s 2n židlemi tak, aby žádný manželský pár neseděl vedle sebe. | 3 |
| 6.1 | Najděte vytvořující funkce posloupností {12, 22, 32, 42, ...}, {1,-1, 2,-2, 3,-3, 4,-4, ...} a { 1/1 , 1/2, 1/3, 1/4, ...}. | 2+2+2 |
| 6.2 | Pomocí vytvořujících funkcí najděte explicitní vzorec pro sumu 12+ 22 + 32 + .. + n2. | 3 |
| 6.3 | Najděte koeficient u x^3 ve výrazu: ((3-4x)3/2)/(1-x). | 2 |
| 7.1 | Uvažme posloupnost, v níž druhý a každý další člen je průměrem předchozích dvou, tj. pro n ≥ 2 platí an = (an-1 + an-2)/2. Určete limitu této posloupnosti v závislosti na členech a0 a a1. | 3 |
| 7.2 | Pro posloupnost platí a0 = 1 a pro všechna n ≥ 0 je an+1=2an+3. Pomocí vytvořujících funkcí určete vzorec pro n-tý člen této posloupnosti. | 3 |
| 7.3 | Kolika způsoby lze nakoupit 100 balení pseudoefedrinu ve čtyřech lékárnách, mají-li v nich na skladě 64, 48, 29 a 17 balení. Vyjde-li Vám součet (nejvýše patnácti) součinů kombinačních čísel, nemusíte (ale můžete) výsledné číslo dopočítávat. | 2 |
| 7.4 | Pro všechna n ≥ 0 spočítejte počet pn posloupností nul a jedniček délky n neobsahujících dvě nuly těsně za sebou. Cílem je vzorec v uzavřeném tvaru. | 2 |
| 8.1 | Určete počet zn platných závorkování s n levými závorkami. Závorkování je nějaká posloupnost levých a pravých závorek a je platné, pokud obsahuje stejně levých jako pravých a v každém prefixu aspoň tolik levých jako pravých. Např. ((())()).
Hint: Catalanova čísla | 2 |
| 8.2 | Určete počet un úplných uzávorkování výrazu a1^a2^a3^a4^...^an. Takové uzávorkování přesně určuje v jakém pořadí bude výraz vyhodnocován a každá operace ^ v něm má právě dva operandy. Pořadí operandů v zápise neměníme. Tj. pro a1^a2^a3^a4 jsou úplná uzávorkování a1^((a2^a3)^a4), (a1^a2)^(a3^a4), nebo (a1^(a2^a3))^a4, ale nikoliv třeba (a4^a2)^(a3^a1) a uzávorkování a1^((a2^a3)^a4) a ((a1)^(((a2)^(a3))^(a4))) jsou stejná.
Všimněte si, že, vezmeme-li z výrazu pouze závorky, dostaneme pro první a třetí uzávorkování stejné závorkování (()), takže se nejedná o stejnou úlohu jako 8.1.
Hint: Catalanova čísla
| 3 |
| 8.3 | Kolik je způsobů, jak rozdělit pravidelný n-úhelník na trojúhelníky pomocí n-3 neprotínajících se úhlopříček?
Hint: Catalanova čísla | 3 |
| 8.4 | Popište všechny dvojice (X,L) takové, že X je neprázdná konečná množina, L je podmnožina P(X) = 2X a platí
- (P1) pro každé dvě různé p,q z L má jejich průnik velikost právě 1
- (P2) pro každé dva různé x,y z X existuje právě jedna p z L taková, že x i y náleží p
- (non P0) Pro každé čtyři různé u,v,w,x z X existuje p z L tak, že |{u,v,w,x} průnik p| je aspoň tři.
Využijte ekvivalentních tvrzení dokázaných na cvičení. | 2 |
| 9.1 | Ukažte, že souvislý d-regulární (d ≥ 2) bipartitní graf je
- a)hranově, nebo
- b)vrcholově
2-souvislý. (Ukažte a) nebo b).) | 2/3 |
| 9.2 | Určete vrcholovou souvislost grafu Kn-Cn,tj. úplného grafu na n vrcholech, z nějž byly odebrány hrany jedné Hamiltonovské kružnice. | 2 |
| 9.3 | Nechť Qn (n ≥ 1) je orientovaný graf (n-dimenzionální krychle) s množinou vrcholů {0,1}n takový, že z vrcholu u vede
orientovaná hrana do vrcholu v právě, když se příslušné vektory
liší pouze na jediném místě a na tom má vrchol u nulu a vrchol v jednotku. Položme kapacitu každé hrany 1 a z = (0,0,..,0), s = (1,1,..,1).
Najděte - a)maximální celočíselný tok v této síti
- b)maximální tok, který je na všech hranách nenulový.
| 2+3 |
| 10.1 | Dokažte, že graf na n vrcholech s minimálním stupněm d ≥ (n-1)/2 je hranově d-souvislý. | 3 |
| 10.2 | Pro n > 3 vezměme n navzájem různých množin A1,A2, . . . ,An, každou o velikosti
n-3, jejichž sjednocením je množina X velikosti n. Dokažte, že A1,A2, . . . ,An má systém různých reprezentantů. | 3 |
| 10.3 | Dokažte, že CNF-formule, která má v každé klausuli právě n proměnných a každá proměnná se vyskytuje nejvýše n-krát (tzv. (n,≤n)-SAT) je vždy splnitelná.
CNF-formule je logická formule ve formě konjunkce (logického součinu) klauzulí, přičemž každá klauzule je disjunkcí (logickým součtem) literálů, což jsou buďto proměnné nebo jejich negace.
Formule je splnitelná pokud je možno dosadit za proměnné pravdivostní hodnoty tak, aby celá formule byla pravdivá.
| 4 |
| 11.1 | Hrany úplného grafu na n vrcholech (aspoň dvou) jsou obarveny 2 barvami (červeně a modře). Ukažte, že v grafu existuje jednobarevná kostra. | 2 |
| 11.2 | Rozhodněte, zda platí: Pro každé obarvení množiny mřížových bodů v rovině (bodů s celočíselnými souřadnicemi) pomocí 2009 barev,
- a) existuje množina aspoň 2009 celých čísel X, taková, že všechny prvky X x X jsou obarveny stejnou barvou.
- b)existují dvě množiny aspoň 2009 celých čísel X a Y, takové, že všechny prvky X x Y jsou obarveny stejnou barvou.
| 2/4 + 2/4 |
| 11.3 | Rozhodněte zda platí: Každý dostatečně velký souvislý graf obsahuje indukovaný podgraf s
- a) 15i hranami.
- b) 27i hranami.
| 6+2 |
|
| 11.4 | Spočítejte s_n, počet koster žebříku Z_n. Žebřík Z_n je graf, který vznikne
ze dvou cest na n vrcholech tak, že spojíme odpovídající si vrcholy n příčkami. Vypadá jako žebřík. Cílem je vzorec v uzavřeném tvaru. | 5 |
| 11.5 | Spočtěte počet koster grafu K_m,n bez jedné hrany. | 4 |