Stránka 1 z 2

2. sada domácich úloh

PoslaťNapísal: Uto Mar 16, 2010 10:59 pm
od FeroG
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.

PoslaťNapísal: Str Mar 17, 2010 1:59 pm
od PainMaster
blbe dokazy...
:x

PoslaťNapísal: Str Mar 17, 2010 2:05 pm
od FeroG
PainMaster píše:blbe dokazy...


Ako interpretovat vyraz "blbe"?

PoslaťNapísal: Str Mar 17, 2010 2:18 pm
od PainMaster
FeroG píše:Ako interpretovat vyraz "blbe"?


Nieco ako vec nevyhovujuca MNE....zbytocnost, strata casu atd...

PoslaťNapísal: Str Mar 17, 2010 2:45 pm
od FeroG
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

PoslaťNapísal: Str Mar 17, 2010 4:22 pm
od johny
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ť :)

PoslaťNapísal: Str Mar 17, 2010 4:58 pm
od Aries
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 :)).

PoslaťNapísal: Str Mar 17, 2010 5:13 pm
od FeroG
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).

PoslaťNapísal: Str Mar 17, 2010 7:32 pm
od Aries
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

PoslaťNapísal: Str Mar 17, 2010 7:42 pm
od FeroG
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).

PoslaťNapísal: Str Mar 17, 2010 7:44 pm
od Aries
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 :)

PoslaťNapísal: Str Mar 17, 2010 7:47 pm
od FeroG
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... :-)

PoslaťNapísal: Str Mar 17, 2010 7:57 pm
od Aries
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 :)

PoslaťNapísal: Str Mar 17, 2010 11:56 pm
od PainMaster
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

PoslaťNapísal: Štv Mar 18, 2010 12:37 pm
od johny
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).