Alapvető algoritmusok

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

Áttekintve az alapvető automatatípusokat,  a félév során megvizsgáljuk, melyik típus mire alkalmas. Az automaták vizsgálata szorosan összefonódik a formális nyelvek vizsgálatával. Cél a klasszikus automaták és a formális nyelvek közötti kapcsolatok mélyebb leírása. A hallgatók megismerik a fordítóprogramok készítése során használható elméleti alapokat is. A Turing-gépek kapcsán megvizsgáljuk egyes elméleti és gyakorlati problémák és nyelvek algoritmikus eldönthetőségének kérdését.

1) Véges automaták, reguláris nyelvek  átismétlése. Minimálautomata. Véges automaták megfeleltetése a reguláris kifejezésekkel A reguláris nyelvek zártsági tulajdonságai: halmazműveletek, konkatenálás, tranzitív lezárt.  

2) A reguláris pumpálási lemma és alkalmazása. Példák reguláris és nem reguláris nyelvekre. Chomsky-féle nyelvosztályok. Reguláris nyelvtanok és reguláris nyelvek kapcsolata. Veremautomaták, környezetfüggetlen nyelvek és nyelvtanok (ismétlés). Üres veremmel elfogadó veremautomata. 

3) Környezetfüggetlen nyelvtanok átalakításai, normálformák. A környezetfüggetlen nyelvek zártsági tulajdonságai. A pumpálás környezetfüggetlen változatai, (pumpálási és Ogden-lemma) alkalmazásuk, példák.

4) Determinisztikus és nem determinisztikus környezetfüggetlen nyelvek fogalma. A veremautomaták nem determinizálhatók. Algoritmikus kérdések: üresség, különbözőség reguláris és környezetfüggetlen esetben. Az elemző feladata: a beletartozás eldöntése.

5) Cocke-Younger-Kasami-algoritmus. Általános elemzői módszerek. Kimenettel rendelkező automaták. Melay-, Moore-automaták, Véges fordítók. A reguláris nyelvek zártsága a véges fordításra. Veremfordító és szintakszisvezérelt fordítási séma.

6) A Turing-gép definíciója, a különféle definíciók ekvivalenciája (több szalagos, nemdeterminisztikus). Eldönthetőség és felismerhetőség (rekurzív, ill. rekurzívan felsorolható nyelvek). Számoló Turing-gép.

7) Church-Turing-tézis. Univerzális Turing-gép létezése.  A diagonális nyelv nem rekurzívan felsorolható. Az univerzális nyelv és megállási nyelv rekurzívan felsorolható, de  nem rekurzív.

8) Az R osztály zárt a műveltekre, az  RE osztály a komplementerképzés kivételével zárt. Komplementer nyelvosztályok. R a RE és coRE  metszete. További nem eldönthető nyelvek: Church-tétel, üres nyelv.

9) A nemtriviális nyelvi tulajdonságok eldönthetetlensége: Rice-tétel. Ennek alkalmazásai. Dominóprobléma. Post megfeleltetési problémája, és alkalmazása CF-nyelvekkel kapcsolatos kérdések eldönthetetlenségének bizonyítására.

10) Az 1. Chomsky-féle nyelvosztály, a két definíció egyenértékűsége. A 0. Chomsky-féle nyelvosztály és az RE kapcsolata.

11) Időigény és tárigény, idő- és tárkorlátos Turing-gépek.  A tár-idő tétel. TIME és SPACE osztályok zártsága a műveletekre. Nemdeterminisztikus idő és tárigény.  A  P, NP, coNP, PSPACE, EXPTIME osztályok, kapcsolatuk.

12) Egy reálisabb számítási modell a RAM-gép. A RAM-gép és a Turing-gép egyenértékűsége, idő- és tárbonyolultságuk kapcsolata.

13)  Kolmogorov-bonyolultság fogalma.  Algoritmikus tömörítés és a Kolmogorov-bonyolultság. Kapcsolat a véletlenszerűséggel. Az optimális tömörítés mértékének eldönthetetlensége.

14) Ismétlés, összefoglalás, tartalék.

A félév során 2 zárthelyit iratunk. A félév teljesítésének feltétele: minden zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a  zárthelyik átlagából adódik.

A vizsgaidőszakban: --

Elővizsga:

A szorgalmi időszak során minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség.

A pótlási héten egyetlen alkalom lesz amikor egy tetszőleges zh dolgozat pótolható.

Hetente adunk ki gyakorló feladatokat, melyeket egy egyeztetett időpontban tartott heti konzultáción az érdeklődőkkel megbeszélünk.

Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet.

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTex, 1999.

Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.