Welche Bücher sollte jeder lesen?

229

[ 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:

MS Dousti
quelle
Da ich die Frage nicht beantworten kann, mache ich das hier. Diskrete Mathematik - TTC: Diskrete Mathematik von Arthur T. Benjamin. Es ist ein Vortragspaket zu verschiedenen Themen von Mengenlehre bis Graphik und Wahrscheinlichkeit.
Pithikos
Es kann interessant sein, diese Liste bemerkenswerter Bücher mit der Liste der einführenden Bücher aus dem Internet zu vergleichen. Gibt es eine Liste der kanonischen einführenden Lehrbücher, die die wichtigsten Bereiche der Informatik abdecken? Frage zu reddit / compsci. Es gibt einige Überschneidungen, aber zum Glück sind die Unterschiede ausreichend signifikant.
Thomas Klimpel

Antworten:

91

Rechenkomplexität:

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

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.

Mohammad Al-Turkistany
quelle
2
Abgesehen von denjenigen, die daran interessiert sind, wie diese Bücher miteinander verglichen werden, kann ich auch diese Buchbesprechung von Arora / Barak und Goldreich anbieten , die ich kürzlich für die SIGACT-Kolumne zur Buchbesprechung geschrieben habe.
Daniel Apon
1
Siehe auch Lance Fortnows Liste seiner Lieblingsbücher zu Computational Complexity bei Amazon: amzn.com/l/22R1UX0Y9YRT2
Alessandro Cosentino
5
Der einzige Kommentar zu Sipsers Buch ist, dass er manchmal nicht standardisierte Namen verwendet, wenn er sich mit der Berechnungstheorie befasst. Beispielsweise verwendet er "erkennbar" anstelle von "halbentscheidbar". Aber ich denke, da das Lehrbuch so weit verbreitet ist, könnte es mittlerweile zum Standard werden.
Dai Le
4
Eigentlich ist das im Allgemeinen ein ausgezeichneter Kommentar, @Dai Le. Ich kann mir ähnliche Unterschiede zwischen Goldreich und Arora / Barak vorstellen. Zum Beispiel verwendet Goldreich den Namen und Arora / Barak den Namen , obwohl beide über dasselbe Konzept sprechen. F N PPCFNP
Daniel Apon
1
Ich fand Sipser weitaus nützlicher als Papadimitriou, um Komplexitätstheorie zu lehren, ymmv.
Jeff Burdges
49

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.

Sadeq Dousti
quelle
6
Nach 30 Jahren immer noch der beste Einstieg in die Komplexitätstheorie.
Emil
1
Nach Jahrzehnten ist dieses Buch immer noch die vollständigste Liste von NP-vollständigen Problemen an einem Ort, anscheinend fast eine Enzyklopädie, und viele CS-Forscher scheinen diese Sichtweise zu teilen
vzn
1
empfehlen, dies in die FAQ aufzunehmen, um eine allgemeine Frage zu stellen: "Ist mein Problem X NP vollständig?" mit der
antwort
47

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)

Nikita Zhiltsov
quelle
7
"Eine Einführung in die Analyse von Algorithmen" von Sedgewick und Flajolet ist großartig.
Jay
Daniel Spielman verwendet das Buch von Kleinberg und Tardos in seinem Kurs "Design and Analysis of Algorithms". Ich habe es genommen und das Buch wirklich geliebt. Ich fand es viel zugänglicher als CLRS.
Alex Reinking
41

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.

Dave Clarke
quelle
7
Für eine mathematischere Perspektive auf die Typentheorie ist "Lectures on the Curry-Howard Isomorphism" von Sorensen und Urzyczyn ein guter Anfang, der einen guten Überblick über typisierte Lambda-Kalküle bis hin zur Konstruktionsrechnung und darüber hinaus bietet.
Dominic Mulligan
4
Ich würde John Mitchells Grundlagen für Programmiersprachen zu diesem Thema vorschlagen. Wie im vorherigen Kommentar ist es mathematisch gereifter.
Artem Pelenitsyn
2
Upvote für TAPL. Benjamin Pierce ist einer der Autoren eines neuen Buches "Software Foundation", das Coq verwendet.
Kunjan Kshetri
40

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:

Sadeq Dousti
quelle
1
Wenn ich einen Link zu etwas hinzufügen darf, das ich selbst gesammelt habe (aus vielen verschiedenen Quellen, einschließlich einiger der oben genannten), ist hier ein Spickzettel mit häufigen Ungleichungen: lkozma.net/inequalities_cheat_sheet
László Kozma
1
Hardy, Littlewood, Polya, "Ungleichheiten", ein Juwel aus den 1930er Jahren (?)
Kodlu
38

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.

Fakrudeen
quelle
4
TAOCP ist immer noch relevant und Vol. 4A wurde gerade veröffentlicht.
Dbasnett
33

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 CCVCVCC

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 VPVPV

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 0PV0

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.

Dai Le
quelle
32

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 .

Hsien-Chih Chang 張顯 張顯
quelle
3
Dieses Buch wurde in einem anderen Thema vorgeschlagen (ich denke von Suresh). Ich fand es ausgezeichnet. Vielen Dank an Aaron, der es hier erwähnt hat.
MS Dousti
29

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:

Sadeq Dousti
quelle
2
Seit ihrer Einführung im Jahr 1993 wurden Zufallsorakel in der Literatur in großem Umfang verwendet. speziell in Signaturschemata. Ich kenne kein Buch, das diesen Bereich angemessen abdeckt. Vorschläge sind willkommen.
MS Dousti
1
Ein Buch über zufällige Orakel wäre eine große Hilfe. Ich arbeite nicht in Krypto, aber ich habe Katz / Lindell von vorne nach hinten gelesen. Der Übergang vom Lehrbuch zur Kryptoliteratur war aus diesem Grund schwierig. @Sadeq, aus Neugier: Hat eines der Bücher, die Sie gelesen haben, eine gute Berichterstattung über das Zurückspulen?
Daniel Apon
1
@Daniel: Martin Gagnés These "Eine Studie des Zufalls-Orakel-Modells" (UC Davis, 2008) ist eine relativ gute Referenz zu zufälligen Orakeln (obwohl sie noch lange nicht vollständig ist). Zu der Frage "Zurückspulen": Ich kenne kein Buch darüber, aber ich glaube, ich habe es vollständig verstanden. Könnten Sie bitte erläutern, welcher Teil für Sie problematisch erscheint? Sie können es sogar zu einem anderen Thema fragen.
MS Dousti
@Sadeq, ich neige dazu, keine unabhängige Frage zu stellen, da es sich nur um "Hilfe, was wird zurückgespult?" Handelt. :) Der problematische Teil ist, dass das Zurückspulen nicht in dem Lehrbuch enthalten war, das in dem von mir belegten Kryptokurs (z. B. Katz / Lindell) verwendet wurde, sodass ich nie eine Einführung in das Konzept gesehen habe. Ich bin mir bewusst, dass es regelmäßig in der Kryptoliteratur auftaucht, aber als jemand, der nicht aktiv an der Kryptoforschung beteiligt ist, bezweifle ich, dass ich genug Artikel lese, um ein solides Verständnis für das Zurückspulen zu erlangen, wenn ich es nur genug antreffe. Vielleicht könnte ich eine Frage zu den Ursprüngen des Zurückspulens stellen ...
Daniel Apon
3
@Daniel: Die Einführung meines Buches mit gleichzeitigem Null-Wissen erklärt das Zurückspulen und die Schwierigkeiten, die es im Zusammenhang mit der Protokollzusammenstellung verursacht. Weitere Quellen sind: (1) Oded Goldreich, Hugo Krawczyk: Über die Zusammensetzung wissensfreier Beweissysteme. SIAM J. Comput. 25 (1): 169-192 (1996) und (2) Cynthia Dwork, Moni Naor, Amit Sahai: Gleichzeitiges Nullwissen. J. ACM 51 (6): 851 & ndash; 898 (2004).
Alon Rosen
25

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.
Sadeq Dousti
quelle
21

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.

Sadeq Dousti
quelle
21

Kombinatorik

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

Fortgeschrittenere Texte.

Sadeq Dousti
quelle
21

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.

Lamine
quelle
20

Programmüberprüfung

Chan Li
quelle
1
Einige der Bücher (Manna und Apt et al.) Sind ziemlich alt (Manna stammt aus dem Jahr 1977 und Apt et al. Aus dem Jahr 1991). Auf dem Gebiet der logikbasierten Programmverifizierung wurden im letzten Jahrzehnt große Fortschritte erzielt. Leider ist kein aktueller Text verfügbar.
Martin Berger
@MartinBerger Gibt es Hinweise darauf, woher dieser wichtige Fortschritt stammen könnte, wenn er nicht in neueren Lehrbüchern enthalten ist?
Mitch
@Mitch Ich fürchte, das wurde noch nicht in Lehrbüchern geschrieben. Vielleicht sehen Sie sich in der Literatur interaktive Tools wie Isabelle / HOL und Coq an. Schauen Sie sich auch die neuesten automatischen Überprüfungstools wie Facebooks "Infer" und die dahinter stehende Theorie an.
Martin Berger
Huth & Ryan ist sehr anfängerfreundlich. Für jemanden, der mit der strengen Mathematik in CS nicht sehr vertraut ist, ist es ein guter Anfang. Es ist das erste Buch, das ich über die formale Seite von CS gelesen habe und das mich seitdem begeistert hat! Es ist auch das erste Lehrbuch, in dem ich tatsächlich alle Lesungen beendet habe.
RexYuan
19

Informationstheorie

Informationstheorie, Inferenz und Lernalgorithmen von David MacKay

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

Sadeq Dousti
quelle
Der Titel lautet "Welche Bücher sollten alle lesen?", Daher sollte die Empfehlung selektiv sein. Jeder kann eine große Liste von Büchern über "Informationstheorie" bei Amazon / library finden, aber wenn Sie nur 2-3 Möglichkeiten haben, welche werden es sein? Sie sollten nur Bücher oder Artikel empfehlen, die Sie sehr sorgfältig gelesen und auf Ihre absoluten Favoriten eingegrenzt haben!
Dai Le
1
@Dai Le: Du hast recht. Ich denke, die Liste sollte eingegrenzt werden. (Ich bin persönlich für das Aufblähen der Liste verantwortlich!) Dies ist jedoch ein Community-Wiki- Beitrag. Ich habe eine lange Liste hinzugefügt, die die Kandidaten vorschlägt. Bitte kürzen Sie die Liste, um nur die am besten geeigneten Bücher anzuzeigen.
MS Dousti
1
@Sadeq: Ich fürchte, es kommt selten vor, dass eine Person die Liste einer anderen Person kürzt. Solange die Post noch in der aktuellen Form ist, ist sie im Hinblick auf den Zweck der Post völlig wertlos.
Dai Le
@Dai: Du hast recht. Aber da ich kein Experte für "Infotheorie" bin, kann ich die Liste nicht selbst kürzen. Ich kann: 1) die Liste, die ich insgesamt hinzugefügt habe, löschen (die ursprüngliche Liste verlassen) oder 2) einen Hinweis in den Text einfügen, um die Aufmerksamkeit eines Experten auf sich zu ziehen. Was schlagen Sie vor?
MS Dousti
@Sadeq: Ich arbeite auch nicht an der Informationstheorie, sonst würde ich helfen, die Liste zu kürzen. Ich weiß, dass das Buch "Thomas M. Cover, Joy A. Thomas. Elemente der Informationstheorie" von vielen empfohlen wird, einschließlich Lance Fortnow. Aber ich bin nicht sicher, ob jeder es lesen soll oder nicht. Ich denke, wir sollten das Originalplakat respektieren, da das Buch sein Lieblingsbuch sein könnte. Das Löschen der gesamten Liste ist daher eine gute Option. Ich entschuldige mich wirklich dafür, dass ich zu unkompliziert bin. Können Sie die Leute auch bitten, zu erklären, warum sie ihre Bücher vorschlagen?
Dai Le
19

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

Massimo Cafaro
quelle
19

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:

  • 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:

Sadeq Dousti
quelle
17

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.

Marcos Villagra
quelle
16
Hsien-Chih Chang 張顯 張顯
quelle
Eine andere Methode, die sich hervorragend für die Boolesche Fourier-Analyse eignet (wie der Titel schon sagt) und sowohl die Grundlagen als auch fortgeschrittenere Themen und (viele) Anwendungen abdeckt, ist die Analyse von Booleschen Funktionen von Ryan O'Donnell (2014). Es ist gerade online frei verfügbar hier auch.
Clement C.
16

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.

Hsien-Chih Chang 張顯 張顯
quelle
16

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.

Jay
quelle
14

Logik / Beweisschreiben:

  1. Wie man es beweist: Ein strukturierter Ansatz von Daniel J. Velleman
Sazzad Bin Kamal
quelle
3
Wie ist das im Vergleich zu "How to solution it" von G. Polya? Ich denke, ich habe den Rat gelesen, dass Polya das Original ist und viel besser, aber ich bin nicht sicher und kann es nicht in den Interwebs wiederfinden;)
DaveBall aka user750378
2
Polyas "How to Solve It" (HTSI) befasst sich mit einem anderen Thema als Vellemans Buch. Polya ist eine Art Grübeln darüber, wie man Lösungen für schwierige Probleme findet, während Velleman ein Lehrbuch darüber ist, wie man Lösungen unter Verwendung der Konventionen und der Sprache der Mathematik formalisiert. HTSI hat Informationen über Beweise, aber es ist in einer Art "Glossar" ohne Struktur dargestellt, während Velleman Ihnen ein systematisches Curriculum mit Übungen vorlegt. Beides ist lesenswert, aber eins ersetzt das andere nicht.
Nate CK
13

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:

Sadeq Dousti
quelle
Was halten Sie von Rosens Buch oder den Dover-Nachdrucken?
Mark C
@ Mark: Sie sind auch gut. Warum nicht den Beitrag bearbeiten und auch diese Bücher hinzufügen?
MS Dousti
11

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

dpufrj
quelle
1
Es gibt auch die Graphentheorie von Claude Berge, einem der Begründer der Graphentheorie. Und Graphen und Algorithmen von Michel Minoux und Michel Gondran.
Lamine