Wprowadzenie do teorii obliczeń

• Druk: Warszawa, 2020
• Autor: Michael Sipser
• Tłumacz: Marek Włodarz
• Wydawca: Wydawnictwo Naukowe PWN

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.

• Kategorie:
  1. Ebooki i Audiobooki »
  2. Ebooki »
  3. Ebooki popularnonaukowe i specjalistyczne »
  4. Informatyka
• Język wydania: polski
• ISBN: 978-83-01-21099-1
• ISBN druku: 978-83-01-20926-1
• Liczba stron: 500

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