Warum zur theoretischen Informatik / Forschung gehen?

36

Ich beginne gerade an der Universität [Informatik] und dort haben wir viele Möglichkeiten, mit der Forschung zu beginnen. Bevor ich diese Website gefunden habe, hatte ich nicht die Absicht, diesen Weg zu gehen [ich wollte mit AI arbeiten, wahrscheinlich mit Spieleentwicklern], aber jetzt kann [oder muss ich] eine Wahl treffen.

Können Sie mich überzeugen, mich dieser "Welt" anzuschließen? Welche "Segmente" kann ich verfolgen? Gibt es etwas zu den Themen, an denen ein Informatiker oder Forscher arbeitet?

JulioC
quelle
18
Wir fühlen uns geehrt, dass Sie die Website bereits zum Nachdenken über Theorie inspiriert hat! Und wenn Sie wissen möchten, woran ein theoretischer Informatiker arbeitet, dann sind Sie hier richtig. Lesen Sie einfach weiter und Sie werden es herausfinden!
Ryan Williams
6
Dies sollte Community-Wiki sein.
Dave Clarke
Ich bin erst heute dazu gekommen und hatte die gleiche Frage ... Ich habe mein Ingenieurstudium in Elektrotechnik absolviert, aber während meines Studiums begann ich, mich für CS zu interessieren ... Ich hatte nie eine formale Einführung in die Theorie, aber jetzt bin ich froh, dass ich diese Seite gefunden habe ... Und @ Júlio Souza, danke, dass du diese Frage gestellt hast. Ich werde dies ab heute überwachen :)
Alan Turing
@supercooldave hat es in Community-Wiki geändert.
JulioC
Epilog: JulioC wurde Softwareentwickler.
Domotorp

Antworten:

32

Ich kann meine Gründe als Student, der sich im kommenden Winter für TCS-Studiengänge bewirbt, angeben (so wenig Zeit bleibt mir noch!).

  • Da ist die Schönheit. Dies kann ich nicht erklären (und ich habe gesehen, wie andere Mathematiker dies nicht erklärten). Es ist wie "gelb". Wenn Sie es nicht gesehen haben, bin ich mir nicht sicher, ob ich Ihnen mitteilen kann, was es ist. Aber seit du dich für Theorie interessierst, nehme ich an, dass du es tatsächlich erlebst.
  • Es gibt Universalität. Universalität jenseits der kirchlichen These . TCS untersucht im Kern Phänomene auf hoher und niedriger Ebene in der Information - es ist die "Physik" der Information. Und da Information qualitativ atomar ist , hat die Informationstheorie einiges über die Physik zu sagen (mein QM-Professor hat mir ausdrücklich gesagt, dass er die Informationstheorie liebt). All dies wird gesagt, es liegt irgendwo zwischen reiner Mathematik und Technik. Es hat die Fähigkeit und Flexibilität, direkt zu beiden beizutragen und von beiden direkt dazu beizutragen. Trotzdem kämpft es an seiner eigenen Grenze.
  • Da ist der Anwendungsbereich. Dies wurde im vorigen Aufzählungszeichen angedeutet. Informatik findet seinen Weg in viele verschiedene Anwendungen - Dinge, an denen sich alle, vom DHD bis hin zu Startups, interessieren. Sie werden sich nicht als hungrig nach Finanzmitteln wie Pure Mathematics sehen. (Sie werden immer noch hungern nach Geld.)
  • Da ist die Herausforderung. Werfen Sie einen Blick auf eine Liste offener Probleme in der Theoretischen Informatik (und verfolgen Sie deren Verständnis bis zum Ende der Untersuchung). Sie sind sehr schwer - hier sind einige Gründe warum . Wir verstehen TCS wirklich nicht - die meisten unserer Beweise laufen darauf hinaus, Beweise zu sammeln. Es gibt einfach so viel zu tun!
Ross Snider
quelle
19

In der Tat ist es eine Frage der Wahl, ob Sie sich für Forschung in der theoretischen Informatik entscheiden. Aber selbst das Lesen der Fragen auf dieser Site (wie Sie es wahrscheinlich getan haben) gibt Ihnen hoffentlich ein Gefühl für die Breite, den Umfang und die Schönheit des Fachgebiets. Ich weiß nicht einmal, wo ich anfangen soll, Sie auf Quellen hinzuweisen, die Sie lesen können, um die Art der Arbeit von Theoretikern zu würdigen, aber genau auf dieser Site gibt es eine Frage, die Sie meiner Meinung nach interessieren könnte.

Die Frage ist:

Paul Erdos sprach über das "Buch", in dem Gott den elegantesten Beweis für jeden mathematischen Satz aufbewahrt. Dies inspirierte sogar ein Buch (von dem ich glaube, dass es jetzt in der 4. Auflage vorliegt): Proofs from the Book.

Wenn Gott ein ähnliches Buch für Algorithmen hätte, welche Algorithmen würden Sie für einen Kandidaten halten?

Derzeit gibt es 64 Antworten auf diese Frage, die Algorithmen für kleine Probleme, große Probleme, Rätsel und tiefe Mathematik behandeln. Ich bin der festen Überzeugung, dass Sie viel darüber lernen würden, was theoretische Informatiker tun und warum wir es tun, wenn Sie nur diese Liste durchgehen und mehr über die Algorithmen lesen, die Ihnen auffallen.

Viel Glück !

Suresh Venkat
quelle
16

Der Grund, warum viele von uns in die Forschung gegangen sind, ist, dass wir es als angenehm empfinden, die Grenzen dessen zu verschieben, was bekanntermaßen sowohl intellektuell als auch unterhaltsam ist. Wenn wir forschen, haben wir außerdem die unvergleichliche Freiheit, an Problemen zu arbeiten, die wir für sinnvoll und interessant halten, und es fordert uns ständig heraus (was uns Spaß macht).

TCS (im Gegensatz zu anderen Bereichen) ist ein mathematisches Studium der Informatik. Sie können den theoretischen Aspekt vieler verschiedener Bereiche von verteilten Systemen bis hin zu maschinellem Lernen bearbeiten. Die Wahl zwischen TCS und anderen Bereichen der Informatik hängt davon ab, wo Ihr Geschmack und Ihre Fähigkeiten liegen. Wenn Ihre natürlichen Interessen und Fähigkeiten mehr in der Programmierung oder im Systemdesign liegen als in der mathematischen Analyse, sollten Sie sich vielleicht nicht mit TCS befassen. Auf der anderen Seite sollten Sie TCS in Betracht ziehen, wenn Ihre Fähigkeiten und Interessen mehr in mathematischen Aspekten liegen.

Außerdem müssen Sie nicht immer einen Bereich vor allen anderen auswählen. Viele Menschen bearbeiten Probleme sowohl von der theoretischen als auch von der praktischen Seite. Dies ist zum Beispiel beim maschinellen Lernen üblich, wo wir zuerst Algorithmen entwerfen und analysieren (oft Theorie) und sie dann in der realen Welt testen (experimentelles Design, Anwendungen usw.).

Eine gute Möglichkeit, herauszufinden, was Sie tun möchten, besteht darin, Kurse in vielen verschiedenen Bereichen zu belegen und in den Sommermonaten möglicherweise sowohl Industrie als auch Forschung zu testen. Am Ende Ihres Studiums werden Sie wahrscheinlich eine gute Vorstellung davon haben, was Sie tun möchten.

Lev Reyzin
quelle
Ich mag Mathe sehr, aber ich liebe es zu programmieren. Vielleicht könnte ich einen Weg finden, mit beiden "Seiten" gleichzeitig zu arbeiten, wie maschinelles Lernen [was ist im KI-Bereich, richtig?]. Im nächsten Jahr werde ich mich für einige Kurse an meiner Universität bewerben, z. B. AI und Algorithm Analysis, die mir helfen können.
23.
Maschinelles Lernen (zumindest aus meiner Sicht) ist kein Teilbereich der KI, obwohl es einige Überschneidungen gibt. Grob gesagt konzentriert sich AI darauf, Probleme zu lösen, die Menschen normalerweise lösen. Maschinelles Lernen konzentriert sich auf die Entwicklung von Algorithmen und Systemen, die das Verhalten ändern, wenn sie Daten sehen. Es gibt also eine deutliche Überlappung zwischen den beiden Feldern, aber sie sind weit davon entfernt, dasselbe zu tun. Maschinelles Lernen gibt den Menschen eindeutig die Möglichkeit, sowohl Theorie als auch Programmierung zu betreiben, aber ich bin sicher, dass es nicht das einzige Teilfeld von CS ist, für das es gilt.
Lev Reyzin
11

Die Theorie der Programmiersprache macht Jung und Alt Spaß. Es wendet Logik auf die reale Welt an. Komm zur Parade !!

Im Ernst, für mich ist die Programmiersprachtheorie aus folgenden Gründen interessant:

  • wahrgenommene Auswirkung auf die reale Welt: Die umfangreiche Typsystemarbeit in Haskell und anderen funktionalen Sprachen, die aus rein logischen Ideen (System F) stammt, beeinflusst die Entwicklung von Sprachen wie Java (seine schrecklichen Generika, Verschlüsse) und Scala (die Moderne) erheblich Tag, an dem Theorie und Praxis zusammentreffen.

  • Schönheit: Viele der in der Programmiersprachtheorie verwendeten Werkzeuge basieren auf Logik. Ein Großteil davon stammt aus der Curry-Howard-Korrespondenz, die einen engen Zusammenhang zwischen logischen Beweisregeln und Schreibregeln für Programmiersprachen sowie zwischen der Eliminierung von Kürzungen in der Logik und der Bewertung in einer Programmiersprache zeigt. Zwei schöne Beispiele für Anwendungen der Logik in der Programmiersprachenforschung sind die umfangreichen Arbeiten zur Trennungslogik in der Verifikation und die Anwendung von Beweisideen, die sich auf das Verständnis von Konzepten der Programmiersprache wie Evaluierungsreihenfolge und Musterabgleich konzentrieren .

  • Spaß: Sie können gleichzeitig programmieren und theoretisch arbeiten, insbesondere wenn Sie Ihre Theorien mit einem Proof-Assistenten wie Coq formalisieren und verifizieren.

  • und viele mehr.

Dave Clarke
quelle
11

Einer der Hauptgründe, warum ich die Computertheorie („mein“ Zweig der theoretischen Informatik) faszinierend und studienwürdig finde, ist der folgende: Sie gibt uns die Möglichkeit, einige tiefe (und manchmal rätselhafte) philosophische Fragen zu untersuchen.

Einer der Begründer der Berechnungstheorie, Alan Turing, versuchte, die Bedeutung von „Berechnen einer Funktion“ für einen Menschen, der mit einem Stück Papier ausgestattet war, durch eine mathematische Beschreibung des Prozesses zu bestimmen. Ich bin nicht der Einzige, der glaubt, dass er äußerst erfolgreich war, und Turing-Maschinen haben sich als genaues Modell für viele andere Computerprozesse erwiesen.

Jetzt, da wir eine Klasse mathematischer Objekte besitzen, die Berechnungen beschreiben, können wir Theoreme über sie beweisen und auf diese Weise herausfinden, was berechnet werden kann und wie es berechnet werden kann. Es stellte sich sofort heraus, dass viele absolut legitime Funktionen überhaupt nicht berechnet werden können und dass sie nach einem Grad an Unberechenbarkeit klassifiziert werden können (einige Funktionen sind einfach „unberechenbarer“ als andere).

Einige andere Typen, die ersten, die normalerweise mit Juris Hartmanis und Richard E. Stearns identifiziert wurden, versuchten mathematisch zu beschreiben, was es bedeutet, dass eine Funktion (bzw. ein Problem) schwer oder einfach zu berechnen (bzw. zu lösen) ist. Es gibt verschiedene Komplexitätsmaße, nach denen die Härte von Problemen beschrieben werden kann; Die häufigste ist, wie viel Zeit wir brauchen, um sie zu lösen. Alan Cobham und Jack Edmonds waren recht erfolgreich darin, einen vernünftigen Begriff von "effizienter Berechnung" zu identifizieren.

Innerhalb der Rechenkomplexität Rahmen können wir nun beweisen einige Ergebnisse , die mit unserer intuitiven Begriff der Berechnung konsistent sind. Mein Lieblingsbeispiel ist der Zeithierarchiesatz: Wenn wir mehr Zeit zum Berechnen haben, können wir schwierigere Probleme lösen.

Das zentrale offene Problem der Komplexitätstheorie, P vs NP , ist nur eine Formalisierung einer anderen philosophisch bedeutsamen Frage: Ist es wirklich schwieriger, ein Problem zu lösen, als zu überprüfen, ob eine angebliche Lösung tatsächlich korrekt ist? Ich glaube, diese Frage ist es wert, unabhängig von ihrer praktischen Bedeutung gestellt und beantwortet zu werden.

Antonio E. Porreca
quelle
+1: Gefällt mir :) ps: Jemand hat ähnliche Meinungen in Scotts Blog geäußert .
Kaveh
6

Wir können Sie nicht "überzeugen", da die Informatik mathematisch nicht besser ist als die KI oder ein anderes Gebiet. Wir können also keinen Beweis für seine Dominanz erbringen! IMO, es ist mehr Geschmackssache als alles andere.

Unglaublich
quelle
1
Ich stimme Ihnen zu, aber wahrscheinlich möchte er wissen, warum "Sie" (oder alle anderen hier) dieses Feld gewählt haben.
MS Dousti
@ Júlio Souza: Im Titel sollte es "theoretisch" sein, nicht "theoretisch".
MS Dousti
Ich möchte nicht wissen, ob es besser ist, aber ich möchte wissen, warum Sie dieses Feld gewählt haben, wie Sadeq sagte.
22.
6

Es ist schwer, diese Frage mit Sicherheit zu beantworten, aber hier sind einige Dinge zu beachten.

Wenn Sie als Informatiker Karriere machen, müssen Sie bei Ihrer Arbeit wahrscheinlich nicht nur Daten so verarbeiten und strukturieren, dass sie nützlich und effizient sind, sondern auch darüber nachdenken, wie und warum das funktioniert, was Sie tun welche Grenzen es hat (wenn auch aus keinem anderen Grund, als es zu verstehen, um es zu implementieren). Dies ist INSBESONDERE bei AI / NLP / IR der Fall, was SEHR forschungsintensiv ist, auch wenn Sie nicht in der akademischen Welt sind. Tatsächlich garantiert das Einsteigen in die KI, dass Sie sich intensiv mit "theoretischen" Problemen befassen, und tatsächlich kann es schwierig sein, einen Job ohne diesen Hintergrund zu finden. Das könnte ein zwingender Grund sein, warum Sie es in Betracht ziehen würden.

Darüber hinaus wäre es wahrscheinlich sehr schwierig, den größten Teil Ihres Lebens in einem CS-Bereich zu verbringen, in dem Sie einen so engen Kontakt zu solch heiklen und launischen (und nicht zu vergessen schwierigen) Prozessen unterhalten müssten und gleichzeitig Nein interessiert sich überhaupt für die Grundlagen, warum die Dinge funktionieren. Mit anderen Worten, ich nehme an, Sie könnten Bibliotheken für den Rest Ihres Lebens zusammenkleben, aber wenn das nicht nach Ihrem Ding klingt, müssen Sie zumindest die Grundlagen der Probleme kennen, mit denen Sie sich befassen.

Während die aktive Teilnahme an der TCS-Forschung eine Frage ist, die wahrscheinlich nur Sie beantworten können, ist es ein guter Ausgangspunkt (IMO), mit Blick auf die Probleme zu beginnen, an denen Sie interessiert sind, und von dort aus fortzufahren. Möglicherweise verfügen Sie auch nicht über genügend Informationen, um diese Frage zu beantworten. Ein besserer Weg, um fortzufahren, besteht darin, nur zu sehen, wohin Ihre Interessen Sie führen.

apc
quelle
Danke für die Antwort. Ich stimme Ihrem POV vollkommen zu, arbeite an etwas, was ich gerade mache, ohne zu wissen, warum es funktioniert, wie es funktioniert und ob ich es verbessern könnte, ist etwas, das ich nicht will. Ich denke, ich kann versuchen, meine Pläne mit KI [oder etwas anderem, was eher wie "praktische Forschung" aussieht] beizubehalten, aber ich werde weiterhin versuchen, mehr über andere Themen im Bereich TCS zu erfahren.
23.
6

Was mich am meisten fasziniert, ist die Fähigkeit, die Theorie der Informatik auf andere Disziplinen anzuwenden, insbesondere auf die Biologie und die Zellbiologie. Wenn Sie dieser Gedanke auch interessiert, sollten Sie sich Folgendes ansehen: einen Aufsatz von Jeannette Wing über die Bedeutung des computergestützten Denkens ; und ein NSF-Bericht über die Anwendung der algorithmischen Linse auf andere wissenschaftliche Disziplinen.

Aaron Sterling
quelle