Wo kann man mehr über theoretische Informatik erfahren?

15

Ich bin ein Doktorand in Mathematik, und theoretische Informatik ist ein Bereich, von dem ich nie verstanden habe, worum es geht, weil ich keine gute Lektüre zu diesem Thema finden konnte. Ich möchte wissen, worum es in dieser Domain eigentlich geht, um welche Themen es sich handelt, welche Voraussetzungen erforderlich sind, um sich darauf einzulassen usw. Im Moment möchte ich nur wissen:

Was ist ein gutes Einführungsbuch in die theoretische Informatik?

Vorausgesetzt, es gibt so etwas. Wenn nicht, wo soll ein Mathematiker mit Grundkenntnissen der Informatik (dh er kennt die Grundlagen einer oder zweier Programmiersprachen) anfangen, wenn er verstehen will, worum es in der theoretischen Informatik geht? Was empfehlen Sie?

Vielen Dank!


quelle
1
Gute Frage. Ich bin wirklich ratlos. Theoretisches CS ist so umfassend und vielfältig, dass ich bezweifle, dass jemand versucht hat, alles an einem einzigen Ort zu erfassen. Es gibt Introbücher wie Sipsers "Theory of Computation" oder "Algorithms" von Dasgupta, Papadimitriou und Vazirani. Aber das sind wie Grundvoraussetzungen für Studienanfänger und geben keine Vorstellung davon, worum es beim derzeitigen TCS "eigentlich geht" ...
usul
6
Die Frage ist viel zu weit gefasst. Man könnte dann gleichermaßen fragen: "Wo kann man mehr darüber erfahren, was Mathematik ist?". Man sollte sich daher die mathematisch nahen Gebiete des TCS ansehen, wie Komplexitätstheorie, Kryptographie, Approximation. Die Komplexität der Schaltung ist nur ein Teil der Extremal Combinatorics. Sipsers Buch ist in der Tat großartig: Es ist eine mathematische Sichtweise bei TCS (ein kleiner Teil davon, es ist unnötig zu sagen); Sipser selbst ist eigentlich Mathematiker.
Stasys
2
Avi Wigdersons kommender Text ist eine großartige Ressource: math.ias.edu/avi/book
András Salamon

Antworten:

29

Erstens bedeutet "theoretische Informatik" für verschiedene Menschen verschiedene Dinge. Ich denke, für die meisten Benutzer auf dieser Site ist eine historische Karikatur (die einige moderne soziologische Tendenzen widerspiegelt), dass es "Theorie A" und "Theorie B" gibt (ohne implizite Ordnungsbeziehung zwischen ihnen): Theorie A besteht aus der Theorie von Algorithmen, Komplexitätstheorie, Kryptographie und ähnliches. Theorie B besteht aus Dingen wie der Theorie der Programmiersprachen, der Theorie der Automaten usw. Abhängig von Ihrem Geschmack in der Mathematik können Sie eines dem anderen vorziehen (oder beides gleichermaßen mögen). "Theorie A" ist mir vertrauter, daher möchte ich hier einige Hinweise geben:

  • Beginnen Sie mit Sipsers Buch. Auf diese Weise erhalten Sie eine gute Einführung in Automaten, Turing-Maschinen, Berechenbarkeit, Kolmogorov-Komplexität, P vs NP und einige andere Komplexitätsklassen. Es ist sehr gut geschrieben (meiner Meinung nach ist es eines der am besten geschriebenen Fachbücher aller Zeiten )

  • Für Algorithmen habe ich eine leichte Vorliebe für Kleinberg-Tardos, aber es gibt viele gute Einführungsbücher. Vielleicht interessieren Sie sich besonders für Computergeometrie, für die es eine Reihe großartiger Bücher gibt.

  • Da Sie ein Mathematik-Doktorand sind, fehlt in diesen Büchern vor allem die algebraische Komplexitätstheorie, die häufig in engem Zusammenhang mit Algebra (sowohl kommutativ als auch nicht kommutativ), Darstellungstheorie, Gruppentheorie und algebraischer Geometrie steht . Es gibt hier einen kanonischen Text, nämlich Burgisser-Clausen-Shokrollahi. Es ist etwas enzyklopädisch, so ist vielleicht nicht die beste Einführung sein, aber ich bin nicht sicher , es ist ein wirklich Einführungsbuch in diesem Bereich. Sie können sich auch die Umfragen von Chen-Kayal-Wigderson und Shiplka-Yehudayoff ansehen.

Danach schlage ich vor, je nach Ihrem mathematischen Geschmack in weiterführenden Büchern zu bestimmten Themen zu stöbern:

  • Arora-Barak ist eine modernere Komplexitätstheorie (setzt fort, wo Sipsers Buch sozusagen endet), die Ihnen einen Einblick in die beteiligten Techniken gibt (hauptsächlich eine Mischung aus Kombinatorik und Algebra).

  • Das Buch von Jukna über die Komplexität von Booleschen Funktionen ist ähnlich, aber ausführlicher, insbesondere für die Komplexität von Booleschen Schaltkreisen (sehr kombinatorisch im Geschmack).

  • Geometrische Komplexitätstheorie. Siehe hier oder Landsbergs Einführung für Geometer .

  • O'Donnells Buch Analysis of Boolean Functions ist stärker fourieranalytisch ausgerichtet.

  • Kryptographie. Die fortgeschritteneren mathematischen Aspekte sind hier typischerweise die Zahlentheorie und die algebraische Geometrie. Während diese rein mathematischen Aspekte nur einen kleinen Teil der Kryptographie ausmachen, sind sie ein wichtiger Aspekt, den Sie vielleicht interessant finden. Da ich nicht in meiner Nähe bin, bin ich mir nicht sicher, was für ein gutes Startbuch hier ist.

  • Codierungstheorie. Hier reicht die mathematische Theorie von der Kugelpackung (siehe das Buch von Conway und Sloane) bis zur algebraischen Geometrie (zB das Buch von Stichtenoth). Auch hier nicht meine Gegend, daher bin ich mir nicht sicher, ob dies die besten Ausgangspunkte sind, aber wenn Sie sie durchblättern, erhalten Sie schnell den Geschmack und entscheiden, ob Sie tiefer eintauchen möchten.

Und dann gibt es viele andere mathematische Themen, die nur in der Forschungsliteratur auftauchen, wie Verbindungen mit Schäumen, Graphentheorie, C * -Algebren (lassen Sie mich nur auf die Kadison-Singer-Vermutung verweisen ), Invariantentheorie, Darstellungstheorie, Quadraturen, und weiter und weiter. Siehe auch diese verwandten Fragen

Joshua Grochow
quelle
2
Ein gutes Einstiegsbuch für die Kryptographie ist Introduction to Modern Cryptography von Katz-Lindell: cs.umd.edu/~jkatz/imc.html - Eine alternative (ältere) Option ist Foundations of Cryptography von Goldreich: wisdom.weizmann.ac.il /~oded/foc-book.html
Daniel Apon
4

Die Natur der Berechnung von Cristopher Moore und Stephan Mertens.

John Donn
quelle
Ich liebe dieses Buch - ich habe es in meiner Antwort meistens wegen seiner Länge nicht empfohlen, obwohl man natürlich immer die zu lesenden Kapitel auswählen und auswählen kann.
Joshua Grochow