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

Witajcie!

Za moment rozpoczniecie poznawanie fascynującej i ważnej dziedziny: teorii obliczeń. Obejmuje ona fundamentalne własności matematyczne sprzętu komputerowego, oprogramowania i ich pewnych zastosowań. Studiując tę dziedzinę, staramy się określić, co można, a czego nie można obliczyć, jak szybko można to zrobić, jak dużo potrzeba do tego pamięci i w jakiego rodzaju modelu obliczeniowym. Zagadnienia te są w oczywisty sposób związane z praktyką inżynierską, a jednocześnie, podobnie jak w wielu dziedzinach nauki, mają również aspekty czysto filozoficzne.

Wiem, że wielu z was z niecierpliwością oczekuje na poznanie tego materiału, choć być może nie wszyscy są tu z własnej woli. Być może chcecie zdobyć dyplom informatyka lub inżyniera, a wykład z teorii jest na liście wymaganych – Bóg jeden wie, dlaczego. Czyż teoria nie jest mętna, nudna, a co gorsza, nieistotna?

Czytajcie dalej, a przekonacie się, że ta teoria nie jest ani mętna czy tajemna, ani nużąca, ale całkiem zrozumiała i wręcz interesująca. Informatyka teoretyczna zawiera wiele wspaniałych, wielkich idei, choć nie brak w niej drobnych i niekiedy nudnych szczegółów, które mogą być męczące. Uczenie się nowych rzeczy zawsze jest trudne, ale może stać się łatwiejsze i bardziej przyjemne, jeśli materiał jest odpowiednio podany. Główny cel, jak postawiłem sobie przed napisaniem tej książki, to przedstawienie Czytelnikom fascynujących aspektów teorii obliczeń bez ugrzęźnięcia w zbędnych zawiłościach. Oczywiście jedynym sposobem ustalenia, czy ta teoria okaże się interesująca, jest próba nauczenia się jej.

Teoria jest blisko powiązana z praktyką. Dostarcza narzędzi myślowych, które praktycy wykorzystują w inżynierii komputerów. Projektujesz nowy język programowania do specjalnych zastosowań? Przyda się to, czego nauczysz się o gramatykach. Zajmujesz się wyszukiwaniem słów i dopasowywaniem wzorców? Pamiętaj o automatach skończonych i wyrażeniach regularnych. Stanąłeś przed problemem, którego rozwiązanie wydaje się wymagać więcej czasu, niż możesz na to przeznaczyć? Pomyśl o tym, czego nauczyłeś się o NP-zupełności. Różne obszary zastosowań, takie jak nowoczesne protokoły kryptograficzne, opierają się na zasadach teoretycznych, których nauczysz się z tej książki.

Teoria jest ważna również dlatego, że pokazuje nową, prostszą i bardziej elegancką stronę komputerów, które zwykle uważane są za bardzo złożone maszyny. Najlepsze projekty komputerów i aplikacji wyłaniają się z eleganckich koncepcji. Teoretyczny wykład może wzmocnić zmysł estetyczny i pomóc w budowaniu piękniejszych systemów.

Wreszcie teoria jest dobra, gdyż studiowanie jej rozwija umysł. Technologie komputerowe szybko się zmieniają. Szczegółowa wiedza techniczna, choć użyteczna w tej chwili, za kilka lat stanie się przestarzała. Warto więc rozwijać umiejętność myślenia, wyrażania się jasno i precyzyjnie, aby móc rozwiązywać problemy i wiedzieć, kiedy problemu nie zdołaliśmy rozwiązać. Takie umiejętności mają trwałą wartość. Studiując teorię, ćwiczymy się w tych dziedzinach.

Pomijając kwestię praktycznej przydatności, niemal każdego wykorzystującego komputery w pracy ciekawią te niezwykłe twory, ich możliwości i ograniczenia. W ciągu ostatnich trzydziestu lat rozwinęła się nowa gałąź matematyki, której badacze szukają odpowiedzi na pewne fundamentalne pytania. Oto jedno z nich, które pozostaje nierozwiązane: Jeśli weźmiemy wielką liczbę – powiedzmy o 500 cyfrach – czy możemy znaleźć jej dzielniki (liczby, przez które dzieli się ona bez reszty) w rozsądnym czasie? Nawet korzystając z superkomputera, nikt obecnie nie wie, jak tego dokonać dla każdego przypadku w czasie krótszym niż równy wiekowi wszechświata! Problem faktoryzacji (czyli problem rozkładu na czynniki) jest ściśle związany z nowoczesnymi systemami szyfrowania. Znajdź szybką metodę rozkładu liczby na czynniki, a zdobędziesz sławę!