od nikdo » 13. 6. 2015 12:41
Termín 12.6.2015 (Jelínek):
1) Porovnejte následující funkce podle rychlosti jejich růstu: [5 bodů]
a)
, b)
, c)
* ta první funkce byla trošku jinak, ale víceméně takhle
2) Zformulujte a dokažte König-Egerváryho větu o velikosti párování a vrcholového pokrytí. [10 bodů]
3) Definujte (n,k,d)-kód. Napište příklad (5,2,3)-kódu. [5 bodů]
4) Počet koster úplného bipartitního grafu (partity velikosti a vrcholů) je ... (nemusíte dokazovat). Kolik koster má graf vzniklý z grafu odebráním jedné hrany? [10 bodů]
Náznak řešení:
1) Buď pomocí horních a dolních odhadů funkcí (viz první cvikopřednáška), nebo analyticky přes limity (nevím, jestli uznával, ale asi jo).
2) Věta a důkaz z přednášky
(20. března).
3) Definice z přednášky
(15. května). Jako příklad (5,2,3)-kódu jsem si nějaký vymyslel (chce to trochu kreativity). Z definice je zřejmé, že takový kód C bude mít 2
2 = 4 kódových slov (vektorů) o délce 5. A každé dva se musí lišit v alespoň 3 bitech. Splňuje to například:
C={(1,1,1,1,1),(1,1,0,0,0),(0,0,1,1,0),(0,0,0,0,1)}
4) Viz přednáška
(3. dubna): věta o tom, kolik koster obsahujících jednu konkrétní hranu má úplný graf. Tedy výsledek je (počet koster celkem - počet koster s konkrétní hranou). Akorát pozor, protože na přednášce jsme to dělali pro úplný graf, tentokrát je to úplný bipartitní graf!
Termín 12.6.2015 (Jelínek):
[b]1) Porovnejte následující funkce podle rychlosti jejich růstu:[/b] [i][5 bodů][/i]
a) [latex]n^{\sqrt{n}}[/latex], b) [latex]\binom{2^n}{n}[/latex], c) [latex](3n)![/latex]
[i]* ta první funkce byla trošku jinak, ale víceméně takhle[/i]
[b]2) Zformulujte a dokažte König-Egerváryho větu o velikosti párování a vrcholového pokrytí.[/b] [i][10 bodů][/i]
[b]3) Definujte (n,k,d)-kód. Napište příklad (5,2,3)-kódu.[/b] [i][5 bodů][/i]
[b]4) Počet koster úplného bipartitního grafu [latex]K_{m,n}[/latex] (partity velikosti [latex]m[/latex] a [latex]n[/latex] vrcholů) je ... (nemusíte dokazovat). Kolik koster má graf [latex]K_{m,n}^{-}[/latex] vzniklý z grafu [latex]K_{m,n}[/latex] odebráním jedné hrany?[/b] [i][10 bodů][/i]
[line][/line]
Náznak řešení:
1) Buď pomocí horních a dolních odhadů funkcí (viz první cvikopřednáška), nebo analyticky přes limity (nevím, jestli uznával, ale asi jo).
2) Věta a důkaz z přednášky [i](20. března)[/i].
3) Definice z přednášky [i](15. května)[/i]. Jako příklad (5,2,3)-kódu jsem si nějaký vymyslel (chce to trochu kreativity). Z definice je zřejmé, že takový kód C bude mít 2[sup]2[/sup] = 4 kódových slov (vektorů) o délce 5. A každé dva se musí lišit v alespoň 3 bitech. Splňuje to například:
[i]C={(1,1,1,1,1),(1,1,0,0,0),(0,0,1,1,0),(0,0,0,0,1)}[/i]
4) Viz přednáška [i](3. dubna)[/i]: věta o tom, kolik koster obsahujících jednu konkrétní hranu má úplný graf. Tedy výsledek je (počet koster celkem - počet koster s konkrétní hranou). Akorát pozor, protože na přednášce jsme to dělali pro úplný graf, tentokrát je to úplný bipartitní graf!