Informacje o publikacji
| Tytuł oryginału: | Introduction To The Theory Of Computation |
| Tłumacz: | Włodarz Marek |
| Język publikacji: | polski |
| Wydanie: | 3 |
| Liczba stron: | 480 |
| Oprawa: | Miękka |
| ISBN/ISSN: | 9788301209261 |
| Producent: | Wydawnictwo Naukowe PWN S.A., ul. Gottlieba Daimlera 2, 02-460 Warszawa (PL), tel. 22 695 43 21, email: recepcja@pwn.pl |
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.
Zobacz również
