Kürzlich wurde in einem Online-Forum eine Frage gestellt: Wie stark ist Mathematik unter den Bedingungen eines echten Programmierers gefragt, wie oft verwendet er sie und in welchen Bereichen? Und hier ist meine Antwort.
Zunächst verwende ich, wie fast alle Programmierer, die
Boolesche Logik aus der Analyse logischer Ausdrücke für bedingte Anweisungen und Ausstiegskriterien, um solche Ausdrücke beispielsweise mit
den Gesetzen von de Morgan in Einklang zu bringen. Der Großteil unserer Arbeit grenzt an die
Berechnung von Prädikaten erster Ordnung und anderer Prädikatenlogik in Form der Analyse von Voraussetzungen, Invarianten und mehr (obwohl es den Anschein haben mag, dass wir einige andere Aufgaben ausführen).
Außerdem beschäftige ich mich häufig mit der Analyse der Komplexität von Algorithmen. Die Dimensionen der Datensätze, die heutzutage verarbeitet werden, sind enorm. Auf einer
Techonomy- Konferenz 2010
sagte Eric Schmidt , dass das Datenvolumen, das die Menschheit heute in nur zwei Tagen erstellt hat, dem Volumen aller weltweit vorhandenen Daten ab 2003 entspricht. Für mich ist es wichtig, große Segmente dieser Volumina verarbeiten und davon profitieren zu können. In diesem Sinne ist das Verständnis der
räumlich-zeitlichen Komplexität von Operationen , die wir auf Daten anwenden, der Schlüssel, um festzustellen, ob bestimmte Berechnungen im Prinzip möglich sind. Im Gegensatz zu den traditionelleren Arten der
O-Analyse oder
Theta-Analyse haben konstante Faktoren auf solchen Skalen einen signifikanten Effekt: Faktor 2 ändert die asymptotische Zeitkomplexität des Algorithmus nicht, erfordert jedoch eine Erhöhung der Anzahl der Prozessoren von 10.000 auf 20.000 und einen solchen Unterschied im Verbrauch Ressourcen werden greifbar sein. Infolgedessen werden die Berechnungen komplexer. Beispiele: Kann ich eine lineare Berechnung durchführen und auf eine logarithmische reduzieren? Ist es möglich, den Speicherverbrauch um das Dreifache zu reduzieren? Usw.
Oft muss ich die ungünstigste Variante der Obergrenze berechnen, beispielsweise die Größe eines Datensatzes. In vielen Fällen können solche Berechnungen nicht trivial sein. Oder Sie müssen möglicherweise eine
Wiederholungsformel analysieren, um zu überprüfen, wie sie sich mit zunehmender Tiefe der Rekursion ändert. Dazu muss ich unter anderem den
Grundsatz über Wiederholungsrelationen kennen und die Prinzipien der Analyse von
Zahlenreihen verstehen. Und es mag unglaublich erscheinen, aber manchmal bedeutet es, dass ich das
Integral berechnen muss (obwohl meistens nur die
Riemann- Integrale). Oder kann ich einfach die rekursive Beziehung lösen und eine
endliche Anzahl von Lösungen erhalten ? Muss ich auf
lineare Algebra zurückgreifen? Dies führt zu
Funktionen wie
Generieren von Funktionen ,
Stirling-Zahlen und
Matrixberechnungen . Wenn Sie neugierig sind, was in den grundlegenden mathematischen Konzepten enthalten ist, die für das Verständnis der Informatik erforderlich sind, lesen Sie den ersten Band von „The Art of Programming“ von Donald Knuth oder „Concrete Mathematics“ von Knut, Ronald Graham und Oren Patashnik.
Ich führe viele grundlegende Berechnungen in Bezug auf das Aggregieren, Kombinieren und Transformieren von Daten durch, und die
Kombinatorik (Zählen der Anzahl, Finden von Symmetrien in verschiedenen Dimensionen usw.) hilft mir dabei. Ich denke, die Beispiele aus diesem Bereich sind offensichtlich.
Ich verwende viel
diskrete Mathematik , insbesondere für die Suche nach algebraischen Systemen in Operationen mit besonders großen Datenmengen. Ist es möglich, diese oder jene Struktur mit Hilfe des
Homomorphismus als eine bestimmte
Gruppe oder einen bestimmten
Ring darzustellen, was mir klarer wird? Gibt es eine Option mit einer weniger engen Verbindung? Kann ich die
Aktion einer Gruppe auf eine bestimmte Menge anwenden, um ein spekulatives Transformationsmodell zu erstellen, das die Argumentation vereinfacht? Kann ich eine Topologie für die Datenanalyse definieren? Sie wären überrascht, wenn Sie wüssten, wie viele Dinge mit
diskreten Topologien beschrieben werden können. Und noch weniger überraschend wäre die Forderung nach
Dreiecksungleichheit .
Ich arbeite viel mit
Graphentheorie . "Erstellen von Websites" - erfordert nicht nur die Fähigkeit, niedliche Bilder von Katzen auf der Seite zu platzieren. Bei diesem Vorgang werden auch Knoten in das globale Diagramm der
Hyperlinks eingefügt . Das Hinzufügen einer einzelnen Seite führt zu einer potenziellen Erhöhung der Anzahl der Diagrammkanten. Dies kann wiederum Auswirkungen haben, die auf den ersten Blick auf Leistung, Analyse, Suchmaschinenranking und andere Merkmale nicht offensichtlich sind. Das Verständnis der Konsequenzen solcher Änderungen kann dazu beitragen, interessante Informationen zu erhalten, z. B. wie das Diagramm wächst. Es stellt sich heraus, dass diese
Dynamik einem
Potenzgesetz schmerzlich ähnlich
ist : Das World Wide Web ist ein
skalierungsloses Netzwerk . Was ist der
kürzeste Weg zwischen zwei Knoten dieses Graphen? Wie sieht ein solches Netzwerk aus, wenn Sie versuchen, es als
planaren oder
zweigeteilten Graphen
darzustellen ? Wann ist es möglich, diese Eigenschaften einzuhalten, wenn es natürlich überhaupt möglich ist? Was aber, wenn wir das World Wide Web nicht als Grafik betrachten, sondern das gesamte Straßennetz Nordamerikas, Europas oder Asiens?
Dieses Wissen hat andere Konsequenzen. Oft verstehen die Leute nicht, dass moderne Webseiten nicht nur
HTML- Dokumente mit Links und anderen Ressourcen sind, sondern
baumartige Datenstrukturen
, die in einem
Diagramm miteinander verbunden sind . Diese Bäume werden aufgrund der Interaktion zwischen dem Webbrowser des Benutzers und einem Server (dank Technologien wie
AJAX ) häufig gecrawlt, verarbeitet und dynamisch aktualisiert.
Ein gutes und geeignetes Beispiel ist
MathJax . Oder
Google Mail . Um zu verstehen, wie sie funktionieren, sind einige Kenntnisse über
symbolisches Rechnen und die
semantische Analyse von Seitenelementen erforderlich. Die Autoren von MathJax mussten ein Programm schreiben, das in der Lage ist, den auf der Grundlage des
Objektmodells des Dokuments generierten Baum zu durchlaufen, mathematische Elemente zu finden, sie zu „
verstauen “ und dynamisch durch neue gezeichnete Elemente zu ersetzen. Vielleicht sind einige Benutzer, die nur sehen, wie es funktioniert, nicht sehr beeindruckend, aber unter der Haube passieren ziemlich komplizierte Dinge. Normalerweise muss ich nichts Ähnliches tun (ich arbeite nicht mit dem Frontend), aber die ganze Zeit mache ich ähnliche Dinge in
Lisp . Bitte beachten Sie, dass Lisp ursprünglich durch die mathematische Verarbeitung symbolischer Informationen geschärft wurde: Die Makros decken die Probleme der Verarbeitung symbolischer Ausdrücke vollständig ab.
Ich arbeite viel mit
Zeitreihen . Wie verändert sich der Verbrauch von Verkehr oder Ressourcen? Welche Trends können hervorgehoben werden? Zeigt sich dieser oder jener Sprung in der Verzögerung bei der
saisonalen Beantwortung von Anfragen oder beim Speicherverbrauch? Wie reagiert die
Änderungsrate von etwas, wenn die Eingabedaten in verschiedenen Dimensionen variieren? Gibt es eine
Korrelation mit einem externen Ereignis?
Ich arbeite viel mit statistischer Datenanalyse, um nicht nur Leistungsmerkmale zu bestimmen, sondern auch die Daten als solche zu verstehen. Neben der Suche nach den oben genannten semantischen Metadaten im DOM-Baum (z. B.
Mikrodaten und
Mikroformate ,
RDF , andere
XML- Daten mit einem bestimmten
Schema ) versuche ich auch,
unstrukturierte Daten zu erfassen . Wie hoch ist die Wahrscheinlichkeit, dass dieser Text eine Adresse ist? Oder sind es
grafische Koordinaten ? In welchem Kontext erscheint er? Ist es
Spam ? Macht es überhaupt Sinn? Sieht es aus wie das Ergebnis eines Textgenerators, der auf
Markov- Ketten basiert? Vielleicht ist dies eine Reihe von Zitaten aus einem bekannten literarischen Werk? Oder ein Fragment einer literarischen Diskussion? Oder ist dies eine Diskussion über Spam, der ein literarisches Fragment enthält? Ich lache immer noch jedes Mal, wenn ich an Spam-E-Mail-Werbemittel denke, die in ein Fragment von Bulgakovs „Meister und Margarita“ eingewickelt sind.
Kategorietheorie .
Typen in Computerprogrammiersprachen entsprechen in etwa Kategorien, und
Monaden und
Funktoren können verwendet werden, um einige Konstruktionen ernsthaft und elegant zu vereinfachen. In der
funktionalen Programmiersprache Haskell werden beispielsweise Monaden für
E / A und für die
Zustandsmodellierung verwendet. Wenn es um vereinfachte Programme geht, ist es einfacher, sie zum Laufen zu bringen. Es ist einfacher, über sie zu sprechen, es ist einfacher zu verstehen, sich zu ändern und so weiter. Typen können oft auf der Grundlage logischer Überlegungen bestimmt werden, was zum Auftreten von
Sonderfällen führt (die auch bei allgemeinen Argumentationsproblemen verwendet werden können). Überlegen Sie, was passiert, wenn Sie die
Schlussfolgerungen verwenden , um logische Funktionen anzuwenden, wie sie beispielsweise in
Prolog verwendet werden , um
Diagramme in
verteilten Systemen zu
transformieren .
Verteilte Systeme bringen uns zur Graphentheorie zurück. Im realen Maßstab beschädigen Systemabstürze, Bagger Fasern, Erdbeben, Vulkanausbrüche und Fischtrawler die Seekabel. Um die Konsequenzen solcher Ereignisse zu verstehen und die besten Reaktionsmöglichkeiten zu ermitteln, müssen die Merkmale des Netzwerkgraphen verstanden werden. Routing-Algorithmen und Netzwerkanalysen hängen eng mit Dingen wie dem
Finden des kürzesten Pfades zwischen Knoten in einem Diagramm zusammen. Der
Dijkstra-Algorithmus hilft Ihnen dabei.
Und doch, wie können Sie die Last aus einer großen Berechnung auf Rechenzentren in verschiedenen Teilen der Welt verteilen? Hier benötigen Sie auch einige physikalische Kenntnisse: Auf der Skala des Internets wird die
Lichtgeschwindigkeit zu einem „Engpass“.
Wärmeableitung ,
Stromdichte pro Flächeneinheit und mehr sind Beispiele dafür, was Programmierer bei der Arbeit mit realen Aufgaben berücksichtigen müssen. Soll ich ein Rechenzentrum in Island hosten? Günstige Kühl- und Geothermiequellen schaffen attraktive Bedingungen, aber wie steht es mit der minimalen Verzögerung für Benutzer, die möglicherweise daran interessiert sind, Geräte in einem solchen Rechenzentrum zu mieten? Wie
groß ist die Entfernung entlang des Bogens eines
großen Kreises zwischen beispielsweise Island und London oder Berlin und Amsterdam? All dies zu berechnen ist recht einfach, aber dafür sind bestimmte mathematische Kenntnisse erforderlich. Können wir Fasern von Island zu einem anderen Zentrum schicken? Was ist die durchschnittliche Verzögerung? Wie hoch ist die Wahrscheinlichkeit eines U-Boot-Kabelbruchs in der Nordsee während eines Betriebs von 12 Monaten? Und für 48 Monate?
Natürlich sind die
Theorie der Algorithmen , die
Theorie der Automaten , das
Parsen , die
formale Grammatik und die
regulären Sprachen alle Wissensbereiche, mit denen sich Programmierer ständig befassen. Ich arbeite oft mit Parsing und
Pattern Matching . Bei der Arbeit mit realen Daten können auch nicht sehr große Mengen Elemente enthalten, die zu
pathologisch schlechtem Verhalten führen können, wenn beispielsweise
Backtracking-Techniken verwendet werden . Wenn ich
reguläre Ausdrücke verwende , um Daten abzugleichen, sollte ich vorsichtig sein und sicherstellen, dass diese Ausdrücke
wirklich regulär sind .
Wenn ich einen
Computer mit Speicher zum Speichern der
kontextfreien Grammatik verwende (was übrigens jedes Mal geschieht, wenn Sie eine Anforderung an einen
HTTP- Server senden), muss ich sicherstellen, dass ich die Rekursionstiefe beschränke, um zu vermeiden, dass der Prozessoraufrufstapel erschöpft wird, was Verständnis erfordert zugrunde liegende Berechnungsprinzipien und die Mathematik, auf der sie basieren.
Wenn ich meinen eigenen
rekursiven Abstiegsalgorithmus für eine ungewöhnliche Grammatik schreiben muss und er nicht mit
LALR (1) übereinstimmt
( ich kann also nicht nur
Yacc oder
Bison verwenden ), muss ich vorsichtig sein oder den Statusstapel von der prozeduralen Rekursion trennen. Dieses Verständnis ist auch erforderlich, wenn ich den DOM-Baum (oder eine rekursiv definierte Datenstruktur) umrunde.
Einige Programmiersprachen betrachten dies als Schwierigkeit bei der Arbeit eines Programmierers und umgehen es durch die Verwendung
segmentierter Stapel . Natürlich wäre es großartig, wenn ich meine Sammlung einiger der analysierten Ressourcen in Form einer
Funktion (im mathematischen Sinne) definieren könnte. Und wie cool wäre es, wenn es nur um ein Problem der
linearen Programmieroptimierung ginge?
Bitte beachten Sie, dass keines der oben genannten esoterischen Kenntnisse ist. All dies basiert auf Erfahrungen mit Aufgaben und realen Daten. Natürlich mache ich das nicht jeden Tag, aber das meiste dieses Wissens wende ich regelmäßig an und nur einige - von Zeit zu Zeit. Wahrscheinlich haben Beobachtung, Erfahrung und Heuristik mehr Einfluss auf den Prozess als sie sollten (heuristische Modelle sind oft unvollständig und ungenau). Verfüge ich über genügend mathematische Kenntnisse, um den durchschnittlichen
Fehler zwischen der Realität und meinem heuristischen Modell zu berechnen?
Dies ist die Essenz der Informatik sowie ihre Interaktion mit der Programmierung und den Realitäten des modernen Rechnens. Ein IT-Experte zu sein ist nicht dasselbe wie ein Experte auf dem Gebiet der Computertheorie zu sein, und wie viele zu Recht betonen, ist ein solcher Experte einem angewandten Mathematiker viel näher als einem Fachhandwerker. Auf keinen Fall möchte ich die Bedeutung solcher Fachkräfte herabsetzen, da sie nützlich sind und allgemein anerkannt werden, aber ich möchte nur darauf hinweisen, dass Informatik etwas anderes ist.
(Übrigens bin ich selbst kein Experte für Informatik. Ich habe reine Mathematik studiert und mein beruflicher Beruf ist dem Ingenieurwesen viel näher.)
