BME VIK - Adatszerkezetek és algoritmusok

3. A tantárgyfelelős személy és tanszék Dr. Csima Judit,

4. A tantárgy előadója

Dr. Csima Judit,      egyetemi docens, SZIT 

Dr. Friedl Katalin,   egyetemi docens, SZIT

Dr. Katona Gyula,   egyetemi docens, SZIT 

5. A tantárgy az alábbi témakörök ismeretére épít Alapvető adatszerkezetek és algoritmusok (BSc Algoritmuselmélet tantárgy anyaga)

7. A tantárgy célkitűzése

A tantárgy célja a BSc képzésből kimaradt legfontosabb, sok helyen használt adatszerkezetek és algoritmusok megismertetése.

A tantárgy követelményeit eredményesen teljesítő hallgatóktól elvárható, hogy: 

 (1) ismerjék az előadáson elhangzó módszereket, 

 (2) megértsék a módszerek helyességének és hatékonyságának bizonyítását,

 (3) képesek legyenek a tanultak alkalmazásával feladatokat megoldani,

 (4) képesek legyenek felismerni az alkalmazási lehetőségeket, fel tudják fedezni, milyen kisebb módosításokra van esetleg szükség az alkalmazásokhoz és ezt átgondolt módon meg is tudják valósítani.

8. A tantárgy részletes tematikája

1. 1. k. elem keresés várhatóan lineáris időben és determinisztikus lineáris időben. A dinamikus eset – bináris keresőfa kibővítése
2. 2. Bináris keresőfák további alkalmazásai: legkisebb közös ős keresése, intervallumba eső minimum keresése. Intervallumfák.
1. 3. Alapvető síkgeometriai algoritmusok (metsző szakaszpár, legközelebbi pontpár keresése, konvex burok)
1. 4. Hash-elés elméleti és gyakorlati változatai: lineáris próba, dupla hash módosítása. Univerzális hash, hosszabbítható hash.
2. 5. Folyamalgoritmusok: Ford-Fulkerson-algoritmus, és ennek javítása az Edmonds-Karp-algoritmus.
2. 6. Hatékonyabb folyamalgortimusok: mohó javítás. Előfolyam módszer, előreemelő algoritmus.
2. 7. Mintaillesztés: egyszerű algoritmus, gyorskeresés. A lineáris idejű Knuth-Morris-Pratt-algoritmus
2. 8. A dinamikus programozás néhány alkalmazása: közelítő mintaillesztés, szerkesztési távolság, leghosszabb közös részsorozat, egy egyszerű bioinformatikai alkalmazás.
2. 9. Az algoritmusok hatékonyságának egy, a tapasztalatokhoz sokszor közelebbi eredményt adó elemzési módszere: amortizált elemzés és ennek néhány alkalmazása.
2. 10. Gráfok minimális feszítőfájának keresése: az általános piros-kék algoritmus, Prim, Boruvka, Kruskal algoritmusa, mint ennek alkalmazásai.
2. 11. A Kruskal algoritmushoz is szükséges unió-holvan adatszerkezet különböző megvalósításai, ezek (amortizált) elemzése.
2. 12. Nagy számok gyorsabb szorzása Karacuba módszerével. Nagy mátrixok gyorsabb szorzása. A gyors-Fourier transzformáció és alkalmazásai.
2. 13. Ismétlés, tartalék.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Heti 2 óra előadás és 1 óra gyakorlat. Az anyag egy részét önálló munkával, kiadott anyagokból kell elsajátítani.

A gyakorlatokon az előadáson tárgyalt anyagrésszel kapcsolatos feladatokat oldanak meg a hallgatók. 

10. Követelmények

Szorgalmi időszakban: 3 kiszárthelyi, egy kiszárthelyi akkor sikeres, ha legalább 50%-os. Az aláírás feltétele 2 sikeres kiszárthelyi.

Vizsgaidőszakban: szóbeli vizsga

11. Pótlási lehetőségek A kiszárthelyik nem pótolhatóak.

12. Konzultációs lehetőségek Az előadóval való egyeztetés szerint.

13. Jegyzet, tankönyv, felhasználható irodalom

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTeX Kiadó 

Thomas H. Cormen,  Charles E. Leiserson , Ronald L. Rivest,  Clifford Stein: Új algoritmusok Scolar Kiadó, 2003 

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	42
Félévközi készülés órákra	28
Felkészülés zárthelyire	9
Házi feladat elkészítése
Kijelölt írásos tananyag elsajátítása	28
Vizsgafelkészülés	43
Összesen	150

15. A tantárgy tematikáját kidolgozta

dr. Csima Judit egyetemi docens SZIT 

dr. Friedl Katalin egyetemi docens SZIT

dr. Katona Gyula egyetemi docens SZIT 