Ja, guten Tag.
Wir hatten beim letzten Mal das recht kurze Kapitel über externe
Algorithmen angefangen.
Damit werden wir auch heute dann fertig.
Genau, wir hatten uns halt das ganz einfache Modell angeschaut.
Einen Prozessor mit einem schnellen Speicher begrenzter Größe und
einem großen Speicher, den man nur blockweise zugreift, in Blöcken der
Größe b.
Und dann kommt halt zur Bestimmung der Anzahl Instruktionen des
Prozessors dazu, dass man die Anzahl Block Zugriff zählt oder die IO
-Operation, wie gesagt.
Wir hatten ein ganz einfaches Beispiel für einen externen Stapel, wo
dann die amortisierte Komplexität 1 durch b IOs pro Operation war.
Beim Sortieren hatten wir diese
Formel Sort N kennengelernt.
Zweimal eine Gabegröße durch b IOs mal ein Pass für eine Run-Formation
und Log Basis M durch b, N durch M aufgerundet.
Pass
ist dann eine Größe, die in ganz vielen externen Memory-Algorithmen
auftritt.
Was kann man noch zu Sortieren erzählen?
Was ganz spannend ist, es gibt eine untere Schranke für Sortieren.
Also man kann dann auch zeigen, dass man eigentlich nicht schneller
sortieren kann oder mit weniger IOs.
Also die Schranke ist eigentlich N durch b mal 1 plus Log blablabla.
Die 2 ist ein offenes Problem, den konstanten Faktor auch zu zeigen.
Allerdings wenn man sich diesen Beweis anschaut, die zeigen, ich weiß
es nicht mehr genau, dass die Anzahl Lese- oder die Anzahl Schreib
-Operationen, die man macht, N durch b mal 1 plus Log blablabla ist.
Wenn man dann zusätzlich annimmt, dass man irgendwie genauso viel
liest, wie man schreibt, hat man den Faktor 2 schon im Griff.
Das ist nicht ganz so offensichtlich, weil man kann tatsächlich
sortieren mit Schreibkomplexität N durch b und dann hat man aber N
durch m Laser-Operationen.
Also was man einfach machen kann, ist man liest die gesamte Eingabe
durch und hat eine Priority Queue, in der man sich die m kleinsten
Elemente merkt.
Die schreibt man raus und dann liest man die ganze Eingabe nochmal
durch, merkt sich die nächsten m kleinsten Elemente und so weiter.
Damit kann man dann offenbar die Anzahl Schreib-Operationen massiv
reduzieren, aber zu gewaltigen Kosten.
Also wie man jetzt wirklich zeigt, dass die Summe von Lese- und
Schreib -Operationen vielleicht dieses 2 N durch b ist, ist mir nicht
so klar.
Da könnte sich noch mal jemand austoben, theoretisch.
Aber immerhin ist es spannend, dass man hier eine nicht-triviale
untere Schranke zeigen kann für die IO-Komplexität.
Und aus dieser Sortierschranke folgen dann auch ganz viele untere
Schranken für andere externe Memory-Probleme durch entsprechende
Reduktionen.
Eine ganz interessante Verallgemeinerung ist, wenn man mehr als eine
Platte hat,
dann kann man einfach den mal so schnell sortieren.
Das klingt jetzt auf den ersten Blick trivial, ist allerdings so, dass
wenn man einen trivialen Algorithmus verwendet für Parallel-Disk
-Sorting, dann landet so ein D hier.
Das heißt, da steht dann M durch in Klammern D mal b.
Das heißt, die Basis des Logarithmuses wird viel kleiner dadurch.
Und wie man das dann wieder los wird, ist relativ komplex.
Was dabei ist, dass die oberen Schranken, die man da kennt, das sind
randomisierte Algorithmen.
Deterministische Algorithmen erreichen asymptotisch auch diese
Schranke, aber die konstanten Faktoren sind recht groß.
Und wie man einen deterministischen Algorithmus angibt, der dann einen
vernünftigen konstanten Faktor erreicht, ist noch ein offenes Problem.
Gibt es Fragen zu externen Sortieralgorithmen?
Genau.
Wir hatten uns dann externe Prioritätslisten angeschaut und
festgestellt, dass man die sozusagen genauso effizient wie sortieren
machen kann mit 1 durch B mal Log Basis M durch B amortisierten IOs.
Und ich habe das im Detail erklärt für mittelgroße Queues, die bis zu
M² durch B Einfügungen haben.
Und habe dann so einen kleinen Einblick gegeben, wie man das
verallgemeinert für große Eingaben.
Frage?
Ja, okay.
So, man hat mich dazu verdonnert, mit diesem komischen Ding hier zu
arbeiten, weil sonst die Aufzeichnung nicht funktioniert.
Ich hätte das innerhalb von 30 Sekunden an der Tafel erklärt.
Mal gucken, ob wir das hier hinkriegen.
Genau, also die Frage wie man auf das Log N durch B kommt.
Wenn das hier so ein Binary Heap ist, der hat dann tiefe Log N.
Also ist ganz klar, dass man es irgendwie in Log N kann.
Man muss diesen Baum da halt runtersteigen.
Aber der Trick ist, man kann die M obersten Knoten dieses Baums, kann
man im internen Speicher halten.
Und dieser Teil des Baums hat dann tiefe Log M.
Und ja, Log N minus Log M ist gleich Log N durch M.
Beantwortet das die Frage?
Genau, dann können wir das in Zukunft auch verwenden.
Ist vielleicht gar nicht so schlecht.
Ich mag die Tafel trotzdem lieber, aber ich glaube, viele mögen das,
dass sie auch mal ein bisschen in die Vorlesung gehen müssen.
Ich wünschte sogar eine Mehrheit, weil die Anzahl Klausurteilnehmer
ist meistens etwas größer als die Anzahl Leute drin.
Andererseits will ich auch einen gewissen Mehrwert in der Vorlesung.
Genau.
Und ich habe dann halt gezeigt, wie man mit so einer etwas komplexeren
Datenstruktur halt tatsächlich ungefähr auf diese Sortierschrank
kommt.
Hier ist allerdings tatsächlich auch noch offen, wie man das mit
parallelen Platten macht.
Und was vielleicht noch wichtiger ist, mit parallelen Prozessoren.
Also das, was hier passiert, ist in großen Teilen inherent
sequenziell.
Man hat zwar Sortieroperationen da drin, wo man diesen Puffer
sortiert, aber das sind halt relativ kleine Puffer und da ist nicht
sehr viel Parallelismus drin.
Diese Aufräumoperationen, da ist schon mehr Parallelismus drin.
Aber trotzdem hat man da noch einiges an sequenziellen bottlenecks
dabei.
Genau, die Experimente zeigten aber, dass das über 20 Jahre hinweg
ziemlich gute Ergebnisse liefert.
Es ist eher so, dass die Speicherhierarchie-Effekte bei modernen
Prozessoren sich noch verstärkt haben.
Ich hatte dann einen ganz einfachen Algorithmus für minimale
Spannbäume vorgestellt.
Und im Wesentlichen läuft es darauf hinaus, zu sagen, naja, wenn man
ein Kruskalz-Algorithmus so implementiert, dass der Sortierschritt mit
einem externen Memory-Sortier-Algorithmus gemacht wird, dann hat man
einen semi-externen Algorithmus.
Das heißt einen, wo man nur Informationen zu den Knoten im
Hauptspeicher halten muss, nicht aber zu den Kanten.
Das ist dann übrigens auch so in der Algorithm-Engineering-Vorlesung
machen wir dann einen Trick, wie man zeigt, dass man diese Union-Find
-Daten -Struktur tatsächlich mit einem einzigen Maschinenwort pro
Knoten präsentiert kriegt.
Aber so weit ins Low-Level will ich sie hier nicht runterziehen.
Sie sollen ja nur ein bisschen einen Appetizer kriegen eigentlich für
fortgeschrittene algorithmische Technik.
Spannender ist dann das allgemeine Problem, wenn man noch nicht mal
die Knoten in den Hauptspeicher bekommt, dann ist halt der Trick, dass
man irgendwie anders MST-Kanten identifiziert und kontrahiert.
Das heißt, man macht einen Graphen, der dann entsprechend weniger
Knoten enthält und irgendwann kann man dann diesen semi-externen
Crosscall verwenden.
Und das funktioniert ganz gut.
Diese Messungen sind relativ alt, aber das wird auch auf modernen
Maschinen funktionieren.
Eben wieder mit der Einschränkung, das hier ist auch ein, zumindest
der semi-externe Crosscall ist sequentiell.
Diese Kontraktionsverfahren, die wir da verwendet haben, sind auch
sequentiell.
Wir benutzen eine externe Priority-Queue.
Also wir haben jetzt tatsächlich schon sehr viel gelernt darüber, wie
man MSTs berechnet.
Einfach, weil Sie wissen, wie man sortiert und externe Priority-Queues
baut.
Aber wenn man das Ganze parallel machen will, braucht man andere
Algorithmen.
Da lernen Sie ein bisschen zu in der parallelen Algorithmen-Vorlesung.
Das bringt mich jetzt zu den Abschlussfolien für externe Algorithmen.
Wir können einfach mal durch diese Basic-Toolbox-Sachen aus
Algorithmen 1 gehen.
Was gibt es da zusätzlich zu bemerken, wenn man eben externe Memory
-Algorithmen dazu nimmt?
Hashtabellen, ja, kann man natürlich auch extern halten, aber man hat
eben einen ganzen I.O.
pro Zugriff.
Dieses, was wir jetzt bei Priority-Queues oder so was hatten, oder bei
Stacks, das ist sowas wie ein Faktor 1 durch B amortisiert ist, ist da
eher nicht.
Wir müssten dann höchstens hergehende Anwendungen machen, wo Sie so
Batch -Zugriffe haben.
Ganz viele Elemente einfügen, ganz viele Such-Operationen.
Was man dann merkt, ist, dass eigentlich so Bulk-Hashing nicht sehr
viel anderes ist, als einfach sortieren nach dem Hash-Funktionswert.
Dann haben Sie wieder externe Sortier-Algorithmen.
Bisschen spannender sind Suchbäume.
Wir haben in Algorithmen 1 Ihnen ja AB-Bäume beigebracht.
Das wurde dann erstmal so dargestellt, naja, das ist eine besonders
elegante Suchbaum-Datenstruktur, weil alle Blätter auf dem gleichen
Level sind und weil man dadurch, dass man den Grad der Knoten, dass
man da ein bisschen flexibel ist, um Faktor 2 meistens, kann man halt
diesen Baum sehr leicht balancieren.
Was wir, glaube ich, nicht so ganz verraten haben, ist, dass wenn man
jetzt diesen Parameter für den Knotengrad so wählt, dass dieses A
gleich Theta B ist.
Also ein Knoten des Baumes, wenn man an eine Seite des externen
Speichers passt, dann kriegt man gleich eine sehr gute externe Memory
-Datenstruktur.
Das ist eigentlich ein klassisches Ergebnis.
Das war tatsächlich einer der Gründe, warum Bayer und McQuaid in den
70er Jahren diese Datenstruktur vorgeschlagen haben.
Und die ist eben auch in allen Datenbanken drin als externe
Datenstruktur.
Wird auch für Dateisysteme verwendet.
Und wenn Sie dann weiter einsteigen wollen, gibt es eine ganze Reihe
Papers, vor allem aus der Datenbank-Community, mit Tuning-Tricks.
Zum Beispiel ist es sinnvoll, ich habe Ihnen ja gesagt, beim Sortieren
haben wir eine Blockgröße von 4 Megabytes oder sowas, auf aktuellen
Maschinen, wenn man mechanische Festplatten verwendet.
Für so einen AB-Baum ist das aber nicht sinnvoll, weil wenn Sie
tatsächlich die Blätter auf dem externen Memory haben wollen, dann ist
es eher besser, etwas kleinere Blockgrößen zu wählen für die
Navigation.
Aber dann ganz unten auf den Blättern des Baums machen Sie dann wieder
große Blockgrößen, weil Sie dann sehr schnell scannen können, zum
Beispiel Range-Querys machen.
Also alle Elemente des Suchbaums in einem bestimmten Bereich von
Schlüsselwerten.
Oder was man natürlich auch macht, ist der gleiche Trick wie hier,
dass man die obersten Noten cached.
Das führt dann dazu, dass bei Datenbanken es im Endeffekt so ist, sie
haben dann ein oder zwei externe Memory-Zugriffe, um ihre Daten
zuzugreifen, weil alles andere ist im Hauptspeicher.
Wenn Sie dann String-Schlüssel haben, gibt es nochmal Tricks.
Also da gibt es eine ganze Menge Literatur, wie man das jetzt tunt, je
nach Anwendungsfall.
Wir haben da gerade auch Arbeiten gemacht, wie man das wieder parallel
macht, also wie man viele Elemente einfügt oder sucht in einem AB-Baum
mithilfe von parallelen Prozessoren.
Das bracht auch alles ganz gut hin.
Dann kann man sich Graphen-Algorithmen anschauen und Graphen
-Algorithmen und External Memory passen eigentlich nicht so gut
zusammen.
Also ein Graph ist ja etwas, der sich dadurch auszeichnet, dass man
sozusagen Kreuz- und Querverbindungen zwischen Objekten als Kanten
modelliert.
Und wenn man das dann in einem External Memory-Algorithmus nachbaut,
dass man zum Beispiel irgendwelche Pfade traversiert, führt das dann
halt immer zu ganz vielen schwer vorhersagbaren Zugriffen auf den
externen Speicher und das ist langsam.
Man muss sich also überlegen, wie man damit umgeht und das ist
ziemlich schwierig.
Deshalb gibt es relativ wenig Ergebnisse dazu.
Diese minimalen Spannbäume hatte ich deshalb sehr bewusst ausgesucht,
weil man das da halt kann.
Noch einfachere Dinge im Internal Memory sind Breitensuche und
Tiefensuche.
Genau, also Breitensuche geht noch ganz gut, wenn der Graph kleinen
Durchmesser hat.
Das ist zum Beispiel der Fall, sehr große Netzwerke, für die man sich
im Moment sehr interessiert, sind soziale Netzwerke, zum Beispiel der
Facebook -Graph oder auch der Web-Graph.
Die haben einen sehr kleinen Durchmesser und da kann man dann ganz gut
eine Breitensuche machen im Endeffekt, indem man mehrfach durch den
ganzen Graphen durchscannt und dann mal ein Level sich nur rauszieht.
Tiefensuche ist noch schwieriger, weil man da halt noch weniger lokal
zugreift.
Es gibt aber wohl Heuristiken, die zumindest semi-externe Tiefensuche
auf bestimmten Graphen ganz gut hinkriegen.
Kürzeste Wege berechnen ist so ähnlich wie BFS.
Also bei Graphen mit kleinem Durchmesser kann man das wohl machen.
So, gibt es noch Fragen zu externen Memory-Algorithmen?
Also da habe ich jetzt nur so einen kurzen Exkurs gemacht.
Wäre das nächste Kapitel Approximations-Algorithmen.
Da muss ich jetzt gleich ein bisschen warnen.
Die Folien haben einen gewissen Überlapp mit theoretischen Grundlagen
der Informatik, weil ich glaube, die Vorlesung, die die meisten von
Ihnen gehört haben, hat die Frau Wagner gehalten und die hat dann
einen Teil der Approximations-Algorithmen dort schon gemacht.
Ich werde deshalb die Sachen, die da schon drin waren, relativ kurz
behandeln.
Und die werden wir dann in der Prüfung so auch nicht drin haben.
Aber wir haben ja auch noch ein paar andere Beispiele und das dürfte
unproblematisch sein.
Genau, Approximations-Algorithmen sind eine Möglichkeit zum Umgang mit
NP -harten Problemen.
Und das ist deshalb wichtig, weil es eigentlich fast alle spannenden
Optimierungsprobleme NP-hart sind.
Wenn Sie eine Algorithmen-Vorlesung halten, dann kriegen Sie
vielleicht einen anderen Eindruck.
Wir erklären Ihnen Dijkstra's Algorithmus, minimale Spannbäume,
maximale Flüsse.
Aber das ist so ein bisschen wie der Betrunkene, der unter der Laterne
seinen verlorenen Schlüssel sucht, obwohl er den da gar nicht verloren
hat.
Also wir erzählen Ihnen halt sozusagen die Algorithmen, wo wir
positive Lösungen haben.
Aber ehrlich gesagt ist es so, wenn Sie irgendwie beliebiges
Optimierungsproblem aus der Industrie kriegen, dann ist das in der
Regel NP-hart.
Und dann muss man sich halt überlegen, wie man damit umgeht.
Da gibt es sicherlich viele Möglichkeiten, aber das ist halt etwas,
was wir Ihnen in Algo 1 oder Algo 2 jetzt nicht in dem Detailgrad
beibringen können, weil das halt relativ schwierig ist.
Aber Sie sollten schon einen gewissen Einblick kriegen, dass das kein
Todesurteil ist.
Wenn Sie ein NP-hartes Problem vor sich haben, gibt es viele
Möglichkeiten, damit umzugehen.
Approximationsalgorithmen sind eine Möglichkeit.
Also was ich dann sage, ist, ich will eine Garantie haben, dass ich
einen effizienten Algorithmus habe.
Für einen Theoretiker ist dann auch wohl definiert, was das ist,
nämlich polynomielle Ausführungszeit.
Und die Lösungen sollen garantiert nah am Optimum sein.
Jetzt haben Sie schon sozusagen zwei Provisos da drin.
Also erstens, Theoretiker finden, dass polynomielle Ausführungszeit
effizient ist.
Und zweitens, was verstehe ich unter nah am Optimum?
Die Leistungsgarantien, die man als Theoretiker da geben kann, sind
oft nicht so nah am Optimum, wie man sich das vielleicht wünschen
würde.
Und die polynomiellen Ausführungszeiten sind oft für große Eingaben
immer noch jenseits von Gut und Böse.
Trotzdem ist das ein Ansatz, systematisch mit diesem NP-Härte-Problem
umzugehen.
Und es kommen zum Teil praktikable Lösungen dabei raus.
Oder zumindest Ansätze, die dann vielleicht in der Praxis auch besser
funktionieren als die theoretischen Garantien, die man hat.
Aber vielleicht ist das jetzt auch trotzdem ein Moment, wo wir uns mal
überlegen können, was sind denn andere Ansätze, um mit NP-Harten
-Problemen umzugehen.
Mal gerade, ob man den irgendwie ein bisschen leiser hier machen kann.
Genau, also ein Ansatz, den man nicht vernachlässigen sollte, wäre,
wir pfeifen auf Negativergebnisse und sagen, wir suchen optimale
Lösungen und effiziente Algorithmen, die optimale Lösungen finden.
Und vielleicht funktioniert es ja trotzdem.
NP-Härte sagt ja nur, dass wir nicht ausschließen können, dass es
Instanzen gibt, für die eine optimale Lösung lange braucht.
Aber ob das die Instanzen sind, die wir in der Praxis wirklich lösen
wollen, steht ja auf einem anderen Blatt.
Und das ist zum Beispiel der Ansatz, der im Operations Research sehr
viel verwendet wird.
Also wenn Sie jetzt Vorlesungen von Herrn Nickel oder anderen Kollegen
hören, dann ist das oft der Ansatz.
Es gibt da auch große Softwarepakete wie CPLEX oder Gurobi, die zum
Beispiel ganzzahlige lineare Programme optimal lösen können im
Prinzip.
Und das in vielen Fällen auch tun, sage ich mal.
In anderen Fällen dauert es ganz lange.
Da muss man dann auch viel Erfahrung sammeln, wie man diese Probleme
so umformuliert, dass man da vielleicht vernünftige Lösungen kriegt.
Was Praktiker dann außerdem noch machen, ist ad hoc Heuristik.
Man überlegt sich halt irgendwas.
Da kommt dann irgendeine Lösung raus.
Wie gut die ist, kann man nicht garantieren.
Aber wenn man das Ganze insgesamt sorgfältig macht, kommt ja
vielleicht was Vernünftiges dabei raus.
Dann, wie gesagt, die Approximationsalgorithmen.
Und dann ein Ansatz, dass man das Problem umgeht oder spezialisiert.
Umgehen hieße, ich mache zum Beispiel eine andere Modellierung meines
Problems und dann wird das Ganze plötzlich ein kürzester Wegeproblem
oder ein maximales Schlussproblem.
Und dann kann ich es mit polynomiellen Algorithmen lösen.
Ich löse ein anderes Problem, aber vielleicht ist das für die
Anwendung dann ja sogar das Richtige oder was Brauchbares, als wenn
ich es gar nicht lösen kann.
Oder wir spezialisieren das Problem.
Das heißt, wir sagen, aha, wir machen eigentlich den Ansatz hier.
Wir suchen eine optimale Lösung und beweisen aber, dass das für eine
bestimmte Familie von Eingabeinstanzen tatsächlich auch in
polynomieller Zeit geht.
Wir werden dazu ein eigenes Kapitel haben, die
Fixparameteralgorithmen.
Gibt es Fragen zu diesen verschiedenen Ansätzen mit NPH-Problemen
umzugehen?
Dann gucken wir uns jetzt mal ein Beispielproblem an, das sehr typisch
ist.
Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen.
Das ist eine relativ lange Überschrift.
Ist auch nicht unbedingt ein Zufall.
Ich habe in meinem Büro so ein Handbook of Scheduling.
Das sind 1200 Seiten und da sind dann ein paar hundert verschiedene
Scheduling -Probleme vorgestellt.
Und wenn Sie die ganze Literatur angucken, da gibt es da so jedes Jahr
Konferenzen, die nur das machen, sind das wahrscheinlich Tausende.
Die meisten davon sind NPH-t.
Und die treten halt in der Praxis auch sehr viel auf.
Es gibt aber eben tatsächlich ein paar, die so fundamental sind, dass
sie auch in der Algorithmen-II-Vorlesung gut reinpassen.
Und eines davon ist halt dieses hier.
Man kann das tatsächlich auf Nicht-Computer-Anwendungen auch anwenden.
Also Sie haben vielleicht tatsächlich in einer Fabrik irgendwie
Maschinen stehen, die von mir aus irgendwelche Rohrleitungen gießen
oder was weiß ich.
Und Sie haben Jobs, die sagen hier produziere 500 Meter blaues Rohr
und hier 600 Meter dünnes schwarzes Rohr.
Keine Ahnung.
Und das können die Maschinen alles.
Und jeder dieser Jobs hatte halt eine bestimmte Ausführungszeit, um
ihn durchzuführen.
Und sie wollen halt die vorliegenden Anfragen in möglichst kurzer Zeit
abarbeiten auf den gegebenen Maschinen.
Aber tatsächlich ist das so, dass diese Variante des Scheduling
-Problems gerade auch in der Informatik oft auftritt, wenn Sie nämlich
irgendeine Anwendung haben, wo Sie eine Vielzahl von Teilproblemen
lösen müssen.
Also Sie haben vielleicht irgendeine Anwendung runtergebrochen darin,
dass Sie ganz viele kleine Aufgaben erfüllen müssen.
Und Sie haben eben viele Computer zur Verfügung, die das können.
Sie können außerdem vielleicht abschätzen, wie lange es dauert, diese
Teilaufgaben zu erfüllen.
Dann ist das genau das Problem.
Sie müssen jetzt die Teilaufgaben auf die Maschinen verteilen und was
Sie interessiert ist, wann die letzte Teilaufgabe fertig ist.
Das ist das, was wir hier machen.
Etwas formaler.
Wir haben n Jobs.
Der i zu Jobs braucht Zeit ti, um auf einer von den Maschinen gelöst
zu werden.
Die Maschinen sind alle gleich.
Und was Sie ausrechnen müssen, ist x von j.
Das ist die Maschine, auf der Job j ausgeführt wird.
Und was Sie dann kriegen ist, für die i Maschine können Sie ausrechnen
die Summe aller Ausführungszeiten der Jobs, die dieser Maschine
zugeteilt sind.
Das ist die Last dieser Maschine i.
Und Ihre Zielfunktion ist, dass Sie die maximale Last minimieren
wollen.
Und das nennt man den Makespan.
Wir haben hier ein paar Annahmen gemacht, die man aufweichen kann.
Und dann kriegt man immer neue Schedulingprobleme.
Man kann sagen, wir haben nicht identische Maschinen, sondern
vielleicht Maschinen, die unterschiedlich schnell sind.
Oder vielleicht sogar unrelated Maschinen.
Das heißt, es gibt Maschinen, die für bestimmte Jobs gut sind und für
andere schlecht.
Dann habe ich also für jede Kombination aus Job und Maschinen
vielleicht eine andere Ausführungszeit.
Ich habe hier angenommen, dass die Jobs komplett unabhängig sind.
Aber vielleicht gibt es da auch Präzedenzen, dass ich sage, ich kann
von mir aus ein, was weiß ich, wenn ich Kunststoffweihnachtsbäume
herstellen will, dann muss ich erstmal den Baum selber herstellen und
dann den Schmuck dranhängen oder sowas.
Das heißt, bestimmte Jobs haben so Abhängigkeiten voneinander.
Ich nehme hier an, dass die Ausführungszeiten bekannt sind.
Das ist gerade in der Informatik leider oft nicht der Fall, weil da
wird halt irgendein Unterprogramm ausgeführt und je nach Eingabe kann
das unterschiedlich lange dauern.
Sie wollen also vielleicht auch mit geringerem Wissen umgehen.
Das ist etwas, was wir im Kapitel über Online-Algorithmen uns
anschauen werden.
Genau und hier offline, online kann man nochmal allgemeiner fassen,
indem man auch sagt, naja, ich hatte eben das Beispiel mit diesen
Aufträgen Rohre herzustellen, aber das ist ja jetzt nicht so, dass
irgendwie alle Aufträge übers Wochenende eingehen und dann der Meister
in der Produktion irgendwie alle Aufträge am Montagmorgen einplanen
und dann werden die über die Woche abgearbeitet, sondern es kommen
eben jeden Tag neue Aufträge rein und die muss man halt in die
laufende Produktion irgendwie einplanen.
Und man weiß aber nicht, welche Aufträge wann reinkommen und muss
deshalb eine gewisse Flexibilität haben.
Und das sind eben Online-Algorithmen, über die wir auch noch reden.
So, jetzt zurück zu diesem relativ speziellen, aber wie ich doch
finde, spannenden grundsätzlichen Problem, das eben in einigen Fällen
dann doch auftritt oder zumindest eine Näherung dessen ist, was man
tatsächlich beobachtet.
Hier ist ein Algorithmus, der schon aus den 50er Jahren kommt.
List-Scheduling.
Also meine Jobs nummeriere ich einfach durch und J ist eben die Menge
der Jobs, die noch zu verarbeiten ist.
Die Lasten, also ich habe N Jobs, M Maschinen.
Ich habe ein Array von Lasten, das ist am Anfang null, weil ich noch
keine Jobs zugeteilt habe.
List-Scheduling ist jetzt was sehr generisches.
Solange es noch nicht eingeplante Jobs gibt, wähle irgendeinen Job
aus, entferne ihn aus der Jobmenge und jetzt muss ich irgendeine Regel
haben, wie ich das zuteile.
Und da ist eben eine ganz naheliegende Lösung, dass ich diejenige
Maschine I wähle, die die kleinste Last hat.
Oder wenn es mehrere mit kleinster Last gibt, wähle ich irgendeine.
Dann teile ich den Job J dieser Maschine I zu und inkrementiere
entsprechend die Last dieser Maschine.
Und dann gebe ich diesen Vektor X als Ergebnis zurück.
Und diesen Algorithmus werden wir jetzt analysieren.
Also zunächst mal Laufzeit ist schon mal ganz gut.
Offensichtlich geht das in O von N mal M Zeit.
Hat jemand eine Idee, wie man das in O von N log M hinkriegt?
Offenbar ist es irgendwie hier durchiterieren.
Ich habe gesagt, egal welche, kann man einfach durch diese Liste hier
durchiterieren.
Ich hätte genauso gut hier schreiben können, vor J gleich 1 bis N.
Und dann muss ich aber immer die Maschine mit kleinster Last wählen.
Aber ich kann ja die Maschinen in einer Prioritätsliste halten.
Und dann geordnet nach ihrer Last.
Und dann muss ich immer delete Min, nehme das mit kleinster Last,
inkrementiere die Last, füge das wieder ein.
Das braucht log M Zeit.
Das sind so Sachen, die kennen Sie jetzt.
Ich hoffe, Sie wissen, was Priority Queues sind und so weiter.
Aber wie analysiere ich jetzt, wie gut ist diese Lösung?
Um dem näher zu gehen, werde ich jetzt einfache Lemmas darüber.
Ich werde sozusagen diese Lösung, die ich da berechne,
charakterisieren.
Jetzt gucke ich mir einen konkreten Job an, L.
Das ist der, der zuletzt beendet ist.
Das Bild hier, der da.
Der hat Zeit TL.
Und wir zeigen jetzt, dass der Makespan Lmax höchstens Summe J TJ
durch M.
Das ist im Prinzip eine einfache untere Schranke für den Makespan, die
sagt, na ja, idealerweise kann ich halt die ganze Last gleichmäßig auf
die Prozessoren verteilen.
Also Summe aller Zeiten TJ und das geteilt durch M.
Und dazu kommt dann,
das ist sozusagen optimal, dieser Teil.
Und das hier ist das, was schlimmstenfalls dazukommen kann.
Das ist natürlich spannend.
Nämlich M-1 durch M mal TL.
Nehmen wir mal an, M ist groß, dann ist das ungefähr 1.
Also es ist sozusagen annähernd das Beste, was man sich vorstellen
kann, plus ich schmeiße jetzt diesen Job obendrauf und der sticht dann
sozusagen raus.
Wie beweise ich das?
Jetzt
gucke ich mir an, der
Zeitpunkt, zu dem dieser Job L eingeplant wurde.
Da war die Maschine, wo er eingeplant wurde, halt die Maschine mit der
kleinsten Last.
Das heißt alle anderen Maschinen mit der Last t.
Was t ist, weiß ich im Moment nicht, ist aber auch erst mal nicht
wichtig.
Aber was wichtig ist, alle anderen Maschinen hatten zu dem Zeitpunkt
bereits eine höhere eingeplante Last.
Ja, also die maximale Last ist dann t plus TL.
Und wie kann ich dieses t abschätzen?
Das ist
höchstens, genau, also ich habe ja jetzt alle anderen Jobs sind ja zu
dem Zeitpunkt schon verteilt.
Deren Gesamtlast ist eben Summe J ungleich LTJ.
Und wenn ich das durch M teile, ist das eine untere Schranke dafür,
wie das t aussehen kann.
Weil es darf ja keine Maschine geben, die eine geringere Last hat.
Das heißt, ich kann dieses t maximieren, indem ich die die Last der
anderen Jobs komplett gleichmäßig verteile über die Maschinen.
Ja, und das ist, was ich dann rauskriege.
Dann muss t mindestens Summe J ungleich LTJ durch M sein.
Und dann kommt natürlich das TL da drauf.
Und das kann ich jetzt einfach umformen.
Das kann ich schreiben als Summe aller J, TJ durch M.
Und dann habe ich hier sozusagen was dazu addiert.
Das ist eben gerade, da muss ich das hier minus TJ durch M schreiben.
Und dann TL durch M.
Und wenn ich das TL dann sozusagen da rausziehe, also es gibt den TL
-Term und den TL durch M-Term, dann kann ich den auch schreiben als M
-1 durch M mal TL.
Also das ist dann nur noch eine arithmetische Umformung.
Und damit ist dieses Lemma bewiesen.
Und das ist schon eine ganz wichtige Aussage.
In gewisser Weise ist das sogar eine stärkere Aussage als das der
Approximationsergebnis, das wir dann später zeigen.
Weil es uns jetzt schon sagt, zum Beispiel, dass wenn alle Jobs klein
sind, dann kriege ich eine supergute Approximation hier.
Wenn also TL klein ist gegen die Summe TJ durch M über alle J, dann
weiß ich, dass es ein guter Algorithmus ist.
Genau.
Dann gibt es noch zwei untere Schranken.
Nämlich die maximale Last ist eben sicherlich mindestens Summe aller J
TJ durch M.
Aber auch die maximale Last, also der Makespan, ist sicherlich
mindestens so groß wie der größte Job.
Max J TJ.
Und aus diesen Lemmas kann ich jetzt ein irgendwie etwas
übersichtlicheres Ergebnis ableiten.
Nämlich den Approximationsfaktor.
Der ist folgendermaßen definiert.
Das kennen Sie dann wahrscheinlich schon aus TDI.
Ich mache das jetzt für den Fall eines Minimierungsalgorithmus.
Ein Minimierungsalgorithmus erzielt den Approximationsfaktor Rho
bezüglich einer Zielfunktion F, falls er für alle Eingaben eine Lösung
berechnet.
So das gilt die Lösungsqualität des Algorithmus geteilt durch die
Lösungsqualität eines optimalen Algorithmus kleiner gleich Rho.
Jetzt sollten wir zur Übung umschalten.
Ich werde dann mithilfe dieser Lemmas, die ich eben hergeleitet habe,
dann beim nächsten Mal zeigen, dass wir grob einen
Approximationsfaktor von zwei bekommen für das Verfahren.
Dass das auch bestmöglich ist.
Wir werden mehr über Scheduling sehen und dann mal gucken, was Frau
Wagner uns noch übrig gelassen hat.
So, dann machen wir im zweiten Teil jetzt die Übung.
Und zwar gibt es als erstes nochmal einen kleinen Nachtrag zu Flüssen
letzte Woche, insbesondere zu Matchings.
Und danach werden wir uns dann mit randomisierten Algorithmen
beschäftigen und External Memory Algorithmen.
Aber zunächst erstmal Matchings.
Nochmal zur Definition, was ein Matching eigentlich ist.
Und zwar ist ein Matching einfach eine Teilmenge der Kanten unseres
Graphen.
Und zwar muss diese Teilmenge die Eigenschaft erfüllen, dass kein
Knoten aus unserem Graphen Inzidenz zu mehr als einer sogenannten
gematchten Kante dann ist.
So, dann haben wir hier ein Beispiel von einem Matching.
Auch wenn man das hier schwer erkennt.
Und zwar müssen diese beiden Kanten hier im Matching sein.
Dieses Matching ist dann maximal.
Das heißt, dass es Inklusionsmaximal ist.
Das heißt, wir können keine weitere Kante mehr zu unserem Matching
hinzufügen, ohne eben diese Eigenschaft zu erfüllen, dass kein Knoten
zu mehr als einer Inzidenz ist.
Dieses Matching ist dann aber kein Maximum.
Ein Maximum ist dann entsprechend, wenn es Kardinalitätsmaximal ist.
Das heißt, das ist das Matching, wenn man sich alle möglichen
Matchings anschaut, dann ist es das mit den meisten Kanten.
Auch hier haben wir dann ein Beispiel, wenn wir statt dieser Kante
hier einfach diese beiden hellblauen oder blauen Kanten nehmen, dann
erhalten wir eben ein Maximum Matching.
Was es dann auch noch gibt, sind perfekte Matchings.
Bei einem perfekten Matching ist dann jeder Knoten aus unserem Graphen
Endpunkt zu einer gematchten Kante.
Kardinalität, das habe ich ja gerade gesagt, das ist einfach die
Anzahl der Kanten, die wir in unserem Matching drin haben.
Und wie bestimmt man normalerweise so ein Maximum Matching?
Das macht man mithilfe von sogenannten alternierenden Faden.
Wie kann man sich das grob vorstellen?
Im Endeffekt, wir können mit einem beliebigen Matching anfangen und
dann traversieren wir gematchte und ungematchte Kanten abwechselnd und
versuchen dadurch einen Pfad zu finden, der mehr Kanten enthält als
unser Ausgangsmatching.
Und dadurch können wir dann iterativ unser Matching immer größer
machen, bis es eben nicht mehr geht und es Kardinalitätsmaximal ist.
In Bezug auf Flüsse wollen wir uns jetzt allerdings insbesondere
Bipartite Matchings anschauen.
Das heißt, wir haben jetzt einen Bipartitengrafen, wie ihr hier rechts
seht.
Bipartit heißt einfach, dass wir unsere Knotenmenge im Endeffekt
partitionieren können in zwei Gruppen und es gibt keine Kanten
zwischen Knoten innerhalb von einer Gruppe, sondern nur Kanten
zwischen den beiden Gruppen.
Das heißt, wir haben hier eine Gruppe links, eine Gruppe rechts.
Zwischen den Knoten hier darf es keine Kante geben, sondern nur
zwischen den beiden Gruppen.
Und auf diesem Grafen wollen wir dann ein Maximum Matching finden.
Und zwar wäre hier noch mal ein Beispiel für so ein Maximum Matching.
Was hat das Ganze dann mit Flussproblemen zu tun?
Was wir jetzt machen können ist, das Ganze in ein Flussproblem
umzuwandeln.
Das heißt, wir fügen hier einmal einen Quellknoten ein und einen
Zielknoten.
Was wir dann machen ist, es gibt von unserem Startknoten oder von
unserer Quelle aus eine Kante mit Kapazität 1 zu allen Knoten auf der
einen Seite unseres bipartiten Grafen und entsprechend für die andere
Partition gibt es dann immer eine Kante mit Kapazität 1 zu unserer
Senke.
Auch alle Kanten, die dann zwischen den beiden Gruppen laufen,
bekommen auch Kapazität 1.
Und wenn wir jetzt einen Standardalgorithmus zur Lösung von einem
Flussproblem nehmen, zum Beispiel Fort Falkersen, dann können wir
damit ein Maximum Matching auf diesem bipartiten Grafen finden, was
eine sehr schöne Eigenschaft ist.
Und zu guter Letzt, wofür brauchen wir die Matchings überhaupt?
Matching sind ein wichtiges Problem in der Praxis, weil sie quasi in
sämtlichen Zuweisungsproblemen auftreten und in irgendeiner Form auch
verwendet werden können.
Was wir jetzt zum Beispiel gerade in der Vorlesung gesehen haben, sind
Scheduling -Probleme, das heißt wir wollen Jobs beispielsweise auf
irgendwelchen Computern oder einem Supercomputer verteilen.
Und was wir dann haben, ist im Endeffekt eine Menge an Jobs und eine
Menge an Computern und wir wollen quasi möglichst viele Jobs
gleichzeitig auf diesen Computern laufen lassen.
Anderes Beispiel, was ihr hier dann seht, ist Crew Scheduling und so
haben wir hier auch wieder einen bipartiten Grafen.
Oben seht ihr die einzelnen Crew-Mitglieder, wenn ihr euch jetzt
vorstellt, dass diese drei Punkte hier zum Beispiel Piloten sind und
das andere sind sonstige Crew-Mitglieder, Ingenieure oder sonst was.
Und auf der anderen Seite haben wir Mengen von oder einzelne
Flugzeuge, die wir dann besetzen wollen mit unserer Crew.
Und hier haben wir zum Beispiel die Restriktion, dass es halt immer
nur einen Piloten pro Flugzeug geben soll.
Das heißt, wir wollen zum Beispiel nicht zulassen, dass zwei Piloten
gleichzeitig ein Flugzeug steuern.
Und auch hier können wir dann ein Matching bestimmen, das dann genau
jedem Piloten ein Flugzeug zuweist.
Genau.
Soweit dann zum Matching.
Das war jetzt nur nochmal ein kleiner Nachtrag.
Machen wir dann direkt weiter mit der eigentlichen Übung.
Und zwar geht es heute unter anderem dann noch um randomisierte
Algorithmen.
Nochmal ein paar Grundlagen zu Las Vegas und Monte Carlo.
Dann ein Beispiel für einen Monte Carlo Algorithmus, nämlich die
Matrix -Matrix-Multiplikation bzw.
die Verifikation von einer Matrix-Matrix-Multiplikation und das Coupon
-Collector -Problem, was ziemlich interessant ist, aber kommen wir
gleich dazu.
Dann schauen wir uns nochmal ein paar Speichermodelle an.
Das Parallel-Disk-Modell.
Wir schauen, welchen Einfluss die Speicher-Latenzen haben und wie wir
quasi die Speicher-Latenzen nutzen können, um unser Modell
praxisrelevanter zu machen.
Und dann schauen wir uns noch an, wie man Blockgrößen in einem
halbwegs realistischen System wählen sollte, damit das Ganze schnell
ist.
Wenn wir dann noch Zeit haben, gibt es noch ein bisschen ergänzendes
Material.
Einmal grundlegende Techniken, die man bei IEO-effizienten Algorithmen
beachten sollte.
Und dann schauen wir uns an, wie man diese Techniken z.B.
bei externem Sortieren verwendet.
Fangen wir aber an mit den randomisierten Algorithmen.
Hier nochmal einfach eine Übersicht über zwei Varianten von
randomisierten Algorithmen, die es gibt.
Das eine ist der Las Vegas-Algorithmus.
Das Schöne an Las Vegas-Algorithmen ist, dass sie immer eine korrekte
oder eine optimale Lösung liefern.
Die Downside ist, dass die Laufzeit eine Zufallsvariable ist.
Was man dann aber trotzdem machen kann, ist beispielsweise sowas wie
die erwartete Laufzeit angeben oder Tail Bounce für die Laufzeit
angeben, um dann zu zeigen, dass mit hoher Wahrscheinlichkeit dieser
Algorithmus trotzdem Linearzeit hat.
Beispiel hierfür ist dann Quicksort.
Einfach deshalb, weil die Laufzeit variiert abhängig von der Wahl
unseres Pivot-Elementes beim Quicksort.
Wenn wir quasi in jeder Runde das schlechtmöglichste Pivot wählen,
dann haben wir beispielsweise quadratische Laufzeit.
Wir können aber zeigen, dass wenn wir ein halbwegs gutes Pivot wählen,
wir auf erwartet sowas wie nLog n kommen.
Genau.
Die zweite Kategorie von randomisierten Algorithmen sind dann Monte
Carlo Algorithmen.
Hier das ganze gerade umgedreht.
Wir haben deterministische Laufzeit, das heißt wir können genau sagen,
okay, der Algorithmus braucht immer Linearzeit.
Allerdings kann es sein, dass er nicht unbedingt die korrekte Lösung
ausgibt.
Das heißt, die Lösung könnte fehlerbehaftet sein oder suboptimal sein.
Und was man dabei eigentlich immer noch hat, ist eine
Fehlerwahrscheinlichkeit p.
Das heißt, wie wahrscheinlich ist es, dass diese Eingabe jetzt falsch
ist.
Auch hier Beispiel, das eine ist der Miller-Rebin-Primzahl-Test.
Ein anderes Beispiel ist ein nicht vorbereiteter Student bei einem
Multiple -Choice-Test.
Dadurch, dass der Student keine Ahnung vom Stoff hat, ist die Zeit,
die er zum Ankreuzen von einem Kästchen braucht, eigentlich immer
gleich.
Das heißt, er ist in Linearzeit fertig.
Allerdings kann es sein, dass er halt eine beschissene Note kriegt.
Entsprechend ein gut vorbereiteter Student kriegt vielleicht immer die
richtige Lösung hin, aber er braucht unterschiedlich lange, um auf
diese Lösung zu kommen.
Und das wäre dann ein Beispiel für einen Las-Vegas-Algorithmus.
Ein Begriff, der häufiger dann noch vorkommt, sind Monte-Carlo
-Simulationen, die man allerdings nicht verwechseln sollte mit Monte
-Carlo -Algorithmen.
Das Prinzip von einer Monte-Carlo-Simulation ist einfach, dass wir ein
Zufallsexperiment, das hoffentlich relativ schnell geht, einfach sehr
oft ausführen und damit quasi einen Trade-off hinbekommen zwischen der
Qualität unserer Lösung und unserer Ausführungszeit.
Das heißt, wir haben quasi ein Problem, wir können schnell ein
Zufallsexperiment machen, jetzt führen wir das einfach 10.000 mal aus
und dann können wir mit einer gewissen Sicherheit sagen, ob das jetzt
eine gute Lösung ist oder nicht.
Insbesondere ist es eine sehr hilfreiche Alternative zu einer
analytischen Lösung, wenn es einfach zu kompliziert oder zu aufwendig
ist, diese Lösung zu berechnen.
Ein Beispiel, was hier zum Beispiel eingezeichnet ist, ist die
Approximation von Pi.
Was man da macht, man nimmt einen Einheitsquadrat, wie ihr jetzt hier
quasi seht, und in diesem Einheitsquadrat haben wir einen Quadranten
von einem Kreis.
Die Monte-Carlo-Simulation, die jetzt eine Approximation von Pi
bestimmt, funktioniert einfach so.
Stellt euch das Ding als Zielscheibe vor und ihr werft einfach
Datenpfeile auf diese Zielscheibe und zählt, wie viele innerhalb von
dem Kreisbogen liegen und wie viele außerhalb.
Wenn ihr das Ratio dann ausrechnet, bekommt ihr eine ziemlich gute
Nährung für Pi Viertel und dann multipliziert ihr es mit 4 und ihr
habt eure Approximation für Pi.
Wofür verwendet man Monte-Carlo-Simulation noch?
Das eine ist, wenn ihr in eurem Algorithmus eine Zufallsvariable drin
habt und ihr wisst aber nicht sicher, was für eine Verteilung diese
Zufallsvariable unterliegt.
Was ihr dann machen könnt, ist auch wieder ein Monte-Carlo-Experiment
ausführen, um damit quasi eine Näherung an die Verteilungsfunktionen
zu bestimmen.
Und dann habt ihr noch ein Beispiel hier rechts, wofür man es auch
verwendet, ist Nachbildung komplexer Prozesse, die einfach zu
aufwendig zu modellieren sind, was Rechnerkapazität beispielsweise
angeht.
Was jetzt bei den beiden randomisierten Algorithmentypen interessant
ist, ist, dass man sie relativ einfach ineinander überführen kann.
Das heißt, wir können einen Las Vegas-Algorithmus nehmen und daraus
relativ einfach einen Monte-Carlo-Algorithmus machen.
Gehen wir das Ganze einfach mal durch.
Also wir haben jetzt unseren Algorithmus mit erwarteter Laufzeit, das
ist einfach f von n.
Und was wir gerne haben wollen, ist quasi ein Algorithmus, der
deterministisch eine Laufzeit von o von f von n hat.
Allerdings erlauben wir, dass er auch eine Fehlerrate von p hat, wo er
dann ein falsches Ergebnis ausgibt.
Die Idee dafür ist relativ simpel.
Und zwar nehmen wir unseren gegebenen Algorithmus und brechen ihn
einfach nach einer bestimmten Zeit alpha mal f von n ab.
Wenn wir den Algorithmus abbrechen, dann gehen wir einfach falsch aus.
Und jetzt kann man quasi bestimmen, wie wahrscheinlich es ist, dass
der Algorithmus abgebrochen wird.
Das ist einfach, dass t größer ist als alpha mal f von n.
Hier nimmt man dann einfach eine Markov-Ungleichung und kann halt
zeigen, dass das ein kleiner gleich 1 durch alpha ist.
Wenn man sich jetzt überlegt, man nimmt für alpha beispielsweise 10,
das heißt wir erlauben das quasi, wir erlauben 10 mal die erwartete
Laufzeit, dann ist die Fehlwahrscheinlichkeit einfach kleiner gleich 1
Zehntel, was schon relativ gut ist.
Jetzt das ganze natürlich auch noch andersherum.
Das heißt, wir haben jetzt einen Monte-Carlo-Algorithmus mit
deterministischer Laufzeit o von f von n und einer Fehlerrate p.
Und außerdem können wir noch die Korrektheit unseres Ergebnisses in g
von n überprüfen.
Die Idee hier ist auch wieder sehr einfach.
Wir wiederholen einfach unseren Monte-Carlo-Algorithmus so lang, bis
wir ein korrektes Ergebnis gefunden haben.
Das heißt, wir haben jetzt eine Laufzeit t und die ist quasi nach oben
beschränkt durch i mal o von f von n plus g von n.
Also einfach die Anzahl an Schritte, die wir brauchen mal die Laufzeit
unseres Algorithmus plus die Laufzeit, die wir brauchen, um die
Korrektheit zu überprüfen.
Das heißt, unsere Laufzeit t ist jetzt eine Zufallsvariable und jetzt
schauen wir uns den Erwartungswert für diese Zufallsvariable an.
Und da können wir relativ einfach sagen, okay, das ist kleiner gleich
dem Erwartungswert für die Anzahl an Schritte, die wir brauchen, mal
unserer deterministischen Laufzeit.
Und für die Anzahl an Schritte gilt einfach, wir brauchen quasi k-1
Fehlversuche und dann kriegen wir einen richtigen Versuch hin und dann
gilt das quasi als korrekt.
Und der Erwartungswert ist jetzt einfach die unendliche Reihe quasi k
für die Anzahl an Schritte mal p hoch k-1.
Das heißt, wir hatten k-1 Versuche, wo wir das falsche Ergebnis
produziert haben und dann noch mal 1-p für das eine Mal, wo wir quasi
ein korrektes Ergebnis produziert haben.
Die Umformung für die geschlossene Form steht dann hier unten und wir
kommen dann einfach auf 1 durch 1-p.
Das heißt, insbesondere hat unser Las Vegas Algorithmus, den wir dann
rausbekommen, eine erwartete Laufzeit, die wir nach oben beschränken
können mit o von f von n plus g von n durch 1-p.
Gibt es hierzu schon irgendwelche Fragen?
Dann schauen wir uns jetzt ein Beispiel für einen Monte Carlo
Algorithmus an.
Und zwar kümmern wir uns dabei um die Verifikation von einer Matrix
-Matrix -Multiplikation.
Die Aufgabe ist relativ einfach.
Wir haben drei Matrizen x, y und z gegeben und wollen einfach gucken,
ob das Produkt von x und y gleich unserer Matrix z entspricht.
Wie macht man das ganze deterministisch?
Und zwar berechnen wir einfach x mal y und vergleichen dann
elementweise mit z.
So, wie schnell geht eine Matrix-Multiplikation?
Naiv, einfach in o von n hoch 3.
Hier steht jetzt noch, der aktuell beste Algorithmus hat o von n hoch
2 mal 2,37.
Der Algorithmus ist, glaube ich, ist richtig weiß aus dem Jahre 2014.
Und um das mal ein bisschen einzuordnen, der vorher beste Algorithmus
war aus dem Jahr 2013.
Und der Unterschied zwischen den beiden Algorithmen ist in der vierten
Nachkommastelle vom Exponenten.
Also, ja, sehr feingetunt.
So, kommen wir aber jetzt dazu, wie wir das ganze randomisiert machen.
Und zwar wählen wir dafür, ach so, wir wollen das natürlich dann auch
schneller als n hoch 2,37 machen.
Und zwar, was wir jetzt machen ist, wir wählen einen zufälligen n
-dimensionalen Vektor mit binären Werten 0 und 1 aus.
Und was wir dann machen ist, wir multiplizieren diesen Vektor erst an
unsere Matrix y und anschließend an x und vergleichen das Ergebnis,
das da rauskommt, dann mit z mal diesem Vektor r.
Wenn da quasi das gleiche rauskommt, geben wir korrekt aus, ansonsten
geben wir falsch aus.
So, Matrix-Vektor-Multiplikation geht jetzt einfach in o von n².
Da wir das einfach dreimal machen, haben wir auch eine Gesamtlaufzeit
von o von n².
Und die Behauptung, die wir jetzt gleich zeigen werden auch, ist, dass
wenn x mal y ungleich z ist, dann ist die Wahrscheinlichkeit, dass wir
trotzdem korrekt ausgeben, kleiner oder kleiner gleich ein Halb.
Vielleicht hier nochmal kurz zur Verdeutlichung, insbesondere, also
wir können quasi nur false positives erzeugen.
Das heißt, wir geben, falls x, y gleich z sein sollte, geben wir auf
jeden Fall immer true aus.
Und wenn x, y ungleich z ist, dann kann es halt sein, dass wir true
ausgeben, obwohl es eigentlich falsch ist.
Und das nennt man dann einen false positive.
So, hier zur Verdeutlichung nochmal, das ist quasi unser n
-dimensionaler Vektor r.
Und ein paar Elemente davon sind jetzt 0 und ein paar sind 1.
Hier ist dann die Matrix C, zum Beispiel jetzt y.
Und wir schauen uns jetzt quasi nicht mehr die ganze Matrix Y an,
sondern nur die entsprechenden hell markierten Spalten von dieser
Matrix.
Das spart uns halt einfach sehr viel Rechenzeit.
So, kommen wir jetzt dazu, wie man das Ganze zeigt.
Und zwar definieren wir uns dafür zuerst mal zwei Hilfsmatrizen.
A, das ist x mal y und b, das ist einfach z.
Und wir nehmen jetzt an, dass a ungleich b ist, wie hier in unserer
Behauptung, und wollen dann rausfinden, wann gilt trotzdem, dass a r
gleich b r ist.
Das heißt, wann haben wir unseren false positive.
So, erstmal, was impliziert quasi unsere Annahme?
Unsere Annahme impliziert erstmal, dass es auf jeden Fall einen
Eintrag in den Matrizen gibt, in dem sich die beiden Matrizen
unterscheiden.
Wir sagen jetzt einfach, dass dieser Eintrag in Zeile i und Spalte j
ist.
Also, die seht ihr quasi hier die beiden Einträge.
Und jetzt definieren wir uns noch ein paar weitere Hilfsvariablen.
Zunächst sagen wir, dass klein a einfach die i-te Zeile von a ist,
also quasi hier.
Und entsprechend auch klein b ist die i-te Zeile von b.
So, jetzt wissen wir ja immer noch, okay, in dieser Zeile gibt es
jetzt unseren Eintrag j, also aj und bj, und die beiden sind
unterschiedlich.
Dann definieren wir uns jetzt als nächstes die Variable alpha.
Und alpha ist einfach die Summe von unserer, von der Zeilenweisen oder
der Matrixvektor-Multiplikation, außer für unseren Eintrag y.
Und auch hier wieder, das definieren wir dann analog mit beta für
unsere Matrix b.
Wir kommen gleich darauf, warum das dann schön funktioniert.
Was wir jetzt quasi sagen können, ist dann, dass die Multiplikation
von der i-ten Zeile, also klein a, mit unserem Vektor r gerade alpha
plus aj mal rj ist, weil das ist ja der einzige Eintrag, der uns quasi
bei dieser Multiplikation oder bei diesem rechten Schritt noch fehlt.
Und analog machen wir das gleiche mit b.
Hier sollte allerdings beta und nicht alpha stehen.
Okay, so.
Und jetzt wissen wir ja, okay, unser Algorithmus gibt genau, dann
fällt schließlicherweise korrekt aus, wenn jetzt bei a r und b r das
gleiche rauskommt.
Das heißt, wir schauen uns jetzt einfach an, wann ist die Differenz
von a r und b r null.
Dafür hier nochmal ein bisschen ausmultipliziert, ausgeklammert, dass
das Ganze das gleiche ist wie alpha minus beta plus aj minus bj mal
rj.
Und um jetzt eine Bound dafür zu bekommen, können wir quasi erstmal
alle anderen Werte von unserem Vektor, also r1, bis j minus 1 und dann
wieder von j plus 1 bis n einfach mal festlegen.
Das heißt, wir fixieren die einfach.
Insbesondere haben wir dann nur noch, oder wir haben allgemein nur
zwei Möglichkeiten für den Wert von rj, damit wir quasi
fälschlicherweise korrekt ausgeben.
Also wir können ja nur für rj 0 oder 1 wählen.
Und insbesondere können wir quasi zeigen, dass die Gleichheit bei
maximal einer von diesen beiden Möglichkeiten richtig ist.
Und das seht ihr quasi in diesem rechten Schritt hier.
Das ist einfach Wahrscheinlichkeit, dass a r minus b r gleich 0 ist,
lässt sich dann mit Hilfe von dieser Zeile hier umformen, dass rj
gerade alpha minus beta durch aj minus bj ist.
Und da diese Gleichheit nur für maximal einer von den beiden Werten
für rj gelten kann, ist diese Wahrscheinlichkeit hier quasi immer
kleiner gleich 1,5.
Und damit haben wir quasi gezeigt, dass wenn x mal y ungleich z ist,
haben wir mit Wahrscheinlichkeit oder gibt unser Algorithmus mit
Wahrscheinlichkeit kleiner gleich 1,5 trotzdem noch fälschlicherweise
korrekt aus.
Hat jemand eine Idee, wie man diese Fehlerrate jetzt quasi noch weiter
senken kann?
Ja,
okay, genau.
Die Antwort war, man kann das Ganze einfach mehrmals ausführen.
Und zwar ist es genau das, was hier beim Probability Boosting
passiert.
Was wir machen ist, wir wiederholen diesen Algorithmus einfach k mal
und wählen jedes Mal einen unterschiedlichen Zufall.
Also unser Vektor r sieht einfach jedes Mal ein bisschen anders aus.
Und auch hier gilt, ein Test liefert falsch, wenn a mal b ungleich c
ist.
Und entsprechend liefern alle Tests korrekt.
Die Wahrscheinlichkeit, dass ein Test jetzt fälschlicherweise korrekt
ausgibt, ist kleiner gleich 1,5.
Und das heißt, die Wahrscheinlichkeit, dass alle Tests korrekt jetzt
liefern, obwohl die beiden Matrizen unterschiedlich sind, ist dann
kleiner gleich 1,5 hoch k.
Was daran extrem schön ist, ist, dass wir das Ganze quasi nur einen
konstanten Faktor k mal öfters ausführen müssen.
Und wir kriegen aber trotzdem einen exponentiell kleineren Fehler.
Hat noch jemand eine andere Idee, wie man 0 und 1 senken kann?
Nein?
Okay.
Eine andere Möglichkeit, den Fehler zu senken, wäre einfach, dass wir
einen anderen Körper für unseren Zufallsvektor r nehmen.
Das heißt, wir erlauben nicht nur 0 und 1, sondern 0, 1 und 2.
Und dadurch, dass wir eine größere Möglichkeit an Werten haben,
kriegen wir dann hier nicht mehr ein Halb raus, sondern ein Drittel
oder sonst was.
Das ist auch eine schöne Möglichkeit, um die Fehlerschranke
runterzudrücken.
Kommen wir jetzt zum zweiten Beispiel und das ist der Coupon
-Kollektor.
Und zwar ist es jetzt hier so formuliert, ihr habt quasi die Müsli
-Packungen und in jeder von diesen Müsli-Packungen ist eine zufällige
von N Sammelkarten drin.
Und ihr fragt euch jetzt, wie viele Müsli-Packungen muss ich essen, um
alle Karten mindestens einmal zu haben.
Auch hier können wir das Ganze wieder mit Hilfe von Zufallsvariablen
definieren.
Und zwar sagen wir jetzt als erstes, dass x die Anzahl der Packungen
ist, bis wir mindestens eine von jeder Karte haben.
Und was wir dann sagen können ist, dass das ja einfach die Summe von
Zufallsvariablen x i ist, wobei x i jeweils die Anzahl an Packungen
ist, die ich quasi brauche, um eine neue Karte zu kriegen.
Das heißt, ich habe schon i minus 1 Unique-Karten.
Wie viele Packungen muss ich jetzt noch haben, bis ich dann i Karten
habe?
Und was dann relativ einleuchtend sein sollte, ist, dass es quasi
geometrisch verteilte Zufallsvariablen sind.
Die Wahrscheinlichkeit hier, die ihr seht, ist einfach, okay, ich habe
i minus 1 Karten, habe ich schon.
Das heißt, die Wahrscheinlichkeit dafür, dass ich jetzt ein Duplicate
ziehe, ist einfach i minus 1 durch n.
Und das Gegenereignis dazu ist dann quasi, okay, wie wahrscheinlich
ist es, dass ich eine neue Karte ziehe?
Und das ist dann einfach 1 minus i minus 1 durch n.
Für den Erwartungswert von so einer geometrisch verteilten
Zufallsvariable gibt es dann entsprechende Formeln und man kann halt
zeigen, dass das gerade n durch n minus i plus 1 ist.
Um jetzt rauszufinden, wie viele Packungen wir insgesamt brauchen,
können wir dann die Linearität des Erwartungswertes ausnutzen.
Das heißt, wir sagen einfach, dass e von x ist das gleiche wie der
Erwartungswert von der Summe der x i.
Dann können wir die Summe rausziehen und erhalten halt die Summe der
Erwartungswerte der einzelnen x i.
Dann setzen wir in die Formel die geschlossene Beschreibung von
unserem Erwartungswert für die x i einfach ein und wir sehen, mit ein
bisschen Umformen kommt hier dann raus, dass gerade n mal die Summe
von i gleich 1 bis n, 1 durch i ist.
Die Frage ist jetzt, was ist das hier für eine Funktion?
Hat irgendeiner eine Idee?
Okay, ich habe nicht alles verstanden, aber harmonische Reihe war auf
jeden Fall richtig.
Genau, harmonische Zahlen.
Und zwar schauen wir uns jetzt die entharmonische Zahl an.
Und das ist einfach die Summe von i gleich 1 bis n, 1 durch i.
Und jetzt, was wir quasi zeigen wollen, ist, dass wir das nach oben
beschränken können durch ln n plus 1.
Erstmal zeigen wir, dass ln n eine untere Schranke für diese
harmonische Zahl ist und dafür ist hier einfach mal die Definition
einfach vom Logarithmus aufgeschrieben.
Das heißt, das Integral von x gleich 1 bis n, 1 durch x dx.
Das ist dann die Funktion, die ihr hier in diesem Graphen seht.
Und was wir jetzt, also was man halt grafisch relativ leicht sieht
hier jetzt, ist, dass 1 durch x, beziehungsweise diese Reihe hier,
einfach eine obere Schranke für den Logarithmus ist.
Insbesondere können wir jetzt diese Reihe oder diese Approximation
nehmen und einfach das ganze 1 nach links verschieben.
Das heißt, wir fangen nicht mehr bei i gleich 1 an, sondern bei i
gleich 2 und kriegen dadurch quasi noch eine untere Schranke für den
Logarithmus hin.
Wie kommen wir dann hier auf ln n plus 1?
Naja, wir haben hier unser... wir fangen hier bei i gleich 2 an.
Für i gleich 1 ist einfach 1 durch i 1.
Und deshalb können wir sagen, dass ln n immer kleiner gleich h von n
ist, nach dem Ding hier.
Und zudem h von n, oder hn, immer kleiner gleich ln n plus 1 ist, mit
Hilfe von dieser unteren Abschätzung hier.
Das heißt, für den Coupon-Collector gilt dann, wir haben n mal hn und
das lässt sich nach oben abschätzen durch n ln n plus n.
Das heißt, so viele Müsli-Packungen müsst ihr quasi kaufen, um alle
Sammelkarten zu kriegen.
Eine Variation von dem Ganzen, was dann vielleicht noch ein bisschen
realitätsnäher ist, ist, dass ihr jetzt nicht nur eine Sammelkarte pro
Müsli -Packung habt, sondern stellt euch vor, ihr spielt irgendein
neues Spiel, freut euch richtig drauf und dann seht ihr, ja, es gibt
Lootboxen, geil.
Und die Frage ist jetzt einfach, wie viele Lootboxen müsst ihr kaufen,
um alle Items einmal zu kriegen.
Und eine entsprechende Aufgabe gibt's dann wahrscheinlich nächste
Woche auf dem Übungsblatt, wenn ihr das mal ausrechnen könnt.
So, das war's soweit zu randomisierten Algorithmen.
Machen wir jetzt noch ein paar Erläuterungen zu External-Memory
-Themen.
Insbesondere nochmal kurz als Wiederholung unser Speichermodell, das
in der Vorlesung auch immer wieder drankommt.
Und zwar ist es inspiriert durch das Parallel-Disk-Modell von Vita und
Shriver.
Was wir hier quasi haben, ist, wir haben unsere CPU, wir haben einen
Hauptspeicher der Größe M und wir haben bis zu D Disks, oder können
theoretisch auch unendlich Disks sein, auf die wir zugreifen können.
Die einzige Einschränkung, die wir eigentlich haben, ist, dass der
Zugriff immer in Blöcken der Größe B vonstatten gehen muss.
Und was unser Ziel dann quasi ist, ist die Anzahl der Blockzugriffe zu
minimieren.
Das heißt, wir wollen irgendwie Daten in einem Block rausholen aus
unserem Speicher, die in irgendeiner Form so miteinander
zusammenhängen, dass unser Algorithmus das ausnutzen kann.
Dieses Muster, oder dieses Parallel-Disk-Model gilt jetzt nicht nur
für Hauptspeicher und irgendwelche Disks, die ihr in eurem Rechner
habt.
Man kann das ganze analog noch machen.
Man hat mehrere unterschiedliche Hauptspeicher oder man hat noch einen
Cache, dann gilt einfach das gleiche.
Ihr habt schnellen Zugriff auf den Cache und der Hauptspeicherzugriff
ist quasi schon wieder Größenordnungen langsamer als dieser Cache
-Zugriff.
Und ihr könnt auch wieder nur Blöcke, hier ist es jetzt der Größe B2,
von eurem Cache in den Hauptspeicher übertragen.
Um das auch nochmal ein bisschen anschaulicher zu machen, sind hier
ein paar Zahlen.
Und zwar seht ihr hier die Zeit, die unter anderem ein CPU-Cycle
braucht, was dann 0,3 Nanosekunden sind.
Und das ganze quasi normiert auf diese Zeit.
Das heißt, wir sagen jetzt, ein CPU-Cycle kostet eine Sekunde.
Dann kostet euch ein Cache-Zugriff schon mal drei Sekunden und ein
Zugriff in den Hauptspeicher quasi sechs Minuten.
Je nachdem, was ihr für eine Platte in eurem Rechner habt, SSD oder
eine gute alte Rotational Disk, dauert es dann schon bis zu zwölf
Monaten.
Und wenn ihr jetzt davon ausgeht, dass ihr in eurem Algorithmus
irgendeinen Fehler macht und ihr euer System neu starten wollt, dann
braucht es bis zu 32 Millenia.
Nur um ein bisschen zu zeigen, warum das wichtig ist, dass man quasi
External -Memory-Algorithmen hat, die die Speicherhierarchie effizient
ausnutzen.
So, jetzt ist IO-effizientes Design, aber nicht nur wichtig, wenn ihr
quasi eine Speicherhierarchie habt, sondern auch bei Algorithmen, die
zum Beispiel einfach in eurem Hauptspeicher laufen.
Das Beispiel hier sind jetzt kürzeste Wege auf Straßennetzwerken, zum
Beispiel auf dem Europagraphen.
Dann könnt ihr beispielsweise Dijkstra verwenden, der halt annähernd
linear ist und das Ganze dauert dann ungefähr drei bis fünf Sekunden.
Alternativ könnt ihr auch eine Breitensuche nehmen, das dauert dann
ungefähr zwei Sekunden.
Wenn ihr das aber richtig macht, dann geht das in unter 0,2 Sekunden.
Und zwar gibt es da ein Paper zu, der Algorithmus heißt Fast und im
Endeffekt machen die ein paar Vorberechnungen und sind dann in der
Lage, einen kürzesten Wegebaum aufzubauen mit Hilfe von einem linearen
Scan.
Das heißt, sie müssen nur noch einmal über ihre Knoten drüber und
haben dann ihren Baum.
Der Vorteil davon ist, dadurch, dass die quasi nacheinander oder einen
linearen Scan machen, kann man immer Blöcke, beispielsweise von
irgendeinem Array, in den Cache laden und einfach die Daten aus dem
Cache komplett durchgeben, bevor man dann den nächsten Block reinlädt.
Und das Ganze ist extrem effizient und wie ihr seht, gibt das mehr als
einen Faktor von 10 in der Praxis, wenn man sowas beachtet.
Ja, eben strukturierter Zugriff, wichtiges Designprinzip, nicht nur
für Hauptspeicher und Disks, sondern für jegliche Art von Algorithmen
eigentlich.
So, dann schauen wir uns noch kurz an, wie man in einem halbwegs
realistischen Szenario jetzt die Blockgröße wählen sollte.
Und zwar gibt es unterschiedliche Einflussfaktoren für die Blockgröße.
Zum einen tseq, das ist einfach die Zeit, die euer Lese- bzw.
Schreibkopf braucht, um den entsprechenden Block im Memory zu finden.
Und außerdem habt ihr noch quasi eine maximale Bandbreite, mit der ihr
Daten schreiben und lesen könnt.
Das Ganze ergibt dann eine Lesedauer t und das ist einfach tseq plus b
durch bmax, wobei b die Größe von einem Block ist.
Um das Ganze jetzt anschaulicher zu machen, haben wir jetzt hier ein
RAM -Beispiel.
Da ist es so, da braucht tseq ungefähr 30 Nanosekunden und ihr habt
eine maximale Bandbreite von 25 Gigabyte pro Sekunde.
Außerdem habt ihr in einer Zeile 128 Blöcke beispielsweise.
Und das Ziel ist jetzt, wir wollen 95% Auslastung der Bandbreite
haben, wenn wir einfach nur sequentiell lesen.
Wie groß müssen dann unsere Blöcke sein?
Das Ganze kann man dann einfach durchrechnen.
W ist jetzt quasi eure effektive Bandbreite.
Das ist dann einfach die Blockgröße geteilt durch die Lesedauer, die
ihr habt.
Dann setzt ihr das Ganze da ein und sagt halt, dass es 95% von eurer
maximalen Bandbreite sein soll.
Und dann kommt man hier in dem Beispiel jetzt eben auf 111 Byte, die
ein Block optimalerweise haben sollte.
Jetzt steht hier zwar Feierabend, aber wir machen noch ganz kurz eine
Folie zu IO-effizientem Design.
Externes Sortieren mache ich dann heute nicht mehr, das machen wir
dann nächstes Mal.
Und zwar hatten wir jetzt kurz Zugriffsmuster.
Einfach hier nochmal als Gegenüberstellung, wenn ihr jetzt quasi
einfach die ganze Zeit Random Access auf irgendwelche Elemente macht,
dann kann es halt sein, dass ihr jedes Mal einen Block lesen, wieder
schreiben müsst, wieder lesen, wieder schreiben.
Und das Worst Case habt ihr halt O von N IOs, was extrem langsam ist.
Vergleich dazu nochmal der lineare Scan mit Blockgröße B.
Hier schafft ihr es halt einfach in O von N durch B IOs quasi ein
komplettes Array zu scannen.
Für Sortieren hattet ihr dann in der Vorlesung als Schranke für die
IOs zwei N durch B mal 1 plus logarithmischen Term.
Hier ist es vor allem wichtig, für IO-effizientes Design lokale
Kriterien zu exploiten.
Das hatte ich vorhin schon mal kurz erwähnt.
Und zwar wollt ihr, dass die Blöcke, die ihr in euren Speicher ladet,
so aufgebaut sind, dass ihr beispielsweise schon eine teilsortierte
Folge habt oder irgendwas, was ihr ausnutzen könnt, um euren
Algorithmus effizienter zu machen, dass ihr nicht die ganze Zeit
irgendwelche random Daten aus eurem Speicher laden müsst, um
irgendwelche Vergleiche zum Sortieren durchzuführen.
Insbesondere ist Sortieren auch ein wichtiger Schritt, um dann einen
linearen Scan zu machen.
Für manche Algorithmen müsst ihr einfach sicherstellen, dass um das
quasi mit einem Scan machen zu können, muss die Folge schon sortiert
sein.
Was ihr dann vorhin noch gesehen habt, waren Prioritätswarteschlangen.
Auch hier, das Ganze geht ungefähr in Sort and IOs.
Sort and ist einfach der Term, der hier oben steht.
Insbesondere werden Prioritätswarteschlangen häufig dafür verwendet,
quasi sowas wie eine Warteliste in External Memory zu implementieren.
Das heißt, ihr habt jetzt ein Element, aber ihr wollt beispielsweise
irgendwas von dem Element ausnutzen und ihr wollt es erst später dann
in die Platte schreiben mit Elementen, die irgendeinen lokalen
Zusammenhang mit diesem Element haben.
Und dann sagt ihr quasi, okay, ich will das nicht jetzt in den
Speicher schreiben, sondern erst viel später, dann packt ihr das in
die PQ und macht dann eure Prioritätsfunktion so, dass ihr im
Endeffekt Elemente da rauskriegt, die irgendwie miteinander
zusammenhängen.
Und dann gibt es eben noch Stacks und Queues.
Habt ihr auch in der Vorlesung schon gesehen.
Aber ich glaube, das war's dann für heute.