reklama - zainteresowany?

Wprowadzenie do teorii obliczeń - Helion

Wprowadzenie do teorii obliczeń
ebook
Autor: Michael Sipser
Tłumaczenie: Marek Włodarz
ISBN: 9788301210991
stron: 500, Format: ebook
Data wydania: 2020-03-19
Księgarnia: Helion

Cena książki: 71,20 zł (poprzednio: 87,90 zł)
Oszczędzasz: 19% (-16,70 zł)

Dodaj do koszyka Wprowadzenie do teorii obliczeń

Tagi: Inne

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.

Dodaj do koszyka Wprowadzenie do teorii obliczeń

 

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

  • Windows Media Center. Domowe centrum rozrywki
  • Przywództwo w świecie VUCA. Jak być skutecznym liderem w niepewnym środowisku
  • Mapa Agile & Scrum. Jak si
  • Lean dla bystrzaków. Wydanie II
  • Gra bez końca

Dodaj do koszyka Wprowadzenie do teorii obliczeń

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

Dodaj do koszyka Wprowadzenie do teorii obliczeń

Code, Publish & WebDesing by CATALIST.com.pl



(c) 2005-2024 CATALIST agencja interaktywna, znaki firmowe należą do wydawnictwa Helion S.A.