WPROWADZENIE DO TEORII OBLICZEŃ SISPER M. Księgarnia

Wprowadzenie do teorii obliczeń

Wprowadzenie do teorii obliczeń to najpopularniejszy podręcznik do teorii obliczeń. Dotyczy podstaw informatyki, a w szczególności możliwości obliczeniowych współczesnych komputerów.

Książka składa się z trzech części. Pierwsza jest 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.

Trzecia edycja zawiera zupełnie nowy podrozdział poświęcony deterministycznym językom bezkontekstowym. Została też wzbogacona o nowe ćwiczenia, problemy i przykłady.

Książka skierowana do studentów informatyki na wszystkich wyższych uczelniach.

Przedmowa do pierwszego wydania
Do studentów
Do nauczycieli
Pierwsze wydanie
Uwagi do autora
Podziękowania

Przedmowa do drugiego wydania
Przedmowa do trzeciego wydania

0. Wstęp
0.1. Automaty, obliczalność i złożoność
Teoria złożoności
Teoria obliczalności
Teoria automatów
0.2. Pojęcia matematyczne i terminologia
Zbiory
Ciągi i krotki
Funkcje i relacje
Grafy
Słowa i języki
Logika Boole‘a
Podsumowanie terminów matematycznych
0.3. Definicje, twierdzenia i dowody
Znajdowanie dowodów
0.4 Typy dowodów
Dowód przez konstrukcję
Dowód nie wprost (przez sprowadzenie do sprzeczności)
Dowód indukcyjny
Dowód

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
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 OBLICZALNOŚ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-zupelność
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
Indeks

480 stron, Format: 16.5x23.5cm, oprawa miękka

Księgarnia nie działa. Nie odpowiadamy na pytania i nie realizujemy zamówien. Do odwolania !.