Tematika (címszavakban)
2017 tavasz
- febr. 6.
- mintaillesztés: az egyszerű algoritmus és a
gyorskeresés
- ordo
, omega, teta
- Gyakorló feladatok
- febr. 13.
- determinisztikus véges automata
- hiányos véges automata
- nemdeterminisztikus véges automata
- reguláris nyelvek
- { a^n b^n } nem reguláris
- Gyakorló feladatok
- febr. 20.
- reguláris kifejezés (kicsit más jelölésrendszer, de
lehet játszani)
- környezetfüggetlen nyelvtan
- levezetés, levezetési fa
- egyértelmű szó/nyelvtan/nyelv
- Gyakorló feladatok
- febr. 27.
- veremautomata (nemdeterminisztikus és determinisztikus)
- CF nyelvtan és veremautomata kapcsolata
- van nem CF nyelv
- van nemdeterminisztikus CF nyelv
- az elemzés feladata
- Gyakorló feladatok
- márc. 6.
- Turing-gép fogalma
- 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
- márc. 13.
- P, NP, coNP, példák, tanú tétel alkalmazása
- Karp-redukció
- NP teljesség
- Cook-Levin-tétel
- Példák NP-teljes nyelvekre (SAT, HAM, HAMÚT, 3SZÍN)
- Gyakorló feladatok
- márc. 20.
- 3SAT, 3SZÍN NP-teljes (bizonyítással)
- MAXKLIKK, MAXFTL NP-teljes (bizonyítással)
- További NP-teljes nyelvek: RH, PARTÍCIÓ
- RÉSZGRÁFIZO és GRÁFIZO bonyolultsága
- Gyakorló feladatok
- márc. 27.
- További NP-teljes nyelvek: 3DH, X3C
- Lineáris és egész értékű programozás
- 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ő (és egy hasznos alkalmazás
)
- Gyakorló feladatok
- ápr. 3. Az előadás előtt reggel 8-tól zh!
- LÁDAPAKOLÁS és közelítése (FF, FFD algoritmusok)
- 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
- ápr. 10.
- 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
- rendezés: kiválasztásos, beszúrásos, gyors, összefésülős
- Gyakorló feladatok
- ápr. 17. Húsvét
- ápr. 24.
- alsó becslés rendezésnél az összehasonlítások számára;
- ládarendezés, radix rendezés
- bináris fa bejárások
- bináris keresőfa
- piros-fekete fa
- Gyakorló feladatok
- május 1. szünet
- május 8.
- 2-3-fa (B-fa)
- hash (vödrös és nyitott címzésű)
- Gyakorló feladatok
Következő előadáson várható:
Könnyű vagy nehéz??