Tematika (címszavakban)

2016 ősz

   Az első zh anyaga lilával látható, a második zh anyag meg zölddel, a harmadik zh anyaga kékkel.

  1. (szept. 7. szerda): adminisztráció, motiváció. Alapdefiníciók, véges automata, példák. Reguláris nyelvek zártsági tulajdonságai: unió, metszet, különbsgég, komplementer
  2. (szept. 8.) Hiányos VA ekvivalens a teljessel, kétirányban mozgó VA ekvivalens az eredetivel (bizonyítás nélkül). Determinizálás (nemdet VA-ból det készítése), epszilonos VA-ból det VA készítése.
  3. (szept. 14.) Sportnap miatt elmarad.
  4. (szeptember 21.) Reguláris nyelvek zártsága konkatenáltra és tranzitív lezártra, Minimálautomata: szavak megkülönböztetése az L nyelv által, best_L állapot kell minden VA-ba, a minimálautomata állapotai megfelelnek ekvivalencia-osztályoknak, konstrukció minimálautomata előállítására (ezt a következő órán folytatjuk).
  5. (szeptember 22.) Minimálautomata előállítása, ez tényleg jó; Pumpálási lemma reguláris nyelvekre
  6. (szeptember 28.) Reguláris kifejezések, Mese a Python nyelvtanáról és a természetes nyelvek nyelvtanairól (vetített slide-ok), Nyelvtan definíciója, levezetés, generált nyelv, példák.
  7. (október 5., szerda) Példa nyelvtanokra, Chomsky-hierarchia nyelvtanokra és nyelvekre. Reguláris nyelvtanok ugyanazt generálják, amit a véges automaták elfogadnak. Algoritmikus kérdések reguláris nyelvekről, Ötletelés az epszilon-szabályok kiküszöbölésére CF nyelvtan esetén
  8. (október 12., szerda) CF nyelvtanokból epszilon és láncszabályok kiküszöbölése, Pumpálási lemma CF nyelvekre: a lemma kimondása, a^nb^nc^n nyelv nem CF, lemma bizonyításának az eleje
  9. (október 19., szerda) CF pumpálási lemma bizonyításának a vége; CF nyelvek zártsági tulajdonságai; Veremautoma: definíció, működés, példa: a^nb^n nyelv automatája
  10. (október 20., csütörtök) CF nyelvtanból PDA készítése (konstrukció), PDa-ból CF nyelvtan készíthető (csak az állítás); det CF nyelvek, zártsági tulajdonságai, det CF nem azonos a CF-fel;  mese elemzésről: brute-force módszer, LL(k) elemzés, LR(1) elemzés nagyon vázlatosan
  11. (október 26., szerda) Chomsky Normál Forma, ilyenre hozás algoritmusa; Cocke-Younger-Kssami algo, a levezetési fák visszakövetése is; Egyértelműség CF nyelvtanok és nyelvek esetén, nem egyértelmű és egyértelmű CF nyelvtan az aritmetikai kifejezésekre, egyértelműség és det CF kapcsolata
  12. (november 2., szerda) Algoritmikus kérdések CF nyelvtanokról (beletartozás, üresség és végtelenség eldönthető, mindent generál-e, két nyelvtan ugyanazt generálja-e, a nyelvtan egyértelmű-e: nem eldönthető); TG motiváció, 1-szalagos, determinisztikus TG definíciója, TG a palindromákra, R és RE definíciója, R és RE-re vonatkozó Church- Turing tézis
  13. (november 3., csütörtök) k-szalagos determinisztikus TG: definíció, palindrómákra ilyen, k-szalagos szimulálása 1-szalagossal; Nemdeterminisztikus TG: definíció, szimulálás determinisztikussal
  14. (november 9., szerda) Számoló Turing-gép: definíció, példák (összeadás, szorzás); Turing-gép kódolása, van algo arra, hogy egy szóról eldöntsük, hogy TG kódja-e, kell lennie nem rekurzívan felsorolható nyelvnek (számossági megfontolások miatt); Diagonális nyelv definíciója, ez a nyelv nem rekurzívan felsorolható
  15. (november 16., szerda) Univerzális TG; Univerzális nyelv nem rekurzív (de RE-beli), megállási nyelv nem rekurzív (de RE-beli), R és RE zártak metszetre, unióra, R zárt complementerre, RE nem zárt complementerre, R = RE metszet coRE
  16. (november 23., szerda) coX nyelvosztály definíciója, alaptulajdonságai; L_üres komplementere RE-beli, L_üres nem R-beli; Rice tétel és bizonyítása, két példa a Rice tételre
  17. (november 30.) Példák Rice tétel alkalmazására; PCP feladat definíciója, ez RE-ben van (bizonyítással), nincs R-ben (biz. nélkül); Cf nyelvtanok egyértelműsége algoval nem eldönthető (bizonyítással), egyéb CF-es algoritmikus kérdések R-belisége, illetve nem R-belisége (biz. nélkül); Kapcsolat a különböző fajta nyelvtanok és automaták között (biz. nélkül); Turing-gépek tár és időbonyolultsága, (D/N)TIME(f(n)) és (D/N)SPACE(f(n)) osztályok definíciója
  18. (december 1., csütörtök) Kapcsolat a (D/N)TIME és (D/N)SPACE osztályok között, coTIME(t(n)) = TIME(t(n)); P, NP, PSPACE, EXPTIME definíció, ezek kapcsolata, tár-idő tétel;
  19. (december 7., szerda) Nyaus és algeles NP definíció ugyanaz: tanú-tétel; Karp-redukció (ismétlés algelből), NP-teljesség definíciója (ismétlés algelből), Cook-Levin-tétel: SAT nyelv NP-teljes








    20.