Algoritmusok

Aszalós László

Herendi Tamás

Új Széchenyi Terv logó.

A tananyag a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-magyarországi Informatika Tananyag Tárház projekt keretében készült. A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával valósult meg.

A Kelet-magyarországi Informatika Tananyag Tárház logója.

Magyarország megújul logó.

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Az EU logója.

2011.


Tartalom

1. Előszó
2. Turing-gép
2.1. A Turing-gép felépítése
2.2. Church-Turing tézis
2.3. Univerzális Turing-gép
2.4. Idő- és tárkorlát
2.5. NP nyelvosztály
2.6. Nevezetes NP bonyolultságú problémák
3. Algoritmusokról általában
3.1. Euklideszi algoritmus
3.2. Az algoritmus tulajdonságai
3.3. Jó és jobb algoritmusok
3.4. Kis ordó és nagy ordó
4. Keresések
4.1. Külső elem keresése
4.2. Belső elem keresése
4.3. Bináris keresés
5. Rendezések
5.1. Beszúró rendezés
5.2. Oszd meg és uralkodj!
5.2.1. Összefésülő rendezés
5.2.2. Gyorsrendezés
5.3. Gráfelméleti alapfogalmak
5.4. Kupac
5.4.1. Kupacépítés
5.4.2. Kupacrendezés
5.5. Lineáris idejű rendezések
5.6. Leszámláló rendezés (ládarendezés)
5.7. Számjegyes (radix) rendezés
5.8. Külső rendezés
5.9. Medián, minimális, maximális, i-dik legnagyobb elem
6. fejezet Dinamikus halmazok
6.1. Műveletek típusai
6.2. Keresés
6.3. Naív beszúrás
6.4. Naív törlés
6.5. Piros-fekete fák
6.5.1. Piros-fekete tulajdonság
6.5.2. Forgatások
6.5.3. Piros-fekete beszúrás
6.5.4. Piros-fekete törlés
6.6. AVL-fa
6.6.1. Forgatások
6.7. B-fa
6.8. Ugrólisták
6.8.1. Keresés ugrólistában
6.8.2. Beszúrás ugrólistába
6.8.3. Törlés ugrólistából
7. Elemi adatszerkezetek
7.1. Verem
7.2. Sor
7.3. Láncolt lista
8. Hasító táblázatok
8.1. Közvetlen címzés
8.2. Hasító függvény
8.3. Hasító függvény kiválasztása
8.4. Nyílt címzés
9. Diszjunkt halmazok
9.1. Láncolt listás ábrázolás
9.2. Diszjunkt-halmaz erdők
9.3. Összefüggő komponensek
10. Gráfalgoritmusok
10.1. Gráfok ábrázolása
10.2. Szélességi keresés
10.3. Mélységi keresés
10.4. Topológikus elrendezés
10.5. Erősen összefüggő komponensek
10.6. Minimális költség ű feszítőfa
10.7. Legrövidebb utak problémája
10.7.1. Fokozatos közelítés
10.7.2. Dijkstra algoritmusa
10.7.3. Bellmann-Ford algoritmusa
10.7.4. Irányított körmentes gráfok esete
10.7.5. Legrövidebb utak meghatározása minden csúcspárra
10.7.6. Floyd-Warshall algortimus
11. Mintaillesztés
11.1. Brute force (nyers erő)
11.2. Rabin-Karp algoritmus
11.3. Knuth-Morris-Pratt algoritmus
11.4. Boyer-Moore algoritmus
12. Fejlett programozási módszerek
12.1. Dinamikus programozás
12.2. Mohó algoritmus
12.3. Korlátozás és elágazás (Branch and bound)
12.4. Visszalépéses programozás (Back-track)
13. Pszeudókód
13.1. Adatok
13.2. Utasítások
13.3. Feltételes szerkezetek
13.4. Ciklusok
14. Irodalomjegyzék
15. Tárgymutató

Az ábrák listája

2.1. Turing gép modell
3.1. Az Euklideszi algoritmus folyamatábrája
5.1. 1. ábra
5.2. 2. ábra
5.3. 3. ábra
5.4. 4. ábra
5.5. 5. ábra
5.6. 6. ábra
5.7. 7. ábra
5.8. 8. ábra
5.9. 9. ábra
5.10. 10. ábra
6.1. 6.5.1. ábra
6.2. 6.5.2. ábra
6.3. 6.5.3. ábra
6.4. A 7, 4 és 8 beszúrása
6.5. A 9, 3 és 2 beszúrása
6.6. A 6, 5 és 1 beszúrása
6.7. A 7 törlése
6.8. A 4 törlése
6.9. A 8 törlése
6.10. A 9 és 3 törlése
6.11. A 6 és 5 törlése
6.12. 6.6.1. ábra Egyszeres forgatások
6.13. 6.6.2. ábra. Kétszeres forgatások
6.14. 6.6.3. ábra. Kétszeres forgatások végeredménye
6.15. 6.6.4. ábra A 7, 9, 3 és 5 beszúrása
6.16. 6.6.5. ábra A 4 naiv beszúrása
6.17. 6.6.6. ábra A forgatás után helyreáll az AVL-tulajdonság
6.18. 6.6.7. ábra A 2 naív beszúrásával ismét sérül az AVL-tulajdonság
6.19. 6.6.8. ábra Forgatással megint helyreállítható
6.20. 6.6.9. ábra Az 1 naív beszúrásával ismét sérül az AVL-tulajdonság
6.21. 6.6.10. ábra Megint egy egyszeres forgatásra van szükség
6.22. 6.6.11. ábra 6 és 8 beszúrása
6.23. 6.6.12. ábra A 9 törlése és a helyreállítás
6.24. 6.6.13. ábra 3 és 5 törlése
6.25. 6.6.14. ábra 2, 1 és 6 törlése
6.26. N, D, W, K beszúrása
6.27. B és A beszúrása
6.28. P és R beszúrása
6.29. X beszúrása átforgatással
6.30. G beszúrása új levél nyitásával
6.31. Q és L beszúrása
6.32. V beszúrása új levél nyitásával
6.33. C beszúrása
6.34. E beszúrása forgatással
6.35. T beszúrása
6.36. Y beszúrása
6.37. U beszúrása
6.38. F beszúrása új levél nyitásával
6.39. Z beszúrása
6.40. O beszúrása
6.41. N törlése
6.42. D törlése
6.43. W törlése
6.44. K törlése forgatással az első levélbő
6.45. B törlése levelek összevonásával
6.46. A törlése
6.47. P törlése Q felhuzásával és Q átforgatásával
6.48. R törlése
6.49. X törlése
6.50. A G törlésekor az őt megelőző kulccsal helyettesítjük
6.51. Q törlése levelek összevonásával
6.52. L törlése
6.53. V törlése
6.54. C, E és T törlése
6.55. Y törlése levelek összevonásával jár
6.56. 6.8.1. ábra Láncolt lista
6.57. 6.8.2. ábra Láncolt lista extra mutatókkal
6.58. 6.8.3. ábra Az eredeti ugrólista
6.59. 6.8.4. ábra Az 5 beszúrása az ugrólistába
6.60. 6.8.5. ábra A 7 törléséhez feljegyezzük az őt megelőző elemeket
6.61. 6.8.6. ábra A 7 tényleges törlése
7.1. Egyszeresen láncolt lista
7.2. Kétszeresen láncolt lista
7.3. Kétszeresen láncolt, ciklikus lista
7.4. Listafejbe szúrás
7.5. Listából törlés
8.1. 8.1.1. ábra. Közvetlen címzés
8.2. 8.2.1. ábra. Ütközések kezelése láncolt listával
8.3. 8.3.1. ábra. k mod 8 hasítófüggvény használata
8.4. 8.3.2. ábra. k mod 9 hasítófüggvény használata
8.5. 1. táblázat. Szorzásos módszer A = 0.618 esetén
8.6. 8.3.3. ábra. Szorzásos módszer m = 8 és A = 0.618 esetén
8.7. Ütközés a 19 beszúrásakor, i = 0
8.8. Ütközés a 19 beszúrásakor, i = 1
8.9. A 19 elhelyezhető i = 2 esetén
8.10. Ütközés a 23 beszúrásakor, i = 0
8.11. Ütközés a 23 beszúrásakor, i = 1
8.12. A 23 elhelyezhető i = 2 esetén
8.13. Ütközés a 29 beszúrásakor, i = 0
8.14. A 29 elhelyezhető i = 1 esetén
9.1. Láncolt listás ábrázolás
9.2. Diszjunkt-halmaz erdő ábrázolás
9.3. 9.3.1. ábra. Példagráf összefüggő komponensek meghatározásához
9.4. 1. táblázat. A kiszámolt komponensek
10.1. 10.1.1. ábra. Példagráf
10.2. 10.1.2. ábra. A példagráf éllistás ábrázolása
10.3. 1. táblázat. A példagráf szomszédsági mátrixos ábrázolása
10.4. 10.2.1. ábra. Eredeti gráf
10.5. 10.2.2. ábra. Kiinduló állapot, az a csúcsból kezdünk
10.6. 10.2.3. ábra. Az a három szomszédja
10.7. 10.2.4. ábra. A d-nek nincs új szomszédja
10.8. 10.2.5. ábra. Az f-nek viszont van, az e
10.9. 10.2.6. ábra. A g-nek sincs új szomszédja
10.10. 10.2.7. ábra. Az e új szomszédjai a b és a h
10.11. 10.2.8. ábra. A b-nek nincs új szomszédja
10.12. 10.2.9. ábra. A h-nak sincs, és ezzel a sor is kiürült
11.1. 11.4.1. ábra. Utolsó pozíció heurisztika, amikor a nem egyező karakter szerepel a mintában
11.2. 11.4.2. ábra. Utolsó pozíció heurisztika, amikor a nem egyező karakter nem szerepel a mintában
11.3. 11.4.3. ábra. A jó szuffix heurisztika, mikor az újra előfordul
11.4. 11.4.4. ábra. A jó szuffix heurisztika, mikor az nem fordul elő újra
12.1. 12.3.1. ábra. Grundy-féle játék fája 7 érme esetén
12.2. 12.3.2. ábra. A felcimkézett Grundy-féle játékfa
12.3. 12.3.3. ábra. Játékfa-részlet
12.4. 12.3.4. ábra. Minimax értékek
12.5. 12.3.5. ábra. alfa - béta vágások

A táblázatok listája

2.1.
2.2. L' diagonális konstrukciója
3.1. Euklideszi algoritmus lépései az m=119 és n=544 számokra
11.1. 1. táblázat. Brute force algoritmus
11.2. 2. táblázat. Rabin-Karp algoritmus
11.3. 3. táblázat. Prefixfüggvény számítás

A példák listája

2.1. 3. példa
3.1. 1. példa
3.2. 2. példa
5.1. 4. Példa
5.2. 5. példa
5.3. 6. példa
5.4. 7. példa
5.5. 8. példa
6.1. 9. példa
6.2. 10. példa
6.3. 11. példa
6.4. 12. példa
6.5. 13. példa a B-fába beszúrásra
6.6. 14. példa törlésre
7.1. 15. példa

Az egyenletek listája

2..
2..
2..
5..
5..