Algoritmuselmélet előadás

(VISZA213, régi algel)



2016/2017 tavasz

Órák helye és ideje

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

Általános tudnivalók:
Ez a weboldal a régi Algoritmuselmélet tantárgyhoz tartozik, melynek kódja VISZA213. Ezt a tárgyat a régi (VISZA110-es) Bsz2-t elvégzett hallgatók vehetik csak fel (és ők csak ezt vehetik fel, az új algelt nem), a többieknek a VISZB01-es kódú szintén Algoritmuselmélet nevű új tárgyat kell felvenniük.

Ebben a félévben  a régi algel oktatása úgy zajlik majd, hogy a félév első 5-6 hetében a régi és az új tárgy előadásai azonos időpontban, de külön teremben, különböző tematikával zajlanak majd, a félév hátralevő részében pedig mindenki egy közös előadásra jár.
Mivel a régi és az új tárgy anyaga jelentősen különbözik, ezért a zh és vizsga is különbözni fog.

Figyelem! Noha a régi algel eféléves anyaga megegyezik a korábbi félévekben oktatott anyaggal, a témák sorrendje megváltozott, emiatt a korábbi évek zhba tartozó anyaga nem egyezik meg az idei év zhjának anyagával.

Az aláírás és jegyszerzés követelményei (amik a korábbi félévekhez képest nem változtak) itt olvashatóak.

Zh:         április 3. hétfő 8-10

Pótzh:    április 21, péntek 8-10

Mit tervezünk  az előadáson?
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.



 Segédanyagok