XI. Erdélyi Tudományos Diákköri Konferencia Kolozsvár, 2008. május 23–24.
KUPAC TĺPUSÚ ADATSZERKEZETEK
Témavezető
Szerző
Dr. Ionescu Klára, adjunktus
Molnár Andrea-Éva
Babeş-Bolyai Tudományegyetem
Babeş-Bolyai Tudományegyetem
Matematika-Informatika Kar
Matematika-Informatika Kar
Programozási nyelvek és módszerek tanszék
Matematika-Informatika Szak
Kolozsvár, 2008
III. év
Tartalomjegyzék 0 1 2
KIVONAT.............................................................................................................. 3 BEVEZETÉS ......................................................................................................... 3 BINÁRIS KUPACOK........................................................................................... 4 2.1 2.2 2.3 2.4 2.4.1 2.4.2 2.4.3
3
A BINÁRIS KUPAC FOGALMA ........................................................................... 4 MINIMUM – ÉS MAXIMUM KUPACOK, KUPAC-TULAJDONSÁG.............. 5 KUPAC MAGASSÁGA........................................................................................... 6 NÉHÁNY ALAPVETŐ ALGORITMUS ................................................................ 6 A KUPAC TULAJDONSÁG FENNTARTÁSA .................................................7 A KUPAC ÉPĺTÉSE.............................................................................................9 KUPACRENDEZÉS ..........................................................................................12
KUPAC TĺPUSÚ ADATSZERKEZETEK ALKALMAZÁSA ...................... 17 3.1
ELSŐBBSÉGI SOROK.......................................................................................... 17
3.1.1 AZ ELSŐBBSÉGI SOR FOGALMA ................................................................17 3.1.2 ELSŐBBSÉGI SOROK ALKALMAZÁSI TERÜLETEI .................................18 3.1.3 NÉHÁNY ALAPVETŐ ALGORITMUS BINOMIÁLIS KUPACOKKAL VÉGEZHETŐ MŰVELETEK ELVÉGZÉSÉHEZ ..........................................................18
4
BINOMIÁLIS KUPACOK ................................................................................ 22 4.1 BINOMIÁLIS FÁK ................................................................................................ 22 4.2 BINOMIÁLIS KUPAC FOGALMA...................................................................... 23 4.3 NÉHÁNY ALAPVETŐ ALGORITMUS BINOMIÁLIS KUPACOKKAL VÉGEZHETŐ MŰVELETEK ELVÉGZÉSÉHEZ .......................................................... 24 4.3.1 4.3.2 4.3.3
5
AZ OKTATÓPROGRAM ISMERTETÉSE.................................................... 28 5.1 5.2
6
ÜRES BINOMIÁLIS KUPAC LÉTREHOZÁSA .............................................25 LEGKISEBB ELEM MEGKERESÉSE.............................................................25 MÁS ALGORITMUSOK...................................................................................26
A MULTIMÉDIÁS OKTATÓPROGRAMOK MEGJELENÉSE......................... 28 AZ OKTATÓPROGRAM FELÉPĺTÉSE. MÓDSZERTANI SZEREP ................ 29
KÖNYVÉSZET ................................................................................................... 30
2
0 KIVONAT Ezen dolgozat célja a kupac típusú adatszerkezetek bemutatása, rávilágítva ezek fontosságára. A bináris kupacok segítségével egy hatékony rendezési algoritmus írható, de használják elsőbbségi sorok kezelésére is. A binomiális kupacok használata általában akkor javasolt, ha gyakran kell az alkalmazásban kupacokat egyesítenünk. Egy oktatóprogramon keresztül bemutatásra kerülnek ezen adatszerkezetek. A személyi számítógépek rohamos elterjedése módot teremtett a pedagógus számára, hogy a tanórán éljen a multimédiás számítógépek, oktatóprogramok, valamint az internet nyújtotta lehetőségekkel. Ezen oktatóprogram segítséget nyújthat a mai pedagógusnak a kupac típusú adatszerkezetek oktatásában, ugyanakkor az otthoni önálló tanulás egyik fontos eszköze lehet, mind középiskolai -, mind egyetemi hallgatók számára. Azonban nem szabad elfeledkeznünk arról a tényről, hogy egy számítógép sohasem helyettesítheti a tanárt, főleg nem a középiskolában.
1 BEVEZETÉS A számítástechnika mai állása megköveteli a programozótól a minél jobb és gyorsabb alkalmazások/programok írását. Ebben nyújtanak segítséget a kupac típusú adatszerkezetek. A „kupac”(heap) elnevezés a kupacrendezéssel kapcsolatban jelent meg először. A Lisp és C nyelvekben egészen más jelentéssel bír, mint a kupacrendezés esetében („hulladékgyűjtéses memória-kezelés” – garbage-collected storage). Ugyanakkor ezt a kifejezést memória-foglalással kapcsolatban is használják. Ezen dolgozatban a kupac elnevezés, mint adatszerkezet fog szerepelni, hisz a cél ezek bemutatása. A kupac egy speciális “fa alapú“ adatszerkezet, mely kielégíti az úgynevezett kupactulajdonságot: ha a B csúcs fia az A csúcsnak, akkor érték(A) ≥ érték(B). Ezen tulajdonság maga után vonja azt a tényt, miszerint a legnagyobb értékű csúcs mindig a gyökérben található. Ekkor maximum-kupacról beszélünk. Ha azonban a rendezés irányát megfordítjuk (érték(A)≤érték(B)), akkor a minimum-kupacokat definiáltuk. Ekkor a legkisebb elem kerül a gyökérbe. A kupac típusú adatszerkezeteknek rengeteg fajtája ismert, beszélhetünk: bináris -, binomiális -, Fibonacci -, intervallum -, párosítós -, min-max -, valamint r - kupacokról, stb.
3
2 BINÁRIS KUPACOK 2.1 A BINÁRIS KUPAC FOGALMA A kupac adatszerkezet hatékonyan implementálható bináris kupac segítségével. A bináris kupac adatszerkezet úgy tekinthető, mint egy majdnem teljes bináris fa, melyet egy tömbben ábrázolunk. 1
20 2
3
15
13
4
5
6
7
9
5
12
8
8
9
10
7
3
1
i) A kupac bináris faként ábrázolva 1
2
9
10
20 15 13 9 5 12 8 7 3
1
ii)
3
4
5
6
7
8
A kupac tömbként ábrázolva
A kupac elemeit egy bináris fában tároljuk. A bináris fa egy olyan fa, melynek csúcsai szinteken helyezkednek el. A fa legalacsonyabb szintjét kivéve, mindenhol teljesen kitöltött. A legalacsonyabb szinten csak egy adott csomópontig vannak elemek. A bináris fában mindig balról jobbra haladva töltjük ki az éleket. A legfelső szinten egyetlen csúcs található, a gyökér. Tetszőleges két csomópontból maximum két él indul ki. Ezeket a csúcs bal-, illetve jobb fiainak (gyerekeinek) nevezzük. Minden gyökértől különböző csúcsnak egy és csakis egy apja (őse) van. Az a csúcs, aminek nincs fia (gyereke) a levél. Egy tömb bináris fának is tekinthető. A fa minden csúcsa a tömb egy elemének felel meg, melyben a csúcs értékét tároljuk. Legyen egy A tömb, melynek segítségével kupacot szeretnénk alkotni. Ebben a tömbben fogjuk tárolni a kupac elemeit. Egy kupachoz 2 tulajdonság tartozik. A hossz, mely a tömb elemeinek számát határozza meg, és a méret, mely a kupac méretét. Az A tömb hossza (elemeinek száma) legyen n, a kupac elemeinek számát pedig jelöljük kupac_méret-tel. Vegyük észre, hogy az A[1..n] tömb minden eleme fontos adatot tartalmaz. Az Akupac_méret utáni értékek, ahol kupac_méret≤n, azonban már nem a kupac elemei. A
kupacot ábrázoló fa gyökere a tömb első eleme (A1). Ha i a bináris fa egy adott csúcsának tömbbeli indexének felel meg, akkor a következő egyszerű képletekkel könnyen kiszámíthatjuk a csúcs ősének (szülőjének) Szülő(i) – , baloldali utódának (gyerekének) Bal(i) –, illetve jobboldali utódának (gyerekének) Jobb(i) indexét: Algoritmus Szülő(i): visszatéríti [i/2]-t Vége(algoritmus) Algoritmus Bal(i): visszatéríti 2∗i-t Vége(algoritmus) Algoritmus Jobb(i): visszatéríti 2∗i + 1-t Vége(algoritmus) A képletek alapján elmondhatjuk a következőket: az Ai csúcs bal fia és jobb fia A2∗i, illetve A2∗i+1, az Ai csúcs apja pedig Ai/2.
2.2 MINIMUM – ÉS MAXIMUM KUPACOK, KUPAC-TULAJDONSÁG 1
20 2
3
15
13
1
4
5
6
7
9
5
12
8
8
9
10
7
3
1
2
3
4
5
6
7
8
9
10
20 15 13 9 5 12 8 7 3
1
A maximumkupac bináris faként és tömbként ábrázolva. A körök belsejébe a fa csúcsának értéke került, a kör mellé írt számok pedig a csúcsnak a tömbben megfelelő elem indexét adják meg. A tömb alatt és felett ívek húzódnak, melyek a szülő-gyerek viszonyokat hivatottak ábrázolni; a szülő mindig balra található a gyerekeihez képest. A bináris kupacnak két fajtája van: a maximum-kupac és a minimum-kupac. Mindkét fajta kupacban a csúcsok értékei kielégítik a kupac-tulajdonságot, melynek jellemző vonása függ a kupac fajtájától.
5
Maximum-kupac esetén a kupac minden gyökértől különböző i eleme maximum-kupac tulajdonságú: ASzülő(i) ≥ Ai, azaz az elem értéke legfeljebb akkora, mint a szülőjének értéke (vagy ennél kisebb). A minimum-kupac a maximum-kupac fordítottja; minden gyökértől különböző elem minimum-kupac tulajdonságú: ASzülő(i) ≤ Ai, vagyis az elem ősének értéke kisebb vagy egyenlő, mint magának az elemnek az értéke. Tehát a maximum-kupacban a gyökérben található a legnagyobb elem, egy adott csomópontban lévő elem értéke pedig nagyobb vagy egyenlő, mint bármely, az adott csúcspont alatti részfához tartozó elemek értéke. Ezzel szemben a minimum-kupac legkisebb eleme van a gyökérben, és egy adott csomópont alatti részfa minden elemének értéke nagyobb vagy egyenlő, mint az adott csomópontban lévő elem értéke. Megjegyzés: A kupacrendezés algoritmusban maximum-kupacot használunk. A minimum-kupacot általában az elsőbbségi soroknál alkalmazzák. A továbbiakban tehát maximum-kupacokkal foglalkozunk, a minimum-kupacokkal legközelebb a 3. fejezetben találkozunk.
2.3 KUPAC MAGASSÁGA A kupac magasságának vizsgálatához, a kupacot egy faként kell vizsgáljuk. Ekkor azt mondhatjuk, hogy a kupac magassága megfelel a gyökérben található elem magasságának. Egy adott elem magasságán azon élek számát értjük, melyek a csúcstól a levélhez vezető leghosszabb egyszerű úton találhatóak. A kupac magassága Θ(log n). Ez abból következik, hogy egy n elemből álló kupac ugyancsak egy teljes bináris fán alapszik. A későbbiekben be fogjuk látni azt a tényt, hogy a kupacon végzett műveletek végrehajtási ideje O(log n) idejű, vagyis arányos a fa magasságával.
2.4 NÉHÁNY ALAPVETŐ ALGORITMUS Az alábbiakban bemutatásra kerül néhány alapvető algoritmus és ezek alkalmazása a kupacrendezésben. Ezen algoritmusok maximum-kupacokra íródtak, de hasonlóan meg lehet őket szerkeszteni minimum-kupacokra is. ĺgy a minimum-kupacokra vonatkozó algoritmusok leírásától eltekintünk. Elsőként a Maximum-Kupacol algoritmussal ismerkedünk meg, mely alapvető fontosságú a maximum-kupac tulajdonság fenntartásához. O(log n) futási idejű.
6
Ezután a Maximum_Kupacot_Épít algoritmus bemutatása következik, mely lineáris időben képes tetszőleges adatokat tartalmazó tömböt maximum-kupaccá alakítani. A kupacok segítségével egy tömb elemeit helyben rendezhetjük. Ezen algoritmus neve Kupacrendezés (a bonyolultsága O(n log n)).
2.4.1 A KUPAC TULAJDONSÁG FENNTARTÁSA Kupacok esetén a legfontosabb a kupac-tulajdonság fenntartása. A továbbiakban bemutatunk egy algoritmust, melynek szerepe e tulajdonság fenntartása maximum-kupacok esetén. Hasonlóan megszerkeszthető egy eljárás minimum-kupacokra is, ezért ezen algoritmus bemutatásától most eltekintünk. Legyen a Maximum-Kupacol(A,i) eljárás, melynek bemenő adatai: az A tömb, és annak egy i indexe. Az eljárás meghívásakor feltételezzük, hogy a Bal(i) és Jobb(i) gyökerű részfák már eleve maximum-kupac felépítésű. Előfordulhat azonban, hogy Ai megsérti a maximum-kupac tulajdonságot azzal, hogy értéke kisebb a gyerekei értékénél. A Maximum-Kupacol(A,i) szerepe, hogy „lefele tolja” az Ai értéket a maximum-kupacban mindaddig, míg az i gyökerű részfa maximum-kupaccá nem alakul.
2.4.1.1 A MAXIMUM_KUPACOL(A,i) ALGORITMUS Algoritmus Maximum_Kupacol(A,i): b ← Bal(i) j ← Jobb(i) Ha (b ≤ kupac_méret) és (Ab > Ai) akkor maximum ← b különben maximum ← i vége(ha) Ha (j ≤ kupac_méret) és (Aj > Amaximum) akkor maximum ← j vége(ha) Ha maximum ≠ i akkor Ai ↔ Amaximum Maximum_Kupacol(A,maximum) vége(ha) Vége(algoritmus)
7
2.4.1.2 AZ ALGORITMUS RÖVID LEĺRÁSA Az algoritmus rekurzív, melynek minden lépésében megállapítjuk, hogy az Ai (apa), ABal(i) és AJobb(i) (gyerekek) közül melyik a legnagyobb, s ennek az elemnek az indexét a maximum változóba helyezzük. Ha Ai a legnagyobb, akkor vége az algoritmusnak, hisz az i gyökerű részfa teljesíti a kupac-tulajdonságot. Különben Ai két utóda közül az egyik lesz a legnagyobb elem. Tehát felcseréljük Ai-t Amaximum-mal (vagyis az apa és a nagyobbik értékű fia elemei helyet cserélnek). Ekkor az i gyökerű részfa biztosan maximum-kupac szerkezetű. Azonban mivel a maximum indexű csúcs most már az eredeti Ai értékét tárolja, most a maximum gyökerű
részfa
elemei
sérthetik
a
maximum-kupac
tulajdonságot.
Vagyis
a
Maximum_Kupacol(A,i) algoritmust ismét le kell futtatni erre a részfára. A következő ábrákon a Maximum_Kupacol(A,i) algoritmus működését követhetjük nyomon. Adott egy 10 elemű A tömb: 1
2
3
4
5
6
7
8
9
10
20 7 13 15 5 12 8 9 3
1
A Maximum_Kupacol(A,2) működése, ahol kupac_méret = 10. 1
20 i
2
3
7
13
4
5
6
7
15
5
12
8
8
9
10
9
3
1
(i) Első alkalommal figyeljük meg az A2 csúcsot. Észrevehetjük, hogy nem nagyobb a gyerekeinél, tehát erre a részfára nem teljesül a maximum-kupac tulajdonság. Ezt a tulajdonságot helyre tudjuk állítani, ha az A2 és A4 elemeket felcseréljük.
8
1
20
i
2
3
15
13
4
5
6
7
7
5
12
8
8
9
10
9
3
1
(ii) Az előbbi lépéssel elrontottuk a maximum-kupac tulajdonságot a 4-es csomópontra nézve. A Maximum_Kupacol(A,4) rekurzív hívása i-t 4-re állítja. A kupac-tulajdonság visszaállításához az A4 és A8 csúcspontokat felcseréljük. 1
20
8
7
2
3
15
13
4
5
6
7
9
5
12
8
i
9
10
3
1
(iii) Látható, hogy a 7 értékű elem helyére kerül. Még egyszer meghívódik a Maximum_Kupacol(A,8) eljárás, ami azonban már nem talál olyan csúcsot, mely sértené a maximum-kupac tulajdonságot.
2.4.1.3 AZ ALGORITMUS FUTÁSI IDEJE A
Maximum_Kupacol(A,i)
algoritmus
futási
ideje
O(log
n).
Más
szóval
a
Maximum_Kupacol(A,i) eljárás futási idejét egy h magasságú csomópontra O(h)-val jellemezhetjük.
2.4.2 A KUPAC ÉPĺTÉSE Legyen a Maximum-Kupacot_Épít(A,n,kupac_méret) eljárás, melynek bemenő adatai: az A tömb, annak hossza és a kupac mérete. A Maximum-Kupacot_Épít(A,n,kupac_méret) feladata, hogy felépítse a maximum-kupacot.
9
2.4.2.1 A KUPACÉPĺTÉS ALGORITMUSA Algoritmus Maximum_Kupacot_Épít(A,n,kupac_méret): kupac_méret ← n Minden i ← [n/2],1 végezd el: Maximum_Kupacol(A,i) vége(minden) Vége(algoritmus)
2.4.2.2 AZ ALGORITMUS RÖVID LEĺRÁSA A Maximum_Kupacot_Épít(A,n,kupac_méret) algoritmus az n elemű A tömböt maximum – kupaccá alakítja. Ezen folyamatot lentről felfelé haladva végzi az algoritmus, hisz a csomópontok ilyen formában történő feldolgozása biztosítja, hogy amikor egy i csúcsra meghívjuk az eljárást, ezután az i csúcs gyerekei már biztosan maximum-kupacot alkotnak. Az A tömb azon elemei, amelyeknek indexei [n/2] és n közöttiek levelek, ezért ezen elemek egyelemű kupacnak tekinthetők. Tehát a Maximum_Kupacot_Épít(A,n,kupac_méret) algoritmusnak csak a többi csomópontot kell megvizsgálnia, valamint meg kell hívnia minden egyes csúcsra a Maximum_Kupacol(A,i) eljárást. A következő ábrákon bemutatásra kerül a Maximum_Kupacot_Épít(A,n,kupac_méret) algoritmus működése. 1
Legyen egy 10 elemű A tömb:
2
3
4
5
6
7
8
9
10
15 1 8 7 20 12 13 9 3
5
Az A tömb, mint egy bináris fa: 1
15 2
3
1
8
4
5
i 20
7 8
9
10
9
3
5
6
7
12
13
(a) Kiinduláskor az i ciklusváltozó a tömb középső elemére, vagyis az 5-dik csúcsra mutat. Erre fogjuk meghívni a Maximum_Kupacol(A,i) eljárást, ami azonban nem fog változtatni az adatszerkezeten, hisz 20 nagyobb, mint 5 – az utóda.
10
1
15
i
2
3
1
8
4
5
7
20
8
9
10
9
3
5
6
7
12
13
(b) Ekkor i=4. 7 nem nagyobb, mint a bal oldali gyereke, ezért felcseréljük a 9 – cel
1
15 2
3
i
1
8
4
5
6
7
9
20
12
13
8
9
10
7
3
5
(c) A következő lépésben i a 3-dik csúcsra mutat. 8 nem nagyobb, mint az utódai. Mivel 13 nagyobb, mint 12, ezért 8-at 13-al cseréljük fel.
1
15 i
2
3
1
13
4
5
6
7
9
20
12
8
8
9
10
7
3
5
(d) i= 2: 1 nem nagyobb, mint a gyerekei, így csere történik 20 és 1 között, majd 1 és 5 között, így 1 a helyére kerül.
11
1
i 15 2
3
20
13
4
5
6
7
9
5
12
8
8
9
10
7
3
1
(e) Az i változó az 1-es csomópontra mutat. Az 1-es csúcs utódai olyan részfák gyökerei, amelyek már kupacok. 15 azonban kisebb a gyerekeinél, így lesüllyesztjük a helyére. 1
20 2
3
15
13
4
5
6
7
9
5
12
8
8
9
10
7
3
1
(f) A Maximum_Kupacot_Épít(A,n,kupac_méret) algoritmus hívásának végeredménye.
2.4.2.3 AZ ALGORITMUS FUTÁSI IDEJE Láttuk, hogy a Maximum_Kupacol(A,i) eljárás futási ideje O(log n). Mivel O(n) hívás történik, legfeljebb O(n log n) lehet a kupacépítés futási ideje. Tudva, hogy a fa magassága log n, elmondhatjuk, hogy bármilyen tömbből kupac építhető lineáris idő alatt.
2.4.3 KUPACRENDEZÉS A kupacrendezés – ahogy a neve is utal rá – egy rendezési algoritmus, mely két másik rendező algoritmus jó tulajdonságait ötvözi: a beszúró -, illetve az összefésülő rendezését. A beszúró rendezés helyben rendez ugyan, de nem túl kedvező a futási ideje, az összefésülő rendezésnek a futási ideje n elemre O(n log n), azonban nem helyben rendez. A kupacrendezés futási ideje O(n log n), helyben rendez, és csak állandó számú változóra van szükségünk, a bemeneti tömbön kívül.
12
Legyen a Kupacrendezés(A,n) eljárás, melynek bemenő adatai: az A tömb és annak hossza. A Kupacrendezés(A,n,kupac_méret) feladata, hogy rendezze az A tömböt.
2.4.3.1 A KUPACRENDEZÉS ALGORITMUSA Algoritmus Kupacrendezés(A,n): Maximum_Kupacot_Épít(A,n,kupac_méret) Minden i ← n-től 2-ig végezd el: Csere(A1, Ai) kupac_méret ← kupac_méret – 1 Maximum_Kupacol(A,1) vége(minden) Vége(algoritmus)
2.4.3.2 AZ ALGORITMUS RÖVID LEĺRÁSA Az algoritmus első sora a Maximum_Kupacot_Épít(A,n,kupac_méret) eljárást hívja meg, amely maximum-kupaccá alakítja az n elemű A tömböt. Tudjuk, hogy a maximum-kupacban – a kupac tulajdonság miatt – a legnagyobb elem a gyökérben található, mely pontosan az A tömb első eleme (A1). Épp ezért az i ciklusváltozót az utolsó elemtől indítjuk, hiszen ha felcseréljük a tömb első és utolsó elemét, a legnagyobb elem a helyére kerül. Eggyel csökkentve a kupac_méretet elérjük, hogy a már helyére került elemet az eljárás ne vegye figyelembe. A megmaradt n – 1 elem ekkor már könnyen maximum-kupaccá alakítható. A Maximum_Kupacol(A,1) eljárás segítségével helyreállítjuk a maximum-kupac tulajdonságot a maradék n-1 elemre. Az eljárást minden lépésben a tömb első elemére hívjuk meg, ugyanis az új gyökérelem sértheti a maximum-kupac tulajdonságot, a gyökér gyerekei azonban maximum-kupacok maradnak. A fent leírtakat ismételjük mindaddig, míg az i ciklusváltozó értéke nem csökken 2-re. A következő ábrákon a Kupacrendezés(A,n) működését követhetjük nyomon. Adott egy 10 elemű A tömb: 1
2
3
4
5
6
7
8
9
10
20 15 13 9 5 12 8 7 3
1
13
Az A tömböt egy bináris faként tekintve: 20 15
13
9
12
5
7
3
8
1
a. Az A tömbből a Kupacot_Épít(A,n,kupac_méret) eljárás kialakítja a maximum-kupacot. 15 9
13
7
12
5
1
3
20
8
i
b. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás első futása után 13 9
12
7
1
3
5
i
8
20
15
c. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás második futása után 12 9
8
7
13 i
5
15
3
1
20
d. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás harmadik futása után
14
9 7
8
1
13
3
5
15
i
12
20
e. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás negyedik futása után 8 7
3
1
13
9
5
15
12
i
20
f. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás ötödik futása után 7 5
3
1
13
i 15
9
8
12
20
g. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás hatodik futása után 5 1
i 13
3
7
8
15
9
12
20
h. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás hetedik futása után
15
3
i
1 7
9
8
13
5 12
20
15
i. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás nyolcadik futása után 1
i
3
5
7
13
9
8
15
12
20
j. Az adatszerkezet a Maximum_Kupacol(A,i) eljárás kilencedik futása után 1
2
3
4
5
6
7
8
9
10
A 20 15 13 9 5 12 8 7 3
1
Az eredmény a rendezett A tömb: (1, 2, 3, 4, 7, 8, 9, 10, 14, 16).
2.4.3.3 AZ ALGORITMUS FUTÁSI IDEJE Mivelhogy a Kupacot_Épít(A,n) algoritmusnak O(n) a futási ideje, a Kupacol(A,i) eljárásnak pedig O(log n), melyet n – 1-szer futtatunk le, a Kupacrendezés(A,n,kupac_méret) futási ideje O(n log n) lesz.
16
3 KUPAC TĺPUSÚ ADATSZERKEZETEK ALKALMAZÁSA Mint ahogy azt már a második fejezetben említettük, a kupac adatszerkezeteknek nagyon sok alkalmazási területe van. Ezek közül a rendezésben használt kupacrendezés algoritmust már bemutattuk. Ez egy rendkívül jó rendezési eljárás, a gyakorlatban mégis egy jól implementált gyorsrendezés hatékonyabbnak bizonyul. A kupac adatszerkezet fontosságára és hasznosságára ez a fejezet világít rá. Ebben a részben ismertetni fogom a kupac adatszerkezetek leggyakoribb alkalmazási területét, vagyis azt, hogy hogyan használhatjuk az ilyen típusú adatszerkezeteket elsőbbségi sorok kezelésére.
3.1 ELSŐBBSÉGI SOROK 3.1.1 AZ ELSŐBBSÉGI SOR FOGALMA „Egyszerű” sorok (várakozási sorok) esetén az elemeket a lista egyik végére (az elejére) szúrhatjuk be és a másik végéről (a legvégéről) törölhetjük. Ezen soroknál a FIFO szemantika érvényesül (épp ezért FIFO listának is nevezik őket), hisz „az elsőnek érkezett lesz elsőként kiszolgálva”. Azonban előfordul, hogy a sorban levő elemeknek valamilyen rendezésük is van. A legjobb példa erre a kórházban a vizsgálatra váró betegek sora, hisz az esetek súlyosság szempontjából különbözhetnek. Ezt a rendezést prioritásnak (elsőbbségnek) nevezzük, az ilyen tulajdonságú sorokat pedig elsőbbségi soroknak. Ezek esetén a cél az, hogy a sorban levő elemek közül a legnagyobb/legkisebb prioritásút töröljük ki. A kupachoz hasonlóan kétféle elsőbbségi sorról beszélhetünk: maximum- és minimumelsőbbségi sorról. Vizsgálatunk tárgya a maximum-elsőbbségi sor maximum-kupaccal történő megvalósítása lesz (ennek alapján megvalósítható a minimum-elsőbbségi sor is). Elsőbbségi sor (más néven prioritási sor) alatt egy P halmazt értünk. A halmaz minden eleméhez hozzárendelünk egy kulcs értéket. Ez fogja megadni az adott elemek prioritását. Elsőbbségi sorok esetén három alapvető műveletről beszélhetünk: beszúrás, legnagyobb elem kiválasztása, illetve törlés. Ezen műveleteket a következő eljárások valósítják meg: a Beszúr(P, x) hozzáfűz egy x elemet a P halmazhoz; a Maximum(P)/Minimum(P) algoritmus meghatározza a P halmaz legnagyobb/legkisebb prioritású elemét; míg a KiveszMax(P)/Kivesz_Min(P) megadja és törli ezt az elemet.
17
3.1.2 ELSŐBBSÉGI SOROK ALKALMAZÁSI TERÜLETEI Esemény-vezérelt szimulációk esetén általában az elsőbbségi sorokat veszik igénybe. A szimulálandó események lesznek a sor elemei, melyekhez kulcsként az adott esemény bekövetkezésének időpontját rendeljük. Az események nem függetlenek egymástól, hisz egy esemény bekövetkezése okozhatja egy másik esemény jövőbeli bekövetkezését. Épp ezért az eseményeket bekövetkezési idejük sorrendjében kell szimulálni. Ennél az alkalmazásnál a sort kezelő eljárások azok az algoritmusok lesznek, melyek a legkisebb kulcsú elemmel dolgoznak. A Kivesz_Min(P) eljárás segítségével fogja a szimulációs program meghatározni a következő eseményt. Új esemény felvételét a sorba a Beszúr(P,kulcs) eljárás végzi. Elsőbbségi sorok alkalmazhatók osztott működésű számítógépeken is, ahol a munkák ütemezéséhez nyújtanak segítséget. Ezen alkalmazásoknál az elsőbbségi sorban az elvégzendő feladatokat és ezek relatív prioritását tárolják. Ha elkészült egy feladat, vagy esetleg megszakítás következett be, akkor a Kivesz_Max(P) algoritmus a várakozók közül a legnagyobb prioritású munkát fogja kiválasztani. A Beszúr(P,kulcs) lehetőséget ad új munkák felvételére az elsőbbségi sorba. Az elsőbbségi sorokat általában kupac típusú adatszerkezetek segítségével ábrázoljuk. Itt már nem halmazzal dolgozunk, hanem egy A tömbbel.
3.1.3 NÉHÁNY ALAPVETŐ ALGORITMUS BINOMIÁLIS KUPACOKKAL VÉGEZHETŐ MŰVELETEK ELVÉGZÉSÉHEZ Az alábbiakban megismerkedünk az elsőbbségi sorokkal végezhető műveleteket megvalósító algoritmusokkal: a Maximum(A), Kivesz_Max(A), illetve a Beszúr_Max(A) eljárásokkal.
Itt
is
beszélhetünk
a
Kivesz_Min(A),
valamint
a
Beszúr_Min(A)
algoritmusokról. Ezen eljárások implementálása hasonlóan történik, így a leírásuktól eltekintünk.
3.1.3.1 A MAXIMUM(A) ALGORITMUS Mivel a kupac legnagyobb eleme (maximum-kupacot tekintve) a gyökérben található, a Maximum(A) művelet Θ(1) idő alatt megtalálja a kupac legnagyobb elemét, hisz ez pontosan a tömb első elemének, vagyis az A1-nek az értéke. 3.1.3.1.1 AZ ALGORITMUS Algoritmus Maximum(A): visszatéríti A1-et Vége(algoritmus)
18
3.1.3.2 A KIVESZ_MAXIMUM(A) ALGORITMUS A Kivesz_Maximum(A) algoritmus valósítja meg a kupac legnagyobb elemének keresését, s ezt fogja majd visszatéríteni. Az algoritmus kódjában felfedezhető a hasonlóság a Kupacrendezés(A,n) Minden ciklusával. Az eljárás futási ideje O(log n), hisz csak néhány, állandó idejű lépést tartalmaz a Maximum_Kupacol(A,1) meghívása előtt (melyről tudjuk, hogy O(n log n) a futási ideje). 3.1.3.2.1 AZ ALGORITMUS Algoritmus Kivesz_Maximum(A): Ha kupac_méret < 1 akkor Ki: 'Hiba: Kupacméret alulcsordulás.' vége(ha) maximum ← A1 A1 ← Akupac_méret kupac_méret ← kupac_méret –1 Maximum_Kupacol(A,1) Vége(algoritmus)
3.1.3.3 A BESZÚR(A,KULCS) ALGORITMUS A kupachoz hozzáadhatunk egy elemet a Beszúr(A,kulcs) eljárás segítségével, mely először megnövelve a kupac méretét, az elemet egy új levélként hozzáfűzi a fához, majd a levéltől a gyökérig haladó utón végigszemléli az elemeket, hogy megtalálja a beszúrandó elem helyét a fában. Ha egy n elemű kupacot tanulmányozunk, a vizsgálandó út hossza a levéltől egészen a gyökérig O(log n), így a Beszúr(A,kulcs) futási ideje is O(log n) lesz. 3.1.3.3.1 AZ ALGORITMUS Algoritmus Beszúr(A,kulcs): kupac_méret ← kupac_méret + 1 i ← kupac_méret Amíg (i > 1) és (ASzülő(i) < kulcs) végezd el: Ai ← ASzülő(i) i ← Szülő(i) vége(amíg) Ai ← kulcs Vége(algoritmus)
19
3.1.3.3.2 AZ ALGORITMUS LEĺRÁSA A következő ábrák a Beszúr(A,kulcs) eljárást mutatják be. Legyen a 2-es fejezetben szereplő A tömb: 1
2
3
4
5
6
7
8
9
10
20 15 13 9 5 12 8 7 3
1
20 15
13
9
7
12
5
8
1
3
a. Az A tömböt egy bináris faként ábrázolva. Be szeretnénk szúrni a 11-es elemet a kupacba. 20 15
13
9
7
12
5
3
8
1
b. A fához hozzáadtunk egy új levelet 20 15
13 12
9
7
3
1
8
5
c. Azon az úton, mely az új levéltől a gyökérhez vezet, az elemeket eggyel lejjebb görgetjük mindaddig, míg meg nem találjuk a 11-es helyét.
20
20 15
13 11
9
7
3
1
12
8
5
d. Sikerült beszúrni a 11-es kulcsú elemet.
Végezetül levonhatjuk a következtetést, miszerint ha az elsőbbségi sorok esetén kupac adatszerkezeteket használunk, akkor az összes, fent bemutatott műveletek logaritmikus idő alatt véget érnek.
21
4 BINOMIÁLIS KUPACOK A fentiekben láttuk, hogy bináris kupacok esetén egy új elem beszúrása a kupacba, a maximális/minimális elem megkeresése vagy épp ezen elem törlése legrosszabb esetben is logaritmikus bonyolultságú. Azonban ha két kupacot szeretnénk egyesíteni, akkor a bináris kupacok nem olyan hatékonyak, hiszen ezek összefűzése tulajdonképpen egy új kupac megalkotását jelenti, tehát a futási idő legrosszabb esetben Θ(n). Ebben a fejezetben egy másik kupac típusú adatszerkezettel fogunk megismerkedni, mégpedig a binomiális kupacokkal. A binomiális kupacok használata általában akkor javasolt, ha gyakran kell az alkalmazásban kupacokat egyesítenünk, hisz e kupacok esetén ez a művelet rendkívül egyszerűen megoldható, a bonyolultsága pedig logaritmikus. A binomiális kupac elnevezést először Vuillemin használta (1978, A Data Structure for Manipulating Priority Queues).
4.1 BINOMIÁLIS FÁK A binomiális kupac binomiális fákból épül fel. Nézzük meg, mit is értünk binomiális fa alatt. A binomiális fát rekurzív módon írjuk le. Jelöljük Bk-val a k-ad rendű binomiális fát. Ekkor a következőket mondhatjuk el: • a B0, 0 rendű binomiális fa egyetlen csomópontot tartalmaz (a gyökeret), • a Bk, k-ad rendű binomiális fa gyökerének gyerekei a k-1, k-2,…, 2, 1, 0 rendű binomiális fák gyökerei (ebben a sorrendben) Ezen egyedi szerkezet miatt a k-ad rendű binomiális fát két (k – 1)-ed rendű, Bk-1-el jelölt binomiális fa alkotja. Ez a két fa össze van kapcsolva a következőképpen: a két fa közül, egyiknek gyökere a másik fa gyökerének legbalra (vagy legjobbra) eső utóda. A binomiális fa e jellemvonása központi szerepet játszik a binomiális kupacok összefésülő műveletében. Mélység B0
3 B1
B2
B3
0
Mélység B0
3
B1
B2
B3
0
1
1
2
2
3
3
Az ábrán 3, kétféleképpen megszerkesztett binomiális fa látható.
22
A Bk binomiális fa az alábbi tulajdonságokkal rendelkezik: • a fa magassága k, • 2k csúccsal rendelkezik, • a fa i-edik mélységében
fa elnevezés, hisz a
Cki
Cki csúcs található, ahol i=1, k . Innen származik a binomiális kifejezéseket binomiális együtthatók néven ismerjük.
• a gyökér foka k s ez a legnagyobb fokszámú csúcs a binomiális fában. Ez a tulajdonság abból a tényből adódik, hogy ha a gyökércsúcs utódait megszámozzuk balról jobbra haladva k − 1, k − 2, . . . 0-val, akkor megállapíthatjuk, hogy a k-ad rendű fa gyökerének pontosan k fia van. Ezt felhasználva a következő kijelentéseket fogalmazhatjuk meg:
Egy k csomópontú binomiális fa foka legfennebb log2 k.
k csomóponttal rendelkező binomiális fában minden egyes csúcs foka maximálisan log k lehet.
4.2 BINOMIÁLIS KUPAC FOGALMA A 4.1-es alfejezetben definiáltuk a binomiális fa fogalmát. Most már tudjuk, hogy a binomiális kupac binomiális fák összessége. Azonban ez csak szükséges, de nem elégséges
feltétele annak, hogy egy kupac binomiális kupac legyen. Ehhez még teljesülnie kell az úgynevezett binomiális-kupac tulajdonságnak: • a binomiális kupachoz tartozó binomiális fák mindegyike kielégíti a minimum-kupac
tulajdonságot: akármelyik csomópontot is vizsgáljuk, ennek értéke mindig nagyobb lesz, mint a szülőjének az értéke, vagyis a legkisebb elem a gyökérben található • egy k-ad rendű binomiális kupacban 0 vagy 1 binomiális fa lehet, melynek rendje i,
ahol i= 1, k . A második tulajdonság azt mutatja meg, hogy egy n elemből álló binomiális kupac olyan binomiális fákra bomlik fel, melyeknek száma ezek alapján legtöbb ⎣log n ⎦ + 1 lehet. Valójában ezeknek a fáknak a számát és rendjeit egyértelműen meghatározza a kupac elemeinek száma (n): az n szám kettes számrendszerbeli ábrázolásában az 1-es bit egy-egy binomiális fát jelöl, az adott fa rendjét az adott 1-es helye adja meg a bináris ábrázolásban (a 0 azt jelzi, hogy az adott kupac nem tartalmaz olyan rendű binomiális fát).
23
A jobb megértés érdekében vegyünk egy példát: a 11-es szám bináris alakja 10112, hiszen 23 + 21 + 20 = 8 + 2 + 1 = 11, ily módon a 11 csúccsal rendelkező binomiális kupac 3 binomiális fát fog tartalmazni (B3, B2 illetve B0 kupacrendezett binomiális fákat), melyek rendje 3, 1 és 0. A bináris ábrázolásból azt is kiolvashatjuk, hogy a fák rendre 8, 2 és 1 csúcsból állnak. A lenti ábra egy 11 elemből álló kupacot mutat be. Az elemekhez természetes számokat rendeltünk. A binomiális kupacot általában egy láncolt listával ábrázoljuk, melyben a binomiális fákat tároljuk: a lista a gyökérelemek láncolt listája, ahol a fák sorrendjét a listában a gyökércsúcsok fokszámának növekvő sorrendje adja meg. Lista feje
9
12
1
17
28
21
18
24
48
89
99
4.3 NÉHÁNY ALAPVETŐ ALGORITMUS BINOMIÁLIS KUPACOKKAL VÉGEZHETŐ MŰVELETEK ELVÉGZÉSÉHEZ Az alábbiakban megismerkedünk a binomiális kupacokon végezhető műveleteket megvalósító algoritmusokkal, valamint összehasonlítjuk ezen algoritmusok futási idejét a bináris kupacoknál bemutatott algoritmusokéval. Mint már említettük, a binomiális kupacokat binomiális fák „egymásba fűzött” listájának tekinthetjük. Az algoritmusok implementálásához illetve bemutatásához szükség van a következő jelölések bevezetésére: minden csúcsnak lesz egy kulcs –, és egy fokszám mezője. A kulcs mező a csomópont értékét tárolja, míg a fokszám mező az adott csúcs gyerekeinek számát tartalmazza. A csúcsoknak további, adatokat tartalmazó mezői is lehetnek, ha ezt a feladat szövege vagy éppen az alkalmazás megköveteli. Emellett minden x csomópontnak lesz még három mutatója: az egyik a csúcs szülőjére mutat (szülő[x]), a másik a legbaloldalibb gyerekére (gyerek[x]), a testvér[x] mutató pedig az x jobboldalán álló első testvérére. Ha x az ősének legbalra eső utóda, akkor a testvér[x] értéke NIL. Ha azonban az x csúcsnak nincs gyereke, akkor gyerek[x]=NIL. Természetesen a kupac azon csomópontjai
24
esetén, melyen nem gyökércsomópontok, a testvér mutató más jelentéssel bír, mint a binomiális fák gyökereinek esetében: gyökércsúcs esetén a testvér[x] pointer a soron következő binomiális fa gyökerére mutat. Ebből világosan kitűnik, hogy ha a gyökérlistának az utolsó eleme épp a vizsgált x érték, akkor testvér[x]=NIL. A legfontosabb mező egy H binomiális kupac esetén a fej[H], mellyel a gyökércsomópontok listájára tudunk hivatkozni, ezen belül is az első gyökércsúcsra. Látható, hogy a fej[H] mutató csak akkor kap NIL értéket, ha a H kupac üres.
4.3.1 ÜRES BINOMIÁLIS KUPAC LÉTREHOZÁSA Új üres kupac létrehozása konstans idejű mind bináris -, mind pedig binomiális kupacok esetén. Üres binomiális kupac létrehozása nagyon egyszerű, hisz nincs más dolgunk, mint a fej[H] mutató értékét egyszerűen NIL-re állítani.
4.3.1.1 A BINOMIÁLIS_KUPACOT_KÉSZĺT(H) ALGORITMUS Algoritmus Binomiális_Kupacot_Készít(H): fej[H] ←NIL
visszatéríti H-t Vége(algoritmus)
4.3.2 LEGKISEBB ELEM MEGKERESÉSE Ez lehet az a művelet, amely miatt megalkották a kupac típusú adatszerkezeteket. Ha bináris kupacokkal dolgozunk, ez a művelet konstans időben fog végrehajtódni. Binomiális kupacoknál csak a gyökérelemek között érdemes és kell keresnünk a minimális kulcsú elemet, hiszen a kupacot olyan binomiális fák alkotják, melyek minimum-kupac tulajdonságúak, vagyis minden fában a gyökér az adott fa legkisebb elemét tartalmazza. Látható, hogy nincs más dolgunk, mint ezen értékek közül a legkisebbet kiválasztani és ezt az értéket visszatéríteni. A Binomiális_Kupacban_Keres_Min(H) a legkisebb kulcs meghatározására szolgáló függvény. Logaritmikus bonyolultságú, hiszen a binomiális kupacban legtöbb
⎣log n⎦ + 1 binomiális fa szerepel.
25
4.3.2.1 A BINOMIÁLIS_KUPACBAN_KERES_MIN(H) ALGORITMUS Algoritmus Binomiális_Kupacban_Keres_Min(H):
x ← fej[H] y ← NIL minimum ← végtelen Amíg x ≠ NIL végezd el: Ha kulcs[x] < min akkor
minimum ← kulcs[x] y←x vége(ha)
x ← testvér[x] vége(minden)
visszatéríti y-t Vége(algoritmus)
4.3.2.2 A BINOMIÁLIS_KUPACBAN_KERES_MIN(H) ALGORITMUS LEĺRÁSA Az algoritmus legelején az x mutatót a kupachoz tartozó lista első elemére (a lista fejére) állítjuk. Ezután végigmegyünk a kupac gyökércsúcsain, és ha találunk az eddigieknél kisebb elemet, akkor a minimum változóban eltároljuk az adott elem kulcsértékét, y-ban pedig megjegyezzük az illető gyökér helyét. Ezt a műveletsort addig végezzük, amíg el nem jutunk a kupac végére. Minden lépésben a testvér mutató segítségével továbblépünk a következő binomiális fa gyökerére. Az eljárás visszatérítési értéke egy y mutató, mely a minimális gyökércsúcsú binomiális fa gyökerére mutat.
4.3.3 MÁS ALGORITMUSOK A következőkben röviden ismertetjük a többi műveletet is, melyek elvégzésében a kupac adatszerkezetek hasznos segítségnek bizonyulnak. Lássuk ezeket a műveleteket.
4.3.3.1 KÉT KUPAC EGYESÍTÉSE Ez az a művelet, ahol fontos a binomiális kupacok használata. Ha két bináris kupacot szeretnénk összefésülni, akkor ennek a műveletnek az a hátránya, hogy lineáris algoritmussal oldható meg. Ezért olyan alkalmazásokban, amelyekben
26
kupacokat kell egyesítenünk, a binomiális kupac használata az előnyösebb, hisz ekkor az összefésülés O(log n) idő alatt fut le. Két binomiális kupac egyesítése két bináris szám összeadásához hasonlít. Tehát minden lépésben egyesítjük azt a két binomiális fát, amelyeknek azonos a rendjük. A binomiális kupac meghatározása szerint nem lehet két egyforma fokszámmal rendelkező binomiális fa, így ha két k-ad rendű binomiális fát egyesítünk, akkor eredményül egy másik binomiális fát kapunk, melynek rendje eggyel nagyobb, mint az egyesített fáké volt.
4.3.3.2 ÚJ ELEM BESZÚRÁSA BINOMIÁLIS KUPACBA Új elem beszúrása logaritmikus idő alatt ér véget, a bonyolultság nem függ a kupac fajtájától: mind bináris-, mind pedig binomiális kupac esetén a futási idő ugyanannyi. Elsőbbségi soroknál láttuk, hogyan is valósul meg egy új csúcs beszúrása a bináris kupacba. Binomiális kupacok esetén a beszúrás két lépésből áll. Először létrehozunk egy új, üres kupacot, melyhez hozzácsatoljuk a beszúrandó elemet. Ezután már csak annyi teendőnk maradt, hogy ezt az új kupacot egybeolvasztani a már meglevő binomiális kupacunkkal.
4.3.3.3 A MINIMÁLIS KULCCSAL RENDELKEZŐ CSÚCS TÖRLÉSE Ez a művelet bináris -, illetve binomiális kupacok esetén is logaritmikus bonyolultságú. A minimális kulcsú csúcs a gyökérelemek között keresendő, ezért először megkeressük azt a binomiális fát, mely tartalmazza ezt az elemet. Ehhez végigpásztázzuk a gyökércsúcsok listáját, majd ha megtaláltuk, akkor ebből a listából kitöröljük ezt a fát. Ezután készítünk egy új, üres kupacot, mely azon fák halmazából fog állni, melyeknek gyökerei az eredeti kupacból kitörölt binomiális fa gyerekei voltak. Ekkor már csak egyesítenünk kell a két kupacot, megkapva így a kizárt kulcsot már nem tartalmazó binomiális kupacot. A fenti műveletek megismerése után levonhatjuk a következtetést, miszerint a binomiális kupacokat csak akkor érdemes használni, ha az alkalmazásban gyakorta szükséges a kupacok egyesítése. A binomiális kupacokat leggyakrabban több elsőbbségi sor feldolgozásakor használják, ha szükséges ezeket egyesítése is.
27
5
AZ OKTATÓPROGRAM ISMERTETÉSE A dolgozathoz készült egy gyakorlati alkalmazás is. Ez egy oktatóprogram, mely azt
tűzte ki célul, hogy bemutassa a fent megismert adatszerkezeteket, biztosítva ez által az elméleti
rész
könnyebb
és
gyorsabb
megértését.
Segítséget
nyújthat
mindazon
pedagógusoknak, akik a kupac típusú adatszerkezetek oktatására vállalkoztak, valamint azon diákoknak, akik önállóan szeretnének ezen adatszerkezetekkel megismerkedni, vagy egyszerűen csak az órán tanult elméleti részt szeretnék gyakorlatba átültetni.
5.1 A MULTIMÉDIÁS OKTATÓPROGRAMOK MEGJELENÉSE A személyi számítógépek rohamos elterjedése utat tört egy új oktatási formának, melynek legfőbb eszköze maga a számítógép volt. Ennek hatására megjelentek a multimédiás CD-ROM-ok, oktatóprogramok, melyek legfőbb célkitűzése az oktatás e területén az volt, hogy egy, önálló tanulásra alkalmas eszközt teremtsen, mind középiskolai -, mind egyetemi hallgatók számára. A multimédiás CD-ROM-ok megjelenésekor még az a téves felfogás uralkodott, miszerint ezek az alkalmazások már helyettesíteni tudják a pedagógust. Ez legfőképp annak volt köszönhető, hogy a diákok a számítógépes ismeretek területén tanáraik előtt jártak, így tehát érthető, hogy először a pedagógusok is kétkedve fogadták ezeket az új alkalmazásokat, ódzkodtak a használatuktól. Szerencsére mára ez a helyzet megváltozott, a tanárok felzárkóztak tanítványaikhoz s világossá vált az is, hogy a számítógép sohasem helyettesítheti teljesen a tanárt, főleg igaz ez a középiskolában. Itt ugyanis még fontos szerepe van a pedagógusnak, mind az új ismeretek bemutatásakor, mind a diákokkal való kapcsolattartás szempontjából. A mai fiatal generáció ugyanis már az Internet és számítógép mellett nőtt fel, így tehát szüksége van arra, hogy egy láthatatlan kéz vezesse az ismeretek szövedékes erdejében, és ne kalandozzon el az általa oly jól ismert számítógépen. Ezt a szerepet a tanár kell játssza. Azonban e korosztály számára is előnyös lehet egyes témakörök ilyen módú tárgyalása, hisz ekkor minden tanuló a saját ütemében dolgozhat, így a gyengébb képességű diákok is felzárkózhatnak a többiekhez. Természetesen ekkor is elengedhetetlen a tanár közreműködése. Azonban a felsőoktatásban már más a helyzet. Ugyanis itt már a tanár és a tanuló szerepe nem azonos a középiskolában megszokott tanár-diák viszonnyal. A tanár szerepe egyre jobban háttérbe szorul, miközben előtérbe kerül a diák szerepe az új ismeretek
28
elsajátításában. A legjobb példa erre az utóbbi években megjelent és egyre népszerűbbé vált oktatási forma, a távoktatás, melynek szempontjából létfontosságú olyan eszközök készítése, melyek elősegítik és megkönnyítik a diákok otthoni, önálló tanulását.
5.2 AZ OKTATÓPROGRAM FELÉPĺTÉSE. MÓDSZERTANI SZEREP Egy multimédia-oktatóprogram esetén lényeges egy minél felhasználó-barátibb környezet kialakítása, ezáltal a programot azok is könnyen használhatják, akiknek számítógépes ismeretei csak felületesek. Ezen oktatóprogram megírásakor is ez volt a legfőbb cél. Nagy hangsúlyt fektettem arra, hogy a program használója könnyen eligazodhasson az alkalmazásban. Ennek érdekében két részre osztottam a felhasználói felületet: a menü került az ablak bal oldalára, mely minden lépésben a felületen marad, így biztosítva az egyes „fejezetek” közti átjárhatóságot; míg a jobb oldalon mindig a kívánt információ lesz látható. Ezenkívül az elkészítéskor szem előtt tartottam azt is, hogy az alkalmazás tegyen eleget a pedagógiai és didaktikai elvárásoknak, a bemutatott ismeretek feleljenek meg az aktuális tantervnek, az átadni kívánt információk legyenek egyszerűen megfogalmazva, a szöveg, animáció legyen érthető, világos, igazodjon az elméleti részben leírtakhoz. Ilyen segédeszközök esetén figyelni kell arra, hogy az ismeretek bemutatása egy adott pillanatban ne váljon unalmassá, monotonná. Az animációk szerepe épp az érdeklődés felkeltésében és fenntartásában rejlik, ezzel ösztönözve a diákot a tanulásra. Ezért igyekeztem minél több animációt készíteni. Ezek segítségével megpróbáltam az algoritmusokat még érthetőbbé, világosabbá tenni. Az animációk végigveszik az algoritmusok lépéseit, s így a diák szeme előtt fog „lefutni” a program a megadott értékekre. Minden animáció esetén két lehetőség közül választhatunk: vagy elindítjuk az animációt az Indít gombbal (ekkor az összes lépés animálva fog megjelenni a képernyőn) – természetesen bármikor le is állíthatjuk a műveletet – , vagy pedig előre -, illetve visszaléphetünk az animációban a megfelelő gombokra kattintva (ekkor viszont csak az egyes lépések „végterméke” fog megjelenni a képernyőn). Maga az oktatóprogram végigveszi a dolgozat fejezeteit és megpróbálja tömören összefoglalni mindazt, amit a fentiekben bemutattunk. A felhasználó megismerkedik a kupac adatszerkezet fogalmával, a bináris -, illetve binomiális kupacokkal végezhető műveletekkel, az ezeket megvalósító algoritmusokkal, valamint ezek alkalmazásaival.
29
6
KÖNYVÉSZET 1. Ionescu Klára – Adatszerkezetek, Kolozsvári Egyetemi Kiadó, Kolozsvár, 2007. 2. Cormen T., Leiserson C., Rivest R.–Algoritmusok, Műszaki Könyvkiadó, Budapest,
1997. 3. Cormen T., Leiserson C., Rivest R., Stein, C. – Új algoritmusok, Scolar Kiadó,
Budapest, 2003. 4. Iwatt Róbert, Tar Domokos Géza – Számításelméleti szigorlat. Kidolgozott tételek
(jegyzet), Budapesti Műszaki Tudományos Egyetem, 2004. Elérhető a http://bme.selye.sk/segedanyagok/szigorlat/bsz/kidolgozva/szamitaselmelet_szigorlat_ kidolgozott_tetelek.pdf címen. 5.
Aszalós László - Informatikai algoritmusok. Szakmai segédanyag programtervező matematikusok részére, mobiDIÁK könyvtár, Debreceni Egyetem Informatikai Kar, 2006. Elérhető a http://www.inf.unideb.hu/~aszalos/dn/alg/bin.pdf címen.
6. Kevin Wayne - Binary and Binomial Heaps, Princeton University, 2002. Elérhető a
http://www.cs.princeton.edu/~wayne/cs423/lectures/heaps-4up.pdf címen. 7. Mihai Scorţaru - Heap-uri binomiale, Gazeta de informatică, 14/7 – noiembrie 2004.
Elérhető a http://www.ginfo.ro/revista/14_7/focus.pdf címen. 8. Bernát László – Az oktatóprogram készítés egy hatékony alternatívája, BGF
Kereskedelmi, Vendéglátóipari és Idegenforgalmi Kara, Informatikai Intézet, Budapest, 2003. Elérhető a http://www.date.hu/acta-agraria/2003-12/bernat.pdf címen. 9. Forgó Sándor - A multimédiás oktatóprogramok minőségének szerepe a
médiakompetenciák kialakításában, Új Pedagógiai Szemle, 2001/07-08. Elérhető a http://www.oki.hu/oldal.php?tipus=cikk&kod=2001-07-it-Forgo-Multimedias címen.
30
