Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 8

Wprowadzenie do teorii obliczeń ukazało się po raz pierwszy jako wydanie wstępne w miękkiej oprawie. Pierwsze wydanie pod kilkoma istotnymi względami różni się od wydania wstępnego. Zostały dodane trzy końcowe rozdziały: rozdział 8 o złożoności pamięciowej, rozdział 9 o problemach nieobliczalnych oraz rozdział 10 poświęcony zaawansowanym zagadnieniom z teorii złożoności. Rozdział 6 został rozszerzony o kilka rozbudowanych tematów z teorii obliczalności. Inne rozdziały zostały również uzupełnione o dodatkowe przykłady i ćwiczenia.

Uwagi, jakie otrzymałem od wykładowców i studentów korzystających z wydania wstępnego, pomogły w dopracowaniu rozdziałów 0–7. Naturalnie poprawiłem też błędy, na które zwrócono mi uwagę.

Rozdziały 6 i 10 zawierają przegląd kilku bardziej zaawansowanych zagadnień należących do teorii obliczalności i złożoności. Nie mają one na celu przedstawienia tematyki w tak wyczerpujący i spójny sposób, jak pozostałe rozdziały. Rozdziały te dołączyłem, aby umożliwić nauczycielowi wybór opcjonalnych tematów, które mogą być interesujące dla studentów. Zagadnienia te same należą do różnorodnych dziedzin. Niektóre, takie jak redukowalność w sensie Turinga lub alternacje, są bezpośrednim rozwinięciem innych koncepcji omawianych w książce. Inne, takie jak rozstrzygalne teorie logiczne czy kryptografia, są tylko krótkimi wprowadzeniami do obszernych dziedzin badań.