Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Visestruka stabla, gdje mogu saznati vise o tome?

[es] :: Art of Programming :: Visestruka stabla, gdje mogu saznati vise o tome?

[ Pregleda: 2521 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

modus_ponens

Član broj: 75014
Poruke: 71
*.dynamic.sbb.co.yu.



+2 Profil

icon Visestruka stabla, gdje mogu saznati vise o tome?21.08.2007. u 11:48 - pre 202 meseci
Zdravo,

Imam problem sledece tematike:

Potrebno mi je da realizujem simulator digitalne elektricne mreze, bez petlji. Koje elemente mreza sadrzi i kako su medjusobno povezani, to diktira ulazni fajl. Posto kola imaju svoje kasnjenje, ne mogu problem rijesiti jednostavnom linearnom listom. Potrebno mi je da saznam sto vise o tome kako se realizuju visestruka stabla (cvorovi imaju u opstem slucaju proizvoljno mnogo nasljednika, sto zavisi od ulaznog fajla, naravno). Ideja koju imam je da propagiram signal od generatora (najstarijih elemenata u stablu) pa sve do krajnjih elemenata u mrezi.

Gdje mogu da saznam o strukturama koje mogu ovo da realizuju (visestruka stabla)? Prelistao sam teme ne Elitesecurity (izvinjavam se ako mi je promaklo),probao sam na Google i Wiki, ali nisam nasao zeljeno.

Konkretno, program realizujem u C++, mada to i nije bitno.

Kako nemam dovoljno znanja iz algoritama, svaka pomoc u vidu reference materijal koji bi mi mogao koristiti,bila bi dobrodosla.

 
Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*



+1 Profil

icon Re: Visestruka stabla, gdje mogu saznati vise o tome?21.08.2007. u 12:03 - pre 202 meseci
Probaj da pogledas algoritme za stabla. Nisam upoznat da se koristi termin visestruka stabla.

Ukoliko je u pitanju struktura koja ima osnovni node (cvor) i dalje se grana (svaki cvor moze proizvesti
proizvoljan broj grana) onda je to stablo.

Poseban oblik stabla je binearno stablo (mozda te je to zbunilo) kod kog svaki cvor daje tacno dve grane.

Ukoliko pak imas slucaj da postoji vise "pocetnih" cvorova onda nije u pitanju stablo nego neka vrsta grafa
(bez obzira sto nemas petlje). U tom slucaju pogledaj malo teoriju grafova i algoritme za grafove.

Drvoidne strukture se mogu implementirati na razne nacine.

Jedan od najjednostavnijih nacina je bas sa listama, odnosno svaki cvor drzi listu cvorova sa kojim je povezan (to su
zapravo grane).
 
Odgovor na temu

MarkoBalkan

Član broj: 141124
Poruke: 1624
*.adsl.net.t-com.hr.



+19 Profil

icon Re: Visestruka stabla, gdje mogu saznati vise o tome?21.08.2007. u 19:57 - pre 202 meseci
imao sam jedan bezvezan kolegij na faksu, a zvao se "primjena racunala u elektroenergetici", totalno dosadan predmet, a radilo se o programima za analizu mreza(cvorovi, naponi itd).
program je pisan u Pascalu.
mislim da imam negdje taj program.
ako ti sta pomaze.
 
Odgovor na temu

modus_ponens

Član broj: 75014
Poruke: 71
*.dynamic.sbb.co.yu.



+2 Profil

icon Re: Visestruka stabla, gdje mogu saznati vise o tome?21.08.2007. u 20:06 - pre 202 meseci
Kao prvo, hvala na odgovoru.

U pravu si, visestruka stabla zapravo i ne postoje (to je "interni" termin koji sam cuo od jednog racunarca) i ovo sto meni zapravo treba, jeste neka vrsta grafa(dobro si shvatio,ima vise polaznih cvorova, a u opstem slucaju cvor moze imati proizvoljno mnogo nasljednika). E sad, buduci da nisam racunarac, pogledao sam neka predavanja sa predmeta Algoritmi i Strukture Podataka, i vidim da meni za moj problem najbolje odgovara formiranje jednog takvog grafa, i obrada po "sirini".

Mozes li da me uputis na neki konkretan sample code, da vidim kako se takva struktura implementira?

Doduse, mislim da bi se ovo dosta dobro dalo rijesiti i Composite Design Patternom, jer mi je jedna od stavki u zadatku i to da je pozeljno da se glavna mreza moze sastojati i od podmreza (a podmreze, opet, od drugih podmreza i osnovnih elemenata kola).

Moze neki prijedlog, da li sam krenuo dobrom putanjom, ili ne...?

Ovakav zadatak je relativno velik zalogaj (za mene), te su savjeti dobrodosli...

 
Odgovor na temu

lukeguy
Novi Sad

Član broj: 46545
Poruke: 470
*.net
Via: [es] mailing liste



+8 Profil

icon Re: Visestruka stabla, gdje mogu saznati vise o tome?24.08.2007. u 16:28 - pre 202 meseci
Mi smo na faksu ove godine radili nešto slično, s tim što je simulator bio opcioni deo zadatka. Koliko sam razumeo one koji su i to uradili, radili su samo logičku simulaciju (dakle bez računanja kašnjenja signala koje uvode pojedine komponente, tj. uzima se da je kašnjenje nula), jer je mnogo jednostavnija da se implementira od fizičke. U svakom slučaju za oba slučaja postoje već poznati algoritmi.

Ovaj za logičku se svodi na to da obeležiš sve komponente redim brojevima i to tako da ih obeležavaš po redosledu po kojem će vrednosti svih ulaznih signala tih komponente biti poznati u toku vremena. Znači, uvek prvo obeležavaš sve ulaze u tvom kolu (izvore signala), recimo od 1 do 4 (jer vrednost signala na izvoru je uvek poznata). Zatim tražiš sve komponente čiji su ulazi vezani na ove tvoje izvore, odnosno komponente čiji su svi ulazi u tom trenutku poznati. Pa njih obeležavaš dalje (npr. 5 i 6). Onda ideš na sledeći nivo (tj. tražiš dalje koje komponente imaju sve definisane ulaze) i to ponavljaš dok ne dođeš do kraja. Simulaciju onda obavljaš tako što ideš od 1 do kraja i za svaku komponentu računaš izlaz po redu. Ovakav algoritam ti sam po sebi garantuje da ćeš u trenutku kada određuješ vrednost logičke funkcije komponente 9 sigurno znati vrednosti svih njenih ulaznih signala (koji su ti i potrebni da odrediš vrednost te funkcije).

Na žalost, za povratnu petlju i fizičku simulaciju se više ne sećam kako je išla procedura. Za fizičku isto može ovako da se numeriše, ali moraš uzeti u obzir i vreme propagacije, tj. da li će ulazne vrednosti biti spremne u tom trenutku. Izguglaj malo na temu simulacionih algoritama, sigurno ćeš naći ove algoritme.
 
Odgovor na temu

modus_ponens

Član broj: 75014
Poruke: 71
*.dynamic.sbb.co.yu.



+2 Profil

icon Re: Visestruka stabla, gdje mogu saznati vise o tome?24.08.2007. u 19:10 - pre 202 meseci
Evo u cemu je stvar:

Ono sto se sigurno zna, jeste da generatore treba prvo prozvati, i to moze i proizvoljnim redoslijedom. A za ostale elemente, potrebno je tacno odrediti red elementa u kolu (logicki red, definisan kao u ORT-u). Dakle, po definiciji, generatori bi imali red 1, i prozivali bi se prvo oni. Medjutim, kola koja su vezana na generatore, ne moraju neposredno da imaju red 2(tj.ne znaci da ako su vezani za generator moraju da se odmah poslije generatora prozovu), jer im drugi ulaz moze biti zakacen na izlaz nekog prethodnog elementa, koje nije generator.

Da ilustrujem kao primjer uvezanosti elemenata (-> znaci "povezan je sa"),npr.: "Generator1"->"dvoulazno I kolo(ulaz1)" , dok istovremeno "Generator2"->"Invertor"->"dvoulazno I kolo(ulaz2)". Drugim rijecima, generatore 1 i 2 prozivam prvo, sigurno, ali onda moram prozvati prvo invertor(on je reda 2), pa onda tek "I kolo", jer je ono ipak reda 3, a ne reda 2(bas zbog drugog ulaza,iako je jednim ulazom vezano za gen1). Ovakav redoslijed prozivanja sigurno omogucava ispravnu simulaciju, pod uslovom da je naravno, kolo bilo dovedeno u definisano stanje po ukljucenju, ali to su vec finese...

Meni je sva poteskoca u odredjivanju algoritma koji ce mi precizno odrediti red svakog elementa kola, na osnovu ulaznog fajla. Kad bih se s tim iskobeljao, bilo da ima kasnjenje ili ne, bilo bi maltene pravolinijski ...

Metod kada nema kasnjenja moze i da se realizuje na "grubu silu" - ubace se svi elementi u listu, cak se ni ne pazi ko se prvo proziva, ali ukoliko se (za fiksiran vremenski trenutak) vrijednost bilo kog izlaza elementa promijenila, treba ici ponovo kroz listu. Ja sam probao da ovako implementiram i sa kasnjenjem, dodajuci samo koncept "zakazivanja dogadjaja", ali nisam mogao izbjeci pojavu laznih dogadjaja, ukoliko ne bih tacno znao kojim redoslijedom trebam prozivati elemente.

Dakle, mreza nema povratnih petlji (sa nekog izlaza, na ulazi istog tog kola, npr.), ali ima "najkomplikovaniji" slucaj koji je objasnjen, gore, u pasusu 2 :)

Poenta je sto sam ja krenuo ovom direkcijom , a mozda ima i boljih nacina razmisljanja, ipak OOP nudi dosta sarolikih mogucnosti, a ako imas neku idejicu jos, slobodno kazi.

Ipak, hvala na trudu i misljenju,cijenim to :) !
 
Odgovor na temu

lukeguy
Novi Sad

Član broj: 46545
Poruke: 470
*.smin.sezampro.yu.



+8 Profil

icon Re: Visestruka stabla, gdje mogu saznati vise o tome?24.08.2007. u 22:47 - pre 202 meseci
mislim da sam ti dao algoritam. prvo moraš numerisati sve komponente po ovom principu koji sam ti objasnio (ovo je faza kompajliranja). znači nešto tipa vrtiš petlju sve dokle nije određen redni broj svih komponenti, a čim za neku komponentu odrediš da je "spremna", baciš je na kraj liste spremnih. kada ovo uradiš samo ideš kroz listu i računaš logičke vrednosti (faza simulacije).

e sad, komponente moraš uvezati u nekakvu dvostruko spregnutu strukturu, a to radiš u toku parsiranja tog tvog ulaznog fajla. dakle, za svaku komponentu vezuješ listu njenih prethodnika (ulaza) i sledbenika (izlaza, verovatno samo jedna komponenta). a kad proveravaš da li je neka komponenta "spremna" proveriš da li su spremni svi njeni prethodnici. ja se na žalost ne sećam kako su moje kolege implementirale ovu strukturu, ali ako uspem da dođem do njihovog primera, mogu ti javiti.
 
Odgovor na temu

[es] :: Art of Programming :: Visestruka stabla, gdje mogu saznati vise o tome?

[ Pregleda: 2521 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.