Algoritmusok és rekurzív függvények bonyolultságelmélete

Szerző

Giorgio Ausiello

Fordító

Gerlits János

Lektor

Dr. Horváth Sándor

Budapest

'Giorgio Ausiello: Algoritmusok és rekurzív függvények bonyolultságelmélete ' összes példány

Kiadó:	Műszaki Könyvkiadó
Kiadás helye:	Budapest
Kiadás éve:	1984
Kötés típusa:	Ragasztott papírkötés
Oldalszám:	267 oldal
Sorozatcím:
Kötetszám:
Nyelv:	Magyar
Méret:	20 cm x 14 cm
ISBN:	963-105-159-5
Megjegyzés:	8 fekete-fehér ábrával illusztrálva. Tankönyvi száma: 61 059.

Értesítőt kérek a kiadóról

A beállítást mentettük,
naponta értesítjük a beérkező friss
kiadványokról

Tartalom

Előszó a könyv magyar kiadásához	9
Előszó	11
Parciális rekurzivitás	13
Rekurzív függvények	13
Algoritmusok, rekurzivitás, kiszámíthatóság	13
Parciális rekurzív függvények	17
Rekurzió és iteráció	22
Függvényegyenletek és a McCarthy-formalizmus	25
A regisztergépek	35
A regisztergépek programjai	35
Kiszámítási sorozatok	39
A regisztergép aritmetizálása	45
A Turing-kiszámíthatóság	47
A Turing-gépek	47
Felhasznált erőforrások	54
Eldönthetetlenségi fokozatok	59
Irodalmi megjegyzések	66
Szubrekurzivitás	68
A rekurzív függvények bonyolultsága	68
A bonyolultság eltérő fogalmai	68
A primitív rekurzió	70
Többszörös rekurzió	75
A Grzegorczyk-hierarchia	78
A primitív rekurzív függvények növekedési gyorsasága	78
Grzegorczyk-osztályok	82
A Grzegorczyk-osztályok és a Turing-gépek	90
Egy szubrekurzív nyelv	95
Primitív rekurziók egymásba skatulyázása	95
A LOOP nyelv	97
Ciklusmélységi osztályok	104
A ciklusmélységi osztályok és a Grzegorczyk-osztályok kapcsolata	110
Elemi függvények és operátorok	118
A szubrekurzív függvényosztályok eldönthetetlenségi kérdései	118
Elemi függvények	121
Elemi operátorok és korlátozott nyelvek	126
Irodalmi megjegyzések	130
Axiomatikus bonyolultságelmélet	132
A kiszámítási bonyolultság tanulmányozásának elvont megközelítése	132
Absztrakt bonyolultsági osztályok	132
A bonyolultsági mérték axiómái	136
A kiszámítási bonyolultság invarianciája	145
Tetszőlegesen bonyolult és tetszőlegesen felgyorsítható algoritmusú függvények	150
Bonyolultsági osztályok és a függvények bonyolultság szerinti rendezése	150
Tetszőlegesen bonyolult függvények szerkesztése	153
Optimális programok létezésének kérdése	160
A bonyolultsági osztályok elmélete	169
Hézagok a bonyolultsági osztályok között	169
A bonyolultsági osztályok "rendes" nevei	173
A Grzegorczyk-osztályok mint bonyolultsági osztályok	182
A programok hosszúsága	189
További megjegyzések a szubrekurzív nyelvekről	189
A programhosszúság axiómái	191
Programhosszúság és hatékonyság a szubrekurzív nyelvekben	194
Irodalmi megjegyzések	200
Az elemi függvények bonyolultsága	204
Konkrét problémák bonyolultsága	204
Általános megjegyzés	204
A kiszámítási idő korlátozása	209
Egyes problémák osztályozása	217
Elemi függvényosztályok	221
A szubelemi osztályok jellemzése	221
Egyszerű függvények	226
A Ritchie-Cleave hierarhia	230
Problémák visszavezetése más problémákra	236
A relatív bonyolultság	236
Reducibilitás és bonyolultsági fokozatok	240
A polinomiálisan teljes fokozat	244
Irodalmi megjegyzések	250
Irodalom	255
Tárgymutató	265