Zkouška 11.6.2013

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
cvutak
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 12. 6. 2013 11:55
Typ studia: Informatika Bc.

Zkouška 11.6.2013

Příspěvek od cvutak »

Na 4 příklady jsme měli hodinu - docela málo, podle mě

- 10b Počet hran v grafu bez C_4, důkaz
- 10b \delta (G) budiž nejmenší stupneń vrcholu v G. Dokažte, že pokud \delta (G) \geq \frac{|V|}{2}, pak je graf hranově \delta (G) souvislý
- 5b Vytvořující funkce pro -1, 3, -5, .... (-1)^n(2n-1), nebo možná 1, -3, 5, ...
- 5b Porovnat růst nějakých funkcí, myslím \binom{4n}{2n}, n^{n/2}, 3^{3n}

Protože to dopadlo mizerně, byla trojka za 10, jinak je polovinu. Většina lidí šla na ústní, dosažené maximum bylo 20b

Řešení úloh:
- standard podle Kapitol, za formulaci a hrubou myšlenku jsem dostal asi polovinu
- dá se dělat třeba tak, že si vezmete řez veliký \delta (G) - 1 a koukáte se, kolik hran vlastně vychází z komponenty menší než \frac{|V|}{2}
- jednoduché řešení je vzít si \frac{1}{1-x}, zderivovat, posunout a sečíst se sebou sama, tím máte lichá čísla. Pak dosadit -x za x a doladit
- nejsem si jistý zadáním, nebudu se v tom šťourat, ale stačilo převést binomiál na exponenciální odhad
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“