☰

» »

Za programerske teoretike

Za programerske teoretike

Dzanko ::

Pozdravljeni,
hvalažen bom, če mi kdo odgovori na sledeče trditve in jih podkrepi tudi z utemeljitvijo.

Slkad deluje hitreje od vrste. DA/NE
V tabelo lahko vrinemo podatek hitreje kot v polje. DA/NE
Namesto sklada lahko vedno uporabimo tudi seznam. DA/NE
Iskanje po tabeli preišče vse elemente, po drevesu pa ne. DA/NE
Tabela dostopa do podatka hitreje kot seznam. DA/NE
Zgoščena tabela išče hitreje kot seznam. DA/NE
Linearno preverjanje je najhitrejši način reševanja kolozij v zgoščeni tabeli. DA/NE
Kopica vedno hrani podatke v polju/tabeli. DA/NE
Kopica je uravnoteženo drevo. DA/NE
AVL drevo je levo poravnano drevo. DA/NE

Angleški izrazi:
Skald - Stack
Vrsta - Queue
Polje - Array list
Tabela - Matrix (matrika)
Seznam - Linked list
Zgoščena tabela - Hash table
Kopica - Heap
AVL drevo - AVL tree
  • spremenil: Dzanko ()

Mitja Bonča ::

Bi se dalo te tvoje izraze prevesti v angleščino? So pomojem vsem nam bolj domači.

teey ::

No da kar začnem :)

Slkad deluje hitreje od vrste. DA/NE
Da, sklad je O(1), Queue je linearna.

V tabelo lahko vrinemo podatek hitreje kot v polje. DA/NE
Tu sklepam da je matrika 2D polje? npr. polje[x][y].

Namesto sklada lahko vedno uporabimo tudi seznam. DA/NE
Jup, pač vedno jemlješ zadnji dodan element.

Iskanje po tabeli preišče vse elemente, po drevesu pa ne. DA/NE
Binarna iskalna drevesa se ne sprehajajo po nepotrebnih vejah, saj z vsakim korakom porežejo iskalno množico na pol.

Tabela dostopa do podatka hitreje kot seznam. DA/NE

Tabela = 2D polje? potem ja, seznam potrebuje linearen čas.

Zgoščena tabela išče hitreje kot seznam. DA/NE
Da, saj je ponavadi preslikava kjuča v vrednost 1:1 pri dobrih algoritmih. Zatakne se lahko samo pri trkih, ko dobita dva različna ključa isto vrednost, ampak redko.

Linearno preverjanje je najhitrejši način reševanja kolozij v zgoščeni tabeli. DA/NE

:)

Kopica vedno hrani podatke v polju/tabeli. DA/NE
Kopica je uravnoteženo drevo. DA/NE
Če me spomin ne vara je kopica binarno drevo z pogojem da če je A oče od B, potem je A < B? Potem tudi ni uravnoteženo.

Popravite me, če sem ga kje mimo pihnil.

JanK ::

teey je izjavil:

No da kar začnem :)

Slkad deluje hitreje od vrste. DA/NE
Da, sklad je O(1), Queue je linearna.


Hmm, ali ni vrsta O(N) samo pri naivni implementaciji, ko dejansko premikas vse elemente. Ce pa sledis glavi in repu vrste, je IMHO tudi vrsta O(1).

Mavrik ::

Če me spomin ne vara je kopica binarno drevo z pogojem da če je A oče od B, potem je A < B? Potem tudi ni uravnoteženo.


Kopica je levoporavnano uravnoteženo drevo.

AVL drevo je levo poravnano drevo. DA/NE


Ni. Kopica je levop poravnana. Sta pa oba uravnotežena.

Kopica vedno hrani podatke v polju/tabeli. DA/NE


Ne, odvisno od implementacije. Se pa v večini primerov implementira kot drevo ja.
The truth is rarely pure and never simple.

xardas ::

Zdravo,

mogoče ni v kontekstu te snovi, vendar me zanima če kdo ve odgovor.

Branje z diska (500GB) pri paralelnem prenosu traja nekaj minut. Ocenite koliko približno traja branje podatkov pri serijskem prenostu:
a)nekaj minut
b)nekaj ur
c)nekaj dni

Mavrik ::

Podaj kontekst, ker tule sploh ni razvidno kaj točno bi naj "paralelni prenos" in "serijski prenos" bila.
The truth is rarely pure and never simple.

xardas ::

Vprašanje je bilo v taki obliki. Pa predpostavimo, da je bila mišljena primerjava SATA Vs. PATA povezava.

Senitel ::

To je potem neumna primerjava, ker se PATA že leta ne razvija več. Ker prideš do iste neumnosti kot "kaj je hitrejše 10Mbps ethernet al 1Gbps ethernet?"

teey ::

Hehe, čista kmečka od naše izobražene elite, odgovorov kot smetja, a le eden pravi :)

Če predpostaviš da oba dirkata pri enaki hitrosti je seveda parallelni prenos hitrejši, saj zabaše več podatkov na cikel. Gledano z vidika trenutnih standardov pa se je PATA ustavil pri 133MB, SATA pa je na prvo inkarnacijo prišla opremlena z 1.5Gbit/sek. Če še malo zabluzim deliš 1.5Gb z 8 in pride ~180MB/sek?

To pravi moja kmečka pamet :)

Spura ::

Dzanko je izjavil:

Slkad deluje hitreje od vrste. DA/NE
Vprasanje nima odgovora, ker je nesmiselno.

Dzanko je izjavil:


V tabelo lahko vrinemo podatek hitreje kot v polje. DA/NE
Nerazumljivo.

Dzanko je izjavil:


Namesto sklada lahko vedno uporabimo tudi seznam. DA/NE
Da.

Dzanko je izjavil:


Iskanje po tabeli preišče vse elemente, po drevesu pa ne. DA/NE
Ne.

Dzanko je izjavil:


Tabela dostopa do podatka hitreje kot seznam. DA/NE
Odvisno od implementacije seznama (linked list ali array list).

Dzanko je izjavil:


Zgoščena tabela išče hitreje kot seznam. DA/NE
Odvisno od stevila in tipa elementov, v splosnem DA.

Dzanko je izjavil:


Linearno preverjanje je najhitrejši način reševanja kolozij v zgoščeni tabeli. DA/NE
Najbrz.

Dzanko je izjavil:


Kopica vedno hrani podatke v polju/tabeli. DA/NE
Ne.

Dzanko je izjavil:


Kopica je uravnoteženo drevo. DA/NE
Da.

Mavrik je izjavil:



Ne, odvisno od implementacije. Se pa v večini primerov implementira kot drevo ja.

Ubistvu je najboljsa implementacija z arrayem (ker je levo poravnano drevo ga lahko lepo v array spakiramo).

Zgodovina sprememb…

  • spremenil: Spura ()

technolog ::

Spura, čestitke, pokriješ vse moje odgovore :D

Samo na žalost bi na izpitu s takimi odgovori najverjetneje padel izpit.

p.s.: Bolj pogosto kot "zgoščena tabela" se uporablja izraz "razpršena tabela".

GhostMB ::

Zdravo!
Imam nekaj trditev za katere bi rabil odgovore.

V tabeli dostopamo do podatkov hitreje kot v dinamičnem seznamu. DA/NE.
Iskanje po iskalnem drevesu v najslabšem primeru pregleda vsak element. DA/NE
V vrsti lahko neposredno dostopamo samo do prvih dveh elementov. DA/NE
V dinamični seznam lahko vinemo podatek hitreje kot v tabelo. DA/NE
AVL drevo je isto kot B-drevo 1.reda. DA/NE
Namesto seznama lahko uporabimo tudi vrsto. DA/NE


Sem hvaležen za vsak odgovor.

lp

darkkk ::

Tabela dostopa hitreje(O(1)), po seznamo greš od enega konca (odvisno od implementacije.) DA
Iskanje po iskalnem drevesu v najslabšem primeru pregleda vsak elt. DA (lahko je drevo neuravnoteženo v seznam :) )
Vrsta: malo odvisno od implementacije, ampak načeloma na en konec tlačiš noter, iz drugega jemlješ ven. (dequeue ma dostop do obeh koncev, ampak na FMF je mela en konc). poglej zapiske :) (queue NE, dequeue DA)
Vrivanje v seznam je O(1), DA
ne vem več, oboje so neka uravnotežena drevesa
namesto seznama lahko uporabiš vrsto? NE (razen če je kak trick question)

noraguta ::

to ni za programerske teoretike toj za plonk cegelce. upam da to ni kak fri, al pa kaj podobnega, ...
Pust' ot pobyedy k pobyedye vyedyot!

darkkk ::

to je tudi res :)

WarpedGone ::

To je točno FRI in nič drugega.
Potem pride pa vprašanje Zakaj in je konec smeha.
Zbogom in hvala za vse ribe

darkkk ::

Ma iste živali se je včasih tudi na matematiki na FMF študiralo, samo odgovori na taka vprašanja so bili pričakovani ob 3am po celem večeru pijančevanja :)

Spura ::

Cel kup izrazov je nedefiniranih. Kot naprimer tabela in seznam. Ce je seznam List, potem pomeni samo interface (kaj mora podatkovna struktura omogocat) z implementacijo nima veze in vprasanja postanejo nemogoca. Iskalno drevo je tudi ohlapen izraz. B drevesa so tudi iskalna drevesa.
- btw tudi dequeue ne omogoca neposrednega dostopa do prvih dveh elementov. Razlika med queue in dequeue je to, da lahko pri dequeue na obeh koncih brises in dodajas elemente namesto na vsakem koncu eno od teh operacij.

V dinamični seznam lahko vinemo podatek hitreje kot v tabelo. DA/NE
Se eno bedasto vprasanje, ker je odgovor odvisen od tega, ali drzis pozicijo na tocki dodajanja v linked listu ali ne.
darkkk probi klicat add(int idx, Object o) na LinkedList v javi pa bos videl koliko je to O(1).

darkkk ::

Glede dequeue - nekako sem tisto do prvih dveh razumel kot prvi z vsakega konca (in maš dostop do dveh elementov).

Tisto dodajanje v linked list sem "razumel bolj kot" maš pointer na element v listu, dodaj neki za ta element. Pa tudi sicer mora vstavljanje v tabelo prestavit ostali del tabele "za ena naprej".

Zgodovina sprememb…

  • spremenil: darkkk ()

Spura ::

darkkk je izjavil:

Pa tudi sicer mora vstavljanje v tabelo prestavit ostali del tabele "za ena naprej".

Kar je veliko hitrejse kot vstavljanje v linked list v random pozicijo. Zato vprasanje nima enega samega odgovora.
Sicer je oboje O(n). Kar pokaze kot bullshit je Big-O notation ko ga folk uporablja za mero hitrosti algoritmov in podatkovnih struktur.

Zgodovina sprememb…

  • spremenil: Spura ()

Bristol11 ::

Imam še jaz 4 vprašanja, če mi kdo lahko pomaga :)

Namestor vrste lahko vedno uporabimo tudi seznam,
Tabela porabi več prostora kot polje,
Zgoščena tabela lahko v povprečju išče hitrreje kot drevo,
Vsako binarno drevo je v osnovi B-drevo 1. reda,

DA/NE

hvala, lp

technolog ::

ja.
ne. tabela je polje. Samo drugo ime.
ja.
ne.

Mi je pa prav bedno, ko lovijo folk na subjektivnosti teh slovenskih spakedrankastih prevodov.

Mavrik ::

Če se ne znaš niti jasno pogovarjati v slovenščini, kako točno si sploh sposoben v ekipi potem načrtovati programsko opremo?

Drugače pa imajo ta vprašanja (kot tudi že prej) premalo konteksta in je pogosto odgovor lahko "odvisno".
The truth is rarely pure and never simple.

Zgodovina sprememb…

  • spremenil: Mavrik ()

technolog ::

Ker ekipa pa ne pozna angleških izrazov. Stran s tako ekipo, raje potem delam sam.

Grumf ::

Mavrik je izjavil:

Če se ne znaš niti jasno pogovarjati v slovenščini, kako točno si sploh sposoben v ekipi potem načrtovati programsko opremo?

technolog je izjavil:

Ker ekipa pa ne pozna angleških izrazov. Stran s tako ekipo, raje potem delam sam.


"ekipa", ki ne pozna angleških izrazov je verjetno vse znanje dobila samo na faksu, kar bi
lahko postavilo pod vprašaj njihovo strokovnost. Tako da se kar strinjam z tehnologovim
mnenjem (npr. variable pom, če imaš to po sourcih naženi developerja :D)
Human beings, who are almost unique in having the ability to learn from the
experience of others, are also remarkable for their apparent disinclination
to do so.

gendale ::

tud na faksu se uporabljajo ang izrazi za array pa te stvari
seznam zanč moderatorjev in razlogov da so zanč
http://pastebin.com/QiWny5dV
gor je mavrik apple uporabniček (mali možgani in mali penis)

GhostMB ::

Potreboval bi nekaj odgovorov.


static int PoisciZBisekcijo(int el, int[] a)
        {

            int konec = a.Length;
            int zacetek = 0, sredina;
            if (a.Length == 0) //vprasanje.... ce res vrne -1 pri praznem polju
                return -1;
            while (zacetek <= konec)
            {
                sredina = (zacetek + konec) / 2;
                if (a[sredina] < el)
                {
                    zacetek = sredina + 1;
                }
                else if (a[sredina] > el)
                {
                    konec = sredina - 1;
                }
                else
                {
                    if (sredina == 0)
                    {
                        return sredina;
                    }

                    while (a[sredina + 1] == el && (sredina - 1) > 0)
                    {
                        sredina++;
                    }

                    return sredina;
                }
            }
            return -1;
        }


1.)
a.)Kaj vrne metoda, kadar polje "a" ne vsebuje el?
b.)Kolikokrat se izvrši blok else, če je dolžina 0?
c.)Kolikšen je v splošnem red rasti časovne zahtevnosti?

2.)Katere značilnosti ima podatkovna struktura tabela?
a.)položaj elementa v tabeli je določen z indeksom ?
b.)je statična podatkovna struktura ?
c.)je izvedena kot množica zaporednih lokacij v pomnilniku
d.)je vgrajena v večina programskih jezikov

Hvala za odgovore.

Spura ::

Stari vsa vprasanja iz prve tocke so trivialna. Preber faking kodo. 2 naloga je odgovor a,b,c ce mislis array. MOgoce tudi D. dvomim da kdo ve tocen odgovor ce so arrayi v vec kot polovici jezikov.

_Dormage_ ::

Ne vem, če je za teoretike razen časovne zahtevnosti.
Za 1a) lahko odgovor dobiš tako, da program zaženeš.
Če je polje velikosti 0 boš metoda vrnila -1. Kaj se zgodi, če je prazno polje velikosti 5? :)

1b) vprašanje mogoče nisem razumel, ampak, če je dolžina polja 0 se else ne izvede.
Odgovor na 1c) je kar v imenu metode (bisekcija)..

2a) ja
2b) ja
2c) ja (shrani se v blok, index elementa je dejanski odmik ram naslova od začetka bloka) vsaj v javi.
2d) ja

darkkk ::

1a. -1 bo vrnla, razn če je kak hud mindfuck noter
1b. nikol :) ?
1c. časovna zahtevnost bisekcije je O(log n)

abyssus ::

Lep pozdrav.

Zanima me ali ima koren trojiškega drevesa 3 vozlišča in nato vsa vozlišča iz "sebe" še nova tri vozlišča? Na izpitu je bil primer, da moramo narisati največje možno trojiško drevo višine 2.

Nato me še zanima kako bi izgledal dvakratno povezan dinamični seznam z vsaj 3 vozlišči/elementi in različnima začetkoma?

Zadnje vprašanje pa je še ta: kako se s pomočjo skladovnega stroja reši postfiksni izraz: 3 7 4 / 4 * + 5 -.

Zahvaljujem se za odgovore.

_Dormage_ ::

Root oziroma koren je eden. Če želiš "največje" drevo za dano višino potem ima koren tri otroke, in vsak od teh otrok še svoje tri otroke.

A si mogoče mislis dvosmerno povezan dinamični seznam? Mogoče nisem še slišal za dvokratno. Verjetno je isto :)
Če je dvosmerni potem to pomeni samo to, da imaš še kazalec na predhodni element.
Kako bi zgledal grafično?

Skladvnega stroja pa se mi ne ljubi, Skyrim time...:))

usoban ::

Stack: nalagas po vrsti, ko naletis na operator popnes dva elementa s sklada in ta operator uporbis na njih, rezultat pa pushas nazaj.
----------------
3, 7, 4 =>
3, 7/4 =>
3, 7/4, 4 =>
3, 7 =>
10 =>
5

Trojisko drevo: ja, vsako vozlisce ima po tri sinove. Ce je visine 2, je to koren -> trije sinovi -> 9 vnukov, vsak sin ima po 3.

Dvakratno povezan seznam:
head (prazen) < = > element 1 < = > element 2 < = > element 3 < = > tail (prazen)

head in tail sta prazna elementa, ki se ju uporablja za direktni dostop na zacetek in konec seznama. Razlika napram navadnemu seznamu je, da elementi nimajo reference samo na naslednji element, ampak tudi na tistega pred njim. V tem primeru pri operaciji brisanja elementa iz seznama (recimo nekje na sredi) ni potrebno iskat prejsnjega elementa (v najslabsem primeru, ce bi brisal zadnjega bi to pomenilo n-1 opercij), ampak je direktno dostopen v konstantnem casu. Tradeoff je pa vec porabljenega prostora za reference.

edit: ja, ce si s tem mislil double linked list; ker ne vem kaj mislis s tem "različnima začetkoma"

Zgodovina sprememb…

  • spremenil: usoban ()

abyssus ::

Hvala obema. :)

Ne vem kaj mislijo z različnima začetkoma. Očitno še moreš prvega pa zadnjega povezat z obeh strani - od prvega k zadnjemu, pa zadnjega k prvemu. Taka so bila navodila na izpitu.

Izraz sem pravilno rešila do 3, 7. :)

Ne skapiram pa še B-drevesa. Ni mi jasno po kakem pravilu dodajaš elemente ali jih odstranjuješ. Če bi se mogoče dalo na hitro razložit.

Hvala še enkrat za pomoč. :)

Zgodovina sprememb…

  • spremenilo: abyssus ()

usoban ::

Uf za B-tree ti pa ne znam na kratko povedat; najbolje da si kar na wikiju preberes B-tree @ Wikipedia , sej je vse napisano :)

Looooooka ::

gendale je izjavil:

tud na faksu se uporabljajo ang izrazi za array pa te stvari

Je blo ze kar nekaj clankov napisanih, kjer so lepo povedali, da bi morali slovenski izrazi lepo spokat v zadnji del avtobusa z vsemi ostalimi prevodi v katerem koli jeziku, ki ni anglescina.
V zivljenju bos slej kot prej delal s tujci in takrat bodo slovenski izrazi in slovenski komentarji takoj ovira in ne prednost.
Kdor pa misli, delat samo s slovenci bo pa zlo hitro brez posla koncal.
Ampak...logicno, da jim pac forsirajo tole. Kar je v bistvu zalostno, ker je narobe.

Mavrik ::

Ne skapiram pa še B-drevesa. Ni mi jasno po kakem pravilu dodajaš elemente ali jih odstranjuješ. Če bi se mogoče dalo na hitro razložit.


Huh, na hitro bolj težko. :)
Torej, pri B drevesih imaš več otrokov v vozlišču - recimo da d. Tam velja naslenje:

1.) Vrednosti v vozlišču so vedno urejene
2.) Vsako vozlišče ima lahko toliko otrok, kot ima vrednosti + 1
3.) Za otroke velja: njihove vrednosti morajo biti VEČJE od vrednosti levo v staršu in MANJŠE kot vrednosti desno v staršu (glej sliko)

B-drevo, vozlišča in povezave otrok

B-drevo, vozlišča in povezave otrok



Dodajanje

1.) Poiščeš list (torej najgloblji element) drevesa, ustrezen za tvojo vrednost in jo vstaviš tja
2.) Preveriš, če si v listu dosegel zgodnjo omejitev števila elementov
3.) Če si dosegel omejitev:
3.1) Poiščeš srednjo vrednost v vozlišču
3.2) Srednjo vrednost potegneš gor in jo daš v starša
3.3) Vozlišče razdeliš na dva dela - levi del z vrednostmi manjšimi kot je srednja vrednost in desni del z vrednostmi večjimi od srednje vrednosti. Ta dva dela potem dodaš staršu, levo in desno od srednje vrednosti
3.4) Preveriš če je starš dosegel omejitev št. elementov in ponoviš korak 3.) na njem

Torej - pri dodajanju je fora v tem, da greš najnižje v drevesu, vstaviš element, potem pa od spodaj gor preverjaš a si dosegel maksimum elementov in razbijaš vozlišča na dva kosa ko si.

Za odstranjevanje pa kasneje, moram laufat ;)
The truth is rarely pure and never simple.

abyssus ::

Hvala. :)

Jerry000 ::

Si bom kr mal to temo izposodil:). Zanima me naslednje:

Pri grafih sprehod v globino in širino. Nekaj sem že bral po netu ampak ne razumem. Mi lahko kdo po kmečko in bolj enostavno razloži?

To mi tut ni jasno:
Kaj je to narejeno, piše: Nariši še vsaj 2 kopici, ki vsebujeta števila 1, 2, 3, 4 in 5! primer: 5,3,4,2
a)_________
b)_________

Rešitev od nepoznane osebe je
a)5,4,3,2,1 (začel z 2)
b)5,4,1,2,3 (začel z 2)


In tudi tole mi ni kaj preveč jasno wtf morš tle sploh gledat in kaka je rešitev in zakaj:

1. Poenostavi izraz s pomojo formalnih definicij osnovnih podatkovnih struktur:
1.1 Sklad:
VRH(ODSTRANI(VSTAVI(ODSTRANI(VSTAVI(VSTAVI(PRIPRAVI,A),B)),C)))
VRH(ODSTRANI(VSTAVI(ODSTRANI(VSTAVI(VSTAVI(S,A),B)),C)))
VRH(ODSTRANI(VSTAVI(VSTAVI(S,A)),C)))
VRH(VSTAVI(S,A))
A
1.2 Vrsta:
ZAETEK(VSTAVI(VSTAVI(ODSTRANI(VSTAVI(PRIPRAVI,1)),2),3))
ZAETEK(VSTAVI(VSTAVI(ODSTRANI(VSTAVI(V,1)),2),3))
ZAETEK(VSTAVI(VSTAVI(V,2),3))
ZAETEK(VSTAVI(V,2))
2
1.3 Seznam:
VRNI(VRINI(VRINI(VSTAVI(PRIPRAVI,1,A),1,B),1,C),2)
VRNI(VRINI(VRINI(VSTAVI(S,1,A),1,B),1,C),2)
VRNI(VRINI(VSTAVI(VRINI(S,1,B),2,A),1,C),2)
VRNI(VRINI(VSTAVI(VRINI(S,1,B),2,A),1,C),2)
VRNI(VSTAVI(VRINI(VSTAVI(S,1,B),1,C),3, A),2)
VRNI(VSTAVI(VSTAVI(VRINI (S,1,C),2,B),3,A),2)
VRNI(VSTAVI(VSTAVI(VSTAVI (S,1,C),2,B),3,A),2)
VRNI(VSTAVI (VSTAVI(S,1,C),2,B),2)
B
1.4 Dvojiško drevo:
VRNI(DESNI_SIN(SESTAVI(PRIPRAVI,A,SESTAVI(PRIPRAVI,X,PRIPRAVI))))) -> X
VRNI(SESTAVI(PRIPRAVI,X,PRIPRAVI))
X



To so nejasnosti, lahko prosim kdo razloži in pomaga malo:)?

darkkk ::

Lej za preglede grafov maš BFS(v širino) pa DFS (v globino).
Najlažje si boš tko predstavljal na primeru dvojiškega drevesa(ki je malo poseben graf), začneš v root-u, v širino pregled dela po nivojih, v globino pa najprej pregleda enega od sinov in vse njegove potomce.

Isto na "splošnih" drevesih(grafih brez ciklov), DFS gre v eno smer kolikor se da pregledovat, nato zamenja vejo, BFS pa v "koncentričnih krogih" okol root-a išče. Pa saj bi moral bit kak demo kje na netu.




Za one naloge je verjetno treba "narisat" kaj je rezultat tistih operacij?
Pač greš po vrsti in premetavaš od noter na ven.

Zgodovina sprememb…

  • spremenil: darkkk ()

Jerry000 ::

Ful hvala za ta video, dobra razlaga in prikaz:). Vseeno pa še vedno ne vem kako rešit takšnega tipa:

To mi tut ni jasno:
Kaj je to narejeno, piše: Nariši še vsaj 2 kopici, ki vsebujeta števila 1, 2, 3, 4 in 5! primer: 5,3,4,2
a)_________
b)_________

Rešitev od nepoznane osebe je
a)5,4,3,2,1 (začel z 2)
b)5,4,1,2,3 (začel z 2)


Tole mi ni kaj preveč jasno wtf morš tle sploh gledat in kaka je rešitev in zakaj:

1. Poenostavi izraz s pomojo formalnih definicij osnovnih podatkovnih struktur:
1.1 Sklad:
VRH(ODSTRANI(VSTAVI(ODSTRANI(VSTAVI(VSTAVI(PRIPRAVI,A),B)),C)))
VRH(ODSTRANI(VSTAVI(ODSTRANI(VSTAVI(VSTAVI(S,A),B)),C)))
VRH(ODSTRANI(VSTAVI(VSTAVI(S,A)),C)))
VRH(VSTAVI(S,A))
A
1.2 Vrsta:
ZAETEK(VSTAVI(VSTAVI(ODSTRANI(VSTAVI(PRIPRAVI,1)),2),3))
ZAETEK(VSTAVI(VSTAVI(ODSTRANI(VSTAVI(V,1)),2),3))
ZAETEK(VSTAVI(VSTAVI(V,2),3))
ZAETEK(VSTAVI(V,2))
2
1.3 Seznam:
VRNI(VRINI(VRINI(VSTAVI(PRIPRAVI,1,A),1,B),1,C),2)
VRNI(VRINI(VRINI(VSTAVI(S,1,A),1,B),1,C),2)
VRNI(VRINI(VSTAVI(VRINI(S,1,B),2,A),1,C),2)
VRNI(VRINI(VSTAVI(VRINI(S,1,B),2,A),1,C),2)
VRNI(VSTAVI(VRINI(VSTAVI(S,1,B),1,C),3, A),2)
VRNI(VSTAVI(VSTAVI(VRINI (S,1,C),2,B),3,A),2)
VRNI(VSTAVI(VSTAVI(VSTAVI (S,1,C),2,B),3,A),2)
VRNI(VSTAVI (VSTAVI(S,1,C),2,B),2)
B
1.4 Dvojiško drevo:
VRNI(DESNI_SIN(SESTAVI(PRIPRAVI,A,SESTAVI(PRIPRAVI,X,PRIPRAVI))))) -> X
VRNI(SESTAVI(PRIPRAVI,X,PRIPRAVI))
X

arjan_t ::

pač poenostavitev glede na operacije nad podatkovno strukturo:
VRH(ODSTRANI(VSTAVI(ODSTRANI(VSTAVI(VSTAVI(PRIPRAVI,A),B)),C)))
VRH(ODSTRANI(VSTAVI(ODSTRANI(VSTAVI(VSTAVI(S,A),B)),C)))
VRH(ODSTRANI(VSTAVI(VSTAVI(S,A)),C)))
VRH(VSTAVI(S,A))
A
(npr. ODSTRANI(VSTAVI(S, A)) == S)

PRIPRAVI -> S (verjetno mišljena inicializacija)
VSTAVI(S, A) -> S(A)
VSTAVI(S, B) -> S(B, A)
ODSTRANI(S) -> S(A)
itd.
(rešitev je tisto zgoraj, to je samo primer evaluacije)

Zgodovina sprememb…

  • spremenil: arjan_t ()

Jerry000 ::

hvala ampak še vedno nič jasno, zbegan sem nekako. Je mogoče kak video al pa razlaga ki točno opisuje vsak korak in zakaj je tko narejeno?

Jerry000 ::

Še nekje se mi je zataknilo.

http://www.gophoto.it/view.php?i=http:/...

B-drevo 2. reda. Prvo me zanima kaj to pomeni da je 2. reda? Drugo pa, kako se to nalogo reši? (Postopoma). Js mislim da je 2. reda to da imaš v vozliščih po 2 cifri, ampak nisem siguren.
Lahko nekdo tole postopoma reši in pokaže rezultat? Sem gledal že tutoriale na netu, ampak nekako ne uspem rešiti

usoban ::

2. reda pomeni da ima vsako vozlisce max dva otroka

Zgodovina sprememb…

  • spremenil: usoban ()

Jerry000 ::

lahko mogoče še nalogo rešiš da vidim?

Jerry000 ::

Torej še vedno me zanima pri Bayerjevih drevesih. Kaj pomeni reda 2, 3, 4 (prosim za kako skico teh red)
Koliko "številk" lahko shranimo v eno vrstico(sorry pišem po domače ker si lažje predstaulam)? Naprimer če bo tako lažje:

http://wiki.fmf.uni-lj.si/wiki/B-drevo

Pri primeru kjer piše: Pri vstavljanju črke D v drevo je potreben razcep najbolj levega vozlišča. D je srednji element, zato ga premaknemo v koren. Naslednje črke P,R,X in Y lahko vstavimo brez razcepa.

Vsak okvir torej lahko hrani max 4 zapise, ko pride 5. zapis se mora okvir razpolovit. Kje je to določeno koliko zapisov gre lahko v okvir?
Sorry za izražanje na tak način

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C#] Iskalno Drevo

Oddelek: Programiranje		131932 (1498) Ciklamen
»

[C#] Razširitev Linked List-a

Oddelek: Programiranje		51041 (707) Ciklamen
»

java pomoč

Oddelek: Programiranje		211832 (1224) kr?en
»

[C++] Iskalno drevo implementacija

Oddelek: Programiranje		52136 (1694) eXoo
»

[C++] Naloga seznam

Oddelek: Programiranje		223107 (2382) Matic1911

Več podobnih tem