A-sort

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

A-sort

Příspěvek od Kuba »

Kód: Vybrat vše

A-Insert(x):
t := Prv
while t <> koren T a Ht(1) < x do
t := otec(t)
enddo
while t <> list do
i := 1
while Ht(i) < x a i < Ro(t) do i := i + 1 enddo
if i > 1 then
v := St(i − 1)
else
v := Sv(ro(v))
endif
t := St(i)
enddo
Zda se mi to, nebo je tam mensi chybka?
Konkretne: Zacinam v prv. lezu nahoru, dokud Ht(1) < x, z whileu vyskocim kdyz Ht(1) > x, i:=1, ten while neudelam, protoze Ht(1) > x, cili i = 1, skocim do Else vetve, ale ted nevim co je vrchol v...
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: A-sort

Příspěvek od chucky »

No zrejme tam bude chyba.
Neviem, co tym

Kód: Vybrat vše

if i > 1 then
v := St(i − 1)
else
v := Sv(ro(v))
endif
malo byt myslene, ale ja by som tento usek kodu uplne vynechal (opravte ma, ak v tom vidite problem). vrochol v sa potom dalej nikde nepouziva.(EDIT: sorry, predsa len sa pouziva :) )
A podmienku predchadzajuceho while cyklu by som prerovnal na

Kód: Vybrat vše

while i < Ro(t) a Ht(i) < x
, lebo Ht(Ro(t)) nie je definovane (a predpokladam skratene vyhodnocovanie).

Ale celkovo som tie kody velmi nestudoval, algoritmy by som popisal skor svojimi slovami, alebo nejakym este viac pseudo kodom.

Inak chyba je uz na druhom riadku algoritmu:

Kód: Vybrat vše

t := Prv
while t <> koren T a Ht(1) < x do
Prv je list a pre listy Ht() nie je definovane.
Asi na prvom riadku malo byt t:=otec(Prv).
Ale este raz, velmi by som sa nesnazil ucit tie kody naspamat.
Naposledy upravil(a) chucky dne 3. 2. 2008 16:29, celkem upraveno 1 x.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: A-sort

Příspěvek od Kuba »

chucky píše:No zrejme tam bude chyba.
Neviem, co tym

Kód: Vybrat vše

if i > 1 then
v := St(i − 1)
else
v := Sv(ro(v))
endif
malo byt myslene, ale ja by som tento usek kodu uplne vynechal (opravte ma, ak v tom vidite problem).
No tim bylo myslene, ze kdyz i = 1, tak predchudce Ht(1) (v lex. usp.) se musi hledat jako maximalni prvek jeho leveho bratra (ktery je vzdy drzen v promenne v - az na prvni kolo, kdy prave neni inicializovan)
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: A-sort

Příspěvek od chucky »

ja to vidim takto:
tento kod mi najde vrchol, do ktoreho podstromu budem pridavat:

Kód: Vybrat vše

t := Prv
while t <> koren T a Ht(1) < x do
t := otec(t)
enddo
a potom uz len leziem dolu po ceste, kde by som x hladal. Nejako mi nie je jasne, kde by som potreboval laveho brata.. Podla mna ked i = 1, tak pridavam do podstromu St(1).
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: A-sort

Příspěvek od Kuba »

Toho potrebujes, abys mohl updatovat ten spojak listu (Next(v) = t), kdyz t je nejlevejsi prvek toho podstromu do ktereho pridavas
chucky
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 17. 5. 2007 16:20
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: A-sort

Příspěvek od chucky »

aha, jasne, na to som zabudol.

V tom pripade snad nevadi, ze v nie je na zaciatku definovane. Staci predpokladat, ze

Kód: Vybrat vše

v := Sv(ro(v))
nevyhodi Null Pointer Exception, ale v zostane nedefinovane.
A ked by v zostalo nedefinovane az do konca, tak

Kód: Vybrat vše

Nasl(v):=t'
by malo znamenat

Kód: Vybrat vše

Prv:=t'
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: A-sort

Příspěvek od Kuba »

Jo, takhle by to asi slo. No... skripta by si zaslouzila mensi revizi...
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: A-sort

Příspěvek od rastik »

IMHO je ten algoritmus OK. Začínaš v liste a ideš nahor, kým Ht(1) < x. Teda buď dojdeš na miesto, kde Ht(1) >= x, alebo si stále na začiatku, v prvom liste. A vtedy sa celá ta vetva preskočí a v sa vôbec nijako nedefinuje. A ani nemusí, pretože pri tejto kombinácii sa v algoritme nepoužije - nový prvok nepôjde na začiatok listu.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: A-sort

Příspěvek od Kuba »

Jo, ale kdyz dojdes na to misto, kde Ht(1) > x, tak pak je tam i :=1, while Ht(1) < x (coz neni) tak i++, takze i je stale 1. A pak je tam if i > 1 (coz neni) else v := Sv(ro(v)). A v tomto okamziku jeste v nebylo definovano, takze kde se vezme Sv a ro(v)?
Uživatelský avatar
rastik
Supermatfyz(ák|ačka)
Příspěvky: 661
Registrován: 19. 10. 2005 21:45
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: A-sort

Příspěvek od rastik »

Kuba píše:Jo, ale kdyz dojdes na to misto, kde Ht(1) > x, tak pak je tam i :=1, while Ht(1) < x (coz neni) tak i++, takze i je stale 1. A pak je tam if i > 1 (coz neni) else v := Sv(ro(v)). A v tomto okamziku jeste v nebylo definovano, takze kde se vezme Sv a ro(v)?
V tom úvodnom príspevku to nie je odsadené, ale všetko to čo píšeš je obalené v

Kód: Vybrat vše

while t <> list do
Takže sa tam vôbec nedostane, pretože sa nedostal z prvého listu.
Uživatelský avatar
Che
Donátor
Donátor
Příspěvky: 166
Registrován: 2. 6. 2005 12:29
Typ studia: Informatika Mgr.
Bydliště: EU
Kontaktovat uživatele:

Re: A-sort

Příspěvek od Che »

Já si taky myslím, že tam je chyba... Podle mne by ten začátek měl vypadat takhle:

Kód: Vybrat vše

if Prv <> kořen T then
  t := otec(Prv) { listy nemají definováno Ht }
else
  t := Prv
endif

while t <> kořen T a Ht(1) < x do
  t := otec(t)
enddo

{ i kdyby předchozí cyklus skončil kvůli tomu, že jsme došli až ke kořeni, tak mohlo už začit platit také: Ht(1) >= x }
if t = kořen T a Ht(1) < x then
  { nedělej nic }
else
  t = St(1)
endif

{ Nyní je jisté, že v nasledujícím cyklu se i inkrementuje alespoň jednou (pokud t není list, to se pak přeskočí celý cyklus)
  protože bude platit Ht(1) < x a proto v bude definováno korektně }

while t <> list do
  i := 1
  while Ht(i) < x a i < Ro(t) do i := i + 1 enddo
  if i > 1 then
    v := St(i-1)
  else
    v := Sv(Ro(v))
  endif
  t := St(i)
enddo
shoot that shit
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: A-sort

Příspěvek od Kuba »

No, co cert nechtel, dneska jsem to dostal u zkousky. Kdyz to tam clovek napise tak jak to je v textu, tak je to ok. A je to tedy tak, ze kdyz to neni definovane, tak je to PRV.

Teda, abyste to spatne nepochopili, ja si nestezuju ze sem to dostal :) Myslim ze A-sort je jedna z nejjednodussich otazek.
Odpovědět

Zpět na „TIN066 Datové struktury I“