ALGORITMUSOK ÉS ADATSZERKEZETEK

Egy általános célú BSc szintű tananyag

Az Algoritmusok és adatszerkezetek I-II. tantárgy előadásaitól való visszavonulásom után az alábbi jegyzettel szeretném továbbra is támogatni az oktatást: http://people.inf.elte.hu/fekete/algoritmusok_jegyzet/

A jegyzet anyaga scorm formában is megtalálható az ELTE TÁMOP-pályázati honlapján: http://tamop412.elte.hu/tananyagok/algoritmusok/index.html

(Az ígéretek szerint az anyag megjelenik majd a Digitális Tankönyvtárban is.)

A jegyzet még hiányos: a 12., 13., 18, 20. és 21. fejezetben csak címek és ábrák találhatók, továbbá egyelőre nem került sor két tervezett fejezet (a Huffman-kódolás és a Lempel-Ziv-Welch tömörítő algoritmus) megírására.

(Az anyagban számos hiba lehet, ezért kérjük az érdeklődő olvasókat, hogy küldjék el észrevételeiket, megjegyzéseiket!)

Jegyzet fejezetei a következő struktúrába rendezhetők:

I. ALAPFOGALMAK

1. Algoritmusok műveletigénye

2. Az adattípus absztrakciós szintjei

II. ALAPVETŐ ADATSZERKEZETEK

3. Tömb

4. Verem

5. Sor

6. Listák

7. Bináris fa

8. Elsőbbségi sor

III. KERESÉS ÉS KIVÁLASZTÁS

9. Maximum és szimultán minimum-maximum kiválasztás

10. Medián és k-adik elem kiválasztás

IV. KERESŐFÁK

11. Bináris keresőfák

12. AVL fák

13. 2-3 fák és B-fák

V. RENDEZÉSEK (összehasonlításos)

14. Három hagyományos (négyzetes) rendezés

15. Verseny rendezés

16. Kupacrendezés

17. Gyorsrendezés

18. Összefésülő rendezés

19. Az összehasonlító rendezések alsókorlát-elemzése

VI. HASÍTÁSOS TECHNIKÁK (HASH CODING) ALKALMAZÁSAI

20. Hasítás

21. Edényrendezések

VII. GRÁFALGORITMUSOK

22. Alapfogalmak, gráfok ábrázolásai

23. Szélességi bejárás

24. Minimális költségű utak egy forrásból I.

25. Minimális költségű utak egy forrásból II.

26. Minimális költségű utak minden csúcspárra

27. Minimális költségű feszítőfák

28. Mélységi bejárás, élek osztályozása

29. DAG topologikus rendezése

30. Erősen összefüggő komponensek

VIII. MINTAILLESZTÉS (STRING KERESÉS)

31. Egyszerű mintaillesztés

32. Knuth-Morris-Pratt algoritmus

33. Gyorskeresés (Horspool alg.)

34. Rabin-Karp algoritmus

35. Mintaillesztés automatával