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
adobe algorytmy apache asp autocad asembler bsd c++ c# delphi dtp excel flash html java javascript linux matlab mysql office php samba voip uml unix visual studio windows word
Księgarnia Informatyczna zaprasza.