Podręcznik do teorii obliczeń skierowany do studentów informatyki na wszystkich wyższych uczelniach. 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, a także deterministycznym językom bezkontekstowym.
- Autor: Michael Sipser
- Kategoria: informatyka, matematyka
- Język: polski
- ISBN: 9788301209261
- Data wydania: 2020-02-25
- Liczba stron: 500
- Tłumaczenie: Marek Włodarz
- Ocena: 0,0
- Wydawnictwo: Wydawnictwo Naukowe PWN
