Autor: Michael Sipser

ISBN: 978-83-204-3436-1

Ilość stron: 486

Data wydania: 01/2009

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 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.

Rozdziały:

0. Wprowadzenie             
0.1. Automaty, obliczalność i złożoność   
0.2. Oznaczenia matematyczne i terminologia   
0.3. Definicje, twierdzenia i dowody
0.4. Rodzaje dowodów
Ćwiczenia, zadania i rozwiązania

CZĘŚĆ I. Automaty i języki

1. Języki regularne
1.1. Automaty skończone  
1.2. Niedeterminizm 
1.3. Wyrażenia regularne   
l.4. Języki nieregularne
Ćwiczenia, zadania i rozwiązania

2. Języki bezkontekstowe
2.1. Gramatyki bezkontekstowe
2.2. Automaty ze stosem   
2.3. Języki inne niż bezkontekstowe   
Ćwiczenia, zadania i rozwiązania

CZĘŚĆ II. Teoria obliczalności 

3. Teza Churcha-Turinga             
3.1. Maszyny Turinga 
3.2. Rodzaje maszyn Turinga  
3.3. Definicja algorytmu 
Ćwiczenia, zadania i rozwiązania 

4. Rozstrzygalność         
4.l. Języki rozstrzygalne   
4.2. Problem stopu 
Ćwiczenia, zadania i rozwiązania 

5. Redukowalność           
5.1. Problemy nierozstrzygalne z teorii języków  
5.2. Prosty problem nierozstrzygalny 
5.3. Redukcja przez odwzorowanie 
Ćwiczenia, zadania i rozwiązania

6. Zaawansowane zagadnienia z teorii obliczalności              
6.1. Twierdzenie o rekursji  
6.2. Rozstrzygalność w logice
6.3. Redukowalność w sensie Turinga  
6.4. Pojęcie informacji   
Ćwiczenia, zadania i rozwiązania

CZĘŚĆ III. Teoria złożoności

7. Złożoność czasowa      
7.1. Pomiar złożoności   
7.2. Klasa P  
7.3. Klasa NP  
7.4.  NP-zupełność  
7.5. Inne problemy NP-zupełne
Ćwiczenia, zadania i rozwiązania

8. Złożoność pamięciowa 
8.1. Twierdzenie Savitcha
8.2. Klasa PSPACE  
8.3. PSPACE -zupełność
8.4. Klasy L i NL  
8.5. NL- zupełność
8.6. Klasa NL jest równa klasie coNL   
Ćwiczenia, zadania i rozwiązania

9. Problemy trudne
9.1. Twierdzenia o hierarchii  
9.2. Relatywizacja
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  
10.3. Alternacje
10.4. Systemy dowodów interakcyjnych
10.5. Obliczenia równoległe  
10.6. Kryptografia   
Ćwiczenia, zadania i rozwiązania