Wprowadzenie do teorii obliczeń

Wprowadzenie do teorii obliczeń to najpopularniejszy podręcznik do teorii obliczeń. Dotyczy podstaw informatyki, a w szczególności możliwości obliczeniowych współczesnych komputerów. Książka składa się z trzech części. Pierwsza jest poświęcona automatom i językom formalnym. Omówiono w niej niedeterminizm, równoważność automatów deterministycznych i niedeterministycznych, wyrażenia regularne, kryteria nieregularności języków, a także języki bezkontekstowe. Druga część dotyczy teorii obliczalności. Opisano w niej ograniczenia współczesnych komputerów, wyjaśniono pojęcia rozstrzygalności i nierozstrzygalności. Trzecia część jest poświęcona teorii złożoności. Przedstawiono w niej podstawowe klasy złożoności obliczeniowej, klasę problemów NP-zupełnych, a także klasyfikację problemów ze względu na możliwość automatycznego ich rozwiązywania przy ograniczonych zasobach. Trzecia edycja zawiera zupełnie nowy podrozdział poświęcony deterministycznym językom bezkontekstowym. Została też wzbogacona o nowe ćwiczenia, problemy i przykłady. Książka skierowana do studentów informatyki na wszystkich wyższych uczelniach.

Spis treści

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