Algoritmusok és adatszerkezetek

Szerkesztők

Fekete István és Hunyadvári László

A fejezetek szerzői

Fekete István: 3–7., 11–12., 14., 16–18., 21. fejezet
Hunyadvári László: 9., 10., 20., 35. fejezet
Fekete István és Hunyadvári László: 1., 2., 8. fejezet
Nagy Tibor és Giachetta Roberto: 22–30. fejezet
Bartha Dénes és Ilonczai Zsolt: 13., 31–34. fejezet
Fekete István és Danyluk Tamás: 15., 19. fejezet

Az ábrákat készítették

Nagy Tibor, Orgován Krisztina és Fekete István

Vissza a tartalomjegyzékhez

A modul célja és tartalma

A jegyzet az egyetemi informatikus képzés részeként az alapvető adatstruktúrák és algoritmusok ismertetésére vállalkozik. (Részletesebben lásd az Előszóban.)

Vissza a tartalomjegyzékhez

A modul leckéi, a megértéshez szükséges előismeretek, tárgyi feltételek

Leckék

1. Előszó
2. Algoritmusok műveletigénye
3. Az adattípus absztrakciós szintjei
4. Tömb
5. Verem
6. Sor
7. Listák
8. Bináris fa
9. Elsőbbségi sor
10. Maximum és szimultán minimum-maximum kiválasztás
11. Medián és k-adik elem kiválasztás
12. Bináris keresőfák
13. AVL fák
14. 2-3 fák és B-fák
15. Három hagyományos (négyzetes) rendezés
16. Verseny rendezés
17. Kupacrendezés
18. Gyorsrendezés
19. Összefésülő rendezés
20. Az összehasonlító rendezések alsókorlát-elemzése
21. Hasítás
22. Edényrendezések
23. Alapfogalmak, gráfok ábrázolásai
24. Szélességi bejárás
25. Minimális költségű utak egy forrásból I.
26. Minimális költségű utak egy forrásból II.
27. Minimális költségű utak minden csúcspárra
28. Minimális költségű feszítőfák
29. Mélységi bejárás, élek osztályozása
30. DAG topologikus rendezése
31. Erősen összefüggő komponensek
32. Egyszerű mintaillesztés
33. Knuth-Morris-Pratt algoritmus
34. Gyorskeresés (Horspool alg.)
35. Rabin-Karp algoritmus
36. Mintaillesztés automatával

Előismeretek

• A jegyzet olvasásához legalább egy programozási alapkurzus elvégzése javasolt. (További tantárgyi alapokról lásd részletesebben az Előszóban.)

Tárgyi feltételek

• Multimédiás számítógép, telepített böngészőprogram

Vissza a tartalomjegyzékhez

A modul irodalomjegyzéke

Ajánlott irodalom

• Cormen, T. H. - Leiserson, C. E. - Rivest, R. L. - Stein, C.: Új algoritmusok, Scolar Kiadó, 2003.
• Rónyai L., Ivanyos G., Szabó R.: Algoritmusok, Typotex Kiadó, 1998.

Vissza a tartalomjegyzékhez

Kulcsszavak

Algoritmusok műveletigénye, Az adattípus absztrakciós szintjei,Tömb,Verem,Sor,Listák,Bináris fa,Elsőbbségi sor, Maximum és szimultán minimum-maximum kiválasztás, Medián és k-adik elem kiválasztás, Bináris keresőfák, AVL fák, 2-3 fák és B-fák, Három hagyományos (négyzetes) rendezés, Verseny rendezés, Kupacrendezés, Gyorsrendezés, Összefésülő rendezés, Az összehasonlító rendezések alsókorlát-elemzése, Hasítás, Edényrendezések, Alapfogalmak, gráfok ábrázolásai, Szélességi bejárás, Minimális költségű utak egy forrásból I., Minimális költségű utak egy forrásból II., Minimális költségű utak minden csúcspárra, Minimális költségű feszítőfák, Mélységi bejárás, élek osztályozása, DAG topologikus rendezése, Erősen összefüggő komponensek, Egyszerű mintaillesztés, Knuth-Morris-Pratt algoritmus, Gyorskeresés (Horspool alg.), Rabin-Karp algoritmus, Mintaillesztés automatával