Tischbeschreibung der theoretischen Informatik?

51

Ich werde oft gefragt, was ein theoretischer Informatiker macht. Es wäre toll, einige nette Antworten auf diese Frage zu haben. Ich neige dazu, auf Fachjargon zurückzugreifen, und die Augen der Leute leuchten an dieser Stelle normalerweise auf.

Was macht ein theoretischer Informatiker in Begriffen, die von Menschen verstanden werden können, die keine Informatiker sind?

Eine gute Antwort sollte bissig und korrekt sein, ohne vage oder banal zu klingen. Für Bonuspunkte sollte die Antwort darauf hinweisen, warum ein theoretischer Informatiker weder Mathematiker noch Informatiker ist.

Diese Frage ist von der MO-Frage https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics inspiriert, obwohl die Absicht anders ist.

András Salamon
quelle

Antworten:

34

Meine Antwort lautet im Allgemeinen: "Ich untersuche, warum einige Berechnungen schwierig sind." Als Beispiel vergleiche ich normalerweise Addition und Multiplikation mit den Standardmethoden der Grundschule. Dies sind Berechnungen, die jeder gemacht hat und die jeder zu schätzen weiß, wie wichtig es ist, schnell zu machen. Alle sind sich einig, dass bei großen Zahlen die Multiplikation viel schwieriger ist als die Addition. Tatsächlich schlagen die meisten Leute vor, dass die Grundschulmethode so schnell ist, wie Sie gehen können. Dann frage ich sie warum. Woher wissen sie, dass es keinen anderen Weg gibt, Multiplikation so einfach wie Addition zu machen?

Ziemlich jeder hat an dieser Stelle zumindest eine gewisse Wertschätzung für die Schwierigkeit, Untergrenzen zu beweisen (mein besonderes Interesse), obwohl ich diesen Begriff nicht verwendet habe. Je nach Hintergrund und Interesse des Publikums kann ich erwähnen, dass jemand einen Weg gefunden hat, um sich zu vermehren, der viel schneller ist als die Grundschulmethode (einfach das Wort "Algorithmus" neigt dazu, ihre Augen glasig zu machen), aber immer noch langsamer als hinzufügen.

Aubrey da Cunha
quelle
8
Ich mag, dass Ihr Beispiel Addition und Multiplikation als Beispiele verwendet. Es scheint, dass dies für einen Laien noch weniger einschüchternd ist als Sortieren oder Suchen.
Lev Reyzin
Dies ist eine wirklich gute Möglichkeit, um schnell zur Sache zu kommen, danke!
András Salamon
3
Ich habe das gleiche Beispiel gegeben :) Die Reaktion, die ich gesehen habe, ist, dass Leute in Ablehnung gehen und sich fast über mich ärgern: "Was meinst du damit, wir wissen nicht, ob Multiplikation schwieriger ist als Addition? Natürlich bist du es mit mir spielen? "
Sasho Nikolov
Ich mag diese Antwort wirklich, aber es ist nicht das, was ich tue! Ich arbeite auf einem ganz anderen Gebiet, nämlich der Theorie der abhängigen Typen. Sollte ich "Theorie A" gegen "Theorie B" erklären?
Cody
39

Ich gebe den Leuten ein konkretes Beispiel. Insbesondere motiviere ich oft die Komplexitätstheorie mit demselben sehr anschaulichen (aber einfachen) Problem. Ich frage meine Zuhörer, wie sie ein kleines Kind anweisen würden, herauszufinden, ob sein Name in einer alphabetisch sortierten Liste von Namen enthalten ist (und sage ihnen, dass das Kind 3 Sekunden benötigt, um einen Namen mit einem anderen zu vergleichen). Es ist häufig der Fall, dass die Person / Gruppe den naiven, linearen Ansatz entwickelt. Ich zwinge die Konversation, sich dem logarithmischen Algorithmus zuzuwenden (möglicherweise verwende ich ein anderes Wort als Logarithmus), indem ich die Person nach etwas Besserem frage oder es selbst erwähne. Ich zeige ihnen, wie die Verdoppelung der Listengröße mit diesem neuen Ansatz nur drei Sekunden Arbeit für das Kind bedeutet. Und ich vergleiche dies direkt mit der linearen Version, die jetzt völlig albern erscheinen wird.

Natürlich bringe ich es zurück auf die Erde. Ich sage ihnen, dass es sich bei dem fraglichen Kind im Allgemeinen um einen Computer handelt, dass es sich aber auch um ein Kind oder um jemanden im Allgemeinen handeln könnte. Die Fragen, die wir stellen, beziehen sich nicht wirklich auf Computer, sondern vielmehr auf die Menge an Platz, Zeit und Informationen, die Sie zur Lösung von Problemen benötigen. Und ich motiviere die Komplexitätsanalyse in Analogie zu den beiden verschiedenen Methoden zur Lösung desselben Problems.

Wenn ich ihre Aufmerksamkeit erlangt habe - bringe ich die schweren Schläger heraus. Ich frage sie: "Können Sie beweisen, dass die logarithmische Lösung die beste ist, auf die Sie jemals hoffen können, oder können Sie etwas Besseres finden?" und ich frage sie: "Gibt es Probleme, die kein Prozess (Algorithmus) lösen kann?" Ich war überrascht, wie die Leute versuchen, diese Fragen zu beantworten, wenn sie keinen TCS-Hintergrund haben.

Ross Snider
quelle
1
Und für die Aufzeichnung, ich hatte ziemlich viel Glück damit, Leute, die mir nahe stehen, für das Thema zu interessieren.
Ross Snider
1
Vor dem endgültigen Untergang des Telefonverzeichnisses hätte dies zu einer bissigen Antwort mit zwei Sätzen werden können. Gibt es ein kanonisches Beispiel für eine nach dem Zufallsprinzip sortierte Liste, die jeder kennt?
András Salamon
Sicher, András. Der Index eines Buches. Alternativ können Sie sich natürlich ein neues Kartenspiel zulegen, bevor es gemischt wurde. Dann können Sie natürlich auch über den ungeordneten Fall nachdenken.
Joe Fitzsimons
@Joe: Ich treffe mich regelmäßig mit Leuten, die keine Lehrbücher mit Indizes verwendet haben. Vielleicht, wenn Harry Potter mit einem Index kam ...
András Salamon
@ András: Ich habe wohl zu oft auf dem College gegessen! Sicher haben sie fast alle Schulbücher.
Joe Fitzsimons
21

Ich mag diesen Beitrag von Scott Aaronson , der die Komplexitätstheorie als quantitative Theologie erklärt. Hier ist ein Auszug:

In der Theorie der rechnergestützten Komplexität geht es wirklich, wirklich, wirklich nicht um Computer. Computer spielen bei der Komplexität dieselbe Rolle wie Uhren, Züge und Aufzüge bei der Relativitätstheorie. Sie sind eine großartige Möglichkeit, den Punkt zu veranschaulichen. Sie waren wahrscheinlich wichtig, um den Punkt zu entdecken, aber sie sind nicht der Punkt.

Die beste Definition der Komplexitätstheorie, die ich mir vorstellen kann, ist die quantitative Theologie: das mathematische Studium hypothetischer superintelligenter Wesen wie Götter. Ihre Anliegen umfassen:

  • Wenn ein Gott oder Götter existierten, wie konnten sie sich den Sterblichen offenbaren? (IP = PSPACE oder MIP = NEXP im polytheistischen Fall.)

  • Welche Götter sind mächtiger als welche anderen Götter? (P NP gegen PP, SZK gegen QMA, BQP NP gegen NP BQP usw. usw.)

  • Könnte ein herrlicher Gott beschließen, einem Sterblichen Seine Allwissenheit zu verleihen? (EXP vs. P / Poly.)

  • Kann man Orakeln trauen? (Können Orakel vertraut werden?)

Und natürlich:

  • Könnten Sterbliche jemals selbst gottgleich werden? (P gegen NP, BQP gegen NP.)
Robin Kothari
quelle
Es kann nur einen Gott geben. Unter der Annahme, dass mehrere Götter logisch inkonsistent sind, haben mehrere Götter unterschiedliche Eigenschaften, was dem Prinzip eines höchsten Gottes widerspricht. (Ein Gott ist mächtiger als ein anderer Gott ist albern.)
Mohammad Al-Turkistany,
1
@ Williams, mein Punkt ist, dass der Laie mit diesen Analogien verwechselt wird .
Mohammad Al-Turkistany
10
obwohl ich das wirklich nicht tun sollte, sollte ich darauf hinweisen, dass mehrere Götter nur unter der Annahme inkonsistent sind, dass gottähnliche Eigenschaften eine Gesamtordnung bilden. Wenn sie eine Teilordnung bilden, ist es vollkommen in Ordnung, mehrere Götter zu haben. (Entschuldigung, Ryan)
Suresh Venkat
@Suresh, deuten Sie an, dass es zwei Götter geben könnte, die wir nicht sagen können, wer mächtiger ist? Die binäre Beziehung ist hier die Gesamtordnung. (Entschuldigung, Ryan)
Mohammad Al-Turkistany
18

Eine Beispielantwort, die definitiv verbessert werden kann:

Theoretische Informatiker untersuchen das Rechnen in mathematischen Begriffen. Sie können Ihren Computer reparieren und Mathematiker können Ihre Steuern berechnen.

András Salamon
quelle
20
Leider sind die meisten Leute, die ich kenne, der Meinung, dass Mathematiker die Steuern genau berechnen können ...
Lev Reyzin
11
Dies erinnert mich an das berühmte Zitat von Dijkstra: "In der Informatik geht es nicht mehr um Computer als in der Astronomie um Teleskope."
Vinayak Pathak
2
Lez - Diese Leute sollten über den Grothendiek Prime informiert werden.
Vinayak Pathak
13
Hier ist eine andere, die von jondoda auf Twitter stammt: "Einen Informatiker um technische Unterstützung zu bitten, ist wie einen Botaniker zu bitten, Ihren Rasen zu mähen." Dieser wird wärmer ...
Ryan Williams
4
Ryan, die Konsequenz ist, dass beide die Aufgabe leicht erfüllen können, es aber ablehnen, gefragt zu werden?
Joe Fitzsimons
16

Ich denke, eine ausgezeichnete (Nicht-) Antwort in dieser Richtung wurde von Dijkstra gegeben (immer eine gute Quelle für knusprige und absolutistische Äußerungen :)).

In der Informatik geht es nicht mehr um Computer als in der Astronomie um Teleskope. - EW Dijkstra

Suresh Venkat
quelle
11

Mir gefällt die Einführung in das Partitionierungsproblem, die Brian Hayes hier gegeben hat, sehr gut .

Er verwendet das Problem der Aufteilung einer Gruppe von Kindern in Teams mit den gleichen Gesamtfähigkeiten (vorausgesetzt, Sie können die Fähigkeiten jedes Kindes anhand einer Zahl quantifizieren) und erklärt auch den Gier-Algorithmus, der normalerweise von Kindern zur Lösung dieses Problems verwendet wird.

Es ist ein sehr einfaches Problem zu verstehen, es ist leicht zu verstehen, überraschend, dass es (höchstwahrscheinlich) im Allgemeinen sehr schwer ist und es peinlich ist, dass wir das letzte Stück noch nicht beweisen können.

Alex ten Brink
quelle
Das ist wirklich gut. Irgendwie habe ich es hier vorher nicht bemerkt.
Ryan Williams
Liebte den Artikel!
Arnab
8

Normalerweise antworte ich so: Ich versuche herauszufinden, was mit einem Computer alles möglich ist. Es ist nicht ganz genau, aber es ist ziemlich nah, und die Leute fragen normalerweise etwas wie "Was meinst du?" und ich kann auf etwas Bestimmtes verweisen, wie TSP. Obwohl ich den reisenden Verkäufer als das Problem des Bar-Hopping, das Problem des Immobilienmaklers, das Problem, dass zu viele Besorgungen nicht genug Zeit haben oder was auch immer angemessen erscheint, umformuliere.

Zum Beispiel: "Nehmen wir an, Sie müssen Schuhe, Lebensmittel und Kleidung kaufen, sich einen Kuchen holen, sich die Haare schneiden lassen und vor dem Abendessen noch einige andere Besorgungen machen. Es wäre großartig, wenn Sie all diese Dinge unterbringen könnten Wenn die Liste der Besorgungen jedoch lang genug ist, ist es im Moment nicht einmal möglich, herauszufinden, ob Sie dies tun müssen kann sie durch 4 getan überhaupt , viel weniger , was Sie sie in in jeder angemessenen Zeit tun müssen , bestellen. ich möchte wissen , ob es möglich ist, dieses Problem schnell mit einem Computer zu lösen.“

philosodad
quelle
Großartig, ich denke, das ist die Art von Antwort, die ein interessantes Gespräch auslösen würde!
András Salamon,
7

Was sind die besten Möglichkeiten, um Probleme zu lösen, und welche Probleme sind zu schwer zu lösen? Es gibt ein Wort in europäischen Sprachen - einschließlich Englisch! - "Informatik". Die Wissenschaft der Information. In den USA nennen wir diese theoretische Informatik wegen der starken Computerindustrie hier, aber denken Sie eine Minute lang an das Lösen von Problemen ohne Computer. Betrachten Sie den menschlichen Körper. Es löst Probleme auf fast wundersame Weise. Licht kommt in unsere Augen und wir können Dinge sehen, die wir erkennen . Ton kommt in unsere Ohren und wir hören Worte, die wir verstehen . Dies sind Informationsprobleme, die wir leicht lösen können und mit denen die besten Computer der Welt noch immer zu kämpfen haben.

Der Evolutionsprozess dauerte Millionen von Jahren, um diese Probleme zu lösen, indem eine Strategie ausprobiert und das Unglück getötet wurde. Stellen Sie sich vor, was wir erreichen könnten, wenn wir rationaler vorgehen und so viel menschliche Kreativität in diese neue Wissenschaft des Problemlösens investieren würden, wie wir in Geometrie, Theologie oder Analysis investiert haben. Was ich tue, ist ein kleiner Teil dieser Investition.


Als Antwort auf die Frage des Laien: "Was machst du?" Ich habe oft geantwortet: "Ich verbringe viel Zeit damit, in den Weltraum zu starren und herauszufinden, wie man Science Fiction Wirklichkeit werden lässt." Dann gebe ich ein konkretes Beispiel für ein Projekt, das in ein paar Sätzen erklärt wird.

Aaron Sterling
quelle
1
Die meisten Leute, die ich kenne, würden denken, dass jemand, der versucht, Science Fiction Wirklichkeit werden zu lassen, ein Physiker ist. Wie unterscheiden Sie sich?
András Salamon
2
Ich würde es lieben , wenn ein experimenteller Wissenschaftler etwas bauen würde, das ich mir ausgedacht habe. Warum muss es einen Weg geben, um zu unterscheiden? Um es dennoch zu beantworten: Ich denke an mikroskopische Computer, während Physiker über die Eigenschaften der Materie nachdenken. Ist da ein Unterschied? Kommt darauf an, worauf Sie Wert legen und worauf Sie Wert legen.
Aaron Sterling
Das hört sich für mich so an, als würde erklärt, was Informatik ist, aber nicht, was theoretische Informatik ist.
Zsbán Ambrus,
6

Theoretische Informatik ist für die Informatik das, was Mathematik für die Physik war.

Andrej Bauer
quelle
2
warum "früher"?
Suresh Venkat
1
Ich erinnere mich an etwas wie: "CS zu Logik / Kombinatorik (TCS) ist wie Physik zu Geometrie."
Kaveh
3
Klar, ich denke, Andrej behauptet dies: Früher hat das Studium der Physik einen großen Teil der von Mathematikern untersuchten Probleme hervorgebracht, aber dieser Teil ist im Laufe der Jahre zurückgegangen (jetzt ist die Mathematik viel weiter gefasst). Ich kann nicht genug über die Geschichte der Mathematik sagen, dass dies wahr ist, aber was ich weiß, stimmt damit überein.
Ryan Williams
1
Ich denke nicht, dass diese Analogie funktioniert, weil Laien auch nicht über Mathematik und Physik Bescheid wissen.
Zsbán Ambrus,
5

Ich gebe in der Regel die folgende Antwort, obwohl ich mich auf die Komplexitätstheorie konzentriere: "Ich untersuche die räumlichen und zeitlichen Grenzen eines zu lösenden Problems. Zu den Problemen gehört es, den kürzesten Weg auf einer Karte zu finden oder ein Schachspiel zu gewinnen."

Michaël Cadilhac
quelle
5

Normalerweise nenne ich das Factoring-Problem als Beispiel; Ich frage zuerst nach der Zahl, die 15 teilt; Normalerweise können die Leute 3, 5 beantworten und sich fragen, ob 1 und 15 die richtige Antwort sind. Dann gebe ich eine riesige Zahl (mehr als 10 Stellen) und frage, ob sie mir sagen können, was die Teiler sind; und ich erkläre, dass dies selbst für Informatiker eine wirklich schwierige Frage ist.

Wenn ich dann Zeit habe, versuche ich zu erklären, dass es entweder darum geht, herauszufinden, wie dieses Problem gelöst werden kann, oder zu beweisen, dass es immer viel Zeit in Anspruch nimmt (ein Begriff, den wir genau definieren können). Und dann ein kleines Wort Kryptographie, um zu erklären, warum es verwendet wird, und ein Wort darüber, wie viel Zeit ein Wissenschaftlerteam benötigt, um den Schlüssel einer Zahl mit Hunderten von Ziffern zu knacken (ich vermeide es, von Bits zu sprechen, weil die Leute es besser zu wissen scheinen) Was ist eine Ziffer?

Arthur MILCHIOR
quelle
5

Die gestellte Frage ist wirklich schwierig, da die meisten Menschen keine Ahnung haben, was Informatiker im Allgemeinen tun. Dies unterscheidet sich sehr von anderen Disziplinen.

Ich verwende gerne die folgende Analogie: (T) CS ist für Computer, die Physik für CD-Player (dh den Laser). Das funktioniert eigentlich ganz gut, weil die meisten Leute eine Vorstellung davon haben, was ein Physiker macht, ob es nun richtig ist oder nicht.

Speziellere Beispiele sind die Dinge, mit denen sich die meisten Menschen identifizieren können

  • String Matching (langsamer naiver Ansatz vs. tägliche Erfahrung mit schneller Suche in Word, Browser, ...)
  • Kürzestes Pfadproblem (wie in Navigationssystemen verwendet)
  • Scheduling (abhängig vom Grad der Nerdiness des anderen, beziehen sich auf Geschäftsprozesse oder Scheduling auf CPU)

Ich würde dann erklären, dass PCS-Mitarbeiter zwar für eine schnelle Implementierung oder eine gute Integration in komplexe Systeme sorgen würden, TCS-Mitarbeiter sich jedoch fragen, was möglich ist, und nachweisen, dass PCS sichere, wiederverwendbare Kenntnisse und Techniken zur Verfügung stellt.

Sie können auch die Frustration der Menschen über Computer nutzen ("Es macht nicht, was ich will!"). Sie können darauf hinweisen, dass es in (T) CS darum geht, Dinge so auszudrücken, dass Computer sie verstehen und effizient verarbeiten können (in Bezug auf Syntax, Semantik, Datenstrukturen, Algorithmen).

Raphael
quelle
4

Wenn Ihnen jemand eine Frage stellt, können Sie diese entweder direkt beantworten oder ihm eine schrittweise Anleitung geben, um zu beweisen, dass die Antwort innerhalb eines angemessenen Zeitraums eingeht, wenn die Schritte genau befolgt werden. Angesichts der Tatsache, dass die Schritte selbst nicht zu kompliziert sind und von einer in diesem Universum existierenden Entität schnell ausgeführt werden können, weisen welche Arten von Fragen solche Verfahren auf? Ich denke, das ist das Thema der theoretischen Informatik.

Vinayak Pathak
quelle
1
Das einzige Problem ist die Rede von Dingen, die im Universum existieren. Das macht es eher zu Physik als zu TCS. Immerhin ist das Universum ein endliches Objekt, und ein großer Teil der TCS befasst sich mit Assymptotik.
Joe Fitzsimons
Hmm, das ist ein guter Punkt. Aber verwenden wir wirklich Asymptotik, weil wir wissen wollen, wie unser Algorithmus bei Eingabegrößen abschneidet, die größer als das Universum sind, oder verwenden wir die Big-Oh-Notation, um unsere Berechnungen grob modellunabhängig zu machen?
Vinayak Pathak
Ich denke, Dinge wie die Entscheidung über die Berechenbarkeit usw. leben auf einer abstrakteren Ebene.
Joe Fitzsimons
4

Meine übliche Antwort, die nicht bissig ist, aber die Konversation garantiert zum Erliegen bringt (Bonus!), Lautet: "Wie die Quantentheorie der mathematische Kern der Physik ist, ist TCS der mathematische Kern der Informatik."

Suresh Venkat
quelle
3
Tatsächlich ist eher die theoretische Physik als die Quantenmechanik das TCS der Physik. Neben der Quantenmechanik gibt es eine Reihe anderer physikalischer Theorien (das offensichtlichste Beispiel ist die klassische allgemeine Relativitätstheorie).
Joe Fitzsimons
Das Ziel ist nicht Genauigkeit :)
Suresh Venkat
Dann kann man aber weiter fragen: "Was ist Informatik?"
Vinayak Pathak
4

Wir untersuchen die Grenzen der Berechnung. Wie schnell können Sie ein bestimmtes Rechenproblem lösen? Wie viel Zeit ist erforderlich, um es zu lösen, egal welche Lösung Sie versuchen? Dann gebe ich ihnen diese Beispiele (die für die meisten Laien leicht zu erklären sind - und in der Tat haben viele Laien direkte Erfahrung mit ihnen -, die einige Eigenschaften von NP-vollständigen Problemen aufzeigen und tatsächlich damit zu tun haben, Leben zu retten).

Offensichtlich mögen Leute (einschließlich ich) witzeln, dass ich wichtige andere Ressourcen wie Raum, Zufälligkeit oder sogar Quantität ignoriert habe. Aber wenn Sie nur 2 Minuten Zeit haben, um jemandem von einem ganzen Feld zu erzählen, werden einige Dinge ausgelassen.

Joshua Grochow
quelle
4

Wenn Sie einen skurrilen Blick in die Vergangenheit werfen möchten, erinnern Sie Ihr Publikum daran, dass sich "Computer" auf eine Person bezog, deren Beruf darin bestand, Dinge zu berechnen . (Und wenn Sie gegen einige Stereotype verstoßen möchten, die sie möglicherweise haben, können Sie darauf hinweisen, dass es sich häufig auch um Frauen handelt.)

Sie können dann eine Handvoll Dinge auf einmal erreichen:

  • ein überzeugendes Argument dafür vorbringen, dass "Informatik" mehr sein kann, als "Computer" zu studieren;
  • weisen darauf hin, dass Computeranwender einige Regeln benötigen , um ihre Aufgabe zu erfüllen (insbesondere in einem Raum voller "Computer", die spezielle Aufgaben erledigen - Komplexität der Kommunikation und Parallelisierung?), und dies gilt auch für Maschinen.
  • beschreiben, dass es in der "Informatik" darum geht, effektive Wege zu finden, um Probleme zu lösen, die "Computing" in diesem Sinne betreffen;
  • Stellen Sie klar, dass es nicht so wichtig ist, was genau das Rechnen leistet, wie die benötigten Ressourcen (wie Zeit und Arbeitsspeicher).
Niel de Beaudrap
quelle
4

Ich beginne immer damit, sie auf ein kreatives, absichtlich respektloses Video oder einen Artikel zu verweisen, in dem ein technisches Konzept auf einer intuitiven Ebene erklärt wird. Hier ist ein gutes Beispiel: Kritzeln in Mathe: Spiralen, Fibonacci und eine Pflanze sein

Sobald sie das Konzept verstanden haben (und hoffentlich ein bisschen Spaß damit hatten), versuche ich, das, was sie gelernt haben, auf etwas über TCS zu verallgemeinern. Das obige Video könnte beispielsweise zu einer grundlegenden Erklärung von Algorithmen oder Berechnungen als rekursiver Prozess führen - "etwas, das aus wenigen, einfachen Regeln eine komplexe Struktur erzeugt." TCS-Leute studieren also einfach, welche Arten von Regeln welche Arten von Strukturen erzeugen!

Von dort aus ist es im Allgemeinen einfach genug, von der allgemeinen TCS zur domänenspezifischen Aufgabe überzugehen. :)

Daniel Apon
quelle
2

Nach dem Vorschlag von Ross Snider, mit einem konkreten Beispiel zu beginnen, kann man die Frage von P gegen NP auch direkt erläutern. Man kann diese Frage einem Laien so beschreiben, dass er herausfindet, ob die Überprüfung einer Lösung nachweislich einfacher ist als die tatsächliche Suche, oder ob wir sie auch finden können, wenn wir eine Lösung überprüfen können?

Vinayak Pathak
quelle
2

Hier ist meins:

Informatik ist nicht nur Wissenschaft, es steckt auch viel Ingenieurwissen dahinter, aber im wissenschaftlichen Teil geht es darum, Berechnungen zu verstehen. Und eine Berechnung ist ein physikalischer Prozess, der Informationen auf geordnete Weise erzeugt. In der theoretischen Informatik glauben wir, dass wir eine relativ ausgefeilte Mathematik benötigen, um die Berechnung zu verstehen.

Dies führt zu einem guten Gespräch über das Rechnen in der Biologie, die Rolle der Logik in der Informatik usw.

Charles Stewart
quelle
2

Vielleicht könnte man das sagen

Ein theoretischer Informatiker studiert wirklich sehr schwierige Probleme im Zusammenhang mit der Informatik.

Der Wissenschaftler benutzt keinen Computer, wenn er kreativ ist, sondern denkt viel nach, kritzelt Formeln und skurrile Zeichnungen auf Papier und wandert gelegentlich herum. Dabei ist die unmittelbare Umsetzbarkeit nicht das Wichtigste, sondern eher ein Künstler, der die Geheimnisse dieser Welt erforscht und zu verstehen versucht.

Dann könnte man Dinge erwähnen, die auf eleganten Lösungen von Theoretikern beruhen, wie Computer, Internet, Suchmaschinen, sicheres Banking, 3D-Filme, DNA-Sequenzierung usw. Man sollte jedoch immer betonen, dass niemand die Anwendungen der heutigen Forschung kennt. Einige davon sind möglicherweise erst seit mehreren Jahrzehnten zu sehen.

Nach meiner Erfahrung haben viele Menschen einen AHA-Moment, in dem sie feststellen, dass die Informatik und insbesondere die Theorie so reich an interessanten Fragen und Problemen ist, die es zu studieren gilt. Viele davon lassen sich auf hohem Niveau beschreiben! Dies ist eine Liste von Prof. Wikipedia (über SIGACT), wählen Sie Ihre Favoriten aus: Algorithmen, Datenstrukturen, Theorie der rechnerischen Komplexität, verteilte Berechnung, parallele Berechnung, VLSI, maschinelles Lernen, rechnerische Biologie, rechnerische Geometrie, Informationstheorie, Kryptographie, Quantenberechnung , rechnergestützte Zahlentheorie und Algebra, Programmsemantik und -verifikation, Automatentheorie und das Studium der Zufälligkeit.

Michael
quelle
0

Was macht ein theoretischer Informatiker in Begriffen, die von Menschen verstanden werden können, die keine Informatiker sind?

So ziemlich das Gleiche wie ein VCR-Reparaturmann. Beide überlegen, wie die beste Leistung von Maschinen erzielt werden kann, die Informationen auf extrem lange Bänder lesen und schreiben.

Das ist vielleicht ein bisschen mehr als das, wonach Sie gesucht haben ...

Joe Fitzsimons
quelle
Es würde sicherlich das Gespräch am Laufen halten!
András Salamon
11
Oh gut. Können Sie mir sagen, wie die Uhr aufhört zu blinken?
Jeffs
1
Natürlich berechne ich den üblichen Gewerkschaftssatz.
András Salamon
Ich weiß, dass dies eine kleine Zunge auf der Wange war, aber wenn ich die Abwärtsstimmen bemerke, werde ich sie gerne entfernen, wenn jemand ein ernstes Problem damit hat.
Joe Fitzsimons
1
Kein Problem! Ich war besorgt, dass entweder einige CS-Theoretiker oder einige VCR-Mechaniker Anstoß genommen haben könnten.
Joe Fitzsimons