Theoretische CS und Mathematik - Empfehlungen zum Selbststudium

14

Ich bin ein Nicht-CS-Absolvent und mein Studienfach ist nicht mit CS verbunden. Als Teil eines größeren Plans, Informatiker zu werden, möchte ich jedoch solide Kenntnisse in theoretischer Informatik und Mathematik in Bezug auf CS erwerben. Ich habe viel recherchiert und die folgenden besten / wirklich guten Bücher zum Thema CS und Mathematik ausgewählt und möchte Ihre Meinung zu folgenden Themen einholen:

  • Vollständigkeit der behandelten Themen (bitte empfehlen Sie alles, was ich verpasst habe)
  • Überlappung von Material bedeckt / Overkill-Bereich (empfehlen Sie Bücher, die aus der Liste entfernt werden sollten)
  • Reihenfolge, um die Bücher zu studieren (Ich listete in der Reihenfolge auf, in der ich denke, dass sie studiert werden sollten)

Die Liste fühlt sich übermäßig lang an, daher würde ich mich über Empfehlungen zum Entfernen einiger Bücher freuen, ohne den Verlust des für CS erforderlichen Kernwissens.

Die Bücher sind also:

  1. Mathematician's Delight von WW Sawyer
  2. Wie man es beweist: Ein strukturierter Ansatz von Daniel J. Velleman
  3. Wie man es löst: Ein neuer Aspekt der mathematischen Methode von G. Polya
  4. Eine Einführung in die funktionale Programmierung durch Lambda-Rechnung von Greg Michaelson
  5. Grundlagen der Informatik von Al Aho und Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
  6. Konkrete Mathematik: Eine Stiftung für Informatik von Graham, Knuth und Patashnik
  7. Einführung in die Berechnungstheorie von Michael Sipser
  8. Einführung in die Automatentheorie, -sprachen und -berechnung von John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman
  9. Computerkomplexität: Eine konzeptuelle Perspektive von Oded Goldreich
  10. Computerkomplexität: Ein moderner Ansatz von Sanjeev Arora, Boaz Barak
  11. Ein Kurs in Kombinatorik von JH van Lint, RM Wilson
  12. Berechenbarkeit: Eine Einführung in die rekursive Funktionstheorie von Nigel Cutland
  13. Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit von MR Garey, DS Johnson
  14. Theorie rekursiver Funktionen und effektive Berechenbarkeit von Hartley Rogers
  15. Ungleichungen von GH Hardy, JE Littlewood, G. Polya
  16. Mathematische Logik: Ein Kurs mit Übungen (Teil I): Aussagenrechnung, Buchalgebren, Prädikatenrechnung von René Cori, Daniel Lascar
  17. Mathematische Logik: Ein Kurs mit Übungen (Teil II): Rekursionstheorie, Godels Theoreme, Mengenlehre, Modelltheorie von René Cori, Daniel Lascar
CSLover
quelle
Bitte beziehen Sie sich auf diese Frage cstheory.stackexchange.com/questions/3253/…
Bartosz Przybylski
Beginnen Sie mit einem bekannten Algorithmusbuch, wenn Sie noch keine Erfahrung mit diesem Thema haben.
AJed
@Bartek: Danke, aber dies war eine der Fragen, die ich mir zuvor angesehen habe, um die Liste zu erstellen. Meine Frage ist eher, wie man das ganze großartige Material da draußen praktisch liest. Die Zeit ist immer eine Einschränkung, deshalb möchte ich wissen, welche Bücher ich "nicht" lesen sollte, um Wiederholungen usw. zu vermeiden
CSLover
@AJed: Schlagen Sie vor, mit Buch Nr. 5 auf der Liste zu beginnen, anstatt mit einigen der Mathebücher Nr. 1-4? Ich glaube, # 5 gibt eine sanfte Einführung in Algorithmen und Datenstrukturen.
CSLover
Zu viel hier. Ich wähle einfach einen aus und mache mir dann Gedanken darüber, was als nächstes kommt, wenn du dort ankommst. Ich kann Sipser empfehlen, für Anfänger zu beginnen, die solide Kenntnisse in den Grundlagen von CS haben möchten.
Usul

Antworten:

10

Ihre Liste ist äußerst problematisch.

Zunächst überspringe ich die Bücher 6,11,12,14,15,16,17: Die Bücher 6, 11 und 15 sind allgemeine Mathematik, die nicht wirklich benötigt wird, es sei denn, Sie werden theoretischer Forscher. Die Bücher 12 und 14 behandeln die Rekursionstheorie, die keine Informatik ist (obwohl sie sich mit der Berechenbarkeit befasst!). Die Bücher 16 und 17 behandeln fortgeschrittene Themen in der Logik, während Sie nur sehr grundlegende Logik kennen müssen.

Aus den Büchern 1,2,3 würde ich nur eines auswählen, um eine allgemeine Einführung in Mathematik und Beweise zu geben.

Die Bücher 5, 7, 8, 9, 10, 13 behandeln verschiedene Themen: Automatentheorie, Algorithmen und Komplexitätstheorie. Lassen Sie mich vorschlagen, dass Sie Sipser (Buch 7) für die Automatentheorie und Komplexitätstheorie und Einführung in Algorithmen von Cormen, Leiserson, Rivest und Stein ("CLRS") für Algorithmen folgen.

Buch 4 befasst sich mit funktionaler Programmierung. Während meine Informatikausbildung noch nie Kurse zu diesem Thema angeboten hat, zählt die funktionale Programmierung für viele Forscher der theoretischen Informatik zu den wesentlichen Grundlagen.

Zusammenfassend: Was Sie dabei bleiben, ist

  • Eines der Bücher 1-3 (oder ein vergleichbarer "Einführungstext")
  • CLRS
  • Buch 4 (Funktionsprogrammierung)
  • Buch 7 (Automatentheorie und Komplexitätstheorie)
Yuval Filmus
quelle
Vielen Dank für eine so gründliche Antwort. Ich wusste, dass die Liste zu umfangreich war, aber wenn man alle Arten von Buchempfehlungen für Informatiker liest, hat man eine lange Liste. Ihre Empfehlung ist sehr praktisch, und danach bin ich. Großer Dank!!
CSLover
1
Ich bin mit dem Rat nicht einverstanden, dass "Mathe nicht benötigt wird". Wählen Sie einen Aspekt der Informatik und ich werde Ihnen zeigen, wie Mathematik benötigt wird. Je mehr Mathematik Sie lernen, desto besser geht es Ihnen. Andererseits ist es fast unmöglich, echte Mathematik allein zu lernen, ohne zur Schule zu gehen. Sie sollten sich also besser auf die Informatik konzentrieren, das ist leichter zu lernen.
Andrej Bauer
5

Sie können auch einige der zahlreichen Online-Kurse in Betracht ziehen. Zum Beispiel bieten Stanford und MIT (kostenlose) Online-Kurse in Informatik an, und ich denke, es gibt auch viele andere.

Was Bücher angeht, halte ich die meisten Empfehlungen von Yuval für angebracht, mit der Ausnahme, dass CLRS eine großartige Referenz ist, aber ein wenig überwältigend als Einführungsbuch, um sich nur hinzusetzen und durchzulesen. Für einen ersten Durchgang im Algorithmus-Teil empfehle ich möglicherweise Algorithmen von Dasgupta et al. . Der vorherige Link führt zum kostenlosen Online-Vorabdruck, ist aber auch als Taschenbuch recht günstig erhältlich.

Joe
quelle
In Ordnung. Ich freue mich über Ihre Antwort. Vielen Dank.
CSLover
2

Die Referenzen, die Sie vorschlagen, würden einen "sehr" theoretischen Informatiker ausmachen. Aber ich finde ehrlich gesagt keinen Vorteil, wenn ich all diese Bücher lese, wenn Sie keinen CS-Abschluss haben. Das hängt natürlich alles davon ab, was Sie brauchen.

Ich finde einige Bücher wie Buch 14, 15, 16, 17 sind nicht für Informatiker gedacht. Buch 3 ist ausführlich. Es ist nur allgemein für jeden Studenten. Daher gehe ich davon aus, dass Buch 1 und 2 gleich sind.

Für mich - in der gleichen Situation wie ursprünglich kein Informatiker (sondern ein Elektro- / Computeringenieur) - schlage ich zwei anfängliche Richtungen vor:

  • Entwurf und Analyse von Algorithmen (viele Leute schlagen die CLRS-Einführung in Algorithmen vor . Es ist eine großartige Referenz, aber ich bin wirklich kein Fan davon, und anfangs war es schwieriger, sie zu verstehen und manchmal sehr ausführlich. Ich schlage allerdings vor, dass Sie Befolgen Sie das Inhaltsverzeichnis, und überprüfen Sie von dort aus die Online-Kurse auf klarere Verweise.

--- Stellen Sie sicher, dass Sie eine Programmiersprache beherrschen, um die von Ihnen erlernten Algorithmen und Datenstrukturen IMPLEMENTIEREN zu können. Daher empfehle ich die Reihe der Algorithmen von Sedgewick (erstaunlich!).

--- ADDED: Ich schlage auch dieses Buch vor: Combinatorial Algorithms: Generation, Enumeration und Search by D. Kreher. Das ist ein sehr schönes Buch. Gibt Ihnen eine andere Perspektive für viele Probleme in Algorithmen.

  • Kombinatorik (insbesondere Graphentheorie), ein Kurs in Kombinatorik von JH van Lint, RM Wilson , ist gut. Es gibt viele andere Referenzen. In der Regel reicht jedes bekannte Kombinatorik-Buch aus - alles andere erhalten Sie aus zusätzlichen Referenzen aus dem Internet. Ich persönlich mochte: Peter J. Cameron Combinatorics und Bondy and Murty Graph Theory.

  • eine Wette der Wahrscheinlichkeit (immer notwendig). Es fällt auf, dass in vielen Bereichen der Wissenschaft die Wahrscheinlichkeit nicht angewendet wird. Aber glauben Sie mir, alles, was Sie wissen müssen, sind die Grundlagen.

Dann: Viele Forscher, die sich theoretische Informatiker nennen, konzentrieren sich so sehr auf die Theorie der Berechnung (Automobile und andere). Hierfür gibt es einige gute Bücher (siehe Beitrag von Yuvul Filmus).

Aho und Ullman sind gut (eigentlich sind alle Bücher von Ullman gut). Machen Sie sich mit dem Compiler-Design vertraut (siehe http://infolab.stanford.edu/~ullman/ullman-books.html ).

Danach kommt es darauf an, was Sie tun möchten. Verschiedene Richtungen, die Sie einschlagen können: 1) Datenbanken, 2) Mustererkennung und Data Mining, 3) verteilte Algorithmen, 4) Grundlagen von Programmiersprachen, 4) Randomisierungsalgorithmen und viele andere. [von denen jeder einen anderen Beitrag benötigt] aber versuchen Sie, eine Idee über alle zu haben!

* Die allgemeine Idee: Wenn Sie neu bei CS sind, sollten Sie sich mit möglichst vielen CS-Subdomains vertraut machen. Wenn Sie sich auf "Theorie" beschränken, verlieren Sie viel an CS-Kreativität! * (meine Meinung)

AJed
quelle
Für mich funktionale Programmierung. Verwenden Sie kein altes Buch wie das, das Sie zitiert haben. Derzeit werden in der Industrie funktionale Sprachen benötigt. Im Internet gibt es einige Tutorials zu Sprachen wie Scheme, Haskel und Erlang. Werde nicht sehr theoretisch, das ist mein Rat.
AJed
Alles gute Kommentare. Mein Ziel ist es, ein vollständiges Selbststudienprogramm zu entwerfen. Diese Frage befasst sich nur mit einem Teil des Programms, dessen Organisation ich für die größte Herausforderung hielt. Weitere Bereiche sind: Datenstrukturen und Algorithmen, Computerarchitektur, Betriebssysteme, Vernetzung, Sicherheit und Kryptographie, Parallelität, Formale Methoden, Künstliche Intelligenz, Grafik und Simulation, Datenbanken, Programmiersprachen, Compiler, Softwareentwicklung und schließlich Unix-Philosophie und -Verwaltung. Die meisten davon sind meiner Meinung nach für CS von grundlegender Bedeutung, würden aber eine separate Frage
rechtfertigen
Ihr bester Trick ist eine solide Grundlage für die Entwicklung und Analyse von Algorithmen. - Jedes andere Feld ist ein Teilfeld des Entwurfs und der Analyse von Algorithmen.
AJed
Würden Sie freundlich sein und klarstellen, welche Sedgewick-Algorithmen Sie empfohlen haben? Er hat einen namens "Algorithmen", aber es ist keine Serie. Er hat auch "Algorithmen in C ++" (oder in anderen Sprachen), das sind 2 Bücher, von denen ich glaube, dass sie insgesamt 5 Teile enthalten.
CSLover
Das, was ich benutzte, waren die C ++. Ich habe sie jedoch als Referenz verwendet. Dies ist seine Website cs.princeton.edu/~rs
AJed