Adatszerkezetek és algoritmusok

Data Structures and Algorithms

A tantárgyleírás hatályossága

Hatályosság kezdete:

2026. March 21.

Hatályosság vége:

—

Tantárgy neve (magyarul, angolul)

Adatszerkezetek és algoritmusok

Data Structures and Algorithms

Tantárgykód

BMEVISZMB02

Tantárgyjelleg

—

Képzési szint

—

Kurzustípusok és óraszámok (heti/féléves)

Kurzustípus	elmélet	gyakorlat	laboratóriumi gyakorlat
óraszám (heti)	2	1	0
jelleg (kapcsolt/önálló)	—	kapcsolt	—

Tanulmányi teljesítmény/értékelés típusa

vizsga

Tantárgy kreditértéke

Tantárgyfelelős

DR. Csima Judit

beosztás: egyetemi docens

elérhetőség: csima.judit@vik.bme.hu

Tantárgyat gondozó oktatási szervezeti egység

Számítástudományi és Információelméleti Tanszék

Kar

Villamosmérnöki és Informatikai Kar

Tantárgy weboldala

—

Tantárgy elsődleges mintatantervi jellege

—

Közvetlen előkövetelmények – Erős előkövetelmény

nincs

Közvetlen előkövetelmények – Gyenge előkövetelmény

nincs

Közvetlen előkövetelmények – Párhuzamos előkövetelmény

nincs

Közvetlen előkövetelmények – Mérföldkő előkövetelmény

nincs

Közvetlen előkövetelmények – Kizáró feltétel

nincs

Célkitűzés

Tantárgyprogram

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.

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.

Tanulmányi eredmények

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Tudás

Nincsenek rögzített tanulási eredmények.

Képességek

Nincsenek rögzített tanulási eredmények.

Attitűd

Nincsenek rögzített tanulási eredmények.

Autonómia és felelősség

Nincsenek rögzített tanulási eredmények.

Oktatási módszertan

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. 

Tanulástámogató anyagok

Online források

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 

A tantárgy teljesítéséhez ajánlott előzetes ismeretek

Tudás típusú kompetenciák

(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

Alapvető adatszerkezetek és algoritmusok (BSc Algoritmuselmélet tantárgy anyaga)

Képesség típusú kompetenciák

(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)

nincs

Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák

(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)

Alapvető adatszerkezetek és algoritmusok (BSc Algoritmuselmélet tantárgy anyaga)

Általános szabályok

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 Pótlási lehetőségek: A kiszárthelyik nem pótolhatóak.

Teljesítményértékelési módszerek

Szorgalmi időszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Szorgalmi időszakban végzett teljesítményértékelések részaránya

Nincs megadva részarány.

Vizsgaidőszakban végzett teljesítményértékelések részletes leírása

Nincs megadva részletes értékelés.

Vizsgarészek részaránya

Nincs megadva részarány.

Érdemjegy megállapítása

Nincs megadva érdemjegy határ.

Jelenléti és részvételi követelmények

Nincs megadva jelenléti követelmény.

Javítás, ismétlés és pótlás különös szabályai

Nincs megadva.

Rövid leírás

Nincs megadva.

Részletes leírás

Nincs megadva.

Ajánlott tantárgyak

Nincs megadva.

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

Nincs megadva munkaidő bontás.

Tantárgykövetelmények hatályossága

Tantárgykövetelmények hatályosságának kezdete:

—

Tantárgykövetelmények hatályosságának vége:

—

Tantervi elhelyezés

Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.