Tematika (címszavakban)

2017 ősz

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

  1. (szept. 6. szerda): Definíciók (ábécé, szó, nyelv), véges automata, példák véges automatákra, reguláris nyelv, reguláris nyelvek zártak az unióra, metszetre, különbségre és komplementerre
  2. (szept. 13.): Hiányos véges automata, nemdeterminisztikus véges automata, epszilon-átmenetes véges automata, ezekből hogyan lehet determinisztikus, teljesen specifikált véges automatát csinálni; két reguláris nyelv konkatenáltja reguláris
  3. (szept. 14): Reguláris nyelv tranzitív lezártja reguláris; Minimálautomata
  4. (szeptember 21): Sportnap miatt elmaradt
  5. (szeptember 28.): Pumplási lemma reguláris nyelvekre, Reguláris kifejezések, regkifből VA
  6. (október 4.): VA-ból regkif, A Python és a természetes nyelvek nyelvtanai, Chomsky elmélete, Nyelvtanok: definíció, példák, Chomsky-hierarchia
  7. (október 11.) Nyelvtan, reguláris és CF nyelvtanok, Reguláris nyelvtanok és VA-k egyenértékűsége, eldöntési kérdések reguláris nyelvekről. CF nyelvtanok átalakításai: epszilon-mentesítés, láncszabályok kiküszöbölése;
  8. (október 12.) CF pumpálás, CF nyelvek zártsági tulajdonságai, Veremautomata: definíció
  9. (október 18.) Veremautomata működése, példa; Cf nyelvtanok és veremautomaták egyenértékűsége; determinisztikus veremautomata
  10. (október 25.) determinisztikus PDA, det CF nyelvek, detCF nem egyenlő CF és hogy ez miért nem nagy baj, CYK algoritmus a fák megkeresésével is  (kiegészítés a jegyzethez)
  11. (október 26.) CF nyelvtanok és nyelvek egyértelműsége, az egyértelműség és a det CF kapcsolata; Turing gép: definíció, működés, példa
  12. (november 1.) Munkaszüneti nap miatt elmaradt
  13. (november 8.) 1-szalagos, determinisztikus TG a palindrómák nyelvére, R és RE nyelvosztály definíciója, kapcsolatuk, van nem RE-beli nyelv; k-szalagos determinisztikus TG definíciója, példa: 2-szalagos gép a palindrómákra, k-szalagos mindig szimulálható 1-szalagossal;
  14. (november 9.) Nemdeterminisztikus TG, szimulálása determinisztikussal; Kiszámolós TG, példa,  Church-Turing tézis; 
  15. (november 15.) Turing-gépek kódolása, algoritmussal eldönthető, hogy egy szó TG kód-e, Diagonális nyelv nem RE-beli, Univerzális TG, univerzális nyelv és megállási nyelv RE-ben van, de nem R-beli; R és RE zártsági tulajdonságai: metszetre és unióra igen, komplementerre R zárt 
  16. (november 22.) coX definíciója, tulajdonságai, R = coR, R = RE metszet coRE, L_üres komplementere RE-ben van, L_üres nincs se R-ben, se RE-ben, Rice tétel és bizonyítása, példák 
  17. (november 23.) Példák még Rice tételre; PCP feladat, ez RE-beli, de nem R-beli (ez utóbbi biz. nélkül), CF nyelvtanok egyértelműsége nem eldönthető, egyéb CF-es nem eldönthető problémák: két nyelvtan ugyanazt generálja-e, két nyelvtan nyelvének a metszete üres-e, nyelvtan minden szót generál-e, CF-es eldönthető kérdések: adott szó benne van-e a generált nyelvben, generált nyelv üres-e, véges-e; Nyelvtanok és TG-ek kapcsolata, CS nyelvtanok és lineárisan korlátozott TG-ek kapcsolata, REG, CF, CS, R és RE kapcsolata
  18. (november 29.) tár és időkorlátos TG-ek, TIME, SPACE, NTIME és NSPACE osztályok, ezek kapcsolata, P, NP, PSPACE és EXPTIME osztályok és ezek kapcsolata
  19. (december 6.) PSPACE kapcsolata a többi nevezetes osztállyal, tár-idő tétel; Az algelben tanult és a Nyaus NP definíció ugyanaz: tanú-tétel; Karp-redukció, NP-teljesség, Cook-Levin tétel (csak kimondva egyelőre)
  20. (december 7.) SAT nyelv definíciója, Cook-Levin tétel bizonyítása, lemma további nyelvek NP-teljességének belátásához, 3-SAT NP-teljes, redukció 3-SAT-ról 3-SZÍN-re






    21.