Podręcznik do teorii obliczeń. Dotyczy podstaw informatyki, a w
szczególności możliwości obliczeniowych współczesnych komputerów.
Składa się z trzech części. Pierwsza 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 czasowej 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. Książka skierowana do studentów informatyki
na wszystkich wyższych uczelniach.
Spis treści:
0. Wprowadzenie
0.1. Automaty, obliczalność i złożoność
Teoria złożoności
Teoria obliczalności
Teoria automatów
0.2. Oznaczenia matematyczne i terminologia
Zbiory
Ciągi i krotki
Funkcje i relacje
Grafy
Słowa i języki
Logika boolowska
Zestawienie
terminologii matematycznej
0.3. Definicje, twierdzenia i dowody
Poszukiwanie dowodów
0.4. Rodzaje dowodów
Dowód konstrukcyjny
Dowód przez sprowadzenie do
sprzeczności
Dowód przez indukcję
Ćwiczenia, zadania i rozwiązania
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 automatu
skończonego
Operacje regularne
1.2. Niedeterminizm
Formalna definicja
niedeterministycznego automatu skończonego
Równoważność niedeterministycznych i deterministycznych automatów
skończonych
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
l .4. Języki nieregularne
Lemat o pompowaniu dla
języków regularnych
Ćwiczenia, zadania i rozwiązania
2. Języki bezkontekstowe
2.1. Gramatyki bezkontekstowe
Formalna definicja gramatyki
bezkontekstowe
Przykłady gramatyk
bezkontekstowych
Projektowanie gramatyk
bezkontekstowych
Niejednoznaczność
Normalna postać
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 inne niż bezkontekstowe
Lemat o pompowaniu dla
języków bezkontekstowych
Ćwiczenia, zadania i rozwiązania
CZĘŚĆ II Teoria obliczalności
3. Teza Churcha-Turinga
3.1. Maszyny Turinga
Formalna definicja maszyny
Turinga
Przykłady maszyn Turinga
3.2. Rodzaje maszyn Turinga
Wielotaśmowe maszyny Turinga
Niedeterministyczne maszyny
Turinga
Enumeratory
Równoważność z innymi
modelami
3.3. Definicja algorytmu
Problemy Hilberta
Notacja do opisu maszyn
Turinga
Ćwiczenia, zadania i rozwiązania
4. Rozstrzygalność
4.l.. Języki rozstrzygalne
Problemy rozstrzyganie
dotyczące języków regularnych
Problemy rozstrzygalne
dotyczące języków bezkontekstowych
4.2. Problem stopu
Metoda diagonalizacji
Problem stopu jest
nierozstrzygalny
Języki rozpoznawalne w
sensie Turinga
Ćwiczenia, zadania i rozwiązania
5. Redukowalność
5.1. Problemy nierozstrzygalne z teorii języków
Redukcje poprzez historię
obliczeń
5.2. Prosty problem nierozstrzygalny
5.3. Redukcja przez odwzorowanie
Funkcje obliczalne
Formalna definicja redukcji
przez odwzorowanie
Ćwiczenia, zadania i rozwiązania
6. Zaawansowane zagadnienia z teorii obliczalności
6.1. Twierdzenie o rekursji
Samoodniesienie
Terminologia w twierdzeniu o
rekursji
Zastosowania
6.2. Rozstrzygalność w logice
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ść
Ćwiczenia, zadania i rozwiązania
CZĘŚĆ III Teoria złożoności
7. Złożoność czasowa
7.1. Pomiar złożoności
Notacja duże O i małe o
Analiza algorytmów
Wzajemna złożoność 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
Problem P versus NP
7.4. NP-zupełność
Redukowalność w
czasie wielomianowym
Definicja
NP-zupełności
Twierdzenie
Levina-Cooka
7.5. Inne problemy NP-zupełne
Problem pokrycia wierzchołkowego
Problem ścieżki Hamiltona
Problem sumy podzbioru
Ćwiczenia, zadania i rozwiązania
8. Złożoność pamięciowa
8.1. Twierdzenie Savitcha
8.2. Klasa PSPACE
8.3. PSPACE -zupełność
Problem TQBF
Strategie wygrywające dla
gier
Uogólniona gra
państwa-miasta
8.4. Klasy L i NL
8.5. NL- zupełność
Przeszukiwanie grafów
8.6. Klasa NL jest równa klasie coNL
Ćwiczenia, zadania i rozwiązania
9. Problemy trudne
9.1. Twierdzenia o hierarchii
Zupełność dla pamięci
wykładniczej
9.2. Relatywizacja
Granice zastosowań metody
diagonalizacji
9.3. Złożoność obwodów (sieci) logicznych
Ćwiczenia, zadania i rozwiązania
10. Zaawansowane zagadnienia z teorii złożoności
10.1. Algorytmy aproksymacyjne
10.2. Algorytmy losowe
Klasa BPP
Pierwszość
Programy z
rozgałęzieniami jednokrotnie czytające
10.3. Alternacje
Czas i pamięć w
obliczeniach alternujących
Hierarchia wielomianowa
10.4. Systemy dowodów interakcyjnych
Nieizomorfizm grafów
Definicja modelu
IP =PSP
10.5. Obliczenia równoległe
Jednostajne obwody
logiczne
Klasa NC
P -zupełność
10.6. Kryptografia
Klucze tajne
Systemy szyfrowania z kluczem
jawnym
Funkcje jednokierunkowe
Funkcje z bocznym wejściem
Ćwiczenia, zadania i rozwiązania
Wybrana literatura
Skorowidz
486 stron, B5, oprawa miękka
