Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

Adatstruktúrák és algoritmusok

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