Programozáselmélet

TARTALOM Előszó 9 Kiszámíthatóság 11 Bevezetés 11 Véges automaták 12 Reguláris kifejezések 13 Véges automaták 17 Átmenetgráfok 18 Kleene tétele 20 Az ekvivalenciatétel 26 Turing-gépek és egyéb automaták 29 Turing-gépek 29 Post-gépek 32 Veremtáras véges gépek 37 Nemdeterminisztikus gépek 43 A Turing-gépek mint akceptorok 46 Rekurzíven felsorolható halmazok 46 Rekurzív halmazok 47 Formális nyelvek 49 A Turing-gépek mint generátorok 52 Primitív rekurzív függvények 54 Parciális rekurzív függvények 59 A Turing-gépek mint algoritmusok 62 Az igen/nem problémaosztályok megoldhatósága 64 A Turing-gépek megállási problémája 65 A szemi-Thue-rendszerek szóproblémája 67 A Post-féle megfelelési probléma 69 Az igen/nem problémaosztályok parciális megoldhatósága 73 Megjegyzések az irodalomhoz 76 Irodalom 77 Feladatok 78 Predikátumkalkulus 88 Bevezetés 88 Alapfogalmak 93 Szintaxis 93 Szemantika 98 Érvényes formulák 104 Formulák ekvivalenciája 111 Formulák normálformái 118 Az érvényességi probléma 123 Természetes következtetés 127 A kapcsolókra vonatkozó szabályok 130 A kvantorokra vonatkozó szabályok 136 Az operátorokra vonatkozó szabályok 144 A rezolúció 148 Formulák klóz alakja 148 A Herbrand-eljárás 154 Az egyesítési algoritmus 161 A rezolúciós szabály 166 Megjegyzések az irodalomhoz 171 Irodalom 173 Feladatok 175 Programbizonyítás 192 Bevezetés 192 Folyamatábra-programok 192 Parciális helyesség 202 Megállás 213 Tömböket használó folyamatábra-programok 220 Parciális helyesség 220 Megállás 226 Algol-szerű programok 234 While-programok 234 Parciális helyesség 237 Totális helyesség 243 Megjegyzések az irodalomhoz 250 Irodalom 252 Feladatok 254 Folyamatábra-sémák 275 Bevezetés 275 Alapfogalmak 276 Szintaxis 276 Szemantika 278 Alaptulajdonságok 283 Herbrand-interpretációk 295 Eldöntési problémák 297 Az alaptulajdonságok megoldhatatlansága 299 Szabad sémák 303 Fasémák 309 Janov-sémák 319 Predikátumkalkulusban való formalizálás 328 Az algoritmus 329 A folyamatábra-programok tulajdonságainak formalizálása 340 A folyamatábra-sémák tulajdonságainak formalizálása 345 Transzformációs problémák 351 Rekurzív sémák 353 A folyamatábra-sémák összevetése a rekurzív sémákkal 356 Megjegyzések az irodalomhoz 367 Irodalom 369 Feladatok 372 A programok fixpontos elmélete 392 Bevezetés 392 Függvények és funkcionálok 394 Monoton függvények 395 Folytonos funkcionálok 403 Funkcionálok fixpontjai 406 Rekurzív programok 411 Kiszámítási szabályok 412 A fixpontot kiszámító szabályok 419 A rekurzív definíciók rendszere 426 Helyességbizonyítási módszerek 428 Lépésenkénti kiszámítási indukció 429 Teljes kiszámítási indukció 436 Fixpontos indukció 440 Strukturális indukció 446 Megjegyzések az irodalomhoz 453 Irodalom 453 Feladatok 456 Tárgymutató 471