Adatstruktúrák és algoritmusok

Házy, Attila

Nagy, Ferenc

Új Széchenyi Terv logó.

Miskolci Egyetem

Kelet-Magyarországi Informatika Tananyag Tárház

Kivonat

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Lektor

Gáti Attila

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.


Tartalom

1. Bevezetés
1.1. A tárgyról
1.2. Alapvető fogalmak, definíciók
1.2.1. A számítógép programozásáról
1.3. Feladatok
1.4. Az absztrakt adat és adattípus
1.4.1. A logikai absztrakt adattípus
1.4.2. A karakter absztrakt adattípus
1.4.3. Az egész szám
1.5. Az algoritmus fogalma
1.6. Az algoritmus megadási módja: a pszeudokód és a folyamatábra.
1.7. Az algoritmus jellemző vonásai (tulajdonságai)
1.8. Az algoritmus hatékonysági jellemzői
1.9. A növekedési rend fogalma, az ordo szimbolika
1.10. A Fibonacci számok
1.11. A rekurzív egyenletek és a mester tétel
1.12. Feladatok
2. Számelméleti algoritmusok
2.1. Alapfogalmak
2.2. A legnagyobb közös osztó
2.3. A bináris legnagyobb közös osztó algoritmus
2.4. Az euklideszi és a kibővített euklideszi algoritmus
2.5. A lineáris kongruencia egyenlet
2.6. Az RSA-algoritmus
2.7. Feladatok
3. Elemi dinamikus halmazok
3.1. A tömb adatstruktúra
3.2. A láncolt lista (mutatós és tömbös implementáció)
3.3. A verem és az objektum lefoglalás/felszabadítás
3.4. A sor
3.5. Feladatok
4. Keresés, rendezés egyszerű struktúrában (tömb)
4.1. Keresés
4.1.1. Lineáris keresés
4.1.2. Logaritmikus keresés
4.1.3. Hasító táblák
4.1.4. Minimum és maximum keresése
4.1.5. Kiválasztás lineáris idő alatt
4.2. Rendezés
4.2.1. A beszúró rendezés
4.2.2. Az összefésülő rendezés
4.2.3. A Batcher-féle páros-páratlan összefésülés
4.2.4. Gyorsrendezés (oszd meg és uralkodj típusú algoritmus)
4.2.5. A buborékrendezés
4.2.6. A Shell rendezés (rendezés fogyó növekménnyel)
4.2.7. A minimum kiválasztásos rendezés
4.2.8. Négyzetes rendezés
4.2.9. A Stirling formula és az Alsó korlát összehasonlító rendezésre tétel
4.2.10. Lineáris idejű rendezők: A leszámláló rendezés
4.2.11. A számjegyes rendezés (radix rendezés)
4.2.12. Edényrendezés
4.2.13. Külső tárak rendezése
4.3. Feladatok
5. Fák
5.1. Gráfelméleti fogalmak, jelölések
5.1.1. Gráfok ábrázolási módjai
5.2. Bináris kereső fák
5.3. Bináris kereső fa inorder bejárása
5.4. Bináris kereső fa műveletek
5.5. Piros-fekete fák
5.5.1. Beszúrás
5.6. AVL-fák
5.7. 2-3-fák
5.8. B-fák
5.9. Feladatok
6. Gráfelméleti algoritmusok
6.1. A szélességi keresés
6.2. A mélységi keresés
6.3. Minimális feszítőfa
6.3.1. Kruskal-algoritmus
6.3.2. Prim-algoritmus
6.4. Legrövidebb utak
6.5. Adott csúcsból induló legrövidebb utak
6.5.1. Bellman-Ford algoritmus
6.5.2. Dijkstra algoritmusa
6.6. Legrövidebb utak minden csúcspárra
6.6.1. A Floyd-Warshall-algoritmus
6.7. Gráfok tranzitív lezártja
6.8. Feladatok
7. Dinamikus programozás
7.1. Feladatok
8. NP-teljesség
9. Mellékletek
9.1. Az ASCII karakterkészlet
9.1.1. Vezérlő jelek
9.1.2. Nyomtatható karakterek
Irodalomjegyzék

1. fejezet - Bevezetés

1.1. A tárgyról

Az adatstruktúrák, algoritmusok tárgy fontos helyet foglal el az informatikában. Egy informatikai alkalmazási rendszer kifejlesztése során három fő szintet szokás megkülönböztetni, amit egy helyjegyfoglalási rendszer példájával illusztrálunk. Mondjuk az InterCity vonatjáratra akarunk helyjegyet venni. Sematikusan az alábbi táblázattal lehetne jellemezni a három fő szintet. A középső szint az, amivel a jelen könyvben foglalkozunk.

A szint neve

A szint jellemzése

A szint fogalomrendszere

Felső szint

Alkalmazói szint

modellalkotás útvonalak, szerelvények, dátumok, helyfoglalások

Középső szint

Modellezési szint, algoritmizálás

file-ok, táblázatok, listák, adatrekordok, stringek, fák

Alsó szint

Csupasz gépszint

objektumok, műveletek, gépi reprezentálásuk, bitek, byte-ok

A felső szint az alkalmazó területe. Ő tudja, neki van meg, hogy milyen útvonalakon, mely napokon közlekedtet szerelvényeket, és milyen ezen szerelvények összetétele a helyfoglalás szempontjából. A helyfoglalási rendszer kereteit neki kell kijelölni, ő kell, hogy megmondja, hogy mi a fontos a rendszerében, mi az el nem hagyható tény és mi az ami elhanyagolható. Tudjon-e majd a rendszer mondjuk olyan igényt is kielégíteni, hogy ablaknál akar ülni az utas, de csak a menetiránnyal azonos irányban, ne háttal. Az alkalmazó a valóságnak egy modelljéhez a kereteket alkotja meg. A későbbi üzemelő rendszer paramétereit, képességeit, rugalmasságát és használhatóságát ez a szint döntően meghatározza. A középső szinten a modell gyakorlati megvalósítása következik, amely már az egyes adatkezelési, számítási, tárolási módszereket is magába foglalja. Itt tisztázódik a file-ok rendszere. Rögzítik a használandó táblázatokat, listákat és azok szerkezetét, az adatrekordok felépítését. Az egyes esetekben használt keresési módszerek, az adatmódosítások módszerei is kialakításra kerülnek, miután eldöntötték, hogy mit és hogyan tárolnak. Az alsó szint a gépek, berendezések szintje, amelyek fizikailag meg is tudják valósítani, amit a középső szinten elterveztek. Ezen a szinten nincs modell, nincs szerelvény, dátum, útvonal. Az adatok, a tárolási szerkezetek és a rajtuk végzett műveletsorok bitek és byte-ok özöneként és átalakításaiként jelennek meg. Itt már minden a biteken, a byte-okon múlik. Azon, hogy az egyes adatainkat milyen elvek alapján transzformáltuk bitekké és byte-okká, hogy ezek majd akár a legfelső szint fogalomrendszere alapján is értelmezhetők legyenek. Nem kevésbé fontos az esetleg egymástól térben és időben is nagy távolságra lévő eszközök között a kommunikáció lehetősége, ténye és milyensége.

Tekintsünk most egy elemi problémát és annak megoldásait. Legyen adott egy n fős társaság. Az egyes tagok időnként pénzt kérnek kölcsön egymástól. Mindenki felírja, hogy kitől mennyit kért kölcsön, amikor kölcsönkér és kinek mennyit adott kölcsön, amikor kölcsön ad. A társaság tagjai időről-időre összejönnek az összegyűlt tartozásokat kiegyenlíteni. Mindenki összegyűjti a saját listáján mindenkivel kapcsolatban, hogy kinek mennyivel tartozik. Ezután némi kavarodást okozva mindenki megkeres mindenkit, hogy kifizesse a tartozását, ami nem kis időbe telik, ha a társaság létszáma nem lebecsülendő. Ha összegyűjtenénk egy táblázatba a tartozik-követel összesítéseket, akkor egy ilyen tábla valahogy így nézhetne ki mondjuk 5 személy esetén, akiket rendre Aladárnak, Bélának, Cecilnek, Dávidnak és Edének-nek hívnak. A táblázat sora mutatja, hogy ki tartozik, az oszlopa, hogy kinek tartozik.

Ha ennél a táblánál maradunk, akkor ennek tárolására fő esetén rekesz szükséges, miután mindenki kigyűjtötte a saját nyilvántartásából a többiekkel kapcsolatos meglévő tartozását. A kölcsönök kiegyenlítésére pedig találkozót kell létrehozni, ahol a két fél kölcsönösen kiegyenlíti az egymással szembeni adósságát. Mind a két formulában szerepel egy négyzetes tag, ami arra utal, hogy ha a társaság mérete mondjuk 10-szeresre nő, akkor a vele kapcsolatos szervezési és tárolási munka egyaránt körülbelül 100-szorosra emelkedik. Nem éppen bíztató következtetés. Van azonban jobb megoldás is. Nem kell minden alkalommal mindenkinek feljegyezni, hogy kitől mennyit kért, vagy kinek mennyit adott. Elegendő, ha mindenki csak egyetlen számot tárol és azt módosítja kölcsönzés esetén, ez pedig az éppen aktuális össztartozása a többiek felé. Ennek a tárigénye n rekesz és a kigyűjtés sem szükséges. A fenti táblázatból ez a következő módon kapható meg. A sorokban is és az oszlopokban is képezzük az összegeket, majd mindenkinél kivonjuk a tartozásból (sorösszeg) a követel (oszlopösszeg) értékeket:

Tárolni csak az össztartozás oszlopot kell, ami szám. A tartozások kiegyenlítéséhez szükséges találkozók száma is drasztikusan csökkenthető. A példánál maradva Aladárnak tartoznak 2-vel, ezt Béla megadja Aladárnak. Mostmár Bélának tartoznak 6-tal, azt Cecil adja meg Bélának. Cecilnek tartoznak 7-tel, amit megad neki Dávid, igy Dávidnak lesz 1 hiánya, amit pedig Ede éppen meg tud adni. Ha fő van, akkor a szükséges találkozók száma legfeljebb . Ennél a megoldásnál nem árt, ha Béla és Cecil rendelkeznek némi plusz pénzzel, hogy fizetni tudjanak az elején. Ez elkerülhető azzal, hogy akik tartoznak (Dávid és Ede), azok mindegyike mondjuk Aladárnak adja oda a tartozását és ebből a pénzből Aladár egyenlíti ki a hiányt azoknál, akik pénzre várnak (Aladár, Béla, Cecil). Itt tehát ha a méretek 10-szeresre nőnek, akkor a tárolás és a tartozás kiegyenlítéssel kapcsolatos szervezési munka is csak körülbelül 10-szeresre fog nőni. Érdemes tehát azon elgondolkodni, hogy milyen adatokat milyen formában tárolunk, azokon milyen műveleteket végzünk, hogy a kívánt eredményre jussunk és az a lehető legkisebb erőforrás lekötéssel és energia felhasználásával valósuljon meg.

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.

1.3. Feladatok

  1. Bizonyítsuk be az alsó és felső egészrész függvényeknek a szövegben összefoglalt 1.-5.- tulajdonságait!

  2. Adott egy előjel nélküli egész számokat tároló, duplaszavas elemekből álló tömb a memóriában, amely egy alsó háromszög mátrixot tárol. Alsó háromszög mátrixnak nevezzük azt a négyzetes mátrixot, amelynek a fődiagonálisa feletti elemei garantáltan zérusok. A mátrixot sorfolytonosan tároljuk. A fődiagonális feletti elemeket nem tároljuk, hiszen tudjuk, hogy azok zérusok. Adjon formulát az elem kezdő byte-ja tömbkezdethez képest relatív indexének kiszámítására! A relatív indexeket zérustól kezdve számláljuk. Ha a tömbelem nincs tárolva, az index legyen negatív (mondjuk -1). Feltételezzük, hogy az indexpár az -es tömb valódi elemére mutat, azaz teljesül.

  3. Legyen a következő P(a,b) kétváltozós függvényünk, amelyet nemnegatív egész argumentumokra értelmezünk rekurzívan: zérus, ha , , ha pozitív és páros, egyébként. Procedúrahívással számíttassuk ki a számot! Hogyan alakul a verem felépítése, mélysége? Mekkora a minimális méretű verem, amely a feladat elvégzéséhez szükséges? Hány rekurzív hívás lesz a számolás során?

1.4. Az absztrakt adat és adattípus

Az adat fogalma az értelmező szótár szerint:

„Az adat valakinek vagy valaminek a megismeréséhez, jellemzéséhez hozzásegítő (nyilvántartott) tény vagy részlet.” (Lásd [1]).

Mi adatnak fogunk tekinteni minden olyan információt, amelynek segítségével leírunk egy jelenséget, tanulmányunk tárgyát, vagy annak egy részét. Az adat formai megjelenésére nem leszünk tekintettel, ettől lesz absztrakt. (Absztrakt adat.) Egy rúd hosszát megadhatjuk úgy is, hogy mondjuk százhuszonhét centiméter. Itt nem fontos, hogy a százhuszonhét a 127 formájában van-e megadva, esetleg , vagy alakban. (Egy számítógépes program számára persze ez egyáltalán nem mindegy.) Ez a fejtegetés sem sokkal konkrétabb. Például mi az az információ? Erre a kérdésre a választ nem feszegetjük. Az adat fogalma az alkalmazások, példák és feladatok során lesz tisztább. Tulajdonképpen azt is nehéz megmondani, hogy mi nem lehet adat.

1.7. Definíció. Az absztrakt adat valamely halmaznak az eleme. Ezen halmaz bármely elemét felhasználhatjuk a munkánkban, számításainkban, az alkalmazott valóságmodellben, objektumainak leírásában, megadásában.

1.8. Definíció. Az absztrakt adattípus egy leírás, amely absztrakt adatok halmazát és a rajtuk végezhető műveleteket adja meg (definiálja) nem törődve azok konkrét (gépi) realizálásával.

1.9. Definíció. n-változós (n-áris) műveletnek nevezzük az a leképzést, függvényt, ahol az absztrakt adat halmazát jelöli. Azaz ez a leképzés egy absztrakt adat -eshez szintén egy ugyanolyan absztrakt adatot rendel hozzá.

A műveletek közül kiemelkednek a bináris (binér) műveletek, amelyekben tehát az elnevezés alapján is érthetően a művelet elempárokhoz rendel hozzá egy elemet eredményképpen. Például a valós számok esetén ilyen művelet lehet két szám összeadása. Számunkra fontosak az egyes műveletek tulajdonságai. A tulajdonságok megléte, vagy meg nem léte lehetővé teszi vagy éppen nem teszi lehetővé, hogy a formuláinkat átalakítsuk, egyszerűsítsük. Ilyen tulajdonságok például az asszociativitás, kommutativitás, disztributivitás, idempotencia, stb., melyeket az alkalmas helyeken tárgyalunk.

Példák absztrakt adattípusokra:

  • logikai érték,

  • természetes szám,

  • egész szám,

  • racionális szám,

  • valós szám,

  • komplex szám,

  • sorozat,

  • halmaz,

  • dinamikus halmaz.

    • tömb

    • verem

    • sor

    • lista

    • fa

    • gráf

1.4.1. A logikai absztrakt adattípus

A logikai absztrakt adattípus egy olyan halmazt ad meg, amelynek két eleme van, a hamis és az igaz. Jelölésben L={hamis, igaz}. Röviden az elemeket a h (hamis) és az i (igaz) jellel jelöljük.

A típus műveletei lehetnek unáris (unér) és bináris (binér) aszerint, hogy hány operandusuk van. (Lehetnek többoperandusú műveletek is, de ezek a korábbiakkal kifejezhetők.)

Unáris műveletek

Unáris művelet a Negáció, (tagadás, NEM, NOT). Jele: felülvonás a logikai adat neve fölött. Pl.: és . Művelettáblája:

További három unáris művelet alkotható, amelyek azonban triviálisak. Ezek az identikus művelet, a hamis és az igaz művelet. Ez utóbbi kettő konstans eredményt ad.

Művelettábláik:

Bináris műveletek

Bináris műveletből 16-ot lehet felírni. A műveletek erősorrendje csökkenő erő szerint (prioritás, zárójelezés nélkül írhatók) a következő: NEM, ÉS, VAGY, KIZÁRÓ VAGY, Ekvivalencia, Implikáció.

A NEM, ÉS, VAGY műveletek tulajdonságai:

Ezen három művelettel (NEM, ÉS, VAGY) az összes többi (a többváltozósak is) kifejezhetők.

1.7. Példa.

Szintén kifejezhető az összes művelet csupán a (NEM, VAGY), vagy a (NEM, ÉS), vagy a (NEM, KIZÁRÓ VAGY), vagy a (NEM VAGY) vagy a (NEM ÉS) műveletekkel.

1.8. Példa.

A diszjunktív normálforma

1.10. Definíció. Elemi konjunkció

Változók vagy tagadottjainak a konjunkciója, melyben a változók legfeljebb egyszer fordulnak elő.

1.11. Definíció. Diszjunktív normálforma (DNF)

Elemi konjunkciók diszjunkciója.

Művelettábla alapján DNF előállítása: Ahol az eredmény oszlopban i van, azokat az eseteket diszjunkcióval kötjük össze úgy, hogy a változók konjunkcióiból formulát alkotunk. A formulában i esetén a változó szerepel, h esetén a változó negáltja.

1.9. Példa.

Innen .

A logikai változó realizálása történhet bitekkel: hamis – 0, igaz – 1.

1.12. Definíció. Izomorfizmus

Két algebrai struktúrát izomorfnak nevezünk, ha létezik olyan kölcsönösen egyértelmű megfeleltetés a két struktúra elemei között, amely esetén a műveletek is szinkronizálódnak. Ez azt jelenti, hogy ha az egyik struktúra az , a másik struktúra a , a kölcsönösen egyértelmű megfeleltetés pedig , akkor fennáll, hogy minden és esetén. Az megfeleltetést nevezzük izomorfizmusnak.

1.10. Példa. Legyen a pozitív valós számok halmaza a szorzás művelettel felruházva, és az összes valós szám halmaza az összeadás művelettel. Akkor az megfeleltetés, ahol , izomorfizmust valósit meg, hiszen a logaritmus azonosságai szerint: minden pozitív és esetén.

Legyen most az halmaz az logikai adattípus a negáció, a konjunkció és a diszjunkció műveletével felruházva. Legyen a halmaz a számokból álló halmaz, amelyen értelmezzük az alábbi három múveletet:

  • Ellentett elem képzése unáris művelet : , a kivonás művelete révén.

  • Szorzás bináris művelet: , a számok szorzási műveletének megfelelően.

  • Bitösszegzés bináris művelet: a számokra érvényes szokásos összeadás, kivonás és szorzás művelete révén.

Ekkor a most definiált három művelet a negáció, konjunkció, és diszjunkció műveletének megfeleltetve, valamint a logikai mennyiségeknek a biteket a fenti módon megfeleltetve a logikai adattípus és a bit adattípus között izomorfizmust hoztunk létre. Azt mondjuk, hogy a logikai adatokat bitekkel modellezzük. Amilyen törvényszerűséget találunk az egyikben, az izomorfizmus révén megtaláljuk a törvény párját a másikban.

A logikai típus nagyon fontos, mert az értékeket feszültségszintekhez lehet társítani, a műveleteket pedig úgynevezett kapuáramkörökkel valósíthatjuk meg. A kapuáramkör fizikai (technikai) felépítése lényegtelen a számunkra, az változott az idők folyamán (relék, diódák, tranzisztorok, stb.). Sematikusan úgy jelölhetjük őket, mint egy dobozba zárt átalakító szerkezet, amelynek vannak bemenetei és kimenetei. A bemeneteken bemenő jeleket dolgozzák fel a rendeltetésüknek megfelelően, és az eredmény megjelenik a kimeneteken.

Példa kapuáramkörökre:

Kapuáramkörökből felépíthető az úgynevezett félösszeadó (Half Adder). Feladata egyetlen bitpozíción képezni a két bit összegét és az átvitelt, tehát a művelet mindig kétjegyű eredményt képez, melynek alacsonyabb helyiértékű bitje az összegbit, magasabb helyiértékű bitje az átvitelbit (Carry bit).

A félösszeadó több-bites számok összeadásakor csak fél munkát végez, helyesen csak a legalacsonyabb bitpozíción működik. A további pozíciókon három bitet kell összeadni, a két összeadandó bitet és az előző pozícióról jövő átvitelbitet. A teljes összeadó (Full Adder) ezt valósítja meg.

Felírva a két eredményoszlopra a diszjunktív normálformákat, tulajdonképpen megkapjuk a műveletek egy lehetséges kapuzását.

Ezt a látszólag bonyolult formulát le lehet egyszerűsíteni és a teljes összeadó felépíthető két félösszeadó és egy VAGY kapuáramkörből. Előtte azonban egy segéd formulát vezetünk le.

1.13. Lemma.

Bizonyítás. Láttuk, hogy

Akkor

Ezután a teljes összeadó levezetése az alábbi lehet:

Jelölje és az első, valamint a második félösszeadő által adott eredmény összegbitet és az átvitelbitet. Akkor

A teljes összeadó sematikus ábrája:

1.4.2. A karakter absztrakt adattípus

A karakter absztrakt adattípus a szöveges információ megjelenítést teszi lehetővé. A szövegeinket elemi egységekből építjük fel.

1.14. Definíció. Karakter

A karakter a tágabb értelemben szövegesen lejegyzett adat legkisebb, elemi egysége, egy tovább már nem bontható szimbólum.

A karakterek halmazát -szel fogjuk jelölni.

A karaktereket osztályozhatjuk jellegük szerint. Eszerint a karakterek lehetnek: számjegyek, betűk, írásjelek (pont, vessző, felkiáltó jel, stb.), speciális jel (félgrafikus jel, matematikai jelek, hieroglifák, szimbólumok, stb.), vezérlőjel (csengő, soremelés, lapdobás, kocsi vissza, file vége, escape, stb.).

A karakter absztrakt adattípusra jellemző, hogy az halmaz elemei között rendezettséget vezetünk be, amely konvención, megállapodáson alapul. Előre rögzítjük a sorrendjüket. (Ezt a sorrendet nevezhetjük ábécé sorrendnek.) A sorrend szerint az egyes karaktereket sorszámmal láthatjuk el. Két műveletet be is vezethetünk ezáltal. Az egyik lehet a Hátrább_álló, a másik lehet az Előbb_álló. A Hátrább_álló a két karakter közül azt adja eredményül, amelyik az -ben hátrább áll, azaz amelyiknek a kettő közül nagyobb a sorszáma, míg az Előbb_álló azt adja, amelyiknek kisebb a sorszáma. A sorszámot a karakter kódjának nevezzük.

1.11. Példa. Előbb_álló('K','C')='C', és Hátrább_álló('K','C')='K'.

Ha bevezetünk bináris műveleti jeleket a két műveletre, például legyen az Előbb_álló jele , a Hátrább_álló jele , akkor az előzőleg felírt példa lehet

Civilizációnkban rendkívül sok karakterrel találkozhatunk. Az informatikában kezdetben nem sokat használtak fel ezek közül. Szorított a tárolóhely hiánya. Jelentős lépés volt, amikor az akkor legfontosabbnak tekintett jelkészletet egységesítették, szabványosították. Ez volt az ASCII kódtáblázat (American Standard Code for Information Interchange, az információcsere amerikai szabványos kódja), amely hétbites kód volt. Jellemzője, hogy 0-tól 127-ig terjed az egyes karakterek kódja és az első 32 jel (0-31) vezérlőjel. Ilyenek például a csengő (7), a soremelés (10), a lapdobás (12), a kocsi vissza (13), a file vége (26), az escape (27). Vezérlőjel még (törlőjel) a 127-es kódú karakter. A többi jel látható. Ilyenek a helyköz (32), a számjegyek növekvő sorrendben (48-57), az angol ábécé nagybetűi (65-90), az angol ábécé kisbetűi (97-122). A kisbetű kódja 32-vel nagyobb, mint a neki megfelelő nagybetűé. A teljes ASCII kódtáblázat a mellékletben látható. Az ASCII kódok tárolása a byte-os memória és társzervezés következtében az egy byte egy karakter elvet követte. Mivel egy byte-on 256 féle bitmintázat helyezhető el, ezért kihasználatlan maradt a 127-es kód feletti 128-255 számtartomány 128 eleme. Ugyanakkor az informatika nemzetközivé válása miatt szükségessé vált a nemzeti ábécék jeleinek az alkalmazása is, amelyet az ASCII tábla bővítésével igyekeztek megoldani. Az ASCII tábla bővítése sajnos rossz irányba történt, A 128 elemű eredeti készletet jóval több, mint további 128 jellel kellett volna bővíteni. Megtartották az egy byte-os szerkezetet. Ezért a 127-es kód feletti kódokat több célra kellett használni, hogy mindenkinek az igényét kielégítsék. Bevezették a kódlap fogalmát. Definiáltak például Latin-1 kódlapot, amelybe sok ékezetes betű is belefért, persze felrúgva ezzel a betűk ábécé sorrendjét. A magyar ő és ű betű azonban ebbe sem fért bele. Azt a Latin-2 kódlapra tették. Az eredmény az lett, hogy ha a szöveget megjelenítő program nem tudta, hogy a szövegfile eredetileg milyen kódlap alapján készült (honnan tudta volna, amikor ez az információ a file-okban nem szerepel), akkor amennyiben ő más kódlap szerinti megjelenítésre volt beállítva, a szöveg akár olvashatatlanná is vált. Ugyanannak a kódnak többféle karakter is megfelelt a kódlapoknak megfelelően. Másik probléma volt az, hogy vannak nyelvek, amelyeknek több ezer írásjel szimbóluma van, amelyek eleve nem férnek el egy ilyen 256-os táblázatban. Ezeket kétbyte-os ábécében helyezték el. Azonban ezek a törekvések bár bevezetésre kerültek, a problémákat nem szüntették meg már csak azért sem, mert egy szöveg tartalmazhat különböző nyelven megírt részleteket is.

A megoldást a Unicode Standard szolgálja. Az 1.0 verzió 1991-ben jelent meg, jelenleg (2011) a 6.0 verziónál tartunk. A Unicode rendszerben a karakter absztrakt fogalom és a neve egyedileg azonosítja, amely nem változtatható. A karaktereket egy-egy rá egyedileg jellemző egész számmal, a karakter kódpontjával (code point) kapcsoljuk össze. Ezek a kódpontok egy kódtérben (codespace) helyezkednek el, amely nevezetesen a nullával kezdődő és a hexadecimális 10FFFF-fel végződő egész számok tartománya. A kódpont mindig ugyanazt a karaktert jelöli és fordítva, egy karakternek mindig ugyanaz a kódpontja. A kódtér mérete 1 114 112 kódpont.Majdnem mindet karakterkódként használják. Vannak speciális célra fenntartott kódpont tartományok. A számunkra (Európa) szokványos karakterek többsége az első 65 536 kódponton elfér. Ezt a tartományt BMP-nek (Basic Multilingual Plane) nevezik. A maradék több mint 1 millió hely elegendő az összes ismert karakter, írásjel kódolására, beleértve a minoritások által használt vagy a történelemből ismert írásképeket.

Lényeges tulajdonsága a Unicode-nak, hogy a karakter absztrakt fogalmát leválasztja annak a képernyőn vagy a nyomtatón megjelenő képétől. A képpel a Unicode nem foglalkozik. (Pl. a karakter mérete, színe, dőlése, kövérsége, kiemelt mivolta, alakja stb.) A karakter Unicode kódját az U+xxxx, U+xxxxx vagy a U+xxxxxx alakban adjuk meg, ahol x hexadecimális számjegy és a számérték a kódpont.

Az absztakt karakter reprezentálására a számítógépben három lehetőségünk van. Ezek a UTF-32, a UTF-16 és a UTF-8 kódolási formák. (UTF - Unicode Transformation Format.) Meg kell különböztetni a kódolt karakter és a szövegelem fogalmát. A szövegelem egy vagy több kódolt karaktert jelent. Például a hullámos vonallal felül díszített u betű előáll az u betű és a felül hullámos vonal karakterek kódjából. Tehát a karakterkép esetleg több elemből is összetevődhet. Tekintsük most az egyes kódolási formákat. Bármely formát is választjuk, ezek egymásba veszteség nélkül áttranszformálhatók.

A UTF-32 esetén a kódpont szerinti egész szám és a kettes számrendszerbeli 32 bites megfelelője között egy-egy értelmű a kapcsolat.A kód mérete fix, négy byte. Emiatt a tárigény nagy.

A UTF-16 esetén a U+0000, ..., U+FFFF kódpontok 16 biten jelennek meg, míg a U+10000, ..., U+10FFFF kódpontok egy 16 bites páron ábrázolódnak a következő módon.

xxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxx

000uuuuuxxxxxxxxxxxxxxxx

110110wwwwxxxxxx 110111xxxxxxxxxx

Itt a wwww szám az uuuuu-1-et jelenti binárisan. Látható, hogy ez a kódolás BMP-re optimalizált. A Unicode elődje.

A UTF-8 byte-orientált kódolás, ASCII alapú, az ASCII-re transzparens, azaz ugyanúgy ábrázolja. A kód mérete változó, 1-4 byte lehet. A vezető byte jelzi a karaktert leíró byte-szakaszt. Kedvező a HTML és Internetes protokollok számára. A kódpont ábrázolásának módja a következő.

00000000 0xxxxxxx

0xxxxxxx

00000yyy yyxxxxxx

110yyyyy 10xxxxxx

zzzzyyyy yyxxxxxx

1110zzzz 10yyyyyy 10xxxxxx

000uuuuu zzzzyyyy yyxxxxxx

11110uuu 10uuzzzz 10yyyyyy 10xxxxxx

A további információkhoz juthatunk a Unicode Standard leírására a [3]-ból.

1.4.3. Az egész szám

Az egész szám esetén nagyon megszoktuk a 10-es alapú számrendszer használatát. Valójában nem törődünk a szám leírásával. Egy szám esetében a számítógép nem a 10-es, hanem a 2-es alapot használja a szám reprezentálására. Attól még az a szám ugyanaz a szám. Nincs értelme absztrakt egész szám esetén beszélni például egy szám számjegyeiről. Más a helyzet abban a pillanatban, amikor az absztrakt adattípus szerinti adatot konkrétan meg akarjuk jeleníteni. Akkor már nem lényegtelen az ábrázolási forma. Próbáljuk meg például összeszorozni papíron kézzel és ceruzával a hetvenkilencet és a negyvenhetet úgy, hogy a két számot 79 és 47 alakban adjuk meg, valamint úgy is, hogy és alakban. Az első esetre van egy módszer, egy könnyen megjegyezhető séma, amely szerint a kisiskolás is el tudja végezni a számítást, a másik esetben pedig nehéz ilyet adni, holott a szorzat létezik az ábrázolástól függetlenül. Adható persze az ábrázolástól független módszer is két nemnegatív egész szám összeszorzására. Ennek a módszernek a neve ma gyakran úgy olvasható, hogy „orosz paraszt” módszer. Az elnevezés nem teljesen jogos, mert a módszert már az ókori egyiptomiak is ismerték és használták [4]. A módszer lényege, hogy a szorzatot fokozatosan gyűjtjük össze és a zérusból indulunk ki. A szorzót vizsgáljuk. A vizsgálat abból tart, hogy megnézzük, hogy páratlan-e. Ha igen, akkor a szorzandót hozzáadjuk a szorzathoz, ha nem, akkor nem adjuk hozzá. Ezután a szorzót lecseréljük a felének az egész részére, a szorzandót pedig lecseréljük a duplájára. A vizsgálat mindaddig ismétlődik, míg a szorzó zérussá nem válik. (Lássuk be, hogy a módszer mindig a helyes szorzathoz vezet két nemnegatív egész szám esetén!)

1.12. Példa. Szorozzuk össze a 79-et és a 47-et az orosz „paraszt” módszerrel!

Az absztrakt adattípus egy fekete doboz, amelybe beletesszük az adatot tárolásra és kivesszük, ha szükségünk van rá. Nem érdekes, hogy a doboz hogyan végzi a tárolást. Ami viszont fontos az az, hogy az absztrakt adattípushoz elválaszthatatlanul hozzátartoznak azok a műveletek, amelyeket az adatokkal végezni lehet.

1.15. Definíció. Adatstruktúrának nevezzük az absztrakt adattípus konkrét megjelenési formáját.

A műveletek az adatstruktúrához ugyanúgy hozzátartoznak, mint az absztrakt adattípushoz. Példák adatstruktúrára:

  • lista, verem,

  • sor, elsőbbségi (prioritásos) sor,

  • bináris kupac, binomiális kupac,

  • fa, gráf, hálózat.

Adatstruktúra a számábrázolás módja is. Az elnevezésekben azonban az absztrakt adattípus és az adatstruktúra nevek gyakran keverednek, hiszen tartalmilag hasonló dolgokról van szó.

1.5. Az algoritmus fogalma

Az adatainkon általában különféle műveleteket, átalakításokat szoktunk végezni azzal a céllal, hogy ezáltal közvetlenül nem kiolvasható összefüggéseket, eredményeket kapjunk. A tevékenységeket logikai sorrendbe rakva az algoritmus matematikai fogalmához kerülünk közelebb. Az algoritmus mély matematikai fogalom. Mi nem adunk precíz definíciót rá, mivel ebben a könyvben erre nincs szükségünk. Azok számára, akiket a téma mélyebben érdekel ajánlhatjuk a [4], [5], [6], [7] könyveket.

Most megadunk egy heurisztikus (nem tudományos) definíciót az algoritmus fogalmára.

1.16. Definíció. Az algoritmus egy meghatározott számítási eljárás, a számítási probléma megoldási eszköze.

Az algoritmus pontos előírás, amely megad egy tágan értelmezett számítási folyamatot. Az algoritmus valamely előre meghatározott adathalmaz valamely tetszőleges kiinduló eleméből kezdve az ezen elem által meghatározott eredmény elérésére törekszik. Lehet, hogy a lépések sorozata azzal szakad meg, hogy nincs eredmény. Az algoritmus is tekinthető egy fekete doboznak, melynek a bemenetére adjuk a probléma, a feladat kiinduló adatait, a kimenetén pedig megjelennek a végeredmények, ha vannak, vagy az jelenik meg, hogy nincsenek. Az algoritmus fekete dobozának belső szerkezete azonban érdekelni fog minket ebben a könyvben. Az algoritmusnak véges idő alatt (véges sok lépés után) véget kell érnie.

1.13. Példa. Négyzetgyök kiszámítása egy számból papíron kézzel.

Határozzuk meg az számot megadott számú értékes jegy pontosságig, ahol valós szám. Egy kézi algoritmus az alábbi formulára építkezve adható:

Az algoritmus leírása (ez az algoritmus épít a szám reprezentációjára, azaz arra, hogy helyiértékes számrendszert használunk):

[1.] Az szám számjegyeit a tizedesvesszőtől balra és jobbra kettes csoportokra osztjuk.

[2.] A balszélső (első) csoportnak vesszük az egyjegyű négyzetgyökét és az eredménybe írjuk.

[3.] A kapott egyjegyű szám négyzetét kivonjuk az első csoportból.

[4.] A maradék mellé leírjuk a következő kétjegyű csoportot, ha van. (A tizedesvesszőt követően mindig lehet zérust, vagy zéruspárokat írni, ha már nem lennének tizedesjegyek.)

[5.] Az eddig kapott eredmény kétszereséhez hozzáillesztünk egy próbaszámjegyet, majd az így kapott számot a próbaszámjeggyel megszorozva a szorzatot kivonjuk a 4. pontnál kapott legutóbbi maradék és következő csoport által meghatározott számból. A próbaszámjegy a lehető legnagyobb olyan számjegy legyen, amely még nemnegatív különbséget ad.

[6.] A próbaszámjegyet az eredményhez hozzáírjuk új számjegyként.

[7.] Ha a pontosság megfelelő, akkor leállunk, egyébként a 4-es pontnál folytatjuk.

1.14. Példa. Konkrét számpélda a kézi négyzetgyökvonás algoritmusára, működésének bemutatása.

Számítsuk ki az értékét! A szám csoportokra osztása: 14 42 48 04. Az algoritmus további lépései az alábbi táblázatban találhatók. A próbajegyeket és a hozzáírt csoportot aláhúztuk.

Kiolvasható, hogy . Az eredmény pontos, mivel a végső maradék zérus.

1.15. Példa. Számítsuk ki az értékét négy tizedes jegyre!

A szám csoportokra osztása: 2, 00 00 00 00.

. Ezen közelítés négyzete a 2-től csak 0,00003896-tal kevesebb.

A tárgyalt algoritmus kellemes, az eredmény jegyei egymás után egyenként jönnek elő. Neuralgikus pont viszont a próbajegyek helyes megválaszásának a kérdése, Igaz, ez a probléma megoldódik, ha a számításokat kettes számrendszerben végezzük. Mégsem ragaszkodunk a négyzetgyökvonás ezen módjához, mivel itt lényeges a szám reprezentációja. Adunk egy másik algoritmust, amely lényegesen jobb mutatókkal rendelkezik. Ez az algoritmus az úgynevezett Newton módszernek egy speciális esete. Ez az algoritmus nem számjegyenként csalja elő a végeredményt, hanem egy számsorozatot képez, amely meglehetősen gyorsan konvergál a végeredményhez. Nem árt persze kellően jó kezdő közelítésből kiindulni. Érdemes megjegyezni, hogy ha a módszer által képzett sorozatban valamely elem már tartalmaz értékes jegyeket a megoldást leíró szám elejéből, akkor minden további elemben az értékes jegyek száma legalább duplájára nő a megelőzőhöz képest. Maga az algoritmus egyszerű és jól programozható, valamint nem igényli a szám reprezentációját. Íme (a leírásban az alkalmazó előre rögzít egy számot, amit nak nevezünk):

[1.] Választunk egy tetszőleges pozitív valós számot és legyen . (Az mindig megfelelő, csak esetleg a kapott sorozat kezdetben lassan kezd közelíteni a megoldáshoz.)

[2.] Képezzük az

számot és értékét eggyel növeljük.

[3.] Ha , akkor megállunk és , egyébként pedig folytatjuk a 2-es pontnál.

1.16. Példa. Határozzuk meg az értékét négy tizedesjegyre, azaz legyen !

Heurisztikus meggondolásból válasszuk kezdőértéknek az számot!

1.17. Példa. Határozzuk meg az értékét négy tizedesjegyre, azaz legyen !

Mivel , ezért válasszuk a kezdő közelítést -nek!

1.6. Az algoritmus megadási módja: a pszeudokód és a folyamatábra.

Az algoritmust szövegesen adtuk meg a fenti esetekben. Ez egy lehetőség általában az algoritmus lejegyzésére. Elterjedt azonban a pszeudokódos megadás is, mely közelebb viszi a leírást a számítgógépes megvalósításhoz anélkül, hogy elkötelezné magát egy konkrét programozási nyelv mellett. (A programozási nyelvek divatja változik - ma már több programozási nyelv van, mint a beszélt emberi nyelvek száma, - de a már lejegyzett algoritmus lényege nem változik.) Alább ismertetünk néhány pszeudokód konvenciót, megállapodást, amely segít az ilyen módon megadott algoritmusok megértésében.

[1.] Blokkszerkezeteket fogunk használni, amint az sok programozási nyelvben elterjedt. A blokk zárójelezése helyett a bekezdés eltolásának módszerét fogjuk használni.

[2.] Az alábbi strukturális (strukturált vagy kvázistrukturált) utasításokat fogjuk használni:

[3.] Az értékadás jele a jel lesz. Bátran alkalmazzuk tömbök, struktúrák értékadására és többszörös értékadásra is.

[4.] A magyarázatokat, megjegyzéseket // kezdőjellel fogjuk jelezni. Ez lehet egy teljes megjegyzés sor, vagy lehet egy adott sorhoz hozzáfűzött megjegyzés.

[5.] Az eljárásokban használt változók lokálisak lesznek.

[6.] Tömbelemet indexeléssel adunk meg. Lehet egy index (vektor), két index (mátrix), vagy több. Az indexek résztartományát -tal jelöljük. Például jelenti a 3,4,5,6 indexeket.

[7.] Az összetett adatok (objektumok) mezőkkel rendelkeznek, amelyekben az objektum attributumait, tulajdonságait tároljuk. A mezőre a nevével hivatkozunk. A mezőnév mögött szögletes zárójelben feltüntetjük az objektum nevét.

[8.] A tömbök vagy objektumok mutatók révén lesznek megadva. A NIL mutató sehová sem, semilyen objektumra sem mutat. Ha mutat egy objektumra, egy másikra, akkor az értékadás után az is és az is ugyanarra az objektumra mutat, nevezetesen az által jelzettre. Az által korábban mutatott objektum ezáltal elvész, mivel a mutatója eltünt.

[9.] Az eljárások az input paramétereiket érték szerint kapják meg, azaz a paraméterről egy másolat készül (ami a verembe helyeződik el). Az eljárásnak a paramétereken végzett változtatásai a hívó rutinban nem láthatók emiatt, hiszen a veremből ezek a visszatéréskor törlődnek. Objektum paraméter esetén azonban az objektum mutatójának másolata kerül a verembe, nem maga az objektum, ezért az objektum mezőin végzett változtatások a hívó rutinban is láthatóak lesznek a visszatérés után. Nem láthatók viszont magának a mutatónak a megváltozásai. Az input és output paramétereket a paraméterlistán feltüntetjük és megjegyzés sorokban írjuk le azokat. Az output paramétereket a visszatérési RETURN utasításban is megadjuk.

[10.] A pszeudokód nem zárja ki, hogy az algoritmus egyes részeit szöveges módon tüntessük fel.

A fenti iteratív négyzetgyökvonási algoritmus pédául így nézhetne ki. A jobboldalon egy praktikusabb változat látható.

A folyamatábra az algoritmust folyamatában a sík kétdimenziós tulajdonságát kihasználva grafikus szimbólumok felhasználásával teszi szemléletessé. Az alábbi, vízszintes vagy függőleges folyamatvonalak révén egymáshoz kapcsolható szimbólumokat használjuk: A folyamatvonalak összefutását kis körökkel jelöljük.

A folyamatvonalakon a haladás iránya balról-jobbra, vagy fentről-lefelé, hacsak a vonalra kitett nyíl másként nem mutat. Megjegyzést a szimbólumokhoz szaggatott vonallal a szimbólumhoz kapcsolt, megfelelően méretezett kezdő szögletes zárójel jellel lehet hozzákapcsolni. A szöveg a szögletes zárójel mögé kerül.

A négyzetgyökvonás fenti praktikusabb változata folyamatábrával:

A strukturális utasításoknak megfelelő folyamatábra részletek:

Az algoritmusok közül kitűnnek a rekurzív algoritmusok és az iteratív algoritmusok. Mindkét fajta algoritmus hatékonyan realizálható számítógépen. Az iteratív algoritmusok hasonló, vagy azonos műveletek sorozatát ismétlik (a latin iteratio szó ismétlést jelent). A rekurzív algoritmusokban azt ismerjük fel, hogy a probléma mérete redukálható kisebb méretre, majd még kisebb méretre, stb. és a kisebb méretű feladat megoldása után visszatérhetünk (a latin recursio szó visszatérést jelent) a nagyobb méretűnek a megoldásához, amely ezáltal lényegesen egyszerűbbé válik. Iteratív algoritmus volt a Summa algoritmus. és a kézi négyzetgyökvonás algoritmusa. Ugyancsak iteratív algoritmusok az 1.2.1 és 1.2.2 algoritmusok. Rekurzív algoritmus volt a RekSumma és a RekSum algoritmus. A rekurzív algoritmusok mindig átírhatók iteratív formára is. Az említett algoritmusoknak a pszeudokódját az alábbi módon készíthetjük el procedúra formában:

Egy probléma megoldására nem mindig könnyű algoritmust találni még akkor sem, ha ismert, hogy van megoldása a problémának és hogy csak egy megoldása van. (Ha nincs megoldása a problémának, akkor persze nincs értelme algoritmust keresni.) Megemlíthetők azonban általános elvek, amelyek figyelembe vehetők egy-egy algoritmus kidolgozásakor. Ez persze nem jelenti azt, hogy ezen elvek figyelembe vételével biztosan mindig célba is érünk. Az intuíciónak továbbra is korlátlanok a lehetőségei és a szerepe nem csökken. Ilyen általános elvet, algoritmus tervezési stratégiát hármat említünk a könyvben:

1.7. Az algoritmus jellemző vonásai (tulajdonságai)

Minden algoritmusnak vannak jellemző tulajdonságai. Ezek között vannak olyanok, amelyek általánosnak tekinthetők. Ezeket az alábbiakban soroljuk fel:

1.18. Példa. A gyökvonás 1.2.2. algoritmusa esetében a 7 pont így nézhetne ki:

[1.] Kiinduló adatok lehetséges halmaza tetszőleges pozitív szám.

[2.] A lehetséges eredmények halmaza tetszőleges pozitív szám.

[3.] A közbülső eredmények tetszőleges pozitív szám.

[4.] A kezdési szabály a számláló beállítás és az kezdőértékből történő indulás.

[5.] Átalakítási szabály a Newton iterációs formula: és a számláló növelése.

[6.] A befejezési szabály a pontosság ellenőrzése és annak teljesülése esetén a befejezés.

[7.] Az eredmény kiolvasható a legutoljára kapott értékből.

1.8. Az algoritmus hatékonysági jellemzői

Amikor egy algoritmust keresünk egy feladat megoldására a következő két kérdés fel kell, hogy vetődjön:

[1.] Megoldható-e a probléma és ha igen, akkor egy vagy több megoldása van-e? (Ezt hívják a megoldás problémájának.)

[2.] Ha már találtunk a problémára megoldási algoritmust, akkor van-e a meglévőnél hatékonyabb másik megoldási algoritmus? (A megoldási módszer, algoritmus problémája.)

A második kérdés csak akkor jogos, ha a megoldás létezik. Meghatározásra szorul az, hogy mit értünk egy megoldó algoritmus hatékonyságán, mikor mondhatjuk, hogy egy probléma egyik megoldó algoritmusa hatékonyabb, mint a másik. Az is tisztázandó, hogy milyen szempont szerint tekintjük a hatékonyságot. A hatékonyságot mérőszámmal lehet jellemezni. Kiválasztva a mérlegelési szempontot, amely alapján az algoritmust vizsgáljuk, az algoritmus minden bemenő adatára egy mérőszámot konstruálunk. Az az algoritmus a hatékonyabb egy rögzített input esetén, amelyikre ez a mérőszám a jobb eredményt adja. Mérlegelési szempontnak általában az algoritmus időigényét (lépésszámát, műveletszámát) szokás tekinteni, hiszen az időnek vagyunk általában szűkében. Nem elhanyagolható azonban egy másik szempont sem, az algoritmus tárigénye a számítógépes realizáció szempontjából. Egy algoritmus lehet egy bizonyos inputra jobb, mint egy másik algoritmus, egy másik input esetében pedig lehet rosszabb. Ezért a hatékonysági mérőszám fogalmát egy kicsit árnyaltabban kell megközelíteni. Először is be kell vezetni az inputok összehasonlítására alkalmas valamiféle mérőszámot. Teljesen nyílvánvaló, hogy például egy százjegyű számból általában tovább tart négyzetgyököt vonni, mint egy tízjegyűből. Be kell tehát vezetni a probléma méretének a fogalmát.

1.17. Definíció. Az algoritmus inputjának a mérete (problémaméret)

Legyen adott egy probléma, amely megoldható egy algoritmussal. Legyen az algoritmus lehetséges inputjainak a halmaza. Legyen egy input. Az input méretének nevezzük az konkrét megadásakor használt bitek számát. Ez egy nemnegatív egész szám, mérőszám. Jelölésben az input mérete .

Meglepő, de ez a bizonytalannak, nem egészen egyértelműnek tűnő méretdefiníció mégis hatékony fogalomnak bizonyul.

1.19. Példa. A négyzetgyökvonó algoritmusunk inputja legyen az egyszerűség kedvéért az pozitív egész szám, amelyből gyököt akarunk vonni. Ekkor az algoritmus inputjának mérete , a számot leíró bitek száma.

Vezessünk be most néhány jelölést. Legyen egy algoritmus, az algoritmus összes lehetséges input adatainak a halmaza és egy lehetséges input. Az input esetén -szel fogjuk jelölni az algoritmus probléma megoldási (-time, idő) és -szel a (-storage, tár).

1.18. Definíció. Az algoritmus időbonyolultsága

A

számot az A algoritmus nak nevezzük.

Az időbonyolultság megadja, hogy az -nél nem nagyobb méretű inputok esetén mennyi a legnagyobb időigény.

1.19. Definíció. Az algoritmus tárkapacitás bonyolultsága

Az

számot az A algoritmus nak nevezzük.

A tárkapacitás bonyolultság megadja, hogy az -nél nem nagyobb méretű inputok esetén mennyi a legnagyobb tárigény.

Mindkét mérőszám hatékonysági mérőszám. A gyakorlatban ma már inkább az elsőt használják algoritmusok hatékonyságának az összehasonlításában, ami nem csökkenti a második szerepének a fontosságát. Elég nagy méretű tárak állnak ma már rendelkezésre, de nincs olyan tár, amit pillanatok alatt ki ne lehetne nőni egy "ügyes" algoritmussal. Láthatóan a bonyolultságok a probléma méretének monoton növekedő függvényei és az adott méretet meg nem haladó méretű esetek közül a legrosszabb esettel jellemzik az algoritmust. Ha ugyanazon probléma megoldására két vagy több algoritmus is létezik, akkor a közülük történő választás megalapozásához ad segítséget az algoritmusok bonyolultsági függvényeinek a vizsgálata, összehasonlítása. Az egyes bonyolultságok összehasonlítása az egyes függvények növekedési ütemének, rendjének az összehasonlítását jelenti, mely fogalmat alább definiáljuk. A fenti mérőszámoknak létezik olyan kevésbé pesszimista változata is amikor a legrosszabb eset helyett az inputok szerinti átlagolt értéket vesszük, vagy ami realisztikusabb, hogy ismerve az egyes inputok gyakoriságát (valószínűségét) súlyozott átlagot (várható értéket) számolunk. Ez utóbbi nem tartozik az anyagunkhoz, mivel valószínűség-számítási ismereteket (sajnos) nem tételezünk föl.

1.9. A növekedési rend fogalma, az ordo szimbolika

Egy algoritmus időbonyolultsága (vagy akár a tárkapacitás bonyolultsága) az input méretének monoton növekvő függvénye. Az ilyen függvényeket növekedést leíró függvényeknek (röviden növekedési függvény) nevezzük.

1.20. Példa. A kézi négyzetgyökvonás algoritmusa esetén ha az input az (egész szám), akkor az input mérete . A négyzetgyököt csak egész jegy pontosságig határozzuk meg. Ebben az esetben számú számjegyet kell meghatározni. Minden új számjegy esetén eggyel nő a visszaszorzandó szám jegyeinek a száma, tehát lineárisan nő minden lépésben a műveleti idő. A műveleti idők összege ezáltal időegység, ahol az egy számjegyre eső műveleti idő. Az input méretével ez kifejezve: . Láthatóan ez az -től függő függvény monoton növekvő.

Az egyes függvények növekedését a növekedés rendjével jellemezzük, amely valamely előre rögzített függvényhez (etalonhoz) történő hasonlítást jelent. A hasonlítást az alábbi úgynevezett ordo szimbolika által előírt módon végezzük el. Legyen két növekedést leíró függvény.

1.20. Definíció. Az ordo szimbolika szimbólumai

Azt mondjuk, hogy az függvény növekedési rendje:

Az és a többi jelölés tulajdonképpen nem szerencsés, mert azt sugalmazza, mintha itt két függvény, az és a , valamilyen közelségéről, egyezőségéről lenne szó. Valójában az egyenlőségjel jobboldalán nem egy függvény, hanem egy általa leírt függvényosztály, függvények egy halmaza áll. A baloldalon álló egyetlen függvény nem lesz egyenlő egy halmazzal. Szerencsésebb lenne az egyenlőségjel helyett a halmaz eleme jelet használni, jelezve, hogy az függvény olyan tulajdonságú, mint a által definiált függvények. Tradicionális okok miatt azonban megmaradunk az egyenlőségjel használata mellett.

A gyakorlatban gyakran előforduló fontos jellemző növekedések

1.21. Definíció. A polinomiálisan gyorsabb növekedés

Azt mondjuk, hogy az növekedési függvény polinomiálisan gyorsabban nő, mint az polinom , ha létezik olyan valós szám, hogy .

1.22. Definíció. A polinomiálisan lassabb növekedés

Azt mondjuk, hogy az növekedési függvény polinomiálisan lassabban nő, mint az polinom , ha létezik olyan valós szám, hogy .

1.21. Példa. Az előbb tárgyalt függvény kvadratikus (négyzetes) növekedésű. Ezt a következőképpen láthatjuk be. Igaz az, hogy . Ezáltal fennáll a következő egyenlőtlenség

A feladatunk olyan pozitív konstansokat és pozitív probléma küszöbméretet mutatni, melyekre esetén

fennáll. Először a baloldalra keressük meg a megfelelő konstansokat. Kis átalakítás után az alábbi egyenlőtlenséget kapjuk:

Feltételezve, hogy , leoszthatunk vele. A kapott egyenlőtlenséget -re megoldva:

Pozitív értéket itt akkor kapunk, ha . Kényelmes választás lehet a . Ekkor 1.1-ből az adódik. A jobboldalra az algebrai átalakítások után az adódó egyenlőtlenség:

Pozitív problémaméret küszöböt akkor remélhetünk, ha az együtthatójára fennáll, hogy , azaz . Válasszuk a értéket. Az 1.1-ben szereplő másodfokú kifejezés alakja ekkor:

Ennek pozitív gyöke:

Tehát ebben az esetben az választás megfelelő. A két oldal elemzését összevetve a keresett megfelelő konstansok lehetnek: , , . Ez alapján teljesül az, hogy ha a probléma mérete legalább 8, akkor . Tehát valóban az algoritmusunk időigénye .

1.22. Példa. Bizonyítsuk be, hogy !

Bizonyítás: Ha az állítás igaz, akkor léteznie kell két pozitív konstansnak, melyekre valamely pozitív -tól kezdve igaz, hogy . Itt -nel leosztva és egyenlőtlenségek adódnak. Látszik, hogy kell legyen. Válasszuk értéket. Ebben az esetben miatt adódik. Tehát lehet például 3. A másik egyenlőtlenségből pedig mivel mindig kisebb, mint 3, ezért lehet 3, vagy annál nagyobb szám, pedig lehet tetszőleges. Összegezve: , , és megfelelő választás, azaz ha , akkor .

1.23. Példa. Bizonyítsuk be, hogy !

Bizonyítás: A definícó értelmében legyen tetszőleges pozitív konstans. Keressünk hozzá pozitív -at, amelytől kezdve fennáll. Itt -nel leosztva adódik. Átrendezéssel , amiből az megfelelő választás a definíció kielégítésére, azaz, ha , akkor a -nél nagyobb problémaméretek esetén .

1.24. Példa. bármely esetén, azaz a logaritmus függvény lassabban nő, mint bármely pozitív kitevőjű hatványfüggvény. Ennek belátására meg kell mutatnunk, hogy bármely pozitív konstans esetén valamely küszöbtől kezdve . Ez minden bizonnyal fennáll, ha belátjuk, hogy . Ekkor ugyanis a limesz definíciójának megfelelően a hányadosnak valamely küszöbtől kezdve alá kell csökkenni akármilyen kicsi pozitív szám is ez a . Természetesen az küszöb -től függ. A határérték kiszámításához az -et először helyettesítjük a valós -szel és arra számítjuk a limeszt. A típusa , így az analízisből ismert L'Hospital szabályt alkalmazva . Az is látható innen, hogy nemcsak lassabban nő, mint , hanem polinomiálisan lassabban nő, hiszen esetén -tól is lassabban nő.

1.10. A Fibonacci számok

1.23. Definíció. Fibonacci sorozat

Fibonacci számsorozatnak nevezzük azt az számsorozatot, amelyet az alábbi formulapár határoz meg:

A 1.2 és 1.3 formulapár által előállított számok sorozata így kezdődik:

A probléma a fenti definícióval az, hogy az indexű elemet nem tudjuk a megelőzőek nélkül kiszámítani a rekurziós formula alapján. Mennyi például -nak az értéke? Ennek a problémának a megoldását adja a Binet formula.

1.24. Tétel. Binet formula

A Fibonacci számsorozat elemei felírhatók az index függvényében az alábbi úgynevezett Binet formula révén:

ahol

Bizonyítás. Keresnünk kell olyan számsorozatot, amely az 1.2, 1.3 feltételeknek megfelel. Könnyebb lesz a dolgunk, ha egyelőre az 1.2 feltételtől eltekintünk. A trükk: keressünk olyan sorozatokat, amelyek tudják a 1.3 tulajdonságot és alakjuk valamilyen számra. A megoldások közül zárjuk ki a z=0 esetet, mint érdektelent, hiszen ez csupa zérust ad és az nekünk biztosan nem jó. A 1.3 tulajdonságot felírva -re

adódik, ahonnan -nel leosztva a

összefüggésre jutunk. Ennek a másodfokú egyenletnek két valós megoldása van: és . Tehát az megoldás. Könnyen meggyőződhetünk behelyettesítéssel 1.3-be, hogy akkor az is megoldás, ahol tetszőleges konstans. Ugyanígy mivel megoldás, akkor is az. Itt szintén tetszőleges konstans. Azt kaptuk, hogy a megoldások konstansszorosai is megoldások. Vegyük észre továbbá, hogy az

is megoldás.

Összegezve: a és a úgynevezett alapmegoldások (bázismegoldások) lineáris kombinációi is megoldást adnak. Helyettesítsük be 1.7-ot 1.2-be az és esetre. Ezzel csempésszük vissza a kezdetben elhanyagolt 1.2 feltételt. Az alábbi kétismeretlenes, két egyenletből álló lineáris egyenletrendszert kapjuk, melyben az ismeretlenek és .

Innen -et és -t kifejezve kapjuk, hogy

1.25. Tétel. A Fibonacci számok előállítása kerekítéssel

Az Fibonacci szám képezhető az alábbi módon a Binet formula felhasználásával:

Bizonyítás. Belátjuk, hogy és között kevesebb, mint az eltérés. Ez azt jelenti, hogy a kerekítendő szám köré fel tudunk rajzolni egy szimmetrikus intervallumot, amelynek a szélessége kevesebb, mint egy. Ekkor azonban csak egyetlen egész szám lehet ebben az intervallumban, ami így szükségszerűen éppen a Fibonacci szám lesz.

Ugyanis és . Tehát

amiből látszik, hogy egybeesik az egyetlen egésszel, amely a megadott intervallumban van.

A Fibonacci számok sorozata exponenciálisan növekszik. Ez következik a előállításból.

Írhatjuk, hogy

1.11. A rekurzív egyenletek és a mester tétel

Az algoritmusok időbonyolultságának elemzésekor sok esetben nem rendelkezünk közvetlen explicit formulával, amely megadná, hogy a méret függvényében hogyan alakul az algoritmus időigénye a legrosszabb esetben. Ismeretes lehet viszont az egyes méretek időigényei közötti kapcsolat, mivel ezt általában könnyebb felírni. Ennek a kapcsolatnak az ismeretében megpróbálhatjuk meghatározni vagy a függvényt explicite, vagy legalább annak aszimptotikus viselkedését.

1.26. Definíció. Rekurzív egyenlet

Rekurzív egyenletnek nevezzük azokat a függvényegyenleteket, amelyekben a függvény az ismeretlen, a meghatározandó, és a függvényérték a függvény -től kisebb értékű argumentumának helyein felvett értékeinek függvényeként adott.

A rekurzív egyenlet a függvényértéket a korábbi (-től kisebb helyen) felvett érték(ek) függvényére vezeti vissza. Ebben az esetben remélhetjük, hogy ha ismert az első néhány értékére a értéke, akkor a nagyobb esetére a már fokozatosan kiszámítható. Ha megadjuk ezeket az első értékeket, akkor azokat kezdőfeltételeknek (vagy kezdetiérték feltételeknek) nevezzük.

1.25. Példa. Legyen , akkor a geometriai sorozat definícióját kapjuk, mint a rekurzív egyenlet speciális esetét. Ennek megoldása triviálisan látszik, hogy , ami ismeretében egyértelműen meghatározott.

1.26. Példa. Legyen , akkor a számtani sorozat (aritmetikai sorozat) definícióját kapjuk, mint a rekurzív egyenlet speciális esetét. Ennek megoldása triviálisan látszik, hogy , ami ismeretében egyértelműen meghatározott.

1.27. Példa. Legyen és , , akkor a megoldás a Fibonacci sorozat.

A rekurzív egyenletek megoldására néhány módszert mutatunk. Egyikük a visszavezetési módszer. Nem megyünk bele bonyolult elméleti fejtegetésekbe, lényegét példákon keresztül szemléltetjük.

1.28. Példa. Legyen és . A visszavezetési módszer abban áll, hogy rendre a függvényértékeket visszavezetjük a kezdőfeltételre rekurzív behelyettesítéssel. A mi esetünkben ez így néz ki:

Az ilyen időbonyolultságú algoritmus a méret egységnyi növekedésére az idő egységnyi növekedésével válaszol. A megoldás megsejthetően . Ez teljes indukcióval be is bizonyítható. Látható az is, hogy aszimptotikusan azaz az algoritmus lineáris idejű.

1.29. Példa. Legyen és . Megoldása visszavezetéssel:

Megsejthető és teljes indukcióval belátható, hogy . Ebből pedig következik, hogy aszimptotikusan , azaz az algoritmus kvadratikus idejű.

1.30. Példa. Legyen és . Megoldása visszavezetéssel:

A függvény csak az alakú -re van értelmezve, ahol . Ezekre azt írhatjuk, hogy . Bevezetve az jelölést azt kapjuk, hogy . Egy nagyon hasonló feladatot az 1.28. Példában megoldottunk és onnan a megoldás . Akkor . Figyelembe véve, hogy , a végeredmény és , azaz az algoritmus logaritmikus idejű.

1.31. Példa. Legyen a rekurzív egyenlet , a kezdőfeltétel . Megoldása visszavezetéssel:

A megoldás a kettő egész hatványainak megfelelő helyeken egybeesik az előző feladat megoldásával. A többi helyen ellentétben az előző feladattal a megoldás értelmezve van. Megsejthető, hogy a megoldás . Erre is igaz az aszimptotika, hogy .

1.32. Példa. Olyan esetet vizsgálunk, amelyben a megoldást nem tudjuk megsejteni, de az aszimptotikát igen és teljes indukcióval bizonyítunk. Legyen . Az aszimptotikus megoldás sejthetően , azaz van olyan és , hogy ha , akkor . Helyettesítsük be az aszimptotikus sejtett megoldást az egyenletbe.

Ha most -et úgy választjuk meg, hogy a zárójelben lévő kifejezés nemnegatív legyen, akkor megkapjuk az áhított egyenlőtlenséget, miáltal a bizonyítás be is fejeződik. Az feltételezésből következik. Válasszuk most mondjuk az -et, akkor . Ebben az esetben a teljesül, tehát ha , akkor mindig fennáll , ahol a helyébe a 72, vagy bármilyen tőle nagyobb szám írható. Ezzel beláttuk, hogy a megoldás növekedési rendje valóban . Meg lehet mutatni, hogy még is fennáll.

Speciális, de a gyakorlat szempontjából sok fontos esetben a rekurzív egyenletekre az alább megfogalmazott úgynevezett mester tétel ad aszimptotikus megoldást (sok esetben meg nem ad).

1.27. Tétel. A mester tétel

Legyenek konstansok, függvény.

Definiálunk egy úgynevezett tesztpolinomot.

Legyen a rekurziós összefüggésünk: . (Az helyén vagy is állhat.) Ezen feltételek esetén igazak az alábbi állítások:

[1.] Ha polinomiálisan lassabb növekedésű, mint a tesztpolinom, akkor

[2.] Ha , akkor

[3.] Ha polinomiálisan gyorsabb növekedésű, mint a tesztpolinom, és teljesül az függvényre az úgynevezett regularitási feltétel, azaz konstans és küszöbméret, hogy esetén , akkor

A tételt nem bizonyítjuk.

1.33. Példa. A mester tétel alkalmazása: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Láthatóan polinomiálisan lassabban nő, mint , mert minden esetén . Teljesülnek a mester tétel 1. pontjának a feltételei, tehát a tételt alkalmazva: .

1.34. Példa. A mester tétel alkalmazása: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Továbbá . Teljesülnek a mester tétel 2. pontjának a feltételei, tehát a tételt alkalmazva: .

1.35. Példa. A mester tétel alkalmazása: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Ha , akkor , azaz polinomiálisan gyorsabban nő, mint a tesztpolinom, ugyanis . A mester tétel 3. pontjának a feltételei fognak teljesülni, ha még kimutatjuk az regularitását. Ez fennáll a következők szerint . Azaz minden pozitív -re teljesül a regularitás -gyel. A tételt alkalmazva: .

1.36. Példa. A mester tétel nem alkalmazható: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Az igaz, hogy legalább olyan gyorsan nő, mint a tesztpolinom, mert , tehát . Az viszont nem igaz, hogy polinomiálisan gyorsabban nő, mint a tesztpolinom. Azért nem igaz, mert bármilyen pozitív esetén . Emiatt a mester tétel gyanított 3. pontja nem alkalmazható. Az aszimptotikus megoldás a mester tétellel nem adható meg. (Behelyettesítéssel be lehet bizonyítani, hogy .)

1.12. Feladatok

  1. Adjunk meg algoritmust az alábbi problémák megoldására szövegesen is és pszeudokóddal is. Készítsük el a megfelelő folyamatábrát! Adjuk meg az algoritmus 7 jellemző vonását! Adjuk meg az algoritmus időbonyolultságát és tárbonyolultságát az input méretének függvényében! Adjuk meg ezen bonyolultságokra a növekedési rendet!

    • Két pozitív egész szám (az egyik jegyű, a másik jegyű) kézi összeadása.

    • Két pozitív egész szám (az egyik jegyű, a másik jegyű) kézi összeszorzása.

  2. Adjunk meg a Fibonacci számok növekedésének jellemzésében a definíciójának megfelelő konstansokat és küszöbméretet!

  3. Bizonyítsuk be, hogy !

  4. Oldjuk meg rekurzív visszahelyettesítéssel a következő rekurzív egyenletet!

  5. Adjunk aszimptotikus megoldást a következő rekurzív egyenletre a mester tétellel!

2. fejezet - Számelméleti algoritmusok

2.1. Alapfogalmak

2.1. Definíció. Az oszthatóság

Azt mondjuk, hogy a egész szám osztja az egész számot, ha az osztásnak zérus a maradéka, azaz, ha létezik olyan egész szám, hogy . Jelölésben: . A számot az osztójának nevezzük. Az szám a többszöröse.

2.2. Definíció. Prímszám

Prímszámnak nevezzük azt az 1-nél nagyobb egész számot, amelynek csak az 1 és saját maga a pozitív osztója.

2.3. Tétel. A maradékos osztás tétele

Ha egész szám, pedig pozitív egész szám, akkor egyértelműen létezik olyan és egész szám, hogy

A szám neve hányados, neve maradék. A hányados és a maradék felírható:

2.4. Definíció. Közös osztó

Azt mondjuk, hogy a egész szám az és egészek közös osztója, ha mindkét számot osztja (azaz és ).

2.5. Definíció. Lineáris kombináció

Az egész számot az és egészek (egész) lineáris kombinációjának nevezzük, ha létezik olyan és egész szám, hogy . Az és számokat a lineáris kombináció együtthatóinak nevezzük. Az és számok összes lineáris kombinációjának halmazát -vel jelöljük.

Speciálisan lineáris kombinációk az és az számok is. Adott egész előállításakor az és együtthatók nem egyértelműek, azaz ha léteznek, akkor több számpár is megfelelhet erre a célra, amint az az alábbi példából is látható.

2.1. Példa. Legyen két szám . Határozzuk meg az értékeket az , együtthatókra!

2.6. Tétel. A közös osztó tulajdonságai

Legyen a egész az és egészek közös osztója. Akkor fennállnak az alábbi állítások:

[1.] vagy .

[2.] Ha és , akkor .

[3.] A közös osztó osztója az és szám minden lineáris kombinációjának is, azaz -re .

2.2. A legnagyobb közös osztó

2.7. Definíció. Legnagyobb közös osztó

Az alább megadott egész számot az és egész számok legnagyobb közös osztójának nevezzük. Jele: .

2.8. Definíció. Relatív prímek

Az és egész számokat relatív prímeknek nevezzük, ha .

2.9. Tétel. A legnagyobb közös osztó elemi tulajdonságai

Legyen a egész az és egészek legnagyobb közös osztója. Akkor fennállnak az alábbi állítások:

[1.] kivéve ha és .

[2.] .

[3.] .

[4.] .

[5.] Ha közös osztó és , akkor .

[6.] A legnagyobb közös osztó minden lineáris kombinációnak osztója, azaz -re .

2.10. Tétel. A legnagyobb közös osztó reprezentációs tétele

Ha az és egész számok nem mindegyike zérus, akkor a legnagyobb közös osztó megegyezik a két szám pozitív lineáris kombinációinak minimumával.

Bizonyítás. A bizonyítás menete az lesz, hogy megmutatjuk, hogy és , amiből következik az állítás.

Az megmutatása úgy történik, hogy belátjuk, hogy közös osztó, ami nem lehet nagyobb, mint a legnagyobb közös osztó. Azt, hogy közös osztó azáltal látjuk be, hogy az osztási maradéka zérus. Csak az számra végezzük el, -re ugyanígy megy a bizonyítás. Osszuk el tehát -t -gal és számítsuk ki a maradékot! Legyen a hányados. Az maradékra igaz, hogy . Akkor

Az egyenlőtlenség közepén álló maradék az és a lineáris kombinációja. A baloldali egyenlőtlenség miatt nem lehet negatív, a jobboldali egyenlőtlenség miatt pedig kisebb, mint a pozitív lineáris kombinációk közül a legkisebb. Emiatt csak zérus lehet. Tehát az osztja az számot.

A abból következik, hogy a legnagyobb közös osztó osztja az összes lineáris kombinációt, így -ot is. Ekkor azonban nem lehet nagyobb, mint , hiszen annak osztója.

A tétel következményei:

[1.] A közös osztó osztja a legnagyobb közös osztót, ugyanis a legnagyobb közös osztó az és egészek lineáris kombinációja a tétel szerint, amit a közös osztó oszt.

[2.] Tetszőleges nemnegatív egészre

Ugyanis -ra az állítás triviális, -ra pedig

(Lássuk be, hogy az utolsó egyenlőségjel valóban igaz, azaz a lineáris kombinációkban mindkét számpár esetén ugyanaz az , megfelelő választás!)

2.11. Tétel. A lineáris kombinációk halmazának jellemzése

Legyen a egész többszöröseinek a halmaza. Állítás:

Bővebben: az minden eleme egész többszöröse és ha egy szám egész többszöröse, akkor az az szám az és lineáris kombinációja is.

Bizonyítás. Megmutatjuk, hogy és , amiből következik az állítás. Az eset: és , amiből következik, hogy van olyan , hogy . Ha , akkor

mert .

Az eset: .

Ha , akkor van olyan , hogy

2.12. Tétel. A legnagyobb közös osztó redukciós tétele

Tetszőleges és két egész szám esetén fennáll, hogy

Bizonyítás. Legyen és Azt fogjuk bizonyítani, hogy és , amiből következik a tétel állítása.

Megmutatjuk, hogy és is fennáll, amiből a kölcsönös oszthatóság már következik.

megmutatása:

megmutatása:

2.3. A bináris legnagyobb közös osztó algoritmus

Az eddigiek alapján algoritmus konstruálható a legnagyobb közös osztó meghatározására. Az algoritmus neve: Bináris lnko algoritmus.

Az algoritmus a két nemnegatív egész bináris felírásának alakjából indul ki. Az utolsó bit alapján a kiinduló problémát fokozatosan egyszerűbbé redukálja, amíg csak az egyik szám zérussá nem válik. Ekkor a legnagyobb közös osztó a másik redukált szám egy szorzóval korrigált értéke lesz. Munka közben az algoritmus csak egyszerű, hatékony gépi műveleteket - egész kivonás és jobbra eltolás (shift) - használ.

Legyen a két szám és és legyen . A kiszámításának feladata ekkor az alábbiak szerint redukálódik az utolsó bit szerint egyszerűbb feladattá:

2.2. Példa. Példa az algoritmusra:

2.4. Az euklideszi és a kibővített euklideszi algoritmus

2.13. Tétel. A legnagyobb közös osztó rekurziós tétele

Tetszőleges és két egész szám esetén fennáll, hogy .

Bizonyítás. Az az -ból ismételt kivonásaival megkapható és így a redukciós tétel (2.12) értelmében az állításunk igaz.

A rekurziós tétel révén készíthető el az euklideszi algoritmus a legnagyobb közös osztó meghatározására. Az algoritmus pszeudokódja:

2.3. Példa. Példa az algoritmusra: ,

2.14. Tétel. Lamé tétele

Ha az euklideszi algoritmusban és valamely -ra, akkor a rekurziós hívások száma kevesebb, mint .

A tételt nem bizonyítjuk

A tétel következménye, hogy ha , akkor a rekurziós hívások száma kevesebb, mint , valamint becslést tudunk adni erre a -ra közvetlenül a -ből. A értékére jól memorizálható becslés az, hogy vehető a tizes számrendszerbeli jegyei ötszörösének. (Valójában megmutatható, hogy itt a kisebb reláció is igaz.) A meggondolás az alábbi:

Bizonyítható, hogy az euklideszi algoritmusnak a legrosszabb bemenő adatai a szomszédos Fibonacci számok. Az euklideszi algoritmus időigénye azon feltételezés mellett, hogy az aritmetikai műveletek konstans ideig tartanak függetlenül a benne szereplő számértékek nagyságától. Ha a számok nagyságát is figyelembe vesszük, akkor az időigény . Az euklideszi algoritmus némi bővítéssel alkalmassá tehető arra, hogy a legnagyobb közös osztó lineáris kombinációként történő előállításában szereplő és együtthatókat is meghatározza. Tekintsük az euklideszi táblát.

A tábla sorában a rekurziós tétel alapján érvényes a összefüggés, ahol továbbá

A és indexű sorok között a kapcsolat:

Kaptunk egy összefüggést az , és az , együtthatók között az egymást követő sorokra, ha fentről lefelé haladunk a táblában.

Haladjunk most lentről fölfelé! Akkor 2.1-ból és kifejezve:

Az utolsó sor esetén viszont , azaz és . Az utolsó sorból indulva így visszafelé sorról-sorra haladva az és értékek kiszámíthatók. Végül az és is kiadódik. Ez a módosítás vezet az euklideszi algoritmus kibővítésére, melynek pszeudokódját alább közöljük.

2.4. Példa. Példa kibővített euklideszi algoritmusra

Az algoritmus eredményeképpen és adódott. Ellenőrzésképpen

ami valóban megfelel az elvárásoknak.

2.5. A lineáris kongruencia egyenlet

2.15. Definíció. Kongruencia

Az és egész számokat kongruensnek mondjuk az modulus szerint, ha az szerinti osztás utáni maradékaik megegyeznek, vagy ami ugyanaz: ha . Jelölésben: .

2.16. Tétel. A kongruenciákon végezhető műveletek tétele

Legyen és Akkor igazak az alábbi állítások:

2.17. Definíció. A lineáris kongruencia egyenlet

Az

egyenletet, melyben az ismeretlen, lineáris kongruencia egyenletnek nevezzük.

2.18. Tétel. A lineáris kongruencia egyenlet megoldhatósági tétele

Legyen az 2.2 egyenletre Az 2.2 lineáris kongruencia egyenletnek akkor és csak akkor van megoldása, ha Ha van megoldás, akkor végtelen sok van, de ezeket egy számú megoldást tartalmazó úgynevezett megoldás alaprendszerből megkaphatjuk az egész számú többszöröseinek a hozzáadásával. Az alaprendszer elemeit a intervallumból választjuk ki. Az alaprendszer megoldásai az alábbi módon írhatók fel:

Bizonyítás. Legyen , , . Akkor a lineáris kongruencia egyenlet alakra írható át, amiből az egyenlet adódik, vagyis hogy a az és az lineáris kombinációja. Ha azt akarjuk, hogy legyen megoldás, akkor fenn kell álljon, ahol az és lineáris kombinációinak a halmaza. Ha ez nem áll fenn, akkor nincs megoldás. A lineáris kombinációban lévő elemeket viszont a legnagyobb közös osztó osztja, és csak azokat osztja a lineáris kombinációk halmazának jellemzési tétele szerint. Legyen most olyan, hogy . Akkor van olyan egész szám, hogy . A legnagyobb közös osztó viszont az és az lineáris kombinációja, azaz van olyan és egész, hogy . Ez a formula viszont egyenértékű az lineáris kongruencia egyenlettel, ha az szerinti maradékokat nézzük. Beszorozva itt -val adódik, amiből azonnal látható, hogy az megoldás. További megoldásokat kapunk, hogyha képezzük az , számokat, ugyanis a lineáris kongruencia egyenletbe történő behelyettesítés után az , jelenik meg a baloldalon, ahol a második tag osztható -nel, mert a az -t osztja, így az megmarad, tehát ez a tag nem módosítja az első tag általi maradékot. Ezeket a megoldásokat alapmegoldásoknak nevezzük. Nyílvánvaló, hogy ha egész többszörösét hozzáadom az alapmegoldásokhoz, akkor újra megoldást kapok, csak az már nem lesz alapmegoldás (nem viselkedik maradékként).

A lineáris kongruencia egyenlet megoldására algoritmus konstruálható, ugyanis a kívánt a kibővített euklideszi algoritmusból megkapható.

2.5. Példa. Oldjuk meg a egyenletet!

Láttuk, hogy . A 136 osztható 68-cal, így az egyenletnek van megoldása. Az alaprendszer 68 különböző elemet tartalmaz. Most

A megoldások:

2.19. Definíció. A multiplikatív inverz

Legyen a lineáris kongruencia egyenlet

alakú (azaz és legyenek relatív prímek). Az egyenlet egyetlen alapmegoldását az szám szerinti multiplikatív inverzének nevezzük. Jelölése:

A multiplikatív inverz meghatározása történhet a lineáris kongruencia megoldó 2.5.1. algoritmus segítségével. Természetesen a FOR ciklus alkalmazására az eljárásban nem lesz szükség.

2.6. Példa. Oldjuk meg: .

Az megoldását keressük.

Láthatóan , tehát van multiplikatív inverz.

Az együtthatója , aminek a 8 szerinti maradéka . Tehát az 5 multiplikatív inverze 8-ra nézve éppen saját maga.

Ellenőrzés:

2.6. Az RSA-algoritmus

Sok esetben – többek között a majd ismertetésre kerülő RSA algoritmusban – szükség van egészek hatványa valamely modulus szerinti maradékának meghatározására. Legyen . A feladat meghatározása lehetőleg elfogadható idő alatt. Ilyennek bizonyul a moduláris hatványozás algoritmusa. Ötlete a szám bináris felírásából jön. Legyenek a bitjei: . A legmagasabb helyiértékű bit 1-es. Ha -nek ki akarjuk számítani az értékét, akkor ezt megtehetjük a hatványaival történő számítással, Ugyanezt az eredményt megkaphatjuk a gazdaságosabb Horner séma szerint:

Itt láthatóan csak kettővel való szorzást és egy nulla vagy egy hozzáadását kell végezni, melyek számítástechnikailag hatékony műveletek. Ez annál inkább hasznos, mivel még a értékét sem kell kiszámítani az algoritmusban, hiszen az adott, hanem csak az egyes bitjeit kell elérni, ami eltolásokkal hatékonyan megvalósítható. A szám a kitevőben van, ezért a hatványozás során a kettővel való szorzásnak a négyzetreemelés az egy hozzáadásának pedig az alappal történő szorzás felel meg. Minden lépés után vehető a modulo szerinti maradék, így a használt számtartomány mérete mérsékelt marad.

A megfelelő algoritmus pszeudokódja:

Az algoritmusban ténylegesen a értékét nem kell kiszámítani, mert az végül a értékét adja majd.

2.7. Példa. .

Az RSA algoritmus fel fogja tételezni, hogy nagy prímszámaink vannak. Ilyenek keresésére egy eszköz lehet (nem a leghatékonyabb és nem abszolút biztos) az alábbi tételen alapuló algoritmus.

2.20. Tétel. A Fermat tétel

Ha prím, akkor

A tételt nem bizonyítjuk.

A tételre épülő prímszám ellenőrzési algoritmus egy egyszerű, de nem teljesen megbízható változatának a pszeudokódja:

Ha ez az algoritmus azt mondja, hogy a szám összetett, akkor az biztosan nem lesz prím. Ha azt mondja, hogy lehet, hogy prím, akkor nagy eséllyel valóban prímet vizsgált, ugyanis 10000-ig terjedően a számok között csak 22 olyan van, amely nem prím és a teszt esetlegesen prímnek minősíti. Ilyenek a Ötven bites számok esetén már csak a számok egy milliomod része lehet ilyen, 100 biteseknél pedig ez az arány 1:1013. Ezen hibák egy része kiszűrhető azzal, hogy a 2 helyett más alapot is beveszünk a moduláris hatványozásba, például a 3-at, stb. Sajnos azonban vannak olyan számok, amelyek mindegyik alap esetén prímnek maszkírozzák magukat ennél az algoritmusnál. Ezek az úgynevezett Carmichael számok. A Carmichael számok relatíve nagyon kevesen vannak. (Valójában végtelen sok ilyen szám van. Ilyenek: . Az első egy milliárd szám között csak 255 ilyen van.)

2.8. Példa. Döntsük el, hogy a 11 és a 12 prímek-e?

Ezen előkészületek után térjünk rá a fejezet céljára a nyilvános kulcsú titkosításra A titkosítás alapja az eredeti szöveg átalakítása, kódolása. A nyílvános kulcsok használata azt jelenti, hogy minden résztvevőnek van egy nyílvános, mindenki számára hozzáférhető kulcsa (, nyilvános, Public) és egy titkos, más által nem ismert kulcsa (, titkos, Secret). Legyen az üzenet. Legyen a két résztvevő és . küldi -nek az üzenetet titkosítva. Az elküldött titkosított szöveg , megkapja a üzenetet és a titkos kulcsával dekódolja A kulcsok egymás inverzei, és úgy vannak kialakítva, hogy a kulcs révén könnyű legyen titkosítani, de a kulcs ismeretében nagyon nehezen lehessen - praktikusan lehetetlen legyen - az kulcsot meghatározni. A digitális aláírás ilyenkor történhet úgy, hogy a küldő a titkosított szöveg mellé akár nyíltan odaírja a saját azonosítóját (aláírását), majd annak az titkosítottját. Ezután a alapján tudva, hogy kit nevez meg az aláírás, annak privát kulcsával dekódolja -et. . Ha , akkor nem történt átviteli hiba, vagy hamisítás, egyébként igen. Persze az -mel együtt is kódolható. Ez annak felel meg, mintha az első esetben nyílt levelezőlapon lenne az aláírásunk, a másodikban pedig mintha borítékba tettük volna.

Alább közöljük az RSA (Rivest – Shamir - Adleman) nyílvános kulcsú titkosítás algoritmusát. Az algoritmus feltételez két nagy prímszámot. (A gyakorlatban legalább 100-200 jegyűekre van szükség, hogy a titkosítás praktikusan feltörhetetlen legyen.) A kulcs felépítése , ahol a két prím szorzata, pedig egy kis páratlan szám. Az kulcs .

A szöveg titkosítása a alapján történik. Dekódolása pedig az alapján. A szöveg darabolásának bitméretét az szabja meg.

Az eljárás helyességét nem bizonyítjuk.

2.9. Példa. Számpélda RSA algoritmusra (nem életszerű, mivel a prímek kicsik)

Legyen a titkos választás:

A kibővített euklideszi algoritmust alkalmazzuk.

Láthatóan és multiplikatív inverze . Ez utóbbi helyett 280-at hozzáadva vesszük a 187-et. Ezek után akkor

Legyen az üzenetünk 100. Egy darabban titkosítható, mivel ez kisebb, mint 319. Titkosítsuk, majd fejtsük meg az üzenetet.

Titkosítás:

Tehát a titkosított érték:

Megfejtés:

Tehát a megfejtés: .

2.7. Feladatok

  1. Bizonyítsuk be a közös osztó tulajdonságainak tételét!

  2. Bizonyítsuk be a legnagyobb közös osztó elemi tulajdonságainak tételét!

  3. Oldjuk meg az alábbi lineáris kongruencia egyenletet! Adjuk meg a megoldások alaprendszerét! Írjuk fel a teljes megoldásrendszert!

  4. Határozzuk meg értékét!

  5. Számítsuk ki értékét!

3. fejezet - Elemi dinamikus halmazok

3.1. A tömb adatstruktúra

Egy adastruktúra számtalan adatot tartalmazhat. Mondhatjuk, hogy egy adathalmazt tárolunk egy struktúrában. Számunkra a dinamikus halmazok lesznek fontosak.

3.1. Definíció. Dinamikus halmaz Az olyan halmazt, amely az őt felhasználó algoritmus során változik (bővül, szűkül, módosul) dinamikus halmaznak nevezzük.

A dinamikus halmazok elemei tartalmazhatnak az információs adatmezőiken felül kulcsmezőt, és mutatókat (pointereket), amelyek a dinamikus halmaz más elemeire mutatnak. (pl: a következő elemre). Felsorolunk a dinamikus halmazokon néhány általánosságban értelmezett műveletet. Konkrét esetekben ezek közül egyesek el is maradhatnak, vagy továbbiak is megjelenhetnek. Az jelöli a szóban forgó halmazt, kulcsot ad meg és mutató a halmaz valamely elemére. Feltételezzük, hogy a kulcsok között értelmezett a kisebb, nagyobb, egyenlő reláció.

Az egyes műveletek végrehajtásukat tekintve lehetnek statikusak (passzívak), vagy dinamikusak (aktívak) aszerint, hogy a struktúrát változatlannak hagyják-e vagy sem. A módosító műveletek alapvetően dinamikusak, a lekérdezők általában statikusak, de nem ritkán lehetnek szintén dinamikusak. (A dinamikus lekérdezés olyan szempontból érdekes és fontos, hogy ha egy elemet a többitől gyakrabban keresnek, akkor azt a struktúrában a keresés folyamán a megtalálási útvonalon közelebbi helyre helyezi át a művelet, ezzel megrövidíti a későbbi keresési időt erre az elemre, vagyis a művelet változást eredményez a struktúrában.)

3.2. Definíció. A sorozat adatstruktúra

Sorozatnak nevezzük az objektumok (elemek) olyan tárolási módját (adatstruktúráját), amikor az elemek a műveletek által kijelölt lineáris sorrendben követik egymást. Tipikus műveletek: keresés, beszúrás, törlés.

A sorozat egyik lehetséges implementációja – gyakorlati megvalósítása, megvalósítási eszköze – a tömb. A tömb azonos felépítésű (típusú) egymást fizikailag követő memóriarekeszeket jelent. Egy rekeszben egy elemet, adatrekordot helyezünk el. Az egyes tömbelemek helyét az indexük határozza meg. Az elemek fontos része a kulcsmező, melyet révén kérdezhetünk le az A tömb x indexű eleme esetén. Számunkra lényegtelen lesz, de a gyakorlat szempontjából alapvetően fontos része az adatrekordnak az információs (adat) mezőkből álló rész. A tömböt szokás vektornak is nevezni. Ha a lineáris elhelyezésen kívül egyéb szempontokat is figyelembe veszünk, akkor ezt az egyszerű szerkezetet el lehet bonyolítani. Ha például az elemek azonosítására indexpárt használunk, akkor mátrixról vagy táblázatról beszélünk. Ilyen esetben az első index a sort, a második az oszlopot adja meg. (Itt tulajdonképpen olyan vektorról van szó, amelynek elemei maguk is vektorok.)

A struktúrának és így az implementációnak is lehetnek attributumai – jellemzői, hozzákapcsolt tulajdonságai. A tömb esetében ezeket az alábbi táblázatban adjuk meg.

Vizsgáljuk meg most a műveletek algoritmusait!

A keresési algoritmus. Az tömbben egy kulcsú elem keresési algoritmusa pszeudokóddal lejegyezve következik alább. Az algoritmus NIL-t ad vissza, ha a tömb üres, vagy a tömbben nincs benne a keresett kulcsú elem. A tömb elejétől indul a keresés. Ha a vizsgált elem egyezik a keresett elemmel, akkor azonnal viszatérünk az indexével. (Realizáció szempontjából úgy is elképzelhetjük a dolgot, hogy a tömb elemeinek indexelése 1-gyel kezdődik és a NIL eredményt a 0 indexszel jelezzük.) Ha nem egyezik, akkor az INC függvénnyel növeljük eggyel az index értékét (rátérünk a következő elemre) és újra vizsgálunk. Addig növeljük az indexet, míg az érvényes indextartományból ki nem lépünk vagy meg nem találjuk a keresett kulcsú elemet. A legrosszabb eset az, ha az elem nincs benne a tömbben, – ekkor ugyanis az összes elemet meg kell vizsgálni – így az algoritmus időigénye: , ahol , a tömbelemek száma.

Az új elem beszúrásának algoritmusa az A tömb adott x indexű helyére szúrja be az új elemet. Az ott lévőt és a mögötte állókat egy hellyel hátrább kell tolni. Emiatt az időigény

Ezzel az algoritmussal nem tudunk az utolsó elem után beszúrni. A problémát egy erre a célra megírt külön algoritmussal is megoldhatjuk. Legyen ennek CSATOL_TÖMBHÖZ a neve. Az olvasóra bízzuk pszeudokódjának megírását. Írjunk pszeudokódot arra az esetre, amikor a beszúrás az adott indexű elem mögé történik! Ennek is van egy szépséghibája!

Egy adott indexű elem törlésének algoritmusa az elem felszabaduló helyének megfelelően az elem mögött állókat feltömöríti, egy hellyel előre lépteti. Az algoritmusban használni fogjuk a DEC függvényt, melynek hatása az, hogy csökkenti eggyel az argumentuma értékét. Ennek révén a hossz és a vége attributumokat korrigáljuk. Legrosszabb esetben az összes megmaradt elemet mozgatni kell, ezért az időigény

A lineáris törlési időt konstansra csökkenthetjük, ha a tömbelemek eredeti sorrendjének megörzése nem fontos azáltal, hogy a törlésre ítélt elem helyére a tömb utolsó elemét helyezzük és a tömböt lerövidítjük.

Az eddigiek során nem használtuk ki, hogy a tömbben a kulcsok rendezetten (növekvő sorrend, vagy csökkenő sorrend) követik egymást. Nem is használhattuk ki, hiszen ezt nem tételeztük fel. Ez ismeretlen volt a számunkra. Most azonban élünk azzal a feltételezéssel, hogy a tömbelemek kulcsai növekvő sorrendben vannak.

A keresés időigénye, amely rendezettlen tömbben lineáris volt, feljavítható logaritmikusra az úgynevezett bináris keresés révén. A bináris keresés alapötlete az, hogy a k kulcs keresésekor a kulcsösszehasonlítást a tömb középső elemének kulcsával kezdjük. Ha egyezést tapasztalunk, akkor az eljárás véget ér. Ha a k kulcs értéke kisebb, mint a megvizsgált elem kulcsa, akkor a tömb középső elemének indexétől kisebb indexű elemek között folytatjuk a keresést. Ha a k kulcs értéke nagyobb, mint a megvizsgált elem kulcsa, akkor a tömb középső elemének indexétől nagyobb indexű elemek között folytatjuk a keresést. A méret ezáltal feleződött. A további keresés ugyanilyen elv alapján megy tovább. Minden lépésben vagy megtaláljuk a keresett kulcsú elemet, vagy fele méretű résztömbben folytatjuk a keresést. Ha a résztömb mérete (hossza) zérusra zsugorodik, akkor a keresett kulcs nincs a tömbben.

Megadjuk a rekurzív algoritmust is és az iteratívat is. Mindkettőben a felezést nyílt index-intervallumra végezzük, ami azt jelenti, hogy az index-intervallum végek nem tartoznak a keresési index-intervallumhoz. Ez az ötlet jó hatással van az algoritmus szerkezetére. Az iteratív esetben az algoritmus bemenő paraméterei természetes módon a tömb és a keresett kulcs, az algoritmus az egész tömbben keres. A rekurzív algoritmus bemenő paraméterei a rekurzivitás sajátosságai révén szintén természetes módon a tömb, a keresési nyílt index-intervallum két vége valamint a keresett kulcs. Tehát alaphelyzetben ez az algoritmus csak a tömb egy összefüggő részében keres, nem a teljes tömbben. Ha a teljes tömbben akarunk keresni, akkor az algoritmust a

BINÁRIS_KERESÉS_TÖMBBEN ( A, fej[A] - 1, vége[A] + 1, k )

sorral kell aktivizálni. Itt feltételeztük, hogy a tömb nem üres.

A másik két művelet hatékonyságára a rendezettség nincs jótékony hatással. A beszúrásnál a helycsinálás továbbra is lineáris ideig fog tartani, és ez lesz a helyzet a törlésnél is a tömörítés idejével.

3.2. A láncolt lista (mutatós és tömbös implementáció)

Egy másik lehetőség a sorozat implementálására a láncolt lista.

3.3. Definíció. A láncolt lista adatstruktúra

A láncolt lista (linked list) olyan dinamikus halmaz, melyben az objektumok, elemek lineáris sorrendben követik egymást. A lista minden eleme mutatót tartalmaz a következő elemre. Műveletei: keresés, beszúrás, törlés.

A láncolt listáról nem feltételezzük, hogy az egymást követő elemei a memóriában valamilyen szabályszerűségnek megfelelően követik egymást. Az elemek lehetnek bárhol, az egyes elemeket mutatón keresztül érhetjük el, nem az index révén.. Ha valamely elemet – például az elsőt - megtaláltuk, akkor a rákövetkezőt is megtaláljuk a benne lévő mutató alapján. Az elem számára helyet foglalni elegendő csak a keletkezése pillanatában. Megszünésekor helyét felszabadíthatjuk. Ennek feltétele, hogy elérhető legyen a dinamikus memória gazdálkodás. A láncolt listák a mutatók és a kulcsok alapján osztályozhatók az alábbi egymást ki nem záró szempontok szerint.

Az listának, mint struktúrának az attributuma a fej[L], ami egy a lista első elemére mutató mutató. Ha fej[L] = NIL, akkor a lista üres. A listaelemek attributumai az alábbi táblázatban következnek. A tárgyalásban kétszeresen láncolt, nem rendezett, nem ciklikus listáról van szó. A listaelemet az mutató révén érhetjük el.

Tekintsük át most a műveletek pszeudokódjait. Elsőként a keresés. A keresésnél a listafej információ alapján a lista kezdetét megtaláljuk és a köv mutatók révén végig tudunk lépkedni a listaelemeken, miközben vizsgáljuk a kulcsok egyezőségét. A legrosszabb eset az, amikor az elem nincs a listában. Ilyenkor minden elem vizsgálata sorrakerül és ez adja a lineáris időt.

A beszúrást konstans idő alatt azáltal tudjuk elvégezni, hogy az új elemet mindig a lista legelső eleme elé szúrjuk be. Ekkor mindegy, hogy hány elem van a listában, a beszúrási idő ugyanannyi.

Szintén megoldható konstans idő alatt a beszúrás a lista tetszőleges eleme elé, vagy mögé, amennyiben az elemre mutató mutató meg van adva. Ha a mutató helyett az elem kulcsa van megadva, akkor lineáris idejű a beszúrás, mivel a beszúrás tényleges elvégzése előtt az elemet meg kell keresni a listában.

Törlésnél az elem nem szűnik meg létezni, csak a listából kiláncolódik, a listán lépkedve többé nem érhető el. Elérhető viszont más úton akkor, ha valahol maradt valamilyen mutató, amely rá mutat. A konstans idő abból adódik, hogy az algoritmus input adataként a törlendő elem mutatóját adjuk meg, így az elemet nem kell keresni. Ha az inputban a törlendő elem kulcsa szerepelne, akkor a kiláncolás előtt előbb a kulcs alapján az elemet meg kellene keresni, ami miatt az idő lineárissá nőne.

Némi kényelmetlenséget jelent a lista kezelésénél a listavégek állandó vizsgálata, valamint hogy a végeken az algoritmus lépései eltérnek a középen alkalmazott lépésektől. Ennek a feloldása úgynevezett szentinel (őrszem, strázsa) alkalmazásával megoldható.

Legyen nil[L] egy mutató, amely az alábbi szerkezetű elemre mutat:

Ez az elem testesíti meg a nem létező NIL elemet. Ezzel az elemmel tulajdonképpen egy ciklikus listát valósítunk meg, melyben egy olyan kulcsú elem van, amelyről azonnal eldönthető, hogy a valódi listához nem tartozhat hozzá. Bármilyen irányban haladunk a listán, mindig jelezni tudjuk a kulcs vizsgálata révén, hogy a lista elejére, vagy a végére értünk. Ennek a listának a sajátossága, hogy köv[nil[L]] a lista első elemére mutat, elő[{nil}[L]] pedig az utolsó elemére. A lista utolsó eleme esetében köv[x] = nil[L], az első eleme esetében pedig elő[x] = nil[L]. A fej[L] attributumra nincs szükség!

Ennek megfelelően az algoritmusaink az alábbi módon változnak, egyszerűsödnek.

A rendezett lista rendezettségi tulajdonságait sajnos nem tudjuk kihasználni algoritmus gyorsításra. Ha a dinamikus memória gazdálkodás nem elérhető, vagy nem kívánunk vele élni, vagy egyszerűen nem vonzódunk a mutatók használatához (bár ez utóbbi nem úri passzió kérdése egy informatikai rendszer kifejlesztésekor), akkor a láncolt lista adatstruktúra realizálható, implementálható tömbbel is. Ekkor minden tömbelemet kiegészítünk ,,mutató” mezőkkel, amelyek valójában tömbelem indexeket fognak tárolni. A listafej is egy különálló, egész számot tároló rekesz lesz, amely megmutatja, hogy a tömb melyik eleme számít a lista kezdő elemének. A műveletek realizálásának pszeudokódjában a beszúrásnál most azt is figyelni kell, hogy van-e még fel nem használt rekesz a tömbben, vagyis, hogy a rendelkezésre álló memória korlátos. Természetesen a valódi mutatók használatakor is figyelni kell a memóriát, hiszen minden új elem megjelenése új memóriaigényt támaszt. A tömbös realizációhoz javasolható a következő séma. Legyen a fej annak a rekesznek a neve, melyben a lista első elemének a tömbelem indexe található. A NIL mutatót szimbolizálja a zérus. A listaelemek tárolására rendelkezésre bocsátott tömb neve legyen A, elemeinek indexelése induljon 1-től és tartson max n-ig. Minden tömbelem, mint rekord álljon a kulcsmezőből, az információs mezőkből, valamint a ,,mutató” mezőkből (előző elemre és a következő elemre mutatók). A zérus realizálja itt is a NIL mutatót.

3.1. Példa. Álljon a listánk a következő kulcsú elemekből: 423, 356, 764, 123, 987, 276, 839. Tömbös realizácóval a következőképpen nézhet ki egy ilyen láncolt lista egy tömbben, amelynek mondjuk 10 eleme van. A rekordokból (sorokból) az információs mezőket kihagyjuk, mert a tárgyalás szempontjából lényegtelenek

Ha most a fenti listába be kellene szúrni a 247-es kulcsot, akkor ez többféle módon is megtehető. Be lehet szúrni - ha semmilyen megkötés sincs – az új elemet a lista elejére az első elem elé. Másik lehetőség, hogy megmondják, hogy például szúrjuk be a 356-os kulcsú elem mögé. Van ezeken kívül még sok lehetőség. Nézzük az említett két esetet. Az új elemet egyelőre helyezzük el mondjuk a tömb 2-es indexű helyén, ami jelenleg üres és a listához nem tartozik hozzá. A lista első eleme az új elem lesz, tehát az ő elő mutatója zérus lesz, és a régi első elem elő mutatója az új elemre fog mutatni, tehát 2-re változik. Meg kell még adni az új első elem köv mutatóját, amely a régi első elemre mutat, tehát értéke 3 lesz, ami korábban a fej mutató volt. A fej mutatónak pedig az új első elemre kell mutatni, tehát értéke 2 lesz. Látható, hogy a művelethez a mutatókat illetően négynek a megváltoztatására volt szükség. Ezek után az új lista tömbös megjelenése alább látható a baloldali táblázatban. A változásokat vastagítva és aláhúzva jelenítettük meg. A másik esetben az új elem elő mutatója a 356-osra fog mutatni, amely a 6-os helyen van, a köv mutatója pedig a 356-os köv mutatóját kapja, vagyis 1-et. A 356-os köv mutatója is és a 356 mögött korábban álló elem (a 764-es kulcsú) elő mutatója is az új elemre mutat, tehát mindkettő értéke 2. Vigyázni kell a mutatók megváltoztatásánál. A 764-es elő mutatóját hamarabb kell megváltoztatni, mint a 356-os köv mutatóját, mert ellenkező esetben a 356-os köv mutatója már nem a 764-esre mutat. Itt is négy mutató változott. Az eredmény az alábbi jobboldali táblázatban látható.

3.2. Példa. Az 1. példabeli listából töröljük a 356-os kulcsú elemet. A kulcs alapján először az elemet meg kell keresni, hogy ismerjük a helyét (a tömbelem indexet). A fej-töl elindulva az első elem a 3-as indexű, az ő kulcsa 423, ami nem jó nekünk. A 3-as köv mutatója 6, és a 6-os indexű kulcsa 356, amit kerestünk. Tehát a listából a 6-os indexűt kell törölni, ami a lista láncából történő kiláncolást jelenti, tehát maga az elem nem semmisül meg. A kiláncoláshoz megnézzük, hogy melyik a megelőző elem. Ez az elő mutató szerint a 3-as. Ezért a 3-as köv mutatóját lecseréljük a 6-os köv mutatójára, azaz 1-re, és a 6-os köv mutatója szerinti 1-es indexű elem elő mutatóját lecseréljük a 6-os elő mutatójára, azaz 3-ra. A törléshez tehát elegendő volt két mutatót megváltoztatni. Az eredmény az alábbi táblázatban látható:

3.3. A verem és az objektum lefoglalás/felszabadítás

3.4. Definíció. A verem adatstruktúra

A verem (stack) olyan dinamikus halmaz, amelyben előre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk. Ez az elem mindig az időben a legutoljára a struktúrába elhelyezett elem lesz. Műveletei: beszúrás (push), törlés (pop).

Az ilyen törlési eljárást Utolsóként érkezett – Elsőként távozik (Last In – First Out, LIFO) eljárásnak nevezzük.

A verem jele S, attributuma a tető[S], amely egy mutató, a legutóbb betett (beszúrt) elemre mutat. Itt a tömbös realizációt mutatjuk be. A vermet egy S tömb valósítja meg. A kezdő tömbindex az 1-es. Az üres verem esetén a tető[S] tartalma zérus. Beszúrásnál a tető[S] tartalma nő eggyel, és az elem a tető[S] által mutatott indexű rekeszbe kerül. Törlésnél csak a tető[S] tartalma csökken eggyel elem nem semmisül meg. Figyelnünk kell, hogy lehetetlen esetben ne végezzük el a műveletet. Nincs beszúrás, ha betelt a tömb, nincs törlés, ha üres a verem. Érdemes ezeket a vizsgálatokat külön eljárásként megírni. Alább következnek a megfelelő pszeudokódok.

3.3. Példa. Helyezzük el egy kezdetben üres verembe a megadott sorrendben érkező 342, 416, 112 kulcsú elemeket, majd ürítsük ki a veremet! A verem maximális mérete hat elem.

A törléseknél láthatóan az elemek nem törlődtek fizikailag, csak már nem elérhetők. Újabb beszúrások esetén természetesen felülíródnak az új elemmel és akkor végképpen elvesznek.

A verem realizálható olyan egyszeresen láncolt, nemrendezett, nemciklikus listával is, ahol a beszúrás mindig a lista első eleme elé történik, és a törlés mindig az első elemet törli.

Egy szép alkalmazása a veremnek és a listának együtt a memóriaterület (objektum) lefoglalása és felszabadítása. Legyen m rekeszünk az adatrekordok tárolására. Legyen n m rekesz lefoglalva listás szerkezettel. Szabadon áll m - n rekesz további elemek számára. Ezeket a szabad rekeszeket egy egyszeresen láncolt listában tartjuk nyilván. A szabad globális mutató mutat az első szabad helyre. Mindig az első szabad helyet foglaljuk le, vagy a felszabadult hely a szabadok közé az első helyre kerül. Tehát a szabad rekeszek egy vermet alkotnak. A felszabadult rekesz a verembe kerül, rekesz igénylés esetén pedig a veremből elégítjük ki az igényt. Két művelet jelentkezik, az objektum lefoglalása és az objektum felszabadítása. Pszeudokódjaik:

3.4. Példa. Legyen adott 6 rekesz – egy hatelemű tömb - tárolási célra. A tömb kezdetben üres. Végezzük el a megadott sorrendben a felsorolt kulcsokkal a műveleteket. Ha a kulcs előtt egy T betű áll, akkor azt törölni kell, ha nem áll semmi, akkor be kell szúrni. Az elemeket kétszeresen láncolt listában tartjuk nyilván, a beszúrás az egyszerűség kedvéért történjen mindig a lista elejére és az objektum lefoglalás/felszabadítás vermes módszerét alkalmazzuk. A kulcsok felsorolása: 987, 654, 365, 247, T654, 123, T247, 235.

A következő animáción látható a megoldás:

Ugyanez lépésenként:

3.4. A sor

3.5. Definíció. A sor adatstruktúra

A sor (queue) olyan dinamikus halmaz, amelyben előre meghatározott az az elem, melyet a TÖRÖL eljárással eltávolítunk és az az elem is amelyet a BESZÚR eljárással a halmazba beteszünk. Törlésre mindig az elemek közül a legrégebben beszúrt kerül. A beszúrt elem lesz a legfrissebb elem. Műveletek: beszúrás, törlés.

Az ilyen törlést Elsőként érkezik – Elsőként távozik (First In – First Out, FIFO) eljárásnak nevezzük. Ha az elemeket lineárisan egymás mellé felsorakoztatjuk az érkezésük sorrendjében, akkor szemléletesen mondhatjuk, hogy törlésre mindig az első helyen álló elem kerül, a beszúrás pedig az utolsó elemet követő helyre történik. A sornak, mint adatstruktúrának többféle realizációja lehetséges. Itt most a tömbös realizációval foglalkozunk. Legyen a tömb neve Q és legyen a tömbméret[Q] attributum értéke n, azaz a tömb n elemű. Az elemek indexelése legyen Tömbös realizáció esetén a tömb a méreténél legalább eggyel kevesebb elemű sort képes csak tárolni. A sor attributumai:

A sor elemei a tömbben a fej[Q], fej[Q]+1, fej[Q]+2,\dots ,vége[Q]-1 indexű helyeket foglalják el. Ebben az index felsorolásban az indexek ciklikusan követik egymást, azaz az n index után az 1 index következik, ha erre szükség van. A műveletek szempontjából a törlés esetében nyilvánvaló, hogy üres sorból nem lehet elemet törölni. Az üres sor felismerhető abból, hogy fej[Q]=vége[Q]. (Kezdetben fej[Q]=vége[Q]=1.). Ha üres sorból veszünk ki elemet, az hiba (alulcsordulás). A beszúrás esetében nem szabad azt elvégezni, ha a sor már megtelt. Ez a jelenség felismerhető abból, hogy A beszúrás tele sorba hibát eredményez (túlcsordulás). Nézzük a műveletek pszeudokódjait:

3.5. Példa. Végezzük el az alábbi műveleteket egy üres sorból kiindulva. A következő felsorolásban egy kulcsérték annak beszúrását jelenti. A T betű a sorból eltávolítást szimbolizálja. A tömb 5 elemű. A felsorolás: 345, 231, 768, T, 893, T, 259, 478. Az eredmény alább látható. Minden egyes lépésben megmutatjuk a sor állapotát. Vastagítottuk a sorhoz hozzátartozó elemeket.

Animációként:

Ugyanez lépésenként:

Sor realizálható láncolt listával is. Törölni mindig a lista első elemét töröljük, beszúrni pedig mindig a lista utolsó eleme után szúrunk be. Elegendő egyszeresen láncolt listával dolgozni, viszont ilyenkor érdemes a lista végének a mutatóját is külön tárolni. Ha kétszeresen láncolt listát használunk, akkor már a ciklikus lista használata a hatékonyabb és ekkor a listavég mutatót nem kell külön tárolni.

3.5. Feladatok

  1. Írjuk meg a CSATOLTÖMBHÖZ algoritmus pszeudokódját! Mennyi az algoritmus időigénye?

  2. Készítsünk lineáris idejű algoritmust a listaelemek sorrendjének megfordítására ?(1) mennyiségű további memória felhasználásával. A listán csak egyszer menjünk végig!

  3. Írjuk meg a sor műveleteinek pszeudokódját egyszeresen láncolt listás realizációra!

  4. Írjuk meg a sor műveleteinek pszeudokódját kétszeresen láncolt ciklikus listás realizációra!

  5. Készítsünk pszeudokódot egy tömbös realizációjú, kétszeresen láncolt listából elem törlésére, ahol a paraméterek a lista neve és a törlendő elem kulcsa. A törlendő elem indexét meg kell keresni. Ha az elem nincs a listában, akkor adjunk hibajelzést és természetesen ne végezzünk semmilyen törlést. Figyeljünk a listavégek törlésének esetére.

4. fejezet - Keresés, rendezés egyszerű struktúrában (tömb)

4.1. Keresés

4.1.1. Lineáris keresés

A tömb adatstruktúrában a keresés műveletét részint megtárgyaltuk a 3.1. fejezetben. Két esetet különböztettünk meg, a rendezetlen és a rendezett tömb esetét. Rendezetlen tömbben egy adott k kulcsú elem megkereséséhez nem áll rendelkezésre semmilyen információ azon kívül, hogy az elemek lineárisan követik egymást. Hiába érhetők el az elemek tetszőleges sorrendben, minden elemet meg kell vizsgálni, hogy a kulcs megegyezik-e a keresett k kulccsal, ugyanis azt sem tételeztük föl, hogy például a kulcsok számok. A kulcsok természete lehet olyan is, hogy mondjuk a rendezésükről szó nem lehet. (Nevezzünk meg ilyen kulcsokat!) Ez pedig azt jelenti, hogy a lineáris keresésnél jobb növekedési rendű időbonyolultsággal rendelkező algoritmus nem adható. A keresés rendezetlen tömbben lineáris idejű, azaz a keresési algoritmus időbonyolultsága . Ez egy aszimptotikus összefüggést jelent (pontosítva: ), melyben egy pozitív konstans. Nem mindegy azonban ennek a konstansnak a konkrét értéke. Azt megtehetjük, hogy a lineáris keresési algoritmust némiképpen módosítva ezt a konstanst lejjebb szorítjuk. Tekintsük például a 3.1.1. keresés_tömbben algoritmust. Legyen az algoritmus számmal számozott sorának a végrehajtási ideje . Tételezzük fel a számolási idő szempontjából a legrosszabb esetet, hogy a keresett elem nincs a tömbben. Ekkor a keresés ideje:

Nem túl sokat torzítunk a valóságon, ha feltételezzük, hogy az értékadás és egy relációvizsgálat valamint logikai művelet (ÉS) körülbelül azonosan ideig tart. Akkor , és így

A -nek megfelelő aszimptotikus kifejezésben szereplő konstans értéke -nek vehető. Módosítsuk most úgy a 3.1.1. algoritmust, hogy a keresés kezdetén a keresett k kulcsot a tömb végéhez hozzáfüggesztjük. Feltesszük, hogy erre van elegendő hely. Ebben az esetben az elem biztosan benne lesz a tömbben. A keresésből a tömbelem indexének végvizsgálata kihagyható. A keresés mindig sikeres lesz, csak ha a visszakapott index nagyobb, mint az eredeti tömb utolsó elemének indexe, akkor valójában az elem nincs a tömbben. Íme a megváltoztatott algoritmus pszeudokódja:

Most a legrosszabb eset ideje

Itt azt feltételezhetjük, hogy , amiből

Itt az aszimptotikus kifejezés konstansa , tehát ezzel a kis trükkel ha a futási idő jellegét (linearitását) nem is, de a konkrét idejét közel felére sikerült csökkenteni a 3.1.1. algoritmus idejéhez képest.

4.1.2. Logaritmikus keresés

Rendezett tömb esetén láttuk a 3.1. fejezetben, hogy a lineáris időnél jobbat is el tudunk érni a bináris kereséssel (3.1.4. algoritmus), amely logaritmikus időt ad. A bináris keresés mellett vele konkuráló érdekes algoritmus a Fibonacci keresés algoritmusa. Feltételezzük, hogy a kulcsokat (és az adatrekordokat) tartalmazó tömb neve , mérete , és a tömbelemek indexelése egytől indul. A rekordok a kulcsok növekvő sorrendje szerint követik egymást, a kulcsok pedig mind különbözőek. Alább megadjuk szövegesen a Fibonacci keresés algoritmusát. A felírást azon feltétel mellett tesszük meg, hogy legyen egyenlő az Fibonacci számmal. (Az algoritmus módosítható tetszőleges pozitív egész esetére is.)

A Fibonacci keresés algoritmusa:

Az eddigi keresési algoritmusok csak a rendezettség tényét használták ki, lényegtelen volt a kulcsok milyensége. Ha föltételezzük, hogy a kulcsok számok, akkor használhatjuk az úgynevezett interpolációs keresést. A módszer hallgatólagosan feltételezi, hogy a kulcsok növekedésükben körülbelül egyenletes eloszlásúak (majdnem számtani sorozatot alkotnak). Az átlagos keresési idő: . Az elv azon alapszik, hogy a feltételezéseink mellett a keresett kulcs a sorban az értékének megfelelő arányosság szerinti távolságra van a keresési intervallum balvégétől. Azaz ha a balvég indexe , a jobbvégé , a megfelelő kulcsok és , akkor a következő vizsgálandó elem indexe Ha a keresett kulcs megegyezik ezen elem kulcsával, akkor az algoritmus sikeresen befejeződik. Ha a kulcs értéke kisebb, akkor az intervallum jobbvégét, ha a kulcs nagyobb, akkor a balvégét cseréljük le erre a közbülső elemre és az új intervallummal folytatjuk a keresést. Az algoritmust nem részletezzük.

4.1.3. Hasító táblák

A hasító táblák algoritmusai tömböt használnak a kulcsok (rekordok) tárolására, de nem az eddig megszokott értelemben, vagyis a tömböt általában nem töltik fel teljesen és a rekordok nem feltétlenül hézagmentesen helyezkednek el a tömbben. Az algoritmusok a keresésre, módosításra, beszúrásra és a törlésre vannak kihegyezve, tehát ezek a műveletek végezhetők el a struktúrán hatékonyan. Például a legkisebb kulcs megkeresése a struktúrában már nem olyan hatékony, mint a fent nevezettek. Az alapvető problémát az okozza, és ez az oka ezen adatstruktúra bevezetésének, hogy a kulcsok elméletileg lehetséges halmaza - az úgynevezett kulcsuniverzum – számottevően bővebb, mint a konkrétan szóbajöhető kulcsok halmaza, amelyet ráadásul még csak nem is ismerünk pontosan. Egy példával világítjuk ezt meg. Legyen adott egy cég, amelyről ismert, hogy legfeljebb 5000 alkalmazottja van. Minden alkalmazottról bizonyos adatokat nyilván kell tartani a különböző adminisztrációs feladatok elvégzéséhez. Ezen adatok egyike a TAJ-szám, amely kilencjegyű, előjel nélküli egész szám. Ezt az adatot néztük ki magunknak kulcs céljára, mivel a TAJ-szám egyértelműen azonosítja a személyt. Ha csak ennyit tudunk a TAJ számról – és most nem is akarunk annak mélyebb ismereteiben elmélyedni, - akkor ez lehetséges kulcsot jelent. Ennyi eleme van a kulcsuniverzumnak. Ebből az írdatlan mennyiségű kulcsból nekünk viszont csak körülbelül 5000 kell. Azaz a kulcsuniverzumnak csak egy viszonylag szűk részhalmaza, (a teljes halmaz körülbelül -a). Azt viszont nem tudjuk, hogy melyik részhalmaz. A kulcsokat majd a munkatársak hozzák magukkal. Ráadásul a személyi mozgás, fluktuáció révén ezek a kulcsok változhatnak is. Teljességgel nyílvánvaló, hogy értelmetlen lenne az adatbázisunkban egy milliárd rekord számára helyet biztosítani. Elég, ha egy kis ráhagyással mondjuk körülbelül 6000 rekordnak foglalunk le helyet ( körüli ráhagyás). Ezen a helyen kell az 5000 rekordot úgy elhelyezni, hogy a rekordok keresése, módosítása, beszúrása, törlése hatékony legyen. Azt a táblázatot (tömböt), ahol a rekordokat, vagy a rekordokra mutató mutatókat (pointereket) elhelyezzük, hasító táblázatnak, hasító táblának nevezzük az angol hash table elnevezés után. A hasító tábla elemeinek indexelése nulláról indul. A tábla elemeit résnek is szokás nevezni. Külön érdemes kihangsúlyozni a módosítás műveletét, amely tulajdonképpen két részből áll, egy keresésből, majd a megtalált rekord módosításából. Ha ez a módosítás a rekord kulcsmezejét érinti, akkor a rekordot a táblából először törölni kell, majd a módosítás elvégzése után újra be kell szúrni az új kulcsnak megfelelően.

Közvetlen címzésű táblázatról beszélünk, ha a kulcsuniverzum az számok halmaza, ahol az egy mérsékelt nagyságú szám. A tárolási célra használandó tábla (tömb) mérete legyen , amit most válasszunk -nek. Ekkor a kulcs egyúttal az index szerepét játszhatja, azaz a kulcsuniverzum minden kulcsa egyidejűleg tárolható. Ha valamely kulcsot nem tároljuk, akkor a helye, a rés üres lesz. Az üres rés az jelenti, hogy a rés tartalma NIL. (Pointeres változat.) A keresés, beszúrás, törlés algoritmusai ekkor rém egyszerűek, pszeudokódjaik következnek alább. Mindegyik művelet időigénye konstans, . A tömb neve , utalásképpen a táblázatra.

Az ismertetett eset nagyon szerencsés és nagyon ritka. Általában értéke lényegesen nagyobb, mint a ténylegesen tárolható kulcsok m száma. A memóriaigény leszorítható -re úgy, hog az átlagos időigény maradjon a láncolt hasító tábla alkalmazásával. Ebben a táblában minden elem egy listafej mutatója, amely kezdetben az üres táblázat esetén mindenütt NIL. Most nem tételezzük fel, hogy az kulcsuniverzum a számok halmaza lenne, de feltételezzük, hogy ismerünk egy úgynevezett hasító függvényt, amely az kulcsuniverzum elemeit képezi bele ebbe a számhalmazba, az indexek halmazába: . Ez a függvény egyáltalán nem lesz injektív, azaz nem fog feltétlenül különböző kulcsokhoz különböző számértéket rendelni, hiszen az elemszáma sokkal több, mint a indexhalmazé. (Ezt a viszonyt az jelöléssel szoktuk jelezni.) A célunk a hasító függvénnyel az, hogy a kulcsú rekord a tábla indexű réséből indított láncolt listába kerüljön. Ezzel a stratégiával oldjuk fel az úgynevezett ütközési problémát, ami akkor lép fel, ha két különböző kulcs ugyanarra az indexre (résre) képeződik le. (Az ütközésnek nem kicsi az esélye. Ha egy tízemeletes ház földszintjén négyen belépnek a liftbe és mindenki a többitől függetlenül választ magának egy emeletet a tíz közül, akkor -féleképpen választhatnak. Ebből a 10000-ből csak olyan van, amikor mindenki a többitől eltérő emeletet választott. Ha továbbá minden ilyen választást azonos esélyűnek tekintünk, akkor annak esélye, hogy legalább két ember ugyanazt az emeletet választotta eszerint . Tehát majdnem eséllyel lesznek olyanok, akik ugyanarra az emeletre mennek. A híres von Mises féle születésnap probléma esetén elegendő legalább 23 embernek összejönni, hogy legalább eséllyel legyen köztük legalább kettő olyan, akik azonos napon ünneplik a születésnapjukat.) Egy elemnek a listában történő elhelyezése történhet a lista elejére történő beszúrással, vagy készíthetünk rendezett listát is, ha a kulcsok rendezhetők. Az egyes műveletek pszeudokódjai alább következnek. Az egyes műveletek idejeivel kapcsolatban bevezetünk egy fogalmat, az úgynevezett telítettségi arányt, vagy telítettségi együthatót.

4.1. Definíció. A telítettségi arány

Az számot a hasító tábla telítettségi arányának nevezzük, ahol a tábla réseinek a száma, pedig a táblába beszúrt kulcsok száma.

A telítettségi arány láncolt hasító tábla esetén nemnegatív szám, amely lehet 1-nél nagyobb is. Szokásos elnevezése még a kitöltési arány is.

Vezessünk most be két jelölést. A megvizsgált kulcsok átlagos számát jelölje a sikeres keresés esetén és a sikertelen keresések esetén.

4.2. Tétel. A láncolt hasító tábla időigénye

Ha a kitöltési arány, akkor a láncolt hasító táblában

és

A láncolt hasító tábla mérete nem korlátozza a struktúrában elhelyezett rekordok számát. Természetesen ha a rekordok száma igen nagy, akkor az egyes résekhez tartozó listák mérete is igen nagy lehet. Nem ritkán azonban ismeretes egy felső korlát a rekordok számára és azok (vagy a kulcsaik, vagy a mutató a rekordra) elhelyezhetők magában a táblázatban. Minden táblabeli elem (rés) legalább két mezőből fog állni az alábbi tárgyalásmódban, egy kulcsmezőből és egy mutatóból, amely a következő elemre mutat. Minden réshez tartozik egy foglaltsági bit, amely szerint a rés lehet szabad, vagy lehet foglalt. Közöljük két algoritmus pszeudokódját. Az első a megadott kulcsú elemet keresi a táblában. Ha megtalálta, akkor visszaadja az elem indexét, ha nem találta meg, akkor NIL-t ad vissza. A második a megadott kulcsú elemet beszúrja a táblába, ha az elem nincs a táblában és van még ott üres hely. Ha az elem benne lenne a táblában, akkor az algoritmus visszatér. Az algoritmus jellegzetessége, hogy a különböző résekhez tartozó listák egymásba nőnek. Az üres helyek adminisztrálása céljából bevezetünk egy változót, amely mindig azt fogja mutatni, hogy az és a magasabb indexű helyeken a táblaelemek már foglaltak. Az a tábla attributuma lesz. Üres táblára , minden rés szabad és a köv mutatók mindegyike NIL.

A törlés műveletét itt nem tárgyaljuk, hanem külön diszkusszió tárgyává tesszük a feladatok között. A keresés és beszúrás műveletének átlagos idejére érvényesek az alábbi közelítő formulák:

Eddig nem szóltunk a hasító függvényről közelebbit. Egy jó hasító függvény kielégíti az egyszerű egyenletességi feltételt, ami azt jelenti, hogy minden kulcs egyforma eséllyel képződik le az rés bármelyikére, amely az ütközések elleni harcban fontos. Ezen felül lényeges, hogy a függvény értéke nagyon gyorsan számítható legyen. Az igazán nem komoly probléma, hogy a kulcsok sokfélék lehetnek, hiszen általában könnyen konvertálhatók számértékké. Például ha a kulcs szöveges, akkor tekinthetjük a szöveg egyes betűinek az ASCII kódját és minden ilyen számértéket egy magasabb alapú számrendszer számjegyeinek vesszük. Ha a szöveg csak (latin) nagybetűket tartalmaz, akkor minden betűhöz hozzárendelhetjük az ábécében elfoglalt helyének az eggyel csökkentett sorszámát. A – 0, B – 1, C– 2, D – 3, E – 4, ..., Z – 25. Ekkor a ,,ZABA” szöveghez hozzárendelhető szám 26-os számrendszerben . Két nagy módszer osztályt szokás kiemelni a hasító függvények kiválasztásakor, az osztó módszerű és a szorzó módszerű függvényeket.

Az osztó módszer esetében a formulával dolgozunk. Nem árt azonban némi óvatosság az kiválasztásánál. Ha páros, akkor paritása is olyan lesz, mint a kulcsé, ami nem szerencsés. Ha a 2-nek hatványa, akkor a kulcs utolsó bitjeit adja. Általában prímszámot célszerű választani. Knuth javaslata alapján kerülendő az az , amely osztja az számot, ahol és kicsi számok, pedig a karakterkészlet elemeinek a száma. Például ha és a kulcsok az ASCII táblázatbeli karakterek lehetnek és az Fermat-féle prímszámot választjuk, akkor mondjuk háromkarakteres kulcsok esetén a kulcsot tekinthetjük egy 256-os számrendszerbeli háromjegyű számnak is. Ha most itt -mel osztunk, , akkor az osztás eredménye lesz, ami azt jelenti, hogy az eredmény úgy adódik, hogy a szám első jegyét levonjuk a hátsó két jegy által alkotott számból. Ezáltal egymáshoz közeli kulcsok egymáshoz közelre képződnek le.

A szorzásos módszer esetében a formulát használjuk, ahol A egy alkalmas módon megválasztott konstans, . Igen jó tulajdonságokkal rendelkezik az

számérték, amelyet a Fibonacci számokkal kapcsolatban már megismerhettünk.

Nyílt címzések

A nyílt címzésű hasító táblákban nincsenek táblázaton kívül tárolt elemek, listák. A táblaelemeket (a rekordokat) a indexekkel indexeljük. Az ütközések feloldására azt a módszert használjuk, hogy beszúráskor amennyiben egy rés foglalt, akkor valamilyen szisztéma szerint tovább lépünk a többi résre, míg üreset nem találunk és oda történik a beszúrás. Keresésnél szintén ha a számított résben nem a keresett kulcs van, akkor a beszúrási szisztéma szerint keressük tovább. Formálisan ezt azáltal érjük el, hogy a hasító függvényünket, amely eddig csak a kulcstól függött, most kétváltozósra terjesztjük ki, a második változója a próbálkozásunk sorszáma lesz. Ez a szám a számok valamelyike lehet. Azaz a függvényünk: és egy rögzített kulcs esetén a egy úgynevezett kipróbálási sorozatot produkál. Ezek az indexek a indexhalmaznak egy permutációját kell, hogy adják. Ezzel biztosítjuk, hogy ha van még hely a táblában, akkor a beszúrást minden esetben meg lehessen csinálni. Tekintsük ezután a keresés, beszúrás és törlés pszeudokódjait a nyílt címzésű hasítótábla esetén

Törlésnél nem megfelelő a NIL beírás, helyette a rés foglaltságát TÖRÖLT-re kell állítani, mivel a NIL a későbbi kereséseket megzavarhatja. A kipróbálási sorozat végét jelzi ott, ahol annak valójában még nincs vége. Ennek az a következménye, hogy sok beszúrás és törlés után már szinte minden rés vagy foglalt, vagy törölt lesz, ami a keresés sebességét lerontja. Ilyenkor a teljes táblát a benne lévő kulcsokkal újra hasítjuk. A másik lehetőség, hogy a láncolt listás megoldást választjuk, ahol a törlések nem okoznak gondot. Most három gyakran alkalmazott módszer típust említünk meg a nyílt címzésű hasításra.

Lineáris kipróbálás

Ez a módszer a

hasító függvényt használja, ahol az lehet. A formula alapján látható, hogy egy alap hasító függvényből indul ki és a kipróbálási sorozat a számokkal módosítja a kipróbálási indexet, amely nem függ a kulcstól, tehát minden kulcsra azonos. (A kipróbálási sorozat csak a résen keresztül függ a kulcstól, az azonos résre képeződő kulcsok esetén azonos.) A hatás pedig az, hogy ha a vizsgált rés nem megfelelő, akkor tovább lépünk a magasabb indexek felé. A továbblépés ciklikus, azaz a tábla végére érve a másik végén folytatjuk a kipróbálást. A módszernek van egy kellemetlen mellékhatása, az elsődleges klaszterezés. Klaszternek nevezzük a kipróbálási sorozat mentén az egymást követő kitöltött rések összességét. Ezen halmaz elemeinek a száma a klaszter mérete. Nem szerencsés, ha a klaszerek mérete nagy, mert ez lelassítja a hasító tábla műveleteit. Egy példa:

A hasító tábla -szel jelölt elemei a foglaltak. A maximális klaszterméret 3, de van két egyelemű és egy kételemű klaszter is. Ha egy új kulcs a 0 indexű helyre kerülne, akkor a negyedik megvizsgált rés lenne csak megfelelő a tárolásra. Tegyük fel azonban, hogy egy új elem a 14-es résbe kerül, majd a következő a 12-esbe. Ez utóbbinak már egy 6 elemű klaszteren kell végigmennie, hogy megfelelő helyet találjon magának. A klaszterek összeolvadnak!

Négyzetes kipróbálás

A hasító függvény a négyzetes kipróbálás esetén

alakú. Az értékei itt is a . A értékeket úgy kell megválasztani, hogy a kipróbálási sorozat kiadja az összes rést. A kipróbálási sorozat itt is csak a réstől függ, holott az számnak permutációja van. A klaszterezés jelensége itt is fellép, de nem olyan súlyos, mint a lineáris esetben. Itt másodlagos klaszterezésről beszélünk, mivel a klaszter elemei nem egymás mellett, hanem a kipróbálási sorozat mentén helyezkednek el. Egy lehetőség például egy négyzetes kipróbálásra, ha a korrekció úgy alakul, hogy az értékekre a zérus, majd egy, azután három stb. értéket vesz fel, szabályát tekintve minden értéknél az addigi értékek összege lesz. Természetesen ez az eset nem minden táblaméret esetén megfelelő. Ha azonban a táblaméret 2-nek hatványa, akkor valóban kiadja az összes rést.

Dupla hasítás

A dupla hasítás a

hasító függvényt használja. Láthatóan minden réshez általában különböző sorozatot ad, azaz a kipróbálási sorozatok száma , ami arra ad reményt, hogy a módszer az előzőekhez képest jobb tulajdonságokkal bír. Mindenesetre a megválasztásakor arra kell ügyelni, hogy az mindig -hez relatív prímet szolgáltasson. Ellenkező esetben a kipróbálási sorozat csak a tábla elemeinek a -edrészét adná, ahol az és a szolgáltatott érték legnagyobb közös osztója. Ha 2-hatványa és páratlan értékeket ad, az megfelel a feltételeknek. Ugyancsak megfelelő, ha prímszám és mindig kisebb, mint , de pozitív. Legyen prím és legyen

Válasszuk az -et. A kulcsok legyenek négyjegyű számok. Az -es kulcsra , és , . A kipróbálási sorozat: 299, 600, 200, 501, 101,... . A 9999-es kulcsra , és , . A kipróbálási sorozat: 185, 385, 585, 84, 284,... .

4.3. Tétel. A nyílt címzésű hasító tábla időigénye

Ha a kitöltési arány, akkor a nyílt címzésű hasító táblában

és

4.1.4. Minimum és maximum keresése

Legyen most kulcs elhelyezve egy tömbben, a kulcsok legyenek egy rendezett halmaz elemei (bármelyik kettő legyen összehasonlítható). Feladatunk a legkisebb és a legnagyobb kulcs megkeresése. A legkisebb kulcs megkeresése lineáris idejű és összehasonlítást igényel.

A legnagyobb elemet már összehasonlítással is megtaláljuk ezt követően. Összesen ez összehasonlítást jelent. A két kulcs meghatározási ideje lineáris és az aszimptotika konstansa 2. Ezen a konstanson tudunk némiképpen javítani az alábbi módszer alkalmazásával.

Legyen az elemek száma páros. Először az első két elemet hasonlítjuk össze (ez 1 összehasonlítás), a kisebbet minimumként, a nagyobbat a maximumként tároljuk. Ezután már csak elempárokkal dolgozunk ( van). Összehasonlítjuk az elempár elemeit egymással (mindegyik 1 összehasonlítás), majd a kisebbet a minimummal, a nagyobbat a maximummal (további 2 összehasonlítás). Ha az addigi minimumot, vagy maximumot változtatni kell, akkor megtesszük. Összesen az összehasonlítások száma:

ami és ez kevesebb, mint 2n-3

Ha páratlan számú elem van, akkor további elempár van az elsőt követően és marad még egy egyedüli elem a legvégén. Ezt az utolsó elemet mind az addigi minimummal, mind a maximummal össze kell hasonlítani legrosszabb esetben. Az összehasonlítások száma ennek megfelelően:

Az aszimptotika konstansa 2-ről 3/2-re csökkent.

4.1.5. Kiválasztás lineáris idő alatt

4.4. Definíció. A kiválasztási probléma

Legyen adott egy halmaz ( különböző szám), és egy index . Meghatározandó az halmaz azon eleme, melyre nézve pontosan darab tőle kisebb elem van az halmazban.

Speciális esetben ha , akkor a minimumkeresési problémát kapjuk. Mivel a minimumkeresési probléma összehasonlítással megoldható és ennyi kell is, ezért a probléma lineáris idő alatt megoldható. Ha növekvő sorrendbe rendezéssel próbáljuk megoldani a problémát, akkor mint később látni fogjuk lépésben a probléma mindig megoldható. Nem szükséges azonban a rendezéshez folyamodni, mert a probléma rendezés nélkül is megoldható, ráadásul lineáris időben, amiről alább lesz szó.

4.5. Definíció. Medián

Mediánnak nevezzük az adatsor azon elemét, amely a rendezett sorban a középső helyet foglalja el. Ha páratlan számú elem van az adatsorban, akkor és így a medián indexe a rendezés után . Ha páros számú elem van az adatsorban, akkor , és ekkor két középső elem van a és a indexű a rendezés után. (Alsó medián, felső medián.)

Ha nem említjük, akkor az alsó mediánról beszélünk.

4.1. Példa. A 123, 234, 345, 444, 566, 777, 890 rendezett adatsorban a medián a 444, míg a 123, 234, 345, 444, 566, 777, 890, 975 sorban két medián van, a 444 (alsó medián) és az 566 (felső medián).

A lineáris idejű kiválasztási algoritmusnak szüksége lesz agy segédalgoritmusra, amely egy előre megadott számnak megfelelően az adatsort két részre osztja űgy, hogy az első részbe kerülnek azok az adatok, amelyek nem nagyobbak, a második részbe a nem kisebbek kerülnek.

Az előre adott értéket az résztömb elemei közül jelöljük ki.

4.2. Példa. Az algoritmus munkáját az alábbi tömbön szemléltetjük. Itt most .

A megoldás animációja:

A fontosabb lépések:

Az eljárás befejeztével a tömb indexű elemei nem nagyobbak, mint 5 a indexű elemek pedig nem kisebbek, mint 5.

4.6. Tétel. A KIVÁLASZT algoritmus időigénye

A KIVÁLASZT algoritmus lineáris idejű.

Bizonyítás. csoport alakult ki. Mindegyikben meghatároztuk a mediánt. Ezen mediánok mediánját is meghatározzuk. Az adatok között a mediánok mediánjánál nagyobb elemek számát meg tudjuk becsülni az alábbi meggondolással. Mivel a medián középen lévő elem, így az a mediánok mediánja, amely medián közül kerül ki. Ezen mediánok fele biztosan nagyobb, mint a mediánok mediánja, azaz legalább ilyen elem van (saját magát nem számítjuk bele). Minden ilyen medián csoportjában akkor legalább három elem nagyobb a medánok mediánjánál, kivéve az esetleg 5-nél kevesebb elemű utolsó csoportot, amit szintén elhagyunk. Ezek alapján legalább elem biztosan nagyobb, mint a mediánok mediánja. (Ugyanennyi adódik a kisebb elemek számára is.)

Az 11-es sorban a KIVÁLASZT algoritmus a fentiek szerint a felosztás másik részében legfeljebb elemmel dolgozhat.

A KIVÁLASZT algoritmus egyes lépéseinek az időigénye:

Az időigényeket összegezve érvényes: a

összefüggés. Legyen itt konstansa . Feltételezzük, hogy a megoldás egy bizonyos küszöbtől kezdve, és behelyettesítéssel ezt fogjuk bizonyítani.

Válasszuk -et úgy, hogy a zárójel nem negatív legyen. Ekkor .

Ha ezen felül , akkor a választás megfelelő a kiinduló feltételezésünk teljesüléséhez.

4.2. Rendezés

4.7. Definíció. A reláció

Valamely halmaz esetén a részhalmazt az halmazon értelmezett relációnak nevezzük. Azt mondjuk, hogy az halmaz és eleme a relációban van, ha . Röviden ezt így írjuk: .

4.3. Példa. Legyen , és a reláció a kisebb ,, ” jel. Az reláció azokat a számpárokat jelenti, amelyekre fennáll az összefüggés.

4.8. Definíció. A rendezési reláció

A relációt rendezési relációnak nevezzük az halmazon, ha

Például a valós számok közötti ,, ” reláció rendezési reláció.

Rendezésről olyan adattípus esetén beszélhetünk, amelyre értelmezve van egy rendezési reláció. Tekintsük a sorozatot és annak is vegyük a tömbös realizációját. A rendezés a sorozat elemeinek olyan felsorolását jelenti, amelyben az egymást követő elemek a megadott relációban vannak. A tárgyalást valós számokon (leginkább egészek) visszük végig és relációnak a kisebb, egyenlő relációt () tekintjük. ami nem csökkenti az általánosságot. A rendezés mind a mai időkig fontos informatikai probléma. Gyakran jelenik meg mint egy nagyobb probléma része. A rendezési algoritmusokkal kapcsolatban több szempont szerinti igény léphet föl. Ilyenek például az alábbiak:

Nem lehet kizárni a nem optimális algoritmusokat sem az alkalmazásokból, mert egy probléma megoldásában nem csak a rendezési algoritmus optimalitása az egyetlen szempont a problémamegoldás hatékonyságára. (Hiába gyors az algoritmus, ha az adatok nem a kívánt formában állnak rendelkezésre, és a konverzió lerontja a hatékonyságot.)

4.2.1. A beszúró rendezés

A beszúró rendezés alapelve nagyon egyszerű. A sorozat második elemétől kezdve (az első önmagában már rendezett) egyenként a kulcsokat a sorozat eleje felé haladva a megfelelő helyre mozgatjuk összehasonlítások révén. A sorozatnak a vizsgált kulcsot megelőző elemei mindig rendezettek az algoritmus során.

4.4. Példa. Az alábbi kulcsok esetén nyíl mutatja a mozgatandó kulcsot és a beszúrás helyét.

Egy másik példa animációként:

Feladat: Számítsuk ki, hogy a beszúró rendezésre a !

Feladat: Készítsük el a beszúró rendezésre a pszeudokódot, ha a kulcsok egy kétszeresen láncolt listával vannak megadva!

4.2.2. Az összefésülő rendezés

Az összefésülő rendezés alapelve az összefésülés műveletén alapszik, amely két rendezett tömbből egy új rendezett tömböt állít elő. Az összefésülés folyamata: Mindkét tömbnek megvizsgáljuk az első elemét. A két elem közül a kisebbiket beírjuk az eredménytömb első szabad eleme helyére. A felszabaduló helyre újabb elemet veszünk abból a tömbből, ahonnan előzőleg a kisebbik elem jött. Ezt a tevékenységet folytatjuk mindaddig, míg valamelyik kiinduló tömbünk ki nem ürül. Ezután a még vizsgálat alatt lévő elemet, valamint a megmaradt másik tömb további elemeit sorba az eredménytömbhöz hozzáírjuk a végén. Az eredménytömb nem lehet azonos egyik bemeneti tömbbel sem, vagyis az eljárás nem helyben végzi az összefésülést.

Legyen ÖSSZEFÉSÜL (A, p, q, r) az az eljárás, amely összefésüli az és az résztömböket, majd az eredményt az eredeti helyre másolja vissza. Az eljárás lineáris méretű további segédmemóriát igényel. Az összefésülés időigénye , ha összesen elemünk van. (Egy menetben elvégezhető és az kell is hozzá.)

4.9. Definíció. Az oszd meg és uralkodj elv

Az oszd meg és uralkodj elv egy algoritmus tervezési stratégia A problémát olyan kisebb méretű, azonos részproblémákra osztjuk föl, amelyek rekurzívan megoldhatók. Ezután egyesítjük a megoldásokat.

Az összefésülő rendezés oszd meg és uralkodj típusú algoritmus, melynek az egyes fázisai:

A teljes tömb rendezését megoldó utasítás: ÖSSZEFÉSÜLŐ_RENDEZÉS(A,1,hossz[A]).

Az összefésülő rendezés időigénye

Az algoritmus időigénye megkapható a mester tétel 2. pontja alapján: .

4.2.3. A Batcher-féle páros-páratlan összefésülés

Az eljárás csak az összefésülést teszi hatékonyabbá. Nem önálló rendező módszer. Nagy előnye, hogy párhuzamosíthatók a lépései. Legyen két rendezett sorozatunk, az n elemű A sorozat és az m elemű B sorozat.

A két sorozat összefésülése adja a sorozatot. Az összefésülés módja a következő: Mindkét kiinduló sorozatból kettőt képezünk, a páratlan indexű és a páros indexű elemek sorozatait:

Összefésüljük az sorozatokat, eredménye az sorozat.

Összefésüljük az sorozatokat, eredménye a sorozat.

Összefésüljük az és sorozatokat, eredmény a sorozat.

4.10. Tétel. A Batcher-féle összefésülés tétele

A Batcher összefésülés során

és

ahol .

Bizonyítás. Fogadjuk el kiindulásként igaznak azt a feltevést, hogy elejéből páros számú elemet véve azok között azonos számú és elem van. Ekkor

és

Ebből viszont

ahonnan miatt adódik a tétel állítása.

A feltételezésünk bizonyítása:

Legyen

Ezek közül -ba kerül elem az -ból (az páratlan indexű elemei) és elem a -ből (a páros indexű elemei), valamint -be kerül elem az -ból (az páros indexű elemei) és elem a -ből (a páratlan indexű elemei). Innen az -beliek száma

és a -beliek száma

4.2.4. Gyorsrendezés (oszd meg és uralkodj típusú algoritmus)

A gyorsrendezés időigénye:

A legrosszabb eset: a felosztás minden lépésben elemű

Innen

A legjobb eset: a felosztás, ekkor

Ez megegyezik az összefésülő módszer formulájával, tehát

Megjegyzés: ha a felosztás aránya állandó pl. akkor a rekurziós formula:

Bizonyíthatö, hogy ekkor is

Ezen túlmenően az átlagos értékre is adódik.

4.2.5. A buborékrendezés

A buborékrendezésnél az egymás mellett álló elemeket hasonlítjuk össze, és szükség esetén sorrendjüket felcseréljük. Ezt mindaddig folytatjuk, míg szükség van cserére.

Időigény a legrosszabb esetben: .

Az algoritmusra jellező a sok csere, az elem lassan kerül a helyére.

4.2.6. A Shell rendezés (rendezés fogyó növekménnyel)

A Shell rendezés a buborékrendezésnél tapasztalt lassú helyrekerülést igyekszik felgyorsítani azáltal, hogy egymástól távol álló elemeket hasonlít és cserél fel. A távolságot (itt növekménynek nevezik) fokozatosan csökkenti, míg az 1 nem lesz. Minden növekmény esetén beszúrásos rendezést végez az adott növekménynek megfelelő távolságra álló elemekre. Mire a növekmény 1 lesz, sok elem már majdnem a helyére kerül.

A növekmények felépítése. Használjunk számú növekményt. Legyenek ezek .

A követelmény: , és .

A szakirodalomban javasolt növekményadatok:

Megjegyzés: A hossz[A] a rendezendő elemek számát jelöli.

Időigény: alkalmas növekmény választással leszorítható -re.

4.2.7. A minimum kiválasztásos rendezés

Ebben a rendezésben -szer végigmegyünk a tömbön. Minden alkalommal eggyel magasabb indexű elemtől indulunk. Megkeressük a minimális elemet, és azt az aktuális menet kezdő elemével felcseréljük.

Időigény: összehasonlításszám .

4.2.8. Négyzetes rendezés

Felosztjuk az elemű tömböt (közel) számú részre (alcsoportra). Mindegyikben (közel) elemet helyezünk el, majd mindegyikből kiemeljük (eltávolítjuk) a legkisebbet. A kiemeltekből egy főcsoportot képzünk. Kiválasztjuk a főcsoport legkisebb elemét és azt az eredménytömbbe írjuk, a főcsoportból pedig eltávolítjuk (töröljük). Helyére abból az alcsoportból ahonnan ő származott újabb legkisebbiket emelünk be a főcsoportba. Az eljárást folytatjuk, míg az elemek el nem fogynak a főcsoportból.

Időigény: összehasonlításszám .

Továbbfejlesztett változat, amikor számú elem van egy fő-főcsoportban és számú főcsoport van, mindegyikben számú elemmel, melyek mindegyikéhez egy elemszámú alcsoport tartozik. A rendezés elve az előző algoritmuséhoz hasonló.

Időigény:

4.2.9. A Stirling formula és az Alsó korlát összehasonlító rendezésre tétel

4.11. Tétel. A Stirling formula

Igaz az alábbi összefüggés az n!-ra:

Bizonyítás. Az egyenlőtlenséget a logaritmusra látjuk be. A logaritmus függvény konkáv és emiatt írható:

Az összehasonlító módszerek döntési fája

4.12. Tétel. Alsó korlát összehasonlító rendezésre

Bármely elemet rendező döntési fa magassága

Bizonyítás. Egy magasságú döntési fa leveleinek száma legfeljebb . Mivel minden permutációt rendezni kell tudnia az algoritmusnak, és összesen permutáció lehetséges, ezért a döntései fának legalább levele kell legyen.

Tehát fennáll. Logaritmálva: . A Stirling formula szerint . Behelyettesítve: .

Tehát:

4.2.10. Lineáris idejű rendezők: A leszámláló rendezés

A lineáris idejű rendezők nem használják az összehasonlítást.

A leszámláló rendezés ( = binsort, ládarendezés) bemenete 1 és k közötti egész szám.

Időigény: . Ha , akkor a rendezési idő is , ahol .

Az elemeket az tömbben helyezzük el. Szükség van további két tömbre: az eredményt tárolja majd, segédtömb.

A rendezés lényege, hogy A minden elemére meghatározza a nála kisebb elemek számát. Ez alapján tudja az elemet a kimeneti tömb megfelelő helyére tenni. Stabil eljárás: az azonos értékűek sorrendje megegyezik az eredetivel

4.2.11. A számjegyes rendezés (radix rendezés)

Azonos hosszúságú szavak, stringek rendezésére használhatjuk. (Dátumok, számjegyekből álló számok, kártyák, stb.) Legyen a szó hossza, pedig az egy karakteren, mezőben előforduló lehetséges jegyek, jelek száma, pedig az adatok száma.

Időigény:

4.2.12. Edényrendezés

Feltételezzük, hogy a bemenet a intervallumon egyenletes eloszlású számok sorozata. Felosztjuk a intervallumot egyenlő részre (edények). A bemenetet szétosztjuk az edények között, minden edényben egy listát kezelve. Az azonos edénybe esőket beszúrásos módon rendezzük. A végén a listákat egybefűzzük az elsővel kezdve.

Várható időigény:

4.2.13. Külső tárak rendezése

Külső tárak rendezésénél az elérési és a mozgatási idő szerepe drasztikusan megnő. Az összefésüléses módszerek jönnek elsősorban számításba.

4.13. Definíció. A k hosszúságú futam file-ban

Egy file szomszédos rekordjából álló részét k hosszúságú futamnak nevezzük, ha benne a rekordkulcsok rendezettek (pl.: növekedő sorrendűek).

Először alkalmas -val ( mindig megfelel) a rendezendő file-t két másik file-ba átmásoljuk úgy, hogy ott hosszúságú futamok jöjjenek létre. Ezután a két file-t összefésüljük egy-egy elemet véve mindkét file-ból. Az eredményfile-ban már lesz a futamhossz.(esetleg a legutolsó rövidebb lehet). Ezt ismételgetjük a teljes rendezettségig mindig duplázva értékét. Legyen a rekordok száma . Egy menetben rekordmozgás van a szétdobásnál és az összefésülésnél. A menetek száma legfeljebb .

Az időigény: .

Külső tárak rendezésének gyorsítása

Az nem javítható az összehasonlítások miatt. A szorzó konstansokat lehet csökkenteni.

4.3. Feladatok

  1. Készítsük el a buborék rendezés pszeudokódját arra az esetre, amikor a kulcsok (rekordok) egy kétszeresen láncolt listában helyezkednek el! Az eredeti listán kívül csak konstans mennyiségű további memóriát használjunk!

  2. Készítsük el az összefésülő rendezés pszeudokódját arra az esetre, amikor a kulcsok (rekordok) egy kétszeresen láncolt listában helyezkednek el! Az eredeti listán kívül csak konstans mennyiségű további memóriát használjunk!

  3. Készítsük el a négyzetes rendezés pszeudokódját arra az esetre, amikor a kulcsok (rekordok) egy kétszeresen láncolt listában helyezkednek el! Az eredeti listán kívül csak konstans mennyiségű további memóriát használjunk!

5. fejezet - Fák

5.1. Gráfelméleti fogalmak, jelölések

5.1. Definíció. Legyen egy véges halmaz, pedig -beli rendezetlen elempárok véges rendszere. Ekkor a párt gráfnak nevezzük.

Vezessük be a következő jelöléseket egy gráf esetében:

  • (csúcsok száma)

  • (élek elemszáma)

Egy gráf nagyon sok probléma szemléltetésére szolgálhat, a legegyszerűbb például az úthálózat, telefonhálózat, de akár házassági problémát is ábrázolhatunk vele.

A gráfokat többféle szempontból is szokás csoportosítani. A legjelentősebb szempont az irányítottság.

5.2. Definíció. A rendezett párt irányított gráfnak (digráfnak) nevezzük. A rendezett pár elemeire tett kikötések:

véges halmaz, a -beli csúcsok halmaza.

bináris reláció a halmazon, az élek halmaza.

={ rendezett pár | } . Hurkok megengedettek.

Hurok az él.

5.3. Definíció. A rendezett párt irányítatlan gráfnak nevezzük. A rendezett pár elemeire tett kikötések:

véges halmaz, a -beli csúcsok halmaza.

bináris reláció a halmazon, az élek halmaza.

={ rendezetlen pár | } . Hurok nem megengedett.

Mint ahogy már fentebb utaltunk rá, a csúcsok közötti kapcsolat sokszor jelentheti út létezéset vagy kommunikáció lehetőséget. Ilyenkor gyakran költségek vagy súlyok tartoznak az élekhez, amelyek az út esetében időt vagy akar pénzt is jelenthetnek (gondoljunk csak az autópályákra, amelyek használatáért fizetni kell).

5.4. Definíció. Az a gráf (irányított vagy irányítatlan), amelynek minden éléhez egy számot (súlyt) rendelünk hozzá, hálózatnak (súlyozott gráfnak) nevezzük.

5.5. Megjegyzés. A súlyt rendszerint egy súlyfüggvény segítségével adunk meg: , egy él súlya .

Az ilyen gráfok sok helyen előfordulnak, például optimalizálási feladatokban, mint az utazó ügynök probléma. Az élhez rendelt érték lehet az él költsége, súlya vagy hossza az alkalmazástól függően.

5.6. Definíció. A gráf egymáshoz csatlakozó éleinek olyan sorozatát, amely egyetlen ponton sem megy át egynél többször, útnak nevezzük.

5.7. Definíció. Legyen adott egy irányított vagy irányítatlan gráf a élsúlyokkal. A gráf egy -ból -be menő útjának hossza az úton szereplő élek súlyának összege.

5.1.1. Gráfok ábrázolási módjai

Két módszert szokás használni egy gráf ábrázolására: az egyikben szomszédsági listákkal, a másikban szomszédsági mátrixszal adjuk meg a gráfot.

Rendszerint a szomszédsági listákon alapuló ábrázolást választják, mert ezzel ritka gráfok tömören ábrázolhatók.

5.8. Definíció. Egy gráfot ritkának nevezünk, ha sokkal kisebb, mint .

Ugyanakkor a csúcsmátrixos ábrázolás előnyösebb lehet sűrű gráfok esetén, vagy ha gyorsan kell eldönteni, hogy két csúcsot összeköt-e él.

5.9. Definíció. Egy gráfot sűrűnek nevezünk, ha megközelíti -et.

Szomszédsági listás

szomszédsági listás ábrázolása során egy tömböt használunk. Ez |V| darab listából áll, és az tömbben minden csúcshoz egy lista tartozik. Minden csúcs esetén az szomszédsági lista tartalmazza az összes olyan csúcsot, amelyre létezik él. Azaz: elemei az csúcs -beli szomszédjai. (Sokszor nem csúcsokat, hanem megfelelő mutatókat tartalmaz a lista.) A szomszédsági listákban a csúcsok sorrendje rendszerint tetszőleges.

Ha irányított gráf, akkor a szomszédsági listák hosszainak összege , hiszen egy élt úgy ábrázolunk, hogy -t felvesszük az listába. Ha irányítatlan gráf, akkor az összeg , mert irányítatlan él ábrázolása során -t betesszük szomszédsági listájába, és fordítva. Akár irányított, akár irányítatlan a gráf, a szomszédsági listás ábrázolás azzal a kedvező tulajdonsággal rendelkezik, hogy az ábrázoláshoz szükséges tárterület .

A szomszédsági listákat könnyen módosíthatjuk úgy, hogy azokkal súlyozott gráfokat ábrázolhassunk. Például, legyen súlyozott gráf súlyfüggvénnyel. Ekkor az él súlyát egyszerűen a csúcs mellett tároljuk szomszédsági listájában. A szomszédsági listás ábrázolás könnyen alkalmassá tehető sok gráfváltozat reprezentálására.

A szomszédsági listás ábrázolás hátránya, hogy nehéz eldönteni szerepel-e egy él a gráfban, hiszen ehhez az szomszédsági listában kell -t keresni. Ez a hátrány kiküszöbölhető csúcsmátrix használatval, ez azonban aszimptotikusan növeli a szükséges tárterület méretét.

Szomszédsági mátrixos

Ha egy gráfot szomszédsági mátrixszal (vagy más néven csúcsmátrixszal) ábrázolunk, feltesszük, hogy a csúcsokat tetszőleges módon megszámozzuk az 1,2, ... , értékekkel. A ábrázolásáhz használt csúcsmátrix mérete , és

A csúcsmátrix tárterültetet foglal el, függetlenül a gráf éleinek számától. Gyakran kifizetődő a csúcsmátrixból csak a főátlóban és az efölött szereplő elemeket tárolni, ezzel majdnem felére csökkenthetjük az ábrázoláshoz szükséges tárterület méretét.

A szomszédsági listás ábrázoláshoz hasonlóan csúcsmátrixokkal is reprezentálhatunk súlyozott gráfokat. Ha súlyozott gráf súlyfüggvénnyel, akkor az él súlyát a csúcsmátrix sorában és oszlopában tároljuk. Nem létező él esetén a mátrix megfelelő elemét nil-nek választjuk, noha sokszor célszerű ehelyett 0 vagy végtelen értéket használni.

A szomszédsági listák együttesen aszimptotikusan kevesebb tárterületet igényelnek, mint a csúcsmátrix, azonban a használat során hatékonyságban ugyanennyivel elmaradnak attól, így ha a gráf mérete nem túl nagy, akkor kedvezőbb a hatékonyabb és egyszerűbb csúcsmátrixos ábrázolást használni. Ha a gráf nem súlyozott, akkor a csúcsmátrixos ábrázolás tovább javítható. Ebben az esetben a mátrix elemei lehetnek bitek, így jelentősen csökkenthetjük a szükséges tárterület méretét.

5.2. Bináris kereső fák

5.10. Definíció. A bináris kereső fa

A bináris kereső fa egy bináris fa, amely rendelkezik az alábbi bináris kereső fa tulajdonsággal:

Legyen a bináris kereső fa tetszőleges csúcsa.

Ha az baloldali részfájában van, akkor .

Ha az jobboldali részfájában van, akkor .

A jellemző műveletek bináris kereső fában:

KERES, MINIMUM, MAXIMUM, ELŐZŐ, KÖVETKEZŐ,BESZÚR, TÖRÖL.

A műveletek általában a fa magasságával függenek össze, amely lehet , de lehet is (ahol a kulcsok száma a fában).

5.3. Bináris kereső fa inorder bejárása

INORDER_FA_BEJÁRÁS( gyökér[T] ) bejárja az egész fát.

Az inorder bejárással növekvő sorrendben tudjuk a kulcsokat kiiratni. Preorder bejárás esetén kulcskiírás a részfák előtt, postorder bejárás esetén a részfák után történik.

5.4. Bináris kereső fa műveletek

5.5. Piros-fekete fák

5.11. Definíció. A piros-fekete fa

A piros-fekete fa olyan bináris keresőfa, melynek minden csúcsa egy extra bit információt tartalmaz (a csúcs színét, amely piros, vagy fekete) és rendelkezik az alábbi Piros-fekete fa tulajdonságokkal:

Minden csúcs színe piros, vagy fekete.

A gyökér színe fekete.

Minden levél (NIL) színe fekete, a levél nem tartalmaz kulcsot.

Minden piros csúcsnak mindkét fia fekete.

Bármely két, azonos csúcsból induló, levélig vezető úton ugyanannyi fekete csúcs van.

5.1. Példa.

5.12. Definíció. A piros-fekete fa fekete magassága

Egy piros-fekete fában egy csúcs fekete magasságának nevezzük az csúcsból kiinduló, levélig vezető úton található, x-et nem tartalmazó fekete csúcsok számát.

A fa fekete magasság a gyökércsúcs fekete magassága.

5.13. Tétel.

Bármely belső csúcsot tartalmazó piros-fekete fa magassága legfeljebb

MŰVELETEK:

A bináris kereső fák műveletei piros-fekete fában idő alatt elvégezhetők. Műveletek: BALRA_FORGAT , JOBBRA_FORGAT , PF_FÁBA_BESZÚR , PF_FÁBÓL_TÖRÖL .

5.2. Példa. A forgatások hatását az alábbi ábrával szemléltetjük.

A műveletek közül most csak a beszúrást írjuk le részletesebben.

5.5.1. Beszúrás

  1. Megkeressük az új elem helyét és oda piros színnel beszúrjuk.

  2. Csak a 3. Piros-fekete tulajdonság sérülhet abban az esetben, ha a beszúrt elem szülője piros. A cél, hogy az ilyen csúcsot feljebb és feljebb vigyük a fában úgy, hogy a többi tulajdonság ne sérüljön. Ha nem tudunk már feljebb menni, akkor forgatunk. (Feltehetjük, hogy a gyökér színe mindig fekete.)

  3. Jelölések: a vizsgált piros csúcs, az piros szülője ( szülője biztosan fekete) az testvére (-nek nagybácsija). Hat eset adódik, amely a szimmetria ( bal- vagy jobbgyerek) miatt 3-ra redukálódik:

    • [(a)] piros esetén és feketére szülő pirosra változtatása után a problémás csúcs már csak a szülő lehet, ez lesz az új vizsgálandó csúcs.

    • [(b)] fekete és -nak baloldali gyereke esetén jobbra forgatást és színcseréket végzünk: feketére, volt szülője pirosra vált.

    • [(c)] fekete és -nak jobboldali gyereke esetén olyan helyzetet állítunk elő, hogy -nak baloldali gyereke legyen balra forgatással ( és szerepcsere). Ezután a (b) eset áll elő.

5.6. AVL-fák

Az AVL-fákat G.M. Adelszon-Velszkij, E.M. Landisz vezették be 1962-ben.

5.14. Definíció. AVL-fa

Egy bináris keresőfát AVL-fának nevezünk, ha a fa minden csúcsára teljesül az alábbi úgynevezett AVL tulajdonság: (kiegyensúlyozottsági feltétel).

az csúcs baloldali, a jobboldali részfáját jelöli, pedig a részfa magassága.

Jelölje a fa szintjeinek számát. (Ez eggyel nagyobb, mint a magasság). Jelölje a szintű fa csúcsainak minimális számát. Ekkor minden k 2 esetén teljesül, hogyb

5.15. Tétel.

, ahol a -dik Fibonacci szám.

Bizonyítás. és esetén a tétel nyílvánvalóan igaz.

Teljes indukcióval -re kapjuk:

5.16. Következmény.

Egy csúcsot tartalmazó AVL-fa szintjeinek számára fennáll a

egyenlőtlenség, azaz a szintszám és így a magasság is nagyságú.

Bizonyítás. A tétel alapján , azaz . A Fibonacci számokra igaz, hogy , ahol . Tehát . Innen logaritmust véve .

5.17. Tétel.

Egy csúcsból álló AVL-fa esetén egy új csúcs beszúrását követően legfeljebb egy (esetleg dupla) forgatással az AVL tulajdonság helyreállítható. A beszúrás költsége ezzel együtt .

Törlés után legfeljebb (szimpla vagy dupla) forgatás helyreállítja az AVL tulajdonságot.

5.7. 2-3-fák

5.18. Definíció. 2-3-fa

A 2-3-fa egy gyökeres fa az alábbi tulajdonságokkal:

A rekordok a fa leveleiben helyezkednek el, a kulcs értéke szerint balról jobbra növekvő sorrendben. Egy levél egy rekordot tartalmaz.

Minden belső (nem levél) csúcsnak 2 vagy három gyereke van. A csúcs szerkezete: , vagy ahol (. Az mutató szerinti részfában minden kulcs kisebb, mint , az mutató szerinti részfa legkisebb kulcsa , és minden kulcs ott kisebb, mint (ha van a csúcsban), az mutató (ha van) szerinti részfában a legkisebbkulcs .

A fa levelei a gyökértől egyforma távolságra vannak.

5.19. Tétel.

Ha a 2-3-fának szintje van, akkor a levelek száma legalább .

Fordítva: ha a tárolt rekordok száma , akkor

Keresés 2-3-fában: A gyökértől elindulva a belső csúcsokban 1 vagy 2 összehasonlítás után tovább lehet menni egy szinttel lejjebb. A műveletigény .

5.8. B-fák

5.20. Definíció. A B-fa egy olyan gyökeres fa, amely rendelkezik a következő

tulajdonságokkal:

Minden csúcsnak a következő mezői vannak:

Az az csúcsban tárolt kulcsok darabszáma. Az darab kulcs (nemcsökkenő sorrendben) . A egy logikai változó, melynek az értéke , ha levél, és , ha egy belső csúcs.

Ha belső csúcs, akkor tartalmazza a mutatókat, melyek az gyerekeire mutatnak. A levél csúcsoknak nincsenek gyerekei és így e mezők definiálatlanok.

A értékek meghatározzák a kulcsértékek azon tartományait, amelyekbe a részfák kulcsai esnek. Ha ki egy olyan kulcs, amelyik a gyökerű részfában van, akkor .

Minden levélnek azonos a mélysége, ez az érték a fa magassága

A csúcsokban található kulcsok darabszámára adott egy alsó és egy felső korlát. Ezeket a korlátokat egy rögzített egész számmal () lehet kifejezni, és ezt a számot a B-fa minimális fokszámának nevezzük.A. Ezért minden nem gyökér csúcsnak legalább kulcsa van. Minden belső csúcsnak legalább gyereke van. Ha a fa nem üres, akkor a gyökércsúcsnak legalább egy kulcsának kell lennie. Minden csúcsnak legfeljebb kulcsa lehet. Tehát egy belső csúcsnak legfeljebb gyereke lehet. Azt mondjuk, hogy egy csúcs telített, ha pontosan kulcsa van.

Ha , akkor a B-fa neve 2-3-4 fa.

5.21. Tétel. Ha , és T egy olyan -kulcsos B-fa, amelynek magassága és minimális fokszáma , akkor

5.9. Feladatok

  1. Üres piros-fekete fába szigorúan monoton növekedő kulcsok sorozatát szúrjuk be egymás után. Hány kulcs kerül összesen beszúrásra, mire a második forgatás megtörténik (a forgatást előidéző kulcsot is beszámítjuk)? Mennyi lesz ekkor a gyökér fekete magassága?

  2. A 250, 265, 270, 260, 150 kulcsokat a megadott sorrendben szúrjuk be bináris kereső fába üres fából kiindulva! Ezután járjuk be a fát a rekurzív inorder bejárási algoritmussal a gyökérből indulva. A bejárás során alkalmazott művelet a kulcs kiírása. Mi lesz a harmadik kiírt kulcs? Hányszor hívja meg az algoritmus saját magát?

  3. Bináris keresőfába szúrjuk be az alábbi kulcsokat a felsorolásuk sorrendjében üres fával indulva, majd töröljük a gyökérelemet! 500, 250, 800, 700, 120, 300, 750, 900, 850, 780, 230, 210, 240. Melyik kulcs lett az új gyökér és hány mutatót kellett megváltoztatni a törlés során? Hány kulcs-összehasonlítás volt a fa feltöltése során?

6. fejezet - Gráfelméleti algoritmusok

6.1. A szélességi keresés

  1. éleit vizsgálja és rátalál minden -ből elérhető csúcsra.

  2. Kiszámítja az elérhető csúcsok legrövidebb (legkevesebb élből álló) távolságát -től.

  3. Létrehoz egy gyökerű ,,szélességi fát”, amelyben az -ből elérhető csúcsok vannak.

  4. A csúcsoknak szint tulajdonít (fehér, szürke, fekete). Kezdetben minden csúcs fehér, kivéve -et, amely szürke. Szürke lesz egy csúcs, ha elértük és fekete, ha megvizsgáltuk az összes belőle kiinduló élt.

  5. A szélességi fa kezdetben az csúcsból áll. Ez a gyökér.

  6. Ha egy fehér csúcshoz értünk az csúcsból, akkor azt felvesszük a fába éllel és lesz a szülője.

Attributumok

: az csúcs színe

: az csúcs elődje

táv : az távolsága -től

: a szürke csúcsok sora

6.1. Definíció. jelölje a legrövidebb úthosszat -ből -be, ha létezik út -ből -be, egyébként (s,v) legyen .

6.2. Lemma. Legyen digráf vagy gráf és tetszőleges csúcs. Ekkor bármely él esetén .

6.3. Lemma. Legyen gráf és tegyük fel, hogy a szélességi keresés algoritmust alkalmaztuk egy kezdőcsúccsal. Ekkor a szélességi keresés által kiszámított táv értékek minden csúcsra kielégítik a táv[v] egyenlőtlenséget.

6.4. Lemma. Tegyük fel, hogy a szélességi keresést alkalmaztuk a gráfra és a futás során a sor a csúcsokat tartalmazza. ( az első, az utolsó). Ekkor táv táv és táv táv bármely értékre.

6.5. Tétel. Legyen gráf és tegyük fel, hogy a szélességi keresés algoritmust alkalmaztuk egy kezdőcsúccsal. Ekkor a szélességi keresés minden -ből elérhető csúcsot elér és befejezéskor táv , . Továbbá bármely -ből elérhető csúcsra az -ből -be vezető legrövidebb utak egyikét megkapjuk, ha az -ből -be vezető legrövidebb utat kiegészítjük a () éllel.

6.6. Definíció. fát előd részfának nevezzük, ha

és

6.7. Definíció. A előd részfa szélességi fa, ha elemei az -ből elérhető csúcsok és bármely csúcsra egyetlen egyszerű út vezet -ből -be -ben

6.8. Lemma. A szélességi keresés olyan értékeket határoz meg, amelyekre a előd részfa egy szélességi fa.

Eljárás az -ből -be vezető legrövidebb út csúcsai kiírására:

6.2. A mélységi keresés

  1. éleit vizsgálja, mindig az utoljára elért, új kivezető élekkel rendelkező csúcsból kivezető, még nem vizsgált éleket deríti fel. Az összes ilyen él megvizsgálása után visszalép és azon csúcs éleit vizsgálja, amelyből -t elértük.

  2. Az összes csúcsot megvizsgálja.

  3. Létrehoz egy ,,mélységi erdőt”, amely az előd részgráf fáiból áll.

  4. A csúcsoknak szint tulajdonít (fehér, szürke, fekete). Kezdetben minden csúcs fehér, szürke lesz, mikor elértük, és fekete, mikor elhagytuk.

  5. Minden csúcshoz két időpontot rendel, az elérési és az elhagyási időpontot .

6.9. Definíció. A gráfot előd részgráfnak nevezzük, ha

6.10. Tétel. [Zárójelezés tétele]

Mélységi keresést alkalmazva egy (irányított, vagy iráyítatlan) gráfra a következő 3 feltétel közül pontosan 1 teljesül bármely és csúcsra:

a és a intervallumok diszjunktak,

a intervallum tartalmazza a intervallumot, és az csúcs a csúcs leszármazottja a mélységi fában,

a intervallum tartalmazza a intervallumot, és a csúcs az csúcs leszármazottja a mélységi fában.

6.11. Következmény. [Leszármazottak intervallumainak beágyazása]

A csúcs akkor és csak akkor leszármazottja az csúcsnak az irányított, vagy irányítatlan gráf mélységi erdejében, ha .

6.12. Tétel. [Fehér út tétele]

Egy gráfhoz tartozó mélységi erdőben a csúcs akkor és csak akkor leszármazottja az csúcsnak, ha elérésekor a időpontban a csúcs elérhető -ból olyan úton, amely csak fehér csúcsokat tartalmaz.

A mélységi keresés révén a mélységi kereséstől függően a bemeneti gráf éleit osztályozhatjuk. Éltípusok: egy él

  1. Fa él, ha a mélységi erdő éle.

  2. Visszamutató él, ha megelőzője -nak egy mélységi fában.

  3. Előre mutató él, ha leszármazottja -nak egy mélységi fában.

  4. Kereszt él, ha a fenti három osztályba nem sorolható be

Irányított gráf akkor és csak akkor körmentes, ha a mélységi keresés során nem találtunk visszamutató éleket.

6.13. Tétel. Egy irányítatlan gráf mélységi keresésekor bármely él vagy fa él, vagy visszamutató él.

Egy irányított gráf topologikus rendezése a csúcsainak sorba rendezése úgy, hogy ha -ben szerepel az él, akkor előzze meg -t a sorban

6.14. Tétel. A TOPOLOGIKUS_RENDEZÉS() egy írányított, körmentes gráf topologikus rendezését állítja elő.

6.3. Minimális feszítőfa

6.15. Definíció. Egy irányítatlan gráf feszítőfája a gráfnak az a részgráfja, amely fagráf és tartalmazza a gráf összes cúcspontját.

6.16. Definíció. A fa súlya a

számérték.

6.17. Definíció. Minimális feszítőfáról beszélünk, ha értéke minimális az összes feszítőfára nézve. A minimális feszítőfa nem feltétlenül egyértelmű.

6.18. Definíció. Legyen egy minimális feszítőfa egy része. -ra nézve biztonságos egy él, ha -hoz hozzávéve továbbra is valamely minimális feszítőfa része marad.

6.19. Definíció. Egy irányítatlan gráf vágása a kettéosztása egy és egy halmazra.

6.20. Definíció. Az él keresztezi az vágást, ha annak egyik végpontja -ben, másik végpontja -ben található.

6.21. Definíció. Egy vágás kikerüli az halmazt, ha az A egyetlen éle sem keresztezi a vágást.

6.22. Definíció. Egy él könnyű egy vágásban, ha a vágást keresztező élek közül neki van a legkisebb súlya.

6.23. Tétel. Legyen egy összefüggő, irányítatlan gráf súlyfüggvénnyel. Legyen egy olyan részhalmaza -nek, amelyik valamelyik minimális feszítőfájának is része. Legyen tetszőleges -t kikerülő vágása a -nek. Legyen könnyű él az vágásban. Ekkor az él biztonságos az -ra nézve.

6.24. Következmény. Legyen egy összefüggő, irányítatlan gráf gráf súlyfüggvénnyel. Legyen egy olyan részhalmaza -nek, amelyik valamelyik minimális feszítőfájának is része. Legyen egy összefüggő komponens a erdőben. Ha a -t és a valamely másik komponenesét összekötő könnyű él, akkor az él biztonságos az -ra nézve.

6.3.1. Kruskal-algoritmus

6.1. Példa.

Animációként:

6.3.2. Prim-algoritmus

6.2. Példa.

Animációként:

6.4. Legrövidebb utak

A csúcs legrövidebb út távolsága -től legyen , amelyet az -ből -be vezető egyes utak élszámáinak minimumaként definiálunk, ha van ilyen út, és , ha nem vezet út -ből -be.

6.25. Definíció. Egy hosszúságú -ből -be vezető utat és közötti legrövidebb útnak nevezzük.

6.26. Lemma. Legyen irányított vagy irányítatlan gráf és tetszőleges csúcs. Ekkor bármely élre:

Bizonyítás. Ha elérhető -ből, akkor is. Ebben az esetben, az -ből -be vezető legrövidebb út nem lehet hosszabb, mint ha az -ből -ba vezető legrövidebb utat kiegészítjük az éllel, így az egyenlőtlenség teljesül. Ha nem érhető el -ből, akkor , ezért az egyenlőtlenség biztosan igaz.

6.5. Adott csúcsból induló legrövidebb utak

Egy gépkocsivezető a lehető legrövidebb úton szeretne eljutni az egyik városból (A-ból) a másikba (B-be). Hogyan határozhatjuk meg ezt a legrövidebb utat, ha rendelkezünk az ország teljes autós térképével, amelyen minden, két szomszédos útkereszteződés közötti távolságot bejelöltek?

Egyik lehetséges megoldás az, ha módszeresen előállítjuk az összes, A-ból B-be vezető utat azok hosszával együtt, és kiválasztjuk a legrövidebbet. Könnyű azonban azt belátni, hogy még ha kört tartalmazó utakkal nem is foglalkozunk, akkor is több millió olyan lehetőség marad, amelyek többsége egyáltalán nem érdemel figyelmet. Például, egy C-n keresztül vezető A és B közötti út nyilvánvalóan szerencsétlen útvonalválasztás lenne, ha C túl hosszú kitérőt jelent.

A legrövidebb utak problémában adott egy élsúlyozott, irányított gráf, ahol a súlyfüggvény rendel az élekhez valós értékeket. A út súlya az utat alkotó súlyainak összege:

Definiáljuk az -ból -be vezető A legrövidebb út súlyát az alábbi módon:

Az csúcsból csúcsba vezető legrövidebb úton egy olyan utat értünk, amelyre teljesül.

Az A-ból B-be vezető utak példájában az autós térképet egy gráf segítségével modellezhetjük: a csúcsok jelentik a kereszteződéseket, az élek szimbolizálják a kereszteződések közötti útszakaszokat, az élek súlyai pedig az útszakaszok hosszaira utalnak. Célunk olyan legrövidebb útnak a megtalálása, amely A-ból adott indul ki, és B-be érkezik.

Az élsúlyok a távolságokétól eltérő metrikákat is kifejezhetnek. Gyakran használják idő, költség, büntetés, veszteség vagy más olyan mennyiség megjelenítésére, amely egy út mentén lineárisan halmozódik, és amelyet minimalizálni szeretnénk.

Fokozatos közelítés

Ennek a fejezetnek az algoritmusai a fokozatos közelítés módszerét alkalmazzák. Minden csúcsnál nyilvántartunk egy értéket, amely egy felső korlátot ad az kezdőcsúcsból a -be vezető legrövidebb út súlyára. A -t egy legrövidebb-út becslésnek nevezzük.

Kezdetben a legrövidebb-út becsléseket és a szülőkre mutató értékeket a következő futási idejű eljárás állítja be.

A kezdeti értékek beállítása után -re nil, és minden -re áll fenn.

Egy él segítségével történő közelítés technikáját alkalmazzák. Egy ellenőrzésből áll, amelyik összeveti a csúcshoz ez idáig legrövidebbnek talált utat az csúcson keresztül vezető úttal, és ha ez utóbbi rövidebb, akkor módosítja a és értékeket. A közelítő lépés csökkentheti a legrövidebb-út becslés értékét, és átállíthatja a mezőt az csúcsra. Az alábbi kód az él közelítő lépését írja le.

Ennek a fejezetnek mindegyik algoritmusa meghívja az Egy-forrás-kezdőérték eljárást, majd az élekkel egymás után végez közelítéseket. Sőt a közelítés az egyetlen olyan lépés, amely megváltoztatja a legrövidebb-út becsléseket és a szülő értékeket. A fejezet algoritmusai abban különböznek egymástól, hogy hányszor és milyen sorrendben végzik el az élekkel a Közelít műveletet. Dijkstra algoritmusa minden éllel pontosan egyszer közelít. A Bellman-Ford-algoritmus az egyes élekkel többször végez közelítést.

6.5.1. Bellman-Ford algoritmus

A Bellman-Ford-algoritmus az adott kezdőcsúcsból induló legrövidebb utak problémáját abban az általánosabb esetben oldja meg, amikor az élek között negatív súlyúakat is találhatunk. Adott egy súlyfüggvénnyel súlyozott irányított gráf, ahol a kezdőcsúcs . A Bellman-Ford-algoritmus egy logikai értéket ad vissza annak jelölésére, hogy van vagy nincs a kezdőcsúcsból elérhető negatív kör. Ha van ilyen kör, az algoritmus jelzi, hogy nem létezik megoldás. Ha nincs ilyen kör, akkor az algoritmus előállítja a legrövidebb utakat és azok súlyait.

A Bellman-Ford-algoritmus a fokozatos közelítés technikáját alkalmazza, bármelyik csúcsnál az kezdőcsúcsból odavezető legrövidebb út súlyára adott becslését ismételten csökkenti mindaddig, amíg az eléri annak tényleges értékét. Az algoritmus akkor és csak akkor tér vissza igaz értékkel, ha a gráf nem tartalmaz a kezdőcsúcsból elérhető negatív köröket.

A következő ábra a Bellman-Ford-algoritmus működését egy 5 csúcsból álló gráfon mutatja be. A és kezdeti beállítása után az algoritmus menetet végez a gráf éleivel. Minden menet a 2-4. sorok for ciklusának egy iterációja, amely a gráf minden élével egyszer végez közelítést. A (b)-(f) ábrák az algoritmus állapotait mutatják az élekkel végzett négy menet mindegyike után. menet után az 5-8. sorok negatív kört keresnek, és a megfelelő logikai értéket adják vissza.

A Bellman-Ford-algoritmus futási ideje , mivel az 1. sor előkészítése idejű, a 2-4. sorokban az élekkel végzett menet mindegyike ideig tart, és az 5-7. sorok for ciklusa idejű.

A kezdőcsúcs az csúcs. A értékeket beleírtuk a csúcsokba, és a vastagított élek jelzik a szülő értékeket: ha () él vastagított, akkor . (a) Az első menet előtti helyzet. (b)-(f) Az egymást követő menetek után kialakult helyzetek. Az (f) rész a végleges és értékeket mutatja. A Bellman-Ford-algoritmus ebben a példában igaz értékkel tér vissza.

6.27. Tétel. Bellman-Ford-algoritmus helyessége

Egy súlyozott, irányított gráfon futtassuk a Bellman-Ford eljárást, ahol a súlyfüggvény a , és a kezdőcsúcs az s. Ha nem tartalmaz -ből elérhető negatív köröket, akkor az algoritmus igaz értéket ad vissza, tovább minden csúcsra , és a szülő részgráf egy gyökerű legrövidebb-utak fa lesz. Ha -ben van egy -ből elérhető negatív kör, akkor az algoritmus hamis értékkel tér vissza.

6.5.2. Dijkstra algoritmusa

Dijkstra algoritmusa az adott kezdőcsúcsból induló legrövidebb utak problémáját egy élsúlyozott, irányított gráfban abban az esetben oldja meg, ha egyik élnek sem negatív a súlya. Ebben az alfejezetben ennek megfelelően feltesszük, hogy minden élre . A Dijkstra algoritmusának futási ideje, egy jó megvalósítás mellett, gyorsabb, mint a Bellman-Ford-algoritmusé.

A Dijkstra-algoritmus azoknak a csúcsoknak az halmazát tartja nyilván, amelyekhez már meghatározta az kezdőcsúcsból odavazető legrövidebb-út súlyát. Az algotimus minden lépésben a legkisebb legrövidebb-út becslésű csúcsot választja ki, beteszi az -t az -be, és minden -ból kivezető éllel egy-egy közelítést végez. Az alábbi megvalósításban egy minimum-elsőbbségi sort alkalmazunk a -beli csúcsok nyilvántartására, amelyeket azok táv értékeivel indexeltünk. Az algoritmus feltételezi, hogy a gráf egy szomszédsági listával van megadva.

A kezdőcsúcs a bal oldali csúcs. A legrövidebb-út becsléseket a csúcsok belsejében tüntettük fel, és vastagított élek jelzik a szülő csúcsokat: ha vastag, akkor . A sötétebb szürke színű csúcsok az S halmazban vannak, és a fehér színűek a prioritási sorban. (a) Ez a 4-8. sorok while ciklusának első iterációja előtti helyzet. A sötét színű csúcs a legkisebb értékű csúcs, és az 5. sor ezt választja ki csúcsként. (b)-(f) A while ciklus soron következő iterációi utáni helyzetek. Minden részben a sötétebb színnel jelölt csúcsot mint csúcsot választja ki a következő iteráció 5. sora. Az (f) rész a végleges táv és értékeket mutatja.

A Dijkstra-algoritmus az ábrán bemutatott módon végzi az élekkel a fokozatos közelítést. Az 1. sor a táv és a értékeinek szokásos kezdeti beállítását végzi, majd a 2. sor az halmazt teszi üressé. A 4-8. sorok while ciklusának minden iterációja előtt fennáll a invariáns állítás. A 3. sor a minimum-elsőbbségi sort készíti elő úgy, hogy az kezdetben minden -beli csúcsot tartalmazzon; mivel ekkor az még üres, az invariáns állítás a 3. sor után teljesül. A 4-8. sorok while ciklusában egy csúcsot veszünk ki az halmazból (legelőször ), és hozzáadjuk az halmazhoz, tehát az invariáns állítás továbbra is igaz marad. Az csúcs tehát a legkisebb legrövidebb-út becslésű csúcs a -ben. Ezután a 7-8. sorok közelítést végeznek az -ból kivezető élekkel, ezáltal módosítjuk a becslést és a szülőt, feltéve, hogy a -hez az -n keresztül most talált út rövidebb, mint az ott eddig nyilvántartott legrövidebb út. Figyelembe véve azt, hogy a 3. sor után már egyetlen csúcsot sem teszünk bele a -ba, valamint azt, hogy mindegyik csúcsot egyetlenegyszer veszünk ki a -ból és tesszük át az -be, a 4-8. sorok while ciklusa pontosan -szer hajtódik végre.

A Dijkstra-algoritmus mohó stratégiát alkalmaz, hiszen minden a ,,legkönnyebb”, a ,,legközelebbi” csúcsot választja ki a -ből, hogy azután betegye az halmazba. A mohó stratégiák általában nem mindig adnak optimális eredményt, de amint a következő tétel és annak következménye mutatja, a Dijkstra-algoritmus szükségszerűen a legrövidebb utakat állítja elő.

6.28. Tétel. Dijkstra-algoritmus helyessége

Ha Dijkstra algoritmusát egy nemnegatív súlyfüggvénnyel súlyozott, kezdőcsúcsú irányított gráfban futtatjuk, akkor annak a befejeződésekor minden csúcsra teljesül, hogy táv .

6.29. Következmény. Ha Dijkstra algoritmusát egy nemnegatív súlyfüggvénnyel súlyozott, irányított kezdőcsúcsú gráfban futtatjuk, akkor annak befejeződésekor a szülő részgráf egy gyökerű legrövidebb-utak fa lesz.

6.6. Legrövidebb utak minden csúcspárra

Ebben a fejezetben célunk egy gráf valamennyi rendezett csúcspárjára a két csúcs közti legrövidebb út megkeresése. Ha például egy autóstérképhez elkészítjük a városok egymástól mért távolságainak táblázatát, éppen ezt a feladatot oldjuk meg. Csakúgy, mint korábban egy súlyozott irányított gráfot jelöl, amelynek élhalmazán egy valós értékű súlyfüggvény van megadva. A gráf minden csúcspárjára keressük az -ból -be vezető legrövidebb (legkisebb súlyú) utat, ahol egy út súlya az úthoz tartozó élek súlyának az összege. Az eredményt általában táblázatos formában keressük; a táblázat -hoz tartozó sorában és -hez tartozó oszlopában álló elem az -ból -be vezető legrövidebb út hossza.

A csúcspárok közti legrövidebb utakat természetesen megkereshetjük úgy, hogy az előző fejezetben látott valamelyik egy kezdőcsúcsból kiinduló legrövidebb utakat kereső algoritmust egyenként végrehajtunk a lehetséges különböző gyökércsúcsot választva. Ha a távolságok nemnegatívak, Dijkstra algoritmusát alkalmazhatjuk.

Ha negatív élsúlyokat is megengedünk a gráfban, Dijkstra algortmusa nem alkalmazható, helyette a lassabb Bellman-Ford-algoritmust kell minden csúcsra egyszer végrehajtanunk. Célunk tehát, hogy a negatív élsúlyok esetére hatékonyabb algoritmusokat adjunk. Eközben megismerjük az összes csúcspár közti legrövidebb út probléma és a mátrixszorzás kapcsolatát is.

Az egy csúcsból kiinduló legrövidebb utakat megadó algoritmusok általában a gráf éllistás megadását igénylik. A bemenő adat tehát egy -es mátrix lesz. A mátrix egy csúcsú irányított gráf élsúlyait tartalmazza: , ahol

A gráfban megengedünk negatív súlyú éleket, azonban egyelőre feltesszük, hogy negatív összsúlyú körök nincsenek.

A fejezetbeli algoritmus kimenete az összes párra adott legrövidebb úthosszakat tartalmazó táblázat egy D -es mátrix lesz. A mátrix eleme az csúcsból a csúcsba vezető legrövidebb út súlyát tartalmazza. A végeredményként kapott értékek tehát megegyeznek a -vel, az csúcsból a csúcsba vezető legrövidebb út súlyával.

Csak akkor mondhatjuk, hogy a kitűzött feladatot megoldottuk, ha a legrövidebb utak súlya mellett magukat az utakat is meg tudjuk adni. E célból egy megelőzési mátrixot is meg kell adnunk, amelyben , ha vagy ha nem vezet és között út; ellenkező esetben a -t megelőző csúcs az egyik -ből -be vezető legrövidebb úton.

Mielőtt az algoritmust ismertetnénk, állapodjunk meg néhány, szomszédsági mátrixokkal kapcsolatos, jelölésben. Először is a gráfnak általában csúcsa lesz, azaz . Másodszor a mátrixokat nagybetűvel, egyes elemeiket pedig alulindexelt kisbetűvel fogjuk jelölni, tehát például és elemei lesznek. Bizonyos esetekben iterációk jelölésére a mátrixokat zárójelezett felsőindexszel látjuk el, úgy mint . Végül egy adott A -es mátrix esetén sorok-száma[A] tartalmazza értékét.

6.6.1. A Floyd-Warshall-algoritmus

A következőkben dinamikus programozási feladatként értelmezzük a legrövidebb utak keresését. Egy irányított gráfon a keletkező ún. Floyd-Warshall-algoritmus futási ideje . A bemenő gráfban megengedünk negatív élsúlyokat, negatív összsúlyú köröket azonban nem.

A legrövidebb utak szerkezete

Dinamikus programozásunk a legrövidebb utak ,,belső” csúcsait tekinti, ahol egy egyszerű út belső csúcsa minden -től és -től különböző csúcsa, azaz a halmaz minden eleme.

A szerkezet jellemzése a következő észrevételen alapul. Legyen a gráf csúcshalmaza , és tekintsük valamely -ra az részhalmazt. Legyen a legrövidebb -ből -be vezető olyan út, melynek belső csúcsait az részhalmazból választhatjuk. (A út egyszerű, hiszen nem tartalmaz negatív összsúlyú köröket.) A Floyd-Warshall-algoritmus a út és az olyan legrövidebb utak kapcsolatát alkalmazza, melynek belső csúcsait az részhalmazból választjuk. E kapcsolat két esetre osztható attól függően, hogy belső csúcsa-e -nek vagy sem:

  • Ha a útnak nem belső csúcsa, akkor a út minden belső csúcsa az halmaz eleme. Így a legrövidebb -ből -be vezető és belső csúcsként csak az halmaz elemeit használó út szintén legrövidebb út lesz, ha a belső csúcsok az halmazból kerülhetnek ki.

  • Ha belső csúcs a úton, akkor felbontjuk a utat két útra. A egy olyan legrövidebb út és között, melynek belső csúcsai az halmaz elemei. Sőt nem is lehet út belső csúcsa, így egyben olyan legrövidebb út is, melynek belső csúcsai -beliek. Hasonlóképpen egy legrövidebb, belső csúcsként csak -et használó -ból -be vezető út.

Az összes csúcspár közti legrövidebb utak rekurzív megadása

A fenti megfigyelés alapján egy rekurzióval adhatunk egyre javuló becsléseket a legrövidebb utak súlyára. Legyen a legrövidebb olyan -ből -be vezető út hossza, melynek minden belső csúcsa az halmaz eleme. A érték esetén egy olyan -ből -be vezető útnak, melyen a belső csúcsok sorszáma legfeljebb 0 lehet, egyáltalán nem lehet belső csúcsa. Egy ilyen útnak tehát legfeljebb egyetlen éle lehet és így . A további értékeket a következő rekurzió szolgáltatja:

A végeredményt a mátrix tartalmazza, hiszen az egyes legrövidebb utak belső csúcsai a halmaz elemei, és így minden esetén.

Az úthosszak kiszámítása alulról felfelé haladva

A 6.2 rekurzió segítségével a értékeket alulról felfelé, értéke szerinti növekvő sorrendben számíthatjuk. Az algoritmus bemenő adatai a 6.1 egyenlőség által definiált -es mátrix lesz, eredményül pedig a legrövidebb úthosszak mátrixát adja.

A Floyd-Warshall-algoritmus futási idejét a 3-6. sorok háromszorosan egymásba ágyazott FOR ciklusa határozza meg. A 6. sor minden egyes alkalommal időben végrehajtható, így a teljes futási idő . A megadott programkód tömör és csak egyszerű adatszerkezeteket igényel. A -jelölésbeli állandó tehát kicsi, és a Floyd-Warshall-algoritmus még közepesen nagy méretű gráfok esetén is hatékony.

A és mátrixok, ha a Floyd-Warshall-algoritmust az ábrán látható gráfon futtatjuk.

A legrövidebb utak megadása

A Floyd-Warshall-algoritmusban több módszer is kínálkozik arra, hogy a legrövidebb utak éleit is megkapjuk. Megtehető, hogy a legrövidebb úthosszak mátrixának ismeretében idő alatt megkonstruáljuk a { } megelőzési mátrixot. A { } megelőzési mátrix ismeretében pedig a Minden-párhoz-utat-nyomtat eljárás megadja a kívánt két csúcs közti legrövidebb út éleit.

A megelőzési mátrixot számíthajuk a Floyd-Warshall-algoritmus menetében a mátrixokkal egyidejűleg is. Pontosabban mátrixok egy sorozatát számíthatunk, melyre . E sorozatban -t úgy definiáljuk, mint egy olyan legrövidebb -ből -be vezető úton a -t megelőző csúcsot, melynek belső csúcsai a halmaz elemei.

Megadjuk a értékeit definiáló rekurziót. (A mátrixok számítása az ábra példájában követhető.) Ha , akkor -től -ig tartó úton nincs közbülső csúcs és így

A esetben pedig egy úton a -t megelőző csúcsnak választható ugyanaz a csúcs, amely -t egy legrövidebb -ból induló és belső csúcsként csak az halmaz elemeit használó úton előzi meg. Ha pedig a legrövidebb -ből -be vezető és az halmaz elemeit használó út -t nem tartalmazza, akkor a -t megelőző csúcs megegyezik a érték esetén választott megelőző csúccsal. Tehát mellett a rekurzív egyenlet

6.7. Gráfok tranzitív lezártja

6.30. Definíció. A gráf tranzitív lezártja az a gráf, melyre

6.8. Feladatok

  1. A Prim algoritmust használva határozzunk meg egy minimális feszítőfát az alábbi hálózatban! Induljunk ki az 1-es csúcsból! Minden élt csak egy helyen adunk meg a szomszédsági listában, zárójelben az él hossza (súlya) áll. Hány él alkotja a kapott minimális feszítőfát? Melyik csúcs a szülője a 6-os csúcsnak a kapott minimális feszítőfában?

  2. Adott egy digráf az 1, 2, 3, 4, 5, 6 csúcspontokkal az alábbi szomszédsági listával. Az 1-es csúcspontból kiindulva végezzünk el egy szélességi keresést! Hány él alkotja az eljárás által létrehozott szélességi fát? Mennyi a megtalált csúcsokba vezető legrövidebb utak összhossza?

7. fejezet - Dinamikus programozás

A dinamikus programozás és az oszd meg és uralkodj elv közötti legfontosabb különbségeket mutatja a következő táblázat.

A dinamikus programozás lépései:

  1. Jellemezzük az optimális megoldás szerkezetét.

  2. Rekurzív módon definiáljuk az optimális megoldás értékét.

  3. Kiszámítjuk az optimális megoldás értékét alulról felfelé módon.

  4. A kiszámított információk alapján megszerkesztjük az optimális megoldást.

7.1. Definíció. Mátrixok szorzatát teljesen zárójelezettnek nevezzük, ha a szorzat vagy egyetlen mátrixból áll, vagy pedig két, zárójelbe tett teljesen zárójelezett mátrix szorzata

7.1. Példa. Legyenek az mátrixok méretei , és . Számítsuk ki a mátrixot.

Ekkor mérete . A műveletszám (szorzások száma) két mátrix összeszorzásakor: , ha a méretek és .

Első módszer: , műveletszám

Második módszer: , műveletszám

Legyenek az összeszorzandó mátrixok: és legyen az mátrix mérete ().

Legyen az mátrix zárójelezéseinek a száma.

Innen:

Az optimális zárójelezés szerkezete:

Legyen . Az optimális eset az szorzatot -nál vágja szét . Költség költsége + költsége + az összeszorzás költsége. és zárójelezése is optimális kell legyen.

Legyen az kiszámításának minimális költsége

Legyen az a index, ahol az szorzat ketté van vágva.

Legyen

7.2. Példa.

</examend>

7.1. Feladatok

  1. 1. Milyen az optimális zárójelezés, ha a mátrixok méretei: ?

  2. 2. Adható-e egyszerű szabály az optimális zárójelezésre akkor, ha a méretek a vektorban monoton növekednek? És ha monoton csökkennek?

8. fejezet - NP-teljesség

A következőkben vázlatosan betekintünk az algoritmusok bonyolultság elméletébe. Az előző fejezetekben tárgyalt algoritmusok általában legrosszabb esetben polinomiális idejűek voltak. Vajon minden probléma megoldására adható polinomiális idejű algoritmus? Sajnos a válasz az, hogy nem. A polinomiális időben megoldható problémákat tekintjük jól kezelhetőknek. Ezen problémák zárt osztályt képeznek, azaz, ha az egyikük eredményét egy másik ilyen probléma bemenetére adjuk, akkor az összetett probléma is polinomiális idejű lesz.

8.1. Definíció. Az absztrakt probléma egy kétváltozós reláció a probléma eseteinek (bemeneteinek) és a probléma megoldásainak halmazán.

Így egy inputhoz több output is tartozhat.

8.2. Definíció. Döntési (eldöntési) probléma az olyan absztrakt probléma, melynek a megoldása "igen", vagy "nem".

Ez azt jelenti, hogy a döntési probléma egy leképezés, ahol a nulla szimbolizálja a"nem"-et, az 1 az "igen"-t. Optimalizálási problémák például átalakíthatók döntésivé azon átfogalmazással, hogy az optimum kisebb-e egy előre megadott értéknél.

8.3. Definíció. Egy absztrakt objektumokból álló halmaz kódolása egy leképezés -ről a bináris sorozatokra.

Az algoritmusok a probléma eseteinek kódolását kapják inputként.

8.4. Definíció. Konkrét az absztrakt probléma, ha esetei a bináris sorozatok.

8.5. Definíció. Egy algoritmus egy konkrét problémát idő alatt megold, ha minden hosszúságú esetre a megoldás lépést igényel.

8.6. Definíció. Egy konkrét probléma polinomiális időben megoldható, ha létezik olyan algoritmus, amely idő alatt megoldja valamely számra.

8.7. Definíció. P bonyolultsági osztálynak nevezzük a polinomiális időben megoldható problémák halmazát.

8.8. Definíció. Azt mondjuk, hogy egy függvény polinomiális időben kiszámítható, ha létezik olyan A polinomiális algoritmus, amely tetszőleges bemenetre az -et adja eredményül.

8.9. Definíció. Azt mondjuk, hogy az és kódolások polinomiálisan kapcsoltak, ha léteznek olyan és polinomiális időben kiszámítható függvények, hogy bármely esetre és .

Polinomiálisan kapcsolt kódolások esetén mindegy, hogy melyiket használjuk a probléma polinomiális időben való megoldhatóságának az eldöntésére. Erős kapcsolat áll fenn a döntési problémák és a formális nyelvek között. A formális nyelvek valamely szimbólumok véges halmazát, amit ábécének neveznek, használják fel a formális nyelv megadására. Az ábécé elemeiből véges sorozatokat (szavakat) képezve, a nyelvet az így képezhető összes véges sorozatok halmazának részhalmazaként adják meg. Ha az ábécét a jelöli, akkor a sorozatokat a . Ha az ábécé a zérus és az egy jel, akkor a sorozatok halmaza az összes véges bináris jelsorozat, amihez hozzávesszük még az üres szót, amit -nal jelölünk. Mivel a nyelv eszerint egy halmaz (részhalmaz), ezért érvényesek rá és általában a formális nyelvekre a halmazelméleti műveletek, mint például az unió, a metszet, a komplementer képzés. További művelet a konkatenáció, amely a benne szereplő nyelvek szavainak egymás után írását, összekapcsolását jelenti. Jelölésben az és nyelvek konkatenáltja . Az nyelv lezártjának nevezik az nyelvet. A döntési problémák esetén a döntési probléma esethalmaza , a bináris jelsorozatok halamaza. Magát a döntési problémát pedig ezen halmazból az a nyelv jelöli ki, amely azon sorozatokból áll, amelyre a probléma egyet ad. Ha a probléma, akkor a neki megfelelő nyelv. .

8.10. Definíció. Azt mondjuk, hogy az algoritmus elfogadja az szót, ha , és elutasitja azt, ha .

8.11. Definíció. Azt mondjuk, hogy az algoritmus elfogadja az nyelvet, ha a nyelv minden szavát elfogadja.

Ez nem jelenti azt, hogy a nyelvhez nem tartozó szavak közül ne fogadna el egyet sem.

8.12. Definíció. Azt mondjuk, hogy az algoritmus eldönti az nyelvet, ha a nyelv minden szavát elfogadja, a többit pedig elutasítja.

8.13. Definíció. Azt mondjuk, hogy az algoritmus polinomiális időben elfogadja az nyelvet, ha a bármely hosszúságú szót időben elfogad valamely konstansra.

8.14. Definíció. Azt mondjuk, hogy az algoritmus polinomiális időben eldönti az nyelvet, ha a bármely hosszúságú szót időben elfogad, ha a szó -beli, vagy elutasít, ha nem -beli. Itt konstans.

8.15. Definíció. Azt mondjuk, hogy az nyelv polinomiális időben elfogadható/eldönthető, ha létezik algoritmus, amely polinomiális időben elfogadja/eldönti.

A bonyolultsági osztály azon nyelvek halmaza a fölött, amelyek polinomiális időben elfogadhatók. Könnyebb általában egy probléma megoldását ellenőrizni, mint azt megtalálni. Az ellenőrzés egfajta tanúsítvány, ami a megoldás helyességét bizonyítja.

8.16. Definíció. Ellenörző algoritmusnak nevezzük az olyan kétbemenetű algoritmust, amelynek egyik bemenete a döntési probléma bemenete, a másik pedig, amit tanúnak neveznek, egy bináris szó.

8.17. Definíció. Azt mondjuk, hogy az ellenörző algoritmus bizonyítja az szót, ha létezik olyan tanú, hogy , és bizonyítja az nyelvet, ha bizonyítja minden szavát és minden szó, amit bizonyít -ben van.

8.18. Definíció. Azon nyelvek osztályát, amelyek polinomiális időben bizonyíthatók, bonyolultsági osztálynak nevezzük.

Az megnevezés a "nondeterministic polinomial (time)" rövidítése. Annyi bizonyos, hogy , hiszen az ellenörző algoritmus lehet maga az nyelv polinomiális idejű eldöntő algoritmusa azáltal, hogy az bemenetet ignorálja. Azt nem tudjuk, hogy , vagy áll-e fönn, bár intuitíve az első látszik igaznak. A válasz egyelőre nem ismeretes. probléma például a Hamilton-kör probléma, amely azt óhajtja eldönteni, hogy van-e egy irányítatlan gráfban Hamilton-kör, azaz olyan kör, amely a gráf mindegyik csomópontján csak egyszer megy át. A problémák bonyolultságának összehasonlítását könnyíti meg a visszavezethetőségi elv. Ez az elv a problémát átfogalmazza egy másik problémává, olyanná, amelynek megoldásából már következik az eredeti probléma megoldása.

8.19. Definíció. Azt mondjuk, hogy az nyelv polinomiálisan visszavezethető az nyelvre (jelölése ), ha létezik olyan polinom időben kiszámítható függvény, hogy minden esetén .

Az függvény neve visszavezető függvény, a kiszámító algoritmusáé pedig visszavezető algoritmus. Teljesül az állítás, miszerint, ha egy probléma visszavezethető polinomiálisan egy másikra és a másik -beli, akkor az eredeti is -beli volt.

8.20. Definíció. Azt mondjuk, az nyelv -teljes, ha teljesül az következő két feltétel

Minden -re .

Az -teljes nyelvek halmazát -vel jelöljük. Ha egy nyelv a második tulajdonságot teljesíti, de az elsőt nem, akkor nehéznek nevezzük.

8.21. Tétel.

Ha létezik polinomiális időben megoldható NP-teljes probléma, akkor P=NP, azaz ha létezik NP-ben polinomiális időben nem megoldható probléma, akkor egyetlen NP-teljes probléma sem polinomiális.

A tétel nyílvánvaló, mert ha van olyan nyelv, amelyre , akkor az -teljesség 2. pontja alapján bármely esetén és emiatt akkor is fennáll. A jelenlegi állapotok alapján kicsi az esélye, hogy valaki előáll egy -probléma polinomiális megoldásával, ami azt jelentené, hogy . egy probléma -teljessége arra utal, hogy a probléma nehezen kezelhető.

Végül néhány -teljes probléma következzen.

  • Irányítatlan gráf Hamilton-köre. (HAM probléma.)

  • Boole-hálózat kielégíthetőségi problémája, azaz egy logikai kapukból (ÉS, VAGY, NEM) álló hálózatnak van-e olyan bemenete, amelyre 1-et ad a kimeneten. (C-SAT probléma.) Ugyanis, ha ilyen nem lenne, akkor helyettesíthető lenne egy konstans nullát adó elemmel, megtakarítva ezzel a bonyolult felépítést.

  • A 3-SAT probléma. A pontosan három elemű zárójeleket tartalmazó konjunktív normálformák kielégíthetőségének problémája.

  • Az irányítatlan gráf klikk-problémája, azaz létezik-e a gráfban -méretű klikk, olyan részgráf, amelyben minden csúcspár szomszédos.

  • A minimális lefedő csúcshalmaz probléma. Irányítatlan gráf lefedő csúcshalmaza a csúcsainak olyan részhalmaza, hogy minden élre az él két végpontján lévő csúcsok egyike, vagy mindkettő ezen csúcshalmazban van. A probléma a minimális lefedő csúcshalmaz méretének megkeresése.

  • A részletösszeg probléma. Adott a természetes számok egy véges részhalmaza. Egy adott természetes számra létezik-e olyan halmaz, melyben a számok összege pontosan a szám.

  • Az utazó ügynök probléma. Adott város, amelyet az ügynöknek tetszőleges sorrendben végig kell látogatnia. Ismert bármely két város között a közvetlen utazási költség, egész szám, ami lehet akár negatív is. Megkeresendő a minimális költségű körutazás.

Egy -probléma esetén nagy méreteknél kevés az esély polinomiális algoritmus megtalálására. (Eddig még nem sikerült.) Ilyenkor célszerű közelítő megoldást adó algoritmusokkal foglalkozni.

9. fejezet - Mellékletek

9.1. Az ASCII karakterkészlet

9.1.1. Vezérlő jelek

Hexa

Decimális

Karakter

Jelentés

00

0

NUL

NULL

01

1

SOH

Start of heading

02

2

STX

Start of text

03

3

ETX

End of text

04

4

EOT

End of transmission

05

5

ENQ

Enquiry

06

6

ACK

Acknowledgement

07

7

BEL

Bell

08

8

BS

Backspace

09

9

HT

Horizontal tab

0A

10

LF

Line feed

0B

11

VT

Vertical tab

0C

12

FF

Form feed

0D

13

CR

Carriage return

0E

14

SO

Shift out

0F

15

SI

Shift in

Hexa

Decimális

Karakter

Jelentés

10

16

DLE

Data link escape

11

17

DC1

Device control 1

12

18

DC2

Device control 2

13

19

DC3

Device control 3

14

20

DC4

Device control 4

15

21

NAK

Negative acknowledgement

16

22

SZN

Synchronous idle

17

23

ETB

End of transmission block

18

24

CAN

Cancel

19

25

EM

End of medium

1A

26

SUB

Substitute

1B

27

ESC

Escape

1C

28

FS

File separator

1D

29

GS

Group separator

1E

30

RS

Record separator

1F

31

US

Unit separator

7F

127

DEL

Delete

9.1.2. Nyomtatható karakterek

Hexa

Dec

Karakter

Hexa

Dec

Karakter

Hexa

Dec

Karakter

20

32

Space

40

64

@

60

96

`

21

33

!

41

65

A

61

97

a

22

34

"

42

66

B

62

98

b

23

35

#

43

67

C

63

99

c

24

36

$

44

68

D

64

100

d

25

37

%

45

69

E

65

101

e

26

38

&

46

70

F

66

102

f

27

39

'

47

71

G

67

103

g

28

40

(

48

72

H

68

104

h

29

41

)

49

73

I

69

105

i

2A

42

*

4A

74

J

6A

106

j

2B

43

+

4B

75

K

6B

107

k

2C

44

,

4C

76

L

6C

108

l

2D

45

-

4D

77

M

6D

109

m

2E

46

.

4E

78

N

6E

110

n

2F

47

/

4F

79

O

6F

111

o

30

48

0

50

80

P

70

112

p

31

49

1

51

81

Q

71

113

q

32

50

2

52

82

R

72

114

r

33

51

3

53

83

S

73

115

s

34

52

4

54

84

T

74

116

t

35

53

5

55

85

U

75

117

u

36

54

6

56

86

V

76

118

v

37

55

7

57

87

W

77

119

w

38

56

8

58

88

X

78

120

x

39

57

9

59

89

Y

79

121

y

3A

58

:

5A

90

Z

7A

122

z

3B

59

;

5B

91

[

7B

123

{

3C

60

5C

92

\

7C

124

\textbar

3D

61

=

5D

93

]

7D

125

}

3E

62

5E

94

̂

7E

126

̃

3F

63

?

5F

95

_

 

 

 

Irodalomjegyzék

[1] Magyar értelmező kisszótár. Akadémiai Kiadó, Budapest. 1975.

[2] Sain Márton. Nincs királyi út!. Matematikatörténet. Gondolat Kiadó Budapest. 1986.

[3] The Unicode Standard / the Unicode Consortium; edited by Julie D. Allen et al. Version 6.0.. ISBN 978-1-936213-01-6. http://www.unicode.org/versions/Unicode6.0.0/.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest. Algoritmusok. Műszaki Könyvkiadó, Budapest. 1999.

[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Új algoritmusok. Scolar Kiadó, Budapest. 2003.

[6] Ivanyos G., Szabó R. Rónyai L. Algoritmusok. TYPOTEX Kiadó KFT.. 2008.

[7] Iványi A. (alkotó szerkesztő). Informatikai Algoritmusok I.. ELTE Eötvös Kiadó, Budapest. 2004.

[8] Iványi A. (alkotó szerkesztő). Informatikai Algoritmusok II.. ELTE Eötvös Kiadó, Budapest. 2005.

[9] D. E. Knuth. A számítógép-programozás művészete. AnTonCom Infokommunikációs Kft.. 2009.