[ 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
quelle
Antworten:
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:
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:
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 .
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.
quelle
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.
quelle
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)
quelle
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.
quelle
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.
quelle
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:
quelle
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.
quelle
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:
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:
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 CC 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 VPV PV
Für exzellente Umfragen zur Beweiskomplexität empfehle ich die folgenden zwei Bücher:
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 0P V0
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.
quelle
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 .
quelle
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:
Spezifische Themen:
quelle
Funktionale Programmierung
quelle
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:
und
Ein aktuelles Buch ist Der Entwurf von Approximationsalgorithmen von Williamson und Shmoys.
quelle
Kombinatorik
Einführungsbücher. Jedes der folgenden Bücher kann als hervorragende Einführung in das Thema dienen:
Fortgeschrittenere Texte.
quelle
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.
quelle
Programmüberprüfung
quelle
Informationstheorie
Informationstheorie, Inferenz und Lernalgorithmen von David MacKay
Andere berühmte Lehrbücher zur Informationstheorie finden Sie auf Wikipedia .
quelle
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
quelle
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:
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:
quelle
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 .
quelle
Kommunikationskomplexität:
Kommunikationskomplexität von Eyal Kushilevitz und Noam Nisan.
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.
quelle
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.
quelle
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 ,
Computergestützte Analyse
Ein interessantes Feld, das sich auch mit Berechnungen in realen Funktionen befasst. Auch als "computable analysis" oder "computable calculus" bekannt.
quelle
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.
quelle
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
quelle
Logik / Beweisschreiben:
quelle
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:
quelle
Hypergraphen
Es gibt nicht viele Bücher, die ausschließlich Hypergraphen gewidmet sind. Ein solches Buch ist
Berge C. Hypergraphen: Kombinatorik endlicher Mengen .
quelle
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
quelle
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
quelle
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:
quelle