zkouška 20.6.2008, Valtr

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: zkouška 20.6.2008, Valtr

Re: zkouška 20.6.2008, Valtr

od Lukas Mach » 3. 6. 2009 16:22

R.U.R. píše:JJ, tohle se dá docela jednoduše ověřit v Mathematice - například

Kód: Vybrat vše

Series[(1 - x)/(1 + x)^3, {x, 0, 10}]
hodí prvních deset členů toho mnohočlenu, který odpovídá té posloupnosti...
Vzhledem k tomu, ze Mathematica neni ve vsech labech, tak bych jen doplnil odkaz na WA (viz "series expansion"):

http://www44.wolframalpha.com/input/?i= ... 1+%2B+x)^3

Popripade si clovek muze nainstalovat Sage (myslim, ze balicek sagemath v Debianu).

Re: zkouška 20.6.2008, Valtr

od R.U.R. » 1. 6. 2009 02:19

JJ, tohle se dá docela jednoduše ověřit v Mathematice - například

Kód: Vybrat vše

Series[(1 - x)/(1 + x)^3, {x, 0, 10}]
hodí prvních deset členů toho mnohočlenu, který odpovídá té posloupnosti...

Re: zkouška 20.6.2008, Valtr

od Jindra » 28. 5. 2009 19:43

Souhlasím s návštěvníkem, má to být (1-x) / (1+x)^3... :-)

Re: zkouška 20.6.2008, Valtr

od Návštěvník » 28. 5. 2009 17:06

Nemela by ta 3 byt takhle ?

3)
(1,1,...) ~ 1/(1-x)
(0,1,2,3,...) ~ x/(1-x)2 ... zderivováno + posunouto
(1,4,9,16,...) ~ (1+x)/(1-x)3 ... zderivováno podruhé //zde bylo (3-x)/(+-x)3
(1,-4,9,-16,...) ~ (1-x)/(1+x)3 ... substituce -x za x

Teda jestli uz nejse blbej a neumim derivovat.

zkouška 20.6.2008, Valtr

od Yawgmoth » 20. 6. 2008 16:16

Zadání:
1) Dokažte, že v každém vrcholově 2-souvislém grafu odlišném od C3 existuje hrana, jejíž kontrakce neporuší vrcholovou 2-souvislost. Je pravda, že dokonce kontrakce libovolné hrany v takovém grafu neporuší 2-souvislost?

2) Dokažte následující tvrzení: Pro každé přirozené číslo k existují přirozené číslo c a k-prvková množina M přirozených čísel takové, že pro každou dvojici a,b z M je číslo a + b + (a-b)12 - c dělitelné 333.

3) Urcete vytvorujici funkci pro posloupnost (1,-4,9,-16,25,-36,...).

4) Definujte tok. Definujte celočíselný tok. Zformulujte a dokažte větu o celočíselnosti.

_____________________________________

Můj názor + možné řešení:
nebylo důležité mít to dokonale, žádná velká technická znalost, stačilo upatlat vlastní slovní řešení...

1) a) podle ušatého lemmatu, ať už podle kterékoliv verze s tím, že buď kontrahujeme hranu na posledním přidaném uchu které má délku alespoň 2 (pokud takové neexistuje tak původní kružnice musela být větší než C3 a můžeme kontrahovat na ní), nebo v druhé verzi kontrahujeme libovolnou hranu vzniklou podrozdělením (tady je potřeba ukázat, že kontrakcí se nic nestane, že maximálně zanikne nějaká hrana přidaná podle ušatého lemma později -> i bez ní je graf 2-souvislý)
b) to pravda není, například čtverec (C4) s jednou úhlopříčkou, kontrakcí úhlopříčky vznikne cesta délky 3, která není 2-souvislá

2) oficiálně to bylo myšlené na Ramseyovu vícebarevnou větu (že to má být nějaká Ramseyova věta nám po cca 40 minutách bylo napovězeno) a to tak, že vrcholy Kn jsou přirozená čísla 1..n, hrany obarvíme 333 barvami tak, že barva hrany ab odpovídá (a + b + (a-b)12) mod 333. Z ramseyovy věty tedy existuje k-prvková jednobarevná množina, tu vezmeme a podle čísla barvy dopočítáme c.

Já jsem to takhle ale neřešil a alternativní řešení (které šlo odhadnout stylem kouknu a vidím) mi bylo uznáno za plný počet bodů:
M = {x|x = 333i, i přirozené, i<=k}, tj k-prvková množina násobků 333
c = 333, tj konstantní pro všechna k
a + b + (a-b)12 - c se tedy dá přepsat na 333m + 333n + (333m-333n)12 - 333 = 333(m+n-1+33311(m-n)12) ... m-n je celé číslo, na sudou mocninu přirozené, celá závorka je tedy také přirozená a po vynásobení 333 tedy dělitelná 333 :)

3)
(1,1,...) ~ 1/(1-x)
(0,1,2,3,...) ~ x/(1-x)2 ... zderivováno + posunouto
(1,4,9,16,...) ~ (3-x)/(1-x)3 ... zderivováno podruhé
(1,-4,9,-16,...) ~ (3+x)/(1+x)3 ... substituce -x za x

4) tok f: E->R0+, 1) pro každou hranu e f(e) <= c(e); 2) pro každý vrchol v mimo zdroj a stok je součet f(uv) přes všechny hrany uv roven součtu f(vu) přes vechny hrany vu
celočíselný tok: f: E->N0 + stejné podmínky

u věty jsem trošku vařil, ani jsem si nebyl jist zněním natož důkazem, ale uznáno bylo :-)
Pokud všechny kapacity celočíselné, pak existuje celočíselný maximální tok.
Dokážeme pomocí Ford-Fulkersonova algoritmu pro hledání maximálního toku, kde v tomto případě každá nalezená zlepšující cesta je celočíselná => zlepšující tok a zbytková kapacita taky. Navíc díky tomu algoritmus určitě doběhne, protože celková kapacita všech hran je konečná a každým krokem zlepšíme tok alespoň o 1.

Nahoru