| Summary: | A jegyzet célja az, hogy egységes rövid bevezetést adjon a számítástudomány három területéhez. Ezek az automaták és formális nyelvek elmélete, a kiszámíthatóságelmélet és a bonyolultságelmélet. Az automaták és formális nyelvek elmélete az 1950-es évekre nyúlik vissza és mind a mai napig a számítástudomány egyik alappillérének tekinthető. A jegyzetben a véges automaták viselkedését jellemezzük a reguláris kifejezések és a jobblineáris nyelvtanok segítségével. Az egyik fő eredmény Kleene klasszikus tétele, mely szerint egy nyelv akkor és csak akkor ismerhető fel véges automatával, ha megadható reguláris kifejezéssel. A véges automaták tárgyalását a környezetfüggetlen nyelvek majd a Chomsky-féle hierarchia tárgyalása követi. Itt az egyik fő eredmény a környezetfüggetlen nyelvtanok és veremautomaták ekvivalenciája. A veremautomatát tekinthetjük a (nemdeterminisztikus) Turing-gép speciális eseteként. A Turing-gép bevezetésére egészen általános okból került sor az 1930-as években. Ma már teljesen elfogadott az a tézis, hogy a Turing-gépet (és a vele ekvivalens számos más modellt) tekinthetjük az algoritmus fogalom matematikai megfelelőjének. Egy feladat, probléma akkor oldható meg algoritmikusan, ha megoldható Turing-géppel. Ismertetjük a Turing-gépekhez kapcsolódó alapfogalmakat és a Turing-gépeken alapuló kiszámíthatóságelmélet néhány alapvető eredményét. Több példát adunk Turing-géppel, és így algoritmuikusan megoldhatatlan feladatra is. A bonyolultságelmélet a kiszámíthatóságelmélet kiterjesztése. Azt vizsgálja, hogy hogyan lehet osztályozni az algoritmikusan megoldható problémákat, feladatokat a megoldásukhoz szükséges erőforrások mennyisége szerint. Ismertetjük a bonyolultságelmélet néhány alapfogalmát, és részletesebben foglalkozunk az P, NP és PSPACE bonyolultsági osztályokkal. A jegyzet azokat az ismereteket öleli fel, amelyet a Szegedi Tudományegyetem műszaki informatikai alapképzésben az Számítástudomány alapjai c. tárgy oktatásában 2005-től helyet kaptak. Számos olyan anyagrész kimaradt a jegyzetből, amely egy önálló automataelméleti bevezető kurzusban, vagy egy önálló kiszámíthatósáqelméleti vagy bonyolultságelméleti bevezető kurzusban helyet szokott kapni. Törekedtünk arra, hogy a jegyzet anyaga egy félévben heti két óra előadással leadható legyen. További kiegészítő ismeretek tárgyalása megtalálható az irodalomjegyzékben felsorolt könyvekben és jegyzetekben, magyarul vagy idegen nyelven.
|
|---|