Előadás: hétfő 10:15-12:00 helye az első hat hétben
IE217-1 (a tanszéken), előadó Katona Gyula
(kiskat at cs.bme.hu), majd a 6. héttől E.I.B, előadó Friedl
Katalin (az új algel
weboldala)
Gyakorlat: szerda 14:15-15:45
IE217-1 (a
tanszéken), gyakorlatvezető Tóth Ádám
1. előadás (február 6., hétfő): Buborékrendezés algoritmusa, helyessége, lépésszáma; O, Omega és Theta jelölés; Gráfok reprezentációi szomszédossági mátrix, éllista); Gráfbejárások általános elve; Szélességi bejárás (BFS) elve, pszeudokódja, lépésszáma
Függvények nagyságrendje, elágazás és korlátozás, dinamikus programozás (vetített változat)
Gráfok megadása, szélességi keresés és alkalmazásai (vetített változat)
2. előadás (február 13., hétfő): BFS mire jó: összefüggőség eldöntése, magyar módszer, legrövidebb utak élsúlyozatlan gráfokban; Legrövidebb út keresése általános esetben, a negatív körök szerepe; Bellman-Ford algoritmus, Floyd algoritmus;
Legrövidebb utak, Bellmann-Ford, Floyd, Dijkstra (vetített változat)
3. előadás (február 20., hétfő): Dijkstra algoritmus, implementációja, ha a D értékeket tömbben tároljuk, implementáció kupaccal; Kupac: fa és tömbös reprezentáció, mintör és beszúrás algoritmusa és lépésszáma, a kupac szintjeinek száma. Kupac: módosítás algoritmusa és lépésszáma, kupacépítés beszúrással és lineáris időben; Kupacos rendezés;
Kupac adatszerkezet, Dijkstra kupaccal (vetített változat)
4. előadás (február 27., hétfő): Mélységi bejárás (elve, pszeudokódja, kétféle számozás létrehozása), élek osztályozása a mélységi bejárásnál; Topologikus sorrend, DAG definíciója; topologikus sorrend megkeresése mélységi bejárással; az eredeti gráf éleinek osztályozása egy DFS-fához képest. Egy gráf DAG pontosan akkor, ha nincs visszaél a DFS során; DAG-ban legrövidebb és leghosszabb út keresése lineáris időben;
Mélységi keresés (vetített változat)
5. előadás (március 6., hétfő): Minimális súlyú feszítőfa feladat, piros-kék algoritmus; Prim algoritmus (helyessége a piros-kék algoritmusból), lépésszáma tömbös és kupacos implementáció esetén; Kruskal algoritmus (helyesség és lépésszám még nem volt). Kruskal algoritmus (helyesség és lépésszám tömbös implementáció esetén, Unió-holvan csak említve); Eldöntési problémák, P és NP nyelvosztály definíciója;
Minimális költségű feszítőfák (vetített változat)
Bonyolultságelmélet (vetített változat)
6. előadástól (március 13., hétfő): Várhatóan az új algelt tanulókkal együtt, E.I.B-ben lesz az előadás.