Skusky

[bilbo]

Ahojte,
mohli by ste sem prosim napisat nejake dalsie reporty zo skusok?
Aby ludia, co este neboli ziskali trochu predstavu o tom, co sa od nich bude cakat.

Vopred dakujem.

[Isidor]

Ahojte,
mohli by ste sem prosim napisat nejake dalsie reporty zo skusok?
Aby ludia, co este neboli ziskali trochu predstavu o tom, co sa od nich bude cakat.

Vopred dakujem.

Hmmm podla SISu bol (okrem predterminu) len jeden termin a na nom 11 ludi....ale niekto by sa ozvat mohol

[Návštěvník]

Az teraz som si vsimol, ze vlastne este ziadne skusky neboli okrem predterminu. Ten jeden termin bola opravna zapoctova pisomka.
Takze si po skuske asi sam odpoviem na moj prispevok.

[Isidor]

Az teraz som si vsimol, ze vlastne este ziadne skusky neboli okrem predterminu. Ten jeden termin bola opravna zapoctova pisomka.
Takze si po skuske asi sam odpoviem na moj prispevok.

Hmmm...teda ja som tam nebol, ale...

TIN060 Algoritmy a datové struktury I, letní sem. 2004/2005 ZK
Datum: 2.6.2005 čtvrtek
Hodina: 9:00
Přihlašování od :
Škrt do: 31.5.2005
Zápis do: 31.5.2005
Místnost: S5 Malostranské nám. 25, 2. patro, projektor, počítač
Učitel: Čepek,O.
Kapacita: 20
Počet přihlášených: 11
Poznámka: ZK + náhradní zápočtová písemka (bez přihlašování)

[Hugo]

mam to z 2. ruky, ale na 2. terminu zkousek bylo

T(n) = T(n/3) + 3T(n/4) + 3n

AVLko a v nem je nejaka cesta z libovolneho vrcholu k listu. mas dokazat nebo vyvratit, ze pro vsechny klice vlevo, v ty ceste a vpravo od ni plati, ze vlevo < v ceste < vpravo.
Druhe bylo, mas graf a v nem vrchol u do nejz jde minimalne jedna hrana a i dochazi min jedna hrana. Dokaz nebo vyvrat, ze tento vrchol bude v DFS strome, kterej bude mit pokazdy aspon dva vrcholy..

[MyS]

T(n) = T(n/3) + 3T(n/4) + 3n

Hmm, ja jsem asi strasne hloupouckej...ale...kdyz pocitam to T(n), tak musim najit horni i dolni odhad, ktery je radove stejny, zejo (tj. T(n)=theta(N)??)? Muze nekdo dat tip, jak tohle pak teda resit, resp. jak to ma vyjit?

Jinak pro dvojku a trojku si myslim neplati+neplati ...?
A jeste neco...vite nekdo, jak probiha ustni cast? thx

[Návštěvník]

odhadnes pres Master Theorem - logaritmy jsou < 1, takze vyhraje 3n (d = 1) => Theta en

pak uz jen indukci dokazes, ze to tak je..kdyztak mrkni do zapisku, na prednasce delal prehledne a rozvlekle par prikladu;)

ty dalsi dva jsou opravdu ze, ne

[MyS]

No to sice jo, ale tady ty rekurzivni volani jsou dve a jinych "pomeru", tudiz je nemuzu primo sepsat dohromady. takze pro horni odhad muzu sjednotit jako 4*T(n/3) a pro dolni 4*T(n/4). Problem je, ze odhady jsou pak radove ruzne (n*logn pro dolni a rekneme n^2 pro horni, coz neni theta).

[Hugo]

Ja bych rekl, ze beres to nejvetsi, nic nesjednocujes (ale to je z me hlavy) - pote vyhraje to 3n -> T(n) = Theta n a s tim ti to take hrave vyjde..

[MyS]

Hmm, to je divny. Prece kdybych pak mel neco jako 99*T(n/100)+....+1*T(n/2)+3n, tak to neni linearni...nebo jo:-)? Kazdopadne kdyz jsem zkousel substitucne pro ten puvodni pro horni odhad n*logn, tak mi to vychazelo, ze je to moc malo...nezkousel to taky nekdo hardcorove substituci?

[Tuetschek]

Me to vychazelo ze n^2 je moc a n*log(n) malo. Coz znamena ze jsem to pravdepodobne zvoral . Kdybyste to nekdo byl schopny spocitat, ozvete se.

[Hugo]

zacinas me privades do nejistoty, ale dle me to linearni je:)

kdyz tam vsude nahazes n, tak je to urcite mensi nez 103n a vetsi nez 53n a s tim si uz konstanta pohraje..

[Hugo]

zadani ze vcerejska:)

1. 2T(n/5) + T(n/2) + n - odhad Thety a dokazat substitucni metodou - vysledek - linearni (priklad zadarmo)

2. V Rusku vede jednim smerem ropovod (predstavte si primku, kolmou na osu x) a okolo je hafo vrtu, pricemz ropovodne rameno vedouci k vrtu muze byt napojeno k ropovodu jenom v pravem uhlu, ukolem je alg., ktery urci souradnice na ose x, kterymi ma vest ropovod, aby ramena k vrtum byla dohromady co nejkratsi.. - reseni pres median

3. je orientovany graf a mate nalezt co nejrychlejsi alg., ktery zjisti, zda graf je ?polosouvisly?, proste v grafu musi vest mezi 2 lib. vrcholy alespon jedna orientovana cesta - reseni pres SSK (pak jeste nejak sikovne pospojovat)

[Hugo]

to zadani je z 23.6.