Teoretyczna CS i matematyka - rekomendacje do samodzielnej nauki

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

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)

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.

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)