Tematika (címszavakban), Elmszámtud

2020 tavasz

• technikai tudnivalók: órák beosztása, követelmények
  
• miről lesz szó a tárgyban?
• 1-szalagos, determinisztikus Turing-gép (nagyjából ismétlés algelből): definíció, működés, példák
• k-szalagos Turing-gép (ismétlés): definíció, működés, példák

2. óra (február 12.):

• k-szalagos TG szimulálása 1-szalgos Turing-géppel, mi történik a lépésszámmal közben?
  
• R és RE definíciója, van nem RE-beli nyelv
• nemdeterminisztikus TG, működése, elfogadott nyelv
• Church-Turing tézis R és RE-re
  
• nemdeterminisztikus TG szimulálása determinisztikussal

      3. óra (február 17.)

• nemdeterminisztikus TG, egyenértékűsége a det TG-pel (ismétlés algelből)
• egy konkrét kódolás TG leírására
• TG-kódok nyelve R-ben van
• diagonális nyelv definíciója, diagonális nyelv nem RE-beli

 
     4. óra (február 19.)

• univerzális Turing-gép, univerzális nyelv, RE-ben van, de nincs R-ben
• megállási nyelv, RE-ben van, de nincs R-ben
• mese a megállási nyelvről
• R és Re zárt unióra és metszetre
• coX nyelvosztály fogalma
• coR = R, R = RE metszet coRE

     5. óra (február 24.)

• L_üres coRE-ben van
• Ha L_üres nincs R-ben (ez lesz jövő órán), akkor nincs RE-ben sem az R = RE metszet coRE miatt
  

    6. óra (február 26.)

• L_üres nincs benne R-ben
• Rice-tétel kimondva, megértve, példák

   7. óra (március 2.)

• Rice-tétel bizonyítása
• Kiszámolós TG: definíció, kiszámolt függvény, példa, Church-Turing tézis függvényekre

   8. óra (március 4.)

• Felsorolós TG
• L RE-ben van pontosan akkor, ha van Tg, ami felsorolja a szavait
• L R-ben van pontosan akkor, ha van TG, ami hosszúság szerint felsorolja a szavait
• PCP: definíció, példák, RE-ben van, de nincs R-ben (ez utóbbi nem bizonyítva)
• Dominó nyelv: coRe-ben van, de nincs R-ben (ez utóbi nem bizonyítva), tehát nincs RE-ben sem

  9. óra (március 9.)

• reagálás a post-ites kérdésekre
• PCP eldöntésének visszavezetése a CF nyelvtanok egyértelműségére, CF nyelvtanok egyértelműségét nem lehet algoval eldönteni
• Tár és időkorlát TG-ekre detreminisztikus és nemdeterminisztikus esetben
• (D)TIME, (D)SPACE, NTIME és NSPACE osztályok tulajdonságai
• P, NP, PSPACE, EXPTIME definíciója, ezek közötti (egyszerű) kapcsolatok 
  

10. óra (március 11.)

• NP része EXPTIME-nak, NP része PSPACE-nek, P = coP, coNP is része EXPTIME-nak
  
• Tár-idő tétel és következményei: PSPACE része EXPTIME-nak, SPACE(bármi) része R-nek, PSPACE = coPSPACE

11. óra (március 23., online)

• NP-re másik definíció: tanú-tétel
• P, NP, coNP körüli sejtések

12. óra (március 25., online)

• Karp-redukció
• NP-teljesség