Welche Bücher sollte jeder lesen?

[ Timeline ]

Bei dieser Frage geht es darum, welche Artikel jeder lesen und welche Videos jeder ansehen sollte . Es werden bemerkenswerte Bücher in verschiedenen Bereichen der theoretischen Informatik verlangt.

Die Bücher können mathematisch orientiert sein, aber für einen Informatiker ist es vielleicht großartig. Beispiele:

• Wahrscheinlichkeit
• Ungleichungen
• Logik
• Graphentheorie
• Kombinatorik
• Entwurf und Analyse von Algorithmen
• Berechnungstheorie / Computational Complexity Theory

Bitte widmen Sie jede Antwort Büchern des gleichen Faches (zB Büchern zur Kombinatorik).

Hinweis: Der Titel kann irreführend sein. Hier ist eine Klarstellung: Lassen Sie X und Y zwei Felder in der Informatik sein. Es gibt Bücher, die jeder hat

• in Feld X sollte lauten.
• in Feld Y sollte lauten.
• In beiden Feldern sollte gelesen werden.

Diese Frage sucht alle 3 Fälle. Mit anderen Worten, es ist NICHT spezifisch für den letzteren Fall.

Bearbeiten: Wie von Dai Le vorgeschlagen , markieren Sie bitte die Gründe, aus denen Sie das Buch mögen.

Verwandte Themen:

• Referenzen für TCS-Proof-Techniken
• Bücher zur Automatentheorie zum Selbststudium
• Bücher für die Wahrscheinlichkeit
• Beliebtestes Mathematikbuch
• Anfängerleitfaden zur Derandomisierung
• Verweise auf Schaltungsuntergrenzen
• Übersichtsartikel zur Theorie der rekursiven Funktionen
• Bücher zur Programmiersprachensemantik
• Was sind die neuesten TCS-Bücher, deren Entwürfe online verfügbar sind?
• Bücher über Wahrscheinlichkeit

Rechenkomplexität:

Wenn Sie nach neueren Lehrbüchern für Komplexität suchen. Die folgenden zwei müssen haben.

• Computerkomplexität: Ein moderner Ansatz von Sanjeev Arora und Boaz Barak ( Lehrbuchhomepage )

• Computerkomplexität: Eine konzeptuelle Perspektive von Oded Goldreich ( Lehrbuchhomepage )

Der größte Teil des Inhalts zwischen diesen beiden Büchern ist vergleichbar. Es gibt jedoch einige wesentliche Unterschiede: Goldreich widmet der Erforschung der konzeptuellen und philosophischen Grundlagen der Komplexitätstheorie mehr Raum, während Arora / Barak eine breitere Auswahl von Themen abdeckt, einschließlich konkreter Modelle der Komplexität, der Quantenberechnung und der Schaltungsuntergrenzen, die größtenteils fehlen vom ersteren.

Eine andere Möglichkeit, ein älteres, aber zeitloses Lehrbuch in seiner Komplexität, ist:

• Computational Complexity von Christos Papadimitriou

Papadimitrious Buch zeichnet sich durch Kapitel aus, die sich mit Logik erster Ordnung befassen , sowie durch die Klassen SNP, MaxSNP und APX (die theoretischen Grundlagen der Approximationshärte), die in den moderneren Texten fehlen.$_0$

Ein weiterer (vergleichsweise) alter, aber durchaus bemerkenswerter Klassiker ist:

• Einführung in die Berechnungstheorie von Michael Sipser

Dies ist eines der wenigen / ersten Lehrbücher, in denen "Proof Idea:" explizit zwischen "Theorem:" und "Proof:" steht, und eines der am besten geschriebenen mathematischen Lehrbücher zu jedem Thema. Auf der anderen Seite ist dies nur eine Einführung in die Komplexität, da nur ein 50-seitiges Kapitel "fortgeschrittenen Themen" gewidmet ist (einschließlich Approximation, probabilistischen Algorithmen, IP = PSPACE und Krypto). Als erstes Buch über Komplexität oder als Beispiel für wirklich exzellentes Schreiben ist dieses Buch großartig .

• Die Natur der Berechnung von Cristopher Moore und Stephan Mertens

Scott Aaronson schreibt, dass dieses Buch "den Spaß eines populären Buches mit dem intellektuellen Gewicht eines Lehrbuchs" hat. Es erzählt Geschichten und gibt viele unterhaltsame Beispiele und Referenzen (Game of Life und viele andere Beispiele für Turing-Komplettmaschinen). Es geht nicht zu tief in die Komplexitätstheorie ein, hat aber eine große Breite. Besonders hervorzuheben sind die Verbindungen zur statistischen Physik.

NP-Vollständigkeit:

Nun, ich denke, Garey und Johnsons Computer und Intraktierbarkeit: Ein Leitfaden zur Theorie der NP-Vollständigkeit befindet sich unter den Top-Büchern in dieser Liste.

Entwurf und Analyse von Algorithmen:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen.

R. Motwani, P. Raghavan. Randomisierte Algorithmen.

Ich habe dieses von Ryan Williams vorgeschlagene Buch bei MathOverflow: Algorithm Design von Kleinberg & Tardos gefunden .

Ein weiteres ausgezeichnetes Buch ist Introduction to Algorithms: Ein kreativer Ansatz von Udi Manber . Dieses Buch ist kein Katalog von Algorithmen; Vielmehr soll dem Leser die Intuition vermittelt werden, "mathematische Strukturen in abstrakten Problemen zu erkennen". (zitiert aus einer Rezension)

Allgemeine Mathematik für Informatik:

• Konkrete Mathematik: Eine Stiftung für Informatik von Graham, Knuth und Patashnik.

• Der Princeton Companion to Mathematics von Gowers et al.

• Beweise aus THE BOOK von Aigner und Ziegler.

Typsysteme und Programmiersprachen Semantik:

Die Typen und Programmiersprachen von Benjamin Pierce und das Folgeband Fortgeschrittene Themen in Typen und Programmiersprachen . Sie bieten einen soliden und dennoch nachvollziehbaren Überblick über die Rolle der Typentheorie beim Entwurf von Programmiersprachen und verwenden die operationale Semantik, um die Semantik von Programmiersprachen auszudrücken.

Ungleichungen:

Ein weiteres wertvolles Buch für jeden in der Informatik, der jemals eine beliebige Menge (also alle!) Binden möchte, ist: Die Cauchy-Schwarz-Meisterklasse: Eine Einführung in die Kunst der mathematischen Ungleichungen von Michael Steele.

Ein enzyklopädisches Buch zum Thema ist A Dictionary of Inequalities . Dies ist zwar kein Buch zum durchgehenden Lesen, aber es ist gut, es zu Ihrer Verfügung zu haben. Siehe auch die Beilage des Buches.

Darüber hinaus weist Wikipedia eine hervorragende Liste von Ungleichungen auf .

Zu bestimmten Themen können Sie konsultieren:

• Probabilistische Ungleichungen
• Matrix-Ungleichungen
• Geometrische Ungleichungen
• Das Buch "A = B" von Petkovsek, Wilf und Zeilberger

Interessant. Niemand erwähnte Bände der Kunst der Computerprogrammierung von Donald E. Knuth . Eine sehr detaillierte Behandlung von Themen mit sehr guten Übungen.

Ich habe in diesem Buch Edelsteine ​​wie "Resorvoir Sampling" gefunden, um nur ein Beispiel zu nennen.

Wie Sylvain Peyronnet bereits erwähnte, ist Logik ein wichtiger Bestandteil der theoretischen Informatik. Es reicht jedoch nicht aus, Logik aus Lehrbüchern zu lernen, die auf reine Mathematiker zugeschnitten sind. Mit anderen Worten, es ist auch wichtig, Logik aus einer "Informatik" -Perspektive zu lernen.

Finite-Modell-Theorie

Wir wollen Techniken lernen, die mit endlichen Strukturen umgehen. Es ist bekannt, dass viele traditionelle Werkzeuge aus der Modelltheorie, z. B. Kompaktheit und Löwenheim-Skolem-Theorem, nicht auf endliche Modelle anwendbar sind . Dies führt uns zum Studium der endlichen Modelltheorie . Für diesen Bereich empfehle ich die folgenden ausgezeichneten Bücher:

• Leonid Libkin, Elemente der endlichen Modelltheorie . (Lehrbuch)
• Grädel et al., Finite-Modell-Theorie und ihre Anwendungen . (Umfrage Artikel und Anwendungen)

Ein Teilbereich der endlichen Modelltheorie ist die deskriptive Komplexität , bei der wir Komplexitätsklassen nach der Art der Logik charakterisieren möchten, die zur Definition der Sprachen erforderlich ist. Die endgültige Referenz für die beschreibende Komplexität lautet:

• Neil Immerman, Beschreibende Komplexität .

Komplexität beweisen

Ein weiteres wichtiges Gebiet der Logik in der Informatik ist Proof Complexity , eine Untersuchung der Drei-Wege-Beziehung zwischen Komplexitätsklassen, schwachen logischen Systemen und Aussagenbeweissystemen. Die folgenden zwei verwandten Aspekte werden betrachtet: (i) die Komplexität von Beweisen von Aussagenformeln und (ii) das Studium von schwachen Theorien der Arithmetik, die als gebundene Arithmetik bezeichnet werden .

Aspekt (i) hat mit der folgenden Frage zu tun: "Gibt es ein Satzbeweissystem, in dem jede Tautologie einen Beweis eines Größenpolynoms in der Größe der Tautologie hat?"

Aspekt (ii) untersucht logische Systeme, die eingeschränktes Denken auf der Grundlage von Konzepten aus der Komplexität von Berechnungen verwenden. Mit anderen Worten, wir ordnen jeder Komplexitätsklasse eine logische Theorie , wobei die nachweislich gesamten Funktionen in genau die Funktionen in der Komplexitätsklasse . Eine aktuelle Entwicklung ist ein neues Forschungsprogramm namens "Bounded Reverse Mathematic", das von Stephen Cook und Phuong Nguyen vorgeschlagen wurde. Ziel ist es, Theoreme (von Interesse für die Informatik) auf der Grundlage der (minimalen) rechnerischen Komplexität von Konzepten zu klassifizieren, die erforderlich sind, um sie zu beweisen .V C V C $C$$VC$$VC$$C$

Aspekte (i) und (ii) sind eng mit dem Begriff der bezogenen Aussagen Übersetzung vorgeschlagen in Cook 1975 Papier , die die Gleichung Theorie eingeführt für polytime Funktionen und zeigte , wie Sätze in kann in übersetzt werden Familien von Tautologien, die im erweiterten Frege-Beweissystem polynomielle Längenbeweise haben.P $\mathsf{PV}$$\mathsf{PV}$

Für exzellente Umfragen zur Beweiskomplexität empfehle ich die folgenden zwei Bücher:

• Stephen Cook und Phuong Nguyen, logische Grundlagen der Beweiskomplexität . (Entwurf hier verfügbar gemacht )
• Jan Krajíček, Gebundene Arithmetik, Aussagenlogik und Komplexitätstheorie .

Das Buch von Cook und Nguyen ist im Wesentlichen in sich abgeschlossen und der gesamte logische Hintergrund ist in den Kapiteln 2 und 3 enthalten. Kapitel 9 ist besonders interessant, da die Autoren eine äußerst einfache Methode eingeführt haben, um Ihre eigene Theorie für alle Komplexitätsklassen innerhalb von . Bei dieser Methode müssen wir nur ein zusätzliches Axiom zu einer hinzufügen , wobei das Axiom lediglich die Existenz einer Lösung für ein vollständiges Problem der Komplexitätsklasse angibt. Ziemlich erstaunlich!V $\mathsf{P}$$V_0$

Das Buch von Krajíček ist etwas herausfordernder, da er davon ausgeht, dass die Leser bereits mit mathematischer Logik und Modelltheorie vertraut sind (oder bereit sind, den notwendigen Hintergrund zu erlernen). Aber Sie werden viel lernen, wenn Sie dieses Buch lesen und verstehen.

Randomisierte Algorithmen:

Wahrscheinlichkeit und Rechnen: Randomisierte Algorithmen und probabilistische Analysen von Michael Mitzenmacher und Eli Upfal.

Tolles Buch zum Erklären der Grundlagen randomisierter Algorithmen. Die Beispiele und Beweise werden sehr anschaulich erklärt und sind leicht zu befolgen. Auch die Übungen machen sehr viel Spaß.

(beantwortet von Marcos Villagra)

Analyse randomisierter Algorithmen:

Wer mit Algorithmen arbeitet, sollte über eine Messkonzentration für die Analyse randomisierter Algorithmen verfügen , die hier auch als PDF-Datei heruntergeladen werden kann .

Kryptographie:

Das zweibändige Buch Foundations of Cryptography von Oded Goldreich ( Band 1: Basic Tools und Band 2: Basic Applications ) ist ein ausgezeichnetes Buch zu diesem Thema. (Frühe Entwürfe sind auf der Homepage des Autors erhältlich .) Eine gekürzte Version dieses Buches ist ebenfalls erhältlich.

Ein weiteres ausgezeichnetes Buch ist Introduction to Modern Cryptography: Principles and Protocols von Katz & Lindell.

Für diejenigen, die sich für mathematische Hintergründe der Kryptographie interessieren, bietet eine Einführung in die mathematische Kryptographie von Hoffstein et al. ist die natürliche Wahl.

Andere ausgezeichnete Bücher sind:

• Handbuch für Angewandte Kryptographie von Menezes et al. (Kapitel sind online verfügbar ).
• Kryptographie: Theorie und Praxis von Stinson.

Spezifische Themen:

• Bücher zur erweiterten Erstellung von Sicherheitsprotokollen:
  • Zusammensetzung sicherer Mehrparteienprotokolle: Eine umfassende Studie von Lindell.
  • Concurrent Zero-Knowledge von Rosen.
• Formale Beweise in Sicherheitsprotokollen
  • Formale Korrektheit von Sicherheitsprotokollen von Bella.
• [Mathematik der Kryptographie mit öffentlichen Schlüsseln] ( http://www.amazon.com/Mathematics-Public-Cryptography-Steven-Galbraith/dp/1107013925 ) von Galbraith

Funktionale Programmierung

• Rein funktionale Datenstrukturen von Chris Okasaki . Die meisten Bücher über Datenstrukturen setzen eine imperative Sprache wie C oder C ++ voraus. Datenstrukturen für diese Sprachen lassen sich jedoch nicht immer gut in funktionale Sprachen übersetzen. Dieses Buch ist eine der besten Darstellungen zur Implementierung von Datenstrukturen und Algorithmen in einer funktionalen Sprache.
• Funktionale Programmierung: Praxis und Theorie von Bruce J. Maclennan . Trotz seines Namens ist dieses Buch eher theorieorientiert als praxisorientiert. Diejenigen, die dieses Buch lesen, haben eine viel bessere Sicht auf das Thema als diejenigen, die es durch Ad-hoc-Programmierung lernen.
• Pearls of Functional Algorithm Design von Richard Bird . Eine brandneue Ausstellung zu diesem Thema, die den Ansatz der Problemlösung verfolgt und die Schönheit des Feldes zeigt, indem sie attraktive Ideen für den Entwurf funktionaler Algorithmen präsentiert.
• Zertifizierte Programmierung mit abhängigen Typen von Adam Chlipala . Es ist eine der besten Ressourcen für das Erlernen von Coq und befasst sich insbesondere mit der Automatisierung der Programmzertifizierung und des Beweises von Theoremen unter Verwendung logischer / regelbasierter Systeme. Beispiele sind umfangreich und leicht zu folgen.

Approximationsalgorithmen

Das Buch Approximation Algorithms von Vazirani ist das beste Buch zu diesem Thema. Ein weiteres Buch ist Approximationsalgorithmen für NP-harte Probleme von Hochbaum.

Hier sind Vergleiche von zwei Rezensenten:

Ich habe Dorit Hochbaums Buch über Approximationsalgorithmen für NP-Hard-Probleme als Leitfaden für meine Arbeit verwendet. Hochbaums Buch ist zweifellos großartig. Das Umfrageformat beeinträchtigte jedoch einen reibungslosen Ablauf, um die besten Personen auf diesem Gebiet zusammenzubringen. Vaziranis Buch korrigiert dies, indem es von Anfang bis Ende so glatt und elegant ist. Ausgezeichnete Problemsätze, ausgezeichnete Hinweise für die meisten Probleme, und am Ende des Buches befindet sich ein Abschnitt, der sich mit offenen Problemen befasst. Dies ist eine wirklich coole Funktion.

und

Ich habe nach Büchern gesucht, die sich mit der Lösung von NP-vollständigen und NP-harten Problemen befassen. Es gibt ein anderes Buch von Hochbaum und das habe ich auch. Leider ist dieses Buch eher ein forschungsorientiertes Buch, da es von mehreren Forschern geschrieben wurde. Es ist, als würde man mehrere Forschungsarbeiten in zwei Hardcovers lesen. Dies bedeutet, dass man eine Art Zwischenerfahrung mit Approximationsalgorithmen haben muss.

Ein aktuelles Buch ist Der Entwurf von Approximationsalgorithmen von Williamson und Shmoys.

Kombinatorik

Einführungsbücher. Jedes der folgenden Bücher kann als hervorragende Einführung in das Thema dienen:

• Handbuch der diskreten und kombinatorischen Mathematik von Rosen.
• Diskrete und kombinatorische Mathematik: Eine angewandte Einführung von Grimaldi. Siehe auch das Lösungshandbuch .
• Ein Spaziergang durch die Kombinatorik und Einführung in die enumerative Kombinatorik und Einführung in die enumerative Kombinatorik von Bona. Das erste Buch ist sowohl umfangreicher als auch klassischer. Das zweite Buch hat erhebliche Überschneidungen mit dem ersten, aber der Schwerpunkt liegt viel mehr auf modernen Zählmethoden.
• Ein Kurs in Kombinatorik von van Lint & Wilson.
• Kombinatorik: Themen, Techniken, Algorithmen von Cameron. (Dieses Buch enthält viele schöne Übungen.)
• Kombinatorische Probleme und Übungen von László Lovász (beantwortet von @Sazzad)

Fortgeschrittenere Texte.

• Enumerative Combinatorics, Volume 1 & Volume 2 von Stanley. Es ist einfach ein Meisterwerk der enumerativen Kombinatorik. sehr herausfordernd, sehr tief.
• Kombinatorische Algorithmen: Generierung, Aufzählung und Suche nach Kreher & Stinson. Eher geeignet für Informatikanwendungen der Kombinatorik.
• Additive Combinatorics von Terence Tao und Van H. Vu. Eine sehr nützliche Referenz, wenn Sie mit einem kombinatorischen Problem in Bezug auf die Zahlentheorie konfrontiert sind.

Kombinatorik

Ich möchte Analytic Combinatorics von Philippe Flajolet und Robert Sedgewick zitieren . Es bietet einen starken mathematischen Hintergrund für die Aufzählung und Analyse von Algorithmen. Ich möchte auch Philippe Flajolet meinen Tribut zollen, der vor zwei Tagen starb und ein großartiger Mathematiker und Informatiker war.

Programmüberprüfung

• Mathematische Berechnungstheorie von Zohar Manna
• Prinzipien der Modellprüfung von Christel Baier und Joost-Pieter Katoen
• Modellprüfung von Edmund M. Clarke Jr., Orna Grumberg und Doron A. Peled
• Überprüfung von sequentiellen und gleichzeitigen Programmen durch Krzysztof R. Apt, Frank S. de Boer und Ernst-Rüdiger Olderog
• Logik in der Informatik: Modellierung und Argumentation über Systeme von M. Huth und M. Ryan

Informationstheorie

Informationstheorie, Inferenz und Lernalgorithmen von David MacKay

Andere berühmte Lehrbücher zur Informationstheorie finden Sie auf Wikipedia .

Verteilte Algorithmen

Verteilte Algorithmen von Nancy Lynch Dies ist ein klassischer Text, der von einem Pionier des verteilten Rechnens geschrieben wurde.

Einführung in verteilte Algorithmen von Gerard Tel Sehr gute Einführung, auch für Grundstudiengänge geeignet; konzentrierte sich auf das Modell der Nachrichtenübermittlung

Distributed Computing: Grundlagen, Simulationen und fortgeschrittene Themen von Hagit Attiya und Jennifer Welch Enthält fortgeschrittene Materialien, die für PhD-Kurse geeignet sind. Es werden sowohl Modelle für das Weiterleiten von Nachrichten als auch für den gemeinsamen Speicher erörtert

Entwurf und Analyse verteilter Algorithmen von Nicola Santoro Ein relativ neues Buch, das sowohl für Studienanfänger als auch für Doktoranden geeignet ist. Die Materialien werden mit einem Schwerpunkt auf dem Protokolldesign vorgestellt

Quanten-Computing

• Quantenberechnung und Quanteninformation von Nielsen und Chuang ist ein großartiges Nachschlagewerk , ideal für diejenigen, die auf diesem Gebiet forschen möchten. Für Anfänger ist es jedoch schwierig, daraus zu lernen, und es ist definitiv nicht für Selbstlerner. Da das Buch keine funktionierenden Beispiele enthält, schlage ich folgendes Buch vor:

  • Probleme und Lösungen im Bereich Quantum Computing & Quantum Information von Steeb & Hardy . Dieses Buch enthält viele Beispiele, ist aber nicht für den absoluten Anfänger gedacht. Für den Anfang wird folgendes Buch empfohlen:

    • Annäherung an Quantum Computing von Marinescu & Marinescu . Während elementar und leicht zu erlernen, finden es einige Leute "mit Fehlern gefüllt". In dieser Hinsicht sind die Errata des Buches nützlich.

• Quantum Computing Since Democritus von Scott Aaronson . Eine Tour-de-Force, die weit über das Quantencomputing hinausgeht und Beziehungen zur Physik, Philosophie usw. aufweist.

Zwei weitere ausgezeichnete Einführungsbücher zu diesem Thema sind:

• Quantum Computing für Informatiker von Yanofsky & Mannucci .
• Eine Einführung in das Quantencomputing von Kaye, Laflamme und Mosca .

Optimierung

Ich mochte Paul Nahins When Least is Best.

Im Wesentlichen eine nette Geschichte der Optimierung durch Probleme und Persönlichkeiten. Auf den Seiten 32 bis 36 finden Sie in einer der Kolumnen von Bill Gasarch eine schöne Rezension .

$e^{i\pi} = -1$

Kommunikationskomplexität:

Dies ist ein klassisches und sehr gut geschriebenes Buch. Obwohl mittlerweile ein bisschen alt, immer noch das beste Einführungsbuch auf dem Gebiet. Außerdem machen die Übungen sehr viel Spaß und werden genau nach der Erläuterung der Konzepte gegeben, damit Sie das korrigieren können, was Sie gerade gelernt haben.

Der Teil der randomisierten Kommunikationskomplexität sollte durch Teile des ersten Buches ergänzt werden.

Kommunikationskomplexität und paralleles Rechnen von Juraj Hromkovič.

Sehr vollständig, wenn auch manchmal etwas schwer zu lesen. Die intuitiven Erklärungen sind sehr klar und sehr schöne Übungen. Im zweiten Teil werden die Verbindungen zum Parallel Computing vorgestellt.

• Die Bücher von Matousek & Chazelle über Diskrepanz sind ausgezeichnet.

  Tatsächlich sind fast alle Bücher von Matousek zum Teil lesenswert.

• Douglas-West-Bücher zur Graphentheorie ( [1] und [2] ) sind gut.

• Alon & Spencer ist auch hervorragend.
• Pach & Agarwal ist gut für diskrete Geometrie, ebenso wie Sharir & Agarwal, wenn Sie DS-Sequenzen mögen .
• Messing, Moser und Pach Buch über offene Probleme in der diskreten Geometrie ist auch sehr gut.
• Das Vanderbei- Buch auf LP ist sehr gut.
• Schrijvers Bücher ( [1] und [2] ) sind erstaunlich.

Computeralgebra

Wie Shiva in dieser Antwort sagte , sind Literaturen auf diesem Gebiet überall verstreut, ohne gemeinsame Terminologien. Man kann nützliche Referenzen finden, indem man nach "symbolischer Berechnung", "algebraischer Komplexitätstheorie", "Computeralgebra" oder "Computeralgebra" sucht. Wie in den Antworten auf diese Frage vorgeschlagen ,

• Moderne Computeralgebra von Joachim von zur Gathen und Jürgen Gerhard.
• Algebraische Komplexitätstheorie von Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi und T. Lickteig.
• Algorithmische Algebra von Bhubaneswar Mishra.
• Eine computergestützte Einführung in Zahlentheorie und Algebra von Victor Shoup.

Computergestützte Analyse

Ein interessantes Feld, das sich auch mit Berechnungen in realen Funktionen befasst. Auch als "computable analysis" oder "computable calculus" bekannt.

• Berechenbare Analyse von Oliver Aberth.
• Rechenanalyse: Eine Einführung von Klaus Weihrauch.

Kombinatorik

Die Erstellungsfunktionalität von Herbert S. Wilf ist eine hervorragende Einführung in die Theorie der Erstellungsfunktionen, die auf eine reibungslose Art und Weise geschrieben und voller Übungen ist. Wenn er all seine Bücher so schreibt, kann ich es kaum erwarten, mit einem anderen zu beginnen.

Enumerative Combinatorics von Richard Stanley ist eine großartige Referenz (für Fortgeschrittene).

Kombinatorik: Themen, Techniken, Algorithmen von Peter Cameron und Einladung zur diskreten Mathematik von Matousek und Nesetril sind gute Einführungen in die Kombinatorik.

Applied Combinatorics von Roberts and Tesman ist eine enzyklopädische Referenz zur angewandten Kombinatorik.

Logik:

Dies ist ein Wortlaut meiner Antwort auf diese Frage .

Grundkenntnisse der mathematischen Logik sind meiner Meinung nach von Vorteil. Sie können sich die beiden Bücher von Cori und Lascar ansehen.

Mathematische Logik: Ein Kurs mit Übungen Teil I

Mathematische Logik: Ein Kurs mit Übungen Teil II

Logik / Beweisschreiben:

1. Wie man es beweist: Ein strukturierter Ansatz von Daniel J. Velleman

Zahlentheorie

Ich fand mehrere Bücher, die häufig in vielen Zeitungen zitiert wurden. Sie sind hervorragend in diesem Bereich, aber einige von ihnen sind ziemlich alt. Hier ist eine Liste dessen, woran ich mich erinnere:

• Eine Einführung in die Zahlentheorie von Hardy et al. Hardy ist ein bekannter britischer Mathematiker. Er war der Mentor des indischen Mathematikers Ramanujan . Sein Beitrag zur Zahlentheorie ist erstaunlich .
• Eine Einführung in die Zahlentheorie von Niven, Zuckerman, Montgomery. Eine weitere klassische Einführung in das Feld.
• Gelöste und ungelöste Probleme in der Zahlentheorie von Shanks. Dies ist das Buch für diejenigen, die noch zu beweisende Vermutungen auf diesem Gebiet suchen.
• Riemanns Zeta-Funktion von Edwards. Ein wichtiger Teil der modernen Zahlentheorie sowie mehrere probabilistische Algorithmen für zahlentheoretische Aufgaben beruhen auf der (erweiterten) Riemannschen Hypothese, wie sie in diesem Buch beschrieben wird.

Hypergraphen

Es gibt nicht viele Bücher, die ausschließlich Hypergraphen gewidmet sind. Ein solches Buch ist

Berge C. Hypergraphen: Kombinatorik endlicher Mengen .

Beweis Theorie

Troelstra und Schwichtenbergs Buch Basic Proof Theory ist der De-facto-Text zu diesem Thema.

Girard, Taylor & LaFonts Proofs and Types ist ein kürzeres Buch zu diesem Thema. Eine Version davon kann unter http://www.paultaylor.eu/stable/Proofs%2BTypes.html heruntergeladen werden

Graphentheorie

Zur Einführung in die Graphentheorie: Einführung in die Graphentheorie von West

Weitere Informationen zur Graphentheorie: Graphentheorie von Bondy und Murty

Das umfassende Buch, das sowohl Neuentwicklungen als auch alte klassische Ergebnisse der Graphentheorie enthält:

Graphentheorie: Reinhard Diestel .

Für Diagramme auf Flächen mit kombinatorischem Ansatz:

Diagramme auf Oberflächen

Und für Digraphen:

Digraphen: Theorie, Algorithmen und Anwendungen

VLSI-Design

Ich bin nicht in Hardware. Da die FAQ jedoch VLSI als Teilbereich von TCS enthält, habe ich einen Experten nach bekannten Büchern im VLSI-Design gefragt. Hier sind sie:

• Digitale integrierte Schaltungen
• CMOS VLSI-Design: Eine Schaltkreis- und Systemperspektive
• Modernes VLSI-Design: IP-basiertes Design