Dann begrüße ich Sie recht herzlich zur Vorlesung Algorithmen 2.
Genau, mein Name ist Peter Sanders.
Ich mache Algorithmen und Algorithm Engineering am Institut für
Theoretische Informatik.
Heute werde ich Ihnen diesen Begriff des Algorithm Engineering etwas
näher bringen, um einen etwas größeren Kontext zu geben, wo ich
Algorithmen sehe.
Und auch, was da in unserer Arbeitsgruppe passiert.
Diese Vorlesung selber wird so ein bisschen weiter auf der
theoretischen Seite bleiben.
Also wir machen die theoretischen Aspekte wichtiger Algorithmen.
Das sind allerdings Algorithmen, die auch praxisrelevant sind.
Aber was in der Vorlesung aus Zeitgründen fehlen wird, ist eine
Abhandlung über Wie implementiere ich das Zeug tatsächlich?
Was sind da Trade-offs?
Wie wirkt sich das auf verschiedene Eingabeinstanzen aus?
Plus extensiver experimenteller Evaluierung.
Das ist eigentlich wichtig, wenn Sie praxisrelevante
Algorithmenforschung machen wollen.
Da gibt es auch eine Spezialvorlesung Algorithm Engineering.
Aber für eine Algorithmen 2 Vorlesung würde das sozusagen den Rahmen
sprengen.
Weil man dann zu jedem Einzelnen dieser Aspekte viel mehr Details
liefern müsste, als man das kann.
Und wir haben uns halt entschieden, lieber einen Überblick zu liefern.
Und dann ist man mit der theoretischen Behandlung von praxisrelevanten
Algorithmen eigentlich einem Sweet Spot.
Und das entspricht auch weitgehend dem Standard dessen, was Sie an
anderen Standorten, an anderen Universitäten, die eine solide
Algorithmen -Ausbildung haben, an einer fortgeschrittenen Algorithmen
-Vorlesung hören.
Dann gibt es halt im ersten Teil fortgeschrittene Datenstrukturen.
Da nehme ich auch nur ein Beispiel, nämlich Prioritätslisten.
Das man aber in verschiedene Richtungen drehen kann.
Prioritätslisten kennen Sie vermutlich alle.
Binäre Heaps oder sowas.
Da hat man aber ein paar Probleme, wenn man entweder zusätzliche
Operationen braucht.
Insbesondere von beliebigen Elementen den Schlüssel ändern.
Das nennt man dann Adressierbare.
Oder man kann die schneller machen, wenn die Schlüssel ganzzahlig
sind.
Oder sie könnten sehr groß sein, mit externer Memory sein.
Dann fortgeschrittene Graphen-Algorithmen.
Wir hatten den Algorithmen 1, Kürzeste-Wege-Algorithmen,
kennengelernt.
Aber da gab es irgendwie so einen Bruch.
Was passiert, wenn es negative Kantengewichte gibt?
Wie gehe ich damit um?
Da sind wir so ein bisschen drum rumlaviert.
Das gucken wir uns jetzt etwas genauer an.
Dabei lernt man eine Technik, die für Graphen-Algorithmen insgesamt
sehr nützlich ist.
Nämlich die Potential-Methode.
Also eigentlich ganz grundsätzlich geht es darum, was passiert, wenn
Sie einen Graphen haben mit Kantengewichten, die negativ sein können
und wo Ihnen diese Tatsache massiv in die Suppe spuckt, wenn Sie
irgendwie nach guten Faden suchen wollen.
Das tritt in vielen Anwendungen auf.
Und man kann diese negativen Kantengewichte loswerden, indem man
sozusagen Kantengewichte manipuliert auf eine systematische Art und
Weise.
Nicht mithilfe von sogenannten Knotenpotentialen.
Das werden wir uns am Beispiel von Kürzesten-Wegen anschauen.
Wir haben in Algorithmen 1 die Tiefensuche kennengelernt.
Ganz schnell konnte man dann erklären, wie man topologische
Sortierungen von gerichteten azyklischen Graphen macht.
Oder einfach irgendwie einen Graphen traversiert.
Diese Methode ist aber erstaunlich stark.
Man kann damit Dinge tun in linearer Zeit, wo man auf den ersten Blick
denkt, das ist richtig schwierig.
Wir werden uns das am Beispiel der starken Zusammenhangskomponenten
anschauen.
Die man eben auch in vielen Anwendungen braucht.
Und dann gucken wir uns was an jenseits dessen, was in dem Algorithmen
1 Buch steht.
Flüsse und Matchings.
Das ist im Prinzip eine logische Fortsetzung von dem, was man bei
Kürzesten -Wegen hat.
Weil man irgendwie Daten- oder Informationsfluss im gesamten Netzwerk
betrachtet.
Und nicht nur einzelne Pfade.
Das hat auch vielfältige Anwendungen.
Sehr spannende Algorithmen und ist deshalb ein schönes Beispiel für
eine fortgeschrittene Algorithmen-Vorlesung.
Dieser zweite Teil könnte man unter Bindestrich-Algorithmen anschauen.
Da gibt es jeweils Spezialvorlesungen dazu, die nicht immer alle jedes
Jahr anbieten.
Randomisierte Algorithmen macht zum Beispiel der Thomas Worsch eine
Spezialvorlesung dazu.
Wie kann ich gezielt Zufall einsetzen, um Algorithmen einfacher oder
effizienter zu machen.
Externe Algorithmen, also wie kann ich mit Speicher-Hierarchien
umgehen.
Parallele Algorithmen, wie setze ich viele Prozessoren ein.
String-Algorithmen, also Texte, Zeichenketten, aber auch Informationen
wie Genomdaten.
Das sind lange Ketten von Buchstaben, in denen man verschiedene Dinge
tun will.
Insbesondere will man die durchsuchen.
Da braucht man Index-Datenstrukturen führen.
Um das zu tun, muss man die zumindest sortieren können.
Jetzt werden wir uns also geometrische Algorithmen anschauen.
Also was ist, wenn ich Objekte habe, wie Punkte, Linien, Kreise usw.,
die ich verarbeiten möchte.
Das ist natürlich auch ein ganz wichtiges Thema für vielfältige
Anwendungen.
Dann sind Approximations-Algorithmen ein Ansatz, um mit NP-harten
Problemen umzugehen.
Wo ich sage, naja, vielleicht ist es schwierig, das Problem optimal zu
lösen.
Aber vielleicht gibt es ja effiziente Algorithmen, die
Näherungslösungen lösen.
Am liebsten hätte ich welche, wo ich garantieren kann, dass diese
Näherungen eine bestimmte Qualität haben.
Damit beschäftigt man sich bei Approximations-Algorithmen.
Und ein anderer Umweg, der es einem erlaubt, NP-harte Probleme doch
lösbar zu machen, ist zu sagen, ich löse die zwar exakt, aber ich
gucke mir genau an, welche Instanzen ich exakt effizient lösen kann.
Und Online-Algorithmen sind wiederum ein anderer Aspekt von
Optimierungsproblemen.
Fast alles, was wir uns in der grundlegenden Algorithmik angucken, ist
so, ich sage mal, Batch.
Also wir kriegen eine Eingabe, wir haben eine komplette Information
über das, was wir lösen wollen.
Und dann berechne ich halt eine Lösung.
Wunderschön, mathematisch, klar und einfach.
Leider ist die reale Welt nicht so einfach.
Computerprogramme müssen durchaus Entscheidungen treffen, ohne die
gesamte Eingabe zu kennen.
Zum Beispiel, weil diese Daten überhaupt nicht da sind oder noch
konkreter, weil sie erst in der Zukunft anfallen werden.
Ein Beispiel, das wir uns da anschauen werden, ist, wenn Sie
überlegen, Skilaufen zu lernen.
Dann kann es sein, dass das irgendwie ganz toll ist.
Es gibt einen tollen Winter, Sie wollen jedes Wochenende Skifahren.
Fahren dann auch in die Alpen, da haben Sie Schneesicherheit und alles
andere.
Es kann aber auch sein, dass das Wetter so schlecht ist, dass Sie gar
nicht viel Gelegenheit haben.
Oder Sie brechen sich im Bein und können dann sowieso ein Jahr nicht
Skifahren.
Das heißt, die Entscheidung, ob es sich lohnt, Skier zu kaufen oder zu
mieten, ist irgendwie abhängig von zukünftigen Ereignissen, die Sie
nicht kennen.
Wie geht man damit um?
Sie kaufen trotzdem eine informierte Entscheidung, die Ihre Kosten,
die Sie haben, begrenzt und nicht zu absurden, hohen Kosten führt,
ohne dass Sie was davon haben.
Und Computerprogramme stehen auch vor so einem Problem.
Oft sogar analog zu dem, was da an diesem persönlichen Ding ist.
Also erstmal werde ich eine allgemeine Motivation da bringen, die ist
auf eine ganz interessante Weise entstanden.
Nämlich nicht als eine wissenschaftliche Arbeit, sondern eigentlich
als ein Projektantrag für ein Schwerpunktprogramm der Deutschen
Forschungsgemeinschaft.
Und das habe ich dann zusammen mit den Kollegen Mehlhorn, Möring,
Butzel und Wagner ausgearbeitet.
Ich werde ein paar Beispiele geben, meistens zu sortieren, weil das
was ist, was Sie jetzt auch wahrscheinlich schon kennen.
Und dann werde ich am Ende nochmal ein bisschen was über
experimentelle Mythologie sagen.
Ich denke mal, das ist dann gar nicht so sehr speziell nur relevant
für Algorithmen, sondern eigentlich egal, in welchem Gebiet Sie
arbeiten später, also in welchem Teilgebiet der Informatik, in den
meisten davon machen Sie Experimente und in den meisten davon gibt es
ein ziemlich ähnliches Setting wie hier.
Sie haben irgendwie Eingaben, müssen die schnell und qualitativ
hochwertig lösen, also im Endeffekt Algorithmen evaluieren.
Worüber ich nicht reden werde, ist User Interfaces, da gibt es
natürlich bei uns auch wichtige Gruppen.
Da haben Sie nochmal ein paar andere Aspekte zu berücksichtigen, wenn
Sie sich mit menschlichen Versuchspersonen auseinandersetzen.
Aber da rede ich jetzt natürlich gar nicht mehr.
Also was ist Algorithm Engineering?
Vielleicht gucken wir uns erstmal die traditionelle Sichtweise auf
Algorithmik an, die nämlich von vielen Leuten als Synonym mit
Algorithmenteorie betrachtet wird.
Also was ich da habe, ich habe irgendwie ein Modell meines Problems,
meiner Maschine.
Dann entwerfe ich einen Algorithmus.
Und zwar im Prinzip auf einem Blatt Papier.
Das hat nichts mit Implementierung zu tun.
Und dann wird der analysiert.
Das heißt, ich beweise mathematische Sätze über diesen Algorithmus.
Zum Beispiel, der hat eine Laufzeit von O von N², wenn N die
Eingabegröße ist.
Oder die Qualität der Lösung ist höchstens im Faktor 2 weg vom
Optimum.
Solche Aussagen werden dann bewiesen.
Das können Beweise sein, die über 20, 30, 100 Seiten gehen.
Das Ergebnis ist dann eine Leistungsgarantie dieses Algorithmus.
Das kann so weit gehen, dass sie bei Hardcore-Theorie arbeiten.
Irgendwie ein Papier haben, da steht Modell, das bedeutet hier
Definition, hier ist das Problem.
Das Ganze wird in dem und dem Maschinenmodell betrachtet.
Satz.
Also dann fangen die gleich damit an.
Dieses Problem lässt sich in Zeit bla lösen.
Beweis.
Und was dann kommt, ist, dass Entwurf und Analyse in einem zigseitigen
Beweis ineinander verquirlt sind.
Sie müssen dann, um zu verstehen, was da passiert, Beweis und
Algorithmus verstehen.
Man könnte argumentieren, dass das sogar ganz gut ist.
Weil wenn Sie einen Algorithmus verstehen wollen, dann müssen Sie
eigentlich auch den Beweis dazu verstehen.
Trotzdem ist das für einen Praktiker, der findet zwar gut, dass da
eine Leistungsgarantie ist, aber eigentlich will er nur den
Algorithmus haben, implementieren, benutzen.
Und ich sag mal, die Theorie der Theoretiker war, dass die Praktiker
dann ihre genialen Papiere lesen, den trivialen Schritt der
Implementierung vollziehen und das dann ganz toll anwenden.
Leider passiert das nicht.
Je komplexer dieser Algorithmus ist, desto seltener gibt es Anwender,
die bereit sind, sich da reinzugraben.
Oder auch nur, die über das Know-how verfügen, das überhaupt nur zu
versuchen.
Wenn es Leute gibt, die sich da reinladen, scheitern die dann oft
daran, dass das Ziel dieses Algorithmenentwurfs ja eben keine
Implementierung und Anwendung war, sondern ein theoretischer Satz.
Es gibt auch theoretische Arbeiten, da stehen dann so Sätze drin,
wie...
Inhaltlich steht das aber nicht formuliert, das ist jetzt ein bisschen
überspitzt.
Wir ignorieren den trivialen Fall von Eingabegrößen kleiner 10 hoch
3443.
Weil das ist trivial, das geht in konstanter Zeit, solche Probleme zu
lösen.
Es ist egal, dass die dann größer sein können als das Universum.
Aber es ist asymptotisch trivial.
Und dann wird eine Datenstruktur dargestellt oder ein Algorithmus, den
man in diesem Universum niemals implementieren will, weil der nur
interessant ist für überastronomisch große Eingaben.
Das ist mathematisch spannend.
Ich vermute sogar, dass in vielen Fällen algorithmische Ideen
dahinterstecken, die vielleicht dann doch mal in praktischen
Algorithmen eine Rolle spielen.
Aber da müssten Leute sich damit beschäftigen, die genauso schlau sind
wie diese Theoretiker und aber einen anderen Algorithmus formulieren,
der die Ideen irgendwie anders umsetzt.
Und das passiert halt in der reinen Algorithmentheorie zu selten.
Ja, das heißt, Sie haben hier einfach einen Mismatch, so einen Gap,
eine Schlucht zwischen Theorie und Praxis, die man irgendwie
überwinden muss.
Eine noch schlimmere Schlucht in gewisser Weise haben Sie, wenn das
Ganze jetzt keine Anwendung ist, die Sie komplett innerhalb der
Informatik abwickeln können oder die Sie sowieso schon super gut
verstehen, sondern wo Sie außerdem noch Know-how aus einer
Anwendungswissenschaft brauchen.
Sie wollen eine Klimasimulation machen oder irgendein
Bioinformatikproblem lösen.
Dann haben Sie eine interdisziplinäre Kooperation.
Das finden bei Sonntagsreden alle Leute ganz toll.
Aber wenn Sie Wissenschaft machen wollen in der Informatik, stellt
sich die Situation oft etwas anders dar.
Insbesondere hier diese Zeitskala-Geschichte.
Ich habe schon von ganz vielen Fällen gehört, gerade in den
Lebenswissenschaften, wo dann die Anwendungswissenschaftler kommen und
sagen, schau mal, wir haben hier diesen Riesenberg Daten produziert.
Es gibt jetzt tolle neue Maschinen und Sensoren.
Damit können wir Terabyte zu Terabyte superspannende Daten
produzieren.
Und wir wissen eigentlich, dass da Informationen drinstecken, die
einen Durchbruch in unserer Wissenschaft bedeuten können.
Wir können dann im Prinzip verstehen, wie Embryonalentwicklung
funktioniert, wie Genome Dinge codieren, die eben nicht einfach nur
Proteine codieren.
Und das ist ganz wichtig, das hat was auch mit Embryonalentwicklung zu
tun.
Also wie werden Gene überhaupt gesteuert?
Und viele andere Beispiele könnte man nennen.
Also man hat eine Revolution in einer datengetriebenen Wissenschaft
heutzutage, die uns gewaltige Möglichkeiten bietet.
Aber wenn Sie jetzt eine konkrete Kooperation haben, dann sagen die
ja, hier sind die tollen Daten, und dann unterhält man sich mit denen
vielleicht ein paar Stunden.
Und es kommt raus, jawohl, Sie haben recht, vermutlich sind die Daten
da.
Das ist ein superspannendes Problem für die Informatik, weil wir
müssen da neue Algorithmen entwickeln, die mit diesen gewaltigen
Datenmengen umgehen, darauf neue Probleme lösen, wo es keine fertigen
Algorithmen gibt.
Alles superspannend.
Und dann wäre jetzt eigentlich meine naive Reaktion dann, dann sagen
wir, okay, wir beantragen dafür jetzt ein Forschungsprojekt, Mittel,
und in den nächsten fünf Jahren werden wir diese Durchbrüche erzielen.
Und dann sagen die, nein, nein, nein, nein, wir müssen in drei Monaten
das eingereicht haben zu Science oder Nature, und wenn das nicht
passiert, dann macht das jemand anderes.
Also im Idealfall, genau, was dann passiert ist, na ja, dann setzt man
halt bekannte Informatikmethoden ein, möglichst mit existierender
Software, klebt die irgendwie mehr oder weniger stabil zu irgendeiner
Toolchain zusammen und kriegt irgendwas raus.
Und im Idealfall gibt das einem tatsächlich so einen Hinweis, was denn
dieser Durchbruch sein könnte, und das reicht dann für so eine
prominente Veröffentlichung.
Und natürlich geht es dann Schritt für Schritt weiter, dass man das
dann immer besser analysiert, aber auch mit neuen Maschinen,
blablabla.
Aber ein Informatiker sagt dann, ja, schön, ich verstehe, dass das
wichtig ist für den Fortschritt deiner Wissenschaft, aber meine
Doktoranden können nicht über bekannte Techniken promovieren.
Die müssen was Neues entwickeln, und dann ist die Kooperation schon zu
Ende.
Das heißt, da muss man auch irgendwie Ansätze entwickeln, wie man
darüber hinausgeht.
Zum Beispiel die Teilchenwissenschaftler, also die
Partikelphysikleute, die bauen Teilchenbeschleuniger, die Milliarden
kosten, wo der Aufbau Jahrzehnte dauert.
Und die Datenmengen produzieren, die jenseits von dem sind, was Google
oder sowas baut.
Sogar zum Teil um Größenordnungen.
Das gleiche gilt zum Beispiel für Radioteleskope oder sonst wo.
Und die haben dann in Datenanalyse Probleme.
Ich gucke mal in die Vergangenheit.
Ende der 90er haben die dann zum Beispiel diesen Large Hadron Collider
am CERN geplant.
Und die wussten, der produziert so und so viele Daten.
Das übersteigt die Rechenleistung aktueller Maschinen um drei
Größenordnungen.
Ist aber nicht schlimm.
Wir wissen ja, Moore's Law gilt irgendwie oder hoffen das.
Das heißt, wir machen jetzt schon einen Plan, wie wir unsere Software
entwickeln.
Wir entwickeln die kontinuierlich weiter auf diesen Zieldatum hin.
Dann und dann wird diese riesige Maschine angeworfen, produziert
Daten.
Und dann ist die Software schon fertig.
Die ist auch getestet und alles an Simulationsdaten.
Und die kann dann loslegen.
Es mag sein, dass das was anderes ist als in den Bio
-Lebenswissenschaften, wo ich mir für 30.000 Euro einen Mikroskop
hinstellen kann, das ich vielleicht auch relativ schnell entwickeln
kann, das trotzdem revolutionäre neue Daten produziert.
Ich will jetzt die Lebenswissenschaften nicht ärgern.
Aber das, was die Teilchenphysiker machen, erlaubt tatsächlich eine
geplante strategische Kooperation mit der Informatik.
Und vielleicht sollte man sich sowas auch für andere Wissenschaften
überlegen.
Da muss man aber dran arbeiten und man braucht eine Grundmethodologie.
Und da spielt, denke ich, das Algorithmen-Engineering auch eine Rolle,
weil im Herzen jeder nicht-trivialen Computeranwendung werkelt wie ein
Algorithmus.
Also wie gehe ich damit jetzt um?
Ich habe hier so verschiedene Sachen.
Anwendungen müssen irgendwie angebettet werden.
Vielleicht noch einen Satz zu dieser Publikationskultur.
Das ist jetzt so ein Informatiker, ein Wissenschaftler, der publiziert
meistens in irgendwelchen Konferenzproceedings.
Also da schreibt man einen relativ kurzen Aufsatz.
Der wird eingereicht zu einer Konferenz.
Und wenn das eine gute Konferenz ist, werden da ganz viele Sachen
eingereicht und nur ganz wenige akzeptiert.
So 10 bis 15 Prozent in einigen der Top-Konferenzen.
Und wenn man dann so eine Arbeiter angenommen bekommen hat, ist das
irgendwie ganz toll.
Gut für die Karriere, lesen alle, ist also so ein Qualitätsstempel.
Aus der Informatik-Sicht ist alles gut.
Das sind aber eben Informatikkonferenzen.
Und wenn Sie jetzt zum Beispiel Mathematik oder Lebenswissenschaften
oder so ansehen, die haben eine andere Kultur, da gibt es
Zeitschriften.
Da können Sie aber eben nur die Anwendungsergebnisse publizieren.
Und nicht, ich habe jetzt einen tollen Algorithmus entwickelt, der das
macht.
Das ist dann oft nur ein Nebensatz.
Dann ist man vielleicht einer von 300 Co-Autoren, auch schön.
Aber für eine akademische Karriere irgendwie ein Problem.
Und auch für die Wahrnehmbarkeit innerhalb der Informatik.
Und es gibt zwar auch Informatik-Zeitschriften.
Aber die haben andere Probleme.
Die brauchen zum Beispiel oft Jahre, um Ergebnisse auch wirklich zu
publizieren.
Deshalb geht man dann doch lieber auf die Konferenzen.
Kann da aber dann oft die interdisziplinären Sachen auch nicht
unterbringen.
Weil die Gutachter sagen, ja, damit kenne ich mich nicht aus.
Das ist ein Anwendungsproblem.
Falsche Konferenz, auch falsche Zeitschrift.
Also es gibt da riesige Probleme.
Die können wir nicht alle durch Algorithm-Engineering überwinden.
Aber ich wollte mal darauf hinweisen, wieso die Lage ist zwischen
Informatik, Theorie, Praxis, interdisziplinäre Sachen.
Vielleicht nochmal, wo denn überhaupt diese Lücken zwischen Theorie
und Praxis sind, ein bisschen genauer erklärt.
Theorie, Praxis, ja.
Wenn man so die Modelle anschaut, sowohl bei der Anwendung als auch
der Maschine, sind die in der Theorie sehr einfach und in der Praxis
oft unglaublich komplex.
Zum Beispiel, wenn Sie auf der Praxisseite Klimasimulation machen
wollen, dann sind das heutzutage halt Millionenzeilen von Code,
viele, viele Differentialgleichungen, verschiedene Subdisziplinen, die
sich mit Dingen wie Vegetation, Eis, Meer, Spurengase, hast du nicht
gesehen, Wolkenbildungsprozesse beschäftigen.
Über jedes davon kann man ganze Arbeitsgruppen, Jahrzehnte forschen
lassen.
Es muss alles irgendwie zusammengreifen.
Während wenn jemand Strömungssimulation macht, was schon irgendwie der
algorithmisch schwierigste Kern davon ist, dann sagt man, wir haben
eine zweidimensionale Welt.
Es gibt diese Differentialgleichung, die das beschreibt.
Da haben wir irgendwie ein paar hässliche Terme weggelassen, aber wir
können halt bestimmte Phänomene wie Turbulenzen und sowas bereits ein
bisschen sehen.
Und wir können vielleicht durchaus auch eine Algorithmenentwicklung
machen, die uns ein bisschen ein Gefühl dafür gibt, wann ist das
numerisch stabil und so weiter.
Alles durchaus sinnvoll, aber halt ein riesiger Unterschied.
Bei den Maschinen genauso.
Da gibt es, ich sag mal, dieses von-Neumann-Modell.
Ein sequenzieller Prozessor, ein uniformer Speicher, alle
Maschinenbefehle brauchen gleich lang.
Das ist ausreichend, um asymptotische Komplexität sequenzieller
Algorithmen zu beschreiben.
Aber hat irgendwie nichts mehr damit zu tun, wie reale Maschinen
heutzutage aussehen.
Mit vielen Prozessoren, Speicherhierarchien, Pipelineausführung von
Befehlen und die Laufzeit eines Befehls hängt von tausenden von
Aspekten an.
Welche Daten braucht die?
Was wurde vorher mit den Daten gemacht?
Welches Prozessormodell habe ich?
Sogar davon, ob es gerade warm oder kalt ist in dem Raum, in dem der
Rechner steht.
Weil wenn er warm ist und vorher außerdem das Ganze auf hoher Leistung
lief, dann regelt er die Taktfrequenz runter.
Wie wollen Sie das in der Algorithmenanalyse berücksichtigen?
Es macht schon Sinn, auf der Theorieseite einfache Modelle zu
betrachten, aber man muss sich bewusst sein, dass die realen Modelle
viel komplexer sind.
Wenn man sich jetzt die Algorithmen und Datenstrukturen anschaut, dann
ist es erstaunlicherweise genau umgekehrt.
Wenn Sie in der Algorithmenteorie auf den Top-Konferenzen
veröffentlichen wollen, muss das was ganz Kompliziertes sein.
Zum Teil so, dass das skandalös ist.
Zum Teil so, dass man den Eindruck hat, dass die Leute bewusst
einfache Ideen hinter komplexen, wolkigen Konstrukten verwerfen.
Aber eben oft auch so, dass es nötig ist, um bestimmte
fortgeschrittene Effekte zu erzielen, dass man dann komplizierte Dinge
tun muss.
Und oft auch so, dass das in der Praxis durchaus anwendbar wäre, wenn
die Programmierer in der Lage wären, das in tatsächlich gutem Code
umzusetzen.
Wenn Sie sich Praktika anschauen, dann habe ich manchmal den Eindruck,
ein Algorithmus, das ist eine Vorschleife.
Ein komplexer Algorithmus, das sind zwei geschachtelte Vorschleifen.
Oder wenn es ein Datenbankmensch ist, eine Datenstruktur ist eine
Relation und ein Algorithmus ist eine SQL-Anfrage.
Eine Datenstruktur, die sich dann ergibt, ist ein Array.
Und wenn es ein Datenbanker ist, sagt er, das ist eine Relation, aber
wenn Sie unten reingucken, wie das implementiert ist, das ist im
Endeffekt wieder ein Array.
Während wir hier komplexierte Pointer-Datenstrukturen haben in der
Algorithmentheorie.
Dann wundert man sich nicht, wenn es da Clashes gibt.
Wenn Sie jetzt einen super komplizierten Algorithmus haben, von dem
Sie aber eigentlich wissen, der funktioniert auch in der Praxis.
Vielleicht sogar, weil Ihre Doktoranden das implementiert haben,
prototypisch und es super gut funktioniert.
Und dann kommt eine Firma und sagt, jawohl, wir wollen das machen,
aber das müssen unsere Absolventen der Fachhochschule Hintertupfingen
machen.
Ich rede explizit nicht über die Fachhochschule Karlsruhe, die hat
durchaus eine gute Ausbildung da.
Dann scheitern die daran regelmäßig.
Wir haben auch schon Masterarbeiter gehabt, die dann keine so gute
Basisausbildung hatten oder bei uns nicht aufgepasst haben, das gibt
es auch, die dann zum Beispiel an der Implementierung von Dijkstra's
Algorithmus scheitern.
Oh, das ist ja ein Graph, das ist ja was Fortgeschrittenes.
Und dann noch eine Datenstruktur Priority Queue obendrauf.
Sowas kann man, also den Eindruck habe ich bei einigen Leuten, auch
hoch bezahlende Industrie wollen.
Oder dann sind eben Datenbankleute und die sagen, kann man das auch
als SQL-Anfrage formulieren.
Also die formulieren das nicht so, aber nach einer halben Stunde
Diskussion merkt man, dass das eigentlich die Frage ist, die sie
haben.
Und dann ist die Antwort leider nein.
Cool.
Ja, also wir haben irgendwie so eine spiegelbildliche Sache, was die
Komplexität angeht, bei Modellen einerseits und den Algorithmen und
Datenstrukturen andererseits.
Und dann aber auch bei den, ich sag mal, Zielen und Maßen.
Was bedeutet überhaupt Erfolg bei der Algorithmenentwicklung?
Da gibt es auch große Unterschiede.
In der Theorie interessieren wir uns meistens für Worst-Case
-Ergebnisse.
Also was ist die schlimmste Eingabe?
Das bedeutet auch, dass die Algorithmen eben entwickelt werden, mit
dem Ziel, die allerschwierigsten Eingaben gut zu behandeln.
Und es macht aber keinen Unterschied, wenn die Laufzeit des
Algorithmus dann für alle Eingaben genauso schlecht ist, wie für die
schlimmsten Eingaben.
Die Praktiker haben aber vielleicht gar keine komplizierten Eingaben,
die haben reale Eingaben, die vielleicht ganz einfach sind und bei
denen diese ausgefuchsten Algorithmen ein totaler Overkill sind, wo
man mit viel einfacheren Verfahren in Größenordnung schneller ist.
Was man dann eigentlich braucht, ist etwas, das irgendwie adaptiv ist
und erkennt, dass die Eingabe einfach ist und es auch nutzt und
natürlich für die komplexen Eingaben trotzdem was Vernünftiges macht.
Das gibt es durchaus.
Und dann ist es so, Effizienz selber wird halt in der Theorie, also
hier Worst Case, da machen sie es sich in gewisser Weise schwer,
während bei konstanten Faktoren, da machen sie es sich leicht, indem
sie sagen, konstante Faktoren werfe ich weg.
Total astronomische Faktoren, wie gesagt.
Werden in der Theorie, in der Praxis, selbst kleine konstante Faktoren
durchaus eine Rolle spielen können.
Also gerade bei wohl untersuchten Problemen ist es dann zum Teil so,
dass man dann in einer guten Konferenz irgendwie so 20% Verbesserungen
sieht, die aber dann durchaus eine Rolle spielen, wenn die halt auf
nicht so wichtigen Anwendungen dann viele tausend oder hunderttausend
Maschinen über viele lange Zeiträume auslasten.
Und wenn ich dann 20% von 10.000 Maschinen einspare, ist das schon ein
paar Millionen.
Spielt also eine Rolle.
So,
wie gehe ich jetzt damit um?
Was wäre eine Methodologie, die da gut ist?
Und was wir uns da überlegt haben, ist erstmal nicht so überraschend.
Wir brauchen natürlich weiter das, was die Theoretiker machen.
Modellierung, Entwurf, Analyse.
Wenig überraschend, muss man daneben eine Implementierung machen und
die auch ausprobieren.
Also ein Experiment.
Vielleicht spannenderer Schritt ist, dass man das Ganze zu einem Kreis
schließt.
Wo man dann sagt, naja, also die Experimente, die ich mache, da lerne
ich was über mein Problem.
Und kann dann neuen Algorithmus entwerfen, den wieder analysieren.
Vielleicht muss ich sogar das Modell ändern, weil ich merke, dass ich
vielleicht zu wenig Eingaben habe und es gibt aber noch andere
Eingaben, die ich zusätzlich berücksichtigen kann, oder keine Ahnung.
Oder ich merke, dass mein Maschinenmodell irgendwie zu vereinfacht
ist, weil ich eben mengenmäßig Cashfalls kriege, die man irgendwie
loswerden muss.
Und das ermöglicht einem dann, mit den Praktikern vernünftig
zusammenzuarbeiten, weil es da sehr viele überlappende Interessen
gibt.
Also die kennen sich natürlich mit Implementierung und Experimenten
aus, vielleicht weniger mit der Analyse und denken vielleicht auch
anders über Modelle nach.
Damit kann man dann Brücken zwischen Theorie und Praxis überwinden.
Und selbst für interdisziplinäre Forschung ist das eigentlich eine
gute Basis, weil die Anwendungsleute verstehen vielleicht viel besser,
welche Eingaben man für die Experimente verwenden sollte, wie man das
zu interpretieren hat, was dabei rauskam, aber haben auch zu der
Modellierung ganz viel zu sagen.
Das heißt, ich habe hier drei Arbeitsgebiete einer interdisziplinären
Anwendung, wo dieser Kreislauf aus Modellierung, Entwurf, Analyse und
Implementierung und experimenteller Evaluierung einem sozusagen das
richtige Framework gibt, den richtigen Rahmen für eine Zusammenarbeit,
wo für jeden Aspekt mehrere Disziplinen zumindest über die gleichen
Dinge nachdenken.
Ich sage leider nicht immer die gleiche Sprache haben, da muss man
dann irgendwie Übersetzungstabellen anfertigen manchmal, was die
Begriffe bedeuten.
Zum Beispiel, wir arbeiten mit den Teilchenphysikern zusammen.
Konkret, wie man Teile, Teilchen in den Detektoren verfolgt.
Und dann sagen wir, oh, wir brauchen einen effizienten Algorithmus.
Und die sagen, jawohl, sie haben genau recht.
Wir brauchen einen effizienten Algorithmus.
Aber leider meinen wir an der Stelle dann zwei verschiedene Dinge, die
beide gleich wichtig sind.
Was wir unter Effizienz verstehen ist, naja, der läuft schnell, ja,
ich brauche nicht auch nochmal eine Milliarde für Rechner, wenn die da
eine Milliarde für den Detektor hingestellt haben.
Was die aber meinen unter Effizienz ist, ich finde die meisten
Teilchen.
Das ist zwar auch wichtig, genauso wichtig, aber das würde man bei uns
nicht unter Effizienz nennen, als Genauigkeit oder sowas.
Oder Recall, keine Ahnung, da muss man nochmal unterscheiden, was
genau Qualität bedeutet.
Wenn man das weiß, ist das kein Problem.
Da muss man halt sagen, die Informatikeffizienz ist jetzt gut.
Oder andere Begriffe, die nicht so mehrdeutig sind.
Genau, also es erleichtert uns auch integrierte, interdisziplinäre
Forschung.
Das ist ein etwas älteres Bild, wo ich aber vielleicht die
Informationsflüsse noch etwas besser darstellen kann.
Und auch die fundamentalen Aspekte dieser Sache.
Das erste ist vielleicht dieser Kreislauf hier.
Der wird eigentlich angetrieben von etwas, was in der
Wissenschaftsphilosophie schon ganz lange Standard ist.
Das ist von Popper die Scientific Method.
Die wissenschaftliche Methode.
Wo der halt sagt, man hat genau diesen Kreislauf aus Theorie und
experimenteller Evaluierung, der in allen Wissenschaften eine wichtige
Rolle spielt.
Im Kern hat man da zwei Dinge.
Einerseits falsifizierbare Hypothesen.
Das heißt, bevor ich ein Experiment mache, muss ich mir eigentlich
überlegen, ja erstens, welches Experiment mache ich und was liefert
mir das Ganze für Informationen.
Und im Allgemeinen kommt aus dem der Modellierung und dem Entwurf dann
eine Erwartung raus, wie gut ist denn das Verfahren jetzt.
Oder was kann das?
Da muss man eine Hypothese aufstellen.
Aha, das Ding ist gut, vor allem für Eingaben von der und der Art.
Ja, sowas.
Und dann macht man ein Experiment und dann kommt raus, jawohl, das ist
ganz gut, aber das Experiment muss so aussehen, dass es zumindest auch
denkbar ist, dass das Gegenteil rauskommt.
Leider funktioniert das Ganze nicht.
Und das ist so ein Minimalkriterium an Wissenschaft.
Es gibt tatsächlich Bereiche in den Wissenschaften, gerade so in den
softeren Wissenschaften wie Psychologie oder sowas, wo es da manchmal
Debatten drüber gibt.
Ist das jetzt überhaupt noch falsifizierbar?
Oder zum Beispiel wird der Psychoanalyse vorgeworfen, dass die
irgendwie alles immer so hindrehen können, dass ihre Theorien stimmen,
dass man da nie irgendwie ein Experiment angeben kann, aha,
Psychoanalyse funktioniert beziehungsweise funktioniert nicht.
Weil es gibt für jedes mögliche Ergebnis eines Experiments eine
Interpretation, die kompatibel ist mit der Theorie der Psychoanalyse.
Und das sollte natürlich in härteren Wissenschaften nicht der Fall
sein.
Ich denke auch, dass es in der Psychologie ganz harte
wissenschaftliche Ergebnisse gibt.
Aber wo da genau die Grenze ist, bin ich jetzt kein Experte dafür.
Das andere ist, wenn man sich hier diesen Theoriepfad anguckt, dann
haben wir bei der Analyse eigentlich deduktives Schließen.
Wir haben einen mathematisch ganz harten Beweis hinter unseren
Leistungsgarantien, die natürlich von irgendwelchen Voraussetzungen
abhängen, aber unter diesen Voraussetzungen ist das Ganze sozusagen
unumstößlich.
Was bei so einer experimentellen Methodik passiert, dass ich eher
induktiv schließe.
Das heißt, ich interpretiere experimentelle Ergebnisse, verfeinere
meine Hypothesen, aber ich kann die Sachen nie beweisen.
Das ist aber wichtig, weil das vielleicht auch erklärt, warum
Theoretiker und Praktiker zwei Sprachen sprechen.
Ein Algorithm und Theoretiker denkt immer in beweisen und deduktiven
Schließen.
Ein Praktiker denkt in so induktiven
Beobachtungszyklen.
Und das muss man natürlich auch irgendwie zusammenbringen.
Das andere ist, dass hier außerhalb dieses Kreises ich habe da jetzt
verschiedene Pfade auch schon eingezeichnet.
Also mal nimmt man das Modell mit in den Kreis rein, mal nicht.
Es stehen da trotzdem noch Sachen daneben, die aber auch wichtig sind.
Algorithmenbibliotheken, wo man dann, wenn man tatsächlich einige
Durchläufe gemacht hat durch diesen Zyklus, dann vielleicht auch mal
Implementierungen sauber konsolidiert und anderen zugänglich macht.
Damit sie in der Vielzahl von Anwendungen oder in zukünftigen
Experimenten auch von anderen Gruppen verwendbar sind.
Wenn diese Leistungsgarantien oder eben reale Eingaben oder Benchmark
Sammlungen, die auch eine Rolle spielen.
Und daneben, also schon außerhalb des Algorithmen Engineering, aber
ganz eng verknüpft mit vielen Aspekten des Algorithmen Engineering,
die Anwendung.
Ich habe das jetzt so ein bisschen draußen gelassen, weil man sich
hier doch oft Dinge anschaut, die unabhängig von Anwendungen sind.
Sehr generische Basic Toolbox Geschichten.
Aber dadurch, dass man hier diesen Kreislauf eingeführt hat, hat man
eine viel engere Verzahnung oder engere Interaktionen mit den
konkreten Anwendungen.
Dann ist hier noch ein Pfeil, den ich ganz interessant finde.
Also natürlich ist es so, dass die Implementierungen was mit den
Anwendungen zu tun haben.
Aber es ist eben nicht einfach so, dass ich dann so eine
experimentelle Implementierung dann ein Kopierbefehl mache und dann
wird das irgendwo Teil eines Anwendungscodes.
Meistens läuft das auf dem Weg entweder über diese
Algorithmenbibliotheken oder ich mache nochmal so ein Application
Engineering, wo ich die Algorithmen zuschneide auf konkrete
Anwendungen.
Also zum Beispiel hat ein Doktorand von mir mal einen Minimum-Spanning
-Tree - Algorithmus im Wesentlichen benutzt, um Bilder zu
segmentieren.
Da wird also aus einem Bild, das aus einem rechteckigen Gitter von
Pixeln besteht, es wird übersetzt in einen Gittergraphen, wo also
jedes Pixel mit seinen Nachbarn verbunden ist.
Darin berechnet man einen minimalen Spannbaum, aber man lässt auch
bestimmte Kanten weg und die Teilbäume, die übrig bleiben, sind dann
halt die Segmente des Bildes, die irgendwie ähnlich sind.
Und Sie sehen schon, man berechnet eigentlich ein bisschen was anderes
und man hat sehr spezielle Graphen.
Und das konnte er dann auch ausnutzen, indem er halt den Graphen dann
tatsächlich als ein Array von Punkten repräsentiert und die Kanten gar
nicht mehr explizit speichert.
Dadurch wird natürlich so eine Implementierung auch nochmal ein
bisschen einfacher, aber vor allem auch schneller.
Gibt es noch Fragen zur Methodik des Algorithmen Engineering?
Ich werde da gleich auf die einzelnen Aspekte nochmal ein bisschen
eingehen.
Aber der Überblick ist jetzt vielleicht auch wichtig.
Gut, dann vielleicht noch einen Hinweis auf unsere Folien.
Wenn da so eine Chili eingeblendet ist, dann ist das sozusagen
Zusatzmaterial, das für die Prüfung nicht relevant ist, auch wenn es
manchmal ein bisschen fortgeschrittener ist, das ich aber wichtig
halte, um so ein bisschen Blick über den Tellerrand zu geben.
Also hier zum Beispiel mal eine historische Sichtweise.
Was ist eigentlich dieser Begriff Algorithmen Engineering?
Wo kommt der her?
Also ich habe jetzt mal den Beginn der Algorithmikforschung auf das
Jahr 1843 gesetzt.
Das hat was mit der Dame zu tun.
Weiß jemand, wer das ist?
Ja.
Genau, Ada Lovelace.
Das war sozusagen die erste Programmiererin.
Sie hat nur das Pech gehabt, dass der Charles Babbage das nicht auf
die Reihe gekriegt hat, den Computer auch wirklich zu bauen, den er
entworfen hat.
Wir wissen heute, dass der funktioniert hätte, aber mit den damaligen
mechanischen Möglichkeiten war das halt nicht so einfach, das Ding
tatsächlich zum Laufen zu bringen.
Und sie hat dann aber schon wirklich was drüber aufgeschrieben, wie
man mit dem Ding rechnen kann, Algorithmen dafür entwickeln.
Finde ich ganz spannend.
Man muss natürlich dazusagen, dass es Algorithmen schon viel länger
gibt, weil es gibt
ja auch, man kann da verschiedene Interpretationen haben, aber
zumindest Menschen können Algorithmen ja auch ausführen.
Insbesondere wenn es ums Rechnen geht.
Lernen wir ja in der Schule alle Algorithmen, die sind natürlich noch
viel älter als 1843.
Es gibt auch wichtige Algorithmen, die so ein bisschen abstrakter
sind, aus der Zahlentheorie zum Beispiel, die bis auf die alten
Griechen zumindest zurückgehen.
Wir wissen auch, dass die Chinesen und die Sumerer so ein recht
komplexes Rechenverfahren beherrscht haben.
Aber ich habe jetzt mal den Anfangspunkt an der Stelle gesetzt.
So richtig los ging es natürlich erst, als es dann echte Computer gab.
Im Zweiten Weltkrieg war das noch so ein bisschen sehr spezialisiert,
auf bestimmte Anwendungen wie Kurzknacken oder sowas.
In den 50er und 60er Jahren ging das dann erst so langsam los, aber
die Algorithmenforschung als solche war noch in den Kinderschuhen.
Und die Methodiken, mit denen dann an Algorithmen herangegangen wurde,
waren sehr unterschiedlich, einfach weil keiner von denen Informatik
studiert hat.
Das waren Mathematiker oder Elektrotechniker, vielleicht auch
Maschinenbauer, die dann natürlich die Methodiken, mit denen sie groß
geworden sind, verwendet haben.
Und es war eigentlich so ein wilder Mix aus verschiedenen
Herangehensweisen.
Es gab auch schon theoretische Abhandlungen, oft wurde das Ganze aber
sehr hemdsärmelig gemacht.
Und es war dann, glaube ich, das Lehrbuch von Donald Knuth, der die
Algorithmik im Besonderen dann in diese Theorieecke gestellt hat.
Das klingt jetzt so negativ, aber ich finde, aus der damaligen Sicht,
das ging dann Ende der 60er in den 70ern richtig los, war das
vielleicht zu dem Zeitpunkt schon der richtige Weg, zu sagen, wir
gucken uns jetzt erstmal an, wie man mathematisch rigoros Algorithmen
entwerfen und untersuchen kann.
Vor allem, weil wenn man dann die Bücher von Knuth liest, das ist zwar
sehr viel über Beweise und sowas, aber am Ende steht da
Maschinenbefehle, wie man das tatsächlich ausführen kann.
Das heißt, er hat die Brücke eigentlich dann auch schon bis zum
gewissen Grade geschlagen, aber die Auswirkungen auf die Informatik
war eher, dass dann so eine Papier- und Bleistift-Algorithmik
entstand.
Also über zwei Jahrzehnte hinweg war das eigentlich fast
ausschließlich Papier und Bleistift.
In den Anwendungsdisziplinen oder Anwendungsgebieten ging das
natürlich dann ein bisschen anders weiter.
Aber innerhalb der Algorithmus gab es dann nur einzelne Figuren, wie
David Johnson oder John Bentley, die dann mal gewagt haben, auch
Experimente zu machen.
Das ging so weit, dass Theoretiker, die dann auch Experimente gemacht
haben, das galt als komplett unschicklich, das in den Papieren zu
erwähnen.
Diese Experimente waren dann oft auch eben, um ein Gefühl dafür zu
kriegen, was da passiert, weil das ist so eine Art Scaffolding,
Gerüstbau um dieses schöne Theoriegebäude herum.
Und natürlich am Ende reißt man die Gerüste wieder ab.
Das war so die Sichtweise.
Aber dass man irgendwie da was drüber lernen kann, über das Problem,
in dem man auch über diese Experimente explizit schreibt, wurde damals
überhaupt nicht wahrgenommen.
Und dann, ich habe das vor 10 Jahren das erste Mal probiert, ich weiß
nicht, ob das immer noch so ist, wenn Sie jetzt in Google Scholar oder
sowas nach dem Begriff Algorithm Engineering in Anführungszeichen
suchen.
Dann ist das älteste Papier, das Sie da finden, von dem verstorbenen
Kollegen Thomas Beth hier in Karlsruhe.
Der da allerdings ein bisschen was anderes darunter verstanden hat,
der war auch jetzt nicht in der Kernalgorithmics, sondern so eher
Computer Algebra die Richtung.
Aber im alten KIT Selbstbewusstsein, wir haben es erfunden, behaupten.
Was dazu passt, ist, dass Ende der 80er Jahre die Fakultät für
Informatik tatsächlich ein Konzept entwickelt hat, wie man die
Informatik stärker als Ingenieurwissenschaft verstehen kann.
Es gab dann insbesondere auch eine Vorlesung, die hieß
Algorithmentechnik und die ist ganz konkret der Vorgänger dieser
Algorithmen 2 Vorlesung.
Auch inhaltlich sehr nah dran.
Es war dann eben tatsächlich so, dass in der Praxis diese
Algorithmentechnik Vorlesung eher Algorithmentheorie war, aus den
Gründen, die ich am Anfang genannt habe.
Aber die Absicht war trotzdem in diesem Curriculum als Ganzes ganz
klar da, diese ingenieurwissenschaftliche Sichtweise auszubauen.
Und sicherlich bis zum gewissen Grade auch in der Algorithmics.
Naja gut, und wenn ich Algorithmentechnik ins Englische übersetze, ist
eine sinnvolle Übersetzung Algorithm Engineering.
Also genauso wie Elektrotechnik in Electrical Engineering übersetzt
werden kann, kann ich doch Algorithmentechnik als Algorithm
Engineering übersetzen.
Nochmal, wir haben es erfunden.
Wenn ich aber jetzt auf die internationale Perzeption eingehe, muss
ich da ein bisschen anders reden, weil die Algorithmik in Karlsruhe zu
dem Zeitpunkt genau durch den Kollegen B definiert war und der eben
eigentlich auch ein bisschen was anderes gemacht hat, war eigentlich
Karlsruhe da so ein bisschen Backwater.
Also wo das dann eher passiert ist, ist 200 Kilometer weiter in
Saarbrücken.
Da hat Kurt Mehlhorn halt diese Library of Efficient Data Types und
Algorithms gebaut, zusammen mit Stephan Neher.
Ab Ende der 80er Jahre.
Wo die sich halt wirklich hingesetzt haben und einen großen Teil der
Basis des Algorithmen in eine sehr schöne C++ Algorithmen Bibliothek
umgesetzt haben.
Da gibt es dann so ein tausendseitiges Buch darüber, das habe ich oben
erwähnt.
Wo die dann mit der Methodik des Literate Programming wirklich Code
-Stücke und die algorithmische Erklärung und die Experimente sehr
schön ineinander verweben.
Also durchaus, wenn sie sich die Zeit nehmen, eine sehr schöne
Lektüre.
Also das war Ende der 80er.
Erst Ende der 90er sind dann eigentlich die Konferenzen entstanden.
Es gab dann einen relativ kleinen Workshop an Algorithm Engineering in
Europa, der aber dann es geschafft hat, immerhin in den...
in die die Europäische Algorithmenkonferenz hat es einen Track
aufgenommen zu werden, der aber immer noch so ein bisschen weniger
bespielt wird.
Bei den Amerikanern war das ein bisschen komisch.
Es gab in 98 einen Workshop on Algorithm and Experimentation oder
sowas in Italien von den Algorithm Engineering Pionieren dort, der
aber dann tatsächlich zu der amerikanischen Algorithm Engineering
Konferenz Allenex geworden ist.
Und da gibt es auch seit Jahrzehnten die Bestrebung, das sozusagen als
Track der amerikanischen Algorithmenkonferenz zu nehmen, was aber die
Theoretiker bisher sehr erfolgreich verhindert haben.
Also da gibt es immer noch so ein bisschen Berührungsängste.
Also seit Ende der 90er Jahre ist eigentlich dieser Begriff in der
Welt.
Es gab da auch ein wichtiges US-Policy-Paper, wo dann wirklich so
Leute wie Aho, wieder David Johnson, Richard Karp und andere, die halt
wirklich die Hauptnahmen in der Informatik aus den 80er Jahren sind,
die ganz wichtige Bücher geschrieben haben und so der US-Regierung
gesagt haben, hier so muss eigentlich die Informatik Entwicklung
weitergehen.
Fragen dazu?
Okay, dann sage ich nochmal ein bisschen mehr zu den einzelnen
Aspekten von Algorithm Engineering.
Ich habe gesagt, es gibt bei den Modellen große Unterschiede zwischen
Theorie und Praxis.
Jetzt ist das so, die auf den ersten Blick naheliegende Antwort ist,
jawohl, dann machen wir halt komplexere Modelle.
Die werden dann ja auch genauer sein.
Das kann man machen.
Also zum Beispiel ein Modell mit vier oder fünf Speicher-Hierarchie
-Ebenen wäre vielleicht angemessener für die Analyse von modernen
Algorithmen, weil das ist also diese Cache-Hierarchie.
Und wenn man schon dabei ist, würde man dann halt genau zählen, wie
viele Cache-Falls man hat unter Berücksichtigung der konkreten
Ersetzungsstrategie von den Hardware-Caches.
Als nächstes müsste man dann irgendwie die, weiß nicht, so und so
vielstufige Pipeline des so und so Prozessors dazunehmen und müsste
aber für jeden anderen Prozessor dann jeweils eine andere konkrete
Pipeline sich angucken.
Das heißt, ich müsste dann für jede Maschine eine eigene Analyse
meines Algorithmus machen.
Die Laufzeit, die dann rauskäme, wäre wahrscheinlich irgendwie eine
Formel, die über drei Seiten geht und von 50 Parametern abhängt.
Also, was weiß ich, die Zeit, die ich brauche, um eine Cache-Line
reinzuholen, wenn ich die Cache-Line, die davor stand, in weniger als
500 Nanosekunden vorher bereits geholt habe.
Weil das ein Unterschied ist, als wenn die komplett frisch ist.
Aller möglicher Scheiß an Parametern müsste.
Wahrscheinlich sogar, je genauer man wird, haben sie irgendwie in so
einem Intel-Prozessor Tausende so Parameter heutzutage.
Also es wären beliebig lange Formeln, von denen sie die Parameter aber
leider nicht kennen.
Das sind nämlich Betriebsgeheimnisse.
Und wahrscheinlich wäre die Analyse eines fünfzeiligen
Sortieralgorithmus, der quadratische Komplexität hat, eine
Doktorarbeit.
Und alles andere ist nicht handelbar.
Also, Sie merken schon, wo ich hin will.
Es hilft nicht, die Modelle komplexer und genauer zu machen, weil wir
sie nicht mehr handhaben können.
Wir können keine Algorithmen mehr analysieren und wenn wir es können,
versteht niemand das Ergebnis.
Das ist ein bisschen anders, wenn man das für Autotuning zum Beispiel
verwenden würde.
Dann könnte der Computer automatisch mit diesen Dingen arbeiten.
Das ist ein interessantes Forschungsgebiet, das aber noch keine
durchschlagenden Erfolge erzielt hat.
Also, was wir stattdessen brauchen, ist ein Modell, das ganz
vorsichtig die Modelle genauer macht, sodass man sie immer noch
handhaben kann und eine gewisse Vorhersage Mächtigkeit kriegt.
Aha, ein Algorithmus, der in diesem vorsichtig verallgemeinerten
Modell gut ist, der wird auch auf realen Maschinen gut sein.
Zum Beispiel bei Speicherhierarchien, habe ich ja gesagt, von Neumann
-Maschine ist halt dadurch ausgezeichnet, dass der Prozessor irgendwie
direkt auf den Speicher zugreift und alle Speicherstellen sind gleich.
Eine Verallgemeinerung, die super erfolgreich ist, ist das External
Memory -Modell.
Da habe ich hier im Prinzip wieder diese von Neumann-Maschine, aber
dieser uniforme schnelle Speicher hat eine begrenzte Kapazität.
Das ist dann ein Tuning-Parameter oder Maschinen-Parameter M, Cache
-Kapazität.
Und dann gibt es einen großen Speicher, zum Beispiel eine Festplatte
oder eine SSD oder vielleicht ist das hier ein Cache-Level und das ist
der Hauptspeicher.
Die Interpretationen sind vielfältig, aber sie betrachten halt nur
zwei Speicherhierarchie-Ebenen und damit das Ganze irgendwie
interessant wird und auch realistisch, berücksichtigen sie außerdem,
dass der Zugriff auf diesen langsamen Speicher normalerweise
blockweise erfolgt.
Das heißt, sie bringen nicht ein Maschinen-Wort in den schnellen
Speicher, sondern gleich mehrere.
Also eine Cache-Line oder ein Disk-Block oder sowas.
Es ist natürlich unrealistisch, dass sie hier eine feste Blockgröße
haben.
Die Realität ist komplexer.
Trotzdem, wenn sie die Blockgröße irgendwie so wählen, dass die
vernünftig ist, sind sie irgendwie, so kann man argumentieren, Faktor
2 weg von der Wahrheit.
Während wenn sie das hier nehmen, können sie in einigen Fällen Faktor
100.000 weg sein von der Wahrheit.
Das ist der Punkt hier.
Und natürlich brauchen wir auch noch andere Modelle, aber die müssen
immer hinreichend einfach bleiben.
Fragen dazu?
Dann Algorithmenentwurf.
Worauf muss ich denn da achten?
Naja, also im ersten Blick ist es trivial.
Wir brauchen Algorithmen, die in der Praxis gut funktionieren.
Was bedeutet das?
Die müssen einfach sein.
Habe ich schon gesagt, es gibt ganz komplexe Algorithmen, die als
nicht implementierbar gelten.
Das Bild hier zeigt
die Datenflussprinzipien der meisten fortgeschrittenen
Sortieralgorithmen, die eigentlich trotzdem auf zwei ganz einfache
Prinzipien zurückführen lassen.
Dass ich nämlich entweder irgendwie sortierte Teilfolgen habe und die
zu einer großen sortierten Folge zusammen mische oder umgekehrt eine
nicht sortierte Folge habe und die in Größenkategorien klassifiziere.
Und dann muss man irgendwie rekursiv weiter vorgehen.
Aber das ist immer noch so einfach, dass man damit umgehen kann.
Es gibt eine Ausnahme, wann ich auch mit komplexen Algorithmen
arbeiten kann.
Nämlich dann, wenn ich sie nicht selber implementieren muss.
Ich mache Wiederverwendung existierender Algorithmen in Bibliotheken.
Und da gibt es eben in einigen Dingen, die sehr gut erforscht sind,
durchaus komplexe Algorithmen, die trotzdem jemand implementiert hat
mit viel Aufwand, weil man sie an vielen Stellen verwenden kann.
Da kann ich auch wieder
sortieren.
Als Beispiel nehmen meine Doktoranden Michael Axmann und Sascha Witt
haben letztes Jahr es tatsächlich geschafft, einen Sortieralgorithmus
zu implementieren, der auf einer sequentiellen Maschine irgendwie
immer noch 20% schneller ist als die Standardbibliotheksachen.
Und der vor allem auf dem Parallelrechner mehr als ein Faktor 2
schneller ist als alle Konkurrenzverfahren.
Und dabei sogar noch ein wichtiges Feature von der Library hat,
nämlich keinen zusätzlichen Platz braucht.
Und dieser Algorithmus ist durchaus etwas komplexer.
Das sind irgendwie ein paar tausend Zeilen Code, die jetzt vielleicht
auch dem noch im Weg stehen, das Ding dann tatsächlich in die
Standardbibliotheken zu überführen.
Weil es doch nicht ganz auszuschließen ist, dass der noch ein paar
Bugs enthält.
Aber das ist jetzt schon ein Code, den wir veröffentlicht haben und
den man für viele Anwendungen durchaus einsetzen will, wenn es da um
Performance geht.
Aber ich würde Ihnen nicht empfehlen, den nachzuimplementieren.
Konstante Faktoren spielen eine Rolle, was in der Theorie halt auch
nicht der Fall ist.
Und ich muss halt einfache Eingaben auch berücksichtigen.
Und das sind eben alles ziemlich orthogonale Aspekte, die man nicht
aus dem Auge verlieren sollte, die vor allem einen Unterschied zur
Algorithmentheorie darstellen.
Analyse.
Das ist zwar eigentlich so das Haus- und Hofgebiet der
Algorithmentheorie, aber auch da muss man andere Dinge tun, wenn man
Algorithmen -Engineering betreibt.
Insbesondere kümmert man sich stärker um die konstanten Faktoren.
Zum Beispiel bei Sortieralgorithmen ist das auch sehr intensiv
passiert, dass Leute sich bis ins Detail angeguckt haben, was sind die
konstanten Faktoren für Kenngrößen wie Anzahlelementvergleiche,
Anzahlspeicherzugriffe und so weiter.
Aber wir wollen auch nicht immer nur Worst-Case machen, da gibt es
verschiedene Analysetechniken, zum Beispiel Average-Case-Analyse oder
sowas, die man da anschaut.
Und eine umgedrehte Sache ist, es gibt gerade aus den
Anwendungsgebieten Algorithmen, die sehr erfolgreich sind, die schon
lange verwendet wurden, die aber noch nie jemand analysiert hat.
Das ist aber auch eine wichtige Herausforderung für die Theoretiker,
das vielleicht mal zu tun.
Oder eben Algorithmen zu entwickeln, die man analysieren kann, die
aber in der Praxis genauso gut sind, wie das, was man da seit langem
benutzt.
Man kann nicht einfach sagen, oh, das ist ja komisch, da weiß ja
keiner, wie die funktionieren.
Hier ist ein anderes Verfahren, da kann ich was beweisen, aber die
Praktiker sagen, ja, das ist ja schön, aber das funktioniert auf
unseren Eingaben nicht.
Zu schlecht, zu langsam.
Da muss man sich dem irgendwie stellen.
Also irgendwie dann eine Synthese vielleicht aus den existierenden
Algorithmen und beweisbaren Verfahren.
Implementierung.
Da war das eben tatsächlich so, dass selbst Algorithm Engineering
Pioniere wie Kurt Mellorn am Anfang gesagt hat, das ist ja trivial.
Das ist so in seinen Invited Talks immer das Beispiel, das er bringt.
Das hat er tatsächlich Leuten gesagt.
So nach der Devise, naja, für reine Implementierungsaufgaben nehmen
wir unsere nicht ganz so guten Masterarbeiter oder damals
Diplomarbeiter.
Dann hat er aber lernen müssen auf die harte Tour durch seine
Lederbibliothek, dass er dann eben plötzlich Backreports bekam von
seinen Implementierungen.
So guck mal, das da funktioniert nicht und das auch nicht.
Das war dann sogar so, das waren dann nicht die Sachen von Kurt
Mellorn, dass es da berühmte Algorithmen gab für wichtige
graphentheoretische Probleme, wo dann die Leute, die das das erste Mal
implementiert haben, gesagt haben, ja tut mir leid, der Algorithmus
stimmt nicht, ihr habt irgendwie zwei Fälle übersehen oder sowas.
Das heißt Implementierung ist eben doch nicht so einfach und durchaus
eine sehr anspruchsvolle Tätigkeit und ich denke einer der Gründe ist
die Semantic Gaps, die dabei auftreten.
Also die semantischen Lücken zwischen einem abstrakten Algorithmus auf
der einen Seite, den ich sehr high level formulieren kann.
Hier ist zum Beispiel so ein Bild, das müssen Sie jetzt nicht im
Detail verstehen, da geht es eigentlich um einen Sortieralgorithmus,
der mit parallelen Platten arbeiten kann, also externe Memory mit
parallelen Platten und die Grundidee von dem Algorithmus erklärt man
im Wesentlichen, indem man so ein Bild malt und sagt, okay, das sind
die Datenströme.
Und dann gibt es ein bisschen Text, der sagt, okay, das ist jetzt die
Policy, in welchem Fall ich jetzt Daten zwischen den verschiedenen
Datenpuffern da hin und her schiebe.
Das kann man dann auf drei, vier Seiten englischen Text und Bildern
beschreiben.
Und ein paar Formeln da drin.
Die C++ Implementierung sind über 10.000 Zeilen Code.
Da ist sicherlich ein gewisser Gap dazwischen.
Und was die Hardware daraus macht, der Compiler, die Prozessor
-Hardware, Betriebssysteme, die ja auch noch irgendwie mitreden, wenn
es darum geht, was die Platte tut, oder der Plattencontroller und
sonstige Dinge.
Das ist nochmal eine ganz andere Geschichte.
Also selbst wenn ich den C++ Code mir anschaue, verstehe ich noch
nicht, was da wirklich passiert.
Und deshalb ist das eine sehr anspruchsvolle Aufgabe, wenn man als
Eingabe einen abstrakten Algorithmus kriegt, sozusagen, oder als
Aufgabenstellung.
Und das Ziel ist, dass es auf einer realen Hardware effizient läuft,
dann auf so einer Zwischenebene irgendwas hinzuschreiben, was das dann
auch tut.
Das ist eine sehr anspruchsvolle Aufgabe und kann auch
wissenschaftlich interessant sein.
So, Experimente ist klar, dass die wichtig sind.
Sie können insbesondere aus der Theoretikersicht auch eine Analyse
ersetzen.
Also oft ist es ja so, ein Algorithmus ist zwar empirisch gut, aber er
ist zu komplex, um ihn zu analysieren.
Das heißt aber nicht, dass man ihn dann aufgeben sollte, wenn man
keinen guten, theoretisch beweisbaren Algorithmus kennt.
Ich habe sehr viel Ausgabedaten.
Ich glaube, in den anderen Wissenschaften ändert sich die Sichtweise
gerade ein bisschen durch Big Data und so.
Aber wenn Sie sich ältere Bücher anschauen, zum Beispiel auch über die
Aufbereitung von experimentellen Daten und so, dann ist der Tenor so
ein bisschen, oh, die Daten sind unser großer Schatz.
Wir haben viel zu wenig davon.
Und die Aufgabe der Evaluierung besteht im Prinzip darin, die von
immer anderen Seiten anzuschauen, aufzubereiten, um dann was zu lernen
über die wenigen Daten, die man hat.
Und das wird in den Anwendungswissenschaften auch weiter so bleiben,
in bestimmten Bereichen, weil es zum Beispiel eben nur ganz wenig
Daten gibt und es sehr teuer ist, neue zu besorgen.
Zum Beispiel, wenn Sie das aus Benutzerumfragen, irgendwelche Daten
benutzen wollen.
Oder Sie vielleicht für die Aufklärung bestimmter Molekülstrukturen
irgendwie eine super teure Maschine irgendwie tagelang laufen lassen
müssen.
Dann wissen Sie nicht so viel.
Aber jedenfalls in der Algorithmik war das schon immer anders.
Wir können eigentlich so viel Ausgabedaten produzieren, wie wir
wollen.
Wir müssen uns nur überlegen, welche.
Also es kommt darauf an, wie unser experimentelles Setup ist.
Und das zu entwerfen, ist eigentlich eine Aufgabe, die eigentlich gar
nicht so weit weg ist vom Software Engineering.
Wir müssen halt irgendwie modellieren, was unsere Problemstellung ist,
was unsere Möglichkeiten sind an Experimenten und dann
Entwurfsentscheidungen treffen, welche Daten wir produzieren und
welche wir nicht produzieren, weil das zu aufwendig wäre.
Und das andere Ding ist, was leider in der Informatik immer noch
missachtet wird, wo andere Wissenschaftler ein bisschen weiter sind,
ist Reproduzierbarkeit.
Das ist eine andere von diesen fundamentalen Dingen aus der
wissenschaftlichen Methode.
Wenn ich Experimente mache, müssen andere die in irgendeiner Weise
reproduzieren können.
Das heißt, sie müssen die gleichen Experimente oder ähnliche
Experimente durchführen können und dann hoffentlich die Ergebnisse
bestätigen und wenn nicht, Ärger sozusagen.
Und bei ganz wichtigen Experimenten ist es eben auch so, bevor die
nicht reproduziert wurden, ist die Vertrauenswürdigkeit vielleicht
auch nicht so hoch.
Und das Ganze muss mindestens zehn Jahre lang möglich sein nach den
Richtlinien der DFG zum Beispiel.
Das heißt, wir müssen auch unsere Daten aufheben, archivieren,
dokumentieren, so ein bisschen wie das früher mit Laborbüchern in den
Anwendungswissenschaften war.
Da steckt also auch noch einiges an Methodologie dahinter.
Da werde ich auch in der nächsten Vorlesung noch ein bisschen weiter
drauf eingehen.
Auch so ein bisschen im Vorgriff auf die praktischen Arbeiten, die sie
vielleicht in der Masterarbeit dann tun müssen.
Algorithmen und Bibliotheken sind auch eine Herausforderung.
Zum einen, weil sie halt eine Art von Software-Engineering sind, die
ich besonders anspruchsvoll finde, weil ich kenne meine Anwendung ja
noch gar nicht.
Das ist ja fast die Definition von Algorithmen und Bibliotheken.
Ich habe ein fundamentales algorithmisches Problem, zum Beispiel eine
Prioritätsliste in Datenstruktur.
Aber ich weiß gar nicht, was die Anwendungen sind.
Ich weiß nicht, was die für typische Operationenfolgen haben,
überhaupt was das für ein Datentyp ist, der da verglichen wird, wie
viele Daten ich habe.
Ich muss aber meine Bibliothek so entwerfen, dass das idealerweise
unabhängig davon immer funktioniert.
Wenn Sie sich aber Software-Engineering-Methodologien anschauen, dann
sind die eben auch meistens so, dass sie so tun, als wären alle
Informationen schon vorhanden.
Also die postulieren eine komplette Spezifikation des Problems und
dann kann ich anfangen, meine Software zu entwerfen.
Aber bei Algorithmen und Bibliotheken muss ich sagen, sorry, die
Spezifikation ist an der und der und der Stelle weiß ich nichts.
Weil es soll ja offen sein für viele.
Und dann kommt dazu, dass es auch keine klare Zielfunktion gibt.
Ich möchte natürlich hohe Leistung haben, damit das genauso gut ist
wie selbstgeschriebener, anwendungsspezifischer Code von einem
Experten, idealerweise.
Sie soll aber ganz allgemein anwendbar sein.
Und die muss aber gleichzeitig so einfach sein, dass jeder es auch gut
benutzen kann.
Also insbesondere die API muss einfach sein, also das Interface.
Aber eigentlich muss auch die Implementierung selber einfach sein,
damit Leute, wenn dann doch mal ein Fehler auftritt oder doch mal man
das außerhalb der eigentlichen ursprünglichen Spezifikation verwenden
will, man den Code auch ändern kann.
Und natürlich widersprechen sich die drei Dinge.
Also ich habe so ein Dreieck aus Anforderungen, die ich im Allgemeinen
nicht alle gleichzeitig erfüllen kann.
Und dann muss ich halt ein Design machen, das einen guten Kompromiss
darstellt.
Das geht dann noch weiter, wenn ich das wirklich allgemein einsetzen
will, muss ich das auch standardisieren.
Das ist jetzt zunehmend so, gerade bei Programmiersprachen wie Java
oder C++, dass mehr und mehr Algorithmen in die Standardbibliotheken
einfließen.
Und wenn ich dann will, dass Leute die verwenden, dann muss ich mich
aber auch in die Standardkomitees setzen und da mitarbeiten.
Das ist zum Beispiel was, was wir in unserer Arbeitsgruppe bisher noch
nicht geschafft haben.
Wo wir aber zunehmend die Notwendigkeit sehen, das zu machen.
Weil wir halt sehen, dass da in vielen Standardbibliotheken, auch für
mathematische Software, extrem veraltete Algorithmen eingesetzt
werden, die um Größenordnungen langsamer sind zum Teil als der Stand
der Technik.
Und da müsste man eigentlich dann, gerade wenn das Open Source ist,
müsste es ja möglich sein, unsere besseren Implementierungen da
einzubringen.
Also wir haben da eine erste Erfahrung, die Doktorarbeit von Johannes
Singler, der hat tatsächlich die C++ Standard Template Library
parallelisiert und in den GCC Compiler eingebracht.
Aber das ist dann auch so ein optionales Feature, das im Moment nicht
gepflegt wird.
Man muss eigentlich dafür sorgen, dass das die Community übernimmt,
das dann an die modernen Entwicklungen von C++ anzupassen und
natürlich auch weiterzuentwickeln.
Ja, es gibt noch einen anderen Aspekt.
Ich habe gesagt, es könnte auch mal ein Fehler sein, den man verändern
muss.
Aber wenn Sie sich angucken, warum Wiederverwendung dann manchmal doch
nicht stattfindet, stellen Sie fest, dass da dieser Not-Invented-Here
-Effekt eine Rolle spielt.
Also Programmierer finden es eigentlich cool, die spannenden Teile
eines Algorithmus selber zu implementieren und sind außerdem fest
davon überzeugt, dass sie das besser können als die blöden Library
-Entwickler.
Und wenn das Management sie dann zwingt, trotzdem eine Library
einzusetzen, dann ist der Reflex beim ersten auftretenden Fehler, oh,
das ist die Library, die ist Schrott, die schmeiße ich jetzt weg.
Auch wenn in 90% der Fälle es dann nicht die Library war, sondern sie
den Fehler im eigenen Code gemacht haben oder irgendwo das Interface
falsch verstanden hat.
Eine Möglichkeit, dem entgegenzutreten, ist die Software so zu
programmieren, dass entweder beweisbar keine Fehler macht durch eine
formale Verifikation, das wäre so der Gold-Standard, oder, wenn einem
das schwierig ist, Result-Checking macht, wo dann sozusagen das
berechnete Ergebnis überprüft wird und wenn das dann doch falsch ist,
dann wird eben eine Ausnahme geworfen.
Und wenn das aber nicht der Fall ist, dann kann keiner mehr sagen, das
ist ja Schrott, was ihr da rechnet.
Der kann dann höchstens noch sagen, euer Checker ist Schrott, aber
wenn das dann ein Fünfzeiler ist, der leicht verständlich ist, wird
vielleicht auch der härteste Programmierer irgendwann sagen, äh,
vielleicht ist der Fehler doch woanders.
Genau, diese Bilder hier zeigen die Architektur von zwei von unseren
Algorithmen -Bibliotheken, die beide die C++ Standard Template Library
implementieren.
Und das kann man auch wieder als Sortierbeispiel nennen.
Wo läuft denn eigentlich ein Sortieralgorithmus in so einer Library?
Also unsere External Memory Library, STXXL, also Standard Template
Library for XXL Datasets, heißt die.
Die basiert natürlich auf dem Betriebssystem, aber standarderweise hat
der Roman Dementschew irgendwie nur ein paar Stunden gebraucht, um das
auf die meisten anderen Betriebssysteme zu portieren.
Nur bei Windows hat es ein bisschen länger gedauert.
Weil es hier so eine Compatibility Layer gibt, die nur ein paar
hundert Zeilen Code hat.
Und das ist das Einzige, was nicht im Teil des C++ Standard war.
Und das musste man dann halt re-implementieren für jede Library.
Dann gibt es so eine Block Management Library, die dafür sorgt, wie
Daten durch die Gegend geschoben werden, auf welche Platten die
liegen, wie man die caches usw.
Und dann gibt es eben eine Layer, die die konkreten Algorithmen
implementiert.
Unter anderem eben auch die Sortierfunktionen in der Standard Template
Library.
Und eine andere daneben stehende Layer, die die Funktionalität so ein
bisschen erweitert.
Und so ähnlich funktioniert das dann auch in unserer Parallelen
-Library.
Lebenstanzen...
Da sag ich jetzt mal was dazu.
Das ist jetzt, glaube ich, ein ordentlicher Ort aufzuhören.
Also ich werde dann nochmal eine kurze Summary machen von Algorithm
Engineering und dann ein bisschen mehr auf experimentelle Methodik
eingehen.
Das wird aber nicht die ganze Vorlesung dauern, sondern dann wird es
endlich etwas konkreter und ich werde etwas sagen über adressierbare
Prioritäten.
Vielen Dank.