POLECAMY
Koszyk
Wprowadzenie do teorii obliczeń
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. |
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 |
KUP NA PREZENT
Wprowadzenie do teorii obliczeń
56,40 zł
Uzupełnij informacje na temat odbiorcy.
Produkt został pomyślnie dodany do koszyka.
Nieudana próba zakupu produktu. Spróbuj jeszcze raz.