Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.2. Alapvető fogalmak, definíciók

1.2. Alapvető fogalmak, definíciók

1.1. Definíció. Az alsó egészrész függvény minden valós számhoz egy egész számot rendel hozzá, éppen azt, amely a tőle nem nagyobb egészek közül a legnagyobb. Az alsó egészrész függvény jele: , ahol valós szám. Tömören:

Más szavakkal formálisan: , ahol olyan egész szám, hogy .

1.1. Példa.

1.2. Definíció. A felső egészrész függvény minden valós számhoz egy egész számot rendel hozzá, éppen azt, amely a tőle nem kisebb egészek közül a legkisebb. A felső egészrész függvény jele: , ahol valós szám. Tömören:

Más szavakkal formálisan: , ahol olyan egész szám, hogy .

1.2. Példa.

Az alsó és felső egészrész függvények fontosabb tulajdonságai:

1.3. Definíció. A kerekítő függvény minden valós számhoz a hozzá legközelebb eső egész számot rendeli hozzá. Ha a legközelebbi egész szám nem egyértelmű, akkor a nagyobbat választja. A kerekítő függvény jele: , ahol x valós szám.

1.3. Példa.

1.4. Definíció. A törtrész függvény minden valós számhoz azt a számot rendeli hozzá, amely azt mutatja meg, hogy a szám mennyivel nagyobb az alsó egészrészénél. A törtrész függvény jele: , ahol valós szám. Tömören:

Mindig fennáll a egyenlőtlenség.

1.4. Példa.

1.5. Definíció. Legyen és egész szám, . Definíció szerint az egész osztás műveletén az osztás eredményének alsó egész részét értjük. Tömören:

1.5. Példa.

1.6. Definíció. Legyen és egész szám. Definíció szerint az egész maradék képzését , az alábbi formulával definiáljuk:

1.2.1. A számítógép programozásáról

A számítógépes programozás területéről több fogalomra lesz szükségünk annak ellenére, hogy igazán egyetlen programozási nyelv mellett sem kötelezzük el magunkat. A számításaink, adatokon végzett tevékenységeink elvégzéséhez gépi utasítások, parancsok rögzített sorozatára lesz szükségünk. Ezeket összefogva programnak fogjuk nevezni. A programot valamilyen magas szintű programozási nyelven (az ember gondolkodásmódjához közel álló nyelven) írjuk meg, majd azt a gép nyelvére egy fordítóprogram (compiler) segítségével fordítjuk le (remélhetően jól). Ha van interpreter program, akkor azzal is megoldható a feladat elvégzésének a gépre történő átvitele. A programok általában procedúrák (eljárások) sokaságát tartalmazzák. Ezek a zárt programegységek egy-egy kisebb feladat elvégzésére specializáltak. A program többi részével csak a paramétereik révén tartják a kapcsolatot. Fekete doboznak kell őket tekintenünk. A dobozra rá van írva, hogy miből mit csinál. Vannak (lehetnek) bemenő (input) és vannak (lehetnek) kimenő (output) paraméterei. A bemenetet alakítják át a kimenetté. Ha ismerjük a procedúra belső szerkezetét – mert mondjuk mi készítettük –, akkor fehér doboz a neve, ha nem ismerjük – mert nem vagyunk kíváncsiak rá, vagy másoktól kaptuk –, akkor fekete doboz szerkezet a neve. Például készíthetünk olyan procedúrát, amely bekéri (input) az három valós számot, melyeket egy kifejezés (itt valós szám, változó) konstans együtthatóinak tekint, majd eredményül (output) meghatározza a kifejezés valós gyökeinek a számát és ha van(nak) gyök(ök), akkor az(oka)t is megadja. Példa egy lehetséges másik procedúrára: egy file nevének ismeretében a procedúra a file rekordjait valamilyen szempont szerint megfelelő sorrendbe rakja (rendezi). A procedúrák által használt memóriarekeszek – a paramétereket kivéve – a zártságnak köszönhetően lokálisak a procedúrára nézve. Csak addig foglaltak, míg a procedúra dolgozik, aktív. A procedúrát munkára fogni az aktivizáló utasítással lehet. Ezt eljáráshívásnak is nevezik. Az aktivizált procedúra lehet saját maga az aktivizáló is, ekkor rekurzív hívásról beszélünk, a procedúrát pedig rekurzív procedúrának nevezzük. A procedúra munkája végén a vezérlés visszaadódik az aktivizáló utasítást követő utasításra. Ezt a mechanizmust a verem (stack) révén valósítjuk meg. A verem a memória egy erre a célra kiválasztott része. A procedúra aktivizálásakor ide kerülnek beírásra a procedúra paraméterei és a visszatérési cím (az aktivizáló utasítást követő utasítás címe). A procedúrából való visszatéréskor ezen cím és információk alapján tudjuk folytatni a munkát, a programot. A visszatéréskor a veremből az aktivizálási információk törlődnek. Ha a procedúra aktivizál egy másik procedúrát, akkor a verembe a korábbiakat követően az új aktivizálási információk is bekerülnek, azt mondjuk, hogy a verem mélyül, a veremmélység szintszáma eggyel nő. Kezdetben a verem üres, a szintszám zérus, procedúrahíváskor a szintszám nő eggyel, visszatéréskor csökken eggyel. A dolog pikantériájához tartozik, hogy a procedúra a lokális változóit is a verembe szokta helyezni, csak ezt közvetlenül nem érzékeljük, mivel a visszatéréskor ezek onnan törlődnek, a helyük felszabadul. Időnként azonban a hatás sajnálatosan látványos, amikor verem túlcsordulás (stack overflow) miatt hibajelzést kapunk és a program futása, a feladat megoldásának menete megszakad. Adódhat azonban úgy is, hogy mindenféle hibajelzés nélkül "lefagy a gép". A veremnek a valóságban van egy felső mérethatára, amelyet nagyon nem tanácsos túllépni.

1.6. Példa. Nézzünk egy példát a veremhasználatra. Tegyük fel, hogy van még olyan elvetemült informatikus, aki nem tudja, hogy

és ezért egy kis procedúrát ír ennek kiszámítására.

Amennyiben az illető a fent említett hibája mellett teljesen normális, akkor igen nagy eséllyel az alábbi módon oldja meg a problémát. A procedúra neve legyen Summa és legyen az input paramétere az , ami jelentse azt, hogy 1-től kezdve meddig történjen az összeadás. Feltételezzük a procedúra jóhiszemű használatát és így az pozitív egész szám kell legyen. (Nem írjuk meg a procedúrát első lépésben még "bolondbiztosra".) Kirészletezzük egy kissé a procedúra teendőit. Szükség lesz egy gyűjtőrekeszre, ahol az összeget fogjuk képezni és tárolni. Legyen ennek a neve . A procedúra munkájának végén ez lesz a végeredmény, ezt kapjuk vissza, ez lesz a procedúra output paramétere. Szükség lesz továbbá egy számlálóra, legyen a neve , amellyel egytől egyesével elszámolunk -ig és minden egyes értékét az -hez a számlálás közben hozzáadjuk. Az -et a munka kezdetén természetesen ki kell nullázni, hiszen nem tudjuk, hogy mi van benne az induláskor.

Ezek után a kósza meggondolások után egy kissé rendezettebb alakban is írjuk le a teendőket.

A Summa procedúra leírása

Összefoglaló adatok a procedúráról:

A procedúra tevékenysége:

Ezután ha szükségünk van, mondjuk, 1-től 5-ig a számok összegére, akkor csak leírjuk, hogy Summa(Input:5, Output s), vagy rövidebben Summa(5,s). Esetleg függvényes alakot használva az s=Summa(5) is írható. Az aktivizálás hatására a verembe bekerül az 5-ös szám, valamint az s rekesz memóriabeli címe és a visszatérési cím, hogy a procedúra munkája után hol kell folytatni a tevékenységet. Miután most nincs több teendő, ezért ez a cím olyan lesz, amelyből ez a tény kiderül. Jelezhetjük ezt formálisan mondjuk egy a STOP utasítás címe-pal. Valahogy így néz ki a verem formálisan:

Kezdetben üres volt a verem, most egy szint került bele bejegyzésre. Amikor a procedúra munkája véget ér, akkor ez a bejegyzés a veremből törlődik, így az újra üres lesz. (Tulajdonképpen a számláló számára lefoglalt helyet is fel kellett volna tüntetni a bejegyzésben, de ez a számunkra most nem fontos.)

Minden nagyon szép, minden nagyon jó, mindennel meg vagyunk elégedve, és akkor jön egy rekurzióval megfertőzött agyú ember, aki így gondolkodik. Egytől -ig összeadni a számokat az ugyanaz, mint az egytől -ig összeadott számok összegéhez az -et hozzáadni. A feladatot visszavezettük saját magára, csak kisebb méretben. Egytől -ig persze megint úgy adunk össze, hogy az -ig képezett összeghez adjuk az -et. Ez a rekurzió. Arra kell vigyázni, hogy valahol ennek a visszavezetésnek véget kell vetni. Amikor már csak egytől egyig kell az összeget képezni, akkor azt nem vezetjük vissza tovább, hiszen ott tudjuk az eredményt, ami triviálisan éppen egy. Tehát a rekurzív agyú ember egy függvényt alkot, mondjuk RekSumma néven, és az alábbi módon definiálja azt:

Ha most leírjuk, hogy , akkor ezt úgy kell kiszámolni, hogy:

Lássuk ezekután hogyan alakul a verem története. A hatására az üres verembe egy bejegyzés kerül:

A továbbiakban pedig a verem az egyes rekurzív hívások hatására a következőképpen alakul:

Itt a rekurzió megakad, további rekurzív hívás már nem lesz, a végleges veremmélység 5, a rekurzív hívások száma 4 (a legelső aktivizálás még nem rekurzív hívás). A legutolsó hívás már tud számolni, és az eredmény 1 lesz, ami a veremben meg is jelenik:

Ezután az utolsó előtti hívásbeli összeadás (1+2) elvégezhető, a hívás befejeződik és a veremből a legutolsó bejegyzés törlődik. A továbbiakban rendre az alábbi veremállapotok állnak elő:

Innen a visszatérés az értékadáshoz, az -be történő eredmény elhelyezéshez történik, miáltal a verem kiürül. Az elmondottak alapján látszik, hogy a feladat elvégzéséhez szükséges maximális veremmélység 5 és összesen 4 rekurzív hívás történt.

Itt akár fel is lélegezhetnénk, de ekkor egy újabb, még súlyosabb állapotban lévő fazon jelenik meg, aki azt mondja, hogy lehet ezt még szebben is csinálni. Ő a rekurziót arra építi, hogy az összeg képezhető úgy is, hogy az összeadandó számok halmaza első felének összegéhez hozzáadja a halmaz második felének összegét. A felezést további felezéssel számolja, mígcsak az aprózódás révén el nem jut egytagú ősszegekig. Röviden és tömören ő egy másik függvényt definiál, amely kétváltozós, neve RekSum(m,n), és -től -ig adja össze a számokat. Ezzel az általánosabb függvénnyel egytől -ig összeadni RekSum(1,n)-nel lehet. Speciálisan a mi fenti problémánk esetében: RekSum(1,5) számolandó. Az ő definíciója így néz ki:

Nézzük csak hogyan is számol ez a ravasz mődszer a mi speciális s=RekSum(1,5) esetünkben?

Hogyan alakul a verem sorsa ebben az esetben? Az első aktivizáló hívás után a verem:

Ezután következik a RekSum(1,3) hívás. A hatása:

Most jön a RekSum(1,2) hívás a RekSum(1,3)-on belül. A hatás:

Ez megint nem számolható közvetlenül, tehát jön a RekSum(1,1), mire a verem új képe:

Itt már van eredmény, átmenetileg nincs több rekurzív hívás. Az eredmény 1.

A hívás befejezte után a veremből kiürül a legutolsó bejegyzés, visszatérünk az összeadásjelhez, amely után azonban egy újabb rekurzív hívás keletkezik, a RekSum(2,2). Hatására a verem képe:

Az innen történő visszatérés után a verem képe:

Az összeadás elvégzéséhez itt azonban egy újabb rekurzív hívás szükséges, a RekSum(3,3).

Innen

következik, majd pedig egy újabb hívás, a RekSum(4,5). A veremállapot:

Újabb hívás szükséges a RekSum(4,4). A veremállapot:

Ennek befejezte után és a veremből történő törlést követően még kell egy hívásnak lennie, ez pedig a RekSum(5,5). A veremállapot:

Innentől kezdve a verem már csak ürül, további rekurzív hívásokra nincs szükség. A feladat elvégzéséhez kevesebb szintből álló verem is elég volt, mint az előző esetben, most a maximális veremmélység csak 4 volt. A rekurzív hívások száma azonban megnőtt, összesen nyolc rekurzív hívás volt. Ebben a rekurzióban minden hívás, kivéve a legalsóbb szinten levőket két újabbat eredményezett, de ezek a veremnek ugyanazon szintjét használták. A hívások szerkezetét egy úgynevezett hívási fa sémával tudjuk ábrázolni, melyben csak a paraméter értékeket tüntetjük fel. Íme:

Az ábrán jól látszik a verem négy szintje. A legfelső szint kivételével a többi szinten lévő hívások rekurzívak. Az azonos szinten lévő hívások a verem azonos szintjét használják, csak eltérő időben.