UNIVERZITA J. SELYEHO – SELYE JÁNOS EGYETEM EKONOMICKÁ FAKULTA – GAZDASÁGTUDOMÁNYI KAR
INTERAKTÍVNA MULTIMEDIÁLNA UČEBNÁ POMÔCKA NA VYUČOVANIE REKURZIE REKURZIÓ TANÍTÁSÁRA SZOLGÁLÓ INTERAKTÍV MULTIMÉDIÁLIS SEGÉDESZKÖZ Bakalárska práca- Szakdolgozat
Nagy Attila 2015
UNIVERZITA J. SELYEHO – SELYE JÁNOS EGYETEM EKONOMICKÁ FAKULTA – GAZDASÁGTUDOMÁNYI KAR
INTERAKTÍVNA MULTIMEDIÁLNA UČEBNÁ POMÔCKA NA VYUČOVANIE REKURZIE REKURZIÓ TANÍTÁSÁRA SZOLGÁLÓ INTERAKTÍV MULTIMÉDIÁLIS SEGÉDESZKÖZ Bakalárska práca - Szakdolgozat Študijný program:
AIdb - Aplikovaná informatika
Tanulmányi program:
AIdb – Alkalmazott informatika
Číslo a názov študijného odboru:
2511 Aplikovaná informatika
Tanulmányi szak száma és megnevezése:
2511 Aplikovaná informatika
Školiteľ:
PaedDr. Ladislav Végh
Témavezető:
PaedDr. Végh Ladislav
Školiace pracovisko:
Katedra matematiky a informatiky
Tanszék megnevezése:
Matematika és Informatika Tanszék
Nagy Attila Komárno 2015
Univerzita J. Selyeho Ekonomická fakulta _____________________________________________________________________________________________________
ZADANIE ZÁVEREČNEJ PRÁCE Meno a priezvisko študenta:
Attila Nagy
Študijný program:
Aplikovaná informatika (Jednoodborové štúdium, bakalársky I. st., denná forma)
Študijný odbor:
2511 aplikovaná informatika
Typ záverečnej práce:
Bakalárska práca
Jazyk práce:
maďarský
Sekundárny jazyk:
slovenský
Téma:
Interaktívna multimediálna učebná pomôcka na vyučovanie rekurzie
Anotácia:
Autor práce sa má
zamerať
na tvorbu takých výukových
interaktívnych animácií na podporu vyučovania algoritmizácie a programovania, ktoré demonštrujú rekurziu a rekurzívne algoritmy (výpočet
faktorialu
rekurzívnym
rekurziou;
algoritmom,
kreslenie
realizácia
rôznych
niektorých
útvarov triediacich
algoritmov rekurziou – napr. SimpleSort, SelectSort a BubbleSort; rekurzívne triediace algoritmy MergeSort a QuickSort; atď.), a sú ľahko integrovateľné do HTML kódu on-line učebnice. Vedúci:
PaedDr. Ladislav Végh
Katedra:
KMI - Katedra matematiky a informatiky
Vedúci katedry:
RNDr. Zuzana Árki, PhD.
Dátum zadania:
05.09.2014
Dátum schválenia: 16.03.2015
RNDr. Zuzana Árki, PhD. vedúci katedry
Becsületbeli nyilatkozat Alulírott Nagy Attila kijelentem, hogy szakdolgozatomat konzultáns tanárom segítségével és a feltüntetett szakirodalmak felhasználásával önállóan készítettem el.
Érsekújvár, 2015.05.09. Aláírás
Köszönetnyilvánítás Ezúton szeretnék köszönetet nyilvánítani PaedDr. Végh Ladislav tanár úrnak, akinek hálával tartozom, mivel idejét nem kímélve segítséget nyújtott az általam kiválasztott témakör kidolgozásában. Köszönöm szaktudását és türelmét. Hálával tartozom a Selye János Egyetem azon tanárainak, akik tanulmányaim során szaktudást biztosítottak a szakdolgozat kidolgozásában. Köszönöm!
Abstrakt v slovenskom jazyku Cieľom bakalárskej práce je vytvoriť také učebné pomôcky, ktoré pomáhajú osvojiť poznatky multimediálnych a výukových interaktívnych animácií, demonštrujú pojem rekurzie a rekurzívnych algoritmov. Dôležitou úlohou práce, aby pre užívateľa ten program bol ľahko zrozumiteľný aj na grafickej ploche. Zamerali sme sa aj nato, aby programy boli jednoducho integrovateľné do HTML kódu on-line učebnice. Diplomová práca sa tvorí zo štyroch častí. Prvá časť sa zaoberá rekurziou, včítane úlohou rekurzívnych algoritmov v matematike. Druhá časť vysvetľuje, realizuje niektorých triediacich algoritmov rekurziou. Nasleduje prehľad používaných pomôcok našej práce. Posledná časť obsahuje postupy vytvorenia programov, ich umiestnenie na webovej stránke, ako aj popis plochy webových stránok. Výsledkom bakalárskej práce je ľahko použiteľná učebná pomôcka na pochopenie významu rekurzií. Program ponúka pre užívateľa užitočný prehľad pri jeho používaním.
Kľúčové slová: rekurzia, fraktál, faktorial, triediacie algoritmy, interaktívna animácia, webová stránka
Absztrakt magyar nyelven A szakdolgozat célja egy interaktív multimediális oktatási segédeszköz létrehozása, mely által elsajátíthatóak a rekurzió és a rekurzív algoritmusok alapismeretei. A tervezés során azt tartottuk fontosnak, hogy a felhasználónak grafikus felület keretén belül könnyen érthetővé váljon a rekurzió fogalma. Azt is szemelőt tartottuk, hogy a segédprogram könnyen integrálható legyen on-line tananyagok HTML kódjába. A munka négy fejezetből áll. Az első fejezetben a rekurziót mutatja be, beleértve a rekurzív algoritmusok matematikában való szerepeit. A második fejezet a rendezési algoritmusokban szerepet játszó rekurzió magyarázata. A következő fejezet, a munka során felhasznált eszközökről ad áttekintést. Az utolsó fejezet a programok létrehozásának az eljárását, weboldalra való beágyazást valamint a weboldal felületeinek leírását tartalmazza. A szakdolgozat végeredménye egy egyszerűen kezelhető oktatási segédeszköz, mely segítségével áttekintést nyerhetünk a rekurzió hasznosságáról.
Kulcsszavak: rekurzió, fraktál, faktoriális, rendezési algoritmusok, interaktív animáció, weboldal
Abstract in English The thesis aims to create an interactive multimedia educational tool, for easy learning the recursion, recursive algorithms knowledge base. During planning it was important to be easily comprehensible the concepts of recursion with the graphical user interface. We also kept in mind that the utility should be easy to integrate in HTML codes of online learning materials. The work consists of four chapters. The first chapter presents recursion, recursive algorithms, including their roles in mathematics. The second section is the explanation of recursion in sorting algorithms. The next chapter is an overview of the tools used in the work. The last chapter is written about the process of setting up the program, embedding into websites and the description of the web interfaces. The outcome of the thesis is an easy educational tool that can be used as an overview of the usefulness of recursion.
Keywords: recursion, fractal, factorial, sorting algorithms, interactive animation, website
Tartalomjegyzék Bevezetés ............................................................................................................................. 10 1
Rekurzió ...................................................................................................................... 12 1.1 Faktoriális ............................................................................................................ 12 1.2 Fibonacci-számok ................................................................................................ 13 1.3 Bináris fa (rekurzív fa) ......................................................................................... 14 1.4 Bináris keresés ..................................................................................................... 14 1.5 Fraktálok .............................................................................................................. 15 1.5.1 Cantor-por ........................................................................................................ 16 1.5.2 Koch-görbe ...................................................................................................... 16 1.5.3 Koch-hópehely ................................................................................................. 17 1.5.4 Sierpinski-háromszög ...................................................................................... 17 1.5.5 Sierpinski-szőnyeg ........................................................................................... 18 1.6 Hanoi tornyai ....................................................................................................... 18
2
Rekurzió a rendezési algoritmusokban.................................................................... 20 2.1 2.2 2.3
3
Oszd meg és uralkodj elv ..................................................................................... 20 Összefésülő rendezés (Merge sort) ...................................................................... 21 Gyorsrendezés (Quick sort) ................................................................................. 22
Oktatási segédlet felületének megtervezése ............................................................. 23 3.1 Felhasznált eszközök bemutatása ........................................................................ 23 3.2 HTML .................................................................................................................. 23 3.3 CSS ...................................................................................................................... 24 3.4 JavaScript programozási nyelv ............................................................................ 24 3.4.1 Notepad++ ....................................................................................................... 25
4
A segédeszköz létrehozása ......................................................................................... 26 4.1 Weboldal létrehozása ........................................................................................... 26 4.1.1 Fejléc létrehozása ............................................................................................. 26 4.1.2 Menü létrehozása ............................................................................................. 27 4.1.3 Bevezető felület ............................................................................................... 27 4.1.4 Lábléc létrehozása............................................................................................ 28 4.2 Faktoriális segédeszköz kialakítása ..................................................................... 28 4.3 Rekurzív fa kialakítása a weboldalra ................................................................... 29 4.4 Sierpinski-háromszög kialakítása a weboldalra ................................................... 30 4.5 A Koch-görbe (hópehely) kialakítása a weboldalra ............................................ 31 4.6 Rendezési algoritmusok ábrázolása ..................................................................... 32 4.6.1 A rendezési algoritmusok kinézete HTML forráskódban................................ 32 4.6.2 A rendezési algoritmusok JavaScript kódjai .................................................... 33 4.6.3 Buborékrendezés kialakítása a webodlara ....................................................... 34 4.6.4 Összefésülő rendezés kialakítása a weboldalra ............................................... 35 4.6.5 Gyorsrendezés kialakítása a weboldalra .......................................................... 36
Befejezés .............................................................................................................................. 38 Resumé ................................................................................................................................ 39 Felhasznált irodalom ......................................................................................................... 42 Melléklet ............................................................................................................................. 44
Ábrák jegyzéke 1.
ábra: Rekurzív faktoriális (kódrészlet).................................................................... 13
2.
ábra: Rekurzív Fibonacci-számok (kódrészlet) ...................................................... 13
3.
ábra: Rekurzív fa ....................................................................................................... 14
4.
ábra: Rekurzív bináris keresés (kódrészlet) ............................................................ 15
5.
ábra: Cantor-por........................................................................................................ 16
6.
ábra: Koch-görbe ....................................................................................................... 16
7.
ábra: Koch-hópehely ................................................................................................. 17
8.
ábra: Sierpinski-háromszög ...................................................................................... 18
9.
ábra: Sierpinski-szőnyeg ........................................................................................... 18
10.
ábra: Hanoi tornyai ............................................................................................... 19
11.
ábra: Hanoi tornyai (kódrészlet) .......................................................................... 19
12.
ábra: Merge sort (kódrészlet) ............................................................................... 21
13.
ábra: Weboldal fejléce ........................................................................................... 26
14.
ábra: Weboldal menüpontjai ................................................................................ 27
15.
ábra: Weboldalon lévő faktoriális ábrázolása..................................................... 29
16.
ábra: Weboldalon lévő rekurzív fa ábrázolása ................................................... 30
17.
ábra: Weboldalon lévő Sierpinski-háromszö ábrázolása ................................... 31
18.
ábra: Weboldalon lévő Koch-hópehely ábrázolása ............................................ 32
19.
ábra: Rendezési algoritmusok ábrázolására szolgáló vezérlőpult .................... 33
20.
ábra: Rekurzív Bubble sort (kódrészlet) ............................................................. 34
21.
ábra: Weboldalon lévő Bubble sort ábrázolása .................................................. 35
22.
ábra: Rekurzív Merge sort (kódrészlet) .............................................................. 35
23.
ábra: Weboldalon lévő Merge sort ábrázolása ................................................... 36
24.
ábra: Rekurzív Quick sort (kódrészlet) ............................................................... 37
25.
ábra: Weboldalon lévő Quick sort ábrázolása .................................................... 37
9
Bevezetés Bakalármunkánk témaköreként egy segédeszközt választottunk, amely a rekurzió megértésére és ábrázolására szolgál. A választást befolyásolta, hogy a matematika és a programozás egyre közelebb áll érdeklődési körünkhöz. Megvalósításához sokat segített a „programozás” tantárgy által szerzet tapasztalat. Ezeken az órákon sikerült megértenem és kibővítenem a programozáshoz szükséges jelenlegi tudásomat. A rekurzió egy programozási módszer, melysegítségével egy eljárásban szereplő kód „önmagát” hívja meg. A folyamatot véges számú lépés után természetesen le kell állítani a végtelen ciklus elkerülése érdekében. A rekurzió segítségével lehetőségünkben áll egy programot (algoritmust) leegyszerűsíteni, és átláthatóbbá tenni. A rekurzió, mint fogalom nemcsak a programozásban található meg, hanem a matematikában (pl.: faktoriális), vagy akár a nyelvészetben is. A Google is viccelődik a témával, mivel ha beírjuk a keresőbe, hogy rekurzió, akkor a fenti javaslatra kidobja az oldalra vonatkozó linket, ami „rekurzívan meghívja“ az adott oldalt, amin jelen pillanatban vagyunk. Munkám elsődleges célja, a rekurzió megértésére szolgál. Nemcsak az e témában kutakodó embereknek, hanem a közemberek számára is. Ennek céljából a faktoriális kiszámítását, magyarázatát tűztem célkeresztbe. Lehetőség van bemeneti adatok megváltoztatására, a program léptetésére és a programkódba való betekintésbe. Következő lépés egy rekurzív fa ábrázolása. A fa ágainak számát egy bemeneti textbox segítségével lehet megadni. Harmadik program segítségével egy Sierpinski-háromszög kirajzolása. A háromszögben keletkezett háromszögek elhagyására egy gomb szolgál, mely lenyomásával lépésről lépésre rajzolódik ki a Sierpinski-háromszög. A program rendelkezik még egy gombbal, amellyel az előző lépest tudjuk előidézni. A következőkben a Koch-görbét (Koch-hópehely) ábrázoljuk, szintén egy háromszög segítségével. A működési eleve és a kinézete nagy részben megegyezik a Sierpinski-háromszögnél leírtakkal. A rendezési algoritmusok ábrázolására a buborékrendezést, összefésülő rendezést és a gyorsrendezést választottam. Az ábrázolás céljából a megszokott oszlopdiagram nyújt vizuális élményt. A tömbök véletlenszerű kirajzolására egy gomb szolgál. Szintén egy-egy gomb segítségével lehet az algoritmust elindítani, leállítani és léptetni. A program lehetőséget nyújt a rendezés gyorsítására és lassítására. Az előbb említett programok mellett megtalálható a működést előidéző forráskód is. A multimediális segédeszköz tárolására egy weboldal szolgál. HTML és CSS kódolás segítségével alakítottuk ki az oldal kinézetét. A programok külön egy-egy 10
menüpont alatt találhatók meg. Az weboldal lehetőséget nyújt a programrészek letöltésére, a szakdolgozat megtekintésére és egy kis ismertetőre a rekurzióról.
11
1 Rekurzió A rekurzió, mint fogalom megtalálható a matematikában, számítógépes tudományban, programozásban, de még a nyelvtudományban is. Olyan ismétlést jelent, amely az eljárások ismétlése révén juttat el az eredményhez. Tehát programnyelvre lefordítva, a program algoritmusa saját magát hívja meg az eredmény elérése érdekében, egy kívánt előre meghatározott lépésszámban a végtelen ciklus elkerülése végett. A nyelvtudományban a rekurzió fogalma alatt az taglaljuk, amikor a tagmondatok egymásba ágyazódnak, vagy amikor egy összetett szónak egy másik szó a része. Tehát potenciálisan végtelen különböző mondatot hozhatunk létre a rekurzió segítségével. Matematikában általában függvényeknél, halmazoknál és végtelenül önhasonló fraktáloknál jelenik meg a rekurzió fogalma. Függvényeknél kiváló példák a faktoriális, illetve a Fibonacci-sorozat. Fraktálok bemutatására szemmel látható rekurziót hozhatunk létre a Sierpinski-háromszög illetve a Koch-görbe (pehely) bemutatásával. Rekurziós fa ábrázolásával
szintén
egyszerű
ábrázolási
módszert
biztosíthatunk
a
rekurzió
megértéséhez. Az egyik legismertebb matematikai játék a Hanoi tornyai, szintén rekurzív algoritmussal oldják meg. Programozásban általában rendezési algoritmusok ábrázolásával lehet bemutatni a rekurzió értelmét és használatát. Az összefésülő illetve a gyorsrendezési algoritmusok alapműködési elve már rekurzív módon működik, de más rendezési algoritmusok (mint pl.: Bubble sort, Simple sort, stb.) forráskódja átalakítható rekurzív kódra (Rekurzió, 2015).
1.1 Faktoriális Egy n szám faktoriálisának nevezzük az n-nel egyenlő és kisebb egész számok szorzatát, amely számok pozitívak. Jelölése egy (!), melyet 1808-ban Christian Kramp vezetette be. Permanencia elv értelmében a 0! = 1, mivel a szorzandók nélküli szorzat értékét 1-nek vesszük. Az elv előnyösnek bizonyul, mivel a rekurzió érvényben marad az (n + 1)! = n! (n + 1) egyenletre, ha n = 0. A faktoriálisok reciprokainak összegeként felírható az e Euler-féle szám is, vagy esetleg a Taylor-sorokban is megjelennek (Faktoriális, 2014).
12
A rekurzív faktoriális működési elve JavaScript programozói nyelvben: function factorial(n) { // ha a szám negatív, akkor, elutasítja if (n < 0) { return -1; } // ha szám 0, akkor a faktoriálisa 1 else if (n == 0) { return 1; } // Ellenkező estben meghívja a rekurzív eljárást else { return (n * factorial(n - 1)); } }
1. ábra: Rekurzív faktoriális (kódrészlet)
1.2 Fibonacci-számok Az egyik legismertebb rekurzív sorozat. A Fibonacci-számok egy végtelenbe tartó sorozatot hoznak létre. Első kettő eleme a 0 és az 1, a következő elem pedig az előző kettő érték összege. Tehát a Fibonacci-sorozat első néhány eleme a következő képen néz ki: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … Fibonacci 1202-ben találta meg a sorozat működésének az elvét, mely akkori magyarázatát még máig tanított képzeletbeli nyúlcsalád növekedésével szemléltette, amely a következőképpen szól: "Hány pár nyúl származhat egy évben egyetlen pártól, ha minden pár havonta új párnak ad életet, amely a második hónaptól lesz tenyészképes, és feltételezzük, hogy egy ivadék sem pusztul el?". Ha például azt szeretnénk meghatározni, hogy hányféleképpen juthatunk egy lépcső n-edik fokára, akkor szintén a Fibonacci-sorhoz jutunk, ha feltételezzük, hogy egyszerre csak egy vagy kettő lépcsőfokra tudunk lépni (Fábián, 2005). A rekurzív Fibonacci-számsor működési elve JavaScript programozói nyelvben: function fib(n) { return function(n,a,b) { return n>0 ? arguments.callee(n-1,b,a+b) : a; }(n,0,1); }
2. ábra: Rekurzív Fibonacci-számok (kódrészlet)
13
1.3 Bináris fa (rekurzív fa) Ha minden elemnek legfeljebb két rákövető eleme van, akkor bináris fáról beszélünk. Szigorúnak vett bináris fának nevezzük, ha minden rákövetkező elem 0 vagy 2. Rekurziós fa kialakításához a kezdő ág egy standard helyzetet vesz fel, mely végpontjára rekurzívan előhívunk egy akár véletlen, akár előre meghatározott dőlésű két ágat. Egyet pozitív, egyet negatív irányban. A kirajzolódott ágak végpontjaira rekurziót alkalmazunk (Fábián, 2005).
3. ábra: Rekurzív fa
1.4 Bináris keresés A bináris keresés (más néven logaritmikus keresés), egy olyan kereső algoritmus, mely egy rendezett tömbben lévő elem (v) keresésére használnak. Feladatunk eldönteni, hogy az A tömb elemei közt a v elem előfordul-e. Ha igen, akkor az is érdekel bennünket, hogy a v elem hányadik helyen fordul elő az A tömb elemei között. Az eljárást rekurzió használatával is megoldhatjuk. Első lépésként az A tömb középső elemével hasonlítjuk össze a v elemet. A középső elem legyen A[k]. Ha v megegyezik az A[k] elemével, akkor készen is vagyunk. Ha nem, akkor a v elem helyét elég az A[1],…A[k - 1] vagy az A[k + 1],….A[n] elemek között 14
keresni attól függően, hogy v < A[k], vagy v > A[k]. A keresés lebonyolítását a fele akkora „résztömbökön” pontosan úgy végezzük el, mint a keresés elején. Tehát, vagy megtaláljuk egy lépéssel a v-t, vagy visszavezetjük a feladatot egy feleakkora feladatra. Az eljárást addig ismételjük, ameddig a felezés lehetséges. Nézzük a rekurzív vázlatot. Az eljárást az (A, v, 1, n) paraméterekkel kell meghívni. Az algoritmus költsége O(log n) (Szabó, 2015). RekurzívBinárisKeresés(A,v,i,j) if i>j then return * középső=[(i+j)/2] if A[középső]=v then return középső else if A[középső]>v then return RekurzívBinárisKeresés(A,v,i,középső-1) else return RekurzívBinárisKeresés(A,v,középső+1,j)
(Szabó, 2015) 4. ábra: Rekurzív bináris keresés (kódrészlet)
1.5 Fraktálok A matematikában már az 1880-as évektől találkozunk fraktálokkal. Igaz eleinte, mint matematikai érdekesség. 1975 körül Benoit B. Mandelbrot amerikai matematikus kezdte összegyűjteni ezeket az alakzatokat, majd elnevezte a latin fractus szóból fraktáloknak. Latin jelentése törött, töredezett. Azokat a geometriai alakzatokat nevezte így, melyek összetettebbek, töredezettebbek, szabálytalanabbak a klasszikus geometria alakzatoknál. Pontos definíció a fraktálokra a mai napig nem létezik. Többen megpróbálták a definíciót meghatározni, de minden esetben találtak egy fraktált vagy fraktál csoportot, melyre a definíció nem felelt meg. Igazi fraktált a valóságban nem lehet előállítani, mivel a körvonalai a végtelenségig csipkéződnek, finomodnak. Ehhez végtelen sok időre és végtelen eszközökre (képernyő felbontása) lenne szükségünk, ami lehetetlen. Ezért csak elképzelni tudjuk teljes valóságban a fraktálokat.
Legegyszerűbb véges
fraktálok egyszerű rekurzióval
előállíthatók. Ilyenek pl.: Cantor-por, Koch-görbe, Koch-hópehely, Sierpinski-háromszög, Sierpinski-szőnyeg, stb (Fraktálok, 2015).
15
1.5.1 Cantor-por Az egyik legrégebben felfedezett fraktál. 1883-ban Georg Cantor jelentette meg. Előállítása szempontjából egyszerű. Vegyünk egy véges szakaszt. Első lépésként vágjuk ki a szakasz középső egyharmadát. A keletkezett szakaszok középső egyharmadát ismét vágjuk ki, majd így tovább. Végtelen lépés után kapnánk egy Cantor-port, vagy Cantorhalmazt (Fraktálok, 2015). A Cantor-por ábrán való ábrázolása:
5. ábra: Cantor-por
1.5.2 Koch-görbe 1906-ban Helge von Koch svéd matematikus írta le először a Koch-görbét. A görbe előállításának ötlete megegyezik a Cantor-poréhoz. Első lépésként szintén egy szakaszt veszünk, amit felharmadolunk. A felharmadolt szakasz középső részét elhagyjuk és helyette egy „sátrat“ emelünk. A „sátor“ két szakaszának hosszúsága megegyezik az előbbiekben felharmadol szakasz egyharmadával. Következő lépésekben az új és a megmaradt szakaszokra ugyanezt a módszert alkalmazzuk. Ezt nevezzük rekurziónak (Koch-görbe, 2014). A Koch-görbe első négy lépése ábrán:
6. ábra: Koch-görbe 16
1.5.3 Koch-hópehely A Koch-hópehely más néven Koch-sziget, három darab azonos hosszúságú szakaszból áll, amely szakaszok kapcsolódási pontjai alapján egy szabályos háromszöget kapunk. Működésének elve azonos a Koch-görbével, csak ebben a helyzetben nem egy szakaszt kell felharmadolni, hanem a szabályos háromszög mindhárom oldalát. Az oldalainak, szintén a középső harmadára emeljük az azonos oldalú „sátrat”. A következőkben már 12 oldalt harmadolunk és így tovább. A leírtakból látszik a rekurzió fontossága a fraktál kialakításnál (Koch-görbe, 2014). A Koch-pehely első négy lépése az ábrán látható:
7. ábra: Koch-hópehely
1.5.4 Sierpinski-háromszög 1916-ban egy lengyel matematikus Waclaw Sierpinski mutatta be először a fraktált. A fraktál kialakítása nem túl bonyolult. Rekurzió segítségével könnyen kivitelezhető. Első lépésként vegyünk egy szabályos háromszöget. A háromszög oldalainak felezőpontjait kössük össze. Az összekötött pontokból kaptunk egy szabályos háromszöget, amelyet kivágunk. Ha követtük a leírt utasításokat, akkor maradnia kellett három kisebb háromszögnek. A maradt háromszögek oldalainak a felezőpontjait összekötjük, majd a létrejött háromszöget kivágjuk. És eme lépéssorozatok végtelen végrehajtása után kapnánk meg a Sierpinski-háromszöget (Sierpinski, 2014). A Sierpinski-háromszög első négy lépéssorozata ábrán szemléltetve:
17
8. ábra: Sierpinski-háromszög
1.5.5 Sierpinski-szőnyeg A háromszöghöz hasonlóan a Sierpinski-szőnyeg szintén síkbeli fraktál. Az előállítás ötlete egyezik. Különbség, lényegében a háromszög helyetti négyzet használata. Tehát első lépésként vegyünk egy négyzetet. A négyzet oldalainak jelöljük ki a harmadoló pontjait, majd a szemben lévő pontokat kössük össze. Így az egy nagy négyzetből kilenc kicsit kapunk. A középső négyzetet vágjuk ki. A maradék 8 négyzetnek ugyanígy vágjuk ki a közepét. Majd a keletkezett négyzetekkel tegyük ugyanezt, és így tovább. Amit végtelen lépés után kapnánk, az nevezhetnénk Sierpinski-szőnyegnek (Sierpinski, 2014). A Sierpinski-szőnyeg első négy lépése:
9. ábra: Sierpinski-szőnyeg
1.6 Hanoi tornyai A játékot Édouard Lucas francia matememtikus találta fel 1883-ban. Az ötletet egy legendából kapta, ami szerint Brahma szerzetesei egy 64 korongból álló hanoi torony feladványt kezdtek el megoldani a világ megteremtésekor. A legenda szerint, amint a szerzetesek végeznek, a kolostor összeomlik és a világ megszűnik létezni. A feladvány lényege, hogy a játék során van három rúd. Az első rúdon, tetszőleges számú különböző méretű korong található, amely méret szerint van rendezve úgy, hogy 18
a legnagyobb alul helyezkedik el. A játékban át kell rakni a korongokat egy másik rúdra úgy, hogy egyszerre csak egy korongot mozgathatuhk, és egy korng sem helyezhető nála kissebb korongra. A kérdés, hogy minimum hány lépéssel lehet a korongokat áthelyezni (Hanoi tornyai, 2014).
10. ábra: Hanoi tornyai A feladat megoldható rekurzív algoritmussal is. Ami a következő:
Hanoi(n, I, J, K) if not n = 0 Hanoi(n-1, I, K, J) Atrak(I,J) Hanoi(n-1, K, J, I) end if end Hanoi
11. ábra: Hanoi tornyai (kódrészlet) Az Atrak(A,B) eljárás az A rúdról áttesz egyetlen korongot a B rúdra. Az algoritmus futásideje: Θ(2^n).
19
2 Rekurzió a rendezési algoritmusokban Amint már szó esett róla, a programozásban is sokszor találkozunk a rekurzió fogalmával. Nincs ez másképp a rendezési algoritmusok végbemenetelénél sem. A rekurzió szerepet játszik az „oszd meg és uralkodj” elvben. Az összefésülő rendezés is ezt az elvet képviseli. Egy n elemű tömböt feloszt két n elemű résztömbre, majd a két résztömböt összefésülő rendezéssel rekurzívan rendezi. A rekurzió fontos szerepet játszik még a gyorsrendezésnél (más néven Quick sort), ami szintén az „oszd meg és uralkodj” elvet követi. A buborékrendezés (Bubble
sort),
kiválasztó rendezés (Selection sort), stb.
rendezési algoritmusok működési elve iteratív. Tehát egymásba épülő ciklusokat használnak. Iteratív algoritmusok átalakítása rekurzív algoritmusokká egyszerű, de nem célszerű. Általában az iteratív megoldás gyorsabb. A rekurzív hívások következményeként adódik a veremkezelés követelménye, ami természetesen a helyfoglalást is megnöveli. Lényegében, ha döntés előtt állunk meg kell vizsgálni az iterációt és a rekurzió hatékonyságát az algoritmus alapján (Adonyi, 2011).
2.1 Oszd meg és uralkodj elv A Római Birodalom politikai módszerét kifejező elv. Az elv, az algoritmusok szerkesztésére vonatkozó paradigma is egyben. Jelentése, hogy egy tömböt több kisebb részre osztja, majd a kisebb részeket rendezi. A rendezett tömb előállítása a kisebb tömbök rendezésén alapszik. Lépésenként a módszer a következő: 1. A problémát felosztjuk több alproblémára. 2. Uralkodunk az alproblémákon. - ha az alroblémák mérete kicsi, akkor megoldjuk - egyébként az alproblémákra újra az „oszd meg és uralkodj” elvet alkalmazzuk rekurzív megoldással 3. Összevonjuk az alproblémák megoldásait, és megkapjuk az eredeti probléma megoldását (Szabó, 2015)
20
2.2 Összefésülő rendezés (Merge sort) Az összefésülő rendezés is az „oszd meg és uralkodj” elv alapján rendezi a tömböt. Az alapötlet abból ered, hogy ha van kettő rendezett résztömbünk, akkor azokból könnyen kaphatunk egy rendezett tömböt, ami tartalmazza az összes résztömb elemeit. Ezt nevezzük összefésülő műveletének. Tételezzük fel, hogy van kettő rendezett tömbünk A és B. Az A tömb n elemet tartalmaz, és B tömb viszont m elemet. Egy C tömbben szeretnénk tárolni az A és a B elemeit rendezett formában. Tehát a C tömb nagysága n + m. A C tömb első elme az A, vagy a B tömb első indexén található elem lesz, mivel rendezett tömbökről beszélünk. Az átírt értéket a továbbiakban nem vesszük figyelembe. A C tömb következő eleme az A, vagy a B tömb aktuális legkisebb eleme közül a kisebb lesz. Minden egyes összehasonlítás után egy elem a helyére kerül. Kivételt képez az utolsó összehasonlítás, mert akkor kettő elem kerül a helyére. Hatékony műveletnek számít, mivel a tömbök egyszeri végigolvasásával létrejön a rendezett sorozat. Az összefésülő rendezés is alkalmazza az előbb említett műveletet. A rendezés a rekurzión, alapszik. Összefésülő rendezéssel rendezzük a tömb első és második felét külön-külön. Utána fésüljük össze a rendezett résztömböket. Az algoritmus pszeudo kódja a következő: void MergeSort(d, i, j) { if(i < j){ mid = [(i + j) / 2]; MergeSort(d, i, mid); MergeSort(d, mid+1, j); Osszefesul(d, i, mid, j); } }
(ADONYI, 2011) 12. ábra: Merge sort (kódrészlet) Az összefésülő rendezés addig bontja kisebb részekre a tömböt, míg a vizsgált tömb elemeinek a száma megegyezik egyel. A résztömbökre bontáshoz meghatározzuk a tömb középső elemét, ami a kódunkban a mid. Ha az algoritmus eljutott az egy elemű tömbökhöz, akkor az Osszefesul() függvény segítségével összefésüli azokat. A függvény paraméterei a d tömb, és az indexek, amik a rendezett résztömböket jelölik. Az 21
összefésülés nem helyben rendező algoritmus, ami miatt szükséges egy segédtömböt használni. Az összefésülő rendezés komplexitása legrosszabb esetben O (n logn) (Merge sort, 2014).
2.3 Gyorsrendezés (Quick sort) A gyorsrendezés is az „oszd meg és uralkodj“ elvén rendezi a tömböt. Tehát a jelentése, hogy egy tömböt több kisebb részre oszt, majd a kisebb részeket rendezi. A rendezett tömb előállítása a kisebb tömbök rendezésén alapszik. A rendezés során két részre osztjuk az eredeti tömböt. Az egyik részben a kulcs értékénél (pivot) kiesebb elemek kerülnek, a másik részben pedig a kulcs értékénél nagyobb elemek kerülnek. Egy elemünk már a rendezett tömb megfelelő helyére került, ami az előbbiekben kiválasztott kulcs. Tehát a két résztömböt felbontjuk még két-két résztömbre és rendezzük egy új pivot segítségével. A kisebb tömbökre való particionálás addig folytatható, míg egy elemű résztömböket kapunk. A gyorsrendezés hatékonysága függ a pivot (kulcs) kiválasztásától. Egy jó pivot érték megtalálása nem triviális feladat. Akkor választottunk jó pivot értéket, ha a keletkezett résztömbök mérete közel azonos egymáshoz. Több módszert ismerünk a pivot értékének kiválasztására. Legegyszerűbb, ha a tömb majd a résztömbök legelső elemét választjuk. Ennél jobb érték, ha több tömbelem átlagát választjuk pivotnak. A gyorsrendezés komplexitása átlagos esetben O(n logn). Legrosszabb estben pedig a négyzetes komplexitású algoritmusok közé tartozik. Legrosszabb eset akkor jön létre, ha a pivot érték kiválasztása után, az egyik résztömb mérte, az algoritmus lefolyása során állandóan 1 (Gyorsrendezés, 2014).
22
3
Oktatási segédlet felületének megtervezése A szakdolgozatban kitűzött cél elkészítésében fontosnak tartjuk ismertetni a
létrehozás során felhasznált eszközöket, a program felépítését, valamint a metódusokat.
3.1 Felhasznált eszközök bemutatása Egy oktatásra szánt segédeszköz megalkotásánál először a programnyelvet kell megválasztani. Kiválasztani, hogy melyik nyelv felel meg legjobban a számunkra. Fontos tényezőnek számít a program futtatására szánt környezet. Mivel a segédeszköz elsődleges céljai közé tartozik, hogy on-line weboldalakon futtatható legyen, ezért döntöttünk az objektumalapú JavaScript programozói nyelv mellett. A JavaScriptben megírt forráskód megszerkesztésére, lényegében bármilyen szövegszerkesztő megfelel. A döntésünk mégis a Notepad++ szerkesztőre jutott. A Notepad++ áttekinthetővé teszi a forráskódot színek alapján, valamint leegyszerűsíti a szerkesztést az automatikus kitöltés lehetőségével. Az eszköz feltüntetése érdekében létrehoztunk egy weboldalt. A weboldal létrehozásának céljából a HTML leíró nyelvet és a CSS stílusleíró nyelvet használtuk. Az oldal sorait szintén a Notepad++ segítségével írtuk a már említett előnyei miatt.
3.2 HTML A HTML (HyperTextMarkup Language) egy leíró nyelv. Weboldalak létrehozására fejlesztették ki. A W3C (World Wide Web Consortium) támogatásával mára már internetes szabvánnyá vált. A HTML-ben négyfajta szimbólum található. Ezek a strukturális elemek, a prezentációs szimbólumok, a hiperszöveg elemek és az eszköz elemek. HTML szerkezete három fő részből áll, melyek a következők: - Az első sorban egy úgynevezett DTD (DocType = Document Type Definition) áll, melyben meghatározzuk a dokumentum típusát. Erre azért van szükség, hogy a böngészők megtudják milyen elemeket és attribútumokat használ az oldal. - Az oldalnak és címkék között kell elhelyezkednie. A következő lépés a fejléc kialakítása, melyet a és címkék közé helyezünk. Ide tartoznak, a meta címkék közti részek, ami a háttér információkat tartalmazza, a title címkék közötti rész és a hivatkozások (pl.: script-re való hivatkozás vagy CSS-re stb.). - A harmadik rész az, amit már a látogatók is látni fognak. Az oldalon megtalálható címkéket, írásokat a body címkék közé rakjuk (HTML, 2015). 23
3.3 CSS A CSS (Cascading Style Sheets) a számítástechnikában egy stílusleíró nyelv, mely segítségével különböző stíluslapokat hozhatunk létre és ágyazhatunk be HTML honlapjainkba. Ezen kívül még használható más dokumentum stílusleírására is, mint például XHTML vagy XML. Befolyásolja az oldal megjelenítését. Meghatározzuk vele a címkék méretét, színét, típusát, hogyan és hol jelenjenek meg stb. A CSS megjelenésének oka az volt, hogy a weblapokon egyre bonyolultabb kinézetet igényeltek a felhasználók. HTML adatszerkezettel már nem nagyon lehetett megoldani, mivel a sok rendezés, színek meghatározása és más hasonló formázások bonyolultabbá és átláthatatlanná tették a forráskód szerkezetét. Manapság már a legtöbb böngésző támogatja a CSS nyelv elemeit, de még mindig vannak olyan böngészők, melyek egyes CSS parancsot rosszul jelenítenek meg vagy kihagynak. Håkon Wium Lie elhatározta, hogy a web számára készít egy stíluslap leíró nyelvet, mely a CSS nevet fogja viselni, amit 1994-ben mutattak be. Akkor még csak HTML nyelvhez kidolgozva. Nem sokkal később Bert Bos csatlakozott hozzá, és megalkottak egy olyan stílusnyelvet, amely a HTML mellett más leíró nyelvekhez is használható. 1996-ban hivatalosan is megjelent a CSS level 1, ami weboldalak megjelenítése terén új korszakot nyitott. Két év múlva a level 2, majd a CSS level 3 (CSS, 2015).
3.4 JavaScript programozási nyelv A JavaScript programozási nyelv objektum alapú szkriptnyelv, amelyet elterjedten használnak weboldalakon. A Netscape Communications mérnöke, Brendan Eich fejlesztette ki. Eleinte a Mocha majd, a LiveScript nevet viselte, és csak később kapta meg a JavaScript nevet. Jelenlegi érvényes szabványát még 1999-ben kapta. Ez a szabvány egyben ISO szabvány is. A JavaScript az első, és máig a legnépszerűbb webes parancsnyelv. A JavaScript programkódot közvetlen a HTML kódba is elhelyezhetjük <script> és a címkék közé. A böngésző csak a záró címke után tér vissza a HTML üzemmódba. Ha összetettebb programokat készítünk JavaScript programozási nyelven, akkor érdemes külső JavaScript fájlokat használni, melynek kiterjesztése .js. Így elkerüljük a HTML fájl méretének megnövelését és olvashatatlanságát. A .js kiterjesztésű fájlok
bármilyen
szövegszerkesztőben
megszerkeszthetőek.
Ügyelnünk
kell
a
kiterjesztésére és, hogy csak JavaScript utasításokat tartalmazzanak. Nagy előnyük, hogy a 24
.js fájlt más HTML dokumentumban is felhasználhassuk. Tehát, ha egy weblap több mellékoldalán is szeretnénk használni a js fájlt, akkor elég csak hivatkozni rá az adott mellékoldalon. HTML kódban a külső js-re való hivatkozás a következő (Michael, 2002 ): <script src=”fajl_neve.js”>
3.4.1 Notepad++ A Notepad++ egy ingyenesen letölthető szöveg- és forráskódszerkesztő, melyet kifejezetten Microsoft Windows platformra fejlesztettek ki. Később továbbfejlesztették, hogy alkalmazható legyen akár Linux vagy akár Mac OS X rendszerek használata mellett is. A Notepad++ egyik fő előnye a Windows beépített szövegszerkesztővel szemben, hogy tartalmaz egy fülekkel ellátott felületet. A felület lehetővé teszi egyidejűleg több fájl párhuzamos szerkesztését,továbbá támogatja a UNIX/LINUX sorvégeket is. Az automatikus kiegészítés, szintaxis színnel való kiemelése, könyvjelzők, reguláris kifejezés használata keresés és csere funkcióhoz megkönnyítik és felgyorsítják a munkálatokat. A Notepad++, olyan méretű népszerűségre tett szert, hogy a legfrissebb adatok szerint a Notepad++ megközelíti az ötvenmillió letöltést a világhálóról. Kétszer megnyerte a Community Choice Award for Best Developer Tool díjat (Notepad, 2014).
25
4
A segédeszköz létrehozása Első lépésként létrehoztunk egy weblapot a segédeszköz számára. Az oldalon
lépésről lépésre figyelemmel tudjuk kísérni a program működésének helyességét, és szemügyre venni az esetleges hibákat. Fontos szerepet játszott számunkra a vizuális kinézet kialakítása az oldal struktúrájához. A soron következő alfejezetekben ismertetjük az egyes munkafázisok kialakításának metódusait. (A weboldal megtalálható a www.attilanagy.esy.es oldalon és a mellékletben is)
4.1 Weboldal létrehozása A weboldal létrehozásánál az egyszerűséget tartottuk szem előtt. Nem arra törekedtünk, hogy minél komolyabb struktúrát öltsön magára az oldal, hanem arra, hogy minden kéznél legyen. A szakdolgozat célja nem a weboldal, hanem az volt, hogy lehetőség legyen a programot könnyen integrálni on-line HTML környezetbe, amit az oldal szemléltet is. A weboldal létrejöveteléhez HTML és CSS kódolást használtunk, és mint már említettük a Notepad++ szerkesztő volt segítségünkre.
4.1.1 Fejléc létrehozása A fejléc egy általunk szerkesztett kép, ami a rekurzióra próbál rávezetni. Egyszerűség elvén próbáltuk pár kép összevágásával kialakítani. A fejléc a weboldal összes felületén megtalálható.
13. ábra: Weboldal fejléce
26
4.1.2 Menü létrehozása A weboldalon két menü található. Egy vízszintes és egy függőleges menü. A vízszintes menü kinézetének struktúrája egyszerű. Szürke háttérben találhatók meg a menüpontok. A menügombra való kattintás során a gomb felülete megváltozik, a hover CSS utasítást használva. A menücsíkon a kidolgozott programrészek találhatók. Sorrend szerint a következők: Faktoriális, Rekurzív fa, Sierpinski-háromszög, Koch-görbe, Bubble sort, Merge sort és Quick sort. Eme mellékoldalak struktúrája megegyezik a főoldal struktúrájával. Annyiban különböznek, hogy a programok vizualizálása céljából elhelyeztünk minden oldalon egy méretnek megfelelő vásznat (canvas). Függőleges menücsík struktúrája követi a vízszintes menücsík struktúráját. A különbség annyi, hogy a menüpontok egymás alatt helyezkednek el a weboldal bal felén. A menü első eleme a „Főoldal”, amely segítségével bármely mellékoldalról vissza tudunk lépni a bevezető felületre. A függőleges menücsík alá tartozik még három gomb. Az egyik gomb a „Rekurzió” nevet viseli, amely alatt a rekurzió és néhány fraktál rövid magyarázatát tekintheti meg a látogató. A következő gomb neve „Szakdolgozat”. A szakdolgozat menügomb alatt letölthető a megírt szakdolgozatunk dokumentációja, és hivatkozások
találhatóak
meg
a
szakdolgozat
megírása
folyamán
használt
segédanyagokhoz. Az utolsó gomb pedig a „Letöltések”, ahol a programrészek tölthetők le külön-külön és egyben is.
14. ábra: Weboldal menüpontjai
4.1.3 Bevezető felület Miután létrehoztuk a fejlécet és a menüt, rátértünk a bevezető felület kidolgozására. A bevezető felületen sor kerül a szakmunka rövid leírására. Itt ismertetjük, a programok használatának útmatatóját és a menüpontok tartalmának leírását is.
27
4.1.4 Lábléc létrehozása A weboldalon megtalálható lábléc létrehozásánál szintén szerepet játszott az egyszerűség elve. A menüpontok szürke és a fehér színárnyalatát alkalmaztuk. A láblécen megtalálható egy hivatkozás, amely az egyetemünk honlapjára vezeti el a látogatót. 4.2
Faktoriális segédeszköz kialakítása Első lépésként létrehoztunk egy mellékoldalt, melyet „faktorialis.html” néven
mentettünk el. Az oldal szerkezete megmaradt a főoldaléval, tehát a megírt kódot átmásoltuk. A body-ban megtalálható menükön kívül, elhelyeztünk egy bemeneti TextBox-ot. A TextBox, a faktoriális méretének lekérdezésére szolgál, melynek adtunk egy id ismertetőt, ami nem más, mint a „valtozo”. Kettő gomb található még az oldalon. Az egyik a „Tovább”, melynek a onClick ismertetője „faktorialis()”. A másik gomb a „Töröl”, mely onClick ismertetője „torol()”. Létrehoztunk még két kiíratásra szánt p címkét, melynek id ismertetői „be” és „ki”. A weblap bal oldalán a program lépésről lépésre való kiíratását tekinthetjük meg, a jobb oldalon pedig a forráskódot, ami alapján működik. Következő
lépésként
létrehoztunk
egy
„faktorialis.js”
fájlt,
melyre
a
„faktorialis.html” head részében hivatkoztunk. A „faktorialis.js” fájlba két function elegendő volt a faktoriális kiíratására. Az első function a „faktorialis()”. A HTML kódban már gombnyomásra hivatkozunk erre a function-re. A gomb lenyomásával először beolvassa az adatot a TextBox-ból, és elmenti egy „valtozo” nevű változóba, majd kiírja a beolvasott számot. Átellenőrizzük, hogy a szám pozitív legyen. Ha a szám kisebb, mint 0 akkor kiírja, hogy „Csak pozitív számot!”. Ha a beolvasott szám 0, akkor a faktoriális 1 lesz és kiírja azt. Ha a feltételeknek eleget tettünk, akkor jöhet a faktoriális számítása. A számítás menetéről már beszéltünk a fentiekben. Az interaktivitás végett a rekurziót gombnyomás segítségével lehet előidézni. Ez alapján lépésről lépésre kiírhatjuk a faktoriális működésének elvét. A weboldalon lévő faktoriális lépésként való ábrázolása a következő:
28
15. ábra: Weboldalon lévő faktoriális ábrázolása
4.3 Rekurzív fa kialakítása a weboldalra Mint a faktoriális kialakításánál most is először a weboldalt állítottuk elő. A főoldalról való másolás segítségével megkaptuk a mellékoldal struktúráját. Egy beviteli mezőt helyeztünk el, ami segítségével megadhatjuk a rekurzív fa méretének nagyságát. A TextBox id neve ismét „valtozo”. Két gombot helyeztünk el. Az egyik az „Indít”, a másik pedig a „Töröl”. Az indít gombbal indítjuk el a fa kirajzolását, amelynek a onClick ismertetője a „indit()” metódus. A törlés gombbal töröljük a már kirajzolt vagy épp kirajzoló félben lévő fát, melynek onClick neve „torol”. A fa kirajzolása céljából létrehoztunk egy vásznat (canvas), mely szélessége és magassága egyaránt 600 pixel. A fa forráskódját ismét, a weblap bal oldalára, tehát a canvas bal felére tettük. Következő lépés a js fájl kialakítása volt. A JavaScript fájl nevének a „rek_fa.js”-t adtunk, amellyel hivatkozunk is rá. Az első function az „indit()”. Az indít gomb lenyomásával beolvassuk a kívánt fa nagyságát, majd belerakjuk egy „meret” nevű változóba. Ha a „meret” kisebb, mint 3 akkor újra bekérjük a fa méretét, ha viszont nagyobb, mint 17 akkor szintén újra meg kell adnunk az adatot. A sok ág kiszámítása és kirajzolása megterhelő a CPU számára, ami a böngésző leállásához vezethet. Ha eleget tettünk a feltételeknek, akkor automatikusan meghívunk egy „tartalom()” function-t. A „tartalom()” function a fa kezdetleges értékeit tartalmazzák, mint pl.: törzs hosszúságát, az ágak dőlésének szögeit, vastagságát stb. A function végénél meghívjuk az „agak()” function-t. Ebben a function-ban lépésenként csökken az ágak hosszúsága, vastagsága. Itt számoljuk ki az ágak érkezési pontjait, ami egyben a következő ágak kiindulási pontjai is. Tehát ezeket a pontokat eltároljuk egy „pontok_kezdete[]” nevű tömbben. Megadjuk, hogy ha az ágak rövidebbek, mint 70 pixel, akkor zöld színűek legyenek, ha viszont nem akkor barnák. A végén pedig megadjuk, hogy ha a „meret” nem egyenlő egy „szamlalo” nevű 29
változóval (a „szamlalo” az „agak()” function lefutását számolja), akkor setTimeout paranccsal rekurzívan meghívjuk az „agak()” function-t egy másodperces késleltetéssel. Az ábra weboldalon lévő rekurzív fa 5. illetve a 12. lépéssorozatát ábrázolja:
16. ábra: Weboldalon lévő rekurzív fa ábrázolása
4.4 Sierpinski-háromszög kialakítása a weboldalra A Sierpinski-háromszög fraktál ábrázolása céljából egy újabb mellék weblapot hoztunk létre, mely struktúrája megegyezik az előbbiekkel. A weblapon található egy kiírás, mely a háromszög mélységének számát szemlélteti. Továbbá az oldalon található még három gomb. Az egyik a háromszög kirajzolását biztosítja, a másikkal az előző lépés ábrázolását tudjuk meghívni, a harmadik pedig a háromszög törlésére szolgál. Mind a három gombhoz onClick tulajdonságot rendeltünk. A háromszög kirajzolásának céljából létrehoztunk egy canvas-t. A vászon szélessége 600 pixel és a magassága pedig 460 pixel. A Sierpinski-háromszög forráskódja a megszokott bal oldalon helyezkedik el a weblapon, amiből következtethetünk arra, hogy a fraktál ábrázolása pedig a jobb oldalon. A következő lépés ismét a JavaScript fájl kialakítása volt, melyet „sierpinski.js” néven mentettünk, majd hivatkoztunk rá. Az első function, a „rajzolas()”. Itt adjuk meg a háromszög színét, és a keletkezett háromszögek színeit is. A böngésző lefagyásának elkerülése végett beállítottuk, hogy a háromszögbe meghívott háromszögek mélysége tíz legyen. Meghívjuk a „fraktal()” function-t, amely kiszámítja a kisháromszögek oldalainak
30
hosszúságát, majd egy „eoHaromszog()” function meghívásával kirajzolja azokat. Megtalálhatunk még egy „torol()” és egy „vissza()” function-t a JavaScript fájlban. Az ábrán, a weboldalon lévő Sierpinski-háromszög néhány lépése figyelhető meg:
17. ábra: Weboldalon lévő Sierpinski-háromszö ábrázolása
4.5 A Koch-görbe (hópehely) kialakítása a weboldalra A segédeszközön lévő Koch-görbe, lényegében hópehely lesz, mivel három egyforma görbéből áll össze, mely végpontjainak összekötéséből egy szabályos háromszöget kapunk. A mellékoldalunk kialakítása rendhagyó módon történt. Az oldalt szintén a főoldalról mintáztuk. A gombok és a kiírások hasonló struktúrát kaptak, mint a Sierpinski-háromszög-nél. Három gomb tehát a tovább, vissza és a törlés nevet viseli. Szintén a gombok onClick hívással hívják meg a js fájlban található function-t. A canvas mérete nagyobb lett, mint az előbbiekben, mivel a kezdeti háromszög területe növekszik. A szélesség és a magasság egyaránt 600 pixelt kapott. A vászon a megszokott módon az weblap bal oldalán helyezkedik el, és a forráskód pedig a jobb oldalon. Következhet a JavaScript fájl kialakítása. A HTML fájlból való hivatkozás a „koch.js” fájlra hivatkozik, mivel ilyen név alatt mentettük el a JavaScript fájlt. Három fő function-t tartalmaz. A „rajzol()” function, a háromszögek kirajzolásáról gondoskodik. A „novel()” function, az új háromszögek végpontjait számolja ki és menti egy ideiglenes 31
tömbbe. Minden léptetés után növekszik a tömb mérete. A „feloszt()” function a szegmenseket osztja fel. E három function egymás meghívásával, lépésenként az oldalak középső egyharmadára kirajzolódik egy újabb háromszög. Az ábra weboldalon lévő Koch-hópehely első, harmadik illetve hatodik lépése:
18. ábra: Weboldalon lévő Koch-hópehely ábrázolása
4.6 Rendezési algoritmusok ábrázolása A rendezési algoritmusok ábrázolását a megszokott oszlopdiagram segítségével oldottuk meg. Három rendezést választottunk a rekurzió bemutatására. Az összefésülő rendezés (Merge sort) és a gyorsrendezés (Quick Sort) tartalmaz rekurzív függvényeket és a működésük elve is a rekurzión alapszik. A harmadik rendezési algoritmusnak a buborékrendezést (Bubble sort) választottuk, amely egymásba ágyazott ciklusokkal (iteratív) működik. A rendezés átalakítható rekurzív rendezésre.
4.6.1 A rendezési algoritmusok kinézete HTML forráskódban A rendezési algoritmusok a weboldalon külön-külön mellékoldalon vannak elhelyezve. Az algoritmusok ábrázolására egy canvas-t használunk. A canvas szélessége 600 pixel a magassága pedig 460 pixel. Mindhárom rendezési algoritmusnál ugyanazt a kinézetet választottuk. A canvas alá helyeztük el az irányítópanelt. Az irányítópanel négy gombból és egy checkbox-ból áll. Az első gomb segítségével véletlenszerűen tudunk kigenerálni különböző nagyságú elemeket. Az elemek száma konstans 16. Az elemek megjelenítése, mint már említettük oszlop kinézetűek. Az oszlopok magasságai nem egyezhetnek egymással, tehát tizenhat 32
különböző magasságú oszlopot kapunk. Az oszlopok alatt található egy számsor. A rendezés nem befolyásolja a számsort. Feladata szemléltetni a rendezés során már rendezett elemeket. Az irányítópanel következő része egy checkbox. A checkbox segítségével tudjuk a rendezést gyorsítani akkor, ha az értéke true. A gyorsítás bekapcsolásával az algoritmus ábrázolása 200 delay sebességre vált, ami 0,2 másodpercnek felel meg. Az irányítópult következő eleme az algoritmus elindítására szolgál. A gomb disabled állapotot vesz fel, amint rákattintunk. Tehát nem tudjuk újra lenyomni. Egyetlen gomb maradt elérhető formában, a leállítás gomb, ami a vezérlőpult következő eleme is egyben. A leállítás gombot csak akkor tudjuk használni, amikor az algoritmus fut. Más esetben disabled állapotban van. Ha leállítjuk a programot, akkor újra elérhető lesz a futtatás és az irányítópult következő eleme is, ami nem más, mint a léptetés. A léptetés gombra kattintva tudjuk irányítani a rendezési algoritmus lépéseit. A vezérlőpultot a 19. ábrán tudjuk megtekinteni.
19. ábra: Rendezési algoritmusok ábrázolására szolgáló vezérlőpult Az irányítópult alatt találunk két kiírást. „Az összehasonlítás” szöveg mellett egy számláló található. A számláló akkor növekszik, amikor a futásban lévő algoritmus összehasonlít egymással elemeket. A második kiírás mellett egy számlálón tudjuk követni, az algoritmus folyamán létrejött áthelyezések számát. Az algoritmus vizualizálására szolgáló canvas mellett megtalálható, a rendezési algoritmus rekurzív pszeudokódja.
4.6.2 A rendezési algoritmusok JavaScript kódjai Az előbbiekben már szó esett a rendezési algoritmusok kinézetéről és hasonlóságukról. A hasonlóságra hagyakozva létrehoztunk egy közös JavaScript fájlt, melyre a mellékoldalak egyaránt tudnak hivatkozni. A közös JavaScript fájlnak a „kinezet.js” nevet adtuk. A fájl megírásánál arra törekedtünk, hogy az algoritmusok közös tulajdonságait tartalmazzák. Ilyenek az oszlopdiagram elemeinek tulajdonságai is. Meghatároztuk az oszlopok színét, álló és mozgó pozícióban, a keret és a számsor színét stb. Az „ujsort()” function tartalmaként kialakítottuk a véletlen elrendezésű oszlopdiagram meghívását, és a kiírások kimenetelére 0 állítottunk. Az oszlopok mérete a canvas 33
szélességétől és magasságától függ. Ezt a lépést fontosnak tartottuk, mivel más HTML oldalakra való beágyazás során a canvas mérete az oldal struktúrájától függ. Több function szolgál az oszlop körüli keret kialakítására. A keretek az összehasonlítást és a felosztást szimbolizálják a rendezési algoritmusban. Közös tulajdonságnak számít az, oszlopok vándorlása a csere folyamán, melyet szintén közös script segítségével valósítottunk meg. A vezérlőpult irányítása is ebből a JavaScript fájlból ered, ami szintén közös. A gyorsításra szánt checkbox true értéket kap, akkor az áthelyezésre szánt grafika kimarad, és 0,2 másodperc gyorsaságra gyorsul az áthelyezések folyamata.
4.6.3 Buborékrendezés kialakítása a webodlara A buborékrendezés, mint már említettük, ciklusok egybeágyazásával működik. A rendezés alapelve a szomszédos elemek felcserélése, amennyiben a kisebb indexel rendelkező elem nagyobb. A következő iteratív lépésekben ugyanezt tesszük, mindig eggyel kevesebb elemű „résztömbben”. Ezt az iteratív műveletet felírhatjuk rekurzív formában is, melynek a pszeudokódja a következő: function recBS(Array arr[], int n) if(n < 2) return; for(int i = 0; i < arr.length-1; i++) { if(arr > arr[i+1]) swap(arr,i); } return recBS(arr,n-1);
20. ábra: Rekurzív Bubble sort (kódrészlet) Az oldalon lévő animáció, rekurzió elvén működik. Az elemek összehasonlítása során az oszlopok kék keretszínt kapnak. Ha az előbbre álló elem nagyobbnak bizonyul, akkor az oszlop átvándorol a canvas alsó felére. Amint a kisebbik elem a nagyobbik helyére kerül, a canvas alsó feléről visszatér az elem, és máris összehasonlítás történik a következő elemmel. Az első „hullám” összehasonlításának száma tizenöt. A legnagyobb elem a rendezett tömb valós helyére kerülését, az oszlop fekete színre változása szemlélteti. A következő összehasonlítás sorozat, már csak a fekete oszlopelemig fut. Így folytatódik tovább a rendezés, amíg meg nem kapjuk a rendezett tömböt.
34
21. ábra: Weboldalon lévő Bubble sort ábrázolása
4.6.4 Összefésülő rendezés kialakítása a weboldalra Az összefésülő rendezés, mint már említettük a „oszd meg és uralkodj” elvet követi. Bontsuk fel a tömbünket két résztömbre, majd a két résztömböt az uralkodás pontból kifolyólag ismét felosztjuk két résztömbre. Ezt az eljárást az egy elemű résztömb szintjéig folytatjuk. Először az egy elemű résztömböket fésüljük össze, amiből kételemű rendezett résztömböket kapunk. A két résztömböt rekurzívan önmagát meghívva rendezi. Majd a következő tömböket ismét összefésüljük addig, ameddig meg nem kapjuk az eredeti tömb rendezett változatát. Az összefésülő rendezés működését a mellékoldal egy „merge.js” fájlból hivatkozza. A JavaScript fájlban található meg az algoritmus agya, tehát a rendezési algoritmus. Az algoritmus pszeudokódja a következő: function merge_sort(list m) if length(m) <= 1 return m var list left, right var integer middle = length(m) / 2 for each x in m before middle add x to left for each x in m after or equal middle add x to right left = merge_sort(left) right = merge_sort(right) return merge(left, right)
(Merge_sort, 2015) 22. ábra: Rekurzív Merge sort (kódrészlet)
35
Az oldalon lévő animáció a résztömbökre való felosztást narancssárga kerettel jelöli. A futás kezdetén, a már egyelemű résztömbök a canvas alsó felében áthelyezéssel összefésülik egymást egy kételemű rendezett résztömbbe. Mivel tizenhat oszlopon szemléltetjük a rendezés működését, ezért az egyelemű tömbök fésülése nyolcszor történik meg. Addig a canvas alsó felében tartózkodnak a már két elemből álló rendezett tömbök. Az első „hullám” lefolyása végeztével az elemek visszakerülnek a felső szintre. Ismét kezdődik a fésülés, de már két kételemű résztömb fésülődik össze az alsó szintre, ahol már négyelemű rendezett résztömbbé válnak. Amint kialakultak a négyelemű tömbök, visszakerülnek a felső szintre. Így folytatódik tovább, míg az alsó szinten utolsó előtti lépésként megkapjuk a két nyolcelemű résztömbből a tizenhat elemű rendezett tömböt. Utolsó lépés, a visszakerülés a felső szintre rendezett tömbként. A rendezés végével az oszlopok fekete színt kapnak, az algoritmus sikeres végbemenetelének jelzéseként. A vezérlőpult alatt megtalálhatjuk, hogy hány összehasonlítás és áthelyezés történt a rendezés során.
23. ábra: Weboldalon lévő Merge sort ábrázolása
4.6.5 Gyorsrendezés kialakítása a weboldalra A gyorsrendezés, mint már említettük az „oszd meg és uralkodj” elvet hasznosítja. A felbontáshoz kiválasztunk egy vezérelemet (pivot). A vezérelemnél kisebb elemeket a vezérelem elé, a nagyobbakat pedig mögé helyezzük. Majd a vezérelem előtti és utáni résztömb elemeket rekurzívan gyorsrendezzük. Az algoritmus pszeudokódja a következő:
36
function quicksort(array) var list less, equal, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x < pivot then append x to less if x = pivot then append x to equal if x > pivot then append x to greater return concatenate(quicksort(less), equal, quicksort(greater))
(http://hu.wikipedia.org/wiki/Gyorsrendez) 24. ábra: Rekurzív Quick sort (kódrészlet) Az gyorsrendezés működését a mellékoldal egy „quick.js” fájlból hivatkozza. A JavaScript fájlban található meg az algoritmus agya, tehát a rendezési algoritmus. Az oldalon lévő animációban mindig a rendezendő tömb legelső elemét válassza ki az algoritmus vezérelemnek. A kiválasztás után a vezérelem a canvas alsó részére kerül, majd a felső szinten megtörténik a rendezés. A rendezés alatt lévő résztömb narancssárga keretben található. Kék kert jelzi az éppen összehasonlítás alatt lévő elemet. Amint az oszlopok a helyükre kerülnek, a pivot elem visszakerül a felső tömbbe. Az oszlop színe átalakul feketére jelezvén, hogy megtaláltuk a majd rendezett tömbben lévő helyét. A következő vezérelem kiválasztására, szintén a résztömb legkisebb indexével ellátott elemét vesszük, ami még nem volt felhasználva vezérelemként, tehát még nem találtuk meg a majd rendezett tömbben lévő helyét. A rendezést egy résztömbben folytatjuk le, amely a legkisebb indexben lévő elemtől, a már helyére állított elemek indexéig tart. A vezérlőpult alatt megtalálhatjuk, hogy hány összehasonlítás és áthelyezés történt a rendezés során.
25. ábra: Weboldalon lévő Quick sort ábrázolása 37
Befejezés A munkánk célja egy olyan segédeszköz létrehozása, amely segítséget biztosít a rekurzió megértésére. Választásunk egy interaktív multimediális segédeszköz, amely web böngészők alatt futtatható. Interaktivitás segítségével az eszköz működése manuálisan működik, mely grafikus megjelenítése leköti a felhasználó figyelmét. A munkánk tartalma a faktoriális ábrázolása, amely a matematikában egyik leismertebben rekurzív művelet, melyet a programozásban használunk. Két fraktál ábrázolása mellett döntöttünk, amely nem más, mint a Sierpinski-háromszög és a Kochgörbe (Koch-hópehely). A fraktálon véges számú lépés folyamtok segítségével szépen kivehető a rekurzió fogalma a fraktál kialakulása folyamán. Mivel a rekurzió megtalálható pár rendezési algoritmus működési elvében, fontosnak láttuk ezt bemutatni. Bemutatás céljából oszlopdiagramok ábrázolását vettük segítségül. Mivel a segédeszköz web felületen helyezkedik el, web felületre írt szkriptnyelven programoztunk. A programnyelv kiválasztásánál az egyik legelterjedtebb szkirptnyelvet választottuk, ami a JavaScript. A JavaScript programozási nyelv eleinte nehézségeket okozott, de egy kis szintaxis tanulásával, egy-kettő belejöttünk a munkába. Végezetül a segédeszközök feltüntetésére egy weboldalt szerkesztettünk. A weboldal struktúrája az egyszerűség elvén épül fel, mivel a programrészekre fektettünk nagyobb figyelmet. Az elgondolásunk szerint sikerült kialakítani és létrehozni a segédeszközt. A kihívást sikerült leküzdenünk, és számos tapasztalatot szereztünk a segédeszköz elkészítése alatt. Reméljük, hogy az alkalmazás a jövőben hozzásegíti a felhasználót a rekurzió megértésére, és élvezettel használja majd az általunk előállított programrészeket.
38
Resumé Cieľom našej bakalárskej práce je vytvorenie takej vyučovacej pomôcky, ktorá umožní porozumieť pojem rekurzií. Rozhodli sme sa pre túto tému, lebo je veľmi zaujímavá a prospešná v dnešnom dobe, v rôznych oblastiach života. Rekurzia sa objaví v matematike, programovaní, lingvistike a v odlišných oblastiach vedy. Rekurzia je opakovanie, ktorá bude posielať výsledky opakovaním postupom. Preložené do jazyka programu, algoritmus programu volá seba tak, aby dosiahol výsledok, ktorý vopred stanovený počet opakovaní sa predišlo nekonečný ciklus. Ak do rekurzívneho programu neuvedieme podmienku ukončenia, bude sa opakovať donekonečna. Hovoríme o nekonečnej rekurzií. Rekurzívny program podmienkou ukončenia, využíva konečnú rekurziu. Hanojskú vežu môžeme riešiť aj rekurzívne. Logická hra Hanojská veža má jednoduché pravidlá. Hra začína postavením pyramídy z hracích „kameňov” na jednu tyčku. Úlohou je potom presunúť celú pyramídu na inú tyčku, tak aby v jednom ťahu je možné premiestniť iba jeden hrací kameň, a väčší kameň nesmie byť nikdy položený na menší. Na pochopenie rekurzií v matematike najlepším príkladom je, funkcie faktoriál a Fibonacci čísla. V matematike sa pojmom faktoriál kladného celého čísla n označuje súčin všetkých
kladných
celých
postupnosť je postupnosť
čísiel
čísiel,
v
menších, ktorej
alebo
každý
rovných
ďalší
člen je
n.
Fibonacciho
súčtom
dvoch
predchádzajúcich. Keď každý prvok má dvoch nasledujúcich, hovoríme o binárny strom. Prísny binárny strom, musí mať nula, alebo dvoch prvkov. Tento algoritmus môžeme aj rekurzívne zavolať. Niektoré fraktály tiež môžeme rekurzívnym algoritmom vykresliť. Dokonalé fraktály nemôžeme dosiahnúť, lebo tomu by sme potrebovali nekonečný čas a nekonečné nástroje (napr.: rozlíšenie monitorov). Preto môžeme len predstaviť plnú realitu fraktály. Najjednoduchšie konečné fraktály môžeme získať jednoduchou rekurziou. Napríklad: Cantor prach, Koch krivka, Koch snehová vločka, Sierpinski trojuholník, Sierpinski koberec, atď. Naša práca sa zamerá na ľahké riešenie úloh, na podporu vyučovanie algoritmizácie a programovania, ktoré demonštrujú rekurziu a rekurzívne algoritmy. Nakoľko pomôcka je 39
umiestnená vo webovom rozhraní, programovanie sme uskutočnili skriptovým jazykom. JavaScript je najčastejšie používaný skript jazyk v programovaní. Na začiatku nám prinášal ťažkosti, ale učením syntaxe ľahko sme ich prekonali. Naša bakalárska práca je rozdelená do štyroch kapitol a niekoľko podkapitol. Prvá kapitola sa zaoberá teoretickými poznatkami rekurzií a úlohou rekurzívnych algoritmov v matematike a v programovaní. Druhá kapitola vysvetľuje niektorých triediacich algoritmov rekurziou. Merge sort a Quick sort sa pôsobí tiež na princípe rekurzií. Pracuje na princípe „rozdeľuj a panuj”. Rozdeluj a panuj po latinsky „divide et impera” je politický spôsob vyjadrenia princípe rímskeho impéria. Princíp je paradigmou
pre editáciu
algoritmy.
Dynamické
programovanie je nasledovné: 1. Určíme podproblém. aké sú rozmery matice, ktorú budeme vypĺňať? aký je presný význam každého políčka matice? kde v matici nájdeme riešenie pôvodnej úlohy? 2. Vyriešime podproblém za pomoci iných podproblémov. Ako vypočítame jedno políčko matice z iných políčiek matice? 3. Bázové podproblémy. Ktoré políčka nemožno vypočítať pomocou vzťahov z predchádzajúceho kroku? Aké hodnoty by mali obsahovať? 4. Vyberieme poradie vypĺňania. V akom poradí musíme maticu vypĺňať tak, aby sme v každom kroku mali vypočítané všetky políčka, ktoré potrebujeme na výpočet daného políčka (Dynamické programovanie, rozdeľuj a panuj, 2014)? Aj iteratívne triediace algoritmy môžeme prerobiť za rekurzívne algoritmy. V ďalšom kapitole predstavíme používané pomôcky. Zamerali sme sa na jednoduché integrovanie do HTML kódu on-line učebnice. Vybrali sme si JavaScript jazyk, lebo jeho používaním získame najjednoduchšie riešenie. Vytvorili sme webovú stránku, pri ktorej sme používali HTML kódovací jazyk a CSS kaskádový štýl. Na tej webovej stránke sa nachádza s nami vytvorená učebná pomôcka. Časti programu a webovú stránku sme písali na Notepad++ textovom editore. V poslednom kapitole demonštrujeme vytvorenie našej vyučovacej pomôcky. V pochopení pojem rekurzií umožňuje výpočet faktoriálov. Máme možnosť zmeniť vstupných údajov, získať prehľad do programu. Vytvorili sme rekurzívny strom. Rekurzívne sme vyvolali konáre stromu. Z každého konára sa vytvoria ďalšie dve konáre. Veľkosť stromu určíme vstupným údajom. Vybrali sme dve fraktálne zobrazovanie, a to 40
Sierpinski trojuholník a Koch krivka. V trojuholníku sa vytvoria ďalšie trojuholníky. Na ich opustenie sa slúži jeden gombík. Tlačením tohto gombíka, krok za krokom sa pekne vykresľuje Sierpinski trojuholník. Koch krivka tiež pomocou trojuholníka demonštruje rekurziu. Štruktúra jeho programu je podobná, ako u Sierpinského trojuholníka. Konečný počet krokov fraktálov pekne demonštruje pojem rekurzií počas tvorby fraktálu. Na zobrazenie triediacich algoritmov sme si vybrali Bubble sort, Merge sort a Qucik sort. Na ich predstavovanie nám slúžia stĺpcové grafy. Na náhodné vykreslenie používame tlačidlo. Tiež pomocou tlačidlami môžeme algoritmy púšťať, zastaviť a krok za krokom demonštrovať princíp operácií. Pod tlačidlami sa nachádza porovnanie a preradenie stĺpcov. Podľa našich predstáv sa uskutočnilo vytvoriť užitočnú pomôcku na výučbu rekurzií. Podarilo sa prekonať ťažkosti, získali sme rad skúsenosti počas prípravy pomôcok. Dúfame, že náš program aplikácie rekurzií sa stane v budúcnosti mnohým užívateľom užitočným a úspešným zdrojom v rôznych oblastiach života a vedy.
41
Felhasznált irodalom ADONYI R. Adatstruktúrák és algoritmusok. Budapest : Typotex Kiadó, 2011. ISBN 978-963-279-488-4.
CSS.
2015.
CSS
[online].
[2015-04-07].
Elérhető
az
interneten:
Dynamické programovanie, rozdeľuj a panuj. 2014 Dynamické programovanie, rozdeľuj a panuj [online]. [2014-10-21]. Elérhető az interneten: < http://compbio.fmph.uniba.sk/vyuka/vkti1/handouts/p05.pdf> FÁBIÁN Z. Adatszerkezetek és Programozási tételek [online]. Budapest: [2005-01-27]. Elérhető az interneten: < http://www.zipernowsky.hu/~naszlaci/prog/prg_t_asz.pdf> Faktoriális. 2014. Faktoriális [online]. [2014-12-17]. Elérhető az interneten: < http://hu.wikipedia.org/wiki/Faktori%C3%A1lis> Fraktálok 2015. Fraktálok [online]. Elérhető az interneten: < http://teamlabor.inf.elte.hu/logosecsetvonasok/lecke7.html> Gyorsrendezés. 2014. Gyorsrendezés [online]. [2014-12-14]. Elérhető az interneten: < http://hu.wikipedia.org/wiki/Gyorsrendezés>
Hanoi tornyai. 2014. Hanoi tornyai [online]. [2014-03-14]. Elérhető az interneten:
HTML.
2015.
HTML
< http://hu.wikipedia.org/wiki/Hanoi_tornyai>
[online].
[2015-04-07].
Elérhető
az
JavaScript. 2015. JavaScript [online]. [2015-04-23]. Elérhető az interneten: < http://hu.wikipedia.org/wiki/JavaScript>
42
interneten:
Koch-görbe 2014. Koch-görbe [online]. [2014-07-08]. Elérhető az interneten:
< http http://hu.wikipedia.org/wiki/Koch-görbe>
Merge sort. 2015. Merge sort [online]. [2015-04-22]. Elérhető az interneten: < http://en.wikipedia.org/wiki/Merge_sort> MICHAEL M. Tanuljuk meg a JavaScript használatát 24 óra alatt. Budapest : Kiskapu Kft. Kiadó, 2002. ISBN 963-9301-42-6. Notepad. 2014. Notepad [online]. [2014-12-22]. Elérhető az interneten: < http://hu.wikipedia.org/wiki/Notepad++> Rekurzió. 2015. Rekurzió [online]. [2015-05-14]. Elérhető az interneten:
< http://hu.wikipedia.org/wiki/Rekurzió>
Sierpinski-háromszög. 2014. Sierpinski-háromszög [online]. [2014-05-24]. Elérhető az interneten:
< http://hu.wikipedia.org/wiki/Sierpiński-háromszög>
SZABÓ L. Algoritmusok [online]. Sopron: [2015]. Elérhető az interneten: < https://inf.nyme.hu/~lszabo/konyvek/alg/alg.pdf>
43
Melléklet CD médium (a borító hátlapján rögzítve): Szakdolgozat elektronikus formában (.pdf) Az segédeszköz futtatható formában (.html, .js) A weboldal tartalma (.rar) Forráskódok és képállományok
44
