Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 5
Spis treści
ОглавлениеPrzedmowa do pierwszego wydania
Przedmowa do trzeciego wydania
0.1 Automaty, obliczalność i złożoność
0.2 Pojęcia matematyczne i terminologia
Podsumowanie terminów matematycznych
0.3 Definicje, twierdzenia i dowody
Dowód nie wprost (przez sprowadzenie do sprzeczności)
CZĘŚĆ I. AUTOMATY I JĘZYKI
1. Języki regularne
1.1 Automaty skończone
Formalna definicja automatu skończonego
Przykłady automatów skończonych
Formalna definicja obliczeń
Projektowanie automatów skończonych
Operacje regularne
1.2 Niedeterminizm
Formalna definicja niedeterministycznego automatu skończonego
Równoważność NFA i DFA
Zamknięcie ze względu na operacje regularne
1.3 Wyrażenia regularne
Formalna definicja wyrażenia regularnego
Równoważność z automatami skończonymi
1.4 Języki nieregularne
Lemat o pompowaniu dla języków regularnych
2. Języki bezkontekstowe
2.1 Gramatyki bezkontekstowe
Formalna definicja gramatyki bezkontekstowej
Przykłady gramatyk bezkontekstowych
Projektowanie gramatyk bezkontekstowych
Niejednoznaczność
Postać normalna Chomsky’ego
2.2 Automaty ze stosem
Formalna definicja automatu ze stosem
Przykłady automatów ze stosem
Równoważność z gramatykami bezkontekstowymi
2.3 Języki niebędące bezkontekstowymi
Lemat o pompowaniu dla języków bezkontekstowych
2.4 Deterministyczne języki bezkontekstowe
Właściwości języków DCFL
Deterministyczne gramatyki bezkontekstowe
Zależności między DPDA a gramatykami DCFG
Parsing i gramatyki LR(k)
CZĘŚĆ II .TEORIA OBLIZALNOŚCI
3. Hipoteza Churcha-Turinga
3.1 Maszyny Turinga
Formalna definicja maszyny Turinga
Przykłady maszyn Turinga
3.2 Odmiany maszyn Turinga
Wielotaśmowe maszyny Turinga
Niedeterministyczne maszyny Turinga
Enumeratory
Równoważność z innymi modelami
3.3 Definicja algorytmu
Problemy Hilberta
Konwencja opisywania maszyn Turinga
4. Rozstrzygalność
4.1 Języki rozstrzygalne
Problemy rozstrzygalne dotyczące języków regularnych
Problemy rozstrzygalne dotyczące języków bezkontekstowych
4.2 Nierozstrzygalność
Metoda diagonalizacji
Język nierozstrzygalny
Język nierozpoznawalny w sensie Turinga
5. Redukowalność
5.1 Nierozstrzygalne problemy teorii języków
Redukcje przez historie obliczeń
5.2 Prosty problem nierozstrzygalny
5.3 Redukcja przez odwzorowanie
Funkcje obliczalne
Formalna definicja redukcji przez odwzorowanie
6. Zaawansowane zagadnienia teorii obliczalności
6.1 Twierdzenie o rekurencji
Samoodniesienie
Posługiwanie się twierdzeniem o rekurencji
Zastosowania
6.2 Rozstrzygalność teorii logicznych
Teoria rozstrzygalna
Teoria nierozstrzygalna
6.3 Redukowalność w sensie Turinga
6.4 Pojęcie informacji
Opisy minimalnej długości
Optymalność definicji
Słowa niekompresowalne i losowość
CZĘŚĆ III.TEORIA ZŁOŻONOŚCI
7. Złożoność czasowa
7.1 Mierzenie złożoności
Notacja wielkiego O i małego o
Analiza algorytmów
Zależności między złożonościami modeli
7.2 Klasa P
Czas wielomianowy
Przykłady problemów z klasy P
7.3 Klasa NP
Przykłady problemów z klasy NP
Zagadnienie P versus NP
7.4 NP-zupełność
Redukowalność w czasie wielomianowym
Definicja NP-zupełności
Twierdzenie Cooka-Levina
7.5 Dalsze problemy NP-zupełne
Problem pokrycia wierzchołkowego
Problem ścieżki Hamiltona
Problem sumy podzbioru
8. Złożoność pamięciowa
8.1 Twierdzenie Savitcha
8.2 Klasa PSPACE
8.3 PSPACE-zupełność
Problem TQBF
Strategie wygrywające w grach
Uogólniona gra w łańcuszek
8.4 Klasy L i NL
8.5 NL-zupełność
Przeszukiwanie grafów
8.6 Klasa NL równa się klasie coNL
9. Problemy trudne
9.1 Twierdzenia o hierarchii
Zupełność pamięci wykładniczej
9.2 Relatywizacja
Ograniczenia stosowalności metody diagonalizacji
9.3 Złożoność obwodów
10. Zaawansowane zagadnienia teorii złożoności
10.1 Algorytmy aproksymacyjne
10.2 Algorytmy probabilistyczne
Klasa BPP
Pierwszość
Programy z rozgałęzieniami z jednokrotnym odczytem
10.3 Alternacje
Czas i pamięć w obliczeniach alternujących
Wielomianowa hierarchia czasowa
10.4 Systemy dowodów interaktywnych
Nieizomorfizm grafów
Definicja modelu
IP = PSPACE
10.5 Obliczenia równoległe
Jednolite obwody logiczne
Klasa NC
P-zupełność
10.6 Kryptografia
Klucze tajne
Systemy szyfrowania z kluczem publicznym
Funkcje jednokierunkowe
Funkcje z bocznym wejściem
Wybrana bibliografia
