Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1. fejezet - Bevezetés

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.