Lista książek wprowadzających do TCS dla tych, którzy niewiele wiedzą o TCS [zamknięte]

10

Jeśli musisz polecać książki komuś, kto chce dowiedzieć się więcej o TCS na poziomie wprowadzającym, takim jak teoria automatów, algorytmika, teoria złożoności itp., Jakie książki poleciłbyś tym zainteresowanym i chcącym dowiedzieć się więcej o TCS, ale nie miałeś do niego kontaktu?

education 
— Ken Li
źródło
2
Myślę, że to powinno być pytanie CW.
— Gigili,
1
Zobacz tę meta dyskusję na temat zarządzania tym pytaniem.
— Raphael
3
cstheory.SE posiada zaawansowaną listę zbyt
— Uli
1
— Gilles 'SO - przestań być zły'
2
@Gigili Nie. Listy książek były kiedyś CW, ale to już nie jest zrobione. Przeczytaj post, który podlinkowałem.
— Gilles „SO- przestań być zły”

Odpowiedzi:

9

Jeśli chcesz mieć ogólne wprowadzenie bez wchodzenia w szczegóły techniczne, proponuję Algorytmikę Davida Harela : The Spirit of Computing . Następnie jest to moja ulubiona lista:

  • Wprowadzenie Michaela Sipsera do teorii obliczeń : najlepsze wprowadzenie do teorii automatów, obliczalności i złożoności.
  • Algorytmy S. Dasgupta, CH Papadimitriou i UV Vazirani: najbardziej intuicyjne wprowadzenie do algorytmów z większym naciskiem na intuicję niż dowody techniczne.
  • Jon Bentley's Programming Pearls : nie jest to podręcznik na temat algorytmów, ale pięknie pokazuje, jak stosować techniki projektowania algorytmów do rozwiązywania prawdziwych problemów, które irytują prawdziwych programistów. :-) Może to być dobry początek, jeśli masz trochę wiedzy na temat programowania.
— Dai
źródło
DPV nie jest jeszcze w druku; czy to jest ogólnie znane?
— Raphael
Ze względu na wynik tej odpowiedzi umieściłem odpowiedzi w odpowiedzi zbiorczej . Rozważ usunięcie ze względu na jasność swojej odpowiedzi.
— Raphael
@Raphael DPV jest drukowany od kilku lat, ale wciąż jest dobrze dostępny online. Starałem się nie linkować do komercyjnej strony internetowej, takiej jak Amazon.
— Dai
@Dai: Rozumiem. Strona, do której prowadzi link, mówi: „To przedostatni szkic naszego podręcznika, który wkrótce się pojawi”. Dlatego moje zamieszanie.
— Raphael
7
— Daniil
źródło
Uważam, że książka Clarke'a jest trochę za ciężka dla kogoś bez doświadczenia w TCS. Znam (osobiście) doktorantów, którzy uważają książkę za trudną do zrozumienia.
— Dai,
@Dai, prawdopodobnie masz rację, zmieniłem go na zasady sprawdzania modelu Baiera
— Daniil
Czy można zrozumieć sprawdzanie modelu bez podstaw w logice i / lub automatach?
— Raphael
1
Dragon Book jest z pewnością dobrym odniesieniem; czy to jednak wystarczająco teoretyczne? (Naprawdę nie wiem)
— Raphael
@Raphael „Zasady” w pewien sposób stanowią wprowadzenie do logiki (przynajmniej niezbędnej wiedzy) i automatów. To także dość duża książka, ~ 980 stron. Jeśli chodzi o The Dragon Book, pomyślałem, że kompilatory to raczej teoretyczny obszar, prawda?
— Daniil,
6

Do matematyki potrzebnej w analizie algorytmów polecam jedyny GKP:

Konkretna matematyka autorstwa Grahama, Knutha, Patashnika
Kompleksowe, wysokiej jakości podejście do praktycznie całej matematyki, której będziesz potrzebować w (podstawowych) algorytmach. Jest to zabawna lektura i zawiera wiele ćwiczeń (i rozwiązań).

— Raphael
źródło
Próbowałem czytać tę książkę, ale mi się nie podobało, ponieważ wszystko wydawało się bardzo ... niezdarne i skupione. Po prostu nie czułem tam piękna matematyki. Porównaj to z konspektem teorii automatów Sipsera lub książkami Smullyana na temat logiki, a nawet abstrakcyjną algebrą Dummita i Foote'a. Może to tylko ja, tho.
— Daniil
Popieram Daniila. To zbiór doskonałych narzędzi dla teoretyków. Ale jest zbyt suchy i techniczny, aby był przyjemny dla początkujących. Naprawdę lubię książki, o których wspomniałem powyżej, ponieważ wydają się mieć własne dusze. Czytają tak, jakby ktoś opowiadał ci historie, interesujące.
— Dai,
Niestety, nie obejmuje indukcji strukturalnej, koindukcji, teorii domen i wszystkich innych rzeczy potrzebnych do TCS typu Teoria B.
— Dave Clarke
@DaveClarke: Poprawnie. Nie jestem pewien, czy spodziewałbym się, że jakakolwiek książka matematyczna zawiera coś takiego. Ale GKP ma być książką matematyki cs. Nie zawiera też logiki, więc powinnam trochę sformułować.
— Raphael
2
@DaveClarke, czy możesz nam polecić kilka książek na temat matematyki teorii B?
— Daniil
5

Algorytmy 4. Edycja R. Sedgewick

Wprowadzenie do analizy algorytmów P. Flajolet, R. Sedgewick

Wprowadzenie do teorii automatów, języków i obliczeń JE Hopcroft, JD Ullman, (R. Motwani)
Pierwsze wydanie z 1979 roku ma więcej wyników teoretycznych, których brakuje w drugim wydaniu z 2001 roku. Jeszcze nie spojrzałem na trzeciego Eda.

Wprowadzenie do formalnej teorii języka MA Harrison
Pochodzi z 1978 roku, ale nadal chciałbym zobaczyć ją na liście.

Logicomix: epickie poszukiwanie prawdy A. Doxiadis, CH Papadimitriou
Ponieważ jest całkowicie niesamowite!

Ponownie 1979
Garey and Johnson's Computers and Intractability: Przewodnik po teorii kompletności NP

Chciałbym mieć TAoCP na liście, ale obawiam się, że skrupulatne podejście dona Knutha nie jest niczym, co można by uznać za „wprowadzające”. Niestety ...

— uli
źródło
Logicomix to z pewnością klejnot, nie mówiąc, że inni nie.
— Dave Clarke
Nie podoba mi się sposób, w jaki Logicomix przedstawiał Logików jako „szalonych” ludzi. Pomysły w logice, gdy są odpowiednio wyjaśnione, są bardzo przyziemne i proste, a nie tak „szalone”.
— Dai,
1
@Dai Rzuć okiem na życie niezwykłych ludzi, takich jak np. Gödel, Wittgenstein, Nash itp. Byli ... niezwykli.
— uli
Które z nich są naprawdę dla początkujących?
— Raphael
@Raphael IMHO wszystkie, w przeciwnym razie nie zamieściłbym ich tutaj. Niektóre mogą mieć stromą krzywą uczenia się, ale myślę, że to w porządku.
— uli
4

Jeśli jesteś zupełnie nowy w dziedzinie TCS, to Wprowadzenie Sipsera do teorii obliczeń jest zdecydowanie najlepszą książką na początek. Czytałem inne książki wprowadzające i żadna z nich, moim zdaniem, nie zbliża się do sposobu, w jaki Sipser przyniósł sprawę.

Inne, bardziej szczegółowe, dobre książki teoretyczne to:

— codd
źródło
Już wspomniano powyżej.
— Dave Clarke
@DaveClarke Planowałem dodać więcej zasobów do listy, tak jak zrobiłem to teraz z moją edycją, ale chciałem również podkreślić, jak wspaniała jest książka Sipsera, wspominając ją ponownie! :-)
— codd
1
Książka Pierce'a to klejnot. Chciałbym, żeby to było w okolicy, kiedy robiłem doktorat (w typach).
— Dave Clarke
@DaveClarke Obecnie używam go do mojej pracy licencjackiej według rekomendacji mojego doradcy i jestem też pod wielkim wrażeniem!
— Codd
1
Dzięki za referencję, przyjrzę się jej dzisiaj. Widzę, że jesteś profesorem w KUL. Przyjeżdżam tam w przyszłym roku, aby studiować Bezpieczne oprogramowanie (oprogramowanie Veilige). Co za mały świat.
— codd
3

Kilka dobrych książek dotyczących części teorii TCS:

  • Logika w CS : Logika w informatyce: Modelowanie i rozumowanie systemów: Michael Huth i Mark Ryan.
    Szeroki zakres różnych zastosowań logiki w informatyce. Około trzeciego roku studiów licencjackich.

  • Rachunek Lambda : Rachunek Lambda i Kombinatory. Wprowadzenie J. Rogera Hindleya i Jonathana P. Seldina.
    Wprowadza rachunek lambda, który jest niezbędnym składnikiem podstaw języków programowania. Około trzeciego roku studiów licencjackich.

  • Wprowadzenie do teorii domen : Wprowadzenie do krat i porządku (wydanie 2) autorstwa Davey, BA i Priestley, HA Cambridge University Press. (2002).
    Obejmuje bardzo przydatny temat, szczególnie jeśli planujesz pracować z semantyką. Jest to trochę bardziej matematyczne niż inne tematy, ale wczesne rozdziały z pewnością są na zaawansowanym poziomie licencjackim.

  • Semantyka : Semantyka z aplikacjami: przekąska : Hanne Riis Nielson i Flemming Nielson.
    Naprawdę miłe wprowadzenie do semantyki języka programowania. Zamiast zagłębiać się w jakikolwiek konkretny formalizm, daje szeroką prezentację i obejmuje aplikacje ogólnie nieuwzględnione w innych książkach dotyczących semantyki. Może być przydatny dla studentów drugiego roku.

— Dave Clarke
źródło
Nie znam żadnego z nich nawet ze względu na reputację, więc nie mogę powiedzieć, czy są one dobre (nawet jeśli jestem skłonny uwierzyć ci na słowo). : /
— Raphael
1
Dodałem opis każdej książki. Wszystkie są dobre.
— Dave Clarke
3

To jest odpowiedź zbiorcza, która zawiera książki z odpowiedzi z wynikiem co najmniej pięciu. Omów jego treść na czacie .

Algorytmy i struktury danych

  • Wprowadzenie do algorytmów autorstwa Cormena, Leisersona, Rivesta, Steina (3. edycja 2009)
    Kompleksowe podejście do podstawowych algorytmów i struktur danych oraz ich analizy bez głębokiego kopania.
  • Algorytmy Dasgupta, Papadimitriou, Vazirani (2006)
    Najbardziej intuicyjne wprowadzenie do algorytmów z większym naciskiem na intuicję niż dowody techniczne.

Obliczalność i złożoność

Języki formalne i automaty

Teoria Stosowana

  • Zasady sprawdzania modelu autorstwa Baiera, Katoen (2008)
    Ogromna książka, którą można wykorzystać jako kompleksowe wprowadzenie do sprawdzania modelu.
  • Programming Pearls autorstwa Jona Bentleya (2nd ed 1999)
    Nie jest podręcznikiem na temat algorytmów, ale pięknie pokazuje, jak używać technik projektowania algorytmów do rozwiązywania prawdziwych problemów. Może to być dobry początek, jeśli masz trochę wiedzy na temat programowania.
— Raphael
źródło
To nie odpowiada na pytanie, a jeśli ma to na celu, nie jest dobrą odpowiedzią. Czy masz na myśli, że ktoś rozpoczynający TCS musi przeczytać wszystkie te książki? Jeśli nie, jak by wybrali? Pamiętaj, że zgodnie z twoją regułą odpowiedź ta prawdopodobnie będzie zawierać setki książek
— Gilles „SO- przestań być zły”
@Raphael Czy uprzejmie jest prosić kogoś innego o usunięcie jego / jej własnej odpowiedzi? Zwykle sam pytający może dokonać agregacji swoich ulubionych odpowiedzi, modyfikując własny tekst pytania, ale nigdy nie widziałem, aby ktokolwiek zmusił inną osobę do usunięcia własnego posta w celu utworzenia własnej odpowiedzi. Ta wymiana stosów staje się dziwna z powodu tych narcystycznych zachowań.
— Dai
@Raphael: Uczynienie z niego CW nie uprawnia do poproszenia kogoś o usunięcie własnej odpowiedzi. To tak, jakby napisać, że napiszę książkę / ankietę (którą opublikuję za darmo w Internecie), więc rozglądam się i pytam wszystkich autorów, których artykuły cytuję, by zdjęli własne, aby uniknąć zamieszania.
— Dai
@Raphael Nie widzę żadnego miejsca w licencjach CC, które mówią, że moja praca zostanie ostatecznie zlecona przez kogoś innego. Nie wiem, jaką fantazję masz w SE, ale zdecydowanie nie jest to Wikipedia. Wiem, że ciężko pracujesz, aby „moderować” tę witrynę, ale szanuj także czyjąś wolność słowa i prywatność, i po prostu pozwól głosom w górę / w dół zająć się resztą. Myślę, że celem cs SE jest zapewnienie bardziej przyjaznego forum niż cstheory SE dla początkujących, ale zaproponowany tutaj mikro poziom zarządzania znacznie go pogorszył.
— Dai
— Raphael
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.