Előszó

Az egyetemi informatikus képzések tantervében a világ országaiban mindenütt megtalálható az a kurzus, amely az alapvető adatstruktúrák és algoritmusok ismertetésére vállalkozik. Az Eötvös Loránd Tudományegyetemen folyó Programtervező informatikus alapképzésben az Algoritmusok és adatszerkezetek című két féléves tantárgy keretében sajátíthatják el a hallgatók a témakör ismereteit. Az Alkalmazott matematikus szakirányon az Algoritmusok tervezése és elemzése című, ugyancsak két féléves, az előzőhöz hasonló tematikájú tantárgy valósítja meg ezt a képzési célt.

A jegyzet, amelyet az Olvasó megnyitott, az informatikus képzéshez illeszkedően az Algoritmusok és adatszerkezetek címet viseli, azonban a matematikus alapképzés céljaihoz is illeszkedik. A jegyzet két szerkesztője Fekete István és Hunyadvári László (akik egyben a legtöbb fejezet szerzői is) évek óta tartják az említett két előadást. A két kurzus egymáshoz képest „keresztfélévben” kerül meghirdetésre, ami azért is lényeges, mert a két tantárgy hivatalosan is kredit-ekvivalens, így a hallgatóknak mindkét félévben alkalmuk nyílik a kezdésre, illetve a hosszabb szünet nélküli folytatásra.

Az elkészült harmincöt fejezet nyolc nagyobb témakörbe sorolható be, amelyek a műveletigényről és az adatabsztrakcióról szóló két bevezető fejezet után sorrendben a következők: alapvető adatszerkezetek, kiválasztások, keresőfák, rendezések, hasítás és edényrendezés, gráfalgoritmusok és a mintaillesztés. Ez így együtt valamivel több is, mint egy két féléves kurzus aktuális tananyaga, másrészt jelenleg az előadásokon szereplő adattömörítés fejezetei még nem készültek el. A pótlással együtt újabb fejezetek (pl. piros-fekete fák), illetve újabb témakörök (pl. geometriai algoritmusok, kriptográfia alapjai) is megjelenhetnek az anyagban.

A nagyobb témakörök és a fejezetek megválasztásában és megírásában a szerzők tekintettel voltak az ELTE informatikus képzésének többi tantárgyára, a programozás, a formális nyelvek, a logika, a számítástudomány és a haladó algoritmusok kurzusaira.

A tárgyalásmód erős kölcsönös kapcsolatban áll a programozás oktatásával. A jegyzet támaszkodik az onnan jövő előzményekre: pl. az algoritmusok leírása „dobozos ábrákkal” (struktogram), az alapvető, sokszor előforduló kisebb feladatok általános megoldásai (pl. maximum kiválasztás, adott tulajdonságú elemek megszámolása), vagy az elő-, utófeltételes specifikáció. Másrészt azonban, az alapvető adatszerkezetek és reprezentációik ismertetését magára vállalja a jegyzet, ami a legtöbb oktatásban csak a programozási tárgyak feladata (mint pl. a tömb, verem, sor, listák esetében).

A logika, valamint a formális nyelvek és automaták kurzusaira is alapozhattak a szerzők (pl. axiomatikus specifikáció, mintaillesztés automatával). Az önálló tantárgyként jelenlévő számításelméletre való tekintettel, az anyag nem tartalmaz bonyolultság-elméleti fejezeteket (Turing-gép, NP-teljesség).

Az ELTE informatikus képzésének MSc szintjén szerepel egy két féléves haladó algoritmusok kurzus is. Ennek tematikájában megjelennek a fontos algoritmustervezési módszerek (oszd meg és uralkodj elve, mohó módszer, matroidok, dinamikus programozás, korlátozás és szétválasztás, visszalépéses és más keresések, véletlent használó módszerek, közelítő algoritmusok stb.). Ezek a módszerek ennélfogva nem szerepelnek a jegyzet anyagban (elméleti részletességű és alapos ismertetésüknek egyébként sem a BSc szint a legmegfelelőbb helye).

A jegyzet két speciális bevezető fejezettel indul. Az első fejezet példákon keresztül mutatja be az algoritmusok műveletigényének elemzését és az „ordó matematikájának” tömör összefoglalását is tartalmazza. A második fejezet az adattípus absztrakciós szintjeiről szól. A két meghatározó eszköznek a következetes alkalmazása végig vonul a jegyzet fejezetein.

A fejezetek teljes anyaga több forrásból állt össze, mivel a szerzők a korábbi oktatási segédanyagokat is felhasználták munkájuk során. A gráfalgoritmusok, valamint a mintaillesztés fejezetei külön stílus- és ábravilágot képviselnek a többihez képest. Három elméletibb látásmódú (a 9-10. és 35.) fejezettel még egy negyedik szín is megjelenik. Távolabbi célként fogalmazható meg a négy eltérő stílusú rész közelítése egymáshoz.

A teljes anyag megírásában Fekete István és Hunyadvári László mellett többen is részt vettek. A gráfalgoritmusokról szóló korábbi oktatási segédanyag szerzője Nagy Tibor, aki most a jegyzet számára, Giachetta Roberto együttműködésével átdolgozta ezt a nagyobb önálló témakört. A mintaillesztő algoritmusokhoz Sike Sándor írt korábban az oktatást támogató anyagot, amelyet most a jegyzet rendelkezésére bocsátott. Ezt a négy fejezetet Bartha Dénes és Ilonczai Zsolt dolgozták át. Két fejezet kidolgozásában Danyluk Tamás végzett értékes munkát.

A jegyzetnek talán szembeötlő jellemzője az, hogy nagyszámú ábra illusztrálja a szöveges leírást. Összesen 275 számozott és címmel ellátott ábra szerepel a fejezetekben. Egy ábra gyakran több megrajzolt részből tevődik össze. Az elkészített ábrák száma jó közelítéssel négyszázra tehető. Az ábrák egy része az algoritmusok leírását tartalmazza „dobozos” struktogramok formájában. Az ábrák nagyobb hányada azonban az algoritmusok működését szemlélteti, alapvető adatszerkezeteik állapotáról készült „pillanatfelvételek” formájában. Az ábrák döntő többségét Nagy Tibor és Orgován Krisztina készítette.

Az Algoritmusok és adatszerkezet, valamint az Algoritmusok tervezése és elemzése előadásokhoz, mindkét szakon gyakorlatok is tartoznak. Az előadók és gyakorlatvezetők együttműködő oktatói közössége az évek során hatékony szakmai hátteret nyújtott a tananyagfejlesztéshez. Az utóbbi években a gyakorlatokat Ásványi Tibor, Giachetta Roberto, Izsák Rudolf, Kőhegyi János, Nagy Sára, Tichler Krisztián és Veszprémi Anna oktató kollégák, valamint Danyluk Tamás, Kovács Péter, Máriás Zsigmond, Nagy Tibor és Tamaga István megbízott gyakorlatvezetők tartották. Az elkészült jegyzetben mindannyiuk munkája megjelenik.

A szerzők köszönetet mondanak Friedl Katalinnak a BME Számítástudományi és Információelméleti Tanszéke egyetemi docensének, aki a kézirat lektoraként, javító észrevételeivel és értékes tanácsaival jelentős mértékben hozzájárult jegyzet színvonalának emeléséhez.

Budapest, 2014. április 30.

Vissza a tartalomjegyzékhez