Adatszerkezetek és közhasznú algoritmusok

Algoritmusok tervezése és elemzése

Az előadás célja, hogy kialakítsa a számítógépes algoritmusok hatékonyságvizsgálatának igényét és készségét. Bevezetésre kerülnek a hatékonyság mérésének legfontosabb jellemzői és példákon keresztül a meghatározásukhoz használatos matematikai eszközök. Bemutatásra kerülnek a hatékony algoritmusok tervezésére használatos legfontosabb technikák, külön csoportosítva az adatszerkezet megfelelő megválasztásán, ill. az algoritmus alkalmas szervezésén alapuló módszereket. Az alkalmazott matematika szakos hallgatók az előadás elején egy rövid módszertani bevezetőt is kapnak.

Azonosító: IKP-ASZ1E, IKP-ASZ2E, maln1k25/ea1, maln1k25/ea2

Szak: programozó matematikus, programtervező matematikus és alkalmazott matematikus szak

Óraszám: 2+2, 2+2

Számonkérés módja: kollokvium, gyakorlati jegy

Javasolt félév a programozó és programtervező matematikus szakon: 3. és 4.

Követelmények:

A záró kollokvium a 2. félév végén a programozó, programtervező matematikus szakon írásbeli, az alkalmazott matematikus szakon szóbeli vizsga, melynek előfeltétele a gyakorlati jegyek megléte.

A gyakorlati jegy feltétele a beadandó programok elkészítése (az alkalmazott matematikus szakon opcionális) és a zárthelyi dolgozatok mindegyikéből legalább az elégséges minősítés megszerzése. A beadandó programok, ill. zárthelyik száma legalább kettő, a tényleges értéket a gyakorlatvezetők határozzák meg.

Tematika

Feladatok algoritmikus megoldhatósága, gyakorlati megoldhatósága, az idő és tárbonyolultság (fajtái, példák számításukra, a nagyságrendek).
Programozási feladat, program, programfüggvény és a megoldás fogalma. Az alapvető programkonstrukciós módszerek és programozási tételek (Csak az alkalmazott matematikus szakon)
Absztrakt adattípusok, specifikációjuk, implementációjuk, példák. Absztrakt adatszerkezetek (ADS), osztályozásuk, ábrázolási módszerek (aritmetikai, láncolt).
A buborék-rendezés levezetése, teljes elemzése.
A hatékonyság növelésének példái (a prioritási sor ábrázolásai, k. elem kiválasztásának véletlenített módszere).
Szelekciós módszerek (k. legkisebb elem kiválasztása átlagos, illetve legrosszabb esetben is lineáris időben; medián kiválasztás, minimum, maximum, szimultán minimum és maximum kiválasztás, a legrosszabb esetre vonatkozó alsó becslések bizonyítása).
Lineáris adatszerkezetek ábrázolása, vektorok és tömbök aritmetikai ábrázolása, a lista adattípus és a lista adatszerkezet, példák listaszerkezetek használatára (sorozat műveletek, számjegypozíciós rendezés).
Vermek és sorok ábrázolása, felhasználási lehetőségeik, példák (helyes zárójelezések feldolgozása, kifejezések alakjai, posztfix forma származtatása, kiértékelése, szint-folytonos fabejárás sorral).
Fák, fák osztályozása, jellemző mennyiségek fákon és összefüggéseik (pontszám, élek száma, magasság, szintszám, mélységösszeg), fák ábrázolási lehetőségei, alapvető műveletek fákon (bejárások, szelektor szerinti keresés). Néhány alkalmazási példa (kifejezés fák, rendező-fa, tournament, heap).
Keresési módszerek asszociatív adatszerkezeteken 1, visszavezetéses technikák (lineáris keresés, logaritmikus keresés, keresőfák, optimális keresőfa, AVL-fa, piros-fekete fák, B-fák).
Keresési módszerek asszociatív adatszerkezeteken 2, direkt elérésű táblázat, hasításos technikák (tökéletes, láncolt alstruktúrákat használó, nyílt címzés, parciális index-módszer), a hasító függvény előállításának módszerei.
Rendezési módszerek osztályozása, a rekord-rendezés módszerei, a hasító függvényt használó (edény) rendezők (tökéletes, előrendezéses, utórendezéses, számjegypozíciós változataik).
Az összehasonlításos rendezési módszerekre vonatkozó alaptételek.
Maximumot kiválasztó rendezők alapalgoritmusa és elemzése, a gyorsítás lehetősége tournament és heap felhasználásával.
Egy elemet a helyére rakó rendezők 1. A quick-sort és elemzése, rendező-fák (bináris rendező-fa, kiegyensúlyozott bináris rendező-fa).
Egy elemet a helyére rakó rendezők 2. Az egyszerű beillesztés és a fogyó növekményű rendezés (Shell-módszere)
Csere rendezések, adat-független csere-rendezések, szemléltetésük rendező hálózatokkal (buborék, piramis, Batcher).
Az összefuttatásos rendezés és realizálása vektorban, illetve külső rendezőként.
Mintaillesztési módszerek (Brute-force, Knuth-Morris-Pratt, Rabin-Karp, Dömölky-szűrő, Knuth-Morris-Pratt véges determinisztikus automatákkal).
A kódolás és a tömörítés feladata, a tömörítés alaptétele. Online kódolás (kód, prefix kód, kódfa, Huffman – kód). A tömörítés adaptív módszerei (Ziv-Lampel, Ziv-Lampel-Welch).
Gráfok, ábrázolásuk, szélességi és mélységi bejárás, topológikus rendezés, erősen összefüggő komponensek.
Feszítőfák, minimális feszítőfa, a piros-kék algoritmus, Kruskál és Prim algoritmus, a legrövidebb utak problémája.
Hálózatok és maximális folyamok, a Ford-Fulkerson algoritmus.

Irodalom:

D.E. Knuth, A számítógép-programozás mûvészete, I. és III., Műszaki Könyvkiadó, 1987.
S. Lipschutz, Adatszerkezetek, Panem - Mc Graw-Hill, 1993.
N. Wirth, Algoritmusok + Adatstruktúrák = Programok, Műszaki Könyvkiadó, 1982.
A. Aho, J. Hopcroft, J. Ullman, Számítógép-algoritmusok tervezése és analízise, Műszaki Könyvkiadó, 1982.
Cormen, Leiserson, Rivest, Algoritmusok, 1997.
Iványi Antal, Informatikai algoritmusok I., II. 2004., 2005.
Rónyai Lajos, Ivanyos Gábor, Szabó Réka, Algoritmusok, TYPOTECH, 2005.