BSc Matematika Alapszak
Tantárgyleírás
2013.

Algoritmusok tervezése és elemzése2
Óraszám
ea/gy
Kredit
ea/gy
Számonkérés Szakirány Tárgykód
ea/gy
Ajánlott
félév
Státusz
2 + 2 2 + 3 kollokvium +
gyak. jegy
alk. mat. mm1c1at5a
mm1c2at5a
5 kötelező
Erős Gyenge előfeltételek
Gyakorlat
Erős:
Előadás
Gyenge:
a gyakorlat
Szükséges előismeretek
Programozási alapismeretek.
Irodalom
  • Cormen, Leiserson, Rivest, Stein: Új algoritmusok. Scolar, 2003.
  • Rónyai L., Ivanyos G., Szabó R.: Algoritmusok. TypoTex, 2005.
Ajánlott:
  • D. E. Knuth: A számítógép-programozás művészete, I. és III. Műszaki Könyvkiadó, 1987.
  • S. Lipschutz: Adatszerkezetek. Panem-McGraw-Hill, 1993.
  • N. Wirth: Algoritmusok + Adatstruktúrák = Programok. Műszaki Könyvkiadó, 1982.
  • A. Aho, J. Hopcroft, J. Ullman: Számítógép-algoritmusok tervezése és analízise. Műszaki Könyvkiadó, 1982.
  • Iványi Antal: Informatikai algoritmusok I-II. 2004, 2005.
  • Tematikák, segédanyagok letölthetők a http://aszt.inf.elte.hu/~hunlaci/ és http://people.inf.elte.hu/fekete/ címekről.
Tematika
  • Keresési módszerek asszociatív adatszerkezeteken: direkt elérésű táblázat, hasításos technikák (tökéletes, láncolt alstruktúrákat használó, nyílt címzés, parciális index-módszer), a hasító függvény előállításának módszerei.
  • Hasító függvényt használó (edény) rendezések (tökéletes, előrendezéses, utórendezéses, számjegypozíciós változataik).
  • Mintaillesztési módszerek: Brute-force, Knuth-Morris-Pratt, Rabin-Karp, Dömölky-szűrő, Knuth-Morris-Pratt véges determinisztikus automatákkal.
  • A kódolás és a tömörítés feladata, a tömörítés alaptétele. Online kódolás: kód, prefix kód, kódfa, Huffman-kód. A tömörítés adaptív módszerei Ziv-Lempel, Ziv-Lempel-Welch.
  • Gráfok ábrázolásai, szélességi és mélységi bejárás, topologikus rendezés, erősen összefüggő komponensek. Feszítőfák, minimális feszítőfa, a Piros-kék algoritmus, Kruskal és Prim algoritmusai. A legrövidebb utak problémája. Hálózatok és maximális folyamok, a Ford-Fulkerson algoritmus.