Wprowadzenie do teorii obliczeń

„Wprowadzenie do teorii obliczeń” jest uznanym podręcznikiem, który zgłębia podstawy informatyki, koncentrując się na możliwościach współczesnych komputerów. Struktura książki obejmuje trzy główne części, które kolejno wprowadzają kluczowe zagadnienia w tej dziedzinie. Pierwsza część skupia się na automatach i językach formalnych, w tym tenatyce niedeterminizmu, oraz równoważności automatów deterministycznych i niedeterministycznych. Omawia także wyrażenia regularne, kryteria identyfikacji nieregularnych języków oraz języki bezkontekstowe.Druga część podręcznika poświęcona jest teorii obliczalności. Czytelnik zapozna się tu z ograniczeniami, przed którymi stają współczesne komputery, oraz z fundamentalnymi pojęciami rozstrzygalności i nierozstrzygalności problemów.Ostatnia część książki odnosi się do teorii złożoności obliczeniowej. Ukazuje podstawowe klasy złożoności, omawia problematykę klas NP-zupełnych oraz dostarcza klasyfikacji problemów w kontekście ich rozwiązywalności przy ograniczonych zasobach.Trzecia edycja tego podręcznika wzbogacona została o nowy podrozdział dotyczący deterministycznych języków bezkontekstowych, a także o nowe ćwiczenia, problemy oraz przykłady, co czyni ją jeszcze bardziej wartościową dla studentów informatyki na wszystkich poziomach.