Adatstruktúrák, algoritmusok
HTML
Digitális Tankönyvtár
Szerző:
- Nagy Ferenc,
- Házy Attila
Típus:
- előadás fólia és feladatgyűjtemény
Elektronizálás módja:
- Latex-PDF
Terjedelem:
- 12 ív
Digitális elemek és számuk:
- 180 kép, ábra, 14 nem interaktív animáció, szimuláció,
- 28 tevékenység, feladat, kísérlet;
Tartalom:
Adat, absztrakt adattípus, adatstruktúra. Az algoritmus. Pszeudokód és folyamatábra. Dinamikus memóriagazdálkodás. Az algoritmus minőségi jellemzői. Függvények növekedésének jellemzése, az ordo szimbolika. A Fibonacci számok, Binet formula. Rekurrens egyenletek, mester tétel. Számelméleti algoritmusok. Legnagyobb közös osztó, euklideszi és kibővített euklideszi algoritmus, lineáris kongruencia egyenletek. Multiplikatív inverz, moduláris hatványozás, Fermat prímteszt. Titkosítás, digitális aláírás, RSA. Az absztrakt adatszerkezetek ábrázolásának módszerei. Dinamikus halmazok. Tömb, láncolt lista, verem, sor és tipikus alkalmazásaik. Keresés egyszerű struktúrákban: lineáris, logaritmikus keresés. Hasító táblák. Kiválasztási problémák. Minimum és maximum keresése. Kiválasztás lineáris idő alatt. Rendezések. Beszúró rendezés. Az oszd meg és uralkodj elv. Összefésülő rendezés, gyors rendezés. Időelemzéseik. Az összehasonlító rendezések időtétele. A Batcher-féle összefésülés és tétele. Buborék-rendezés, Shell rendezés, minimum kiválasztásos rendezés, négyzetes rendezés. Lineáris idejű rendezések: leszámláló, radix, edényrendezés. Külső tárak rendezése és a gyorsítás. Elemi gráfelméleti bevezető. A fa szerkezet, a nyílt fák tulajdonságainak tétele, műveletek. Gyökeres fák és ábrázolásuk, bináris fák, kupac. Kupacrendezés. Az elsőbbségi sor. Mohó algoritmusok. A Huffmann kód. Diszjunkt halmazok. Binomiális fák, binomiális kupac. Keresési technikák. Bináris keresőfák. Piros-fekete fák. AVL-fák, kiegyensúlyozott fák, 2-3 fák, B-fák. Gráfalgoritmusok. Szélességi keresés. Mélységi keresés. Topologikus rendezés. Erősen összefüggő komponensek. Optimumfeladatok fákon. Minimális feszítőfák. Kruskal és Prim algoritmus. Adott csúcsból induló legrövidebb utak. Dijkstra algoritmus. Bellman-Ford algoritmus. Körmentes irányított gráfban legrövidebb utak. Legrövidebb utak minden csúcspárra. Floyd-Warshall algoritmus. Gráfok tranzitív lezártja, a Warshall algoritmus. A dinamikus programozás elve. Alkalmazás mátrixok véges szorzatainak optimalizálására. Kitekintés a feladatok algoritmikus megoldhatósága kérdéskörére. Az egyes fejezetek végén javasolt feladatok gyűjteménye lesz, melyben elméleti és gyakorlati feladatok is lesznek.
Kurzus:
GEMAK121B, Adatstruktúrák, algoritmusok, mérnök informatikus, programtervező informatikus és gazdaságinformatikus alapszak.