|
|
|
|
| LEADER |
03684nnm a2200289 i 4500 |
| 001 |
tana52 |
| 005 |
20240422111128.0 |
| 008 |
240422s2011 hu o 0|| zxx d |
| 020 |
|
|
|a 978 963 279 496 9
|
| 040 |
|
|
|a PEREPO TANANYAG
|b hun
|
| 041 |
|
|
|a zxx
|
| 100 |
1 |
|
|a Ésik Zoltán
|
| 245 |
1 |
2 |
|a A számítástudomány alapjai
|h [elektronikus dokumentum] /
|c Zoltán Ésik
|
| 260 |
|
|
|a Typotex Kiadó
|c 2011
|
| 300 |
|
|
|a 75
|
| 520 |
3 |
|
|a 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.
|
| 650 |
|
4 |
|a Számítástudomány, információtudomány és bioinformatika
|
| 650 |
|
4 |
|a Kognitív tudomány, ember-gép kapcsolat, természetes nyelv feldolgozása
|
| 695 |
|
|
|a automata
|
| 695 |
|
|
|a Turing-gép
|
| 695 |
|
|
|a formális nyelv
|
| 695 |
|
|
|a reguláris nyelv
|
| 695 |
|
|
|a bonyolultságelmélet
|
| 695 |
|
|
|a kiszámíthatóságelmélet
|
| 695 |
|
|
|a Chomsky-féle hierarchia
|
| 695 |
|
|
|a számítástudomány
|
| 856 |
4 |
0 |
|u https://perepo-tananyag.uni-pannon.hu/id/eprint/52/1/2011_A%20sz%C3%A1m%C3%ADt%C3%A1studom%C3%A1ny%20alapjai_%C3%89sik%20Zolt%C3%A1n.pdf
|z Dokumentum-elérés
|