• Kategorie
  • Wprowadzenie do teorii obliczeń.

Autor(zy) Sipser Michael
Miejsce wydania Warszawa
Rok 2020
Wydanie III
Ilość stron 480
Format B5
Okładka miękka
89.00 -10% 80.00
szt. Do przechowalni
Wysyłka w ciągu 1-5 dni
Cena przesyłki 0
PP Przesyłka biznesowa pobranie (od 80 zł gratis) 0
Odbiór osobisty 0
PP Przesyłka biznesowa (od 80 zł gratis) 0
Odbiór osobisty 0
Paczkomaty InPost przelew (od 100 zł gratis) 12
Kurier przelew (od 200 zł gratis) 12
Kurier pobranie (od 200 zł gratis) 16
Dostępność 0 szt.
ISBN 978-83-01-20926-1.
EAN 9788301209261

Zamów telefonicznie: 914340603

Zostaw telefon

Wprowadzenie do teorii obliczeń.

Autor(zy): Sipser Michael.
ISBN: 978-83-01-20926-1.
Miejsce wydania: Warszawa
Rok wydania: 2020
Wydanie :III
Ilość stron: 480
Format: B5
Okładka: miękka

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.





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







Nie ma jeszcze komentarzy ani ocen dla tego produktu.