Teoretyczna CS i matematyka - rekomendacje do samodzielnej nauki

14

Jestem absolwentem CS, a mój kierunek studiów nie jest związany z CS. Jednak w ramach większego planu zostania informatykiem chcę uzyskać solidne podstawy teoretycznej informatyki i matematyki w zakresie CS. Przeprowadziłem wiele badań i wybrałem następujące najlepsze / naprawdę dobre książki na temat CS i matematyki i chciałbym zapytać o twoje opinie na temat:

  • Kompletność omówionych tematów (proszę polecić wszystko, co przegapiłem)
  • Nakładanie się na obszar objęty / nadmiaru (proszę polecić książki, które należy usunąć z listy)
  • Zamów studiowanie książek (wymieniłem je w kolejności, która według mnie powinna być przestudiowana)

Lista wydaje się zbyt długa, dlatego byłbym wdzięczny za zalecenia dotyczące usunięcia niektórych książek, bez utraty podstawowej wiedzy wymaganej dla CS.

Książki są więc:

  1. Mathematician's Delight autorstwa WW Sawyer
  2. Jak to udowodnić: podejście strukturalne Daniela J. Vellemana
  3. Jak to rozwiązać: nowy aspekt metody matematycznej autorstwa G. Polya
  4. Wprowadzenie do programowania funkcjonalnego za pomocą rachunku lambda autorstwa Grega Michaelsona
  5. Podstawy informatyki autorstwa Al Aho i Jeffa Ullmana (http://i.stanford.edu/~ullman/focs.html)
  6. Konkretna matematyka: podstawa informatyki Grahama, Knutha i Patashnika
  7. Wprowadzenie do teorii obliczeń Michaela Sipsera
  8. Wprowadzenie do teorii automatów, języków i obliczeń autorstwa Johna E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  9. Złożoność obliczeniowa: perspektywa koncepcyjna Odeda Goldreicha
  10. Złożoność obliczeniowa: nowoczesne podejście autorstwa Sanjeev Arora, Boaz Barak
  11. Kurs kombinatoryki JH van Linta, RM Wilsona
  12. Obliczalność: wprowadzenie do teorii funkcji rekurencyjnych autorstwa Nigela Cutlanda
  13. Komputery i nienaruszalność: Przewodnik po teorii kompletności NP autorstwa MR Garey, DS Johnson
  14. Teoria funkcji rekurencyjnych i efektywnego obliczania autorstwa Hartleya Rogersa
  15. Nierówności: GH Hardy, JE Littlewood, G. Polya
  16. Logika matematyczna: Kurs z ćwiczeniami (część I): Rachunek zdań, Algebry Bookean, Rachunek predykatu René Cori, Daniel Lascar
  17. Logika matematyczna: Kurs z ćwiczeniami (część II): Teoria rekurencji, Twierdzenia Godela, Teoria mnogości, Teoria modeli René Cori, Daniel Lascar
CSLover
źródło
Proszę odnieść się do tego pytania cstheory.stackexchange.com/questions/3253/...
Bartosz Przybylski,
Zacznij od znanej książki o algorytmach, jeśli nie masz jeszcze doświadczenia w tym temacie.
AJed,
@Bartek: Dziękuję, ale to było jedno z pytań, na które najpierw spojrzałem, aby skompilować listę. Moje pytanie dotyczy bardziej, jak praktycznie przeczytać wszystkie wspaniałe materiały. Czas jest zawsze ograniczeniem, więc chcę wiedzieć, jakich książek powinienem „nie” czytać, aby uniknąć powtórzeń itp.
CSLover,
@AJed: Czy sugerujesz zacząć od książki nr 5 na liście zamiast niektórych książek matematycznych nr 1-4? Uważam, że # 5 daje łagodne wprowadzenie do algorytmów i struktur danych.
CSLover,
Za dużo tutaj. Po prostu wybrałbym jeden i poszedł, a potem martwiłem się, co będzie dalej, kiedy tam dotrzesz. Mogę polecić Sipser, aby zaczął od początkującego, który chce mieć solidne podstawy w podstawach CS.
usul

Odpowiedzi:

10

Twoja lista jest bardzo problematyczna.

Na początek pomijam książki 6,11,12,14,15,16,17: Książki 6, 11 i 15 to matematyka ogólna, która tak naprawdę nie jest potrzebna, chyba że zostaniesz badaczem teoretycznym . Książki 12 i 14 dotyczą teorii rekurencji, która nie jest informatyką (nawet jeśli dotyczy obliczalności!). Książki 16 i 17 zawierają zaawansowane tematy z zakresu logiki, podczas gdy wystarczy znać tylko bardzo podstawową logikę.

Z książek 1, 2, 3 wybrałbym tylko jeden, który miałby służyć jako ogólne wprowadzenie do matematyki i dowodów.

Książki 5,7,8,9,10,13 obejmują kilka tematów: teorię automatów, algorytmy i teorię złożoności. Pozwól, że zasugeruję, abyś podążał za Sipserem (Księga 7) w zakresie teorii automatów i teorii złożoności, a także Wprowadzenie do algorytmów Cormena, Leisersona, Rivesta i Steina („CLRS”) w zakresie algorytmów.

Książka 4 dotyczy programowania funkcjonalnego. Chociaż moja edukacja informatyczna nigdy nie obejmowała żadnych kursów na ten temat, można śmiało powiedzieć, że wielu badaczy informatyki teoretycznej zalicza programowanie funkcjonalne do podstawowych podstaw.

Podsumowując: pozostajesz z tym

  • Jedna z książek 1-3 (lub dowolny porównywalny tekst „wprowadzenie do dowodu”)
  • CLRS
  • Książka 4 (programowanie funkcjonalne)
  • Książka 7 (teoria automatów i teoria złożoności)
Yuval Filmus
źródło
Dziękuję bardzo za tak dokładną odpowiedź. Wiedziałem, że lista jest nadmierna, ale po przeczytaniu wszelkiego rodzaju rekomendacji książkowych dla informatyków otrzymujesz długą listę. Twoje zalecenie jest bardzo praktyczne i właśnie o to mi chodzi. Wielkie dzięki!!
CSLover,
1
Nie zgadzam się z radą, że „matematyka nie jest potrzebna”. Wybierz dowolny aspekt informatyki, a pokażę ci, jak matematyka jest potrzebna. Im więcej matematyki się uczysz, tym lepiej. Z drugiej strony, prawie niemożliwe jest samodzielne nauczenie się prawdziwej matematyki bez konieczności chodzenia do szkoły. Prawdopodobnie więc lepiej jest skoncentrować się na informatyce, która jest łatwiejsza do nauczenia.
Andrej Bauer,
5

Możesz także rozważyć skorzystanie z wielu dostępnych kursów online. Na przykład zarówno Stanford , jak i MIT oferują (bezpłatne) kursy online z informatyki, i myślę, że dostępnych jest również wiele innych.

Jeśli chodzi o książki, ja popieram większość zaleceń Yuvala, z wyjątkiem tego, że CLRS jest świetnym materiałem referencyjnym, ale trochę przytłaczającym jako książka wprowadzająca, aby po prostu usiąść i przeczytać. Dla pierwszego przejścia w części dotyczącej algorytmów mogę polecić Algorytmy autorstwa Dasgupta i in. . Poprzedni link zawiera bezpłatny wstępny wydruk online, ale kupowanie w miękkiej oprawie jest również dość tanie.

Joe
źródło
Dobrze. Doceniam twoją odpowiedź. Dziękuję Ci bardzo.
CSLover,
2

Referencje, które sugerujesz, byłyby „bardzo” teoretycznym informatykiem. ale szczerze mówiąc, nie znajduję żadnej korzyści z czytania wszystkich tych książek, jeśli nie masz dyplomu CS. Wszystko oczywiście zależy od tego, czego potrzebujesz.

Uważam, że niektóre książki, takie jak Księga 14, 15, 16, 17, nie są przeznaczone dla informatyków. Książka 3 jest pełna. To jest po prostu ogólne dla każdego ucznia. Dlatego zakładam, że książka 1 i 2 są takie same.

Dla mnie - będąc w takiej samej sytuacji, jak pierwotnie nie informatyk (a zamiast tego inżynier elektryk / informatyk) - proponuję dwa wstępne kierunki:

  • projektowanie i analiza algorytmów (wiele osób sugeruje wprowadzenie CLRS do algorytmów . To świetne odniesienie, ale tak naprawdę nie jestem jego fanem i początkowo trudniej było je zrozumieć, a czasem bardzo gadatliwie. Sugeruję jednak, abyś postępuj zgodnie ze spisem treści, a stamtąd sprawdzaj kursy online w celu uzyskania jaśniejszych referencji).

--- upewnij się, że opanowałeś język programowania w celu WDROŻENIA poznanych algorytmów i struktur danych - dlatego sugeruję serię algorytmów Sedgewick (niesamowite!)

--- DODANO: Proponuję również tę książkę: Algorytmy kombinatoryczne: generowanie, wyliczanie i wyszukiwanie według D. Krehera. To bardzo fajna książka. Daje ci różne niezależnie od wielu problemów w algorytmach.

  • kombinatoryka (szczególnie teoria grafów), kurs z kombinatoryki JH van Linta, RM Wilsona , jest dobry. Istnieje wiele innych odniesień. Zwykle wystarczy każda dobrze znana książka o kombinatoryce - wszystko, co można uzyskać z dodatkowych referencji z Internetu. Osobiście lubiłem: kombinatorykę Petera J. Camerona oraz Teorię wykresów Bondy i Murty.

  • zakład prawdopodobieństwa (zawsze konieczne). Uderzające jest to, że wiele dziedzin nauki nie wykorzystuje prawdopodobieństwa. Ale wierz mi, wszystko, co musisz wiedzieć, to podstawy.

Następnie: wielu badaczy nazywających siebie teoretycznymi informatykami tak bardzo koncentruje się na teorii obliczeń (automota i inni). Jest na to kilka dobrych książek (patrz post Yuvul Filmus),

Aho i Ullman są dobre (właściwie wszystkie książki Ullmana są dobre). Rozgość się dzięki projektowi kompilatora (patrz http://infolab.stanford.edu/~ullman/ullman-books.html ).

Potem: wszystko zależy od tego, co chcesz zrobić. Różne kierunki, które możesz obrać: 1) bazy danych, 2) rozpoznawanie wzorców i eksploracja danych, 3) algorytmy rozproszone, 4) podstawy języków programowania, 4) algorytmy losowe i wiele innych. [każdy z nich wymaga innego postu], ale spróbuj mieć pojęcie o wszystkim!

* Ogólny pomysł: jeśli dopiero zaczynasz korzystać z CS, zapewnij sobie komfort korzystania z jak największej liczby subdomen CS. Ograniczenie się do „teorii” sprawi, że stracisz dużo kreatywności CS! * (moja opinia)

AJed
źródło
Dla mnie programowanie funkcjonalne. Nie używaj starszej książki, takiej jak ta, którą zacytowałeś. Języki funkcjonalne są obecnie wymagane w branży. W Internecie istnieje kilka samouczków na temat języków takich jak Scheme, Haskel i Erlang. Nie bądź bardzo teoretyczny, to moja rada.
AJed
Wszystkie dobre komentarze. Moim celem jest zaprojektowanie kompletnego programu do samodzielnej nauki, a to pytanie dotyczy tylko części programu, która moim zdaniem była najtrudniejsza do zorganizowania. Inne obszary obejmują: struktury danych i algorytmy, architekturę komputerową, systemy operacyjne, sieci, bezpieczeństwo i kryptografię, równoległość, metody formalne, sztuczną inteligencję, grafikę i symulację, bazy danych, języki programowania, kompilatory, inżynierię oprogramowania i wreszcie filozofię i administrację Uniksa. Większość z nich, jak sądzę, ma zasadnicze znaczenie dla CS, ale uzasadniałaby osobne pytanie
CSLover
Twoja najlepsza sztuczka to silny fundament w projektowaniu i analizie algorytmów. - każde inne pole jest podpolą projektowania i analizy algorytmów.
AJed
Czy byłbyś uprzejmy i wyjaśnił, które algorytmy Sedgewick poleciłeś? Ma jeden o nazwie „Algorytmy”, ale to nie jest seria. Ma także „Algorytmy w języku C ++” (lub w innych językach), które, jak sądzę, to 2 książki z 5 częściami.
CSLover, 12.12.12
Ten, którego użyłem, to C ++. Użyłem ich jednak jako referencji. To jest jego strona internetowa cs.princeton.edu/~rs
AJed