Wprowadzenie do teorii obliczeń - Michael Sipser - książka

„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.