BSc Matematika Alapszak
Tantárgyleírás
2017.
Tantárgyleírás
2017.
Algoritmusok tervezése és elemzése2
- Óraszám (ea+gy): 2 + 2
- Specializáció: alk. mat.
- Kredit (ea+gy): 3 + 2
- Számonkérés: kollokvium + gyak. jegy
- Tárgykód (ea, gy): algter2a0_m17ea, algter2a0_m17ga
- Ajánlott félév: 5
- Státusz: köt. vál.
Óraszám
ea(+k) + gy(+k) |
Kredit
ea + gy |
Számonkérés | Specializáció | Tárgykód
ea/gy |
Ajánlott
félév |
Státusz |
---|---|---|---|---|---|---|
2 + 2 | 3 + 2 | kollokvium + gyak. jegy |
alk. mat. | algter2a0_m17ea algter2a0_m17ga |
5 | köt. vál. |
Tantárgyfelelős
Erős | Gyenge | előfeltételek |
---|---|---|
Gyakorlat | ||
Erős:
Algoritmusok tervezése és elemzése1E-a
(algter1a0_m17ea)
| ||
Előadás | ||
Gyenge:
a gyakorlat
|
Megjegyzések
- Alkalmazott matematikus specializáción kötelezően el kell végezni legalább hármat az alábbi négy tárgy közül: Algoritmusok tervezése és elemzése2, Parciális differenciálegyenletek, Komplex függvénytan, Numerikus analízis2.
A tematikát kidolgozta:
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.