Biuletyn PW / Publikacje / Wprowadzenie do teorii obliczeń

Wprowadzenie do teorii obliczeń

Wprowadzenie do teorii obliczeń to publikacja dotycząca podstaw informatyki, a w szczególności możliwości obliczeniowych współczesnych komputerów. Polecana szczególnie studentom informatyki.

Książka składa się z trzech części. Pierwsza dedykowana jest 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. Ostatnia, trzecia część dotyczy 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.

Najnowsza edycja zawiera podrozdział na temat deterministycznych języków bezkontekstowych. Została również wzbogacona o dodatkowe ćwiczenia, problemy i przykłady.

Michael Sipser, Wprowadzenie do teorii obliczeń, Warszawa 2020, Wydawnictwo Naukowe PWN

CYTAT TYGODNIA

"

 

Ważne jest,
by nigdy nie przestać pytać.
Wielki płomień
rodzi się z małej iskry

Dante

"

KONTAKT

Biuletyn Politechniki Warszawskiej

Pl. Politechniki 1, 00-661 Warszawa

Tel. 22 234 71 71, 22 234 71 81

Biuro Komunikacji i Promocji Politechniki Warszawskiej

REDAKCJA

Biuletyn Politechniki Warszawskiej
Wydawnictwo elektroniczne skierowane do społeczności Uczelni redagowane przez Biuro Komunikacji i Promocji.

Zapraszamy do zgłaszania wydarzeń!

Redakcja Biuletynu Politechniki Warszawskiej

DEKLARACJA DOSTĘPNOŚCI