Ich kann vielleicht damit anfangen.
Sollte ich eigentlich nur aufs Übungsblatt bringen, aber vielleicht
bringe ich es auch schon jetzt einfach, solange die Leute noch
eintrudeln.
Ich wollte noch ein paar Sachen zu Pseudocode fallen lassen, weil sie
ja in den Übungsblättern und später dann auch
in der Klausur und so Pseudocode verfassen sollen.
Und beim Korrigieren sind den Tutoren ein paar Sachen aufgefallen.
Die haben es mir mitgeteilt und jetzt habe ich mal so ein...
das was so aufgefallen ist mal zusammengefasst und ein paar Regeln
erstellt.
Naja.
Den letzten Punkt, gut, das kann man halt klar machen.
Der letzte Punkt ist mir eigentlich ein bisschen zu detailliert, um
den in den Regelsatz aufzunehmen.
Ich glaube, den nehme ich nochmal raus.
Aber es ist klar, man sollte in der Deklaration auf jeden Fall klar
machen, ob die Initis jetzt bei 0 oder 1 beginnen.
Aber ansonsten grundsätzlich
versuchen sie sich da dran zu halten, dass sie eben erstmal so ein
bisschen den Algorithmus vorstellen, die Grundidee.
Das ist so ähnlich wie beim Programmieren, auch die Kommentare einfach
so ein bisschen deutlicher machen, was man da jetzt im Sinne hat, wenn
man den Algorithmus hier schreibt.
Genau.
Und sie müssen jetzt nicht nochmal so den Code von MergeSort oder so
abschreiben, wenn sie MergeSort verwenden wollen.
Die Methoden gibt es, die kann man nachlesen in der Vorlesungsfolie.
Die kann man einfach verwenden.
Es sei denn, es ist natürlich explizit verlangt, dass man die
hinschreibt.
Das wäre dann die Ausnahme zur Regel.
Genau.
Dann eben auch so, was man auch in Clean Code Regelwerken findet, dass
man Funktionen auch aufteilt sinnvoll nach Einzelaufgaben.
Strukturierter Code gilt auch für Pseudocode.
Ist auf jeden Fall da auch besser, das so zu machen.
Genau.
Blöcke eindeutig kennzeichnen.
Das ist auch noch so eine Sache.
Wenn der Tutor nicht mehr weiß, ob der letzte Befehl außerhalb oder
innerhalb der Schleife ist, ist schlecht.
Gut.
Dann beginnen wir mit der Übung.
Genau.
Jetzt ist auch nach 14 Uhr.
Vorgeblenke vorbei.
Vierte Übung heute.
Ich stelle wieder drei spezielle Datenstrukturen vor.
Die auch wieder, wie beim letzten Mal, unter bestimmten besonderen
Voraussetzungen besondere Laufzeitanforderungen genügen.
Erstmal als Erinnerung nochmal der Bucket Sort.
Den kennen Sie aus der Vorlesung.
Kann man sich hier nochmal anschauen.
Man hat im Prinzip hier so eine endliche Anzahl an Buckets und kann
eine Bejektion zwischen dem Sortierschlüssel und den Buckets
herstellen.
Wenn das möglich ist, ist danach vollständig sortiert.
Ansonsten muss man die Buckets selber nochmal sortieren, aber da
kommen wir gleich dazu.
Also das Prinzip ist, denke ich, klar.
Danke für den Hinweis.
Da habe ich überhaupt nicht dran gedacht.
Wir machen das Licht aus.
Ne, das hat hier nichts mehr zu tun.
Sofern ich den Schalter finde, machen wir das.
Hier gibt es Knöpfe.
Also ich finde den Schalter nicht.
Wenn jemand eine Idee hat, wo er es sein könnte.
Hier hinten dran, oder was?
Guck mal, hier gibt es Zeug.
Ne, da ist auch nichts.
Also ich finde hier wahnsinnig viel spannende Technik vorne, aber...
Kein Schalter.
Ne, sorry.
Müssen Sie sich dann im Netz nochmal angucken.
Oder Sie kommen weiter vor.
Ist es vorne besser?
Aber ist schlecht.
Ich mache jetzt trotzdem mal weiter.
Vielleicht habe ich zwischendurch noch eine Idee, wo man draufdrücken
könnte.
Wenn ich irgendeinen Knopf sehe, drücke ich drauf.
Bucket Sort Spezial.
Also nochmal kurz zurück, Wiederholung.
Ah, da kommt einer zu spät.
Sie könnten mir helfen, indem Sie den Ausschalter für dieses Licht
suchen.
Sorry, das ist Ihnen nicht so aufgefallen, weil Sie gerade reinkamen.
Sollen wir es ausprobieren?
Oh, okay, gut.
Immer gut, wenn die fähigsten Studenten auffallen.
Gut, jetzt nochmal zurück zu Bucket Sort.
Alles klar.
Also wir haben hier so etwas mit Bejektion zwischen Schlüsseln und
Buckets.
Was dann hinterher, wenn man es zusammenfügt, dann dadurch vollständig
sortiert ist.
Man kann auch etwas anderes machen, man kann Zahlen aus dem Intervall
0,1 nehmen und so in Buckets legen, dass sie hinterher möglichst gut
sortiert sind oder möglichst effizient zu sortieren sind.
Dann ist jetzt hier folgender Algorithmus.
Wir teilen das Intervall auf in N Buckets, also so viele Buckets, wie
wir jetzt gerade haben, wie wir zur Verfügung haben, und verteilen
dann eben unsere Zahlen aus einer Menge, die uniform gleich verteilt
aus diesem Intervall kommt.
Das ist nachher wichtig für die Laufzeitanalysen.
Also die sind uniform gleich verteilt, das ist Voraussetzung.
Verteilen die Zahlen auf den Bucket, sortieren dann jeden Bucket mit
Insertion Sort und hinterher werden die Buckets zusammengefügt und
dann haben wir eine sortierte Menge, eine sortierte Liste von Zahlen.
Ich mach es mal vor, also hier Zahlenfolge, jetzt teilen wir die
Buckets auf, alles was kleiner als 0,1 ist, kommt in den ersten
Bucket, alles was kleiner als 0,2 ist und größer als 0,1 kommt in den
zweiten Bucket, und so weiter und so fort.
So, verteilen wir die Zahlen, entsprechend 0,2, 0,3, 0,4 kommt in den
dritten Bucket, 0,9 in den letzten.
Dann haben wir da verkettete Listen pro Eimer.
Da hängen wir gerade die zusätzlichen Elemente hinten dran.
Da hinten nochmal ein ganz großer Bucket.
So, und wenn wir dann durch sind, müssen wir noch sortieren.
Da sehen wir hier eine Inversion im zweiten Bucket.
Drehen wir richtig rum, dann haben wir nochmal eine Inversion hinten
im vorletzten Bucket.
Drehen wir richtig rum.
Also, naja, wir sortieren mit Insertion Sort, offiziell.
Gut, ist jetzt geschehen.
Genau, also der Algorithmus sieht so aus.
Hier haben sie nochmal ein Beispiel für Pseudocode.
Hier ist auch klar gemacht, dass der Array bei 0 beginnt in der
Deklaration.
Gut, dann überlegen wir uns mal, was der für eine Laufzeit hat.
Genau, jetzt wollen wir die Laufzeit von Insertion Sort haben, wissen
aber jetzt nicht, wie groß die Buckets sind.
Also, theoretisch könnte jedes Element im gleichen Bucket sein, aber
wir haben ja noch diese zusätzliche Information, dass die Elemente
gleich verteilt sind, uniform gleich verteilt in diesem Intervall.
Also, definieren wir uns eine Zufallsvariable für die Größe des
Buckets.
Fangen wir unten an zu lesen.
Wir definieren die Zufallsvariable xij.
xij ist 1, falls das Element j in Bucket i landet und 0 sonst.
Genau, und dann ist die Größe des Buckets eben die Summe über diese
xij.
Und dann überlegen wir uns, was zu dem xij.
Und zwar den Erwartungswert.
Der Erwartungswert von xj, also der Größe unseres Buckets, ist die
Summe der Erwartungswerte von xij.
Und da kommt jetzt diese uniforme Gleichverteilung ins Spiel.
Was war da?
Genau, die Wahrscheinlichkeit ist eben 1 durch n, dass das Element in
so einem Bucket landet und das liegt an unserer uniformen
Gleichverteilung.
Und dann können wir den Erwartungswert relativ leicht ausrechnen.
Und die erwartete Größe ist dann eben auch 1, also konstant.
Und wir haben so eine erwartete Gesamtlaufzeit von o von n.
Und das kriegen wir nur deswegen hin, weil wir Grundannahmen gehabt
haben.
Also das waren unsere Grundannahmen.
Wir haben ein endliches Intervall von Zahlen zwischen 0 und 1.
Und wir haben die uniforme Gleichverteilung angenommen.
Und wenn wir das angenommen haben, kriegen wir sowas raus.
Also im Endeffekt haben wir es uns gleich von Anfang an schön einfach
gemacht.
Aber wenn Sie jetzt dann eben in der Praxis Szenarien haben, spezielle
Szenarien, können Sie eben auch so besondere Laufzeiten rauskriegen,
wenn Sie sich sowas überlegen.
Gehen wir zu Prioritätswarteschlangen.
Das kam, glaube ich, gerade in der Vorlesung.
Ja, gab es noch eine Frage dazu?
Die Frage ist, ob wir eine gute Hash-Funktion brauchen, um die
Elemente in die...
Ich kann nochmal kurz zurückgehen und den Bucket-Sort erklären.
Also, letzten Endes ist es so, wenn ich eine endliche Anzahl an
erwarteten Werten habe, dann kann ich ja genau so viele Buckets zur
Verfügung stellen, wie ich Werte erwarte.
Und wenn ich dann eine Projektion herstellen kann, zwischen Bucket
-Index und Elementwert, dann sind sie direkt sortiert.
Wenn das nicht möglich ist, dann muss man die Buckets selber nochmal
sortieren.
Das sieht man ja dann zum Beispiel bei Radix-Sort.
Das geht dann nochmal weiter.
Aber hier, heute, haben wir jetzt einen Spezialfall betrachtet für n
Zahlen, die gleich verteilt aus einem festen Intervall rausgenommen
werden.
Und dann ist die Zuordnung ja klar.
Also, dann macht man sowas in der Art.
Oder für noch größere n werden die Buckets halt kleiner, also enger.
Genau,
dann Prioritätswarteschlangen, also Heaps zum Beispiel.
Hier haben wir folgende Laufzeiten, nochmal so als Erinnerung.
Aber eigentlich können Sie sich das auch selber angucken.
Ich wollte heute eine spezielle Priority-Queue anschauen, deswegen
diese Folie.
Und jetzt haben wir auch wieder eine besondere Annahme, weshalb wir
die Datenstruktur auch besonders auslegen können und dann besondere
Laufzeiten rausbekommen.
Die Annahme ist folgende.
Wenn wir ein neues Element einfügen in diese Prioritätswarteschlange,
ist es immer größer oder gleich dem Minimum und kleiner als dem
Minimum, bloß eine feste Konstante.
Genau, also wir haben es mit ganzen Zahlen zu tun.
Gut, das ist jetzt nicht so besonders, die Annahme.
Aber die beiden anderen Annahmen über die neuen Elemente, die
eingefügt werden, die sind eigentlich schon krass, also die schränken
ein.
Das wäre dann sowas wie...
Na gut, wenn ich ein anderes Szenario habe, kann ich diese
Datenstruktur nicht benutzen.
Aber wenn ich eben so ein Szenario habe, kann man sowas machen.
Dann nimmt man jetzt diese Größe c.
c wäre jetzt hier in dem Beispiel 12.
Das müssen wir uns immer vor Augen halten.
Wenn ich jetzt hier ein neues Element einfüge, dann liegt es immer
zwischen dem Minimum und Minimum plus c.
Dann verteile ich das mit so einer Modulo-Operation auf diese
einzelnen Buckets.
Auch hier wieder Buckets.
Und das ist eben hier so ein Beispiel, wenn so ein Fall auftritt, dass
jetzt hier quasi 13 drin ist und dann wird später hier eine 25
eingefügt.
Das wäre jetzt quasi hier ein Widerspruch zu der Annahme.
Da müsste man erst wieder die 13 rausnehmen, bevor man die 25 einfügen
kann.
Dann wäre nämlich 15 das Minimum, dann würde es wieder passen.
Dann hat man hier diesen Minimums-Pointer.
Wenn man die 13 rausholt, würde der dann verschoben werden.
Das ist im Prinzip die Idee.
Dadurch kommt man eben auf eine konstante Laufzeit beim DeleteMin auch
wieder.
Man hat eben diesen Minimum-Zeiger, den man verschieben muss, wenn
gerade kein Minimum mehr verfügbar ist in dem Zeiger.
Und es kann eben nicht passieren, beim Einfügen, dass irgendein
Element da drüber rutscht über diesen Minimum-Zeiger.
Es bleibt also immer hinten dran.
Die größeren Elemente bleiben immer hinter dem Minimums-Zeiger.
Hat das jeder verstanden oder wollt ihr noch was fragen dazu?
Keine Frage.
Weil jetzt geht es gleich schon zur nächsten Datenstruktur.
Da sind wir echt verdammt schnell wieder.
Binary, Badexiv.
Wir haben jetzt sogar noch Wünsche.
Wir wollen jetzt irgendwie Logarithmus von c Laufzeiten.
Haben c unterschiedliche Werte.
Genau.
Und wir haben die Bit-Darstellung dieser Werte.
Dann nehmen wir uns dieses höchstwertige Bit, den MSD.
Da haben sie hier ein Beispiel dafür.
Wir sehen hier die binäre Darstellung von der Zahl 60, die binäre
Darstellung der Zahl 42.
Und haben hier the most significant difference, also im Prinzip das
höchstwertige Bit.
Wir fangen von rechts an zu schauen und gucken, wann sich die beiden
binären Darstellungen zum ersten Mal von links betrachtet
unterscheiden.
Das ist eben hier von rechts gezählt, von links geschaut, das vierte
Bit.
Machen wir mal ein Beispiel, dann sieht man das deutlicher.
Also wir fügen jetzt quasi hier Zahlen ein in diesen Heap.
Wir haben hier jetzt gerade ein Minimum bei 9.
Ach, kleinen Moment, ich muss gerade selbst noch mal die Datenstruktur
anschauen, bevor ich es erklären kann.
Was war das?
Ah, ok.
Genau, ok.
Also genau, wir schreiben das Minimum jeweils.
Das Minimum, also das ist eine Invariante dieser Datenstruktur.
Das Minimum muss hier in diesem Feld, das mit Minus 1 markiert ist,
stehen.
Und dann kommt quasi jedes weitere Element, das größer ist als unser
Minimum, kommt in den Bucket, der sich eben aus diesem MSD von Minimum
und der Zahl selbst ergibt.
Also, wenn wir jetzt die 16 einfügen, dann ist unser MSD hier an der
Stelle 4, wenn wir bei 0 anfangen zu zählen.
Ja, weil die 9 hat hier gleich am Anfang eine 0, die 16 eine 1.
Das heißt, das kommt dann eben auch hier an die Stelle 4 in diesem
Array.
Wenn wir die 10 einfügen, kann man sich überlegen, wo ist da der MSD,
also das höchste Bit, wo die sich unterscheiden.
Naja, das wäre im Prinzip an der Stelle 1.
Dann kommt das hier rein.
Und man sieht es auch schon hier an der Beschriftung der Felder.
Im Prinzip sind die Bits der Zahlen, die da reinkommen, hier ohne
Sternchen hingeschrieben und alle anderen, also alle Downcales
sozusagen, mit Sternchen gekennzeichnet.
Dadurch kann man das auch relativ schnell einsortieren.
Genau.
Das wäre im Prinzip das Insert.
Und den MSD, den können wir eben auch in konstanter Zeit bestimmen,
deswegen ist das relativ billig.
Also wir haben dann, genau, einfach nur das Anhängen in die Liste.
Genau, jetzt ist halt das DeleteMin, das ist das Spannende.
Da muss man sich ein bisschen mehr überlegen.
Genau, jetzt haben wir im Prinzip normalerweise das Minimum in Bucket
-1, d.h.
das Element wird daraus zurückgegeben.
Oh, ich sehe gerade, Bucket-1 kann auch leer sein, d.h.
es wird bei DeleteMin gefixt.
Und nicht sofort.
Okay, also da muss ich nochmal einen Kommentar von vorhin rückgängig
machen, wo ich gemeint habe, das wäre eine Invariante.
Normalerweise steht in Bucket-1 das Element.
So, wenn jetzt Bucket-1 leer ist, dann müssen wir im Prinzip diese
Eigenschaft reparieren, dass in Bucket-1 das Minimum steht.
Genau, d.h.
da müssen wir aufräumen.
So, wie geht jetzt dieses Aufräumen?
Das können wir uns mal anschauen, hier im Beispiel.
Also wir haben jetzt das Neue hier rausgenommen.
Jetzt müssen wir die Eigenschaft reparieren.
Ja, genau, also quasi die Invariante wiederherstellen.
Und wir müssen jetzt feststellen, dass wir eigentlich nur die Elemente
bis zum nächsten Bucket betrachten müssen.
Ansonsten ändert sich hinten dran nichts mehr.
Also wir müssen nichts weiter vorschieben als nur die ersten drei
Elemente.
Und dadurch kriegen wir eigentlich dann auch nicht mehr so die
schlechte erwartete Laufzeit.
Also man muss im Prinzip nur diesen einen Bucket, also den nächsten,
zum Minimum neu verteilen, da sich eben das Minimum geändert hat.
Und die MSD-Werte sich ändern.
Genau, wenn man das jetzt amortisiert...
Lock C ist im Prinzip die Größe von unserem Array.
Da wir mit der Binärdarstellung arbeiten, dann müssen wir im Prinzip
jedes Element höchstens Lock C mal verschieben.
Und dieses Lock C, das können wir beim Einfügen, weil das Einfügen
konstant ist, schon einbezahlen.
Dadurch amortisiert sich das dann quasi am Ende.
Also wenn wir am Anfang den konstanten Einfügen Lock C Token uns
aufheben, können wir dann später einmal beim Rausholen Lock C bezahlen
zum Verschieben.
Und dadurch haben wir dann insgesamt nach dem Amortisieren die
Laufzeit von Lock C.
Ja, das funktioniert nicht, wenn wir jetzt im letzten Bucket sehr
große Elemente haben.
Also gehen wir mal davon aus, wir haben ein sehr kleines Element und
ganz viele große Elemente, die alle im hinteren Bucket sind.
Dann geht im Prinzip die Amortisierung kaputt.
Also es wäre jetzt hier dieses Szenario, wo alle sind ganz hinten und
wir müssen den ganzen Saustall aufräumen.
Also das beschränken wir dann im Prinzip dadurch, dass wir sagen, wir
nehmen nur C-Bit und alles was darüber ist, berücksichtigen wir nicht.
Jetzt könnte man auf die Idee kommen, dass es irgendwie ein bisschen
schöner wird, wenn man eine andere Basis wählt.
Aber das funktioniert nicht, das wird ein bisschen komplizierter dann.
Also schon das eine Szenario, ich mache es mal kurz vor, wenn man
jetzt hier die 9 rausnimmt, dann muss man ja eigentlich, wenn man
vorgeht wie beim letzten Mal, muss man hier dann den dritten Bucket
hier an der Stelle 1 neu verteilen.
Aber mit der 16 passiert jetzt an der Stelle nichts, also die muss man
nicht neu verteilen.
Also man merkt schon, das wird ein bisschen komplizierter.
Also man kann nicht so einfach sagen, ich verteile den Bucket jetzt
neu, sondern das hat einfach größere Auswirkungen auf die ganze
Datenstruktur.
Und deswegen funktioniert das leider nur so mit der Basis 2 im
Binärsystem.
Okay, das sind die drei Datenstrukturen, die ich vorstellen wollte heute.