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

Książka ta jest przeznaczona jako podręcznik z zakresu informatyki teoretycznej dla studentów studiów magisterskich oraz wyższych lat studiów licencjackich i inżynierskich. Zagadnienia przedstawione są matematycznie, oparte na twierdzeniach i dowodach. Dołożyłem starań, aby wprowadzić studentów mających niewielkie doświadczenie w dowodzeniu twierdzeń, ale bardziej zaawansowanym studentom będzie to przychodziło łatwiej.

Moim głównym celem było przedstawienie materiału w sposób przejrzysty i interesujący. Z tego względu przedkładałem intuicję i obraz ogólny nad drobiazgowe analizy szczegółów niższego poziomu.

Na przykład, choć przedstawiłem metodę dowodu przez indukcję w rozdziale Ø wraz z innymi podstawami matematycznymi, nie odgrywa ona istotnej roli w dalszej części książki. W ogólności nie pokazuję typowych indukcyjnych dowodów poprawności różnych konstrukcji dotyczących automatów. Jeżeli zostaną jasno przedstawione, to konstrukcje takie bronią się same i nie wymagają dalszego uzasadniania. Indukcja mogłaby raczej zaciemniać, niż wyjaśniać problem, gdyż sama w sobie jest dość wyrafinowaną techniką, niezrozumiałą dla wielu osób. Objaśnianie oczywistych faktów przez indukcję stwarza ryzyko, że studenci utrwalą przekonanie, że dowód matematyczny jest rodzajem formalnej manipulacji, zamiast nauczyć ich odróżniania przekonywającej argumentacji od nieprzekonywającej.

Drugi przykład występuje w częściach drugiej i trzeciej, gdzie opisuję algorytmy językiem potocznym zamiast posługiwania się pseudokodem. Nie poświęciłem zbyt wiele czasu na programowanie maszyn Turinga (ani żadnego innego formalnego modelu). Dzisiejsi studenci mają przygotowanie programistyczne i hipoteza Churcha-Turinga jest dla nich oczywista. Dlatego nie przedstawiam długich symulacji jednego modelu przez drugi, aby wykazać ich równoważność.

Mimo że większą rolę przyznaję intuicji i pominijam pewne szczegóły, przedstawiam materiał w sposób, który można nazwać klasycznym. Większość teoretyków uzna, że dobór materiału, terminologia i kolejność prezentacji są zgodne z tym, co jest zawarte w innych szeroko wykorzystywanych podręcznikach. Własną oryginalną terminologię wprowadziłem jedynie w kilku miejscach, gdy uznałem, że standardowo wykorzystywane pojęcia są szczególnie niejasne lub mylące. Wprowadziłem na przykład pojęcie redukcji przez odwzorowanie w miejsce redukcji wiele do jednego.

Ćwiczenie przez rozwiązywanie zadań jest podstawą nauki dowolnej dziedziny matematycznej. Przedstawione w książce zadania zostały podzielone na dwie kategorie: Ćwiczenia i Zadania. Ćwiczenia mają na celu przypomnienie i utrwalenie definicji i pojęć. Zadania wymagają pewnej kreatywności. Zadania oznaczone gwiazdką są trudniejsze. Starałem się, aby rozwiązywanie zarówno ćwiczeń, jak i zadań było ciekawym wyzwaniem dla studentów.