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.

Osoby które kupowały "Wprowadzenie do teorii obliczeń", wybierały także:

• Windows Media Center. Domowe centrum rozrywki 66,67 zł, (8,00 zł -88%)
• Przywództwo w świecie VUCA. Jak być skutecznym liderem w niepewnym środowisku 58,64 zł, (12,90 zł -78%)
• Mapa Agile & Scrum. Jak si 57,69 zł, (15,00 zł -74%)
• Sztuka podst 53,46 zł, (13,90 zł -74%)
• Lean dla bystrzaków. Wydanie II 49,62 zł, (12,90 zł -74%)

Spis treści

Wprowadzenie do teorii obliczeń eBook -- spis treści

• Okładka
• Strona tytułowa
• Strona redakcyjna
• Spis treści
• 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 Boolea
    • 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
      • Przykłady gramatyk bezkontekstowych
      • Projektowanie gramatyk bezkontekstowych
      • Niejednoznaczność
      • Postać normalna Chomskyego
    • 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 OBLIZALNOŚ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-zupełność
      • 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
  • Przypisy