POLECAMY
Autor:
Wydawca:
Format:
epub, mobi, ibuk
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
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 |