Haladó adatszerkezetek és algoritmuselemzési technikák

Advanced Datastructures and Techniques for Analysis of 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)

Haladó adatszerkezetek és algoritmuselemzési technikák

Advanced Datastructures and Techniques for Analysis of Algorithms

Tantárgykód

BMEVISZDV05

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)	4	0	0
jelleg (kapcsolt/önálló)	—	—	—

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

vizsga

Tantárgy kreditértéke

Tantárgyfelelős

DR. Katona Gyula

beosztás: egyetemi tanár

elérhetőség: katona.gyula@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

http://cs.bme.hu/haladoadat/

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. Hashelés haladóknak:

az univerzális hash fogalma, univerzális hash-függvények konstrukciója és

a k-szoros függetlenség, a tökéletes hash.

2. Biztosan konstans keresési idő:

kakukk hash. Keresés randomizáltan kis hibával: Bloom-filter.

3. Átlagos futási idő elemzése:

a munkaerő felvételi probléma gyorsrendezés randomizált változata,

4. Véletlen sorozatból generált bináris keresőfa magassága,

gráf színezési algoritmus várható ideje véletlen gráf esetén.

5-6. Haladó adatszerkezetek és elemzésük: skip list, treap, S-fa (splay tree), szófa,

szuffix-fa (ennek alkalmazásai bioinformatikai problémákra: átfedések keresése,

leghosszabb közös részszó), trie

7. Hálózati folyamok:

Edmonds-Karp algoritmus, Dinitz algoritmus, általánosítások, alkalmazások

8. Adatszerkezetek diszjunkt halmazokra

(unió-holvan adatszerkezet útösszenyomással és ennek elemzése).

Megmaradó (persistent) adatszerkezetek, lusta kiértékelés.

9. Maximális párosítás keresése nem páros gráfokban, Edmonds algoritmusa.

10. Gyors mátrixszorzás, Karatsuba algoritmusa.

11. Paraméteres bonyolultság: Kernel technika, dinamikus programozás

12. Paraméteres bonyolultság: Iteratív összenyomási technika, randomizált algoritmusok

13. Véletlen gráf modellek:

Erdős-Rényi, Barabási. Közösségek keresése szociális hálózatokban.

A tantárgy keretében a hallgatók megismerkednek néhány modern, jól használható adatszerkezettel. Az algoritmusoknak a legrosszabb esetre koncentráló elemzése nem mindig ad elég támpontot a gyakorlati használhatóságról. A kurzus célja, hogy bemutassa és szemléltesse a véletlen (átlagos) esetekre vonatkozó becslések néhány módszerét, és más manapság sokszor alkalmazott technikát (pl. simított vagy paraméteres bonyolultsági elemzés).

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 4 óra előadás.

Tanulástámogató anyagok

Online források

Cormen, Leiserson, Rivest, Stein: Új algoritmusok (Scolar, 2003); Motwani, Raghavan: Randomized Algorithms (Cambridge, 2000); Hromkovic: Algorithmics for hard Problems (Springer, 2004); Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh: Parameterized Algorithms (Springer 2015); internetes források

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 További részletek a tárgy weboldalán: http://cs.bme.hu/haladoadat/

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 További részletek a tárgy weboldalán: http://cs.bme.hu/haladoadat/

Általános szabályok

Követelmények: A vizsgaidőszakban: szóbeli vizsga Elővizsga: lehetséges

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.