Tematika (címszavakban)

2012 ősz

1. előadás (szeptember 3.) : bevezető, függvények nagyságrendje (ordó, omega, theta), dinamikus programozás

Szeptember 10-én elmarad az előadás, sportnap miatt.

2. előadás (szeptember 17.): Hátizsák feladat dinamikus programozással; Gráfok megadása (mátrixos és éllistás megadás); Szélességi bejárás és alkalmazásai: összefüggőség eldöntése, legrövidebb utak élsúlyozatlan esetben, gráf párosságának eldöntése, magyar módszer

3. előadás (szeptember 24.):  Legrövidebb élsorozat keresésének alapfeladata; Bellman-Ford algoritmus, Floyd algoritmus (Warshall algoritmusa), Dijkstra algoritmusa

4. előadás (október 1.): Dijkstra algoritmus jóságának igazolása; Kupac adatszerkezet: definició, kupacol eljárás, kupacépités lineáris időben, MINTÖR, BESZÚR, MÓDOSIT; Dijkstra algoritmus éllistásan, kupaccal

Október 5-én az infós gyakorlatok Schönherz-kupa miatt elmaradnak 

5. előadás (október 8.): Rendezési reláció; Keresés rendezett halmazban: lineáris és bináris keresés; Összehasonlitás-alapú rendezések: beszúrásos, buborék, összefésüléses és kupacos rendezés, gyorsrendezés

6. előadás (október 15.): Láda- és radixrendezés; Bináris fák bejárásai (pre-, in-, poszt-); Bináris keresőfa, ebben keresés, beszúrás, min, max, tólig és törlés. Eddig tart a zh anyaga.

7. előadás (október 27., szombat, az október 22-i előadás helyett): Piros-fekete fák (definició, szintszám, beszúrás részletesen, törlés vázlatosan); 2-3 fák (definició, szintszám, keresés, beszúrás)

8. előadás (október 29.): 2-3 fákban törlés; Hash: vödrös hash, nyilt cimzés: lineáris próbálás, kvadratikus maradék próba, kettős hash

ZH: október 31., szerda, 18-20

9. előadás (november 5.): irányított gráf mélységi bejárása (mélységi és befejezési számozás, élek osztályozása); DAG, DAG-ság eldöntése mélységi bejárással; topologikus sorrend; legrövidebb és leghosszabb utak DAG-ban; irányítatlan gráf mélységi bejárása

November 10-én szombaton lesznek megtartva a november 2-i gyakorlatok

10. előadás (november 12.): Minimális súlyú feszítőfa keresése: piros-kék algoritmus; Jarnik-Prim algoritmus naív és kupacos implementációval; Kruskal algoritmus UNIO-HOLVAN adatszerkezettel

Pótzh: november 16., péntek 14-16

11. előadás (november 19.): Bonyolultságelmélet: eldöntési probléma; P nyelvosztály; hatékony tanúsítvány, NP és coNP nyelvosztály, ezek kapcsolata egymással és P-vel; Karp-redukció, NP-nehéz és NP-teljes nyelv definíciója

November 23-án a gyakorlatok elmaradnak nyílt nap miatt.

12. előadás (november 26.): Ha X Karp-redukálható Y-ra és Y P-beli, NP-beli, coNP-beli, akkor X is ilyen; a Karp-redukció tranzitív; NP-teljes problémák: 3SZIN (biz nélkül), MAXFTLEN, MAXKLIKK, H (biz nélkül), H-ut (biz nélkül), s-t-H-UT (biz nélkül), RÉSZGRÁFIZO, RH (biz nélkül), PARTICIO (biz nélkül) , HÁTIZSÁK (biz nélkül)  

13. előadás (december 3.) : Technikák NP-teljes esetben: Branch-and-bound (3SZIN, MAXFTLEN); Közelítő algoritmusok: csúcsfedés, Ládapakolás
(FF 2-es közelítés bizonyítással is, FFD), TSP: közelíthetetlensége, metrikus esetben 2-es közelítés bizonyítással is; Randomizálás (Fermat-teszt)