.

0 (hodnocen0 x )

BK

Praha : Státní nakladatelství technické literatury, 1981

467 stran : 95 obrázků

000061036

Úvod 9 // Poznámka překladatele 11 // 1. Teorie vyčíslitelnosti 13 // 1.1. Konečné automaty 14 // 1.1.1. Regulární výrazy 15 // 1.1.2. Konečné automaty 19 // 1.1.3. Přechodové grafy 21 // 1.1.4. Kleeneova věta 22 // 1.1.5. Věta o ekvivalenci 28 // 1.2. Turingovy stroje 30 // 1.2.1. Turingo vy stroje 31 // 1.2.2. Posto vy stroje 34 // 1.2.3. Konečné stroje se zásobníky 38 // 1.2.4. Nedeterministické stroje 43 // 1.3. Turingovy stroje jako akceptory 46 // 1.3Л. Rekurzívně spočetné množiny 46 // 1.3.2. Rekurzívní množiny 47 // 1.3.3. Formální jazyky 48 // 1.4. Turingovy stroje jako generátory 51 // 1.4.1. Primitivně rekurzívní funkce 52 // 1.4.2. Parciálně rekurzívní funkce 57 // 1.5. Turingovy stroje jako algoritmy 60 // 1.5.1. Rozhodnutelnost tříd problémů typu ano/ne 61 // 1.5.2. Problém zastavení pro Turingovy stroje 62 // 1.5.3. Problém ekvivalence pro semi-Thueovy systémy 64 // 1.5.4. Postův problém přiřazení 66 // 1.5.5. Parciální rozhodnutelnost tříd problémů typu ano/ne 70 // Cvičení 73 // Historické a bibliografické poznámky 79 // 2. Predikátový počet 81 // 2.1. Základní pojmy 84 // 2.1.1. Syntaxe 84 // 5 2.1.2. Sémantika (interpretace) 88 // 2.1.3. Logicky pravdivé formule 93 // 2.1.4. Ekvivalence formulí 98 // 2.1.5. Normálni formy formulí 103 // 2.1.6. Problém logické pravdivosti 107 // 2.2. Přirozená dedukce 110 // 2.2.1. Pravidla pro spojky 112 // 2.2.2. Pravidla pro kvantifikátory 116 // 2.2.3. Pravidla pro operátory 122 // 2.3. Rezoluční metoda 125 // 2.3.1. Klauzulární forma 125 // 2.3.2. Herbrandova procedura 129 // 2.3.3. Obecná rezoluční metoda a unifikační algoritmus 135 // 2.3.4. Pravidlo rezoluce 139 // Cvičení 143 // Historické a bibliografické poznámky 155 // 3. Verifikace programů 157 // 3.1. Programy 157 // 3.1.1. Parciální korektnost 166 //

3.1.2. Ukončení 176 // 3.2. Programy s poli 182 // 3.2.1. Parciální korektnost 183 // 3.2.2. Ukončení 188 // 3.3. Algolovské programy 194 // 3.3.1. Strukturované programy 194 // 3.3.2. Parciálni korektnost 197 // 3.3.3. Totálni korektnost 203 // Cvičení 209 // Historické a bibliografické poznámky 224 // 4. Programová schémata 226 // 4.1. Základní pojmy 227 // 4.1.1. Syntaxe 227 // 4.1.2. Sémantika (interpretace) 228 // 4.1.3. Základní vlastnosti 232 // 4.1.4. Herbrandovy interpretace 242 // 4.2. Otázky rozhodnutelnosti 245 // 4.2.1. Nerozhodnutelnost základních vlastností 247 // 4.2.2. Volná schémata 251 // 4.2.3. Stromová schémata 257 // 4.2.4. Janovova schémata 265 // 6 4.3. Formalizace v rámci predikátového počtu 274 // 4.3.1. Algoritmus 274 // 4.3.2. Formalizace vlastností programů 284 // 4.3.3. Formalizace vlastností programových schémat 288 // 4.4. Rekurzívní programy a schémata 293 // 4.4.1. Rekurzívní schémata 295 // 4.4.2. Srovnání programových a rekurzívních schémat 298 // Cvičení 307 // Historické a bibliografické poznámky 322 // 5. Pevné body programů 324 // 5.1. Funkce a funkcionály 325 // 5.1.1. Monotónní funkce 326 // 5.1.2. Spojité funkcionály 332 // 5.1.3. Pevné body funkcionálů 335 // 5.2. Rekurzívní programy 339 // 5.2.1. Výpočetní pravidla 340 // 5.2.2. Korektní výpočetní pravidla 348 // 5.2.3. Systémy rekurzívních definic 353 // 5.3. Verifikační metody 356 // 5.3.1. Postupná výpočetní indukce 356 // 5.3.2. Úplná výpočetní indukce 362 // 5.3.3. Další varianty indukce 364 // 5.3.4. Strukturní indukce 369 // Cvičení 375 // Historické a bibliografické poznámky 384 // Dodatky 386 // A. Verifikace programů 386 // A.l. Metoda podcílových podmínek 386 // A.l.l. Princip metody 386 // A.1.2. Obecný postup 390 // A.1.3. Příklady 391 //

A.2. Metoda podcílových pravidel 395 // A.2.1. Princip metody 395 // A.2.2. Přiklad 397 // A.3. Metoda intermitentních podmínek 399 // A.3.1. Princip metody 399 // A.3.2. Příklady 401 // A.4. Důkaz ukončení programu 408 // A.4.1. Úvod 408 // A.4.2. Metoda čítačů 409 // 7 I // A.4.3. Metoda podmínek ukončení 413 // Závěrečné a bibliografické poznámky 416 // B. Programová schémata 418 // B.l. Otázky ekvivalence 418 // B.l.l. Úplné systémy transformací 418 // B.1.2. Liberální a konzervativní schémata 420 // B.1.3. Progresivní schémata, prostá Janovo va schémata // a průchodná schémata 424 // B.2. Hierarchie tříd programových schémat 428 // B.2.1. Porovnávání tříd schémat 428 // B.2.2. Strukturovaná schémata 429 // B.2.3. Schémata s násobnými cykly a schémata s výstupy 441 // B.3. Srovnávací schematologie 445 // B.3.1. Programová schémata se zásobníky a poli 445 // B.3.2. Schémata a gramatiky 446 // B.3.3. Převod rekurze na iteraci 450 // Literatura 453 // Rejstřík 462

(OCoLC)40079316

cnb000136279