ebook Wprowadzenie do teorii obliczeń Michael Sipser

Spis treści ebooka Wprowadzenie do teorii obliczeń

Przedmowa do pierwszego wydania IX
Do studentów IX
Do nauczycieli X
Pierwsze wydanie XI
Uwagi do autora XII
Podziękowania XII
Przedmowa do drugiego wydania XIV
Przedmowa do trzeciego wydania XVII
0. Wstęp 1
0.1 Automaty, obliczalność i złożoność 1
Teoria złożoności 2
Teoria obliczalności 3
Teoria automatów 3
0.2 Pojęcia matematyczne i terminologia 3
Zbiory 3
Ciągi i krotki 6
Funkcje i relacje 7
Grafy 10
Słowa i języki 13
Logika Boole’a 14
Podsumowanie terminów matematycznych 15
0.3 Definicje, twierdzenia i dowody 17
Znajdowanie dowodów 17
0.4 Typy dowodów 21
Dowód przez konstrukcję 21
Dowód nie wprost (przez sprowadzenie do sprzeczności) 21
Dowód indukcyjny 23
Dowód 24
Część I. AUTOMATY I JĘZYKI 29
1. Języki regularne 31
1.1 Automaty skończone 31
Formalna definicja automatu skończonego 34
Przykłady automatów skończonych 37
Formalna definicja obliczeń 39
Projektowanie automatów skończonych 40
Operacje regularne 43
1.2 Niedeterminizm 47
Formalna definicja niedeterministycznego automatu skończonego 52
Równoważność NFA i DFA 54
Zamknięcie ze względu na operacje regularne 58
1.3 Wyrażenia regularne 62
Formalna definicja wyrażenia regularnego 63
Równoważność z automatami skończonymi 65
1.4 Języki nieregularne 75
Lemat o pompowaniu dla języków regularnych 76
2. Języki bezkontekstowe 101
2.1 Gramatyki bezkontekstowe 102
Formalna definicja gramatyki bezkontekstowej 104
Projektowanie gramatyk bezkontekstowych 106
Niejednoznaczność 107
Postać normalna Chomsky’ego 108
2.2 Automaty ze stosem 111
Formalna definicja automatu ze stosem 112
Przykłady automatów ze stosem 114
Równoważność z gramatykami bezkontekstowymi 116
2.3 Języki niebędące bezkontekstowymi 124
Lemat o pompowaniu dla języków bezkontekstowych 125
2.4 Deterministyczne języki bezkontekstowe 130
Właściwości języków DCFL 133
Deterministyczne gramatyki bezkontekstowe 136
Zależności między DPDA a gramatykami DCFG 147
Parsing i gramatyki LR(k) 153
Część II. TEORIA OBLICZALNOŚCI 167
3. Hipoteza Churcha-Turinga 169
3.1 Maszyny Turinga 169
Formalna definicja maszyny Turinga 171
Przykłady maszyn Turinga 174
3.2 Odmiany maszyn Turinga 179
Wielotaśmowe maszyny Turinga 180
Niedeterministyczne maszyny Turinga 182
Enumeratory 184
Równoważność z innymi modelami 185
3.3 Definicja algorytmu 186
Problemy Hilberta 187
Konwencja opisywania maszyn Turinga 189
4. Rozstrzygalność 199
4.1 Języki rozstrzygalne 200
Problemy rozstrzygalne dotyczące języków regularnych 200
Problemy rozstrzygalne dotyczące języków bezkontekstowych 204
4.2 Nierozstrzygalność 207
Metoda diagonalizacji 208
Język nierozstrzygalny 213
Język nierozpoznawalny w sensie Turinga 216
5. Redukowalność 223
5.1 Nierozstrzygalne problemy teorii języków 224
Redukcje przez historie obliczeń 228
5.2 Prosty problem nierozstrzygalny 235
5.3 Redukcja przez odwzorowanie 242
Funkcje obliczalne 242
Formalna definicja redukcji przez odwzorowanie 243
6. Zaawansowane zagadnienia teorii obliczalności 255
6.1 Twierdzenie o rekurencji 255
Samoodniesienie 256
Posługiwanie się twierdzeniem o rekurencji 259
Zastosowania 260
6.2 Rozstrzygalność teorii logicznych 262
Teoria rozstrzygalna 265
Teoria nierozstrzygalna 267
6.3 Redukowalność w sensie Turinga 270
6.4 Pojęcie informacji 272
Opisy minimalnej długości 273
Optymalność definicji 276
Słowa niekompresowalne i losowość 277
Część III. TEORIA ZŁOŻONOŚCI 285
7. Złożoność czasowa 287
7.1 Mierzenie złożoności 287
Notacja wielkiego O i małego o 288
Analiza algorytmów 290
Zależności między złożonościami modeli 294
7.2 Klasa P 297
Czas wielomianowy 297
Przykłady problemów z klasy P 299
7.3 Klasa NP 305
Przykłady problemów z klasy NP 309
Zagadnienie P versus NP 311
7.4 NP-zupełność 312
Redukowalność w czasie wielomianowym 313
Definicja NP-zupełności 317
Twierdzenie Cooka-Levina 317
7.5 Dalsze problemy NP-zupełne 324
Problem pokrycia wierzchołkowego 325
Problem ścieżki Hamiltona 327
Problem sumy podzbioru 333
8. Złożoność pamięciowa 347
8.1 Twierdzenie Savitcha 349
8.2 Klasa PSPACE 352
8.3 PSPACE-zupełność 353
Problem TQBF 354
Strategie wygrywające w grach 358
Uogólniona gra w łańcuszek 360
8.4 Klasy L i NL 365
8.5 NL-zupełność 368
Przeszukiwanie grafów 370
8.6 Klasa NL równa się klasie coNL 372
9. Problemy trudne 381
9.1 Twierdzenia o hierarchii 381
Zupełność pamięci wykładniczej 390
9.2 Relatywizacja 395
Ograniczenia stosowalności metody diagonalizacji 396
9.3 Złożoność obwodów 399
10. Zaawansowane zagadnienia teorii złożoności 413
10.1 Algorytmy aproksymacyjne 413
10.2 Algorytmy probabilistyczne 416
Klasa BPP 416
Pierwszość 419
Programy z rozgałęzieniami z jednokrotnym odczytem 424
10.3 Alternacje 429
Czas i pamięć w obliczeniach alternujących 431
Wielomianowa hierarchia czasowa 435
10.4 Systemy dowodów interaktywnych 436
Nieizomorfizm grafów 436
Definicja modelu 437
IP = PSPACE 439
10.5 Obliczenia równoległe 449
Jednolite obwody logiczne 450
Klasa NC 452
P-zupełność 454
10.6 Kryptografia 455
Klucze tajne 456
Systemy szyfrowania z kluczem publicznym 458
Funkcje jednokierunkowe 458
Funkcje z bocznym wejściem 460
Wybrana bibliografia 465
Indeks 469