Wprowadzenie do teorii obliczeń - ebook

Przedmowa do pierwszego wydania

Do studentów

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ę!

Do nauczycieli

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.

Pierwsze wydanie

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

Uwagi do autora

Internet stwarza nowe możliwości interakcji między autorami a czytelnikami. Otrzymałem wiele e-maili zawierających sugestie, pochwały i uwagi krytyczne, w tym także zgłoszenia błędów występujących w wydaniu wstępnym. Proszę, piszcie nadal! Staram się odpowiadać na każdą wiadomość, gdy tylko pozwala mi czas. Adres, pod który należy kierować korespondencję dotyczącą tej książki, to

[email protected].

Na bieżąco prowadzona jest również strona internetowa zawierająca erratę książki. Na stronie tej mogą pojawiać się też inne materiały przydatne dla nauczycieli i studentów. Będę wdzięczny za informacje, co mogłoby się tam znaleźć. Strona ta jest dostępna pod adresem:

http://math.mit.edu/~sipser/book.html.

Podziękowania

Nie mógłbym napisać tej książki bez pomocy wielu przyjaciół, kolegów i mojej rodziny.

Chciałbym podziękować moim nauczycielom, którzy pomogli ukształtować moje poglądy naukowe i metody nauczania. Pięciu z nich wyróżnia się szczególnie. Mój promotor, Manuel Blum, zasługuje na szczególną uwagę za wyjątkową zdolność do inspirowania studentów dzięki przejrzystości przedstawianych myśli, entuzjazm i opiekę. Jest wzorem dla mnie i wielu innych. Jestem także wdzięczny Richardowi Karpowi za wprowadzenie mnie w tajniki teorii złożoności, Johnowi Addisonowi za nauczenie mnie logiki i przygotowywanie wspaniałych zadań domowych, Jurisowi Hartmanisowi za wprowadzenie w teorię obliczeń oraz mojemu ojcu za nauczenie mnie podstaw matematyki, posługiwania się komputerami i sztuki przekazywania wiedzy.

Książka to powstała na podstawie notatek do wykładu, który prowadziłem w MIT przez ostatnie 15 lat. Spisali je studenci uczestniczący w moich wykładach. Mam nadzieję, że wybaczą mi, że nie wymienię ich wszystkich. Asystenci, którzy pracowali ze mną przez te lata – Avrim Blum, Thang Bui, Benny Chor, Andrew Chou, Stavros Cosmadakis, Aditi Dhagat, Wayne Goddard, Parry Husbands, Dina Kravets, Jakov Kučan, Brian O’Neill, Ioana Popescu i Alex Russell – pomogli w redagowaniu i rozwinięci tych notatek. Są także autorami niektórych ćwiczeń i zadań.

Prawie trzy lata temu Tom Leighton przekonał mnie do napisania podręcznika z teorii obliczeń. Rozmyślałem nad tym od pewnego czasu, ale to argumentacja Toma pozwoliła przekształcić teorię w praktykę. Jestem mu wdzięczny za liczne rady dotyczące pisania książek i wiele innych rzeczy.

Chciałbym podziękować za uwagi, komentarze i pomoc w trakcie pisania książki, jakiej udzielili mi Eric Bach, Peter Beebee, Cris Calude, Marek Chrobak, Anna Chefter, Guang-Ien Cheng, Elias Dahlhaus, Michael Fischer, Steve Fisk, Lance Fortnow, Henry J. Friedman, Jack Fu, Seymour Ginsburg, Oded Goldreich, Brian Grossman, David Harel, Micha Hofri, Dung T. Huynh, Neil Jones, H. Chad Lane, Kevin Lin, Michael Loui, Silvio Micali, Tadao Murata, Christos Papadimitriou, Vaughan Pratt, Daniel Rosenband, Brian Scassellati, Ashish Sharma, Nir Shavit, Alexander Shen, Ilya Shlyakhter, Matt Stallmann, Perry Susskind, Y. C. Tay, Joseph Traub, Osamu Watanabe, Peter Widmayer, David Williamson, Derick Wood i Charles Yang.

Następujące osoby przekazały dodatkowe komentarze i uwagi, które pozwoliły ulepszyć tę książkę: Isam M. Abdelhameed, Eric Allender, Shay Artzi, Michelle Atherton, Rolfe Blodgett, Al Briggs, Brian E. Brooks, Jonathan Buss, Jin Yi Cai, Steve Chapel, David Chow, Michael Ehrlich, Yaakov Eisenberg, Farzan Fallah, Shaun Flisakowski, Hjalmtyr Hafsteinsson, C. R. Hale, Maurice Herlihy, Vegard Holmedahl, Sandy Irani, Kevin Jiang, Rhys Price Jones, James M. Jowdy, David M. Martin Jr., Manrique Mata-Montero, Ryota Matsuura, Thomas Minka, Farooq Mohammed, Tadao Murata, Jason Murray, Hideo Nagahashi, Kazuo Ohta, Constantine Papageorgiou, Joseph Raj, Rick Regan, Rhonda A. Reumann, Michael Rintzler, Arnold L. Rosenberg, Larry Roske, Max Rozenoer,Walter L. Ruzzo, Sanatan Sahgal, Leonard Schulman, Steve Seiden, Joel Seiferas, Ambuj Singh, David J. Stucki, Jayram S. Thathachar, H. Venkateswaran, Tom Whaley, Christopher Van Wyk, Kyle Young oraz Kyoung Hwan Yun.

Robert Sloan wykorzystał roboczą wersję książki w swoim wykładzie i przekazał mi nieocenione uwagi i pomysły wynikające z tego doświadczenia. Mark Herschberg, Kazuo Ohta i Latanya Sweeney przeczytali części rękopisu i zasugerowali liczne poprawki. Shafi Goldwasser pomogła mi przy pracy nad materiałem do rozdziału 10.

Otrzymałem pomoc techniczną od Williama Baxtera z firmy Superscript, który napisał pakiet makr w L^(A)T_(E)X-u, implementujący układ wewnętrzny książki, oraz od Larry’ego Nolana z wydziału matematycznego MIT, który zadbał o to, by wszystko działało.

Przyjemnością była współpraca z ekipą z PWS Publishing przy tworzeniu wersji finalnej. Wspomnę tu tylko Michaela Sugarmana, Davida Dietza, Elise Kaiser, Monique Calello, Susan Garland oraz Tanję Brull, gdyż to z nimi miałem większość kontaktów, ale zdaję sobie sprawę, że w pracę zaangażowanych było wiele innych osób. Dziękuję Jerry’emu Moore’owi za redakcję tekstu, Diane Levy za projekt okładki oraz Catherine Hawkes za projekt układu wewnętrznego.

Dziękuję National Science Foundation za wsparcie w ramach grantu CCR-9503322.

Mój ojciec, Kenneth Sipser, oraz siostra, Laura Sipser, przekształcili rysunki zamieszczone w książce na postać elektroniczną. Moja druga siostra, Karen Fisch, ratowała nas z różnych komputerowych opresji, a moja mama, Justine Sipser, służyła matczynymi radami. Dziękuję im wszystkich za wsparcie w trudnych warunkach, w tym przy zwariowanych terminach i opornym oprogramowaniu.

Na koniec kieruję wyrazy miłości do mojej żony Iny i córki Rachel. Dziękuję, że zniosłyście to wszystko.

Michael Sipser

Cambridge, Massachusetts, październik 1996Przedmowa do drugiego wydania

Sądząc z e-maili, które otrzymałem od tak wielu czytelników, największą wadą pierwszego wydania był brak przykładowych rozwiązań choćby niektórych zadań. Zatem już są. Każdy rozdział zawiera teraz nowy punkt zatytułowany Wybrane rozwiązania, w którym są odpowiedzi na reprezentatywny wybór ćwiczeń i zadań z tego rozdziału. Aby uzupełnić zmniejszony w ten sposób wybór zadań do samodzielnego rozwiązania, dodałem także sporo nowych ćwiczeń i zadań. Wykładowcy mogą też zamówić Podręcznik nauczyciela zawierający dodatkowe rozwiązania. W tym celu należy się skontaktować z regionalnym przedstawicielem handlowym wskazanym na stronie www.course.com.

Wielu czytelników domagało się szerszego omówienia niektórych „standardowych” zagadnień, a w szczególności twierdzenia Myhilla-Neroda oraz twierdzenia Rice’a. Częściowo zastosowałem się do tych próśb, rozwijając te zagadnienia jako zadania z rozwiązaniami. Nie zamieściłem twierdzenia Myhilla-Neroda w zasadniczym tekście, gdyż uważam, że ten wykład powinien zapewniać jedynie wprowadzenie do teorii automatów skończonych, a nie jej pogłębioną analizę. W moim ujęciu rola automatów skończonych w tej książce polega na tym, aby studenci mogli poznać prosty formalny model obliczeń jako preludium do silniejszych modeli, a także aby stanowiły podstawę wygodnych przykładów przy omawianiu dalszych zagadnień. Oczywiście niektórzy będą woleli bardziej szczegółowe potraktowanie tego tematu, podczas gdy inni chcieliby, abym w ogóle pominął wszelkie wzmianki o automatach skończonych (a przynajmniej nie uzależniał od nich późniejszych zagadnień). Nie włączyłem twierdzenia Rice’a do zasadniczego tekstu książki, gdyż, mimo że jest to użyteczne narzędzie dowodzenia nierozstrzygalności, niektórzy studenci mogliby posługiwać się nim mechanicznie, bez prawdziwego zrozumienia istoty problemu. Dowodzenie nierozstrzygalności za pomocą redukcji zamiast twierdzenia Rice’a daje lepsze przygotowanie do redukcji, które pojawiają się później w teorii złożoności.

Jestem wdzięcznym dłużnikiem moich asystentów, którzy pomogli mi w opracowaniu niektórych nowych zadań i rozwiązań. Są to Ilya Baran, Sergi Elizalde, Rui Fan, Jonathan Feldman, Venkatesan Guruswami, Prahladh Harsha, Christos Kapoutsis, Julia Khodor, Adam Klivans, Kevin Matulef, Ioana Popescu, April Rasala, Sofya Raskhodnikova oraz Iuliu Vasilescu. W opracowywaniu rozwiązań brali również udział Ching W. Law, Edmond Kayi Lee i Zulfikar Ramzan. Dziękuję Victorowi Shoupowi za znalezienie prostego sposobu załatania luki w analizie probabilistycznego algorytmu sprawdzania pierwszości liczb, która występowała w pierwszym wydaniu.

Dziękuję osobom z Course Technology za motywowanie mnie i innych uczestników tego projektu, a zwłaszcza Alyssi Pratt Aimee Poirier. Wielkie podziękowania należą się też Geraldowi Eismanowi, Weizhenowi Mao, Rupakowi Majumdarowi, Chrisowi Umansowi i Christopherowi Wilsonowi za recenzje. Jestem też zobowiązany Jerry’emu Moore’owi za świetną robotę przy redakcji tekstu i Laurze Segel z firmy ByteGraphics ([email protected]) za przepiękne opracowanie rysunków.

Liczba e-maili, które dostałem, przekroczyła moje oczekiwania. Otrzymywanie wiadomości z tak wielu miejsc było wspaniałym doświadczeniem i starałem się odpowiadać wszystkim – proszę o wybaczenie tych, których pominąłem. Wymieniam tu te osoby, których sugestie miały szczególny wpływ na to wydanie, ale wszystkim dziękuję za korespondencję:

Luca Aceto, Arash Afkanpour, Rostom Aghanian, Eric Allender, Karun Bakshi, Brad Ballinger, Ray Bartkus, Louis Barton, Arnold Beckmann, Mihir Bellare, Kevin Trent Bergeson, Matthew Berman, Rajesh Bhatt, Somenath Biswas, Lenore Blum, Mauro A. Bonatti, Paul Bondin, Nicholas Bone, Ian Bratt, Gene Browder, Doug Burke, Sam Buss, Vladimir Bychkovsky, Bruce Carneal, Soma Chaudhuri, Rong-Jaye Chen, Samir Chopra, Benny Chor, John Clausen, Allison Coates, Anne Condon, Jeffrey Considine, John J. Crashell, Claude Crepeau, Shaun Cutts, Susheel M. Daswani, Geoff Davis, Scott Dexter, Peter Drake, Jeff Edmonds, Yaakov Eisenberg, Kurtcebe Eroglu, Georg Essl, Alexander T. Fader, Farzan Fallah, Faith Fich, Joseph E. Fitzgerald, Perry Fizzano, David Ford, Jeannie Fromer, Kevin Fu, Atsushi Fujioka, Michel Galley, K. Ganesan, Simson Garfinkel, Travis Gebhardt, Peymann Gohari, Ganesh Gopalakrishnan, Steven Greenberg, Larry Griffith, Jerry Grossman, Rudolf de Haan, Michael Halper, Nick Harvey, Mack Hendricks, Laurie Hiyakumoto, Steve Hockema, Michael Hoehle, Shahadat Hossain, Dave Isecke, Ghaith Issa, Raj D. Iyer, Christian Jacobi, Thomas Janzen, Mike D. Jones, Max Kanovitch, Aaron Kaufman, Roger Khazan, Sarfraz Khurshid, Kevin Killourhy, Seungjoo Kim, Victor Kuncak, Kanata Kuroda, Thomas Lasko, Suk Y. Lee, Edward D. Legenski, Li-Wei Lehman, Kong Lei, Zsolt Lengvarszky, Jeffrey Levetin, Baekjun Lim, Karen Livescu, Stephen Louie, Tzer Hung Low, Wolfgang Maass, Arash Madani, Michael Manapat, Wojciech Marchewka, David M. Martin Jr., Anders Martinson, Lyle McGeoch, Alberto Medina, Kurt Mehlhorn, Nihar Mehta, Albert R. Meyer, Thomas Minka, Mariya Minkova, Daichi Mizuguchi, G. Allen Morris III, Damon Mosk-Aoyama, Xiaolong Mou, Paul Muir, German Muller, Donald Nelson, Gabriel Nivasch, Mary Obelnicki, Kazuo Ohta, Thomas M. Oleson, Jr., Curtis Oliver, Owen Ozier, Rene Peralta, Alexander Perlis, Holger Petersen, Detlef Plump, Robert Prince, David Pritchard, Bina Reed, Nicholas Riley, Ronald Rivest, Robert Robinson, Christi Rockwell, Phil Rogaway, Max Rozenoer, John Rupf, Teodor Rus, Larry Ruzzo, Brian Sanders, Cem Say, Kim Schioett, Joel Seiferas, Joao Carlos Setubal, Geoff Lee Seyon, Mark Skandera, Bob Sloan, Geoff Smith, Marc L. Smith, Stephen Smith, Alex C. Snoeren, Guy St-Denis, Larry Stockmeyer, Radu Stoleru, David Stucki, Hisham M. Sueyllam, Kenneth Tam, Elizabeth Thompson, Michel Toulouse, Eric Tria, Chittaranjan Tripathy, Dan Trubow, Hiroki Ueda, Giora Unger, Kurt L. Van Etten, Jesir Vargas, Bienvenido Velez-Rivera, Kobus Vos, Alex Vrenios, Sven Waibel, Marc Waldman, Tom Whaley, Anthony Widjaja, Sean Williams, Joseph N. Wilson, Chris Van Wyk, Guangming Xing, Vee Voon Yee, Cheng Yongxi, Neal Young, Timothy Yuen, Kyle Yung, Jinghua Zhang, Lilla Zollei.

Podziękowania należą się też osobom, które wskazały błędy w pierwszym wydaniu: Suzanne Balik, Matthew Kane, Kurt L. Van Etten, Nancy Lynch, Gregory Roberts oraz Cem Say.

Przede wszystkim zaś dziękuję mojej rodzinie – Inie, Rachel i Aaronowi – za ich cierpliwość, wyrozumiałość i uczucie, gdy przez niekończące się godziny tkwiłem przed ekranem mojego komputera.

Michael Sipser

Cambridge, Massachusetts, grudzień 2004Przedmowa do trzeciego wydania

Trzecie wydanie zawiera zupełnie nowy podrozdział poświęcony deterministycznym językom bezkontekstowym. Wybrałem ten temat z kilku powodów. Po pierwsze, wypełnia oczywistą lukę w poprzednim ujęciu teorii automatów i języków formalnych. Starsze wydania wprowadzały pojęcia automatów skończonych i maszyn Turinga w wariantach deterministycznych i niedeterministycznych, ale omawiałem w nich tylko niedeterministyczne wersje automatów ze stosem. Dodanie omówienia deterministycznych automatów ze stosem jest brakującym fragmentem układanki.

Po drugie, teoria deterministycznych języków bezkontekstowych jest podstawą gramatyk LR(k), ważnego i nietrywialnego zastosowania teorii automatów w projektowaniu języków programowania i kompilatorów. To zastosowanie łączy wiele kluczowych koncepcji, w tym równoważność deterministycznych i niedeterministycznych automatów skończonych oraz przekształcanie gramatyk bezkontekstowych na automaty ze stosem i odwrotnie, doprowadzając do wydajnej i pięknej metody parsingu. Mamy tu więc rzeczywiste współdziałanie teorii i praktyki.

Na koniec zagadnienie to wydaje się nie dość wyczerpująco omówione w istniejących podręcznikach teorii obliczeń, jeśli weźmiemy pod uwagę jego ważność jako naturalnego zastosowania teorii automatów. Gramatyki LR(k) studiowałem lata temu, ale nie osiągnąłem wówczas pełnego zrozumienia ich działania i nie dostrzegłem, jak pięknie pasują one do teorii deterministycznych języków bezkontekstowych. Pisząc ten podrozdział, miałem na celu przedstawienie intuicyjnego, ale ścisłego wprowadzenia do tej dziedziny, zarówno dla teoretyków, jak i praktyków, a tym samym chciałem przyczynić się do szerszego docenienia tych zagadnień. Muszę jednak dodać pewne ostrzeżenie: część materiału zawartego w tym podrozdziale jest dość wymagająca, zatem nauczyciel prowadzący pierwszy, podstawowy wykład teorii może wybrać go na lekturę dodatkową. Późniejsze rozdziały nie zależą i nie odwołują się do treści tego podrozdziału.

Wiele osób miało bezpośredni lub pośredni udział w powstawaniu tego wydania. Jestem wdzięczny recenzentom Christosowi Kapoutsisowi i Cem Say, którzy przeczytali szkic nowej części i podzielili się wartościowymi uwagami. W produkcji brało udział wiele osób z Cengage Learning, a szczególnie Alyssa Pratt i Jennifer Feltri-George. Suzanne Huizenga zredagowała tekst, a Laura Segel z firmy ByteGraphics przygotowała nowe ilustracje i zmodyfikowała niektóre spośród starszych rysunków.

Chciałbym podziękować moim asystentom z MIT, Victorowi Chenowi, Andy’emu Druckerowi, Michaelowi Forbesowi, Elenie Grigorescu, Brendanowi Juba, Christosowi Kapoutsisowi, Jonowi Kelnerowi, Swastikowi Kopparty, Kevinowi Matulef, Amandzie Redlich, Zackowi Remscrimowi, Benowi Rossmanowi, Shubhangi Saraf oraz Orenowi Weimannowi. Każde z nich pomogło mi, omawiając nowe zadania i ich rozwiązania, i dając wgląd w to, jak dobrze nasi studenci rozumieją zawartość wykładu. Praca z tak utalentowanymi i entuzjastycznymi młodymi ludźmi jest prawdziwą przyjemnością.

Wielką nagrodą jest otrzymywanie e-maili z uwagami i komentarzami z całego świata. Dziękuję za wszystkie sugestie, pytania i pomysły. Oto lista tych korespondentów, których uwagi wpłynęły na kształt tego wydania:

Djihed Afifi, Steve Aldrich, Eirik Bakke, Suzanne Balik, Victor Bandur, Paul Beame, Elazar Birnbaum, Goutam Biswas, Rob Bittner, Marina Blanton, Rodney Bliss, Promita Chakraborty, Lewis Collier, Jonathan Deber, Simon Dexter, Matt Diephouse, Peter Dillinger, Peter Drake, Zhidian Du, Peter Fejer,Margaret Fleck, Atsushi Fujioka, Valerio Genovese, Evangelos Georgiadis, Joshua Grochow, Jerry Grossman, Andreas Guelzow, Hjalmtyr Hafsteinsson, Arthur Hall III, Cihat Imamoglu, Chinawat Isradisaikul, Kayla Jacobs, Flemming Jensen, Barbara Kaiser, Matthew Kane, Christos Kapoutsis, Ali Durlov Khan, Edwin Sze Lun Khoo, Yongwook Kim, Akash Kumar, Eleazar Leal, Zsolt Lengvarszky, Cheng-Chung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, Hans-Rudolf Metz, Mladen MikŜa, Sara Miner More, Rajagopal Nagarajan, Marvin Nakayama, Jonas Nyrup, Gregory Roberts, Ryan Romero, Santhosh Samarthyam, Cem Say, Joel Seiferas, John Sieg, Marc Smith, John Steinberger, Nuri Tas¸demir, Tamir Tassa, Mark Testa, Jesse Tjang, John Trammell, Hiroki Ueda, Jeroen Vaelen, Kurt L. Van Etten, Guillermo Vazquez, Phanisekhar Botlaguduru Venkata, Benjamin Bing-Yi Wang, Lutz Warnke, David Warren, ThomasWatson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi.

Ponad wszystko zaś dziękuję mojej rodzinie – mojej żonie Inie i naszym dzieciom Racheli i Aaronowi. Czas jest skończony i umyka szybko. Wasza miłość jest wszystkim.

Michael Sipser

Cambridge, Massachusetts, kwiecień 2012