Algoritmuselmélet előadás

(VISZA213, régi algel)



2015/2016 tavasz

Órák helye és ideje

Előadás: hétfő 10:15-12:00   helye az első hat hétben IB134 (a tanszéken), előadó Csima Judit (csima at cs.bme.hu), majd a 7. héttől QI, előadó Friedl Katalin  (az új algel weboldala)             

Gyakorlat:  szerda 14:15-15:45   IB134 (a tanszéken), gyakorlatvezető Soltész Dániel  (protosdrone at gmail.com)

Á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 11., eredmények itt

Pótpótzh:  május 24., 12-14 IB028, a Neptunban jelentkezni kell rá

Mi volt az előadáson?

   
    1. előadás (február 15., 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

   2. előadás (február 22., 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;

  3. előadás (február 29., 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.

  4. előadás (március 5., szombat): 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; 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

  5. előadás (március 7., hétfő):  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; 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)

 6. előadás (március 21., hétfő):  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; Karp-redukció, példa: 3-SZÍnről 4-SZÍNre; NP-teljesség definíciója, Cook-Levin tétel kimondva

7. előadástól (április 4., hétfőtől): Az új algelt tanulókkal együtt, Q-I-ben lesz az előadás.

 Segédanyagok