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.
quelle
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.
quelle
Ich mag diesen Beitrag von Scott Aaronson , der die Komplexitätstheorie als quantitative Theologie erklärt. Hier ist ein Auszug:
quelle
Eine Beispielantwort, die definitiv verbessert werden kann:
quelle
Ich denke, eine ausgezeichnete (Nicht-) Antwort in dieser Richtung wurde von Dijkstra gegeben (immer eine gute Quelle für knusprige und absolutistische Äußerungen :)).
quelle
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.
quelle
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.“
quelle
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.
quelle
Theoretische Informatik ist für die Informatik das, was Mathematik für die Physik war.
quelle
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."
quelle
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?
quelle
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
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).
quelle
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.
quelle
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."
quelle
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.
quelle
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:
quelle
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. :)
quelle
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?
quelle
Hier ist meins:
Dies führt zu einem guten Gespräch über das Rechnen in der Biologie, die Rolle der Logik in der Informatik usw.
quelle
Vielleicht könnte man das sagen
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.
quelle
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 ...
quelle