2. sada domácich úloh

Moderátor: FeroG

<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Uto Mar 16, 2010 10:59 pm

2. sada domácich úloh

Keďže mnohí sa už pustili do riešenia úloh 2. sady, jeden komentár vychádzajúci z dnešného cvičenia k úlohe na overenie, či je strom binárnym vyhľadávacím stromom.

Ak zrealizujete inorder prechod BVS dostanete utriedenú postupnosť hodnôt.
Tvrdenie: Inorder prechod BVS je utriedená postupnosť.
Dôkaz indukciou na výšku stromu. Pre strom s výškou 0 je tvrdenie zrejmé (máme len 1 uzol - koreň). Nech T je strom s výškou h. Ľavý a pravý podstrom koreňa stromu T sú BVS (viď definícia) výšky nanajvýš h-1. Preto splňajú indukčný predpoklad. Inorder postuposť stromu vyzerá takto: Inorder(lavy podstrom), koren, Inorder(pravý podstrom). Z IP sú postupnosti Inorder(lavy podstrom) a Inorder(pravý podstrom) utriedené. Z definície BVS máme, že každá hodnota v Inorder(lavy podstrom) je menšia ako hodnota v koreni a každá hodnota v Inorder(pravý podstrom) je väčšia ako hodnota v koreni. Preto Inorder(T) je utriedená postupnosť.

Prirodzená otázka je, či platí opačná implikácia: Ak výsledkom inorder prechodu binárnym stromom je utriedená postupnosť, potom binárny strom je BVS.

Ak vaše riešenia úlohy jeBVS budú stavať na niečom inom, než je definícia, treba ako súčasť riešenia pridať dôkaz tvrdenia, na ktorom sa stavia.
<<

PainMaster

Príspevky: 689

Registrovaný: Uto Okt 06, 2009 12:50 pm

Bydlisko: 3.Kanal,4.Chodba

Poslať Str Mar 17, 2010 1:59 pm

blbe dokazy...
:x
We weren't born to follow
You gotta stand up for what you believe!

Ps: Za gramatiku ma neopravovat! Dakujem!
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 17, 2010 2:05 pm

PainMaster píše:blbe dokazy...


Ako interpretovat vyraz "blbe"?
<<

PainMaster

Príspevky: 689

Registrovaný: Uto Okt 06, 2009 12:50 pm

Bydlisko: 3.Kanal,4.Chodba

Poslať Str Mar 17, 2010 2:18 pm

FeroG píše:Ako interpretovat vyraz "blbe"?


Nieco ako vec nevyhovujuca MNE....zbytocnost, strata casu atd...
We weren't born to follow
You gotta stand up for what you believe!

Ps: Za gramatiku ma neopravovat! Dakujem!
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 17, 2010 2:45 pm

PainMaster píše:....zbytocnost, strata casu atd...


Práve o tom je computer science (a to je to, čím sa má líšiť "computer science" informatika od informatík na technických školách). Tvorca algoritmu by mal vedieť jeho fungovanie podložiť aj inak než len tým, že si myslí, že je to dobré a na všetkom, čo skúšal to fungovalo.

Aj Intel si myslel, že formálne dôkazy sú nanič, kým neprišlo toto: http://en.wikipedia.org/wiki/Pentium_FDIV_bug A teraz to tam vyzerá takto: http://www.cl.cam.ac.uk/~jrh13/slides/lics-22jun03.pdf
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Str Mar 17, 2010 4:22 pm

PainMaster píše:blbe dokazy...
:x


FeroG píše:Ak vaše riešenia úlohy jeBVS budú stavať na niečom inom, než je definícia, treba ako súčasť riešenia pridať dôkaz tvrdenia, na ktorom sa stavia.


Môžeš priamo "implementovať definíciu". Tuším v zadaní domácej úlohy nie je žiadna požiadavka na časovú zložitosť :)
E-mail/Jabber: jan[zavináč]jergus.eu
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Mar 17, 2010 4:58 pm

Podla definicie je to najlahsie aj najrozumnejsie, vyslo mi to tak na 5-6 riadkov kodu bez ziadneho vyrazneho zamyslania sa... Ani nevidim dovod preco to pisat inak (jedine ze by si chcel byt prudko originalny :)).
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 17, 2010 5:13 pm

Ano, v zadani pri tejto ulohe nie je obmedzenie na casovu zlozitost. Teda ist podla definicie je ta najlahsia a najrozumnejsia cesta. Len doplnim, ze bude asi aj nejaku tu pomocnu metodu treba vyrobit (v zavislosti od pouziteho algoritmu).

Poznamka pre "pokrocilych": Riesenie podla definicie ma casovu zlozitost O(n^2) a pamatovu O(h), kde h je vyska stromu (ak zaratavame do pamatovej zlozitosti pamat pouzitu callstackom). Pri inej implementacii vyuzivajucej iste fakty (ktore musia byt dokazane), je mozne overenie zrealizovat v case O(n) s pamatou O(h).
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Mar 17, 2010 7:32 pm

Tak som nad tym algoritmom trochu porozmyslal, kedze O(n^2) je fuj :) Zda sa, ze podla definicie s uvedomenim si jedneho zrejmeho faktu (bez potreby dokazu) to ide v O(n) s pamatovou narocnotou O(1). Sice ta casova mozno bude o trochu horsia (nieco*n) ako u "nedefinicneho" algoritmu, ale kazdopadne to ide linearne. Teraz mi uz len ostava dufat, ze som niekde opat nespravil blbu chybu :D
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 17, 2010 7:42 pm

Ano, mas pravdu. S vyuzitim ineho faktu to ide naozaj spravit bez potreby dokazu v case O(n). Pojde to trochu na ukor estetiky kodu. Avsak urcite pamat nebude O(1).
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Mar 17, 2010 7:44 pm

Pravda, prave som isiel napisat, ze pamat je tiez O(n)... Nejak som zabudol, ze ked metoda vola dve metody, tak tie udaje v pamati sa tiez musia zdvojnasobit. To bude tym nadsenim z vylepsenia vlastneho algoritmu :)
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 17, 2010 7:47 pm

Nie tak celkom. V pamati je vzdy stale len jedna vetva stromu volani (vid prva prednaska). Ak si metoda vytvara O(1) lokalne premenne, tak pri stromovych algoritmoch, kde je max. hlbka rekurzivneho vnorenia O(h), to vedie k pamati O(h).

Zaujimalo by ma, ako moze tuto vzajomnu diskusiu vnimat nezainteresovany divak... :-)
<<

Aries

Príspevky: 379

Registrovaný: Pia Jan 30, 2009 1:26 pm

Bydlisko: 127.0.0.1

Poslať Str Mar 17, 2010 7:57 pm

Eeeh, musim po sebe citat prispevky... Chcel som len povedat, ze pamatova narocnost nebude konstantna, a zo zvyku som tam hodil mudru hlasku a pismeno n. Ako inak, upne od veci :)
P.S: otazne je, ci to tu vobec niekto iny este cita :)
Vasnivy pestovatel binarnych stromov a opravar Turingovych strojov na polovicny uvazok.
"Problem citatov najdenych na internete je taky, ze si nikdy nemozete byt isti ich autenticitou" Abraham Lincoln
<<

PainMaster

Príspevky: 689

Registrovaný: Uto Okt 06, 2009 12:50 pm

Bydlisko: 3.Kanal,4.Chodba

Poslať Str Mar 17, 2010 11:56 pm

FeroG píše:Zaujimalo by ma, ako moze tuto vzajomnu diskusiu vnimat nezainteresovany divak... :-)


prejdem to ocami a dufam ze raz ked sa budem citit zainteresovany tak sa k tomu vratim...pohlad nezainteresovaneho divaka:D
We weren't born to follow
You gotta stand up for what you believe!

Ps: Za gramatiku ma neopravovat! Dakujem!
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Štv Mar 18, 2010 12:37 pm

FeroG píše:Riesenie podla definicie ma casovu zlozitost O(n^2) a pamatovu O(h), kde h je vyska stromu (ak zaratavame do pamatovej zlozitosti pamat pouzitu callstackom).


Pre vyvážené stromy dokonca Theta(n log n), je to riešenie rekurencie T(n) = 2T(n/2) + n (2T(n/2) za zavolanie sa na oboch synov, n za overenie, či vľavo sú menšie a vpravo väčšie hodnoty).

Alebo intuitívne: Na hodnotu každého z n vrcholov sa pozrieme práve raz pri spracúvaní každého z jeho predkov, ktorých je O(log n).

A s vhodným uložením stromu by sa to snáď dalo aj v O(1) pamäti (nie rekurzívne), ale na tom asi veľmi nezáleží, keďže samotný strom aj tak zaberie Omega(n) pamäti (n >= h).
E-mail/Jabber: jan[zavináč]jergus.eu
Ďalší

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 1 hosť

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.