EBOOKI WYDAWCY
Wydawca:
Format:
ibuk
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 stron | 496 |
---|---|
Wydawca | Wydawnictwo Naukowe PWN |
ISBN-13 | 978-83-0114-502-6 |
Numer wydania | 2 |
Język publikacji | polski |
Informacja o sprzedawcy | ePWN sp. z o.o. |
EBOOKI WYDAWCY
POLECAMY
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 |