Liste der Intro-TCS-Bücher für diejenigen, die nicht viel über TCS wissen [geschlossen]

Wenn Sie Bücher für jemanden empfehlen müssen, der auf der Einführungsebene mehr über TCS erfahren möchte, wie z. B. Automatentheorie, Algorithmus, Komplexitätstheorie usw., welche Bücher würden Sie für diejenigen empfehlen, die interessiert sind und mehr darüber erfahren möchten TCS, aber keine Exposition gegenüber?

Wenn Sie eine allgemeine Einführung wünschen, ohne auf die technischen Details einzugehen, empfehle ich David Harels Algorithmics: The Spirit of Computing . Danach ist dies meine Favoritenliste:

• Michael Sipsers Einführung in die Berechnungstheorie : Die beste Einführung in die Automatentheorie, Berechenbarkeit und Komplexität.
• Algorithmen von S. Dasgupta, CH Papadimitriou und UV Vazirani: die intuitivste Einführung in Algorithmen mit einem stärkeren Fokus auf Intuition als technische Beweise.
• Jon Bentleys Programmierperlen : Dies ist kein Lehrbuch über Algorithmen, aber es zeigt auf wunderbare Weise, wie man Algorithmus-Entwurfstechniken verwendet, um echte Probleme zu lösen, die echte Programmierer irritierten. :-) Dies könnte ein guter Anfang sein, wenn Sie Vorkenntnisse in der Programmierung haben.

• Einführung in Algorithmen von Cormen, Leiserson, Rivest, Stein ist eine beliebte Wahl, Titel spricht für sich.
• Compiler: Prinzipien, Techniken und Werkzeuge von Aho, Ulman und Sethi ist ein gutes Buch über Compiler und enthält auch Einführungsmaterial zur Automatentheorie.
• Prinzipien der Modellprüfung ist ein umfangreiches Buch, das als Einführung in die Modellprüfung verwendet werden kann

Für die Mathematik, die für die Algorithmusanalyse benötigt wird, empfehle ich das einzige GKP:

Konkrete Mathematik von Graham, Knuth, Patashnik
Eine umfassende und qualitativ hochwertige Behandlung praktisch aller Mathematik, die Sie für (grundlegende) Algorithmen benötigen. Es ist eine unterhaltsame Lektüre und enthält eine Fülle von Übungen (und Lösungen).

Algorithmen 4. Ausgabe R. Sedgewick

Eine Einführung in die Analyse von Algorithmen P. Flajolet, R. Sedgewick

Einführung in Automatentheorie, Sprachen und Berechnung JE Hopcroft, JD Ullman, (R. Motwani)
Die erste Ausgabe von 1979 enthält theoretischere Ergebnisse, die in der zweiten Ausgabe von 2001 fehlen. Ich habe mir den dritten Ed noch nicht angesehen.

Einführung in die formale Sprachtheorie MA Harrison
Es ist von 1978, aber ich würde es immer noch gerne auf der Liste sehen.

Logicomix: Eine epische Suche nach der Wahrheit A. Doxiadis, CH Papadimitriou
Weil es total großartig ist!

Wieder 1979
Garey und Johnsons Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit

Ich würde TAoCP gerne auf der Liste haben, aber ich befürchte, dass Don Knuths akribischer Ansatz nichts ist, was als „einleitend“ angesehen werden könnte. Traurig...

Wenn Sie auf dem Gebiet der TCS völlig neu sind, ist Sipsers Einführung in die Theorie der Berechnung definitiv das beste Buch, um Ihnen den Einstieg zu erleichtern . Ich habe andere einführende Bücher gelesen, und keines davon kommt meiner Meinung nach Sipsers Art, die Angelegenheit zu erörtern, nahe.

Andere, spezifischere, gute theoretische Bücher sind:

• Benjamin Pierces Typen und Programmiersprachen . Dies ist theoretische Informatik und Logik aus einer anderen Perspektive.
• Edelsteine ​​der Theoretischen Informatik von U. Schöning und R. Pruim.

Einige gute Bücher über den Theorie-B-Teil von TCS:

• Logik in CS : Logik in der Informatik: Modellierung und Argumentation über Systeme Von Michael Huth und Mark Ryan.
  Breite Abdeckung verschiedener Verwendungen von Logik in der Informatik. Etwa im 3. Studienjahr.

• Der Lambda-Kalkül : Lambda-Kalkül und Kombinatoren. Eine Einführung von J. Roger Hindley und Jonathan P. Seldin.
  Führt den Lambda-Kalkül ein, der ein wesentlicher Bestandteil der Grundlagen von Programmiersprachen ist. Etwa im 3. Studienjahr.

• Führen , um Domain - Theorie : Einführung in den Gittern und Order (2. Aufl.) Von Davey, BA und Priestley, HA Cambridge University Press. (2002).
  Behandelt ein sehr nützliches Thema, insbesondere wenn Sie mit Semantik arbeiten möchten. Es ist ein bisschen mathematischer als die anderen Themen, aber die ersten Kapitel befinden sich sicherlich auf einem fortgeschrittenen Bachelor-Niveau.

• Semantik : Semantik mit Anwendungen: Ein Appetizer von Hanne Riis Nielson und Flemming Nielson.
  Eine wirklich schöne Einführung in die Semantik der Programmiersprache. Anstatt sich eingehend mit einem bestimmten Formalismus zu befassen, bietet er eine breite Darstellung und enthält Anwendungen, die in anderen Büchern zur Semantik im Allgemeinen nicht berücksichtigt werden. Könnte möglicherweise für Studenten im 2. Jahr nützlich sein.

Dies ist eine aggregierte Antwort, die Bücher aus Antworten mit einer Punktzahl von mindestens fünf enthält. Bitte besprechen Sie den Inhalt im Chat .

Algorithmen & Datenstrukturen

• Einführung in Algorithmen von Cormen, Leiserson, Rivest, Stein (3. Ausgabe 2009)
  Eine umfassende Behandlung grundlegender Algorithmen und Datenstrukturen und ihrer Analyse, ohne zu tief zu graben.
• Algorithmen von Dasgupta, Papadimitriou, Vazirani (2006)
  Die intuitivste Einführung in Algorithmen mit einem stärkeren Fokus auf Intuition als technische Beweise.

Berechenbarkeit und Komplexität

• Einführung in die Theorie der Berechnung von Sipser (2. Auflage 2005)
  Die beste Einführung in die Automatentheorie, Berechenbarkeit und Komplexität.

Formale Sprachen & Automaten

• Compiler: Prinzipien, Techniken und Werkzeuge von Aho, Ulman und Sethi (2. Ausgabe 2006)
  Das Standardbuch über Compiler; sehr umfassend. Berührt auch die Automatentheorie.

Angewandte Theorie

• Prinzipien der Modellprüfung von Baier, Katoen (2008)
  Massives Buch, das als umfassende Einführung in die Modellprüfung verwendet werden kann.
• Programming Pearls von Jon Bentley (2. Aufl. 1999)
  Kein Lehrbuch über Algorithmen, zeigt aber auf wunderbare Weise, wie man Algorithmus-Design-Techniken verwendet, um echte Probleme zu lösen. Könnte ein guter Anfang sein, wenn Sie Vorkenntnisse in der Programmierung haben.