BSc-s Algoritmuselmélet tematika (VISZA213)
(2010/11. őszi félév)
előadás: szept. 6.
Bevezetés, motiváció.
Nagyságrendek.
Elágazás és korlátozás: maximális független ponthalmaz keresése.
Dinamikus programozás: binomiális együtthatók.
előadás: szept. 13.
Dinamikus programozás: hátizsák probléma.
Gráfok ábrázolása: szomszédossági mátrix, éllista.
Szélességi bejárás (BFS).
BFS alkalmazásai:
összefüggő komponensek
maximális párosítás páros gráfban (magyar módszer)
előadás: szept. 20.
Legrövidebb utak súlyozatlan gráfban.
Legrövidebb utak súlyozott gráfban: Bellmann-Ford, Floyd, Dijkstra.
előadás: szept. 27.
Kupac adatszerkezet: kupacépítés, műveletek, d-kupac.
Keresések: lineáris, bináris.
előadás: okt. 4.
Rendezések: kupacos, buborék, beszúrásos, összefésüléses, gyorsrendezés.
Alsó becslés a rendezés lépésszámára.
előadás: okt. 11.
Kulcsmanipulációs rendezések: láda, radix.
Bináris fák bejárásai.
Keresőfák.
előadás: okt. 18.
Piros-fekete fák.
előadás: okt. 25.
2-3-fák.
B-fák.
Vödrös hash.
Nyitott címzésű hash: lineáris és kvardratikus maradék próba, kettős hash.
előadás: nov. 8.
Jó hash-függvények.
Hashelés összehasonlítása keresőfákkal.
Mélységi bejárás (DFS).
DAG, irányított kör keresése.
előadás: nov. 15.
Topologikus rendezés.
Legrövidebb és leghosszabb utak DAG-ban.
Erősen összefüggő komponensek meghatározása.
Minimális súlyú feszítőfák: piros-kék algoritmus.
Prim algoritmusa.
előadás: nov. 22.
Kruskal, Boruvka algoritmusai.
P, NP osztályok.
előadás: nov. 29.
coNP osztály.
Karp-redukció.
NP-teljesség, példák NP-teljes nyelvekre.
előadás: dec. 6.
További példák NP-teljes nyelvekre.
Izomorfia probléma bonyolultsága.
Közelítő algoritmusok: maximális párosítás, ládapakolás.