Wprowadzenie do teorii obliczeń

1 opinia

Format:

epub, mobi, ibuk

DODAJ DO ABONAMENTU

WYBIERZ RODZAJ DOSTĘPU

42,60  71,00

Format: epub, mobi

 

Dostęp online przez myIBUK

WYBIERZ DŁUGOŚĆ DOSTĘPU

6,15

Wypożycz na 24h i opłać sms-em

42,6071,00

cena zawiera podatek VAT

ZAPŁAĆ SMS-EM

TA KSIĄŻKA JEST W ABONAMENCIE

Już od 19,90 zł miesięcznie za 5 ebooków!

WYBIERZ SWÓJ ABONAMENT

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.


Liczba stron500
WydawcaWydawnictwo Naukowe PWN
TłumaczenieMarek Włodarz
ISBN-13978-83-01-21099-1
Numer wydania1
Język publikacjipolski
Informacja o sprzedawcyRavelo 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
RozwińZwiń
W celu zapewnienia wysokiej jakości świadczonych przez nas usług, nasz portal internetowy wykorzystuje informacje przechowywane w przeglądarce internetowej w formie tzw. „cookies”. Poruszając się po naszej stronie internetowej wyrażasz zgodę na wykorzystywanie przez nas „cookies”. Informacje o przechowywaniu „cookies”, warunkach ich przechowywania i uzyskiwania dostępu do nich znajdują się w Regulaminie.

Nie pokazuj więcej tego powiadomienia