Mathe für TCS-Hauptfach

10

Ich suche ein Hauptfach in Theoretischer Informatik; Insbesondere interessiere ich mich für Komplexitätstheorie und probabilistische Automatentheorie. Welche fortgeschrittenen Kurse in Mathematik (wie zum Beispiel Galois-Theorie oder Harmonische Analyse) halten Sie nach meinem Abschluss in einem Jahr für nützlich, um die nächsten zwei Semester zu übernehmen? Warum?

complexity-theory automata education ADR
quelle
2
Siehe verwandte Frage.
Nicholas Mancuso
1
Überprüfen Sie auch die Kursanforderungen an Ihrer Schule sowie ähnliche Fragen zur Theoretischen Informatik (z. B. dies oder das ). Ich bin versucht, dieses hier als Duplikat zu schließen; es ist auch ziemlich lokalisiert.
Raphael
6
Nimm die ganze Mathematik!
JeffE
2
@ JeffE Nehmen Sie ... die ganze Mathematik?
MrGomez
2
Die ganze Mathematik in A Theorist's Toolkit .
Chao Xu

Antworten:

2

(Eine Zusammenfassung der Kommentare zu den Fragen)

In TCS kann so ziemlich jeder Bereich der Mathematik wichtig sein. Sie sollten also das Beste tun, um Ihren mathematischen Hintergrund zu stärken. Jedes Werkzeug, das Sie lernen, ist ein Gewinn und kann in einigen TCS- (Unter-) Bereichen eingesetzt werden.


Diese Frage wurde auch in anderen SE beantwortet, und sehr informative Details finden Sie in:

  1. Welche Art von mathematischem Hintergrund wird für die Komplexitätstheorie benötigt?
  2. Beispiele für „nicht verwandte“ Mathematik, die eine grundlegende Rolle in TCS spielt?
  3. Welche Mathematikkurse sollte ich belegen, um mich auf einen CS-Master oder eine Promotion vorzubereiten?
Ran G.
quelle
1
Stimme dieser pauschalen Aussage überhaupt nicht zu. Tatsächlich ist die überwiegende Mehrheit der Bereiche der Mathematik für die theoretische Informatik nicht hilfreich. Sagen wir Funktionsanalyse, Mengenlehre (z. B. Forcen), Topologie, algebraische Geometrie (nein, GCT zählt nicht), Differentialgleichungen, und die Liste könnte weiter und weiter gehen. Das wichtigste mathematische Fach ist die Wahrscheinlichkeitstheorie (auch das hängt von der Art des TCS ab, das Sie machen). Abgesehen davon einige sehr grundlegende Kenntnisse in einigen Bereichen, z. B. Gruppentheorie.
Yuval Filmus
@ Yuval, ich denke, dass dies ein bisschen kurzsichtig ist. Wer hat gedacht, dass Fourier-Transformationen für TCS so nützlich sein können (vor dem Ruhm, den sie bei der Verwendung für PCP usw. erlangt haben?) Wer hat gedacht, dass SDP-Löser für TSP so relevant sind (wie kürzlich in [arxiv: 1111.0837] gezeigt, wenn ich ihre Arbeit richtig verstehe? ) .. Ich denke, viele andere Methoden können für TCS und sicherlich für CS im Allgemeinen verwendet werden .. Richtig, nicht alle Methoden sind gleich wichtig, und ich hatte gehofft, dass dieser Thread zu einer Liste von Methoden / Anwendungen wird, wo die meisten wichtige Methoden würden die höchsten Stimmen erhalten.
Ran G.
Fourier-Transformationen sind sehr elementare Konzepte. Sie müssen den Fejer-Kernel in TCS nicht verstehen. SDPs stammen aus der Operations Research (oder aus der konvexen Optimierung, wenn Sie dies bevorzugen). Es stimmt , dass einige Dinge , könnte nützlich sein. Zum Beispiel fand ich meinen Hintergrund in C sehr nützlich, und Virginia Williams fand ihren Hintergrund in Maple sehr nützlich. In Bezug auf Ihre Karriere sind Schreiben und öffentliches Sprechen ebenfalls sehr nützlich. All dies ist wahrscheinlich nützlicher als ein Kurs über kombinatorische Mengenlehre. Warum nicht den Leuten sagen, dass sie diese Fächer anstelle von zufälligen Mathematikkursen studieren sollen?
Yuval Filmus
1
@ YuvalFilmus Ich verstehe nicht: Das MMO-Invarianzprinzip ist eine strikte Verallgemeinerung von Berry-Esseen. Ich stimme auch Ihrem größeren Punkt nicht zu. Viele TCS verwenden möglicherweise die Wahrscheinlichkeit bis zu einer Chernoff-Grenze. Aber das JL-Lemma, die Konzentration des Maßes in etwa ARV, Dvoretzkys Theorem für die komprimierte Abtastung, Grothendiecks Ungleichheit bei der Annäherung an die Schnittnorm sind nur einige sehr erfolgreiche Beispiele dafür, dass FA bei TCS nützlich ist. Ja, der Hauptfokus der beiden Bereiche ist unterschiedlich - aber die Schnittpunkte gehen über "die ersten 10 Seiten" hinaus und machen das Erlernen der Mathematik lohnenswert.
Sasho Nikolov
1
Während unsere Anwendungen es uns normalerweise ermöglichen, an (Varianten von) Ergebnissen festzuhalten, die beschrieben und oft auf elementare Weise bewiesen werden können, bietet der größere Kontext Intuition (CLT ist beispielsweise eine großartige Heuristik). und da es schwer zu sagen ist, was nützlich ist, bis Sie es verwenden müssen, würde es mir nichts ausmachen, einige Mathematikkurse zusätzlich zu Lesegruppen in TCS zu belegen, die Ihnen helfen, zu lernen, was bereits als nützlich bekannt ist. Ich habe kürzlich festgestellt, dass ein FA-Ergebnis (das in TCS afaik fast nie verwendet wird) der Schlüssel zu einem Problem ist, an dem ich gearbeitet habe
Sasho Nikolov,