Az előadás főbb témái (címszavakban)
A hivatkozott segédanyagok és slide-ok nem egyeznek meg teljesen
azzal, ami az előadáson elhangzik, általában az előadáson kicsit
kevesebb hangzik el. Ha az előadás lényegesen több, mint a
hivatkozott segédanyag, akkor azt jelzem.
A számonkérések anyaga az, ami az előadáson elhangzik.
2020 ősz
- (február 10.):
- mit tanulunk és miért?
- lépésszám becslése, függvények nagyságrendje: ordó, omega,
theta (segédanyag
és slide-ok)
- mintaillesztés: feladat, két algoritmus: egyszerű és
gyorskeresés (segédanyag)
2. (február 17.)
- determinisztikus, teljes véges automata (DVA) definíciója,
működése, elfogadott nyelv
- determinisztikus, hiányos véges automata, egyenértékűsége a
teljes det VA-val
- nemdeterminisztikus véges automata (NVA), működése, számítási
fa, elfogadott nyelv
- determinizálás: NVA-ból ugyanazon nyelvet elfogadó DVA
készítése
- segédanyag
a véges automata és reguláris nyelv témakörhöz
3. (február 24.)
4. (március 2.)
- egyértelmű nyelvtan fogalma, miért akarunk egyértelmű
nyelvtant
- az E-> E+E | E * E | (E) | a nyelvtan nem egyértlemű
- az előző nyelvtan nyelve egyértelmű, mert van rá egyértelmű
nyelvtan
- nemdeterminisztikus veremautomata definíciója, működése,
elfogadott nyelve
- nemdeterminisztikus veremautomata a 0^n1^n nyelvre
- segédanyag
a veremautomatás részhez
5. (március 9.)
- CF nyelvtanból nemdet PDA készítése: példa és az általános
konstrukció
- nemdet PDA-ból is lehet CF nyelvtant csinálni (biz. nélkül),
CF nyelv fogalma
- determinisztikus PDA vázlatosan, ez (sajnos) nem tud annyit,
mint a nemdet PDA, de ez nem baj
- van nem CF nyelv: a^nb^nc^n
- determinizstikus Turing-gép: elve, részei, működése,
elfogadott nyelv
- Turing-gép az a^nb^nc^n-re
- Segédanyag
a Turing-gépes részhez
- Algel
előadás érkezik! Katona tanár úr előadásában, érdemes
meghallgatni :)
6. (március 23., az előadás videója a Teamsen megnézhető)
- véges automata, veremautomata és a Turing-gép kapcsolata
- Church-Turing tézis
- TG kódolható 0-1 ábécé feletti szóval
- diagonális nyelv, erre nincsen Turing-gép
- megállási nyelv, erre van TG, de nincs mindig leálló TG
- mese a megállási nyelvről (miért érdekes ez nekünk, mi a
történeti háttere)
- nemdet TG, ez is csak annyit tud, mint a det TG
- segédanyag a
TG-ekről
7. (március 30., az előadás videója a Teams-en megtekinthető)
- időkorlátos det és nemdet TG, polinom időkorlátos TG-ek
- P és NP
- P robusztus, azaz ami eddig polinomiális volt, az most is az
- NP-re szemléletesebb leírás: tanú-tétel (csak a kimondás és
értelmezés)
- L nyelv komplementere, coNP osztály
- példák P, NP, coNP-beli problémákra
- segédanyag
ehhez a részhez
8. (április 6., videó a Teamsben)
- sejtések P, NP, coNP-vel kapcsolatban
- Karp-redukció:
- definíció
- miért jelenti ez azt, hogy az egyik nyelv maximum olyan
nehéz, mint a másik
- 3-SZÍN-ről 4-SZÍN-re redukció
- NP-teljesség:
- definíció
- Cook-Levin tétel kimondva (de nem bizonyítva), SAT nyelv
micsoda?
- Iszonyú Hasznos Lemma (bizonyítás csak nagyon vázlatosan)
- néhány NP-teljes nyelv felsorolása: H, H-út, 3-SZÍN, 4-SZÍN,
MAXFTLEN, MAXKLIKK
- Ha Y NP-teljes és P-beli is, akkor P=NP lenne
- Katona
tanár úr slide-jai ehhez a részhez (de mi ennél kevesebet
vettünk)
9. (április 20., videó a Teamsben van)
- Iszonyú Hasznos Lemma bizonyítása
- Még két NP-teljes nyelv definíciója: RH, PARTÍCIÓ
- Redukció MAXFTLEN-ről MAXKLIKK-re
- Mit lehet tenni, ha NP-teljes problémát kell megoldani?
- Lehet, hogy speciális esetben meg tudjuk oldani: leghosszabb
út keresése NP-teljes, de DAG-ban könnyű
- Átírjuk Egészértékű Lineáris Programozásra:
- Lineáris és Egészértékű programozási (EP) feladat micsoda
- EP NP-teljes, mert MAXFTLEN visszavezethető rá
- Miért jó mégis EP-re átírni dolgokat, ha az NP-teljes?
- Branch-and-bound algoritmusok elve, egy példa erre:
3-színezés
10. (április 27., videó a Teamsben)
- Közelítő algoritmusok:
- alapgondolat
- c-közelítő algo definíciója
- Ládapakolás feladat
- FF és FFD algoritmusok demo
- FF 2-közelítő a Ládapakolásra
- Dinamikus programozás:
- elve
- n-edik Fibonacci szám kiszámolása
- legnagyobb összegű résztömb meghatározása
- leghosszabb növekvő résztömb meghatározása
- emlékeztető korábban tanult DP algokra:
- Bellman- Ford
- Floyd
- DAG-ban legrövidebb és leghosszabb út keresése egy
csúcsból
11. (május 4., videó a Teamsben)
- Dinamikus programozás:
- Hátizsák feladat
- RH feladat
- Keresés, rendezés:
- minimum és maximum keresése n-1 összehasonlítással
- lineáris és bináris keresés
- beszúrásos rendezés
- összefésüléses rendezés
12. (május 11., videó a Teamsben)
- Rendezések:
- buborékrendezés
- gyorsrendezés
- alsó korlát az összehasonlítás-alapú rendező algoritmusok
lépésszámára
- ládarendezés
- raxidrendezés
- linkek a rendezésekhez:
- keres, beszúr és töröl láncolt listában és rendezett tömbben
- bináris fa, bináris keresőfa
- pre-, in-, és poszt-order fabejárás
- keresés és beszúrás bináris keresőfába
13. (május 18., videó a Teamsben)
- törlés bináris keresőfából
- bináris keresőfa magassága log n és n között lehet
- mese AVL-fáról
- 2-3 fa: definíció, példa, keresés, beszúrás (törlésnél csak
lépésszám), a fa magassága
- hash: alapgondolat, vödrös hash, nyílt címzés: lineáris próba,
kvadratikus próba és kettős hash