Twój koszyk : Do zapłaty 0,00 zł Ilość w koszyku: 0

Strona główna » podręczniki i lektury » Podręczniki akademickie » Techniczne » Informatyka

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.

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


Przedmowa do drugiego wydania (międzynarodowego)

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