Wprowadzenie do teorii automatów, języków i obliczeń

Wprowadzenie do teorii automatów, języków i obliczeń

1 opinia

Format:

ibuk

WYBIERZ RODZAJ DOSTĘPU

 

Dostęp online przez myIBUK

WYBIERZ DŁUGOŚĆ DOSTĘPU

6,15

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

39,50

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

Nowe, rozszerzone i zmienione wydanie kompendium wiedzy dotyczącej teorii automatów, języków formalnych i obliczeń, czyli uniwersalnych podstaw informatyki teoretycznej i lingwistyki matematycznej. Książkę napisano praktycznie od nowa (nowy współautor Rajeev Motwani), czyniąc ją mniej formalną i bardziej przystępną dla studentów. Zrezygnowano z pewnych teoretycznych zagadnień, a położono nacisk na nowoczesne zastosowania omawianych teorii. Dodano informacje o algorytmach losowych oraz zwiększono liczbę prostych przykładów i rysunków ilustrujących omawiane zagadnienia.


Książka przeznaczona jest dla studentów kierunków informatycznych i matematycznych uniwersytetów i uczelni technicznych oraz pracowników naukowych zajmujących się informatyką teoretyczną, matematyką, automatyką i lingwistyką matematyczną, a także dla inżynierów i ekonomistów.


Liczba stron496
WydawcaWydawnictwo Naukowe PWN
ISBN-13978-83-0114-502-6
Numer wydania2
Język publikacjipolski
Informacja o sprzedawcyRavelo Sp. z o.o.

Ciekawe propozycje

Spis treści

  Przedmowa XIII
  1. Metody i szaleństwo    1
    1.1. Dlaczego mamy badać teorię automatów?    2
      1.1.1. Wprowadzenie do automatów skończonych    2
      1.1.2. Reprezentacjastrukturalna    4
      1.1.3. Automatyizłożoność    5
    1.2. Wprowadzenie do dowodu formalnego    5
      1.2.1. Dowodydedukcyjne    6
      1.2.2. Sprowadzenie do definicji    9
      1.2.3. Inne postacie twierdzeń    10
      1.2.4. Twierdzenia, które – jak się wydaje – nie są stwierdzeniami „jeśli,to”    13
    1.3. Dodatkowe postacie dowodu    14
      1.3.1. Dowodzenie równoważności zbiorów    14
      1.3.2. Kontrapozycja    15
      1.3.3. Dowód przez sprowadzenie do sprzeczności    17
      1.3.4. Kontrprzykłady    18
    1.4. Dowody przez indukcję matematyczną    20
      1.4.1. Indukcjanaliczbachnaturalnych    20
      1.4.2. Bardziej ogólne postacie indukcji na liczbach naturalnych    23
      1.4.3. Indukcjastrukturalna    24
      1.4.4. Indukcjawzajemna    27
    1.5. Podstawowe pojęcia teorii automatów    29
      1.5.1. Alfabety    29
      1.5.2. Łańcuchy    29
      1.5.3. Języki    31
      1.5.4. Problemy    32
    1.6. Podsumowanie rozdziału 1    34
    1.7. Bibliografia do rozdziału 1    36
  2. Automaty skończone    37
    2.1. Nieformalny wizerunek automatów skończonych    38
      2.1.1. Podstawowe reguły    38
      2.1.2. Protokół    39
      2.1.3. Umożliwienie automatowi zignorowania akcji    41
      2.1.4. Cały system ako automat    43
      2.1.5. Zastosowanie automatu produktowego do dowodzenia poprawności protokołu    44
    2.2. Deterministyczny automat skończony    45
      2.2.1. Definicja deterministycznego automatu skończonego    45
      2.2.2. Jak DAS przetwarza łańcuchy    46
      2.2.3. Prostsze oznaczenia dla DAS    47
      2.2.4. Rozszerzenie funkcji przejścia na łańcuchy    49
      2.2.5. Język DAS    51
      2.2.6. Ćwiczenia do podrozdziału 2.2    52
    2.3. Niedeterministyczny automat skończony    54
      2.3.1. Nieformalne spojrzenie na niedeterministyczne automaty skończone    54
      2.3.2. Definicja niedeterministycznego automatu skończonego    56
      2.3.3. Rozszerzona funkcja przejścia    56
      2.3.4. Język NAS    57
      2.3.5. Równoważność automatów deterministycznych i niedeterministycznych    59
      2.3.6. Zły przypadek konstrukcji podzbiorów    63
      2.3.7. Ćwiczenia do podrozdziału 2.3    64
    2.4. Zastosowanie: przeszukiwanie tekstu    66
      2.4.1. Znajdowanie łańcuchów w tekście    66
      2.4.2. Niedeterministyczne automaty skończone do przeszukiwania tekstu    67
      2.4.3. DAS rozpoznający zbiór słów kluczowych    68
    2.5. Automaty skończone z ?-przejściami    70
      2.5.1. Zastosowania ?-przejść    70
      2.5.2. Formalna notacja dla ?-NAS    72
      2.5.3. Epsilon-domknięcia    72
      2.5.4. Rozszerzone przejścia i języki dla ?-NAS    73
      2.5.5. Eliminacja ?-przejść    74
      2.5.6. Ćwiczenia do podrozdziału 2.5    77
    2.6. Podsumowanie rozdziału 2    77
    2.7. Bibliografia do rozdziału 2    78
  3. Wyrażenia i języki regularne    79
    3.1. Wyrażenia regularne    79
      3.1.1. Operatory wyrażeń regularnych    80
      3.1.2. Budowanie wyrażeń regularnych    82
      3.1.3. Priorytet operatorów w wyrażeniach regularnych    84
      3.1.4. Ćwiczenia do podrozdziału 3.1    86
    3.2. Automaty skończone i wyrażenia regularne    86
      3.2.1. Od DAS do wyrażeń regularnych    87
      3.2.2. Przekształcanie DAS na wyrażenie regularne przez eliminowanie stanów    91
      3.2.3. Przekształcanie wyrażeń regularnych na automaty    96
      3.2.4. Ćwiczenia do podrozdziału 3.2    99
    3.3. Zastosowania wyrażeń regularnych    101
      3.3.1. Wyrażenia regularne w systemie UNIX    101
      3.3.2. Analiza leksykalna    103
      3.3.3. Znajdowanie wzorców w tekście    105
      3.3.4. Ćwiczenia do podrozdziału 3.3    106
    3.4. Prawa algebraiczne dla wyrażeń regularnych    107
      3.4.1. Przemienność i łączność    107
      3.4.2. Elementy neutralne i anihilator    108
      3.4.3. Prawa rozdzielności    109
      3.4.4. Prawo idempotencji    110
      3.4.5. Prawa dotyczące domknięć    110
      3.4.6. Odkrywanie praw dla wyrażeń regularnych    111
      3.4.7. Test prawa algebraicznego dla wyrażeń regularnych    113
      3.4.8. Ćwiczenia do podrozdziału 3.4    114
    3.5. Podsumowanie rozdziału 3    115
    3.6. Bibliografia do rozdziału 3    115
  4. Własności języków regularnych    117
    4.1. Dowodzenie, że języki nie są regularne    117
      4.1.1. Lemat o pompowaniu dla języków regularnych    118
      4.1.2. Zastosowania lematu o pompowaniu    119
      4.1.3. Ćwiczenia do podrozdziału 4.1    121
    4.2. Własności zamkniętości języków regularnych    122
      4.2.1. Zamkniętość języków regularnych ze względu na operacje boolowskie    122
      4.2.2. Odwrócenie    128
      4.2.3. Homomorfizmy    129
      4.2.4. Przeciwobrazy homomorficzne    131
      4.2.5. Ćwiczenia do podrozdziału 4.2    135
    4.3. Własności decyzyjne języków regularnych    138
      4.3.1. Wzajemne przekształcanie reprezentacji    139
      4.3.2. Testowanie pustości języków regularnych    141
      4.3.3. Testowanie należenia do języka regularnego    142
      4.3.4. Ćwiczenia do podrozdziału 4.3    143
    4.4. Równoważność i minimalizacja automatów    143
      4.4.1. Testowanie równoważności stanów    144
      4.4.2. Testowanie równoważności języków regularnych    147
      4.4.3. Minimalizacja DAS    149
      4.4.4. Dlaczego zminimalizowany DAS jest nie do pobicia    152
      4.4.5. Ćwiczenia do podrozdziału 4.4    153
    4.5. Podsumowanie rozdziału 4    154
    4.6. Bibliografia do rozdziału 4    155
  5. Gramatyki i języki bezkontekstowe    156
    5.1. Gramatyki bezkontekstowe    156
      5.1.1. Nieformalny przykład    157
      5.1.2. Definicja gramatyk bezkontekstowych    158
      5.1.3. Wyprowadzenia w gramatyce    160
      5.1.4. Wyprowadzenia lewostronne i prawostronne    162
      5.1.5. Język gramatyki    164
      5.1.6. Formy zdaniowe    165
      5.1.7. Ćwiczenia do podrozdziału 5.1    166
    5.2. Drzewa wyprowadzenia    168
      5.2.1. Konstruowanie drzew wyprowadzenia    168
      5.2.2. Plon drzewa wyprowadzenia    170
      5.2.3. Wnioskowanie, wyprowadzenia i drzewa wyprowadzenia    170
      5.2.4. Od wnioskowania do drzew    171
      5.2.5. Od drzew do wyprowadzeń    173
      5.2.6. Od wyprowadzeń do wnioskowania rekurencyjnego    176
      5.2.7. Ćwiczenia do podrozdziału 5.2    177
    5.3. Zastosowania gramatyk bezkontekstowych    178
      5.3.1. Parsery    178
      5.3.2. Generator parserow YACC    181
      5.3.3. Języki znakowania    182
      5.3.4. XML i definicja typu dokumentu    184
      5.3.5. Ćwiczenia do podrozdziału 5.3    189
    5.4. Wieloznaczność języków i gramatyk    190
      5.4.1. Gramatyki wieloznaczne    191
      5.4.2. Usuwanie wieloznaczności z gramatyk    192
      5.4.3. Wyprowadzenia lewostronne jako metoda wyrażenia wieloznaczności    196
      5.4.4. Ścisła wieloznaczność    197
      5.4.5. Ćwiczenia do podrozdziału 5.4    198
    5.5. Podsumowanie rozdziału 5    199
    5.6. Bibliografia do rozdziału 5    200
  6. Automaty ze stosem    202
    6.1. Definicja automatu ze stosem    202
      6.1.1. Nieformalne wprowadzenie    202
      6.1.2. Formalna definicja automatu ze stosem    204
      6.1.3. Notacja graficzna dla AZS    206
      6.1.4. Opis chwilowy AZS    207
      6.1.5. Ćwiczenia do podrozdziału 6.1    210
    6.2. Języki AZS    211
      6.2.1. Akceptacja przez stan końcowy    211
      6.2.2. Akceptacja przez pusty stos    212
      6.2.3. Od pustego stosu do stanu końcowego    213
      6.2.4. Od stanu końcowego do pustego stosu    216
      6.2.5. Ćwiczenia do podrozdziału 6.2    217
    6.3. Równoważność AZS i GBK    219
      6.3.1. Od gramatyk do automatów ze stosem    219
      6.3.2. Od AZS do gramatyk    222
      6.3.3. Ćwiczenia do podrozdziału 6.3    227
    6.4. Deterministyczne automaty ze stosem    227
      6.4.1. Definicja deterministycznego AZS    228
      6.4.2. Języki regularne a deterministyczne AZS    229
      6.4.3. DAZS i języki bezkontekstowe    230
      6.4.4. DAZS i gramatyki wieloznaczne    231
      6.4.5. Ćwiczenia do podrozdziału 6.4    232
    6.5. Podsumowanie rozdziału 6    233
    6.6. Bibliografia do rozdziału 6    234
  7. Własności języków bezkontekstowych    235
    7.1. Postacie normalne gramatyk bezkontekstowych    235
      7.1.1. Eliminowanie symboli bezużytecznych    236
      7.1.2. Obliczanie symboli generujących i osiągalnych    238
      7.1.3. Eliminowanie ?-produkcji    239
      7.1.4. Eliminowanie produkcji jednostkowych    243
      7.1.5. Postać normalna Chomsky’ego    247
      7.1.6. Ćwiczenia do podrozdziału 7.1    251
    7.2. Lemat o pompowaniu dla językow bezkontekstowych    253
      7.2.1. Wielkość drzew wyprowadzenia    254
      7.2.2. Sformułowanie lematu o pompowaniu    254
      7.2.3. Zastosowania lematu o pompowaniu dla językow bezkontekstowych    257
      7.2.4. Ćwiczenia do podrozdziału 7.2    259
    7.3. Własności zamkniętości językow bezkontekstowych    261
      7.3.1. Podstawienie    261
      7.3.2. Zastosowania twierdzenia o podstawieniu    263
      7.3.3. Odwrocenie    264
      7.3.4. Przecięcie z językiem regularnym    264
      7.3.5. Przeciwobraz homomorficzny    268
      7.3.6. Ćwiczenia do podrozdziału 7.3    270
    7.4. Własności decyzyjne JBK    272
      7.4.1. Złożoność obustronnej konwersji pomiędzy JBK a AZS    272
      7.4.2. Czas wykonywania konwersji na postać normalną Chomsky’ego    273
      7.4.3. Testowanie pustości JBK    274
      7.4.4. Testowanie należenia do JBK    276
      7.4.5. Rzut oka na problemy nierozstrzygalne dla JBK    280
      7.4.6. Ćwiczenia do podrozdziału 7.4    280
    7.5. Podsumowanie rozdziału 7    281
    7.6. Bibliografia do rozdziału 7    282
  8. Wprowadzenie do maszyn Turinga    283
    8.1. Problemy, których nie potrafią rozwiązać komputery    283
      8.1.1. Programy drukujące „hello, world”    284
      8.1.2. Hipotetyczny program dla testu „hello, world”    286
      8.1.3. Redukcja jednego problemu do drugiego    289
      8.1.4. Ćwiczenia do podrozdziału 8.1    292
    8.2. Maszyna Turinga    292
      8.2.1. Zadanie rozstrzygnięcia wszystkich pytań matematycznych    293
      8.2.2. Notacja dla maszyn Turinga    294
      8.2.3. Opisy chwilowe dla maszyn Turinga    295
      8.2.4. Diagramy przejść dla maszyn Turinga    299
      8.2.5. Język maszyny Turinga    302
      8.2.6. Maszyny Turinga i problem stopu    302
      8.2.7. Ćwiczenia do podrozdziału 8.2    303
    8.3. Techniki programowania dla maszyn Turinga    304
      8.3.1. Pamięć w stanie    305
      8.3.2. Wiele ścieżek    306
      8.3.3. Podprocedury    308
      8.3.4. Ćwiczenia do podrozdziału 8.3    310
    8.4. Rozszerzenia podstawowej maszyny Turinga    310
      8.4.1. Wielotaśmowa maszyna Turinga    311
        8.4.2. Równoważność jednotaśmowych i wielotaśmowych maszyn Turinga    312
        8.4.3. Czas pracy a konstrukcja sprowadzania wielu taśm do jednej    313
        8.4.4. Niedeterministyczne maszyny Turinga    315
        8.4.5. Ćwiczenia do podrozdziału 8.4    317
    8.5. Ograniczone maszyny Turinga    319
      8.5.1. Maszyny Turinga o taśmach jednostronnie nieskończonych    319
      8.5.2. Maszyny wielostosowe    322
      8.5.3. Maszyny licznikowe    325
      8.5.4. Moc maszyn licznikowych    325
      8.5.5. Ćwiczenia do podrozdziału 8.5    328
    8.6. Maszyny Turinga a komputery    328
      8.6.1. Symulacja maszyny Turinga przez komputer    329
      8.6.2. Symulacja komputera przez maszynę Turinga    330
      8.6.3. Porównywanie czasu pracy komputerów i maszyn Turinga    334
    8.7. Podsumowanie rozdziału 8    337
    8.8. Bibliografia do rozdziału 8    339
  9. Nierozstrzygalność    340
    9.1. Język, który nie jest rekurencyjnie przeliczalny    341
      9.1.1. Ponumerowanie łańcuchów binarnych    342
      9.1.2. Kody maszyn Turinga    342
      9.1.3. Język diagonalizacji    344
      9.1.4. Dowód, że Ld nie jest rekurencyjnie przeliczalny    345
      9.1.5. Ćwiczenia do podrozdziału 9.1    345
    9.2. Problem nierozstrzygalny, który jest RP    346
      9.2.1. Języki rekurencyjne    346
      9.2.2. Dopełnienie języków rekurencyjnych i RP    347
      9.2.3. Język uniwersalny    350
      9.2.4. Nierozstrzygalność języka uniwersalnego    352
      9.2.5. Ćwiczenia do podrozdziału 9.2    353
    9.3. Problemy nierozstrzygalne dotyczące maszyn Turinga    355
      9.3.1. Redukcje    355
      9.3.2. Maszyny Turinga akceptujące język pusty    356
      9.3.3. Twierdzenie Rice’a i własności języków RP    359
      9.3.4. Problemy dotyczące specyfikacji maszyn Turinga    362
      9.3.5. Ćwiczenia do podrozdziału 9.3    362
    9.4. Problem odpowiedniości Posta    363
      9.4.1. Definicja problemu odpowiedniości Posta    364
      9.4.2. Zmodyfikowany problem odpowiedniości Posta    366
      9.4.3. Zakończenie dowodu nierozstrzygalności POP    369
      9.4.4. Ćwiczenia do podrozdziału 9.4    374
    9.5. Inne problemy nierozstrzygalne    375
      9.5.1. Problemy dotyczące programów    375
      9.5.2. Nierozstrzygalność wieloznaczności GBK    375
      9.5.3. Dopełnienie języka listy    377
      9.5.4. Ćwiczenia do podrozdziału 9.5    380
    9.6. Podsumowanie rozdziału 9    381
    9.7. Bibliografia do rozdziału 9    381
  10. Problemy niepodatne    383
    10.1. Klasy P i NP    384
      10.1.1. Problemy, które można rozwiązać w czasie wielomianowym    384
      10.1.2. Przykład: algorytm Kruskala    385
      10.1.3. Niedeterministyczny czas wielomianowy    389
      10.1.4. Przykład NP: problem komiwojażera    389
      10.1.5. Redukcje w czasie wielomianowym    391
      10.1.6. Problemy NP-zupełne    392
      10.1.7. Ćwiczenia do podrozdziału 10.1    394
    10.2. Problem NP-zupełny    395
      10.2.1. Problem spełnialności    396
      10.2.2. Reprezentacja przypadków SAT    397
      10.2.3. NP-zupełność problemu SAT    398
      10.2.4. Ćwiczenia do podrozdziału 10.2    404
    10.3. Ograniczony problem spełnialności    405
      10.3.1. Postać normalna wyrażeń boolowskich    405
      10.3.2. Przekształcanie wyrażeń do PNK    406
      10.3.3. NP-zupełność CSAT    410
      10.3.4. NP-zupełność 3SAT    414
      10.3.5. Ćwiczenia do podrozdziału 10.3    415
    10.4. Inne problemy NP-zupełne    416
      10.4.1. Opisywanie problemów NP-zupełnych    416
      10.4.2. Problem zbiorów niezależnych    417
      10.4.3. Problem pokrycia wierzchołkowego    421
      10.4.4. Problem skierowanego obwodu Hamiltona    423
      10.4.5. Nieskierowane obwody Hamiltona i PK    428
      10.4.6. Podsumowanie problemów NP-zupełnych    430
      10.4.7. Ćwiczenia do podrozdziału 10.4    431
    10.5. Podsumowanie rozdziału 10    434
    10.6. Bibliografia do rozdziału 10    435
  11. Dodatkowe klasy problemów    436
    11.1. Dopełnienia językow z NP    437
      11.1.1. Klasa językow ko-NP    437
      11.1.2. Problemy NP-zupełne a ko-NP    438
      11.1.3. Ćwiczenia do podrozdziału 11.1    439
    11.2. Problemy rozwiązywalne w pamięci wielomianowej    440
      11.2.1. Maszyny Turinga o pamięci wielomianowej    440
      11.2.2. Związek między PS i NPS a poprzednio zdefiniowanymi klasami    441
      11.2.3. Deterministyczna i niedeterministyczna pamięć wielomianowa    443
    11.3. Problem zupełny dla PS    445
      11.3.1. PS-zupełność    445
      11.3.2. Kwantyfikowana formuła boolowska    446
      11.3.3. Obliczanie wartości kwantyfikowanych formuł boolowskich    447
      11.3.4. PS-zupełność problemu KFB    449
      11.3.5. Ćwiczenia do podrozdziału 11.3    454
    11.4. Klasy języków oparte na losowości    455
      11.4.1. Quicksort: przykład algorytmu losowego    455
      11.4.2. Model maszyny Turinga wykorzystującej losowość    456
      11.4.3. Język losowej maszyny Turinga    457
      11.4.4. Klasa LP    460
      11.4.5. Rozpoznawanie języków należących do LP    462
      11.4.6. Klasa ZPP    462
      11.4.7. Związek pomiędzy LP a ZPP    463
      11.4.8. Związki z klasami P i NP    465
    11.5. Złożoność testowania, czy dana liczba jest liczbą pierwszą    466
      11.5.1. Waga testowania, czy dana liczba jest liczbą pierwszą    466
      11.5.2. Wprowadzenie do arytmetyki modulo    468
      11.5.3. Złożoność obliczeń w arytmetyce modulo    470
      11.5.4. Losowo wielomianowe testowanie, czy dana liczba jest liczbą pierwszą    471
      11.5.5. Niedeterministyczne testowanie, czy dana liczba jest liczbą pierwszą    472
      11.5.6. Ćwiczenia do podrozdziału 11.5    475
    11.6. Podsumowanie rozdziału 11    476
    11.7. Bibliografia do rozdziału 11    477
  Skorowidz    478
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