Tematika (címszavakban)

2014 tavasz

1. (febr. 10.):
   • ordo, omega, teta
   • elágazás és korlátozás (független pontok)
   • elágazás és korlátozás (színezés)
   • dinamikus programozás (binom együtthatók, hátizsák)
2. (febr. 17.):
   
   • gráfok megadása
   • szélességi bejárás
   • összefüggőség eldöntése (irányítatlan)
   • páros gráfban max párosítás
3. (febr. 24.):
   
   • legrövidebb utak (súlyozatlan)
   • legrövidebb utak (súlyozott): Bellman-Ford, Floyd, 
   • Dijkstra algoritmus
     
4. (márc. 3.)
   
   • Dijkstra-algoritmus helyességének bizonyítása
     
   • adatszerkezetek (bináris fa, kupac )
   • Dijkstra kupaccal
5. (márc. 10.)
   
   • keresés (lineáris, bináris)
   • alsó becslés az összehasonlítások számára
   • minimumkeresés
   • összehasonlításos rendezések: beszúrásos, buborék
   • alsó becslés az összehasonlítások számára
   • összefésüléses rendezés
6. (márc. 17.) 
   
   • kupacos-, gyors-ládarendezés, radix rendezés 
   • radix bizonyítása, lépésszáma
   • bináris fa pre-, in- és postorder bejárása
   • bináris keresőfa
7. (márc. 24.) 
   
   • piros-fekete fa (tulajdonságok, KERES, MIN,MAX)
     
   • piros-fekete fa (BESZÚR,TÖRÖL)
   • 2-3 fa
   • B-fa (ZH anyaga eddig tart)
     
8. (márc. 31.) 
   
   • Hash (ötlet, vödrös hash) 
   • nyitott címzésű hash
   • hash-függvények
   • gráfok mélységi bejárása DFS
9. (ápr. 7.)
   
   • topologikus rendezés, dag
   • dagban legrövidebb, leghosszabb út
   • erős összefügőség eldöntése
     
   • minimális feszítőfa -- piros-kék algoritmus
   • Jarnik-Prim-algoritmus (mátrixos, illetve éllistás+kupacos változat)
10. (ápr. 14.)
    
    • Boruvka-algoritmus
    • Kruskal-algoritmus
    • Unió-holvan adatszerkezet
11. (ápr. 21.) szünet
    
12. (ápr. 28.)
    
    • eldöntési problémák
    • P, NP, coNP és kapcsolatuk
    • Karp-redukció, alaptulajdonságok
13. (máj. 5.)
    • NP-teljesség
      
    • a 3SZÍN probléma NP-teljes (biz nélkül)
    • További NP-teljes problémák: MAXFTL, MAXKLIKK, H, HÚT,  RH, PARTÍCIÓ, HÁTIZSÁK, RÉSZGRÁFIZO
      
    • GRÁFIZO: NP-beli, de nem tudjuk, teljes-e
    • LP (lineáris programozás) P-ben van (biz. nélkül)
    • egészértékű programozás -- NP-teljes
14. (máj. 12.)
    
    • c-közelítő algoritmusok
    • Utazóügynök probléma közelítése is nehéz
    • Euklideszi utazóügynökre 2-közelítő algoritmus
    • LÁDAPAKOLÁS NP-teljes, First Fit algoritmus 2-közelítősége (pontos arány biz. nélkül)