POLECAMY
Autor:
Wydawca:
Format:
epub, mobi
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.
Rok wydania | 2020 |
---|---|
Liczba stron | 500 |
Kategoria | Programowanie |
Wydawca | Wydawnictwo Naukowe PWN |
Tłumaczenie | Marek Włodarz |
ISBN-13 | 978-83-01-21099-1 |
Numer wydania | 1 |
Język publikacji | polski |
Informacja o sprzedawcy | ePWN sp. z o.o. |
POLECAMY
Ciekawe propozycje
Wprowadzenie do CAD
do koszyka
Wprowadzenie do ekonometrii
do koszyka
Wprowadzenie do logopedii
do koszyka
Wprowadzenie do akustyki użytkowej
do koszyka
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 |