Tematika (címszavakban)

2018 tavasz

A gyakorló feladatok a jövőbeli időpontoknál az előadás tervezett anyaga és tavalyi gyakorlati feladatsorok. A lezajlott előadások és gyakorlatok anyagát  frissítem.

1. febr. 5.
   
• mintaillesztés: az egyszerű algoritmus és a gyorskeresés 
• ordo , omega, teta
• Gyakorló feladatok


2. febr. 12.
   
   • determinisztikus véges automata
   • hiányos véges automata
   • nemdeterminisztikus véges automata
   • Gyakorló feladatok, új változat
     


3. febr. 19.
• reguláris nyelvek
• { a^n b^n } nem reguláris
• reguláris kifejezés  (kicsit más jelölésrendszer, de lehet játszani)
  
• környezetfüggetlen nyelvtan
• levezetés
  
• Gyakorló feladatok


4. febr. 26.
• levezetési fa
• egyértelmű szó/nyelvtan/nyelv
• veremautomata (nemdeterminisztikus és determinisztikus)
  
• CF nyelvtan és veremautomata kapcsolata
• Gyakorló feladatok


5. márc. 5.
• van nem CF nyelv
• van nemdeterminisztikus CF nyelv
  
• az elemzés feladata (a Python nyelvtana)
  
• Turing-gép fogalma (Turing-gép példák animációval)
  
• Gyakorló feladatok

márc. 10. szombat: gyakorlat márc. 16. péntek helyett


6. márc. 12.
• diagonális nyelv
  
• megállási nyelv (+ egy bizonyítás az érdeklődőknek)
• Church-Turing-tézis
• nemdeterminisztikus TG és determinizálása
  
• P, NP, tanú tétel
• Gyakorló feladatok


7. márc. 19.
• coNP, példák, tanú tétel alkalmazása (eddig tart a ZH anyaga)
  
• Karp-redukció
• 2017zh
  2016zh
  


8. márc. 26. ZH 8:15-10:00
   
• Karp-redukció tranzitívitása, NP teljesség
  
• Cook-Levin-tétel
• Példák NP-teljes nyelvekre (SAT, HAM, HAMÚT, 3SZÍN)
• 3SAT, 3SZÍN  NP-teljes (bizonyítással)
• MAXKLIKK, MAXFTL NP-teljes (bizonyítással)
• Gyakorló feladatok
  




9. ápr. 9.  
   
• További NP-teljes nyelvek: RH, PARTÍCIÓ
• RÉSZGRÁFIZO és GRÁFIZO bonyolultsága
• További NP-teljes nyelvek: 3DH, X3C
• Lineáris és egész értékű programozás (demo1, demo2)
  Vicces video NP-ről
  Dal a bonyolultságelméletről
• Rövid összefoglalás angolul
  
• Gyakorló  feladatok


10. ápr. 16. PZH 8:15-10:00
• Algoritmusok: elágazás és korlátozás (független pontok, 3-színezés)
• Közelítő algoritmusok
• UTAZÓÜGYNÖK közelítése is nehéz, euklideszi változat közelíthető (egy játék és egy hasznos  alkalmazás )
• LÁDAPAKOLÁS és közelítése (FF, FFD algoritmusok) demo
  
• Dinamikus programozás
• binomális együtthatók
• maximális hosszú növekvő intervallum és részsorozat
• maximális részösszegű intervallum
• a hátizsák probléma
• Gyakorló feladatok


11. ápr. 21.szombat, ápr. 30. hétfő helyett, hétfői gyakorlatok is
    
• az optimális érték mellett az optimális megoldás megtalálása
• minimumkeresésre n-1 összehasonlítás optimális
• keresésnél a bináris optimális
• Gyakorló feladatok


12. ápr. 23.


• rendezés: kiválasztásos, beszúrásos, gyors, összefésülős
• alsó becslés rendezésnél az összehasonlítások számára;
• ládarendezés, radix rendezés
• Gyakorló feladatok
ápr. 30. munkanap áthelyezés miatt elmarad, helyette ápr. 21.


13. május 7.
• bináris fa bejárások
• bináris keresőfa
• piros-fekete fa
• Gyakorló feladatok
14. május 14.
• 2-3-fa (B-fa)
  
• hash (vödrös és nyitott címzésű)
• Gyakorló feladatok