Ja, schönen guten Tag.
Lassen Sie uns mal in der ersten Stunde noch mit der Vorlesung ein
Stück weitermachen.
Immer noch Online-Algorithmen.
Und das Kapitel werden wir auch heute noch nicht zu Ende bekommen, da
machen wir dann also nächsten Montag noch weiter.
Wenn alles gut geht, schaffen wir das, was hier jetzt noch übrig ist,
zum Thema Speicherverwaltung.
Also, großer langsamer Speicher, kleiner schneller Speicher.
Wenn die Anforderung kommt, eine neue Seite in den schnellen Speicher
zu laden, die da nicht schon ist, dann muss man was anderes verdrängen
und die Frage ist, was?
Das Beste, was man erreichen kann, die kleinste Anzahl Seitenfehler
kriegt man, wenn man in die Zukunft guckt und das rauswirft aus dem
Cache, was eben am spätesten wieder gebraucht wird.
Aber das ist dann kein Online-Algorithmus.
Das Letzte, was wir gestern bewiesen haben, war deterministisch.
Das Beste, worauf man überhaupt hoffen kann, ist, dass man Online
-Cache -kompetitiv ist.
Und klein K ist immer die Größe des Caches, des schnellen Speichers.
Das ist jedenfalls eine untere Schranke, das klein K.
Und jetzt im nächsten Abschnitt wollen wir als erstes uns angucken,
dass zum Beispiel dieser deterministische Online-Algorithmus, der LRU
heißt, Least Recently Used, dass der K-kompetitiv ist.
Und besser geht's nicht, also der ist optimal.
Ein Beispiel, damit Sie so ein bisschen ein Gefühl dafür kriegen, wie
das funktioniert, das ist dann auch gleich bei dem Beweis nochmal
witzig.
Also stellen Sie sich vor, Sie haben hier so eine Anforderungsfolge,
ein Stückchen ist schon abgearbeitet, sagen wir mal bis einschließlich
hier zu dieser Anforderung von irgendeiner Seite 1.
Und nehmen wir an, der Cache hat Größe 3, dann zu dem Zeitpunkt, wenn
ich soweit bin, was ich im Cache habe, sind halt die drei Seiten, die
zuletzt angefordert wurden, also 2, 1 und 4.
Und jetzt stellen Sie sich vor, als nächstes würde eine Seite 3
angefordert, also die hier sind erledigt und jetzt kommt hier die 3.
Ist nicht im Cache, es muss etwas aus dem Cache entfernt werden, die
Frage ist was.
Und was macht least recently used, das guckt für jede dieser Seiten,
2, 1 und 4, die im Cache sind, wie lange ist es denn her, dass die zum
letzten Mal angefordert wurden.
Also für 2 war das hier, für 1 war das hier und für 4 war das hier.
Und was liegt am längsten zurück?
Die Anforderung der 2 und deswegen ist das dasjenige Element, das man
rauswirft aus dem Cache.
Also das fliegt jetzt raus und stattdessen kommt die 3 rein, die man
gerne möchte.
Also dann haben wir hier 3, 1 und 4 im Cache.
Dann ist das auch erledigt, dann stellen Sie sich vor, als nächstes
kommt die Anforderung Seite 4.
Das ist wieder ganz prima, denn 4 ist im Cache drin, muss man nichts
tun, alles ist gut.
Okay, haben wir das auch erledigt.
Immer noch 3, 1 und 4 im Cache.
Und dann meinetwegen kommt wieder Anforderung 2.
Das haben wir gerade rausgeworfen, das ist jetzt nicht mehr im Cache.
Wieder das gleiche Spiel für die Seiten, die gerade im Cache sind.
Wann wurden sie denn zuletzt angefordert?
Achso, das ist jetzt natürlich ein bisschen blöd gemalt, aber ich habe
auch nicht daran gedacht, dass ich das anders machen wollte.
Also, wann wurden die zuletzt angefordert?
Die 4 hier, die 1 da und die 3 da.
Und was liegt am weitesten zurück?
Ja, das ist die Anforderung von der 1, die anderen kamen später.
Also wird man jetzt die 1 rauswerfen, wenn man hier die 2 bearbeitet
und stattdessen die 2 in den Cache holen.
Und dann hat man 3, 4 und 2 und so weiter.
Also man guckt immer von den Seiten, die im Cache sind, wann wurden
die zuletzt angefordert und welche Anforderung ist die, die am
längsten zurückliegt und das Element fliegt raus.
Jetzt, na, da kommen wir später drauf zurück.
Gut, jetzt gehen wir erstmal wieder hier.
So, und was wir jetzt beweisen wollen, wenn man das so macht, dann
schlimmstenfalls produziert man k-mal so viele...
Ich zögere, weil ich jetzt gleich was sagen werde, was nicht ganz
richtig ist.
Schlimmstenfalls k-mal so viele Cache Misses, wie der optimale
Algorithmus, der in die Zukunft gucken kann.
Nicht ganz genau genommen wollen wir zeigen, LRU ist k-kompetitiv.
Das bedeutet, die Anzahl Cache Misses von LRU für jede
Anforderungsfolge ist höchstens k-mal Anzahl Cache Misses des
optimalen Algorithmus plus vielleicht noch eine konstante BR, also so
einen konstanten additiven Term erlauben wir uns und den brauchen wir
jetzt auch.
Also hier steht nicht strikt k-kompetitiv.
So, was ist die Idee?
Also, wir geben eine beliebige Anforderungsfolge, das muss für alle
gelten.
Wir zerhacken die so ein bisschen in Teile.
Die heißen Phasen.
Und zwar wie folgt.
Also, die erste Phase beginnt mit der ersten Anforderung.
Und ist möglichst lang so, dass innerhalb dieser ganzen Phase nur k
-verschiedene Seiten angefordert werden.
Manche können ja mehrfach angefordert, also eine Seite kann ja
mehrfach angefordert werden, deswegen das können mehr als k
-Anforderungen sein.
So wie wir gerade irgendwie zweimal die Anforderung 4 schon hatten in
der Anforderungsfolge.
So also möglichst lang, so dass in der Phase k nur k-verschiedene
Seiten angefordert werden, aber möglichst lang.
Das ist die erste Phase und da wo eine Phase aufhört, fängt sofort die
nächste an.
Ab da dann auch wieder ein möglichst langer Abschnitt, in dem nur k
-verschiedene Seiten angefordert werden.
Da ist dann die zweite Phase zu Ende und ab da dann die dritte und so
weiter.
Also möglichst lange Phasen, aber innerhalb jeder Phase nur
Anforderungen für k-verschiedene Seiten.
Vielleicht mehrfach, im Allgemeinen öfters.
Und dann muss man noch so ein bisschen was anderes betrachten.
Also stellen Sie sich vor, wir haben jetzt hier so eine
Anforderungsfolge.
Dann haben wir die also jetzt irgendwie in Phasen eingeteilt.
Die sind unterschiedlich lang, je nachdem wie häufig Elemente mehrfach
angefordert wurden.
Hier Phase 0, Phase 1, Phase 2, Phase 3.
Und was wir jetzt auch noch betrachten, sind so Abschnitte, so ähnlich
wie die Phasen, aber um 1 nach rechts versetzt.
Also das wäre dann so von ein Element weiter rechts bis hier.
Das hier, und das ist dann Q0, das ist eine bessere Idee.
Also das hier sind die P's und dann so 1 versetzt, das sind die Q's.
Also jedes QI ist genauso lang wie das PI, aber 1 weiter rechts.
So und jetzt zeigen wir das folgende.
Wenn Sie irgendeine Phase PI angucken, dann in dieser Phase LRU hat
höchstens klein k Cache Misses.
Das gilt für jedes PI.
Und wenn Sie die QI angucken, die also fast das gleiche sind, mit
Ausnahme ganz vorne irgendwie.
Für jedes QI wollen wir uns überlegen, da hat der optimale Algorithmus
LFD, der Offline-Algorithmus, mindestens 1 Cache Miss.
Also in jedem PI LRU hat höchstens k und in jedem QI LFD hat
mindestens 1.
Und wenn Sie sich jetzt vorstellen, dass man insgesamt klein m Phasen
hat, dann hat LRU in jeder von den m Phasen jeweils höchstens k Cache
Misses, also insgesamt höchstens k mal m.
Wir ignorieren jetzt hier vielleicht irgendwelche Kleinigkeiten mit
der letzten Phase oder so.
Und andererseits, in jedem QI hat LFD mindestens 1 Cache Miss.
Und weil aber das irgendwann zu Ende ist, das letzte QI ist irgendwie
ein bisschen komisch, da ignorieren wir ein bisschen was.
Da müssen wir was weglassen, deswegen, abgesehen vom letzten, in jedem
QI hat LFD mindestens 1 Cache Miss, also insgesamt hat LFD mindestens
m -1 Cache Misses.
Und wenn wir das beides bewiesen haben, dann offensichtlich gilt, dass
die Kosten von LRU höchstens k mal die Kosten von LFD sind plus k.
Und da ist dieser additive Term, den wir gut brauchen können.
Um da so Randfälle am Anfang, am Ende, wo vielleicht irgendwas nicht
so ganz passt, zu sagen, okay, das können wir unter den Tisch fallen
lassen.
So.
Also, wenn man diese beiden Punkte bewiesen hat, dann ist man fertig,
ja?
Also muss man sich diese beiden Dinge überlegen.
LRU hat höchstens k Cache Misses in der Phase und LFD in jedem QI
mindestens eine.
Gut.
LRU hat höchstens k Cache Misses in einer Phase.
Wieso?
Also in so einer Phase per Definitionen kommen ja nur Anforderungen
von k verschiedenen Seiten vor.
Wenn jetzt da LRU in einer Phase mehr als k Cache Misses hätte, dann
gäbe es also eine Seite, die zweimal angefordert wird und zweimal LRU
hat ein Cache Miss.
Gut.
Also, irgendwann der erste Cache Miss für eine Anforderung dieser
Seite.
Und wir haben es mit LRU zu tun.
Damit jetzt irgendwann später die gleiche Seite nochmal angefordert
wird und wir haben wieder ein Cache Miss, dann muss die Seite, die da
vorne angefordert wurde und in den Cache reinkam, muss wieder
zwischenzeitlich rausgeflogen sein.
Es sind also andere Seiten angefordert worden und das hat dazu
geführt, dass irgendwann die Seite, die vorhin zum ersten Mal mit
einem Cache Miss reingeladen wurde, wieder rausflog.
Und man wirft aber immer das raus, was am längsten in der
Vergangenheit geladen wurde.
Und jetzt laden Sie also diese Seite, die dann später noch ein zweites
Mal ein Cache Miss angeblich verursacht.
Und dann laden Sie eine neue Seite, da fliegt die noch nicht raus, die
ist ja gerade erst angefordert worden.
Dann irgendwann kommt die zweite neue Seite, da fliegt die auch noch
nicht raus, die ist ja erst vorgestern angefordert worden.
Und bis die rausfliegt, müssen Sie k andere Seiten anfordern.
Dann fliegt die Seite erst raus, die Sie dann angeblich nochmal
anfordern, damit sie wieder reinkommt in den Cache und nochmal ein
Cache Miss macht.
Dann haben Sie da k andere Seiten angefordert und die Seite nochmal,
sind k plus 1 verschiedene Seiten, die Sie angefordert haben in einer
Phase.
Und das gibt es nicht, es gibt nur k verschiedene Seiten in jeder
Phase.
Also, das kann einfach nicht sein, in einer Phase, in der nur k
verschiedene Seiten angefordert werden, in irgendeinem Abschnitt, LRU
hat garantiert höchstens k Cache Misses.
Einen solchen Algorithmus nennt man konservativ, da kommen wir gleich
nochmal drauf zurück.
So, also in jedem PI, LRU hat höchstens k Cache Misses.
Und was ist mit LFD?
Na, da guckt man sich das QI an, um 1 versetzt.
In PI gibt es k verschiedene Seiten, die der Reihe nach zum ersten Mal
auftreten.
Die erste lassen wir mal weg.
Und, also angenommen, das sind PI1 bis PIk, das erste lassen wir weg.
Und dafür nehmen wir eben das erste von der nächsten Phase dazu, das
PI plus 1, das erste da.
Das sind k verschiedene Seiten.
Und LFD, am Anfang von Phase I lädt es ja dieses PI1 in den Cache.
Und jetzt kommen also da, dahinter, diese P2 bis PK oben I und das P1
I plus 1, das sind k verschiedene Seiten.
Da muss jetzt irgendwann mal ein Cache Miss passieren.
Spätestens bei dem ersten Element von der nächsten Phase, dass man zu
dem QI dazugeht.
Also hat man auf dieser Länge da in diesem QI garantiert mindestens
einen Cache Miss.
Ja, und das war es, was wir noch zeigen wollten.
Ah, hier unten, oh ja, Sie haben recht.
Also das ist natürlich grober Unfug, das muss ich noch korrigieren,
ja, das ist natürlich LFD.
LFD.
Schnell weg, gut.
Also es gibt ein Algorithmus, z.B.
LRU, der ist k-kompetitiv und auf was besseres kann man
deterministisch gar nicht hoffen.
Aber, das habe ich gestern schon erwähnt, das ist ein bisschen kurios,
denn das k ist die Größe des Caches und das ist irgendwie etwas
merkwürdig.
Je größer der Cache, umso schlechter dieser Quotient im Vergleich zum
optimalen Algorithmus.
Deswegen, was man sich manchmal anguckt, ist die folgende Variante und
da spricht man dann im Englischen von Resource Augmentation und ich
habe gar nicht erst versucht, das irgendwie einzudeutschen.
Und da redet man dann vom HK Seitenwechselproblem, also da ist noch
eine zweite Zahl H im Spiel.
Und was man da macht, ist man sagt, okay, ich habe meinen
deterministischen Online-Algorithmus, der Cache hat Größe k.
Und das vergleiche ich schon mit dem optimalen Algorithmus, aber dem
gebe ich nicht einen genauso großen Cache wie dem Online-Algorithmus,
sondern einen kleineren.
Also das kleine h soll kleiner sein als das kleine k und das ist die
Größe des Caches für den optimalen, für den Offline-Algorithmus.
Und dann guckt man sich an, ja wie ist es denn jetzt im Verhältnis
zueinander.
Und dann kann man nochmal ein bisschen was sehen und denkt, ah ja, das
sieht jetzt nicht mehr ganz so schlimm aus, irgendwie eine vernünftige
Sache.
Und was wir jetzt dann gleich beweisen, ist etwas nicht nur für LRU,
sondern für alle Algorithmen, dazu gehört dann zum Beispiel auch FIFO
und andere, die, wie man sagt, konservativ sind.
Das heißt, genau genommen das folgende, wenn Sie eine
Anforderungsfolge haben, ein Stück, in der höchstens k verschiedene
Seiten vorkommen, dann passieren auch höchstens k Caches.
Sie können ja mal versuchen, sich einen Algorithmus, ach so, ist nicht
so schwierig, aber trotzdem, überlegen Sie mal für irgendeinen anderen
Algorithmus, dass der nicht konservativ ist.
So groß ist die Auswahl ja nicht, was wir so gesehen haben.
Schauen Sie mal, ob Sie einen sehen, der nicht konservativ ist.
So.
Und für diese konservativen, also das ist genau die Eigenschaft, die
wir gerade für LRU auch irgendwie ausgenutzt haben, in einem Abschnitt
mit nur k verschiedenen Anforderungen, wir haben höchstens k Caches.
Und das jetzt in dem Beweis, werden wir das gleich wieder ausnutzen,
das ist auch praktisch schon fast der gleiche Beweis wie vorhin.
Die Behauptung, die Aussage ist nämlich, wenn Sie so einen
konservativen Online-Algorithmus haben, also LRU gehört dazu, FIFO und
noch ein paar, und der Online-Algorithmus hat ein Cache der Größe k
und der Offline-Algorithmus, mit dem Sie sich vergleichen, dem
bestehen Sie nur ein Cache der Größe klein h zu, dann ist der Online
-Algorithmus k durch k minus h plus 1 kompetitiv.
Und ein Fall, den man sich mal angucken kann, den man dann vielleicht
ganz nett findet, der steht da unten in der letzten Zeile.
Stellen Sie sich vor, Sie sagen, der Offline-Algorithmus, der kriegt
nur ein Cache, der halb so groß ist, also h ist k halbe.
Und wenn Sie dann da oben in diesen Bruch für h k halbe einsetzen,
dann kommt da sowas raus wie 2, grob gesagt.
Gut, das heißt, so ein Online-Algorithmus, so ein konservativer, egal
welcher, wenn Sie dem erlauben, doppelt so viel Cache zu haben wie der
Offline -Algorithmus, dann hat er immerhin nicht mehr k mal so viel
Cache, sondern noch zweimal so viel Cache.
Und Offline ist ja auch irgendwie sozusagen, in Anführungszeichen, ein
etwas unfairer Vergleich und dann zu sagen, na gut, dem geben wir dann
dafür halt weniger Cache, ist ja vielleicht nicht ganz unplausibel.
Ja, wie beweist man diesen Satz?
Na fast genauso wie das, was wir eben gesehen haben.
Sie haben diese Anforderungsfolge, Sie hacken sie auf die gleiche Art
und Weise in Phasen, die jeweils maximal lang sind, aber nur k
verschiedene Anforderungen für max k verschiedene Seiten haben, außer
der letzten Phase, da ist vielleicht alles ein bisschen kürzer.
Und QI genauso, Sie nehmen das PI, lassen vorne eins weg und dafür
hinten eins dazu.
So.
Und weil vorausgesetzt wird, der Online-Algorithmus ist konservativ,
wir wissen schon, für jede Phase, der Online-Algorithmus hat maximal k
Cachemisses, weil in jeder Phase nur k verschiedene Seiten angefordert
werden.
So.
Und was ist... ah, da steht jetzt LRU wieder, also hier ist jetzt
gemeint, das ist auch wieder falsch, also hier auch LFD bitte.
So, LFD kommt an.
Man stellt sich vor, die erste Anforderung von der Phase macht er
noch.
Gut.
Das ist dann im Cache.
Und noch irgendwelche anderen h-1 Seiten.
h ist die Größe des Caches von LFD.
In der... jetzt im folgenden werden aber k verschiedene Seiten
angefordert.
Im Cache kann er aber nur h-1 andere halten.
Also die Differenz k-h-1, die sind garantiert nicht im Cache und das
kann gar nicht anders sein, als dass für jede von diesen Seiten ein
Cachemiss passiert.
Bei LFD.
Also garantiert k-h-1 Cachemisses hat man.
Für LFD, nicht LRU, wie da steht.
Und naja, k durch das ist genau der Prozent, der da behauptet wird im
Satz.
Gut.
Und dann ist man fertig.
Bis auf... also ich erlaube mir hier kleine Ungenauigkeiten.
Ja, wie gesagt, die letzte Phase, das muss ja nicht genau vielleicht k
verschiedene Anforderungen... Anforderungen von k verschiedenen Seiten
enthalten und so.
Da ist man so ein bisschen großzügig.
Überlegen Sie sich mal im Zweifelsfall noch zu Hause, dass das nicht
schlimm ist, weil man ja den additiven Term da noch dazu basteln kann.
Gut.
Okay.
Und dann jetzt randomisiert.
Oh, ich bin viel langsamer als gedacht.
Na gut.
Also wir haben gesehen deterministisch, man schafft k-kompetitiv und
besser geht es nicht mit deterministischen Online-Algorithmen.
Und jetzt randomisiert werden wir uns dann einen Algorithmus angucken
und beweisen, der ist zweimal hk-kompetitiv.
Und wem sagt hk etwas?
Karte, harmonische Zahl, Hand hoch.
2,5.
Das ist ein bisschen wenig.
Also, um das einmal hier hingeschrieben zu haben.
hk, das ist die Summe i gleich 1 bis k, der 1 durch i.
Und das ist, wenn man es sich ein bisschen anguckt,
größenordnungsmäßig, log k.
Log k, ja.
So.
Und hier in der Überschrift steht jetzt also schon, dieser
randomisierte Algorithmus ist in irgendeinem Sinn zweimal, also da
steht sowas wie zweimal log k-kompetitiv.
Das ist also deutlich kleiner als das bestmögliche im
deterministischen Fall von k.
Prima.
So.
Darauf wollen wir hinaus.
Dazu muss man sich als erstes mal noch so ein bisschen genauer
angucken, wie definiert man denn c-kompetitiv, wenn man es mit
randomisierten Algorithmen zu tun hat.
Da ist ja die Anzahl Cashmisses wahrscheinlich im Allgemeinen eine
Zufallsvariable.
Das wird nicht immer das gleiche sein.
Und da muss man vielleicht ein bisschen vorsichtig sein, sich
überlegen, was man tut.
Und dann gucken wir uns auf jeden Fall noch den Algorithmus an.
Der ist ganz naheliegend sozusagen.
Und dann kommt die Analyse und die ist nicht mehr ganz so simpel.
Die erstreckt sich über 10 Folien oder so, aber es ist relativ viel
Text.
Und im Vergleich dazu verhältnismäßig wenig Gedanken, bis auf eine
Stelle.
So.
Ja, also wenn man jetzt irgendwie Zufall einbaut in so einen
Algorithmus, der irgendwie einen schnellen Speicher verwaltet, dann
wird er halt für die gleiche Eingabefolge, Anforderungsfolge, mal das
eine, mal das andere machen und sich am Anfang unterschiedlich
verhalten potenziell und deswegen später vielleicht unterschiedlich
viele Cashmisses haben.
Also die Anzahl Cashmisses wird eine Zufallsvariable sein.
Und...
Naja, das naheliegende ist dann halt, sich den Erwartungswert
anzugucken und mit dem zu arbeiten, darüber zu reden.
Also wenn man definiert, was C-kompetitiv ist, dann wird da irgendwie
Erwartungswert auftreten.
Und die Frage ist, wie man das dann macht.
Und es zeigt sich, dass es dann im randomisierten Fall sinnvoll ist,
sich vorzustellen, da ist so ein Widersacher der ein oder anderen Art,
der Anforderungsfolgen produziert, die hoffentlich, also hoffentlich
für den Widersacher, richtig viele Cashmisses produzieren.
Und...
Das passiert dann eben.
Und da ist noch die Frage, womit vergleicht man denn diese Anzahl
Cashmisses, die da jetzt passieren, bei dieser Folge, die der
Widersacher produziert hat.
Womit vergleicht man sich denn?
Und dann gibt es dann das, was im Englischen jedenfalls Oblivious
Adversary und Adaptive Adversary heißt, also im Deutschen vielleicht
unwissender und adaptiver Widersacher.
Der Unterschied ist, also so ein Widersacher, sage ich, hier ist der
randomisierte Algorithmus, gucke ihn dir an, und jetzt mach mal eine
Anforderungsfolge, und zwar bitte der Länge N für irgendein N.
So.
Und der unwissende Widersacher hat nicht mehr eine Information, sieht
einfach den Programmtext und kriegt gesagt, so lange soll die
Anforderungsfolge sein, da muss er jetzt irgendwas sich ausdenken, in
Anführungszeichen.
Und was er aber nicht sieht, der unwissende Widersacher ist, wenn er
jetzt diese Anforderungsfolge, die er da vielleicht so nach und nach
sich ausdenkt, dem randomisierten Algorithmus gibt, was der da
anstellt, welche Zufalls-Bits er würfelt, was der randomisierte
Algorithmus dann tatsächlich zu irgendeinem Zeitpunkt aktuell in
seinem Cash hat, das weiß der unwissende Widersacher nicht.
Man kann sich aber auch vorstellen, das sind dann diese adaptiven
Widersacher, die erzeugen so eine Anforderungsfolge und geben die
sozusagen immer gleich dem randomisierten Algorithmus und sehen,
welche Zufalls-Bits gewürfelt werden, wissen zu jedem Zeitpunkt, was
hat er denn im Cash, und können da natürlich irgendwie Dinge machen,
mit denen auch der randomisierte Algorithmus viel mehr Probleme hat.
Und dann ist aber die Frage, womit vergleichen wir denn jetzt die
Anzeige Cashmisses des randomisierten Algorithmus für eine so ganz
gemein konstruierte Anforderungsfolge?
Und da gibt es dann zwei Varianten von adaptiven Widersachern, die wir
uns jetzt in der Vorlesung hier nicht genauer angucken, aber einfach,
dass das schon mal klar ist.
Bei dem adaptiven Online-Widersacher, also da gibt es jetzt einen
adaptiven Online- und einen adaptiven Offline-Widersacher.
Und bei dem adaptiven Online-Widersacher sagt man, ja okay, du siehst
zwar die Zufalls-Bits und kannst da was ganz Gemeines machen für den
randomisierten Online-Algorithmus, aber selber musst du deine
Anforderungsfolge auch online irgendwie bearbeiten und selber auch
irgendeine Art von Cash-Verwaltung machen.
Wie ist egal, aber es muss auch online sein.
Das heißt, da besteht dann eine gewisse Chance, dass die Anzeige
Cashmisses des randomisierten Algorithmus vielleicht nicht absurd viel
größer ist, als die des adaptiven Online-Widersachers.
Beim adaptiven Offline-Widersacher sagt man, ja der darf das jetzt
alles genau angucken und was ganz kompliziertes produzieren.
Und die Kosten für den Offline-Widersacher, ja da nimmt man einfach
nur die optimalen Kosten.
Man kann in die Zufung gucken, man hat erstmal alles erzeugt und dann
macht man das so, wie es optimal ist.
Da hat man dann den Eindruck, da hilft dann wahrscheinlich
Randomisierung überhaupt nicht mehr und das ist auch tatsächlich so.
Also da hat man dann völlig verloren.
Gegen adaptive Offline-Widersacher.
Aber das gucken wir hier nicht an, wir gucken uns nur unwissende
Widersacher an.
Deswegen der untere Teil hier auf der nächsten Folie, der steht nur
der Vollständigkeit halber da, damit Ihnen klar ist, da muss man auch
irgendwas machen.
So.
Und gegen unwissende Widersacher sagt man dann, ein randomisierter
Algorithmus ist zäh kompetitiv.
Dann sieht es so ähnlich aus, wie im deterministischen Fall.
Wenn für jede Anforderungsfolge der Länge n gilt, dass die Anzahl der
Cash Misses des randomisierten Algorithmus, das ist das was hier Fr
von R1 bis Rn heißt, also davon zahlt der Erwartungswert.
Höchstens 10 mal die optimalen Kosten sind.
Optimal heißt jetzt hier LFD.
Plus so ein konstanter additiver Term, klein b, der aber bitte von der
Anforderungsfolge, von der Länge der Anforderungsfolge unabhängig ist.
Und der unwissende Widersacher, der wird gegeben dem Programmtext und
das n immer die gleiche Eingabefolge produzieren.
Er hat ja nur das, kein Zufall ist im Spiel.
Bei adaptiven Widersachern, die sehen die Zufallsbits, in Abhängigkeit
von den Zufallsbits erzeugen sie vielleicht auch unterschiedliche
Folgen.
Da ist dann auch das, was der adaptive Widersacher produziert, eine
Zufallsvariable und so.
Da wird dann alles noch ein bisschen komplizierter, aber das muss uns
hier nicht interessieren.
So.
Und dann kommen wir jetzt zu diesem Algorithmus.
Ja, wenn Sie sich jetzt mal überlegen, also Sie haben sowas gesehen
wie LRU oder so, ja?
Also man muss halt immer irgendetwas rauskicken aus dem Cache im
Zweifelsfalle.
Und man möchte natürlich vermeiden, dass man was rauswirft, was man
gerade erst reingeholt hat in den Cache.
Das hat auch gesprochen.
Was könnte man da tun?
Ja, weiß ich nicht.
Haben Sie einen Vorschlag?
Ah, ok.
Ok.
Ah, das wäre also jetzt tatsächlich noch so relativ nah an LRU in dem
Sinne.
Also ich weiß nicht, ob Sie alle gehört haben.
Die Idee ist, welches Element man hinauswirft, macht, also das hängt,
jedes Element das im Cache ist, hat eine gewisse Wahrscheinlichkeit
hinausgeworfen zu werden und die ist umso größer, je länger es schon
im Cache ist.
Habe ich das richtig verstanden?
Ja.
Und das kann man jetzt noch ein bisschen vereinfachen sozusagen.
Und dann ist man mehr oder weniger bei diesem Algorithmus.
Der geht so, also Sie haben die Cache-Einträge und so zusätzlich zu
jedem Cache-Eintrag ein Bit.
Dann stellen Sie sich vor, die Bits sind am Anfang alle 0.
Und jetzt immer wenn etwas in den Cache an eine Stelle kommt, kommt es
da rein und das Bit wird auf 1 gesetzt.
Und ja, jetzt irgendwann, das ist erstmal der einfache Fall,
irgendwann kommt es zu einem Cache-Miss und man muss etwas
hinauswerfen.
Und was wirft man, um ein Element zu finden, das man hinauswirft,
guckt man sich nur die Einträge an, wo das Bit noch 0 ist.
Die mit 1 sind die, die zuletzt reingeladen wurden irgendwie und die,
wo das Bit noch 0 ist, das ist irgendwie länger her.
Und von denen sucht man gleichverteilt 1 aus, irgendeines zufällig.
Das, was da ist, wirft man raus, macht das rein, was man haben will
und setzt das Bit auf 1.
Also wenn etwas nicht im Cache ist, man sucht sich unter den
Einträgen, die noch ein 0, das Bit auf 0 haben, gleichverteilt 1 aus
und das wirft man raus.
Wenn es überhaupt keinen Eintrag im Cache mehr gibt, wo das Bit 0 ist,
wenn die alle auf 1 sind, dann setzt man sie alle wieder auf 0.
Und dann fängt sozusagen eine neue Phase an.
Also egal, ob das Element, was man haben will, schon im Cache ist oder
man es explizit reinholt, die Stelle wird auf jeden Fall mit einem 1
-Bit markiert.
Und deswegen dann erstmal in Ruhe gelassen, weil die Auswahl für zu
entfernende Elemente immer unter denen ist, die das Bit auf 0 haben.
Und so nach und nach werden es immer mehr 1en und dann irgendwann
alles wieder auf 0.
Behauptung, dieser Algorithmus ist zweimal HK, also grob gesagt
zweimal Logarithmus K kompetitiv.
Das ist also dann ein deutlich kleinerer Faktor als das K, was man
bestenfalls deterministisch erreichen kann.
So.
Und das muss man dann noch beweisen.
Und das werde ich in den letzten 8 Minuten sicherlich nicht
hinkriegen, aber fangen wir mal langsam an.
Also, bitte?
Ah, ich habe mehr als 8 Minuten, ist auch recht.
Gut.
Ja, also wir haben eine Anforderungsfolge.
Die zerhacken wir auch wieder in Teile, die nennen wir auch wieder
Phasen.
Und eine Phase fängt immer dann an, wenn man bei den Cache-Einträgen
überall das Bit auf 0 setzt, weil überall eine 1 ist und man hätten
gerade ein Cache miss.
Und OBDA, gleich am Anfang passiert das, ja.
Ne, sind alle Bits auf 0, ja.
Und dann eben maximal lang, ja.
Also immer bis das nächste Mal alles auf 0 gesetzt wird.
Das ist eine Phase.
Ähm.
Ich weiß nicht, warum ich hier immer OPT statt LFD geschrieben habe,
aber gut.
So.
Um das fair zu halten, stellen wir uns vor, der randomisierte Marke
-Algorithmus und der optimale Algorithmus LFD haben am Anfang, wenn es
losgeht, die gleichen Cache-Inhalte, ja, irgendwie faire
Voraussetzungen.
Und wir fangen mit einem Cache miss an.
Und dann, da der Cache Größe K hat, so eine Phase, was ist da drin?
Das ist eine möglichst lange Phase, wo maximal K verschiedene Seiten
angefordert werden.
Denn solange das passiert, reichen einem die K-Einträge aus.
Und wenn der K plus erste kommt, alle Bits sind auf 1 gesetzt, dann
ist die Phase zu Ende und die nächste geht los.
So.
Und was ist der Plan?
Wir wollen zeigen, so für jede Phase, da taucht jetzt eine Zahl,
kleine L auf, was das ist, werden wir dann gleich noch festlegen, ja.
Aber mal vorausgesetzt, also das ist irgendwie festgelegt.
Der Plan ist zu zeigen, der optimale Algorithmus, also LFD, in so
einer Phase im Mittel, er hat L halbe Cache Misses.
Und der randomisierte Marker-Algorithmus hat pro Phase L mal HK Cache
Misses, höchstens, oder erwartet.
Ja, also der Erwartungswert ist kleiner gleich L mal HK.
Naja, und wenn Sie dann den Quotienten angucken, L mal HK durch L
halbe, dann sind Sie bei diesem 2 mal HK.
Also wenn wir diese beiden Dinge bewiesen haben, dann wissen wir, dass
der randomisierte Marker-Algorithmus 2 mal HK kompetitiv ist.
So.
Fangen wir mal mit dem ersten Teil an.
Der optimale Algorithmus hat eine gewisse Anzahl mindestens L halbe
Cache Misses.
Was ist das L?
Also so eine Phase ist so, die fängt an, wenn alle Bits auf 0 gesetzt
werden von den Cache Einträgen.
Und dann hat man da am Anfang aber natürlich, also die Einträge sind
noch da.
Und wenn jetzt zufällig die erste Anfrage ein Element betrifft, das da
im Cache ist, dann hat man keinen Cache Miss, aber das Bit wird halt
auf 1 gesetzt.
Also die Einträge, die am Anfang, die Elemente, die am Anfang einer
Phase da drin sind, die am Anfang drin sind, die wollen wir veraltet
nennen.
Und die, die nicht drin sind, das kann ja nicht alles im Cache sein,
die wollen wir sauber nennen.
Ja, und ein Element heißt markiert, wenn zu irgendeinem Zeitpunkt das
Bit halt auf 1 gesetzt ist.
Gut.
Was macht der randomisierte Marke-Algorithmus?
Also er, wenn er was aus dem Cache rauswirft, er nimmt immer etwas,
was nicht markiert ist, ja, das Bit ist 0.
Und was da rausgeworfen wird, ist offensichtlich ein veraltetes
Element, ein Element, das am Anfang der Phase drin war, aber jetzt
offensichtlich nicht gerade nicht gebraucht wird oder so und
rausgeworfen wird.
Und das, was dafür reinkommt in den Cache, wird sofort markiert.
Und, ja, wenn Sie ein Element haben, das am Anfang der Phase nicht im
Cache ist, wenn das zum ersten Mal angefordert wird, ja, kommt es halt
rein, hat den Cache-Miss verursacht, weil es eben nicht im Cache war.
Und ab da dann aber nicht mehr, ne.
So.
Also jedes Element, das am Anfang der Phase nicht drin ist und
reinkommt, verursacht genau einen Cache-Miss.
Und dieses kleinen l, das sei genau die Anzahl von Elementen, die am
Anfang einer Phase nicht im Cache sind, aber am Ende, also mindestens
einmal angefordert werden.
Gut, das ist das kleinen l.
Ein Element, das am Anfang der Phase im Cache drin ist, so ein
veraltetes Element, kann, wenn man Pech hat, auch dazu führen, wenn es
angefordert wird, dass ein Cache-Miss passiert, nämlich dann, bevor es
angefordert wird, es mal rausgeworfen wurde aus dem Cache.
Und dann kommt es wieder rein und dann bleibt es aber drin, denn das
Bit wird ja auf 1 gesetzt.
Also so ein veraltetes Element, das rausgeworfen wurde und dann beim
Reinholen wieder ein Cache-Miss verursacht, verursacht nur einen Cache
-Miss.
Und wenn es noch öfter angefordert wird, nicht mehr.
Weil das Markierungsbit auf 1 gesetzt wurde.
So, und wenn das dann wieder reingeholt wird, was wird dafür
rausgeworfen?
Ja, ein anderes veraltetes Element, wo das Bit halt noch auf 0 ist.
Es wird ja immer nur was rausgeworfen, was am Anfang der Phase im
Cache war.
Also veraltete Elemente, die wieder reingeholt wurden und ein Cache
-Miss verursachen, verdrängen dafür ein anderes veraltetes Element
raus.
So, und wie ist das jetzt bei dem optimalen Algorithmus?
Da kann man sich auch noch ein kleines Bild malen.
Also die verhalten sich ja wahrscheinlich unterschiedlich im Laufe der
Zeit.
Und das heißt, wenn Sie sich irgendeinen Zeitpunkt rauspicken, der
optimale Algorithmus hat irgendwelche Elemente in seinem Cache, der
randomisierte Marker-Algorithmus auch, aber die Cache-Inhalte sind
halt nicht unbedingt gleich.
Und mit klein d a, sei mal bezeichnet, die Anzahl der Elemente, also a
wie Anfang, die Anzahl der Elemente, die zwar der optimale Algorithmus
in seinem Cache hat, aber der randomisierte Algorithmus nicht.
Und mit d e, wie e wie Ende, genau das gleiche für das Ende der Phase,
wie viele Elemente hat der optimale Algorithmus in seinem Cache, die
der randomisierte Algorithmus nicht in seinem Cache hat.
So, und wir wollen jetzt irgendwas rauskriegen über die Anzahl der
Cache -Misses des optimalen Algorithmus in einer Phase.
Also, am Anfang einer Phase sind Elemente im Cache drin und andere
sind halt draußen.
Und von diesen, die draußen sind, von den sauberen, haben wir gesagt,
per Definition von klein l, klein l Stück werden angefordert, kommen
also in den Cache rein.
Das heißt, der randomisierte Algorithmus hat klein l Cache-Misses,
mindestens, für diese sauberen Elemente.
Der optimale Algorithmus hat ein paar andere Elemente in seinem Cache,
und zwar d a viele sind anders.
Das können vielleicht d a von diesen Elementen, von den sauberen
Elementen sein, für die der randomisierte Algorithmus ein Cache-Miss
hat.
Aber die restlichen l minus d a, die hat dann auch der optimale
Algorithmus nicht in seinem Cache, und für die hat auch der optimale
Algorithmus dann einen Cache-Miss.
Kann natürlich sein, dass l minus d a negativ ist, dann steht da nur,
der optimale Algorithmus hat mindestens minus drei Cache-Misses, ja,
also gut, egal.
So, also die Anzahl Cache-Misses des optimalen Algorithmus ist
mindestens l minus d a.
Das ist das eine.
Das andere ist, wenn man auf das Ende einer Phase guckt,
welche Elemente hat der randomisierte Algorithmus in seinem Cache
näher, die, die angefordert wurden.
Die k Stück, ja.
Wenn jetzt der optimale Algorithmus d e andere Elemente stattdessen im
Cache hat, dann sind also die, die der randomisierte Algorithmus im
Cache hat, die angefordert wurden, beim optimalen Algorithmus nicht
mehr drin.
Und das kann nur heißen, es sind Cache-Misses passiert.
Nämlich d e viele.
Also, der optimale Algorithmus muss mindestens d e Cache-Misses
gesehen haben.
Also sowohl l minus d a, als auch d e.
Das Größere von beidem, ja.
Das ist eine untere Schranke für die Anzahl Cache-Misses.
Und das, das Größere von den beiden, das schätzen wir jetzt mal ab
durch das arithmetische Mittel, das ist noch kleiner, ja.
Also,
wenn man sich da so eine Phase anguckt, die Anzahl Cache-Misses ist l
halbe plus d e halbe minus d a halbe.
Kann man das lesen?
So halbwegs, ja.
Das ist eine untere Schranke für die Anzahl Cache-Misses des optimalen
Algorithmus in dieser Phase.
Das gilt für die nächste Phase analog.
Also, da ist jetzt das l natürlich ein bisschen anders, sondern l
strich halbe plus d e strich halbe minus d a strich halbe.
Das ist eine untere Schranke für die Anzahl Cache-Misses des optimalen
Algorithmus in der nächsten Phase.
Und jetzt, sehen Sie was?
Sepp Herberger nach dem Spiel ist vor dem Spiel.
d e halbe, das was am Ende einer Phase ist, ist das gleiche wie das
was am Anfang der nächsten Phase ist.
Und wenn Sie das jetzt alles aufaddieren über die ganzen Phasen, dann
fällt das hier weg, das hier fällt weg.
Diese ganzen Dinge da zwischendrin, die heben sich auf.
Was übrig bleibt, sind die l halbe und l strich halbe und l zwei
strich halbe für jede Phase-Anzahl, also dieses l von der Phase halbe.
Außerdem, bei der ersten Phase bleibt vorne minus d null halbe.
Am Anfang der ersten Phase, wie groß ist der Unterschied zwischen
randomisierten Marker-Algorithmus und optimalen Algorithmus?
Gar keiner.
Per Definitionen, das ist null.
Und ganz am Ende bleibt halt noch so ein bisschen was übrig, plus ein
kleines bisschen.
Und das ist die untere Schranke für die Anzahl Cache-Myths des
optimalen Algorithmus.
Und da sehen Sie, das sind also im Mittel sozusagen pro Phase jeweils
l halbe für das l von der jeweiligen Phase.
Und das haben wir damit erledigt.
Also für jede Phase.
Im Zweifelsfall stellt man sich vor, dass man gewisse Cache-Myths
nicht der eine, sondern der Nachbarphase zurechnet.
Im Mittel hat man mindestens l halbe Cache-Myths pro Phase.
Und das ist eine natürliche Stelle, um hier mit dem Beweis aufzuhören.
Es kommen jetzt noch drei Folien, fünf Minuten.
So, das war der optimale Algorithmus.
Jetzt der randomisierte Marker-Algorithmus.
Da wollen wir jetzt auch wissen,
was erwartet.
Wie viele Cache-Myths passieren denn?
Also, erstens.
Wir gucken wieder eine beliebige Phase an.
Es gibt l saubere Elemente, die also am Anfang der Phase nicht drin
sind, die reingeholt werden.
Macht also auf jeden Fall l Cache-Myths.
Wir wollen jetzt eine Abschätzung nach oben haben.
Deswegen stellen wir uns vor, dass das als erstes passiert.
Dass gleich mal möglichst viele veraltete Elemente, die vielleicht
später auch noch angefordert werden, gleich mal rausfliegen aus dem
Cache.
Also stellen wir uns vor, als erstes kommen l Anforderungen von
Elementen, die gerade nicht im Cache sind.
Die machen l Cache-Myths.
Und dann kommen noch, und wenn die mehrfach angefordert werden,
passieren weiter keine Cache-Myths.
Alle anderen Cache-Myths kommen durch Anforderungen veralteter
Elemente.
Das sind dann offensichtlich k-l.
Die sind dann am Ende k-l im Cache.
Und am Anfang, wenn wir die l sauberen reinholen, werfen wir l
Veraltete raus.
Und dabei bleibt es jetzt, dass dann immer l Veraltete draußen sind,
denn wenn man eins von den Veralteten wieder reinholt, was man dafür
rauswirft, erinnern Sie sich, ist auch wieder ein Veraltetes.
Etwas, was das Bit noch auf 0 hat.
Also jetzt ab da immer l Veraltete sind draußen.
So.
Das müssen Sie jetzt wirklich merken, deswegen habe ich das auch blau
gemacht, ja?
l Veraltete sind draußen und das ist jetzt immer so.
Und jetzt kommt die Folie, wo man in der Mitte bei dem dritten Punkt
sich das also wahrscheinlich auch zu Hause nochmal durchlesen muss und
durch den Kopf gehen lassen muss, was das ist.
So.
Am Ende der Phase.
Da sind also die l sauberen Elemente drin und k-l Veraltete.
Nennen wir die x1 bis x k-l.
Und stellen wir uns vor, die sind so durchnummeriert, dass x1 das
Veraltete ist, das dann irgendwann als erstes angefordert wurde.
Und x2, das als nächstes dann irgendwann angefordert wurde und dann x3
und so weiter.
Und dann stellt sich bei jedem xi, das da jetzt eben irgendwann
angefordert wird, die Frage, ist es noch im Cache, ist er ein
veraltetes Element, oder ist es draußen und macht das jetzt ein
Cachemist, das reinzuholen.
So.
Jetzt nehmen wir mal das x1, also das erste Veraltete, das irgendwann
nochmal angefordert wird.
l Veraltete sind draußen, weil wir die l sauberen angefordert haben
und das ist dann immer so.
l Veraltete sind draußen, ein paar sind hier drin, nämlich k-l.
Was ist die Wahrscheinlichkeit, dass wir ein Cachemist haben und
insgesamt sind es k-veraltete Elemente.
l sind draußen, k-l sind drin, insgesamt sind es k.
Wir haben Pech, wenn wir dummerweise eins von den l-veralteten
erwischen, das draußen ist.
Von den insgesamt k-veralteten Elementen.
Die Wahrscheinlichkeit, dass wir bei x1 ein Cachemist haben, ist l
durch k.
So.
Und dann geht es also weiter.
x2, x3, x4 und jedes Mal.
Was ist der schlechte Fall?
Das betrifft leider gerade ein veraltetes Element, das gerade draußen
ist.
Eins von den l, die draußen sind.
Von denen, die insgesamt veraltet und noch nicht angefordert sind.
Noch nicht angefordert wurden.
Und wenn wir bei Element i sind, i-1 veraltet, der haben wir schon
angefordert und wieder im Cache.
Das heißt, es sind jetzt nicht mehr l schlecht von k, sondern l sind
schlecht von k-i-1.
Die Menge ist kleiner.
Das heißt, bei x1 die Wahrscheinlichkeit, dass man ein Cachemist
kriegt, ist l durch k-i-1 oder k-i-1.
Und wenn Sie jetzt für alle diese Elemente x1 bis xk-l diese
Wahrscheinlichkeiten aufaddieren, um zu kriegen, die erwartete Anzahl
Cachemists, dann steht da sowas, dass l können Sie rausziehen und so
eine Summe von Brüchen.
Und da fehlen die Summanden 1 durch 1 bis 1 durch l.
Das heißt, man kann das schreiben als l mal hk, Summe aller Brüche bis
1 durch k, minus hl, Summe aller Brüche bis 1 durch l.
Das ist die erwartete Anzahl Cachemists durch Anfragen, Anforderungen
von veralteten Elementen.
Und da müssen Sie jetzt noch draufaddieren die l Cachemists für die
sauberen Elemente und dann l plus dieser Ausdruck ist locker
abgeschätzt, kleiner gleich l mal hk und das war es, was wir wollten.
Erwartet weniger maximal l mal hk im Vergleich zu den l halbe pro
Phase.
Das Optimale macht einen Faktor 2 mal hk.
Und dann bin ich sogar mit dem Beweis ganz durch und dann war es das
mit der Vorlesung und es geht weiter mit der Übung.
Dann machen wir mit der Übung weiter zu Online-Algorithmen heute.
Heute ist auch das nächste Übungsblatt veröffentlicht worden zu Online
-Algorithmen und Geometrischen Algorithmen.
Wie gesagt, heute sprechen wir über Online-Algorithmen, also wie
können wir ein Problem, wo wir nur beschränkte Informationen haben,
vernünftig abschätzen.
Das heißt nochmal zur Erinnerung, die Informationen, die wir brauchen,
um unser Problem zu lösen, die kommt also erst nach und nach rein.
Das bedeutet insbesondere, wir können noch keine Lösung für unser
Problem finden, die gleich optimal für unsere gesamte Eingabe ist,
weil wir die noch nicht von Anfang an haben.
Beispiele dafür sind Ski-Rental, das wurde kurz in der Vorlesung
angerissen.
Ich hoffe nicht so ausführlich, sonst habe ich heute nichts mehr.
Job-Sketching haben wir gesehen.
Streaming-Algorithmen wären dann so ein anderer Fall.
Da geht es dann irgendwie darum, dass wahrscheinlich die ganzen Daten,
die wir haben, nicht mal in unseren Speicher passen würden oder sowas
und wir sie nach und nach kriegen.
Ähnlich dazu wird vermutlich in der Vorlesung später noch externe
Algorithmen kommen, die verpassen das Zeug auch nicht im Speicher,
aber man kann es sich nochmal angucken, wenn man möchte.
Es geht aber schon in die gleiche Richtung wie Streaming-Algorithmen.
Oder vielleicht wenn wir in so einem Labyrinth rumsuchen, dann wissen
wir ja noch nicht, wie wir wirklich durch das Labyrinth durchkommen
können, aber wir müssen an jeder Kreuzung, an der wir ankommen, eine
Entscheidung treffen.
So, dafür haben wir einen Gütemaß uns definiert.
Wir hatten dann irgendwie so eine Definition wie ein Online
-Algorithmus ist C-kompetitiv, streng C-kompetitiv hatten wir noch.
Und was wir jetzt hier heute betrachten ist irgendwie der kompetitive
Faktor, was irgendwie das kleinste C ist, sodass der Algorithmus
streng C-kompetitiv ist.
Und das ist irgendwie das Supremum über alle Instanzen, die wir in
unserem Algorithmus geben können, von unserem Algorithmus durch die
optimale Lösung für diesen Algorithmus.
Also das ist wieder sehr ähnlich zu Approximationsalgorithmen, wo wir
auch irgendwie das, was unser Algorithmus gibt, durch das, was der
optimale Algorithmus tun würde, geteilt haben.
Was könnte da passieren?
C gleich unendlich ist irgendwie doof, das bedeutet unser Algorithmus
kann unendlich viel schlechter sein als das, was ein optimaler
Algorithmus tun würde.
Was wir lieber haben wollen, wäre irgendwie eine konstante C, das
heißt wir können sagen, unser Algorithmus braucht maximal doppelt so
viel Kosten, oder wie auch immer, was auch immer wir optimieren
wollen, er ist maximal doppelt so schlecht wie die optimale Lösung.
Und vielleicht könnte das aber auch noch abhängen von irgendwelchen
anderen Parametern in unseren Problemen, da werden wir auch ein
Beispiel gleich für sehen.
Genau, hier nochmal dieses Ski-Rental-Problem.
Wir stellen uns irgendwie vor, wir sind im Ski-Urlaub und wir wollen
Ski fahren und wir können uns jetzt entscheiden, kaufen wir uns Ski
oder mieten wir uns Ski.
Und wir wissen nicht, wie lange das Wetter hält, das heißt wir wissen
irgendwie nicht, wie viele Tage wir Ski fahren wollen.
Dann sagen wir okay, wir können uns entweder Ski kaufen für Kosten
Großk, oder wir können uns die Ski ermieten für Kosten Kleink.
Und Kleink ist kleiner als Großk, weil ansonsten wäre das eine
ziemlich schlechte Ski-Vermietung.
Und was wir jetzt tun wollen, ist wir wollen irgendwie eine
intelligente Strategie finden, wann wir unsere Skier kaufen.
Gleich am ersten Tag zu kaufen ist irgendwie doof, weil was ist, wenn
am nächsten Tag das Wetter schlecht ist, dann haben wir gleich schon
mal Skier gekauft, obwohl die Skier zu mieten viel viel weniger
gewesen wäre.
Das heißt, wir haben irgendwie eine Instanz, ist bestimmt durch die
anzählende Nutzung, also was der Online-Algorithmus dann kriegt, ist
im Grunde genommen immer nur, heute wollen wir Ski fahren, heute
wollen wir auch Ski fahren, heute wollen wir auch Ski fahren, heute
auch und jetzt nicht mehr.
Und das ist unsere Eingabe.
Und wir müssen jedes Mal, wenn das Algorithmus sagt, wir wollen heute
gerne Ski fahren, müssen wir eine Entscheidung treffen, ob wir jetzt
die Skier kaufen oder nicht.
Und was dann natürlich die Kosten unserer Algorithmen sind, sind wie
viel Geld haben wir ausgegeben für die Skier.
Genau, die Definition hatten wir gerade schon, da gehen wir jetzt
einfach rüber.
Das sind jetzt also irgendwie die Kosten, die wir irgendwie so haben
könnten.
Das ist jetzt über die Zeit, also über wie viele Tage wir Ski fahren
insgesamt, das ist das N auf der x-Achse und auf der y-Achse sind die
Kosten, die wir dafür zahlen müssen.
Und wenn wir uns entscheiden, wir kaufen sofort die Skier, dann haben
wir irgendwie so Kosten von K und die sind einfach konstant, weil wir
gehen davon aus, Skier gehen nicht kaputt, wir können die endlos lange
benutzen, weil wir haben ja diese gerade sofort K-Zahlen.
Oder wir könnten jeden Tag Skier mieten und einfach nie uns Skier
kaufen, dann haben wir irgendwie so eine Funktion, die einfach jeden
Tag um kleinen K weiter hoch geht.
Was würde der optimale Algorithmus jetzt tun?
Der optimale Algorithmus weiß, wie lange wir Ski fahren, also wie
viele Tage.
Der weiß, wann das Wetter schlecht wird.
Das heißt, wenn er weiß, dass wir nach N Tagen aufhören Ski zu fahren,
dann kann er sich ja vorher schon entscheiden, okay, ich weiß, nach N
Tagen hätte ich jetzt irgendwie, wenn ich es gemietet hätte, mehr Geld
ausgegeben, als wenn ich es kaufen würde, also kaufe ich es jetzt.
Oder er weiß, N mal Mieten ist günstiger, als sofort K zu zahlen.
Das heißt, sobald wir dann bei Groß-K durch Klein-K Tagen sind, das
ist genau der Break-Even-Point, wenn wir bei Groß-K durch Klein-K
Tagen sind, dann kaufen wir.
Und wenn wir öfter fahren, kaufen wir auch.
Und wenn wir seltener fahren, dann kaufen wir halt nicht.
Das ist das Optimale, was man hier machen kann.
Weniger ausgeben kann man nicht fürs Skifahren.
Ja, und das wäre jetzt irgendwie ein Algorithmus, der sagt, am zweiten
Tag kaufe ich.
Ich gehe am ersten Tag hin und miete mir auf jeden Fall meine Skier.
Und am zweiten Tag sage ich, okay, wenn ich jetzt am zweiten Tag immer
noch fahre, dann ist das Wetter bestimmt noch viel länger gut, dann
kaufe ich mir jetzt die Skier.
Und dann sind die Kosten halt irgendwie um Klein-K größer als der
Optimale Algorithmus, wenn wir oft Skifahren.
Und es ist irgendwie viel schlechter, wenn wir nicht so oft Skifahren.
Weil der Optimale Algorithmus, der hätte sich halt dann nur ein paar
Tage die Skier gemietet, wir haben aber schon gekauft.
Sieht irgendwie diese Kurve so aus.
Und was uns jetzt irgendwie interessiert ist, naja, was ist dieses C
hier?
Wissen wir irgendwie nicht.
Was wir jetzt eigentlich machen wollen ist, wir gucken uns einen
Algorithmus an, der nach x Tagen die Skier kauft.
Also er geht jeden Tag zum Skifahren und mietet sich jeden Tag seinen
Skier bis zu irgendeinem Tag x.
Und Tag x wissen wir jetzt noch nicht, den gucken wir uns gleich an,
wie der aussieht.
Und erst wenn wir am Tag x angekommen sind, dann kauft er sich die.
So, das heißt, unser Algorithmus hat dann irgendwie, solange n, also
die Anzahl an Tagen, die wir wirklich Skifahren kleiner ist als x,
haben wir Kosten von n mal Klein-K.
Und sobald es größer ist, dann zahlen wir x minus 1 mal, zahlen wir
die Miete und dann kaufen wir noch einmal Skier.
Dann haben wir dieses x minus 1 mal K plus Groß-K.
Ja und der optimale Algorithmus hat halt immer n mal Klein-K, wenn es
sich lohnt und ansonsten kauft er sich Skier sofort Groß-K.
Und jetzt gucken wir uns irgendwie mal an, wie sich die beiden
zueinander verhalten.
So, das heißt jetzt ist auf der x-Achse immer noch die Anzahl Tage,
wie lange wir Skifahren und auf der y-Achse ist jetzt aber dieser
Faktor, unser Algorithmus, durch den optimalen Algorithmus.
Dann haben wir die Skier auch in unserem Algorithmus noch nicht
gekauft, weil n ist kleiner als x.
Dann haben wir hier irgendwie, wenn wir das teilen, ist das 1.
Beide zahlen irgendwie gleich 4.
Jetzt kommen wir zu dem Fall, der optimale Algorithmus weiß, es lohnt
sich die Skier zu kaufen und wir kaufen uns die Skier auch irgendwann.
Also wir kaufen oft genug Skier, wir fahren oft genug Ski, wir fahren
mehr als x mal Ski und kaufen uns irgendwann die Skier.
Dann haben wir diese Kosten x-1 mal K plus K, Klein-K, Groß-K, das
sollte ich vielleicht immer dazu sagen.
Und dann haben wir genau das, was da steht.
Also dx-1 mal Klein-K durch Groß-K plus Groß-K durch Groß-K, also 1.
So, das sind jetzt irgendwie die beiden Randfälle, wo entweder keiner
der Algorithmen kauft oder beide Algorithmen kaufen.
Was passiert dazwischen?
Was dazwischen passiert ist, wir haben jetzt irgendwie einmal die
beiden oberen Fälle fallen zusammen und die beiden unteren Fälle
fallen zusammen, was ist mit den anderen Kombinationen?
Beide können irgendwie auftreten, also gucken wir uns die jetzt
irgendwie mal an.
Als erstes, der optimale Algorithmus weiß, es lohnt sich nicht zu
kaufen, wir machen es aber trotzdem.
Und das Blödste, was dann passieren kann, ist irgendwie, wir kaufen
genau an dem Tag, der unser letzter Tag ist.
Das ist ärgerlich, also wir fahren irgendwie erstmal eine Woche lang
Ski und am achten Tag sagen wir, so jetzt kaufen wir endlich mal
unsere Skier und am nächsten Tag ist Wetter scheiße und der Skiurlaub
ist vorbei.
Wenn wir das jetzt durcheinander teilen, dann muss man irgendwie ein
bisschen, Klammer aus, multiplizieren und dann kommt das raus, was da
oben dran steht.
Das hoffe ich glaubt ihr mir jetzt einfach mal, Großk minus Kleink
durch Xk plus 1.
Und der letzte Fall, den wir angucken müssen, der optimale Algorithmus
weiß, es lohnt sich zu kaufen, wir machen es trotzdem nicht, weil wir
es nicht wissen.
Dann sieht die Kurve irgendwie so aus, das steigt halt immer weiter
an.
Also der optimale Algorithmus, der weiß schon, ab da wo diese blaue
Kurve anfängt, der weiß da schon, ja jetzt sollten wir irgendwie
kaufen, aber wir machen es trotzdem nicht.
Am Anfang ist das noch nicht so schlimm, weil wir am Anfang immer nur
Kleink mehr ausgeben und am Ende geben wir einfach immer und immer
mehr aus.
Wir steigen dann irgendwie immer mehr in diese Nähe von diesem rechten
Extremfall.
Und jetzt legen wir uns irgendwie diese beiden Kurven mal
übereinander.
Die hellblaue Kurve gibt jetzt an, wenn der Tag an dem wir kaufen
kleiner ist oder kleiner gleich Großk durch Kleink, dann ist dieser
Faktor das, also diese hellblaue Kurve.
Wenn wir unser x so wählen, dass es größer ist als Großk durch Kleink,
dann sind unsere Kosten diese dunkelblaue Kurve.
Naja und was ist dann unser kompetitiver Faktor?
Wir schätzen sie beide von oben ab.
Was ist das blaue von oben abgeschätzt?
Also x größer Großk durch Kleink, na das ist genau diese Gerade, die
da oben ist.
Also x minus 1 Kleink durch Großk plus 1.
Und wenn unser x kleiner gleich Großk durch Kleink ist, dann ist
irgendwie dieser eine Punkt da oben, das ist der größte.
Und wenn wir das nachrechnen, dann ist das auch größer als wo er da
unten ankommt, das ist eine Funktion, die ist monoton fallend, also
damit können wir nach oben abschätzen.
Und das ist jetzt ein Plot, der ist anders, jetzt hat sich jetzt so
ungefähr alles geändert.
Die x-Achse hat sich geändert und auch die y-Achse ist jetzt der
kompetitive Faktor.
Das müsste man jetzt im Grunde genommen einfach glauben, dass diese
Kurve halt so aussieht.
Und wir sehen hier halt irgendwie, die Kurve hat ihren Tiefpunkt bei
Großk durch Kleink.
Also wenn x, der Tag an dem wir kaufen, genau Großk durch Kleink ist,
dann hat diese Funktion ihren Tiefpunkt und dieser c, der kompetitive
Faktor, ist dann 2 minus Kleink durch Großk.
Ein Sonderfall gibt es noch, der irgendwie ein bisschen vielleicht was
kaputt machen kann.
Wir zahlen die Skier, aber benutzen sie nie.
Das ist irgendwie doof.
Wir kaufen die Skier am Tag 0, bevor wir jemals Skifahren.
Und dann machen wir den Algorithmus so, dass er das nicht tut, weil
sonst sind wir irgendwie unendlich oder undefiniert, wie auch immer.
So, genau, das ist nochmal das c, was wir eben schon unten auf der
Folie stehen hatten.
Wann ist jetzt x optimal?
Haben wir eben Beweis per Bild, dass ihr mir glauben müsst, gesehen
bei Großk durch Kleink.
Das ist auch das gleiche, was in der Vorlesung, wenn ich das richtig
gesehen habe bei der Vorlesung, genau dieses Zahlenbeispiel hier
unten.
Kaufen kostet 100, Leihen kostet 10 und dann haben wir irgendwie c
gleich 1,9 für diese speziellen Werte.
Was man da auch machen kann, ist ein randomisierter Algorithmus.
Mit dem könnte man dann einen erwarteten kompetitiven Faktor von 1,58
erreichen.
Und was der macht ist, der hat eine Wahrscheinlichkeitsverteilung, der
mir angibt, mit irgendeiner bestimmten Wahrscheinlichkeit kaufe ich an
jedem Tag.
Das ist halt abhängig von dem Tag.
An Tag 1 kaufe ich mit einer bestimmten Wahrscheinlichkeit, an Tag 2
kaufe ich mit einer anderen Wahrscheinlichkeit usw.
Und dann habe ich irgendwie e durch e-1 und das ist 1,58, sagt der
Taschenrechner.
Das war es auch schon zu Ski-Rental.
Gibt es da noch Fragen?
Und wenn nicht, dann vergrößern wir unsere Schätzungen.
Und zwar geometrisch.
Also verdoppeln oder verdreifachen oder verdvierfachen.
So eine Art Strategie.
Das Problem, was wir uns hier für angucken, ist das Online-Bidding.
Wir geben einem Zielwert U größer 1.
Und unsere Aufgabe ist es jetzt, im Grunde genommen, U rauszufinden.
Das ist eine Auktion mit komischen Regeln.
Nämlich, wir müssen jetzt Gebote abgeben und wir kriegen jedes Mal
gesagt, nee, das ist noch zu wenig, das ist immer noch zu wenig und
wir müssen immer weiter Gebote abgeben, bis wir irgendwann gesagt
kriegen, jo, jetzt war es genug.
Wir nennen diese Gebote Bi und wir geben Gebote bis Bk ab, sobald Bk
größer gleich U ist.
Dann kriegen wir einen Zuschlag in der Auktion.
Und das ist aber ein doofes Auktionshaus, weil wir müssen dann
irgendwie die Summe aller unserer Gebote zahlen.
Also wir müssen B1 plus B2 plus B3 bis Bk haben, müssen wir alles
zahlen.
Und die Frage ist jetzt, wie können wir in diesem Spiel geschickt
genug vorgehen, um nicht zu viel zu viel zu zahlen.
Das klingt hier jetzt erstmal ein bisschen blöd, gibt aber auch andere
Formulierungen dieses Problems, in denen das Sinn macht.
Das heißt, unsere Lösungen sind diese Bi's und die Kosten, die ein
Algorithmus verursacht, ist die Summe der Gebote.
Was macht der optimale Algorithmus?
Der optimale Algorithmus erkennt einfach U, sagt sofort als erstes
Gebot, ich zahle U und kriege gesagt, jo, passt und muss halt nur U
zahlen.
Das ist das einzige Gebot, was er jemals abgegeben hat.
Und was ist jetzt der kompetitive Faktor?
Der kompetitive Faktor ist für jede Reihe von Bi's, dass das Supremum
die ganzen Bi's aufsummiert durch U.
Also B0 bis Bk aufsummiert durch U, sodass Bk-1 noch kleiner ist als U
und Bk ist dann das erste, was mindestens U ist.
Also selbst wenn Bk-1 ganz kurz unter U ist, sind wir leider immer
noch nicht fertig, wir müssen immer noch mal ein Bk drauflegen und
müssen alles zahlen.
Jetzt werden wir uns zwei verschiedene Strategien angucken, nämlich
einmal die Strategie, wir zahlen am ersten Tag 5 und am nächsten Tag
10 und dann 15, 20, 30, 25, Entschuldigung.
Also wir zahlen jeden Tag x mehr und die zweite Strategie, die wir uns
angucken ist, wir zahlen jedes Mal einen Faktor x mehr.
Also wir starten bei einem Gebot von a und am nächsten Tag zahlen wir
x mal a und am nächsten Tag zahlen wir x² mal a.
Dann gucken wir uns mal an, was da rauskommt und wer die Überschrift,
wie gesagt, gelesen hat, wird wahrscheinlich schon vermuten, b
funktioniert besser.
Also, erste Strategie, wir zahlen jeden Tag x mehr.
x größer 0, weil ansonsten zahlen wir jeden Tag 0 und das bringt nix,
dann kommen wir nie auf U.
Und wovon wir jetzt mal ausgehen, wir gehen jetzt mal von so einem
ganz blöden Worst Case aus, nämlich dass unser vorletztes Angebot ganz
ganz knapp unter U ist.
Also, wir haben irgendwie, unser vorletztes Angebot ist ja k-1 mal x,
weil unser letztes Angebot ist k.
Und das ist jetzt u-y und dieses y kann beliebig klein werden, aber
wir sind immer noch nicht fertig, es ist immer noch kleiner als u.
Das ist also irgendwie ärgerlich und was dann passieren kann, b1 ist
irgendwie x mehr, b2 ist nochmal ein x mehr, b3 und so weiter, bis wir
dann irgendwann hier bei bk-1 angekommen sind, das ist fast u, aber da
ist ein nicht sichtbarer und ich glaube auch nicht eingezeichneter
Pixel mehr zwischen diesen beiden Linien und erst bk-plus-1, bk ist
jetzt endlich mehr als u und naja, das sind k mal x.
Wenn wir das jetzt alles aufsummieren, das ist also irgendwie diese
Fläche, wo man die ganzen Balken miteinander aufsummiert, dann, naja,
man sieht es irgendwie ja, wenn man das zu einem Quadrat aufbaut, dann
ist das irgendwie die Hälfte davon, also das ist ein halb k mal x mal
k -plus-1, weil die Seitenlänge auf der Seite, also links ist k-plus
-1, unten ist k mal x, dann ist das die Fläche.
So, und was ist jetzt, was passiert für diesen Worst Case?
Naja, also unsere Anzahlgebote ist k-plus-1.
k-plus-1 ist, wenn wir uns diese Formel da oben umstellen, da steht k
-minus -1 mal x ist gleich u-minus-y, wir teilen durch x und machen
dann plus 1, dann haben wir raus, was k ist, nämlich u-minus-y durch x
plus 1.
Also k-plus-1 ist gleich u-minus-y durch x plus 1, nochmal plus 1.
Und da y größer 0, das steht hier jetzt nicht drauf, ist aber wichtig,
ja, weil wir wollen ein kleines Stückchen unter u sein, y ist größer
0, schätzen wir das jetzt einfach mal nach oben ab, wir schmeißen das
y weg.
Und das ist auch irgendwie tight, ja, also wir können nicht besser
abschätzen als das.
So, was haben wir dann für Kosten für unseren Algorithmus?
Unser Algorithmus, der zahlt irgendwie Summe von i gleich 0 bis k, i
mal x.
Das ist irgendwie, wie gesagt, entweder mit dieser geometrischen
Argumentation oder Gauss-Formel oder wie auch immer ihr sie nennt, ist
das 1 halb mal k plus 1 mal k mal x.
Und wenn wir das dann in diese Formel für diesen kompetitiven Faktor
einsetzen, lösen wir vom Algorithmus durch die optimale Lösung, da
setzen wir jetzt für das k plus 1 und das k auch, setzen wir diese
Abschätzung von da oben ein, und was wir dann rauskriegen ist, das
wächst unendlich groß.
Also, wenn wir uns das angucken, wir haben zweimal u überm Bruchstrich
und nur einmal unterm Bruchstrich, also wir haben u² überm Bruchstrich
und nur u unterm Bruchstrich, das wächst unendlich groß, also dieser
Faktor ist irgendwie unendlich blöd.
Also wir können beliebig schlecht werden, weil je größer wir u wählen,
desto schlechter wird dieser Algorithmus.
So, was passiert, wenn wir dieses Dublin machen?
Dublin bedeutet, oder na, das hier, ja, aber nennen wir es erstmal
nicht Dublin, Dublin klingt irgendwie nach 2, wir sagen, wir fangen
mit einem Wert a an und jeden Tag multiplizieren wir x da drauf.
Worst case wieder, gleiches Szenario, unser vorletztes Gebot ist fast
u, aber nicht ganz.
Das Ganze sieht dann so aus, also wir fangen mit a an, dann setzen wir
x mal a, dann x² mal a, und jetzt x hoch k minus 1 mal a, das ist ganz
knapp unter u und jetzt sind wir endlich drüber.
Wir müssen diese Fläche zahlen und diese Fläche ist, wie wir gleich
nochmal sehen werden, diese Formel, die ich jetzt nicht nochmal
vorlese.
Was können wir machen?
Wir formen wieder diese Formel von oben um, dass a mal x hoch k minus
1 ist gleich u minus y formen wir um, also k plus 1 ist, ja, was tun
wir?
Wir teilen durch a, dann haben wir u minus y durch a, dann ziehen wir
einen Logarithmus zur Basis x, damit wir k minus 1 raus haben und dann
rechnen wir nochmal plus 1, damit wir k raus haben.
Und dann haben wir raus, k plus 1 ist gleich Logarithmus zur Basis x
von u minus y durch a plus 1 plus nochmal 1.
Gleiche Abschätzung wie eben, wir werfen das y einfach weg und unser
Algorithmus hat dann, was für eine Lösungsqualität?
Naja, dieses a mal x hoch i von i gleich 0 bis k, das ergibt diesen
Wert hier, ja, a mal x hoch k plus 1 minus 1 durch x minus 1.
Wir schätzen das Ganze wieder ab mit unserer Abschätzung für k plus 1,
setzen wir da wieder für das k plus 1 ein.
Und was machen wir dann?
Ah, genau, dann haben wir x hoch Logarithmus von x, super, das fällt
irgendwie weg.
Und wir haben jetzt das was, ich lese nochmal vor, a mal, in Klammern,
u durch a, x gradab minus 1 durch x minus 1.
So, was ist jetzt unser Faktor c?
Im Faktor c setzen wir wieder diese Abschätzung nach oben für den
Algorithmus ein und wenn wir das durcheinander teilen, haben wir x
quadrat minus x minus 1 durch x minus 1 minus a durch x minus 1 mal u.
Ich führe das jetzt nicht aus, ja, das sind irgendwie alles
Rechenschritte, die, ich bin mir sicher, die kriegt ihr hin.
Da muss man mal, ja, also, ich glaube ihr habt alle Abi gemacht, dann
werdet ihr das hinkriegen.
Und was wir hier jetzt rauskriegen ist, c ist kleiner gleich x quadrat
durch x minus 1.
Weil, das was da auf der rechten Seite steht, ist halt auf jeden Fall
auch positiv, ja, und für große u läuft das Ganze sogar gegen 0.
Und wenn dann alles andere bleibt fest, also a ist fest, x ist fest, 0
wird größer, ja, dann haben wir x quadrat durch x minus 1.
Und wenn wir das Ganze jetzt minimieren wollen, dann kriegen wir raus,
für x gleich 2 ist das minimal.
Da ist jetzt, ah, hier steht jetzt c gleich 4, das steht hier zwar
noch nicht, aber wir sehen gleich, dass es trotzdem stimmt, ja.
Also, erstmal haben wir hier nur stehen, c kleiner gleich 4.
Wir könnten das Ganze wahrscheinlich auch so analysieren, dass hier
gleich c gleich 4 steht, aber wir werden gleich sehen, dass es gar
nicht anders sein kann.
Okay, wir wissen also, wenn wir unseren Preis immer weiter verdoppeln,
wir starten bei irgendeinem Wert und verdoppeln immer weiter, dann
haben wir einen kompetitiven Faktor von 4.
So, und jetzt kommt ein bisschen der eklige Teil an heute, nämlich,
wir wollen zeigen, dass c gleich 4 eine untere Schranke ist.
Und damit ist dann auch klar, dass hier c gleich 4 ist, ja.
Wir haben gezeigt, c ist kleiner gleich 4.
Hier werden wir zeigen, besser als 4 geht gar nicht, also ist der
kompetitive Faktor, diesen Algorithmus, den wir eben angeguckt haben,
gleich 4.
Wie gesagt, könnte man mit Sicherheit auch direkt zeigen.
So, was wir uns als erstes mal definieren, sind so zwei Abkürzungen.
sk ist die Summe von 0 bis k dieser ganzen Bi's, also im Grunde
genommen einfach das, was wir zahlen, wenn wir k-Gebote abgeben.
Und yk, ich weiß nicht, ob man da irgendeine Bedeutung
reininterpretieren kann, wir benutzen es, um Sachen abzukürzen, ist sk
plus 1 durch sk.
Das definieren wir uns einfach so.
Und was wir uns jetzt angucken, ist...
Also wir nehmen an, wir haben einen Algorithmus, der eine Folge von b
ist, erzeugt, sodass der kompetitive Faktor kleiner ist als 4.
In anderen Worten, sk durch u ist kleiner als c und wir nennen das
ganze Ding jetzt hier uk, weil wir uns verschiedene u's angucken
werden.
Und zwar wählen wir u, wir wollen es schaffen, dass der Algorithmus
schlecht abschneidet.
Das ist unser Ziel, wir wollen zeigen, diesen Algorithmus mit c
kleiner 4, den kann es gar nicht geben.
Wir wählen uns unsere uk's jetzt immer so, dass sie halt irgendwie nur
um ein y von dem vorletzten Gebot entfernt sind.
Also uk gleich bk minus 1 plus yk.
So.
Das können wir also sagen, sk plus 1 ist kleiner als c mal u.
Naja, und wir setzen... sk plus 1 ist kleiner als c mal uk plus 1.
Und wir ersetzen uk plus 1 mit diesem bk plus yk plus 1.
Und außerdem ist bk das letzte Summenglied von sk.
Das heißt, wir können einfach sk minus sk minus 1 rechnen und haben
auch bk raus.
So, das heißt, sagen wir das, was auf der rechten Seite steht.
Was wir als nächstes tun, ist, wir teilen das ganze durch sk.
Was wir dann raus haben, ist, auf der linken Seite haben wir sk plus 1
durch sk.
Das ist yk per Definition, so haben wir uns yk definiert.
Danach haben wir c mal sk durch sk, das ist 1.
Dann sk minus 1 durch sk.
Wenn wir uns dann yk angucken, das ist irgendwie genau 1 durch yk
minus 1.
Plus nochmal dieses blöde y durch sk.
Jetzt gibt es hier so eine Abschätzung, die ist allgemein gültig für
natürliche Zahlen.
1 minus 1 durch x ist kleiner gleich, müsste es, glaube ich, heißen, x
viertel.
Und wenn wir das da einsetzen, x ist yk minus 1, dann können wir das
also abschätzen mit c viertel mal yk minus 1 plus c mal yk plus 1
durch sk.
Also das c ausmultipliziert und das 1 minus 1 durch yk minus 1 mit
dieser Abschätzung ersetzt.
So, was wir jetzt tun, ist halt, wie gesagt, was wir tun, ist, wir
wählen uns unser u ganz gemein, damit dieser Algorithmus nicht
funktioniert.
Das heißt, wir wählen uns jetzt dieses yk plus 1, was da drin ist, so.
Und was dann nämlich passiert ist, dieser ganz additive Term, wo
dieses yk plus 1 drin ist, wird zu einem 2 hoch minus k.
Das ist also eine schön kleine Zahl, mit der wir jetzt gleich was
anfangen können.
So, wir werden jetzt erstmal das Ganze, was wir hier getan haben, also
wir können dieses yk kleiner c viertel mal yk minus 1 plus 2 hoch
minus k, das können wir induktiv anwenden.
Das funktioniert für alle k.
Das heißt, wir ersetzen jetzt auch dieses yk minus 1, ersetzen wir mit
der gleichen Abschätzung und vielleicht können wir hier schon, in dem,
wie es da ausgeschrieben ist, so ein Pattern erkennen.
Wir haben irgendwie immer einen c viertel hoch immer 1 mehr mal yk
minus 2 und dann haben wir jedes Mal noch dieses c viertel Zeug und
das wird auch immer mehr mal dieses 2 hoch minus k beziehungsweise 2
hoch minus k minus 1.
Das werde ich gleich beheben, ja, also c viertel mal 2 hoch k minus 1
sollte c viertel mal 2 hoch minus k minus 1 sein.
So, das können wir jetzt weiter fortführen und zwar bis wir irgendwann
bei y2 angekommen sind, also bis wir das k minus 2 mal fortführen,
haben also c viertel hoch k minus 2 mal y2 und dann plus irgendwie
diese ganzen 2 hoch minus 3, minus 4, minus k, wobei wir die c
viertel, die davor sind, weggeschmissen haben, ja, die sind kleiner
als 1.
Wir können auf jeden Fall nach oben abschätzen, indem wir diese
Viertel einfach wegwerfen.
c ist kleiner als 4, ist dafür wichtig, ja.
Wir teilen etwas, was kleiner ist als 4, eine konstante c, die kleiner
ist als 4, teilen wir durch 4.
Und das ist nämlich der ganze Trick, weshalb uns das gleich schief
gehen wird.
So, was wir jetzt noch tun können ist, naja, diese ganzen 2 hoch minus
3 plus 2 hoch minus 4 und so weiter, das ist irgendwie auf jeden Fall
eine Konstante kleiner als 1.
Genau, es ist sogar kleiner als 1 minus 2 hoch minus 2, weil wenn wir
alle nehmen würden, also von 2 hoch 0 an, dann würde sich das zu 2
aufsummieren.
Und wenn wir diese ersten beiden Summenglieder weglassen, dann haben
wir halt 2 minus diese ersten beiden Summenglieder, also 1 minus 2
hoch minus 2.
So, und wir multiplizieren das Ganze mit sk, damit wir aus unserem yk,
was wir auf der linken Seite stehen haben, wieder ein sk plus 1 und
dieses ganze Gedöns, was wir da stehen haben, mal sk.
Jetzt haben wir auf jeden Fall einen additiven Term, diese Konstante,
die kleiner ist als 1, haben wir da.
Und wir haben s3 durch s2, das war vorher y2, das ist auch konstant.
Naja, und dann haben wir da noch irgendwas kleineres als 1, was wir
für beliebig große k auch beliebig klein werden lassen können.
Das heißt, das ganze Term in der Summe ist kleiner als 1 für große k.
Und k können wir uns ja schön groß wählen.
Weil wir wollen ja einfach nur eine Eingabe finden, sodass der
Algorithmus nicht funktioniert.
Naja, das heißt, das ganze Ding ist um die kleiner als sk, und was
haben wir jetzt raus?
Naja, sk plus 1 ist kleiner als sk.
Ja, aber sk plus 1 hat einen Summenglied mehr, also negative Gebote
erlauben wir wohl eher nicht.
Das heißt, das geht gar nicht, das ist ein Widerspruch.
Und was wir dafür angenommen haben, das Einzige, was wir angenommen
haben, ist c ist kleiner als 4.
Das heißt, c kann nicht kleiner als 4 sein.
Und jetzt bin ich auch schon zwei Minuten drüber.
Zusammenfassung, naja, wir haben gesehen, was ein kompetitiver Faktor
ist.
Wir haben Dublin und eRental uns nochmal angeguckt.
Beispielfragen, die ihr vielleicht in der Klausur oder sowas sehen
könntet, ist ja, wir haben den Algorithmus gegeben, wie groß ist ein
kompetitiver Faktor?
Oder entwerfen Sie einen eigenen Algorithmus mit einem kompetitiven
Faktor?
Oder vielleicht auch sowas, wie wir gerade gesehen haben, nur mit
leichteren Rechnungen.
Was ist denn die untere Schranke für einen kompetitiven Faktor, den
wir jemals erreichen können hierfür?
Genau.
Das war's.
Vielen Dank.
Bis...