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

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 (lauras@bytegraphics.com) 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ń 2004