Tematika (címszavakban)
2023 tavasz
Az előadások tervezett anyaga és gyakorlati
feladatsorok.
A lezajlott előadások anyagát majd frissítem.
A feladatsorokhoz a megoldások a következő gyakorlat után
kerülnek fel. (A linkek korábban nem működnek.)
- márc. 2.
- márc. 9.
- márc. 16.
- márc. 23.
- márc. 30.
- ápr. 6. tavaszi szünet
- ápr. 13.
- ápr. 20.
- ápr. 27.
- Gyakorló feladatok
- megoldások
- P, NP, tanú tétel
- példák, tanú tétel alkalmazása
- coNP
- Karp-redukció
- máj. 4.
- Szakirány bemutató miatt elmarad
- máj. 5. péntek: ZH
- máj. 11.
- Gyakorló feladatok
- megoldások
- Karp-redukció tranzitivitá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)
- További NP-teljes nyelvek: RH, PARTÍCIÓ
- Rövid
összefoglalás angolul
- máj. 18.
- máj. 17. szerda 18-20: PZH
- Gyakorló feladatok
- megoldások
- 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
- binomiá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
- máj. 25.
- Gyakorló feladatok
- megoldások
- minimumkeresésre n-1 összehasonlítás optimális
- keresésnél a bináris optimális
- buborékrendezés, beszúrásos rendezés
- összefésüléses rendezés, gyorsrendezés
- alsó becslés rendezésnél az összehasonlítások számára;
- ládarendezés, radix rendezés
- jún 1.
Könnyű vagy nehéz??