12.6.2015 Jelínek

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: 12.6.2015 Jelínek

12.6.2015 Jelínek

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) n^{\sqrt{n}}, b) \binom{2^n}{n}, c) (3n)!
* 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 K_{m,n} (partity velikosti m a n vrcholů) je ... (nemusíte dokazovat). Kolik koster má graf K_{m,n}^{-} vzniklý z grafu K_{m,n} 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 22 = 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!

Nahoru