1.2. 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. 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.