Die lineare Programmierung ist ein sehr leistungsfähiges algorithmisches Werkzeug. Im Wesentlichen geht es bei einem linearen Programmierproblem darum, eine lineare Funktion reeller Variablen zu optimieren, die durch ein System linearer Ungleichungen eingeschränkt wird. Dies ist ein äußerst vielseitiger Rahmen, der sich sofort auf die Verallgemeinerung von Flussproblemen anwenden lässt, aber auch zur Diskussion einer Vielzahl anderer Probleme verwendet werden kann, von der Optimierung von Produktionsverfahren bis hin zur Suche nach dem billigsten Weg zu einer gesunden Ernährung. Überraschenderweise lässt dieser sehr allgemeine Rahmen effiziente Algorithmen zu. In dieser Lektion werden wir einige der wichtigsten Probleme der linearen Programmierung sowie einige der Werkzeuge zu ihrer Lösung besprechen.

Obwohl viele der Algorithmen, die Sie bisher gelernt haben, in der Praxis häufig angewandt werden, stellt sich heraus, dass die Welt von realen Problemen ohne einen bekannten, nachweislich effizienten Algorithmus dominiert wird. Viele dieser Probleme lassen sich auf eines der klassischen Probleme reduzieren, die als NP-komplette Probleme bezeichnet werden und die entweder nicht durch einen polynomialen Algorithmus gelöst werden können oder deren Lösung Ihnen eine Million Dollar (siehe Millenium Prize Problems) und ewigen Weltruhm für die Lösung des Hauptproblems der Informatik namens P vs NP einbringen würde. Es ist gut, das zu wissen, bevor Sie versuchen, ein Problem vor der morgigen Deadline zu lösen :) Obwohl es sehr unwahrscheinlich ist, dass diese Probleme in naher Zukunft effizient gelöst werden können, lassen sich die Menschen immer wieder verschiedene Umgehungslösungen einfallen. In diesem Modul werden Sie die klassischen NP-kompletten Probleme und die Reduktionen zwischen ihnen studieren. Sie werden auch üben, große Instanzen einiger dieser Probleme trotz ihrer Schwierigkeit zu lösen, indem Sie sehr effiziente Spezialsoftware verwenden, die auf tonnenweise Forschung im Bereich der NP-kompletten Probleme basiert.

Nach dem vorangegangenen Modul sind Sie vielleicht traurig: Sie haben gerade 5 Kurse über Algorithmen besucht, nur um zu erfahren, dass diese für die meisten Probleme der realen Welt nicht geeignet sind. Aber geben Sie noch nicht auf! Die Menschen sind kreativ und müssen diese Probleme sowieso lösen, so dass es in der Praxis oft Wege gibt, ein NP-komplettes Problem zu bewältigen. Wir zeigen zunächst, dass einige Spezialfälle von NP-kompletten Problemen tatsächlich in polynomieller Zeit gelöst werden können. Dann betrachten wir exakte Algorithmen, die eine Lösung viel schneller finden als der Brute-Force-Algorithmus. Wir schließen mit Approximationsalgorithmen, die in polynomieller Zeit arbeiten und eine Lösung finden, die nahe am Optimum liegt.

In den meisten früheren Vorlesungen waren wir daran interessiert, Algorithmen mit einer schnellen (z.B. kleinen polynomiellen) Laufzeit zu entwerfen, und nahmen an, dass der Algorithmus zufälligen Zugriff auf seine Eingabe hat, die in den Speicher geladen wird. In vielen modernen Anwendungen der Big Data-Analyse ist die Eingabe jedoch so groß, dass sie nicht im Speicher abgelegt werden kann. Stattdessen wird die Eingabe als ein Strom von Aktualisierungen präsentiert, die der Algorithmus durchsucht, während er eine kleine Zusammenfassung des bisher gesehenen Stroms behält. Dies ist genau der Rahmen für das Streaming-Modell der Berechnung, das wir in dieser Vorlesung untersuchen. Das Streaming-Modell ist gut geeignet, um Algorithmen auf kleinem Raum zu entwerfen und darüber nachzudenken. Es hat in der Literatur viel Beachtung gefunden, und es wurden mehrere leistungsstarke algorithmische Primitive für die Berechnung grundlegender Stream-Statistiken in diesem Modell entwickelt, von denen einige die Praxis der Big Data-Analyse beeinflussen. In diesem Vortrag werden wir uns einen solchen Algorithmus (CountSketch) ansehen, einen Small Space Algorithmus zur Ermittlung der k häufigsten Elemente in einem Datenstrom.