Nyelvek és automaták (VISZMA12)

2024 ősz

Ugyanez a matematikusoknak Elméleti számítástudomány   néven fut (a korábbi ilyen nevű tantárgy utódja), az órák, számonkérések közösek.

• Előadás:  szerda 8-10,   IB027 és páratlan tanítási héten  Cs 10-12,  IB027 is.
• Előadó: Friedl Katalin,  IB137/A, email, weboldal
  
• Konzultáció:  Igény esetén
• Számonkérés:
  Két 90 perces zh lesz. Ezeken az anyaghoz kapcsolódó feladatokat kell megoldani, illetve az órai anyagot számonkérő elméleti kérdés(ek)re kell válaszolni.
  
  • Mindegyik zh-n legalább 40%-ot el kell érni a legalább elégséges jegyhez.
  • A félévi jegy a zh-pontszámok átlagából (kerekítés nélkül!) keletkezik.
  • Minden zh a hozzá tartozó pótzh-n pótolható/javítható.
  • Nincs pótpótzh alkalom!

A félév során lesz néhány beadható feladat, amelyekkel a zh-kból kapott pontátlagot lehet (kicsit) felfelé módosítani.

Az 1. zh anyaga: A Turing-gépek már em, de addig minden (CYK és az egyéb algoritmikus kérdéesk is). Vigyázat, 2023-ban máshol volt a határ!

Eredmények: a kari Moodle-ban.
Tájékoztatásul: átlagpontszám: 36, legtöbb pont: 59 (gratulálok!), legkevesebb pozitív pont: 1, jegyátlag: 3,1.
A dolgozatok megnézhetők a szerdai óra után, a csütörtöki óra előtt és (korlátozottan) az órák szünetében is. Továbbá egyéb, emailben egyeztetett időpotban.

Anyaga: ugyanaz, mint az 1. zh anyaga.

Aki nem ért el az 1.zh-n legalább 24 pontot, annak ebben a félévben ez a lehetőség maradt.

Aki elért annyit, az, ha akar, jöhet javítani (de kérem jelezze a szándékát).
Figyelem, aki bead dolgozatot, annál a pótzh eredménye felülírja az esetleges zh-eredményét -- kivéve, ha az 1.pótzh-n nem éri el a 24 pontot, de az 1.zh-n volt legalább 24 pontja. Ebben az esetben a pontszám nem az 1.pótzh eredményére, hanem 24-re csökken.

Eredmények a moodle-ban.
Tájékoztatásul: átlagpontszám: 26, legtöbb pont: 54 (gratulálok!), legkevesebb pozitív pont: 1, jegyátlag: 2,1.
A dolgozatok megtekinthetők a szerdai (nov. 13.) előadás után, esetleg a szünetben, vagy egyéb, egyeztetett időpotban.
Az esetleges kérdésekkel keressenek meg.

Anyaga: ugyanaz, mint a 2. zh anyaga

  1. Véges automaták   (megoldások) ,    2. Minimalizálás    (megoldások)    3. Reguláris kifejezés, pumpálási lemma    (megoldások)    4. Nyelvtanok    (megoldások)    5. Környezetfüggetlen nyelvek     (megoldások)    6. CF pumpálás    (megoldások)    7. CYK, algoritmikus feladatok    (megoldások)    8. Turing-gépek, R, RE      (megoldások)    9. R, RE, Rice-tétel    (megoldások)    10. Dominó, PCP, CF problémák   

Plusz pontért beadható feladatok (időnként bővülő lista, 1-2 hetes határidőkkel): Extra feladatok

Az extra feladatok megoldásait pdf-ben lehet elküldeni emailben vagy papíron az előadás elején beadhatók (esetleg korábban is a tanszéki adminisztárcióban).

Egy python és egy C nyelvtan.

  A játékok is lehetnek nehezek.

☺Egy beszélt nyelv is lehet nem CF

☺Melyik a legnehezebb nyelv?