Dinamikus adatszerkezetek és velük kapcsolatos műveletek VEREM Szemléletesen olyan tárat képzeljünk el mint egy ”multivitaminos dobozt” melybe egyenként tudunk vitaminokat belerakni és kivenni, de csak úgy, hogy kivenni csak a legutoljára berakott korongocskát tudjuk . A verem is egy olyan szerkezetnek tekinthető melynek csak az egyik oldalával végezhetünk műveleteket. A verembe rakhatunk elemeket, kivehetünk elemeket, de mindig csak a verem legfelső szintjéhez férhetünk hozzá. Az először a verembe helyezett elemet csak akkor vehetjük ki a veremből, ha minden később ráhelyezett elemet már kivettünk onnan. A verem adatok sorozatát tartalmazza, de csak speciális műveleteket engedünk meg vele kapcsolatban. Ezek a következők: VEREMBE(x)
– egy x értéket a verem tetejére ( a sorozat végére helyez) szokás ezt PUSH műveletnek is nevezni
x <- VEREMBŐL
- a verem tetején lévő értéket( a sorozat utolsó elemét) az x változóba teszi, majd a veremből elhagyja. ( POP művelet)
A verem tehát egy olyan speciális sorozat melynek egyik végét tudjuk csak kezelni, oda tehetünk új elemet s csak onnan vehetünk ki. Szokás LIFO adatszerkezetnek is nevezni( last in first out – ’utolsóból lesznek az elsők’) arra utal , hogy az utolsónak behelyezett elemet vehetjük ki először. A veremhez tartozik egy speciális változó a veremmutató amely a veremnek mindig arra a szintjére mutat, ahol a verem tetején lévő elem helyezkedik (0 ha üres a verem):
Adat4 Adat3
Veremmutató (ide lehet új adatot elhelyezni)
Adat2 Adat1 A fenti verembe először az adat1, majd az adat2, az adat3, s végül az adat4 került s a kivétel sorrendje adat4, adat3, adt2 adat1 lehet. Verem megvalósítása: Két feladat van : 1, verem ábrázolása 2, műveletek elkészítése Használjunk egy S[1..N] vektort a verembe kerülő elemek tárolására! Mivel a vektor csak véges számú elemet tartalmazhat, ebből következik, hogy N elemnél többet nem helyezhetünk el a veremben, ezt a VEREMBE ( PUSH) műveletnél figyelembe kell venni. Szükség van arra is , hogy megmondjuk meddig van kitöltve ez a vektor, azaz kell egy mutató amely a verem tetejére mutat. Ebből az is következik , hogy a verem használata előtt ennek a
változónak kezdőértéket kell adni, tehát a műveletek körét szélesíteni kell. Jelöljük ezt a mutatót SP-vel! Műveletek : Üresre állítás: SP:=0 Eljárás vége. VEREMBE(x) : Ha ( SP = N )
akkor ’HIBA’ különben SP:= SP+1 : S[SP]:= x
// betelt a verem
Ha vége. Eljárás vége. VEREMBŐL : Ha( SP=0)
akkor ’HIBA’ különben SP:=SP-1 : Return S[SP + 1]
// üres a verem
Ha vége. Eljárás vége. A veremszerkezeteknek számos alkalmazása területe van. Ilyen például a függvényhívások szervezése a C/C++ ban. Ha a főfüggvényben meghívunk egy FX() függvényt , akkor többek közt tárolni kell azt a címet amelyre az FX() függvény végrehajtása után vissza kell térni. Ha az FX() függvény meghív még egy másik HX() függvényt akkor FX()-beli folytatás címét szintén tárolni kell. A verem alkalmazásával ez egyszerűen megoldható. Minden függvényhívásnál a verembe tesszük azt a címet, ahol folytatni kell a függvény befejezése után a végrehajtást, a függvény lefutásának végén pedig ezt a címet ki kell venni a veremből, majd ezen a címen kell folytatni tovább a program futtatását.
SOR A sor, mint adatszerkezet kicsit hasonlít a veremre. Úgy kell elképzelni, mint egy egysávos alagutat ahova bemennek az autók és az alagút másik oldalán jöhetnek csak ki. Az autók a sorrendjüket nem változtathatják meg és aki elsőnek bement az alagútba az jön is ki elsőnek a túlsó végén. Új autó csak a sor végére állhat. Ez a szerkezet tehát az elemek olyan sorozata, mely sorozat egyik végére lehet tenni új elemeket , a másik végéről pedig el lehet venni őket. Szokás FIFO adatszerkezetnek is nevezni( first in first out – ’ elsőből lesznek az elsők’ ) A sor műveletei: SORBA(x) - berak a sor végére egy x elemet X <- SORBÓL - kivesz a sor végéről egy x elemet
Adat1
Adat2
Adat3
adatmozgás iránya Honnan (innen lehet adatot kivenni )
Hova (ide lehet adatot rakni)
Ábrázolás: Legegyszerűbb megvalósítása szintén egy vektorral történik SOR[1..N], de itt két mutatóra van szükség. Tudni kell, hogy hova lehet tenni új elemet ( HOVA) és tudni kell , hogy honnan lehet kivenni ( HONNAN). Itt is szükség van kezdőérték adásra. Célszerű használni az úgynevezett sor ciklikus tárolását. Akkor, ha az N-ik, hely foglalt, következik újra az első hely az új elem tárolására, amennyiben ez már üres. Használjunk egy DB változót a sorban levő elemek számlálására! Sor műveletei: Üresre állítás : HOVA :=1 : HONNAN := 1 : DB =0 Eljárás vége. SORBA(x): Ha (DB=N)
akkor HIBA // betelt a sor különben SOR[HOVA]:=x HOVA : = HOVA+1 DB:=DB+1 Ha( HOVA >N) akkor HOVA:=1 Ha vége
Ha vége Eljárás vége. SORBÓL: Ha (DB=0) akkor HIBA // üres a sor különben x:= SOR[HONNAN] HONNAN := HONNAN+1 DB:= DB-1 Ha( HONNAN >N)akkor HONNAN :=1 Ha vége Return x Ha vége. Eljárás vége.
LISTA Mielőtt rátérünk ezen szerkezez tárgyalására, nézzünk egy egyszerű példát. Adott több ezer banki folyószámlával rendelkező ember halmaza valamilyen háttértáron tárolva. Egy emberről tároljuk a nevét, lakcímét, személyi adatait, betétjüket, adósság állományukat stb. Sokszor előfordul, hogy az adatokra nem olyan sorrendben van szükség, ahogyan eredetileg táruljuk őket. Időnként névsorba kellene rendezni, esetenként adósság nagysága, máskor lakcím szerint. Ezekben az esetekben megoldás lehetne az is, hogy mindig átrendezzük a sorozat elemeit a kívánt sorrendbe, ez azonban rengeteg időt venne igénybe. Egészítsük ki az emberek adatait egy újabb ”mezővel” s ebbe a mezőbe írjuk, az új listában a logikailag utána következő adat sorszámát(címét). Az így kapott lista egy olyan szerkezet, amely megmondja, hogy egy adott adatelem után logikailag melyik következik. Nevezik az ábrázolást láncolt
ábrázolásnak is. Az eredeti sorozat sorrendjének megváltoztatása nélkül számtalan ilyen logikai láncot hozhatunk létre. Egy adat mellé több ilyen mutatóértéket is elhelyezhetünk, és így több logikai sorrendet tárolhatunk. Természetesen meg kell mondanunk, hogy az adott sorrendben melyik elemet tartjuk az elsőnek. Ez lesz a lista feje. Meg kell még oldani az utolsó elem felismerését, ez az az elem amely után nem következik semmi sem. Ezt például egy speciális, egyébként elő nem forduló mutatóértékkel jelezhetjük. Ez a megoldás akkor is előnyös, amikor két adatelem közé egy újabbat kell felvenni vagy pedig az adatsorból kell elemet törölni vagy két elem sorrendjét kell megváltoztatni Nézzünk egy egyszerű példát: Rendezzük névsor szerint a következő táblázat adatait. Az eredetileg tárolt adatokat egészítsük ki, egy új elemmel ami, a logikailag következő elem sorszámát(címét) tartalmazza. Az után az adat után, ami után már nincs semmi( a lánc utolsó eleme) a NULL jelet írjuk. Egészítsük ki egy FEJ nevű taggal a listánkat s az logikai lánc első elemének a sorszámát (címét) a lista FEJ nevű elemébe írjuk be. Ebben a sorrendben tároljuk eredetileg az adatokat
Egészítsük ki az adatokat egy új ”résszel”
Sorsz
NÉV
Betét
Következő adat
1
Tóth Mihály
60 000 FT
2
Nagy Ferenc
15 000 000 FT
4
3
Kiss Péter
120 FT
2
4
Orosz Balázs
50 000 FT
1
NULL
Új lista első eleme Az elkészült logikai lánc : Kiss Péter
FEJ
2
Nagy Ferenc 4
Orosz Balázs 1
Tóth Mihály NULL
3
Hasonló láncot készíthetünk, ha a logikai sorrendet nem a nevek szerint, hanem a fizetés alapján hozzuk létre. Természetesen, hangsúlyozzuk, hogy a láncok létrehozása nem néhány elem esetén, hanem nagy adathalmaz meglétekor célszerű. A láncolt adatszerkezetek általánosságban tehát így ábrázolhatók:
FEJ FEJ
ADAT1
ADAT2
ADAT N NULL
Ebből eddig az látszik, hogy a láncolt ábrázolásnál, az adatszerkezet helyfoglalása megnövekszik, a következő elem címét tartalmazó résszel. A láncolt ábrázolás előnyei az adatszerkezet módosításakor mutatkoznak meg. Egyszerű a listába új elemet beilleszteni, pl. a K. és K+1. közé ( a K. elem mutatóját át kell állítani.!) Új elem beillesztése a láncba: K+1. ADAT
K. ADAT
Új elem Egy elem törlése (kifűzése) a láncból : A K. ADAT törlése csak a (k-1.) ADAT mutatójának (a következő elem sorszámát (címét) tartalmazó rész megváltoztatását jelenti
K-1. ADAT
K. ADAT
K+1. ADAT
Láncok ábrázolása: Az adatokat az ADAT[1..N] vektorban tároljuk, a következő elemre mutatókat(a logikailag következő elemek sorszámát (címét) a KOV[1..N] vektorban. A lista utolsó eleme esetén KOV tartalma 0. Tartalmazza a logikailag első elem sorszámát (címét) a FEJ változó! A lista üres, ha a FEJ változó tartalma 0. Műveletek: Az első elem sorszámának (címének) meghatározása: Első: MUT:=FEJ Return MUT Eljárás vége. Következő elem sorszámának (címének) meghatározása: Következő(MUT): Ha (MUT > 0) akkor
MUT:=KOV[MUT] Ha vége Return MUT Eljárás vége. Új elem (X) beillesztése a listába a K. után a fizikailag H. helyre (ADAT [H] az érték, KOV [H] lesz a mutatója). Új elem (K, H, X): Ha (K=0) akkor // Beillesztés a lista elejére KOV[H]:=FEJ FEJ:=H különben // Ha nem a lista elejére illesztjük be, akkor keressük meg a K. címét Első (MUT): I:=1 Ciklus, amíg I
0 és ADAT[MUT]<>X Következő (MUT) Ciklus vége SORSZÁM:=MUT Return SORSZÁM Eljárás vége.
Egyes esetekben kétirányú listákat (kétirányú láncokat) alkalmaznak. Ezekben az esetekben az adatelemekhez még egy mezőt illesztünk, amely az őt megelőző elem címét adja meg és tároljuk a lista utolsó elemének sorszámát (címét) a VÉG nevű változóban. NULL
ADAT1
ADAT2
ADAT3
FEJ
ADAT N NULL
VÉG
Kétirányú láncok ábrázolása: Az adatokat tartalmazó ADAT[1..N] és a következő elemek címét tartalmazó KOV[1..N] vektorokon kívül használjuk az ELO[1..N] vektort az előző elemek címeinek a tárolására. Így a kétirányú láncban a lista első eleme esetén az ELO tartalma 0. A fenti három művelet könnyen kiterjeszthetők a kétirányú listákra: Új elem (X) beillesztése a kétirányú listába a K. után a fizikailag H. helyre (ADAT [H] az érték, KOV [H] lesz a mutatója). Új elem (K, H, X): Ha (K=0) akkor // Beillesztés a lista elejére KOV[H]:=FEJ ELO[H]:=0 Ha (FEJ=0) akkor VEG:= H különben ELO[FEJ]:= H Ha vége FEJ:=H különben // Ha nem a lista elejére illesztjük be, akkor keressük meg a K. címét Első (MUT): I:=1 Ciklus, amíg I
Törlés (K): Ha (K=1) akkor // Ha a lista első elemét töröljük FEJ:=KOV[FEJ] Ha (FEJ=0) akkor VEG:=0 különben ELO[FEJ]:=0 Ha vége különben // Ha nem az első elemét töröljük, akkor keressük a K-1. elemet Első (MUT): I:=1 Ciklus, amíg I
A szabad helyek tárolására használhatunk egy másik egyirányú listát, amelyet ugyanazokon a tömbökön ábrázolunk. Ebben az esetben a tömb minden eleme vagy a listába vagy szabad elemek listájába tartozik. A következő ábra mutatja az előző példát a szabad elemek listájával kiegészítve:
A szabad elemek listájában két műveletet valósítjuk meg: egy elem bevitele (egy az eredeti listában törölt elem által foglalt területet szabadítunk fel) és egy elem kivitele (egy az eredeti listába beszúrandó elem számára foglalunk területet). Egy elem (H) bevitele a szabad elemek listájába: Bevitel (H): KOV(H):=SZ_FEJ SZ_FEJ:=H Eljárás vége. Egy elem kivitele a szabad elemek listájából: Kivitel: H:=SZ_FEJ Ha (H <> 0) SZ_FEJ:=KOV[SZ_FEJ] Ha vége Return H Eljárás vége. Nem nehéz észrevenni, hogy a szabad elemek listája veremként működik, azaz az utolsó bevitt elemet veszünk ki elsőként. Az utolsó bevitt elem az első elem, amelyre a SZ_FEJ változó mutat. A fentiek után egy X elem beszúrását a listába illetve törlését a listából két lépésben hajtunk végre: Beszúrás:
1. H := Kivitel
// Kiveszünk egy X számára lefoglalt elemet a szabad // elemek listájából
2. Új Elem (K, H, X)
// Az új elem beillesztése a K. után a lefoglalt, fizikailag // H. helyre
1. Törlés (K, H)
// A K. elem törlése, H-ban kapjuk vissza a fizikai címét, // azaz az általa foglalt elem a tömbön belül // A fizikailag H. elem, azaz a tömb H. elem bevitele a // szabad elemek listájába
Törlés:
2. Bevitel (H) Megjegyzések:
1. Bár a mutatott példák egyirányú listák, tárgyalásunk érvényes a kétirányú listákra is. A kétirányú listák esetében a szabad elemek listája nem használja az ELO tömböt. 2. A megadott Törlés eljárások egy paraméterrel rendelkeznek, így módosításra szorulnak, hogy a törölt paraméter címét adják vissza. A módosítás egyszerű. Megmutatjuk Törlés eljárások módosítását, amely érvényes az egyirányú listák és a kétirányú listák esetén is: Törlés (K, H): Ha (K=1) akkor // Ha a lista első elemét töröljük H:=FEJ // Az 1. (törlendő) elem címe . . // Ez a rész változatlan marad . különben // Ha nem az első elemét töröljük, akkor keressük a K-1. elemet Első (MUT): I:=1 Ciklus, amíg I
Az informatikában, matematikában fontos szerepet játszanak azok az adatszerkezetek, amelyeknek az elemei között a szerkezeti összefüggések fával ábrázolhatóak. Vizsgáljuk meg a következő egyszerű aritmetikai kifejezést: a*b+c Ennek kiszámítási szabályát bináris fával ábrázolhatjuk: +
c
* a
b
Ebben a fejezetben csak olyan fákkal foglalkozunk, melyeknél egy elemből (csúcsból) legfeljebb két él indul ki - ezt bináris fának nevezzük. Azt az elemet (csúcsot), amelybe nem fut be él a fa gyökérelemének, vagy egyszerűen a fa gyökerének nevezzük. A gyökér kivételével minden elembe (csúcsba) pontosan egy él fut be. Ha egy csúcsból él vezet egy másik csúcsba, akkor az elsőt a második szülőjének, a másodikat az első gyerekének nevezik. Egy fa minden eleme (csúcsa) egy részfának a gyökere. A részfa tartalmazza az eredeti fát minden élét és csúcsát, amely a szóban forgó csúcsból kiindulva és az éleket folytatva elérhető. A bináris fákon szokás beszélni egy csúcs baloldali ill. jobboldali részfájáról. Egy csúcsból maximum két él indulhat, egy baloldali él és egy jobboldali él. A baloldali részfája az, amelynek gyökere az a csúcs, amelybe a baloldali éle fut be. A jobboldali részfája az, amelynek gyökere az a csúcs, amelybe a jobboldali éle fut be.
Ábrázolás: A bináris fát, leggazdaságosabban láncolt ábrázolással jeleníthetjük meg. Minden adatelemet ADAT [1..N]vektorban tároljunk s ezeket két mutatóval egészítünk ki. (BAL [1..N], JOBB [1..N]), melyek megadják az elemtől jobbra ill. . balra elhelyezkedő elem címét. A GYÖKÉR nevű változó fogja tárolni a gyökérelem címét. Ha egy mutató értéke 0, az jelentse azt, hogy a fa arra nem folytatódik! Bejárás : Azt jelenti, hogy valamilyen irányt szigorúan betartva bejárjuk a fa minden elemét. A bináris fa bejárásakor három stratégiát követhetünk: - csúcs, baloldali részfa, jobboldali részfa (középső, baloldal, jobboldal) KBJ - baloldali részfa, csúcs, jobboldali részfa (baloldal, középső, jobboldal) BKJ - baloldali részfa, jobboldali részfa, csúcs (baloldal, jobboldal, középső) BJK Nézzük az egyes bejárásokat! Mindegyiknek a GYÖKÉR címet kell átadni paraméterként, ha az egész fát szeretnénk bejárni, különben azt a részfát járja be, amelynek a kapott címhez tatozó csúcs a gyökere. KBJ-rekurzív-bejárás (MUT): KI: ADAT[MUT] Ha (BAL[MUT]<>0) akkor KBJ-rekurzív-bejárás(BAL[MUT]) Ha (JOBB[MUT]<>0) akkor KBJ-rekurzív-bejárás(JOBB[MUT]) Eljárás vége. BKJ-rekurzív-bejárás (MUT): Ha (BAL[MUT]<>0) akkor BKJ-rekurzív-bejárás(BAL[MUT]) KI: ADAT[MUT] Ha (JOBB[MUT]<>0) akkor BKJ-rekurzív-bejárás(JOBB[MUT]) Eljárás vége. BJK-rekurzív-bejárás (MUT): Ha (BAL[MUT]<>0) akkor BJK-rekurzív-bejárás(BAL[MUT]) Ha (JOBB[MUT]<>0) akkor BJK-rekurzív-bejárás(JOBB[MUT]) KI: ADAT[MUT] Eljárás vége. A fenti algoritmusok rekurzív fabejárási algoritmusok, most nézzük bonyolultabb, de hatékonyabb nem rekurzív eljárásokat. Felírjuk nem rekurzív KBJ bejárást és a nem rekurzív BKJ bejárást. Az algoritmushoz szükség van egy veremre, amit már fentebb ismertettünk. A BJK nem rekurzív bejárás algoritmus megírását az olvasóra bízzuk! KBJ-bejárás (MUT): VEREMBE(-1) Ciklus amíg MUT >= 0 Ciklus amíg MUT > 0 KI: ADAT[MUT]
Ha (JOBB[MUT]<>0) akkor VEREMBE(JOBB[MUT]) MUT:=BAL[MUT] Ciklus vége VEREMBOL(MUT) Ciklus vége. Eljárás vége. BKJ- bejárás (MUT): VEREMBE(-1) Ciklus amíg MUT >= 0 Ciklus amíg MUT > 0 VEREMBE(MUT) MUT:=BAL[MUT] Ciklus vége. VEREMBOL(MUT) HA (MUT > 0 )akkor Ki: ADAT[MUT] : MUT:= JOBB[MUT] Ciklus vége. Eljárás vége. Bináris keresőfák Egy bináris fa bináris keresőfa, ha minden csúcs esetén a csúcson lévő adat nagyobb vagy egyenlő, mint a baloldali részfájához tartozó csúcsokon lévő adatok, és kisebb vagy egyenlő, mint a jobboldali részfájához tartozó csúcsokon lévő adatok.
A bináris keresőfa BKJ bejárása növekvő sorrendben írja ki a fa elemeit. Műveletek a bináris kereső fában: Egy X elem keresése: Először nézzük meg egy rekurzív keresést! Két paramétere van az eljárásnak, a bináris keresőfa – amelyben keresünk – gyökerének a címe MUT és a keresendő X elem; ELEM, a cím, amelyen találtuk a keresett elemet, azaz a visszaadandó cím. Fa-rekurzív-keresés (MUT, X): Ha (MUT = 0 vagy ADAT[MUT]=X) akkor ELEM = MUT
különben Ha (ADAT[MUT]>X) akkor ELEM := Rekurzív-keresés(BAL(MUT), X) különben ELEM := Rekurzív-keresés(JOBB(MUT), X) Ha vége Ha vége Return ELEM Eljárás vége. Most nézzük meg egy nem rekurzív, iteratív keresést: Fa-nem-rekurzív-keresés (MUT, X): Ciklus amíg MUT <> 0 és ADAT[MUT] <> X Ha (ADAT[MUT]>X) akkor MUT:=BAL[MUT] különben MUT:=JOBB[MUT] Ha vége Ciklus vége ELEM:=MUT Return ELEM Eljárás vége. Minimum és maximum keresése: Egy paramétere van az eljárásnak, a bináris keresőfa – amelyben keresünk – gyökerének a címe MUT. ELEM, a cím, amelyen találtuk a minimumot vagy a maximumot. Fa-minimum-keresés (MUT): Ciklus amíg BAL[MUT] <> 0 MUT:=BAL[MUT] Ciklus vége ELEM:=MUT Return ELEM Eljárás vége. Fa-maximum-keresés (MUT): Ciklus amíg JOBB[MUT] <> 0 MUT:=JOBB[MUT] Ciklus vége ELEM:=MUT Return ELEM Eljárás vége. Új X elem beszúrása a fizikailag H. helyre: Az X elem beszúráshoz a gyökértől lefelé haladunk balra vagy jobbra, attól függően, hogy a beszúrandó elem kisebb vagy nagyobb, mint az adott csúcson lévő elem. Ha nem tudunk tovább haladni, mert abba az irányba, amelybe kellene nincs elem (0 a mutató), akkor pont ott kell beszúrni az X elemet. Fa-beszúr (X, H): MUT1:=0;
MUT:=GYÖKÉR Ciklus amíg MUT <> 0 MUT1:=MUT Ha (X < ADAT[MUT]) akkor MUT:=BAL[X] különben MUT:=JOBB[X] Ha vége Ciklus vége Ha (MUT1=0) akkor GYÖKÉR = H // Üres fa esete különben Ha (X < ADAT[MUT1]) akkor BAL[MUT1]:=H különben JOBB[MUT1]:=H Ha vége Ha vége ADAT[H]:=X BAL[H]:=0 JOBB[H]:=0 Eljárás vége. Egy X elem törlése: Egy X elem törlése valamivel bonyolultabb művelet. Először megnézzük a törlendő elemnek a baloldali és a jobboldali mutatóját. Ha legalább az egyik nem 0, akkor elegendő lesz a törlendő elemet „kivágni”. Ha egyik sem 0, akkor „kivágjuk” a törlendő elemet sorrendben követő első elemet. A „kivágás” úgy történik, hogy a „kivágandó” elem gyerekét (csak egy lehet) megfelelően kapcsoljuk hozzá a szülőjéhez. Végül, ha a „kivágott” elem nem a törlendő elem, akkor a törlendő elem helyére a „kivágott” elem kerül. Fa-törlés (X): Fa-nem-rekurzív-keresés(GYÖKÉR, X, ELEM) // Az X címének keresése Ha (BAL[ELEM] = 0 vagy JOBB[ELEM] = 0) akkor KIVÁG:= ELEM különben Fa-következő(ELEM, KIVÁG) Ha vége Ha (BAL[KIVAG] <> 0) akkor KIVÁG_GYEREKE:=BAL[KIVAG] különben KIVÁG_GYEREKE:=JOBB[KIVAG] Ha vége Szülő(KIVÁG, SZÜLŐ) Ha (SZÜLŐ = 0) akkor GYÖKÉR:=KIVÁG_GYEREKE különben Ha (KIVÁG = BAL[SZÜLŐ]) akkor BAL[SZÜLŐ]:=KIVÁG_GYEREKE különben JOBB[SZÜLŐ]:=KIVÁG_GYEREKE Ha vége Ha vége Ha (ELEM <> KIVÁG) akkor ADAT[ELEM]:=ADAT[KIVÁG] Ha vége Eljárás vége Az algoritmusban alkalmazott Fa-következő és Szülő eljárások megírását az olvasóra bízzuk Az Fa-következő eljárás első paramétere egy cím, amelynek elemet növekvő sorrendben követő elem címét adja vissza a második paraméterben. A Szülő eljárás első paramétere egy
cím, amelynek eleme szülőjének a címét adja vissza a második paraméterben. A szülő eljárás elkerülhető, ha a bináris fa ábrázolására egy SZÜLŐ[1..N] tömböt is alkalmazzuk. Megjegyezzük még, hogy a memória kezelésére használhatunk, a listák esetéhez hasonlóan, egy a szabad elemeket tartalmazó listát. A Fa-törlés eljárást kiegészítjük egy második paraméterrel, amelyben visszaadja a kivágott elem címét (KIVAG) felszabadítására. Tetszőleges leágazásszámú gyökeres fák ábrázolása: A bináris fák ábrázolási módszere természetesen kiterjeszthető az olyan esetekre, amikor a gyerekek maximális száma egy ismert k érték. Ilyenkor a BAL és JOBB tömbök helyett, a GYEREK1, GYEREK2, ..., GYEREKk tömböket használjuk. Azonban, ha a gyerekek maximális számát nem ismer, akkor más ábrázolási módszer szükséges. Egy jó megoldás lehet az úgynevezett bal-gyerek, jobb-testvér ábrázolás, amelynek lényege, hogy az ADAT[1..N] tömbön kívül további két tömböt használunk: – BAL-GYREK[1..N]: BAL-GYEREK[I] az I arra a gyerekére mutat, amely baloldali szélén áll, – JOBB-TESTVÉR[1..N]: JOBB-TESTVÉR[I] az I arra a testvérére mutat, amely I-től közvetlenül jobbra van. A következő ábra egy példát mutat egy fáról és bal-gyerek, jobb-testvér ábrázolásáról.
PROBLÉMAOSZTÁLYOK A következő táblázatban különböző időigényeket kifejező függvények viselkedését hasonlítjuk össze: TÁBLAZAT a) Aszimptotikus viselkedés (végrehajtási idő növekedése a bemenet mértékének a növekedésével) ALGORITMUS Idő ( µsec-ban) A bemenet mértéke és a hozzátartozó végrehajtási idő
1
2
33 n
3
46 n log n
4
13 n
2
5
3,4 n
3
2n
n = 10
0,00033 sec 0,0015 sec
0,0013 sec
0,0034 sec 0,001 sec
n = 100
0,0033 sec
0,03 sec
0,13 sec
3,4 sec
n = 1 000
0,033 sec
0,45 sec
13 sec
n = 10 000
0,33 sec
6,1 sec
22 perc
n = 100 000 3,3 sec
1,3 perc
4 . 106 év
0,94 óra 39 nap
1,5 nap
108 év
b) A maximális bemenet mértékének növekedése a rendelkezésre álló végrehajtási idő növekedésével ALGORITMUS Idő ( µsec -ban) Maximális bemenet
1 sec 1 perc
1
2
3
4
5
33 n
46 n log n
13 n2
3,4 n3
2n
30 000
2 000
280
67
20
1 800 000
82 000
2 200
260
26
A táblázat a) részén látható a végrehajtási idő növekedése a bemenet értékének a növekedésével a különböző függvények esetében. Érdekes figyelni, hogy a Θ(n) és Θ(n log n) függvények a nagyobb szorzók ellenére a bemenet nagy értékeire gyorsabbak a többinél. A táblázat b) részén látható, hogy a végrejatási idő nővekedése, vagy egy gyorsabb számítógép használata, hogyan befolyasolja a máximális bemenet mértékét. A Θ( n ) és Θ( n log n ) függvények nagy szorzóinak nincs jelentőségük a vizsgált összefüggésben. Mind a két esetben megfigyelhető az 5 algoritmus „rossz” viselkedése.
Problémaosztályok: P és NP osztályok. NP-teljesség A P és NP problémaosztályokat informálisan vezetjük be. A P osztály a polinom időben megoldható problémákból áll, azaz olyan problémákból, amelyekhez megadható olyan k konstans, hogy a probléma bármelyik n hosszúságú bemenet esetén O(nk) idő alatt megoldható. Az ebben a jegyzetben eddig tárgyalt problémák P osztálybeliek. Azonban léteznek problémák, amelyek nehezebbek, olyanok is, amelyek egyáltalán nem oldhatók meg számítógéppel a rendelkezésre álló időtől függetlenül, és olyanok is, amelyek megoldhatók, de nem polinomiális időben. Az NP osztály bevezetése előtt nézzük meg a gráfok alapfogalmait és néhány a gráfokkal kapcsolatos problémákat. Irányított gráf: Egy G = (V, E) rendezett pár, ahol – V a G csúcsainak véges halmaza, – E a G éleinek halmaza, egy V-n értelmezett bináris reláció. Irányítatlan gráf: Egy G = (V, E) rendezett pár, ahol – V a G csúcsainak véges halmaza, – E a G éleinek halmaza, amelynek elemei V kételemű részhalmazai. A követkző ábra irányított és irányítatlan gráfokat mutat.
Az egyszerűség és egységes jelölés kedvéért az irányítatlan gráfok esetén is az élek jelölésére az (u,v) szimbólumot fogjuk használni az {u,v} helyett.
A G = (V, E) gráfban az u csúcsot az u' csúccsal összekötő k hosszúságú úton a csúcsoknak egy olyan véges sorozatát értjük, amelyre u = v0, u' = vk és (vi-1,vi) élek (i = 1, 2, …, k). Az út a v0, v1, …, vk csúcsokat és (v0,v1), (v1,v2), …, (vk-1,vk) éleket tartalmazza. Egy út egyszerű, ha a benne foglalt csúcsok páronként különbözők. A VIII.2 ábra irányított gráfján az <1,2,5,4> 3 hosszúságú egyszerű út, a <2,5,4,5> nem egyszerű út. Egy utat körnek nevezünk, ha kezdő és befejező csúcsa megegyezik, azaz v0 = vk. Egy kör egyszerű, ha v1, v2, …, vk különböző csúcsok, azaz vi ≠ vj, minden 1 ≤ i < j ≤ k esetén. Egy gráfot összefüggő gráfnak nevezünk, ha út köti össze bármelyik két csúcsát. Néhány gráfelméleti probléma és osztálybeli hovatartozásuk: Legrövidebb út: Adott egy G = (V, E) irányított gráf és két csúcsa v 1 és v2, meg kell találni a G gráfon v1-ből v2-be vezető legrövidebb utat. A legrövidebb út problémája polinomiális időben oldható meg, azaz a legrövidebb út problémája P-beli. Leghosszabb út: Adott egy G = (V, E) irányított gráf és két csúcsa v1 és v2, meg kell találni a G gráfon a v1-ből v2-be vezető leghosszabb utat. A leghosszabb út problémája igen nehéz, sőt, már annak eldöntése is NP-teljes, hogy létezik-e egy gráfban egy adott k számú élnél többet tartalmazó egyszerű út. Az NP osztály azokból a problémákból áll, amelyhez létezik olyan algoritmus, amely polinomiális időben el tudja dönteni a probléma egy lehetséges megoldásáról, hogy valóban megoldás-e vagy sem. Az NP osztály elnevezése a „nondeterministic polinomial”, azaz a nem determinisztikusan polinomiális rövidítése. Az NP osztály egy ekvivalens definíciója az, hogy egy probléma NPbeli, ha létezik egy nem determinisztikus algoritmus, amelynek a segítségével a probléma megoldható polinomiális időben. A nem determinisztikus algoritmus eltér az eddig alkalmazott algoritmus fogalmától. A nem determinisztikus algoritmus esetén egy lépés vagy művelet végrehajtása után a következő művelet nem egyértelműen meghatározott, hanem több művelet közül választható. Így egy nem determinisztikus algoritmusnak több végrehajtási ága lehet nyitva egy időben. A nem determinisztikus algoritmus polinomiális idejű, ha minden bemenetre létezik egy O(nK) végrehajtási idejű ág, amely megadja a probléma megoldását. Informális tárgyalásunkban világosan látszik, hogy P ⊆ NP, hiszen ha egy probléma megoldható polinomiális időben, akkor természetesen egy lehetséges megoldásról eldönthető, hogy megoldás-e vagy sem, ugyanis elegendő előállítani a megoldást és megnézni, hogy megegyezik-e a vizsgált lehetséges megoldással. Itt az NP osztály első definícióját használtuk, de ha a másodikat nézzük, akkor nyilvánvaló, hogy ha egy probléma megoldására létezik polinomiális idejű (determinisztikus) algoritmus, akkor ugyanaz az algoritmus tekinthető a problémát megoldó polinomiális idejű nem determinisztikus algoritmusnak is, hiszen az algoritmusok (determinisztikus algoritmusok) speciális esetei a nem determinisztikus algoritmusoknak. Már tudjuk, hogy P ⊆ NP, de mit lehet mondani a fordított állításról? Azaz, fennáll-e vagy sem NP ⊆ P? Az olvasó talán azt sejti, hogy nem, mert különben azonnal következne, hogy P = NP, és egy és csak egy osztály lenne a kettő. A válasz talán meglepő: bár sejtjük, hogy NP ⊆ P nem áll fenn, azaz sejtjük, hogy P ⊂ NP, a bizonyítása még a mai napig nem sikerült.
Egy probléma NP-teljes probléma, ha legalább olyan nehéz, mint bármelyik más NP-beli probléma. Ez azt jelenti, hogy ha sikerülne bebizonyítani egy NP-teljes problémáról, hogy polinomiális időben megoldható, akkor minden NP-beli probléma polinomiális időben megoldható lenne és P = NP igaz lenne. Hogyan látható be, hogy egy probléma NP-teljes? Ez a feladat nem mondható könnyűnek és túl lépi ennek a jegyzetnek a kereteit. Annyit teszünk hozzá, hogy az A probléma NPteljességének a bizonyításához szokás indulni egy ismert NP-teljes B problémából és megkeresni egy algoritmust, amely a B probléma példányait átalakítja az A probléma példányivá polinomiális időben. Ha sikerül ilyen algoritmust találni, akkor készen is vagyunk, mert ha sikerülne bebizonyítani, hogy A megoldható polinomiális időben, akkor az átalakító algoritmus és az A-t megoldó algoritmus egymásutáni alkalmazásával a B probléma is megoldható lenne polinomiális időben, és mivel B NP-teljes, akkor P = NP adódik azonnal. Tehát, ha A P-beli lenne, akkor P = NP következne, vagyis A NP-teljes. Ez a módszer egy ismert NP-teljes problémából indul, de szükséges bebizonyítani az NP-teljességét valamelyik problémának más NP-teljes probléma kihasználása nélkül, hogy azután alkalmazható legyen. Ilyen NP-teljes probléma, amely NP-teljességének ismert bizonyítása van más NP-teljes probléma felhasználása nélkül, a Boole-hálózatok kielégíthetőségének a problémája („circuit satisfiability”). Az NP-teljesség alapjainak az ismerete nagyon fontos szerepet játszik a gyakorlatban. Ha olyan problémát kell megoldanunk, amelyről tudjuk, hogy NP-teljes, akkor legtöbbször jobban tesszük, ha egy közelítő, elfogadhatóan jó megoldást szolgáló algoritmust alkalmazunk, és nem a legjobb megoldást szolgáló algoritmust keressük, alkalmazzuk.
Formális nyelvek. Turing-gépek (Nem vizsgaanyag!) Ebben az alfejezetben bevezetjük a formális nyelvek és a Turing-gépek fogalmát. A formális nyelvek és a Turing-gépek segítségével matematikailag formálisan tárgyalhatjuk az algoritmusokat, a P és NP osztályokat, az NP-teljességet. Vezessük be a formális nyelv fogalmát: Egy ábécé szimbólumok véges halmaza. Σ = { s1, s2, … , sn }, ahol si (1 ≤ i ≤ n) egy szimbólum. Példák: Σ1 ={0,1}, Σ2 ={0,1,2,3,4,5,6,7,8,9}, Σ3 ={a,b,c,d,e,...,z}. Egy szó egy ábécé szimbólumaiból álló véges sorozat (üres is lehet és tartalmazhat ismételt szimbólumokat). Σ* jelöli a Σ ábécé szimbólumaiból alkotható összes szavak halmazát, más szavakkal a Σ ábécé fölötti összes szavak halmazát. |x| jelöli az x szó hosszúságát, amely az xet alkotó szimbólumok száma (egy szimbólum annyiszor számítandó, ahányszor szerepel). Példák: Σ1 ={0,1}, Σ1* = {e, 0, 1, 00, 01, 10, 11, 000, 001, 011, 100, 101, 110, 111, ..}, ahol e az üres szó, |e| = 0, |0| = |1| = 1, |00| = |01| = |10| = |11| = 2, |000| = |001| = |010| = |011| = |100| = |101| = |110| = |111| = 3. Egy L nyelv a Σ ábécé fölött a Σ ábécé fölötti szavaknak egy halmaza. L egy nyelv Σ fölött akkor is csak akkor, ha L ⊆ Σ*. Példa: Σ1 ={0,1}, L1 = {0, 1, 01, 10} (véges nyelv), L2 = {e, 01, 0011, 000111, … } = { 0n1n : n≥0} (végtelen nyelv).
Szavak konkatenációja: Legyenek x és y két szó, az x és y konkatenációja az az xy szó, amelyet úgy kapunk, hogy y szimbólumait hozzáadjuk az x végéhez ugyanabban a sorrendben, amelyben az y szóban szerepeltek. ex = xe = x minden x szóra. |xy| = |x| + |y|. Nyelvek konkatenációja: Legyenek L1 és L2 két nyelv, L1.L2 = { xy : x ∈ L1 és y ∈ L2 } az L1 és L2 nyelvek konkatenációja. Példa: L1 = {0, 1, 01, 10}, L2 = {e, 01, 0011}, L1.L2 = {0, 001, 00011, 1, 101, 10011, 01, 0101, 010011, 10, 1001, 100011}. Egy nyelv hatványai: Legyen L egy nyelv, L hatványainak definíciója: L0 = {e}, L1 = L, L2 = L.L, L3 = L.L2, … , Ln = L.Ln-1. Példa: L1 = {0, 1, 01, 10}, L10 = {e}, L11 = {0, 1, 01, 10}, L12 = {00, 01, 001, 010, 10, 11, 101, 110, 011, 0101, 0110, 100, 1001, 1010}. Egy nyelv Kleene-féle lezártja: Legyen L egy nyelv, akkor L Kleene-féle lezártja: ∞ L* = ∪ Li i=0 Egy nyelv Kleene-féle pozitív lezártja: Legyen L egy nyelv, akkor L Kleene-féle pozitív lezártja:: ∞ + L = ∪ Li i=1 Megjegyzés: 1.
Legyen L = Σ , azaz, az ábécé, vagyis az összes egy hosszúságú szavak halmaza, akkor: L* = Σ* , azaz az összes Σ fölötti szavak halmaza, L+ = Σ+ , azaz az összes Σ fölötti szavak halmaza kivéve az üres szót.
2.
Legyen L egy nyelv, amely tartalmazza az üres szót, akkor L* = L+. Legyen L egy nyelv, amely nem tartalmazza az üres szót, akkor L+ = L* \ {e}.
A formális nyelvek segítségével tudjuk kódolni a problémák példányait. Ehhez elegendő használni a Σ = {0, 1} ábécét. Ha gondolkozunk egy eldöntési problémán, azaz, adott egy lehetséges megoldás, el kell dönteni, hogy valóban megoldás-e, akkor a lehetséges megoldások halmaza Σ*, a megoldások halmaza pedig egy Σ feletti L nyelv, mégpedig: L = { x ∈ Σ* : T(x) = 1 } ahol T egy algoritmus, amely el tudja dönteni, hogy x megoldás-e vagy sem (az eredmény 1 vagy 0). Az algoritmusok egyik formális modellje a Turing-gépek. Mint látni fogjuk, egy Turing-gép által végrehajtott lépések sorozata egy algoritmust valósít meg, azaz egy Turing-gép definiál egy algoritmust. A Church-Tézis ennek az állításnak az inverze, azaz, minden algoritmushoz megadható egy Turing-gép, amely megvalósítja az algoritmust. Az algoritmus fogalma informális volta miatt a Church-tézis nem bizonyítható, de elfogadása ésszerűnek tűnik, ha
tudjuk, hogy nem sikerült megtalálni a Turing-gépen nem megvalósítható algoritmust, valamint azt, hogy a szakirodalomban használt különböző modellek – véletlen elérésű számítógép (RAM), a rekurzív függvények elmélete, Markov normál algoritmusai, Postgépek – ekvivalensek a Turing-gépekkel. Itt mindjárt meg kell jegyezni, hogy a Turing-gép annyiban különbözik az algoritmusok általunk használt informális definíciójától, hogy a Turing-gép egy nem determinisztikust algoritmust valósít meg, amelynek nincs biztosítva a befejeződése véges időn belül. Vezessük be a Turing gépeket: Turing-gép: MT = ( Σ, S, δ, ∆, q0, F ), ahol Σ a szalag ábécéje; S az állapotok nem üres, véges halmaza; δ : S x ( Σ ∪ { ∆ } ) → P( S x Σ x { R, L, N } ) az átmenetfüggvény – P argumentumának hatványhalmazát jelöli; ∆ ∉ Σ az üres speciális szimbóluma; q0 ∈ S a kezdő állapot, amelyből indul a Turing-gép működése; és F ⊆ S a végállapotok halmaza. A leírt Turing-gép nem determinisztikus Turing-gép. AVIII.3 ábra bemutat egy Turing-gépet.
A Turing gép által elfogadott nyelv: A Turing-gép egy konfigurációja: xpy ∈ Σ*.S.Σ*, ahol x az éppen olvasás alatt álló szimbólumtól balra álló szó (az olvasás alatt álló szimbólum nem tartozik hozzá), y az éppen olvasás alatt álló szimbólummal kezdődő és az első jobbra eső ∆-ig (de ez nincs benne) terjedő szó, és p a gép belső állapota. A gép átmehet egy konfigurációból egy másikba, ha a második konfiguráció elérhető az átmenetfüggvény alkalmazásával az első konfiguráción, jelölése X MT⇒ Y, ahol X és Y konfigurációk. (q, b, M ) ∈ δ(p, a) azt jelöli, hogy a p ∈ S állapotban, az a ∈ Σ vagy a = ∆ olvasásával, a gép átmehet a q ∈ S állapotba, kiírni b ∈ Σ az olvasott karakter helyére és jobbra mozgatni az olvasófejet (M = R), balra mozgatni az olvasófejet (M = L) vagy helyben hagyni az olvasófejet (M = N). Az átmenet reláció reflexív és tranzitív lezártját, az úgynevezett „átmenet 0 vagy több lépésben”-t, X MT⇒* Y (X y Y ∈ Σ*.S.Σ*) -vel jelöljük. Egy xpay konfiguráció végkonfiguráció, ha δ(p, a) = ∅. A Turing-gép akkor fogad egy szót, ha a kezdő q0x konfigurációból kiindulva létezik egy átmenet 0 vagy több lépésben egy yqz végkonfigurációba, ahol q ∈ F (végállapot), azaz, a Turing-gép megáll végállapotban. A Turing-gép által elfogadott nyelv: L(M ) = { x | x ∈ Σ*, q0x MT⇒* yqaz, q ∈ F y δ(q, ) = ∅ }. Determinisztikus Turing-gép: Egy Turing-gép determinisztikus, ha minden elérhető konfigurációban létezik legfeljebb egy lehetséges átmenet.
Állítás: Minden nem determinisztikus MT Turing-géphez létezik egy determinisztikus MT' Turing-gép, amely ugyanazt a nyelvet fogadja el, mint az MT, azaz L(M ) = L(MT'). Turing-gép által végrehajtott lépések száma egy szó felismeréséhez: Egy determinisztikus Turing-gépen a végrehajtott lépések száma egy szó felismeréséhez egyértelműen meghatározott a végrehajtott átmenetek számával. Egy nem determinisztikus Turing-gépen egy konfigurációból több átmenet is lehetséges, így a szó felismeréséhez szükséges lépések száma a legrövidebb út átmeneteinek a száma, amely a kezdő konfigurációból indulva felismeri a szót. Ha úgy képzeljük el a nem determinisztikus Turinggép működését, hogy amikor több átmenet közül választhat, akkor mindegyiket elvégzi egy lépésben, és úgy folytatja a működését minden megnyitott úton, és akkor áll meg, amikor elér egy végkonfigurációt, a végrehajtott lépések száma megegyezik az előbb definiálttal. Egy Turing-gép akkor fogad el egy nyelvet polinomiális időben, ha a nyelv minden szavát felismeri polinomiális időben. Ezek után formálisan definiálhatjuk a már ismert P és NP osztályokat: P osztály: az összes nyelvek halmaza, amelyet egy determinisztikus Turing-gép elfogad polinomiális időben. NP osztály: az összes nyelvek halmaza, amelyet egy nem determinisztikus Turing-gép elfogad polinomiális időben.
