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.
Spis treści:
Przedmowa
1. Metody i szaleństwo
1.1. Dlaczego mamy badać teorię automatów?
1.1.1. Wprowadzenie do automatów skończonych
1.1.2. Reprezentacja strukturalna
1.1.3. Automaty i złożoność
1.2. Wprowadzenie do dowodu formalnego
1.2.1. Dowody dedukcyjne
1.2.2. Sprowadzenie do definicji
1.2.3. Inne postacie twierdzeń
1.2.4. Twierdzenia, które - jak się wydaje - nie są stwierdzeniami ?jeśli, to"
1.3. Dodatkowe postacie dowodu
1.3.1. Dowodzenie równoważności zbiorów
1.3.2. Kontrapozycja
1.3.3. Dowód przez sprowadzenie do sprzeczności
1.3.4. Kontrprzykłady
1.4. Dowody przez indukcję matematyczną
1.4.1. Indukcja na liczbach naturalnych
1.4.2. Bardziej ogólne postacie indukcji na liczbach naturalnych
1.4.3. Indukcja strukturalna
1.4.4. Indukcja wzajemna
1.5. Podstawowe pojęcia teorii automatów
1.5.1. Alfabety
1.5.2. Łańcuchy
1.5.3. Języki
1.5.4. Problemy
1.6. Podsumowanie rozdziału 1
1.7. Bibliografia do rozdziału 1
2. Automaty skończone
2.1. Nieformalny wizerunek automatów skończonych
2.1.1. Podstawowe reguły
2.1.2. Protokół
2.1.3. Umożliwienie automatowi zignorowania akcji
2.1.4. Cały system jako automat
2.1.5. Zastosowanie automatu produktowego do dowodzenia poprawności protokołu
2.2. Deterministyczny automat skończony
2.2.1. Definicja deterministycznego automatu skończonego
2.2.2. Jak DAS przetwarza łańcuchy
2.2.3. Prostsze oznaczenia dla DAS
2.2.4. Rozszerzenie funkcji przejścia na łańcuchy
2.2.5. Język DAS
2.2.6. ćwiczenia do podrozdziału 2.2
2.3. Niedeterministyczny automat skończony
2.3.1. Nieformalne spojrzenie na niedeterministyczne automaty skończone
2.3.2. Definicja niedeterministycznego automatu skończonego
2.3.3. Rozszerzona funkcja przejścia
2.3.4. Język NAS
2.3.5. Równoważność automatów deterministycznych i niedeterministycznych
2.3.6. Zły przypadek konstrukcji podzbiorów
2.3.7. Ćwiczenia do podrozdziału 2.3
2.4. Zastosowanie: przeszukiwanie tekstu
2.4.1. Znajdowanie łańcuchów w tekście
2.4.2. Niedeterministyczne automaty skończone do przeszukiwania tekstu
2.4.3. DAS rozpoznający zbiór słów kluczowych
2.4.4. Ćwiczenia do podrozdziału 2.4
2.5. Automaty skończone z E-przejściami
2.5.1. Zastosowania e-przejść
2.5.2. Formalna notacja dla E-NAS
2.5.3. Epsilon-domknięcia
2.5.4. Rozszerzone przejścia i języki dla E-NAS
2.5.5. Eliminacja e-przejść
2.5.6. Ćwiczenia do podrozdziału 2.5
2.6. Podsumowanie rozdziału 2
2.7. Bibliografia do rozdziału 2
3. Wyrażenia i języki regularne
3.1. Wyrażenia regularne
3.1.1. Operatory wyrażeń regularnych
3.1.2. Budowanie wyrażeń regularnych
3.1.3. Priorytet operatorów w wyrażeniach regularnych
3.1.4. Ćwiczenia do podrozdziału 3.1
3.2. Automaty skończone i wyrażenia regularne
3.2.1. Od DAS do wyrażeń regularnych
3.2.2. Przekształcanie DAS na wyrażenie regularne przez eliminowanie stanów
3.2.3. Przekształcanie wyrażeń regularnych na automaty
3.2.4. Ćwiczenia do podrozdziału 3.2
3.3. Zastosowania wyrażeń regularnych
3.3.1. Wyrażenia regularne w systemie UNIX
3.3.2. Analiza leksykalna
3.3.3. Znajdowanie wzorców w tekście
3.3.4. Ćwiczenia do podrozdziału 3.3
3.4. Prawa algebraiczne dla wyrażeń regularnych
3.4.1. Przemienność i łączność
3.4.2. Elementy neutralne i anihilator
3.4.3. Prawa rozdzielności
3.4.4. Prawo idempotencji
3.4.5. Prawa dotyczące domknięć
3.4.6. Odkrywanie praw dla wyrażeń regularnych
3.4.7. Test prawa algebraicznego dla wyrażeń regularnych
3.4.8. Ćwiczenia do podrozdziału 3.4
3.5. Podsumowanie rozdziału 3
3.6. Bibliografia do rozdziału 3
4. Własności języków regularnych
4.1. Dowodzenie, że języki nie są regularne
4.1.1. Lemat o pompowaniu dla języków regularnych
4.1.2. Zastosowania lematu o pompowaniu
4.1.3. ćwiczenia do podrozdziału 4.1
4.2. Własności zamkniętości języków regularnych
4.2.1. Zamkniętość języków regularnych ze względu na operacje boolowskie
4.2.2. Odwrócenie
4.2.3. Homomorfizmy
4.2.4. Przeciwobrany homomorficzne
4.2.5. ćwiczenia da podrozdziału 4.2
4.3. Własności decyzyjne języków regularnych
4.3.1. Wzajemne przekształcanie reprezentacji
4.3.2. Testowanie pustości języków- regularnych
4.3.3. Testowanie należenia do języka regularnego
4.3.4. Ćwiczenia do podrozdziału 4.3
4.4. Równoważność i minimalizacja automatów
4.4.1. Testowanie równoważności stanów
4.4.2. Testowanie równoważności języków regularnych
4.4.3. Minimalizacja DAS
4.4.4. Dlaczego zminimalizowany DAS jest nie do pobicia
4.4.5. Ćwiczenia do podrozdziału 4.4
4.5. Podsumowanie rozdziału 4
4.6. Bibliografia do rozdziału 4
5. Gramatyki i języki bezkontekstowe
5.1. Gramatyki bezkontekstowe
5.1.1. Nieformalny przykład
5.1.2. Definicja gramatyk bezkontekstowych
5.1.3. Wyprowadzenia w gramatyce
5.1.4. Wyprowadzenia lewostronne i prawostronne
5.1.5. Język gramatyki
5.1.6. Formy zdaniowe
5.1.7. Ćwiczenia do podrozdziału 5.1
5.2. Drzewa wyprowadzenia
5.2.1. Konstruowanie drzew wyprowadzenia
5.2.2. Plon drzewa wyprowadzenia
5.2.3. Wnioskowanie, wyprowadzenia i drzewa wyprowadzenia
5.2.4. Od wnioskowania do drzew
5.2.5. Od drzew do wyprowadzeń
5.2.6. Od wyprowadzeń do wnioskowania rekurencyjnego
5.2.7. Ćwiczenia do podrozdziału 5.2
5.3. Zastosowania gramatyk bezkontekstowych
5.3.1. Parsery
5.3.2. Generator parserów YACC
5.3.3. Języki znakowania
5.3.4. XML i definicja typu dokumentu
5.3.5. ćwiczenia do podrozdziału 5.3
5.4. Wieloznaczność języków i gramatyk
5.4.1. Gramatyki wieloznaczne
5.4.2. Usuwanie wieloznaczności z gramatyk
5.4.3. Wyprowadzenia lewostronne jako metoda wyrażenia wieloznaczności
5.4.4. Ścisła wieloznaczność
5.4.5. ćwiczenia do podrozdziału 5.4
5.5. Podsumowanie rozdziału 5
5.6. Bibliografia do rozdziału 5
6. Automaty ze stosem
6.1. Definicja automatu ze stosem
6.1.1. Nieformalne wprowadzenie
6.1.2. Formalna definicja automatu ze stosem
6.1.3. Notacja graficzna dla AZS
6.1.4. Opis chwilowy AZS
6.1.5. Ćwiczenia do podrozdziału 6.1
6.2. Języki AZS
6.2.1. Akceptacja przez stan końcowy
6.2.2. Akceptacja przez pusty stos
6.2.3. Od pustego stosu do stanu końcowego
6.2.4. Od stanu końcowego do pustego stosu
6.2.5. Ćwiczenia do podrozdziału 6.2
6.3. Równoważność AZS i GBK
6.3.1. Od gramatyk do automatów ze stosem
6.3.2. Od AZS do gramatyk
6.3.3. Ćwiczenia do podrozdziału 6.3
6.4. Deterministyczne automaty ze stosem
6.4.1. Definicja deterministycznego AZS
6.4.2. Języki regularne a deterministyczne AZS
6.4.3. DAZS i języki bezkontekstowe
6.4.4. DAZS i gramatyki wieloznaczne
6.4.5. ćwiczenia do podrozdziału 6.4
6.5. Podsumowanie rozdziału 6
6.6. Bibliografia do rozdziału 6
7. Własności języków bezkontekstowych
7.1. Postacie normalne gramatyk bezkontekstowych
7.1.1. Eliminowanie symboli bezużytecznych
7.1.2. Obliczanie symboli generujących i osiągalnych
7.1.3. Eliminowanie e-produkcji
7.1.4. Eliminowanie produkcji jednostkowych
7.1.5. Postać normalna Chomsky'ego
7.1.6. ćwiczenia do podrozdziału 7.1
7.2. Lemat o pompowaniu dla języków bezkontekstowych
7.2.1. Wielkość drzew wyprowadzenia
7.2.2. Sformułowanie lematu o pompowaniu
7.2.3. Zastosowania lematu o pompowaniu dla języków bezkontekstowych
7.2.4. Ćwiczenia do podrozdziału 7.2
7.3. Własności zamkniętości języków bezkontekstowych
7.3.1. Podstawienie
7.3.2. Zastosowania twierdzenia o podstawieniu
7.3.3. Odwrócenie
7.3.4. Przecięcie z językiem regularnym
7.3.5. Przeciwobraz homomorficzny
7.3.6. Ćwiczenia do podrozdziału 7.3
7.4. Własności decyzyjne JBK
7.4.1. Złożoność obustronnej konwersji pomiędzy JBK a AZS
7.4.2. Czas wykonywania konwersji na postać normalną Chomsky'ego
7.4.3. Testowanie pustości JBK
7.4.4. Testowanie należenia do JBK
7.4.5. Rzut oka na problemy nierozstrzygalne dla JBK
7.4.6. Ćwiczenia do podrozdziału 7.4
7.5. Podsumowanie rozdziału 7
7.6. Bibliografia do rozdziału 7
8. Wprowadzenie do maszyn Turinga
8.1. Problemy, których nie potrafią rozwiązać komputery
8.1.1. Programy drukujące ?hello, world"
8.1.2. Hipotetyczny program dla testu ?hello, world"
8.1.3. Redukcja jednego problemu do drugiego
8.1.4. Ćwiczenia do podrozdziału 8.1
8.2. Maszyna Turinga
8.2.1. Zadanie rozstrzygnięcia wszystkich pytań matematycznych
8.2.2. Notacja dla maszyn Turinga
8.2.3. Opisy chwilowe dla maszyn Turinga
8.2.4. Diagramy przejść dla maszyn Turinga
8.2.5. Język maszyny Turinga
8.2.6. Maszyny Turinga i problem stopu
8.2.7. Ćwiczenia do podrozdziału 8.2
8.3. Techniki programowania dla maszyn Turinga
8.3.1. Pamięć w stanie
8.3.2. Wiele ścieżek
8.3.3. Podprocedury
8.3.4. Ćwiczenia do podrozdziału 8.3
8.4. Rozszerzenia podstawowej maszyny Turinga
8.4.1. Wielotaśmowa maszyna Turinga
8.4.2. Równoważność jednotaśmowych i wielotaśmowych maszyn Turinga
8.4.3. Czas pracy a konstrukcja sprowadzania wielu taśm do jednej
8.4.4. Niedeterministyczne maszyny Turinga
8.4.5. ćwiczenia do podrozdziału 8.4
8.5. Ograniczone maszyny Turinga
8.5.1. Maszyny Turinga o taśmach jednostronnie nieskończonych
8.5.2. Maszyny wielostosowe
8.5.3. Maszyny licznikowe
8.5.4. Moc maszyn licznikowych
8.5.5. ćwiczenia do podrozdziału 8.5
8.6. Maszyny Turinga a komputery
8.6.1. Symulacja maszyny Turinga przez komputer
8.6.2. Symulacja komputera przez maszynę Turinga
8.6.3. Porównywanie czasu pracy komputerów i maszyn Turinga
8.7. Podsumowanie rozdziału 8
8.8. Bibliografia do rozdziału 8
9. Nierozstrzygalność
9.1. Język, który nie jest rekurencyjnie przeliczalny
9.1.1. Ponumerowanie łańcuchów binarnych
9.1.2. Kody maszyn Turinga
9.1.3. Język diagonalizacji
9.1.4. Dowód, że Ld nie jest rekurencyjnie przeliczalny
9.1.5. Ćwiczenia do podrozdziału 9.1
9.2. Problem nierozstrzygalny, który jest RP
9.2.1. Języki rekurencyjne
9.2.2. Dopełnienie języków rekurencyjnych i RP
9.2.3. Język uniwersalny
9.2.4. Nierozstrzygalność języka uniwersalnego
9.2.5. ćwiczenia do podrozdziału 9.2
9.3. Problemy nierozstrzygalne dotyczące maszyn Turinga
9.3.1. Redukcje
9.3.2. Maszyny Turinga akceptujące język pusty
9.3.3. Twierdzenie Rice'a i własności języków RP
9.3.4. Problemy dotyczące specyfikacji maszyn Turinga
9.3.5. Ćwiczenia do podrozdziału 9.3
9.4. Problem odpowiedniości Posta
9.4.1. Definicja problemu odpowiedniości Posta
9.4.2. Zmodyfikowany problem odpowiedniości Posta
9.4.3. Zakończenie dowodu nierozstrzygalności POP
9.4.4. Ćwiczenia do podrozdziału 9.4
9.5. Inne problemy nierozstrzygalne
9.5.1. Problemy dotyczące programów
9.5.2. Nierozstrzygalność wieloznaczności GBK
9.5.3. Dopełnienie języka listy
9.5.4. ćwiczenia do podrozdziału 9.5
9.6. Podsumowanie rozdziału 9
9.7. Bibliografia do rozdziału 9
10. Problemy niepodatne
10.1. Klasy P i NP
10.1.1. Problemy, które można rozwiązać w czasie wielomianowym
10.1.2. Przykład: algorytm Kruskala
10.1.3. Niedeterministyczny czas wielomianowy
10.1.4. Przykład NP: problem komiwojażera
10.1.5. Redukcje w czasie wielomianowym
10.1.6. Problemy NP-zupełne
10.1.7. ćwiczenia do podrozdziału 10.1
10.2. Problem NP-zupełny
10.2.1. Problem spełnialności
10.2.2. Reprezentacja przypadków SAT
10.2.3. NP-zupełność problemu SAT
10.2.4. ćwiczenia do podrozdziału 10.2
10.3. Ograniczony problem spełnialności
10.3.1. Postać normalna wyrażeń boolowskich
10.3.2. Przekształcanie wyrażeń do PNK
10.3.3. NP-zupełność CSAT
10.3.4. NP-zupełność 3SAT
10.3.5. ćwiczenia do podrozdziału 10.3
10.4. Inne problemy NP-zupełne
10.4.1. Opisywanie problemów NP-zupełnych
10.4.2. Problem zbiorów niezależnych
10.4.3. Problem pokrycia wierzchołkowego
10.4.4. Problem skierowanego obwodu Hamiltona
10.4.5. Nieskierowane obwody Hamiltona i PK
10.4.6. Podsumowanie problemów NP-zupełnych
10.4.7. Ćwiczenia do podrozdziału 10.4
10.5. Podsumowanie rozdziału 10
10.6. Bibliografia do rozdziału 10
11. Dodatkowe klasy problemów
11.1. Dopełnienia języków z NP
11.1.1. Klasa języków ko-NP
11.1.2. Problemy NP-zupełne a ko-NP
11.1.3. Ćwiczenia do podrozdziału 11.1
11.2. Problemy rozwiązywalne w pamięci wielomianowej
11.2.1. Maszyny Turinga o pamięci wielomianowej
11.2.2. Związek między PS i NPS a poprzednio zdefiniowanymi klasami
11.2.3. Deterministyczna i niedeterministyczna pamięć wielomiarowa
11.3. Problem zupełny dla PS
11.3.1. PS-zupełność
11.3.2. Kwantyfikowana formuła boolowska
11.3.3. Obliczanie wartości kwantyfikowanych formuł boolowskich
11.3.4. PS-zupełność problemu KFB
11.3.5. Ćwiczenia do podrozdziału 11.3
11.4. Klasy języków oparte na losowości
11.4.1. Quicksort: przykład algorytmu losowego
11.4.2. Model maszyny Turinga wykorzystującej losowość
11.4.3. Język losowej maszyny Turinga
11.4.4. Klasa LP
11.4.5. Rozpoznawanie języków należących do LP
11.4.6. Klasa ZPP
11.4.7. Związek pomiędzy LP a ZPP
11.4.8. Związki z klasami P i NP
11.5. Złożoność testowania, czy dana liczba jest liczbą pierwszą
11.5.1. Waga testowania, czy dana liczba jest liczbą pierwszą
11.5.2. Wprowadzenie do arytmetyki modulo
11.5.3. Złożoność obliczeń w arytmetyce modulo
11.5.4. Losowo wielomiarowe testowanie, czy dana liczba jest liczbą pierwszą
11.5.5. Niedeterministyczne testowanie, czy dana liczba jest liczbą pierwszą
11.5.6. Ćwiczenia do podrozdziału 11.5
11.6. Podsumowanie rozdziału 11
11.7. Bibliografia do rozdziału 11
Skorowidz |
