Ja, willkommen zur aller-allerletzten Algorithmen 1 Vorlesung-Übung.
Es hat mir eigentlich großen Spaß gemacht, ich hoffe Ihnen auch
meistens.
Ich hoffe, die Klausur macht noch mehr Spaß, oder wahrscheinlich macht
sie keinen Spaß, sondern ich hoffe, Sie haben danach ein gutes Gefühl,
da geht es wahrscheinlich mehr darum.
Und um das ein bisschen zu unterstützen, machen wir heute also erstmal
weiter Wiederholung und dann gibt es noch Auswertung
Programmieraufgabe und ein Beispiel zu evolutionären Algorithmen.
Gut, wir waren bis zu dem Kapitel 6 gekommen, Prioritätslisten beim
letzten Mal und jetzt mache ich weiter mit den sortierten Folgen, die
halt bei uns so sind, dass wir sagen, eine gute Sichtweise ist, wir
haben eine doppeltverkettete Liste von Elementen, die sortiert ist
nach einem Schlüsselattribut und um jetzt schnell darauf zugreifen zu
können, haben wir zusätzlich eine Navigationsdatenstruktur, die ich
hier etwas wolkig dargestellt habe.
Ja,
ich habe dann hier angefangen mit binärer Suche in Arrays, aber das
kannten Sie ja ohnehin schon.
Wichtig ist bei diesen sortierten Folgen, wir haben so
Basisoperationen, einfügen, löschen, verändern und dann locate, das
ist halt das Besondere, verglichen mit einer Liste ohne
Navigationsdatenstruktur zum Beispiel.
Wir suchen gegeben einen Schlüssel, das kleinste Element mit einem
mindestens so großen Schlüssel wie der gegebene Schlüssel.
Das heißt insbesondere, wir können auch Elemente suchen, die nicht in
der Liste sind und das ist der wichtige Unterschied zur Hash-Tabelle.
Und dann gibt es viele andere Operationen, Minimum, Maximum, simple
Bereichssuche, Aufbauen, Konkatenieren, Spalten und wenn wir die
Datenstruktur noch augmentieren, um zusätzliche Informationen können
wir auch RANK- oder SELECT-Operationen in logarithmischer Zeit machen
oder Bereichsgrößen finden.
Genau, Abgrenzung ist zur Hash-Tabelle, dadurch, dass die kein Locate
kann und keine Range-Query, ein sortiertes Feld ist bei Updates
langsam, bestenfalls noch Bulk-Updates, Prioritätslisten unterstützen
nur Einfügen und Elite-Min, also eine viel spezialisiertere Menge von
Operationen.
Ja, es gibt eine ganze Reihe Anwendungen, wir haben dann angefangen
mit binären Suchbäumen, die in gewisser Weise am einfachsten sind und
dieses Konzept der durch Schlüssel gesteuerten Suche eigentlich sehr
schön darstellen.
Das Locate war da eine ziemlich simple Funktion, außer dass wir dann
einen Fall noch berücksichtigen mussten, dass das gesuchte Element
irgendwie einem weiter rechts steht, als man gedacht hat.
Das ist dann ein ganz guter Verständnis-Check, warum das auftreten
kann.
Das kann so, wie wir es gemacht haben, nur auftreten, wenn
zwischendurch mal was gelöscht wird.
Weil dann können hier nämlich so Navigations-Schlüssel stehen, die
unten in den Blättern gar nicht mehr drinstehen und dann muss man
manchmal einen weiterschauen.
Das war jetzt hier ein Beispiel dafür.
Das war auch ein gutes Beispiel dafür, warum Invarianten, sowohl
während der Suche, als auch Invarianten der Datenstruktur wichtig
sind, um herleiten zu können, was man hier machen muss.
Also hier konnte man dann mit dieser Spezialfallbehandlung tatsächlich
zeigen, dass man in jedem Fall das richtige Element findet.
Laufzeit war dann, man hätte gerne logarithmisch, aber das gilt nur,
wenn dieser binäre Suchbaum hinreichend balanciert ist.
Und das kriegen wir nicht geschenkt.
Also hier, wenn man zum Beispiel Elemente in sortierter Reihenfolge
einfügt, kriegt man hier im Prinzip wieder so eine Suchbaum
-Datenstruktur, die lineare Tiefe hat, statt logarithmischer.
Und dafür müsste man dann die Suchbäume irgendwie balancieren und da
gibt es mehrere Möglichkeiten und wir haben uns für die Möglichkeit
entschieden, also wir müssen dann entweder die Tiefe des Baumes
flexibilisieren, oder was wir gemacht haben, die Knotengerade.
Wir sagen, die haben nicht alle gerade zwei, die inneren Knoten,
sondern sie können gerade in einem Bereich von A bis B haben.
Und meistens war dann B gleich 2A.
Und dann kriegen wir nämlich eine Höhe des Baumes von LOG zur Basis A,
wenn A eine Konstante ist, ist das wieder logarithmisch, wenn nicht,
ist das auf den ersten Blick noch besser, aber die Suchzeit ist sowas
wie A mal LOG Basis A von N und da ist eine Konstante eine optimale
Wahl.
Ja, genau, Datenstrukturenvarianten von A-B-Bäumen waren so, die
Gerade der inneren Knoten waren zwischen A und B, der Grad der Wurzel
zwischen 2 und B, wichtiger Spezialfall, wo man wissen sollte, warum
das so ist, kann man auch schöne Mini-Aufgaben zu stellen, wird auch
bei Rechenaufgaben schnell mal vorkommen, gut, und die Blätter sind
halt diese Listen-Elemente und haben natürlich keinen Ausgangsgrad in
dem Sinne.
Ja, dann die Details, musste man halt ein bisschen gucken, wie man
damit umgeht, es gibt wieder ein Dummy-Element, um bestimmte
Spezialfälle abzufangen, das Locate steigt dann im Wesentlichen diesen
Baum runter, macht in jedem Item auch ein Locate, das im Prinzip eine
binäre Suche sein könnte.
Die Laufzeit ist dann halt Basis A von N im Wesentlichen.
Ja, die weiteren wichtigen Operationen einfügen und löschen, müssen
jetzt halt aufpassen, dass sie diese Invarianten auf dem Knotengrad
aufrechterhalten.
Und da ist halt das Problem, wenn man jetzt irgendwo ein Element
einfügt, das einen Knotengrad von B auf B plus 1 aufblasen würde, dann
würde man die Invariante verletzen, das ist jetzt hier der Fall, dann
spaltet man das in zwei Knoten der Größen B halbe und B halbe plus 1
auf und muss dann in dem älteren Knoten dazu halt einen weiteren
Verweis einfügen, der kann wieder zu einer Aufspaltung führen, das
macht man so lange, bis man halt einen Knoten hat mit Grad kleiner B,
dort erhöht sich dann einfach der Grad und man ist fertig.
Und im schlimmsten Fall läuft das ganz bis zur Wurzel durch, dann wird
die Wurzel aufgespalten und man fügt eine neue Wurzel vom Grad 2 ein.
Das ist die wichtigste Idee beim Einfügen und das sollte man
verstanden haben, alle anderen Details kann man daraus eigentlich
ableiten.
So ähnlich geht das beim Entfernen, da muss man halt auch schauen, was
mit den Invarianten passiert und da gab es zwei Fälle.
Wenn halt ein Knoten einen Grad kriegt, der kleiner a ist, dann ist
eine Möglichkeit, so eine Balance-Operation, der klaut sich von einem
Geschwisterknoten, ein Element, das geht nur dann schief, wenn dieser
Geschwisterknoten auch Grad a hat.
Dann haben wir hier einen Knoten vom Grad a, da einen vom Grad a-1,
aber dann sagt mir die Datenstruktur-Invariante, wenn ich die jetzt
zusammenfüge, also zusammenlöte, dann entsteht ein Knoten vom Grad 2a
-1 und das ist aber gerade kleiner gleich b, weil wir haben diese
Bedingung, dass b größer gleich 2a-1 war und das war einer der Gründe
dafür, das heißt, wenn es tatsächlich so ist, dass ich nichts klauen
kann, dann funktioniert die Fuse-Operation.
Die Fuse-Operation führt jetzt ihrerseits dazu, dass man im
Älterknoten von den beiden Knoten wieder was löschen muss, sodass die
sich auch wieder fortpflanzen kann nach oben.
Im Extremfall wird dann der Knotengrad der Wurzel von 2 auf 1
reduziert und dann kann man die Wurzel weglassen.
Das sind die wichtigsten Operationen bei A-B-Bäumen.
Wenn man die verstanden hat, der Rest eigentlich einfach.
Weitere Operationen, Concat und Split haben wir nicht gemacht, habe
ich hier nur erwähnt, Stoff wäre dann, dass Sie wissen, dass das in
logarithmischer Zeit geht, aber nicht, wie man es macht.
Aufbauen haben wir nicht im Detail gemacht, aber das ist so einfach,
das sollten Sie auch, wenn Sie eine Aufgabe dazu haben, selber können.
Das ist auch eine gute Übung jetzt als Vorbereitung.
Merge, nee, das müssen Sie nicht können.
Das ist zwar auch nicht wirklich schwierig, aber minimum, maximum,
Range -Suche oder so, das könnte man alles fragen.
Ich glaube, das haben wir auch im Prinzip gemacht.
Amortisierte Analyse von Insert und Remove haben wir nicht gemacht,
brauchen Sie entsprechend auch nicht zu können.
Augmentierung von Suchbäumen, da habe ich, glaube ich, ein bisschen
was zu gemacht, wir haben es in den Übungen gemacht, also da könnte
durchaus was zu drankommen.
Also zum Beispiel Elternzeiger mit abspeichern, was mache ich damit,
Teilbaumgrößen abspeichern, was mache ich damit.
Dann haben wir weitere, das war jetzt Blick über den Tellerrand.
Karteikasten, Array mit Löchern, da kann man schöne Aufgaben zu
stellen eigentlich, aber das ist dann nicht so, dass wir jetzt
erwarten, dass Sie da wissen, wie es geht, sondern wir würden Ihnen
dann in der Aufgabe sagen, also hier ist eine Array mit Löchern
-Datenstruktur, würden die spezifizieren und Sie dann bitten,
irgendeine Operation da mal zu beschreiben.
Externe Datenstrukturen machen wir nicht, ganzzahlige Schlüssel mit
Doppellogarithmisch machen wir auch nicht, das war alles nur Blick
über den Tellerrand, Erweiterung auf Zeichenketten und
mehrdimensionale Daten werden wir auch nicht machen, alles Blick über
den Tellerrand.
Die Zeiten hier sind da auch nicht so relevant, dann
Grafrepräsentation war das nächste Kapitel.
Ja, eine Sache, die man sich merken sollte, ist, dass wir eigentlich
alles mit gerichteten Grafen machen, was die Repräsentation angeht und
wenn wir einen ungerichteten Grafen haben, repräsentieren wir die
bigerichtete Variante davon, also einen, wo wir jede ungerichtete
Kante durch zwei Kanten in beide Richtungen ersetzen.
Die wichtigste Operation auf statischen Grafen ist die Navigation,
gegebenen Knoten liefern mir die ausgehenden Kanten und natürlich
Konstruktion oder Umwandlung und Ausgabe, aber das ist relativ simpel,
wobei man da natürlich auch schöne, kleine, einfache Aufgaben hier
stellen könnte.
Dynamische Grafen sollten Sie auch in der Lage sein, da irgendwas zu
bauen, da werden wir nur kleine Aufgaben zu stellen, weil das ja
relativ komplexe Datenstrukturen sind, aber zum Beispiel, wenn wir
sagen, definieren Sie eine Grafdatenstruktur, die das Einfügen von
Kanten erlaubt und zeigen Sie, wie die Füge-Kante-Ein-Operation
funktioniert, dann sollten Sie halt in der Lage sein, da für jeden
Knoten eine verkettete Liste von Kanten oder sowas anzulegen.
Kantenanfragen war so eine Operation, die nicht so ohne weiteres in
das Schema passt, wobei das für Grafen mit beschränktem Grad ohnehin
nicht so ein Problem ist, aber man kann die ja dann immer über
Hashtabellen -Zugriffe implementieren.
Also eine Kantenanfrage, ich gebe zwei Knoten, habe eine Hashtabelle,
in der alle Kanten drinstehen, dann kann ich das in erwartet
konstanter Zeit.
Dann gibt es eine Repräsentation, wo ich nur eine Liste von Kanten
habe, da wäre eine schöne Frage, nennen Sie zwei Grafen-Algorithmen,
die damit umgehen können.
Dann wäre eine Antwort, Konversion nach Adjacenz-Array, haben wir
erklärt, wie das geht, und Großkreis-Algorithmus zum Beispiel.
Oder wir würden Ihnen vielleicht ein anderes grafentheoretisches
Problem stellen, wo Sie sagen, hier ist nur diese Repräsentation, wie
können Sie das schnell, ohne explizit eine Adjacenz-Array
-Repräsentation zu konstruieren?
Also Adjacenz-Felder oder Adjacenz-Array, das waren so unsere
Hauptdatenstruktur, wo man sehr kompakt mit zwei Arrays einen
gerichteten Grafen so repräsentiert, dass man nur ein Maschinenwort
pro Knoten plus ein Maschinenwort pro Kante braucht im Wesentlichen.
Ja, was ganz witzig war, war, dass die Konversion von der Kantenliste
in Adjacenzfeld im Prinzip wieder unser Bucket-Sort war.
Ja, wenn man jetzt zusätzliche Informationen für Knoten und Kanten
braucht, nimmt man halt zusätzliche Arrays oder Strukturen mit
mehreren Einträgen, die diese Sachen halt speichern, da sollten Sie
auch in der Lage sein, so etwas vielleicht zu beschreiben.
Meistens sind unsere Aufgaben aber so high-level, dass Sie da gar
nicht ins Detail gehen müssen.
Aber Ihnen sollte halt klar sein, dass man das machen kann, wenn man
das vielleicht irgendwo braucht.
Genau, also hier, wir werden Sie nicht bitten, eine
Lederrepräsentation eines Grafen hinzumalen oder sowas.
Genau, Anpassung von Datenstrukturen.
Da wäre es halt auch denkbar, dass wir Sie bitten, irgendwie so eine
Custom -Grafrepräsentation zu entwerfen, die eine bestimmte schöne
Eigenschaft hat.
Aber irgendwas relativ Einfaches.
Ein Beispiel, das wir halt hatten, wo ich auch letztes Mal schon
gesagt habe, ist Erkennung eines Stacks mit dem Algorithmus, der auf
den ersten Blick Kanten löscht, also eine dynamische
Grafstatenstruktur braucht, aber wo wir mit diesem Pseudocode hier
gezeigt haben, dass das Einzige, was man im Prinzip braucht, ein
zusätzliches Array ist, wo pro Knoten der aktuelle Grad abgespeichert
wird und ein Stack, der uns die Knoten vom Grad Null sagt.
Und es könnte sein, dass wir so eine Art Algorithmus auch mal als
Aufgabe stellen, dass Sie sowas entwerfen sollen.
Bei der Adjacenz-Matrixrepräsentation haben wir gesagt, die ist außer
bei sehr dichten Grafen nicht so praktikabel, aber hat den großen
Vorteil, uns eine Verbindung zur linearen Algebra herzustellen, da
kann man auch wieder schöne Aufgaben stellen, wie man mit so zum
Beispiel Matrixmultiplikationen irgendwelche Sachen ausrechnet und da
muss man in diese Matrix vielleicht auch geschickte Dinge
reinschreiben oder so.
Implizite Repräsentation hatten wir Intervallgrafen als Beispiel, da
kann man auch sehr schöne Aufgaben stellen, weil das so Fünfseiler
sind, mit denen man dann bestimmte Probleme auf Intervallgrafen lösen
kann.
Und meistens lautet die Antwort, sortieren und scannen und dann das
Richtige tun.
Als Beispiel hatten wir einen Zusammenhangstest gemacht.
Und hier stand zum Beispiel, Übung Zusammenhangskomponenten finden,
hatten wir das als Übungsaufgabe?
Hatten wir Zusammenhangskomponenten finden als Übungsaufgabe?
Und wäre das eine schöne Klausuraufgabe?
Oder nächstes Jahr, wer weiß?
Das ist sowieso so, wir entwerfen jetzt Klausuraufgaben und am Ende
macht es nur die Hälfte in die Klausur, aber die werden dann halt ein
andermal verwurstet, nach Klausur, nächstes Jahr.
Gut, Zusammenfassung, dann Graftraversierung, hatten wir wieder dieses
Konzept gehabt, wie auch bei minimalen Spannbäumen.
Erst ein abstraktes mathematisches Konzept, nämlich wir bauen einen
Spannbaum auf, der sozusagen die Knoten alle erreicht, die man von
einem Knoten aus erreichen kann, das sind dann die Baumkanten und wenn
man die hat, definieren die andere Kategorien von Kanten, nämlich
vorwärts, rückwärts und querkanten und in Termen dieser abstrakten
Begriffe lassen sich dann wieder viele Grafenalgorithmen auch besser
erklären.
Wir haben uns dann die Breitensuche angeschaut, die eine besonders
einfache und intuitive Art der Exploration ist und uns auch sowas wie
Umgebung ermöglicht.
Und wie war das, es gibt da keine Vorwärtskanten, stimmt das?
Ja, die Implementierung gehe ich jetzt nicht darauf ein, das war
relativ simpel, dieser Baum wurde wieder repräsentiert durch so Parent
-Pointer, so ähnlich wie bei Dijkstra´s Algorithmus auch.
Eigentlich ist das hier Dijkstra´s Algorithmus, nur dass wir keine
Prioritätsliste brauchen, sondern mit einer Pfeife oder zwei Stacks
zum Beispiel arbeiten können, oder zwei Arrays.
Ja, Tiefensuche war dann so ein Beispiel für ein Algorithmen-Schema
oder Pattern, bei dem man Operationen initialisieren hatte, neun noch
nicht explorierten Knoten finden, die man dann exploriert und dann hat
man so eine Initialisierung für einen Teilbaum des DFS-Waldes, den man
da eigentlich berechnet und dann eine rekursive Funktion, die
Baumkanten und Nichtbaumkanten separat behandelt, die immer alles, was
sie sieht, markiert und sofort rekursiv wieder exploriert, deshalb
Tiefensuche, und dann am Ende einen Backtrack macht und dann weiß man,
alles, was von hier erreichbar ist, wurde erreicht.
Oder bereits in der vorherigen Traversierung besucht.
Ja, und wir haben dann verschiedene Instanzierungen dieses Schemas
gesehen, um zum Beispiel den DFS-Baum selber zu berechnen, besonders
simpel, eine DFS-Nummerierung oder eine Fertigstellungszeit
auszurechnen und wenn man das alles zusammenpackt, kriegt man daraus
eine Klassifizierung in Baum vorwärts, rückwärts und querkanten.
Und wir haben auch gesehen, wie die Finishing-Time einem im
Wesentlichen auch eine topologische Sortierung des Graphen gibt.
Wenn er a-zyklisch ist, dann könnte man wahrscheinlich schöne Aufgaben
stellen, wenn er nicht a-zyklisch ist, wie findet man das raus und wie
berechnet man dann einen Kreis oder sowas.
Das war nur ein Blick über den Tellerrand, aber Sie sollten vielleicht
wissen, was eine starke Zusammenhangskomponente ist, und die anderen
Sachen haben wir nicht so genau definiert, das war nur ein Blick über
den Tellerrand.
Man kann schöne kleine Kurzaufgaben zum Vergleich, Breitensuche und
Tiefensuche stellen.
Kürzeste Wege war das nächste Kapitel, da suchen wir alle kürzesten
Wege von einem Startknoten zu allen erreichbaren Knoten, das war die
Standardformulierung, und wir berechnen auch eine Repräsentation der
kürzesten Pfade.
Anwendungen gibt es eine ganze Menge.
Wichtigster Unterschied, also wichtigste Frage an die Eingaben war
dann, sind negative Kantengewichte zugelassen?
Wenn ja, muss man sich überlegen, gibt es negative Kreise in dem
Graphen und alle Knoten, die dann über negative Kreise erreichbar
sind, haben dann Abstand, Minus und Endlich.
Das ist eine kleine Komplikation.
Genau, a-zyklische Graphen hatten wir hier erstmal verschoben, weil
das im Prinzip am Ende dann relativ simpel wurde, einen
Linearzeitalgorithmus anzugeben, der Trick war ja im Wesentlichen, man
scannt alle Knoten in topologischer Reihenfolge.
Also statt diesem Dijkstra-Algorithmus, der sich irgendwelche
Prioritätslisten macht, berechnet man einmal offline eine topologische
Sortierung und scannt dann alle Knoten.
Scannen war, eines Knoten hieß, ich gucke mir alle ausgehenden Kanten
an und relaxiere die.
Für den Fall, dass wir einen allgemeinen Graphen haben, aber mit nicht
-negativen Kantengewichten, hatten wir dann Dijkstras-Algorithmus, da
gab es eine schöne Analogie zu einem Analogrechner auf Bindfaden- und
Knotenbasis.
Ansonsten hatten wir, wie gesagt, das Apparent-Pointer, tentative,
also vorläufige Distanzwerte, d, Kanten relaxieren hieß, guck mir die
Entfernung zu u an, addiere das Gewicht der Kante, und schaue dann,
gibt das eine Entfernung, die kleiner ist als die bisher bekannte
tentative Distance von v und wenn ja, verringere ich diesen Wert.
Dann hatten wir bewiesen, dass Dijkstras-Algorithmus diese kürzesten
Wege berechnet, was der im Wesentlichen macht, ist.
Für jeden Knoten eine Einfügeoperation, eine Prioritätsliste und eine
Delete -Min-Operation, sowie maximal eine Decrease-Key-Operation pro
Kante.
Dadurch, dass wir uns die Knoten in aufsteigender Reihenfolge ihrer
kürzesten Wegeentfernung zum Startknoten anschauen, war garantiert,
dass wir einen Knoten erst dann scannen, wenn er bereits eine
endgültige Distanz hat.
Das war dann ein Beweis, der hier drin steht und das wäre natürlich
auch, wenn wir eine komplexere Beweisaufgabe machen wollen, ein
Beispiel, wo man irgendwas dreht, wo man sagt, hier ist ein anderer
Algorithmus, zeigen Sie, warum das dann nicht mehr klappt, oder hier
ist ein anderer Algorithmus, zeigen Sie, dass das trotzdem
funktioniert, ja, das könnte man machen.
Laufzeit war dann im Wesentlichen bestimmt durch die Kosten für diese
Prioritätslisten -Operationen, die bei uns hier alle logarithmisch
waren, wenn man binäre Heaps verwendet.
Analyse im Mittel haben wir nicht gemacht, kommt auch nicht dran,
monotone, ganzzahlige Prioritätslisten, da könnte so eine Frage
kommen, wie zeigen Sie, dass Dijkstra das Algorithmus dieser
Monotonitätseigenschaft hat, aber wir werden keine Prioritätslisten
für monotone, also keine Implementierungen solcher Prioritätslisten
besprechen, weil das ist Stoff von Algorithmen 2, gut, dann haben wir
uns Algorithmen für den Fall, wo auch negative Kosten erlaubt sind,
angeschaut, da haben wir eigentlich was sehr Simples gemacht, im
Wesentlichen konnten wir zeigen, wenn alle Kanten auf einem kürzesten
Weg in der richtigen Reihenfolge relaxiert werden, und dabei spielt es
keine Rolle, ob die jetzt in falscher Reihenfolge vorher schon mal
relaxiert wurden, dann hat man am Ende die kürzeste Wegedistanz.
Und dann war der Bellman-Ford-Algorithmus der dümmste denkbare
Algorithmus, der das erreicht, der nämlich einfach sagt, ich relaxiere
alle Kanten n-mal hintereinander.
Und dann ist garantiert, aha, alle Kanten wurden in der ersten
Iteration relaxiert, prima, die dann wohl auch, in der zweiten
spätestens wird die relaxiert, in der dritten die und so weiter.
Also es war super simpel, zu beweisen, dass der korrekt ist, nur ist
halt leider im Allgemeinen viel teurer als der Dijkstra-Algorithmus.
Und wenn man dann genau hinschaut, kann man aus der Information, die
der Bellman-Ford-Algorithmus generiert, auch so Sachen machen, wie
negative Kreise tatsächlich finden, wenn es sie denn gibt.
Und der Christian hat dann, glaube ich, in der Übung zum Beispiel
erzählt, wie man im ganzen Graphen negative Kreise findet.
Was wir hier bei Bellman-Ford gemacht haben, war ja, ich habe einen
Startknoten.
Und dann findet man raus, ob vom Startknoten aus ein negativer Kreis
erreichbar ist.
Und der Christian hat aber dann erklärt, wie man sozusagen für den
ganzen Graphen global herausfinden kann, ob es negative Kreise gibt.
Obwohl die nicht notwendigerweise von irgendeinem Knoten alle
erreichbar sind, das ist ein kleiner Unterschied.
Ja, bei a-zyklischen Graphen war diese Eigenschaft, dass man die in
der richtigen Reihenfolge scannen muss, die Kanten, trivial, wenn man
das in topologischer Reihenfolge macht.
Wohlgemerkt, a-zyklische Graphen haben nicht nur den Vorteil, dass es
in Linearzeit geht, man also keine Lockfaktoren durch Prioritätslisten
hat, sondern ich darf sogar negative Kantengerichte erlauben.
Ja, dann das All-to-all-kürzeste-Wege-Problem haben wir im
Wesentlichen gelöst durch einmaliges Aufrufen eines One-to-all
-Algorithmus.
Und dann gab es viel Blick über den Tellerrand, der aber jetzt für
mich nicht so offensichtliche Aufgabenquellen liefert.
Also außer vielleicht, dass wenn man den Zielknoten scannt in
Dijkstra's Algorithmus, dass man dann wohl fertig ist.
Und naja, bidirektionale Suche könnte man eigentlich auch,
irgendwelche schönen kleinen Beweisaufgaben zu machen.
Aber der Rest hier war Blick über den Tellerrand.
Genau, diese Folien hatte ich noch nicht mal gezeigt, wir hatten dann
ja in der Übung stattdessen Contraction Hierarchies vorgeführt, da
könnten dann Aufgaben zu rauskommen, aber eben nicht irgendwie
Wissensabfrage zu Contraction Hierarchies, sondern wir definieren da
nochmal irgendwie so eine Eigenschaft und bitten Sie dann, einfache
Beweise zu machen.
Zum Beispiel, wir definieren, was so eine Knotenkontraktion macht und
dann sollen Sie beweisen, dass danach die kürzesten Wege im
verbleibenden Graph die gleichen bleiben oder sowas.
Genau, dann kam das Kapitel über minimale Spannbäume,
wo es wieder viele Anwendungen gab und da könnte man sich dann auch
irgendwelche Textaufgaben überlegen, wo dann am Ende die Antwort
lautet, ich muss einen MST berechnen oder ich muss einen kürzesten Weg
berechnen oder ich muss eine Breitensuche machen, solche Textaufgaben
wird es wohl irgendwie geben.
Ja, bei MST war es dann so, dass wir die Algorithmen eben aus zwei so
abstrakten Eigenschaften zusammengebaut haben, nämlich der
Schnitteigenschaft, die uns sagt, wenn wir den Graphen zerschneiden in
zwei Teile, dann kann man die leichteste zerschnittene Kante für einen
minimalen Spannbaum verwenden und umgekehrt in einem Kreis braucht man
die schwerste Kante nicht für einen minimalen Spannbaum.
Ja, dann gab es den Janik-Priem-Algorithmus, der ausgehend von einem
Startknoten einen minimalen Spannbaum wachsen lässt.
Das Spannende daran war, dass der fast identisch ist zu Dijkstra´s
Algorithmus, außer dass die Kantenrelaxation und die Definition der
Prioritäten etwas anders ist.
Entsprechend war die Laufzeit auch die gleiche.
Kruzkals-Algorithmus sortiert die Kanten in der Reihenfolge
aufsteigenden Gewichts und macht dann immer so einen Test, sind die
beiden Enden der gerade betrachteten Kanten in der gleichen Komponente
bezüglich des minimalen spannenden Waldes für die bereits betrachteten
Kanten?
Und wenn das so ist, kann ich die Kante wegwerfen, wegen der
Kreiseigenschaft.
Wenn das nicht so ist, sagt mir die Schnitteigenschaft, dass ich den
als minimale Spannbaumkante verwenden kann.
Und das Ganze ließ sich effizient implementieren, mithilfe der Union
-Find -Datenstruktur, die ist auch für sich betrachtet eine nützliche
Datenstruktur, die verwaltet eine Partition der Menge 1 bis N, also
eine Zerlegung in bisjunkte Teilmengen M1 bis Mk und die sind
dynamisch.
Am Anfang haben wir triviale Teilmengen, jedes Element steht für die
eigene Teilmenge und ich kann mit Aufruf der Union-Operation dann zwei
Teilmengen zu einer zusammenfügen und ich kann mithilfe der Find
-Operation sozusagen herausfinden, in welcher Teilmenge ein Element
ist.
Wir hatten das implementiert, indem wir so einen Repräsentanten
zurückgeben.
Und dann kann man einfach durch Vergleich der Repräsentanten zum
Beispiel feststellen, ob zwei Elemente in dem gleichen Block der
Partition sind.
Und das war genau das, was wir für den Großkarl-Algorithmus dann auch
brauchten.
Die Implementierung basierte im Wesentlichen auf Wurzelbäumen, also
Bäumen, wo wenn man Zeigern nachläuft, man an der Wurzel landet und
die verweist dann auf sich selber.
Und die Union-Operation hat im Wesentlichen die beiden Wurzeln
aneinander gehängt, also die eine Wurzel zu einem Kind der anderen
gemacht.
Das hat dann leider eine schlechte Worst-Case-Komplexität, deshalb
haben wir dann zwei Beschleunigungen gemacht, Pfadkompression, wenn
wir einmal suchen müssen, werden danach alle Zeiger auf die Wurzel
umgebogen, also wir machen die dynamisch, diese Bäume immer wieder
flach und Union-by-Rank, wo wir gesagt haben, wenn wir zwei Bäume
zusammenfügen, dann nehmen wir sozusagen den mit geringerem Rang als
den untergeordneten.
Und damit konnten wir dann nachweisen, dass die nur logarithmische
Tiefe haben, diese Bäume.
Wir konnten dann zeigen, dass wenn man nur Union-by-Rank macht, man
logarithmische Zeiten für Feind braucht.
Im Buch wird dann auch gezeigt, aber da gibt es keine Fragen zu, wie
man das mit Pfadkompression auch erreicht.
Und beides zusammen hat dann halt eine ziemlich spannende Komplexität,
nämlich amortisiert die inverse Ackermann-Funktion und die ist beinahe
konstant.
Und Sie müssen sich jetzt nicht auswendig lernen, wie die Ackermann
-Funktion lautet, und wir werden Sie auch nicht bitten, den Wert von A
5,5 hinzuschreiben oder sowas, aber Sie sollten sich vielleicht
gemerkt haben, dass es so komische geschachtelte Rekursionen gibt und
dass dann ganz wilde Dinge passieren können, was die
Wachstumsgeschwindigkeit angeht.
Das habe ich jetzt schon gesagt.
Ja, dann war das letzte Kapitel Optimierungsalgorithmen, durchgehendes
Beispiel war das Rucksack-Problem, also wie packt man eine Teilmenge
von Objekten so in einen Rucksack, dass eine Kapazitätsbegrenzung
erfüllt ist, und wir insgesamt den Profit maximieren,
dann haben wir gesagt, allgemein können wir versuchen,
Optimierungsprobleme durch Blackbox-Löser zu lösen, indem wir halt
eine deklarative Spezifikation des Problems machen und dann ein
Programmpaket nehmen, das halt mit der Art Spezifikation, die wir da
gegeben haben, allgemeine Lösungen findet.
Wir hatten da nur lineare Programmierung als ein Beispiel
kennengelernt, aber es gibt halt auch noch andere.
Dann habe ich erklärt, was lineare Programmierung ist, also wir haben
eine lineare Zielfunktion, lineare Constraints, wir haben dann mal
angenommen eine Anzahl von Variablen, die nicht negativ sein sollen,
es gab dann eine geometrische Interpretation, die im Zweidimensionalen
auch sehr anschaulich ist und man kann sich dann zum Beispiel an den
Ecken entlangkangeln, um ein Optimum zu finden.
Wir haben dann eine ganze Reihe Beispiele angegeben, kürzeste Wege
kann man durch ein lineares Programm spezifizieren, minimale
Spannbäume auch, aber das war ein bisschen komisch, weil wir da
exponentiell viele Constraints brauchten.
Wir haben dann so ein klassisches Anwendungsbeispiel uns angeschaut,
Tierfutter mischen, kosteneffizient, mit Verfeinerungen, ja, die
Algorithmen für lineare Programmierung war ein Blick über den
Tellerrand, wir werden da nichts Konkretes zu fragen.
Eine Erweiterung von lineare Programmierung war dann ganzzahlige
lineare Programmierung oder gemischt ganzzahlige lineare
Programmierung, wo halt einige oder alle der Variablen nur ganzzahlige
Werte annehmen dürfen.
Sehr oft waren das dann Entscheidungsvariablen, 0 oder 1.
Und dann war es auch so, manchmal hat man Probleme, die man als so was
hier, ganzzahliges lineares Programmierungsproblem formulieren kann,
und dann lässt man danach die Ganzzahligkeitsbedingungen weg, das
nennt man dann die lineare Relaxation, und die hat dann manchmal
interessante Eigenschaften, zum Beispiel, dass die Lösung so ist, dass
nur wenige Variablen tatsächlich einen gebrochenen Wert annehmen, und
da kann man sich dann überlegen, wie man den rundet oder wie man damit
dann halt sinnvolle Lösungen für das ganzzahlige Problem ableitet.
Beispiel war das Rucksackproblem.
Da war es so, wenn wir die Gegenstände nach Profitdichte sortieren und
nacheinander in den Rucksack packen und dann das Stück, das nicht mehr
reinpasst, sozusagen durchschneiden, dann ist das gerade die optimale
Lösung der linearen Relaxation.
Das haben wir nicht bewiesen, aber das könnten Sie, glaube ich, in der
Klausur auch beweisen, wenn wir kleine Hinweise geben.
Da gab es so ein Austauschargument,
genau, und wenn man dieses zerschnittene Element weglässt, kriegt man
halt Näherungslösungen.
Ja, das war jetzt so allgemeiner Blick über den Tellerrand, ich weiß
nicht, ob man hieraus groß Aufgaben bauen kann.
Ja, wir haben uns dann Gridi-Algorithmen angeschaut, eigentlich war
das, was ich gerade genannt habe, ja auch schon wieder ein Gridi
-Algorithmus.
Andere Beispiele waren Dijkstra, die beiden minimalen Spannbaum
-Algorithmen.
Wir haben dann gezeigt, wie man beim Rucksackproblem tatsächlich eine
Approximation um den Faktor 2 erreicht, indem man entweder die Lösung
des Gridi-Algorithmus nimmt, oder das Element mit dem höchsten Profit
nimmt, das überhaupt in den Rucksack passt.
Ja, das nächste war dann dynamische Programmierung, wo man optimale
Lösungen aus optimalen Lösungen für Teilprobleme systematisch aufbaut.
Was dabei wichtig war, ist so ein Austauschprinzip, dass es egal ist,
welche optimale Lösung Sie für die kleineren Probleme verwenden.
Wir haben das dann am Beispiel des Rucksackproblems vorgeführt, wie
das geht.
Dann baut man halt irgendwelche Tabellen auf und muss sich dann halt
überlegen, wie man, also aus dieser Tabelle kann man dann meistens
direkt ablesen, was der Wert der Zielfunktion in der optimalen Lösung
ist, man muss aber noch ein bisschen was zusätzliches tun, um die
Lösung dann tatsächlich rekonstruieren zu können.
Das sind sehr beliebter Fehler in Klausuren.
Wir stellen eine Aufgabe zu dynamischer Programmierung, geben Sie ein
Programm an, das eine optimale Lösung für Problem X berechnet.
Und dann kriegen wir einen wunderbaren Algorithmus, der den
Zielfunktionswert ausrechnet, aber keine Lösung berechnet.
Es gibt dann leider erhebliche Punktabzüge.
Also nicht vergessen.
Ja, falls Sie da so ein dynamisches Programmierungsproblem in der
Klausur lösen müssen, sollten Sie sich als allererstes die Frage
stellen, was sind denn jetzt die Teilprobleme.
Und das ist der kreative Teil und damit natürlich zusammenhängend, wie
setzen sich optimale Lösungen aus Teilproblemlösungen an.
Zusammen, vielleicht fragen wir auch nach einem Beweis, vielleicht
auch nicht, ich weiß es noch nicht, und dann müssen Sie vielleicht
noch einen Code angeben, der dann wirklich diese Tabellen ausfüllt und
Lösungen rekonstruiert.
Fragen dazu?
Ja, der Bellman-Ford-Algorithmus war auch sowas wie dynamische
Programmierung, es gibt noch weitere Anwendungen.
Bei dieser Teilproblemeigenschaft kann man böse auf die Nase fallen,
deshalb wirklich drüber nachdenken, manchmal geht die schief und auch
die Austauschbarkeit muss man sich gut überlegen.
Ja, dann haben wir uns angeguckt, systematische Suche, also wie kann
man einfach durch geschicktes Aufzählen aller sinnvollen Möglichkeiten
optimale Lösungen berechnen.
Wir haben uns dann zum Beispiel einen Branschen-Bound-Algorithmus für
das Rucksackproblem angeschaut, der halt so einen systematischen
Entscheidungsbaum aufbaut, nehme ich nun ein Objekt, nehme ich es
nicht.
Welche Objekte er jeweils als nächstes betrachtet war, wie er durch
diese Sortierreihenfolge nach Profitdichte bestimmt, und ganz wichtig
war, dass es so eine Berechnung von oberen Schranken gab, die man dann
verwenden konnte, um zu berechnen, ob es überhaupt noch lohnt, in
diesem Teilbaum weiterzusuchen.
Und das ist beim Rucksackproblem eine sehr effektive Beschränkung des
Suchraumes.
Ein Beispiel für das Rucksackproblem, vorgerechnet, da kann man auch
eine Rechenaufgabe zu stellen, gibt man eine andere Instanz und baut
mal diesen Baum hier auf, wobei das relativ viel Zeit braucht, weiß
nicht.
Das war ein weiteres Beispiel für so ein Algorithmenentwurfsschema, wo
man halt verschiedene Sachen dann frei bestimmen kann.
Wie verzweige ich, in welcher Reihenfolge, wonach mache ich
Fallunterscheidungen, was ist diese Bounding-Funktion und Zusatzsachen
wie Elimination von Sachen, die man schon gesehen hat.
Dann gab es lokale Suche, wenn man sich die systematische Suche nicht
leisten kann, kann man halt den Raum der zulässigen Lösungen sozusagen
nur abtasten.
Teile davon erkunden und hoffen dabei, gute Lösungen zu finden.
Im einfachsten Fall macht man da Hill-Climbing, man definiert eine
geeignete Nachbarschaft und guckt, gibt es in der Nachbarschaft eine
verbesserte Lösung.
Und was man aber auch machen kann, ist selbst Verschlechterungen unter
gewissen Umständen in Kauf zu nehmen und die Idee war, damit Lokalen
optimal zu entkommen.
Und evolutionäre Algorithmen haben das halt nochmal verallgemeinert,
indem sie halt nicht nur eine Lösung, sondern ganze Populationen
betrachten und auch Kombinationen aus mehreren Lösungen produzieren.
Ja, das war die Zusammenfassung.
Die Zusammenfassung der Zusammenfassung ist, wir haben was über
Datenstrukturen, Algorithmen, Entwurfstechniken und Analysetechniken
gelernt und ich danke Ihnen vielmals für das Interesse.
Dankeschön.
So, bevor der Timo jetzt gleich noch die Siege des
Programmierwettbewerbs kürt und Dinge von der Übung ausschließt für
die Klausur, erzähle ich jetzt noch was über evolutionäres Graph
-Partitionieren.
Das ist für die Klausur selber jetzt in den Details nicht so relevant,
aber es ist, denke ich, doch ganz interessant, mal Instanzen gesehen
zu haben für lokale Suche und für evolutionäre Algorithmen.
Genau, was Graph-Partitionierung ist, hatte ich schon einige Mal in
der Übung erzählt, ich wiederhole es trotzdem nochmal, also gegeben so
einen Graphen G mit Knoten und Kanten, sowie einer Kostenfunktion für
die Knoten, die zum Beispiel angibt, wie viel man rechnet auf so einem
Knoten und einer Kostenfunktion auf den Kanten, die zum Beispiel
angibt, wie viel man kommuniziert.
Und jetzt hat man zu diesem Graphen noch eine Zahl K gegeben und
möchte dann den Graphen in K-designierte Blöcke aufteilen, sodass das
Gewicht von jedem Block kleiner gleich 1 plus Epsilon mal diesem
durchschnittlichen Blockgewicht ist.
Und das Ziel nachher ist einfach, das Gewicht der Kanten, die hier
zwischen den Blöcken laufen, zu minimieren.
Und wenn jetzt auch die technischen Details von dem Graph
-Partitionierungsproblem nicht wichtig sind für die Klausur, die
Definition könnte durchaus interessant sein, sich mal anzuschauen,
also sowas könnten wir auch abfragen.
Um jetzt diesen evolutionären Algorithmus zu verstehen, versuche ich
ganz kurz nochmal ein sehr, sehr bekanntes Verfahren, was in der Graph
-Partitionierung verwendet wird, zu skizzieren.
Also dieses Verfahren, was hier dargestellt ist, nennt man nochmal
Mehrlevel -Verfahren.
Und in drei bis vier Minuten erzähle ich dann genau, wie diese
einzelnen Komponenten hier nochmal funktionieren.
Und einen Teil davon haben wir auch schon in der Übung gesehen.
Also dieses Mehrlevel-Verfahren versucht erstmal, zunächst aus einem
gegebenen Graphen eine Sequenz von kleineren Graphen zu erzeugen, die
alle ähnliche Eigenschaften haben wie dieser Eingabegraph.
Wenn dieser Graph dann nachher klein genug ist, dann verwendet man
einen teuren Algorithmus, zum Beispiel mit Breitensuchen, das haben
wir in der Übung gemacht, um den Graph initial zu partitionieren, das
heißt die Knoten hier tatsächlich den Blöcken zuzuweisen.
Das ist dargestellt durch diese blauen Linien hier.
Jetzt nimmt man diese Lösung von diesem groben Level und überträgt sie
auf das nächst feinere Level und das sehen wir gleich genau, wie das
funktioniert auf der nächsten Folie.
Und durch dieses Übertragen habe ich dann den gleichen
Zielfunktionswert auf dem nächst feineren Level in dieser Hierarchie
wie auf dem groben Level hier.
Und jetzt verwendet man lokale Suchen, das passt genau in das Schema,
was Professor Sanders gerade erzählt hat, um diesen Kantenschnitt zu
verbessern.
Diese lokalen Suchen bewegen also einfach diese Knoten zwischen diesen
Blöcken hin und her, um den Kantenschnitt zu reduzieren.
Schauen wir uns einmal an, wie diese Kontraktion funktioniert, das ist
wichtig, um nachher diesen evolutionären Algorithmus zu verstehen.
Diese Kontraktion kann man zum Beispiel mit Matchings machen.
Also ein Matching ist eine Menge von Kanten, die paarweise nicht
inzidenzen, wie zum Beispiel diese rot hervorgehobenen Kanten hier.
Wenn ich jetzt zum Beispiel diese Kante hier noch hinzufügen würde,
wäre es kein Matching mehr, weil wir dann zwei inzidente Kanten
hätten.
Jetzt kann man zwei Knoten, die durch eine Kante gematcht sind,
kontrahieren, indem man sie, diese beiden Knoten hier zum Beispiel,
durch einen groben Knoten ersetzt.
Und dessen Gewicht wird dann gerade auf das Gewicht gesetzt, die Summe
der Eingabeknoten.
Und wenn da eine parallele Kante entstehen würde, dann ersetzt man das
durch eine einzelne Kante, dessen Gewicht gerade die Summe der
parallelen Kanten ist.
Im Allgemeinen geht man dann halt so vor, dass man zunächst erstmal
irgendeine Kantenbewertungsfunktion berechnet, die einem sagt, wie gut
es ist, jetzt eine spezielle Kante zu kontrahieren, und berechnet dann
einfach mit irgendeinem Algorithmus, den ich jetzt nicht erläutern
werde, ein gewichtetes Matching.
Genau, jetzt hat man diese Kontraktion gemacht, und das hatte ich
vorhin schon erwähnt, dann macht man initiale Partitionierung, zum
Beispiel mit Breitensuchen, und man sieht jetzt, wenn ich die
kontrahierten Knoten in den gleichen Block packe, wie sein grober
Repräsentant hier, das ist hervorgehoben durch die Farbe und die blaue
Linie, dann ändert sich zum einen der Kantenschnitt nicht, weil hier
steht A plus B plus irgendwas, und das ist genau der Kantenschnitt,
den wir hier haben, und zum anderen, dieses Balance Constraint, was
dieses Problem enthält, ändert sich ebenfalls nicht.
Das heißt, ich kann auf diesen groben Leveln exakt rechnen und Knoten
hin und her bewegen, um tatsächlich die Zielfunktion bezüglich des
Eingabeproblems zu reduzieren.
Der nächste Schritt in diesem Schema ist initiale Partitionierung, und
das haben wir schon in der Übung gemacht, das sind einfach
Breitensuchen, da gehe ich jetzt nicht drauf ein.
Ganz wichtig ist dann dieser lokale Verbesserungsschritt, und das ist
jetzt auch einfach eine Beispielinstanz für lokale Suchen, die in der
Vorlesung ja behandelt wurden.
Lokale Suchen, im Graph-Partitionierungsfall, habe ich schon erwähnt,
bewegen Knoten zwischen den Blöcken, um den Kantenschnitt zu
reduzieren.
Und eine Möglichkeit, das zu tun, ist genau hier dargestellt.
Also wir haben erstmal einen Graphen gegeben, der ist perfekt
balanciert in genau zwei Teile geteilt, und die Teile sind dargestellt
durch diese blau gestrichelte Linie hier.
Was jetzt eine lokale Suche macht, ist, die berechnet für jeden
Randknoten, den wir hier sehen, also Randknoten heißt, ich habe einen
Nachbarn, der in dem anderen Block ist, berechnet dieser Algorithmus
einen Gewinn.
Und dieser Gewinn gibt gerade an, wie stark sich der Kantenschnitt
reduziert, wenn ich diesen speziellen Knoten zum anderen Block
hinüberbewege.
Das heißt, für den Knoten, der jetzt hier grün hervorgehoben ist,
haben wir einen Gewinn von 1, da er einen externen Grad, das heißt,
die Anzahl der Nachbarn im linken Block von 3 hat, und einen internen
Grad, das ist das hier drüben, das sind dann die Anzahl der Nachbarn
im eigenen Block von 2, und dann haben wir 3 minus 2 ist gerade der
Gewinn von 1.
Jetzt gehen diese lokalen Suchen immer so vor, dass sie immer einen
Knoten von der einen Seite auf die andere bewegen und dabei die Blöcke
immer alternierend auswählen.
Also wenn ich jetzt den grünen Knoten hier bewege, dann ändert sich
die Partition und ich habe also eine neue Lösung erhalten und wie
schon gesagt, die Blöcke werden dann immer alternierend ausgewählt.
Das heißt, ich muss jetzt einen von links nach rechts hinüber bewegen
und dann wieder von rechts nach links.
Und der Algorithmus ist dann auch in einem gewissen Maße greedy, weil
er immer den Knoten mit dem höchsten Gewinn gerade zum anderen Block
hinüber bewegt.
Wenn man jetzt ein bisschen in technische Details reinschaut, dann
stellt man fest, man kann auf der linken Seite eine Prioritätsliste
verwenden, auf der rechten Seite eine Prioritätsliste verwenden, also
eine adressierbare Prioritätsliste und hat dann schon die nötigen
Datenstrukturen zusammen, um das in Linearzeit zu implementieren.
Außerdem, wenn ich diesen Knoten hier bewegt habe, muss ich die
Gewinne der Nachbarknoten updaten und kriege damit dann einen lokalen
Suchalgorithmus.
Man erhält also insgesamt dann nachher so eine Sequenz von Partitionen
hier, genau, von Partitionen mit dem Zielfunktionswert 7, 6, 5, 5 und
6.
Und jetzt stellt man zum einen nochmal fest, dass sich der
Zielfunktionswert hier erhöhen kann, das heißt, ich kann mich
verschlechtern.
Aber das ist kein Problem, denn die lokale Suche, also in dem Bild
hier sieht man die Partition, hier den Kantenschnitt und wir haben
dann gesehen, dass sich der Kantenschnitt verschlechtern kann und die
lokale Suche macht dann einfach alle Änderungen rückgängig, bis ich
bei der Partition bin, die den besten Schnitt hat und balanciert ist,
die also gerade das Balance Constraint erfüllt.
Und am Ende hat man dann hier einfach eine bessere Partition
berechnet, in dem Fall hat die Kantenschnitt 5 und der ursprüngliche
Kantenschnitt war 7.
Genau, da habe ich eben schon gesagt, das kann man dann in Linearzeit
implementieren.
Okay, jetzt muss ich ein paar Sachen überspringen, wir springen jetzt
direkt zum evolutionären Algorithmus.
Also ich wiederhole nochmal, was generell so ein evolutionärer
Algorithmus macht.
Das ist hier in diesem kleinen Algorithmus dargestellt, also man
erzeugt jetzt mal Individuen, bei uns sind das jetzt Partitionen von
Graphen, also jeder farbig dargestellte Knoten in diesem großen Kreis
hier, das ist unsere Population und jeder farbig dargestellte Knoten
ist jetzt eine Partition, ein Individuum von unserer Partition.
Und jetzt wollen wir so lange Partitionen in diesem Framework
kombinieren und bessere Partitionen erhalten, bis irgendein Stopp
-Kriterium erfüllt ist und am Ende geben wir dann die beste Partition
zurück.
Das heißt, man wählt zunächst erstmal zwei Partitionen, also
Individuen von unserer Population aus, führt einen
Kombinationsoperator aus, das ist der, den ich jetzt gleich erklären
werde, als Instanz für den evolutionären Algorithmus, und dann kriegt
man eine neue Partition, das ist die grüne hier, und fügt die in die
aktuelle Population ein.
Und dadurch, dass diese Population nicht beliebig groß werden soll,
muss man halt eins entfernen, und in dem Fall entfernen wir jetzt halt
dieses rote Individuum, was einen schlechteren Kantenschnitt hat als
das neu berechnete Individuum.
Und das ist jetzt ein bisschen komplizierter, gerade weil ihr ja nicht
so in dem Thema drin seid.
Hier ist eine Möglichkeit, diese Kombinationsoperation durchzuführen.
Dargestellt ist hier jetzt die Kontraktionsseite von diesem
Mehrlevelverfahren.
Und vorhin hatte ich erwähnt, dass für die Kontraktion immer Matchings
berechnet werden, und diese Matchings, also gematchte Knoten,
kontrahiert werden.
Jetzt modifiziert man diese Kontraktion so, dass man zunächst erst mal
zwei Partitionen gegeben hat, P1 und P2, und diese Partition ist hier
einmal durch die blaue Linie und einmal durch die graue Linie
dargestellt.
Und diese Kontraktion wird so modifiziert, dass die Schnittkanten, das
sind gerade die gestrichelten Kanten in diesem Bild hier, dass die
nicht kontrahiert werden können.
Das heißt, der Matching-Algorithmus kann jetzt nur Kanten
kontrahieren, die innerhalb von diesen Blöcken hier sind.
Und das hat den Vorteil, dass ich jede dieser Eingabepartitionen hier
nachher als initiale Lösung für diesen groben Graphen benutzen kann.
Und da die lokalen Suchen, die wir ja gesehen haben gerade eben, uns
zusichern, dass der Kantenschnitt nicht schlechter wird, ist das
Kindobjekt, das wir erzeugen, nachher hat einen Kantenschnitt
mindestens so gut wie das bessere der beiden Eltern.
Also wir verwenden immer die bessere Eingabepartition als Startlösung
und werden dadurch dann halt unser Offspring, unsere Kindpartition hat
dadurch einen Kantenschnitt, der wenigstens so gut ist wie bei der
Eingabepartition.
Und wir sehen jetzt gleich in dem Beispiel, dass ich dann gute Teile
von Lösungen, was auch immer das jetzt bedeutet, einfach austauschen
kann.
Wir haben jetzt hier einen zufälligen geometrischen Graphen, der
zweimal partitioniert ist, nämlich einmal auf der linken Seite und die
Partition soll hier oben schlecht sein und hier unten gut und zum
anderen auf der rechten Seite, die Partition soll hier oben gut sein
und hier unten schlecht.
Und wir wollen jetzt eigentlich eine Partition erzeugen, die genau die
besseren Teile von diesen beiden Partitionen vereint, nämlich einmal
einen guten Kantenschnitt hier unten und einen guten Kantenschnitt
hier oben, also irgendwie was dazwischen.
Der Kombinationsoperator legt jetzt diese beiden Partitionen
übereinander und ich wiederhole nochmal, dass die Schnittkanten hier
in diesem Bereich nicht zulässig sind, um zu kontrahieren.
Das heißt, der Matching-Algorithmus kontrahiert Kanten in diesem roten
Bereich, in dem blauen Bereich, in dem grauen und in dem grünen
Bereich und kann am Ende dann eine von den beiden Eingabepartitionen
als staatlosen Grund nutzen.
Also man macht das so lange, bis keine matchbare Kante mehr vorhanden
ist und man erhält dann sowas wie den Graphen, der hier dargestellt
ist.
In diesem Graphen steht jeder farbig hervorgehobene Knoten hier für
einen farbigen Block und die Gewichte von diesem Knoten sind dann
gerade die Anzahl der Knoten in den Blöcken und die Kanten zwischen
diesen Knoten in dieser abstrakten Struktur hier widerspiegeln gerade
die Anzahl der Kanten zwischen den Blöcken hier.
Jetzt verwende ich eine von den beiden Eingabelösungen als
Staatlösung, das ist jetzt auch wieder dargestellt durch die Farben,
das heißt, wir haben den jetzt durch blau und grau in zwei Teile
geteilt und wir sehen jetzt schon, dass dieser graue Knoten hier unten
sehr, sehr stark an den blauen Block angebunden ist, aber sehr, sehr
schwach in den eigenen Block.
Das heißt, wenn ich jetzt wieder diesen Begriff des Gewinns verwende,
für diese lokalen Suchen, dann hat dieser Knoten hier gerade einen
sehr, sehr hohen Gewinn
und unsere lokalen Suchen werden diesen Knoten dann gerade den blauen
Block zuordnen.
Und was ich durch diese Knotenbewegung hier gemacht habe, ist, ich
habe diesen gesamten grünen Bereich hier dem blauen Block zugeordnet.
Das ist genau diese Kontraktion von diesem Mehr-Level-Verfahren macht
das.
Und außerdem habe ich dann den Kantenschnitt reduziert, das sieht man
so ein bisschen durch die Dicke der Kanten hier.
Das heißt, ich habe jetzt die schlechten Teile hier unten ausgetauscht
und habe eine Partition erzeugt, die die guten Teile von beiden
Eingabepartitionen vereint und ich habe eine Instanz für einen
evolutionären Algorithmus.
Und lokale Suchen macht man dann immer noch auf jedem Level von diesem
Mehr -Level-Verfahren.
Also das war jetzt schon mal die Idee von diesem evolutionären
Algorithmus Und in der Praxis sieht man dann, dass das einen echten
Vorteil bringt gegenüber wiederholten Ausführungen von so einem Mehr
-Level -Partitionierer.
Also diese Kurve hier sagt so ein bisschen was wie, wie entwickelt
sich der Kantenschnitt über die Zeit für meine Eingabeinstanzen im
Mittel.
Hier ist der sequentielle Algorithmus aufgetragen und hier der
evolutionäre Algorithmus und dann sieht man, dass man einen echten
Vorteil hat durch evolutionäre Algorithmen.
Genau, also das war es zum Thema evolutionäre Graph-Partitionierung.
Bevor der Timo jetzt gleich startet, noch ein paar Worte vielleicht
zur Klausur von meiner Seite aus.
Für mich war das damals immer wichtig, irgendwie nicht, wie sagt man
so schön, Bulimie lernen zu machen, also nicht den ganzen Kram da rein
zu pressen und dann nach der Klausur direkt wieder zu vergessen,
sondern so zu lernen, dass man den Kram auch versteht, weil dann wären
die Aufgaben ziemlich einfach, ja, die Klausur wird schon ziemlich
schwer, glaube ich.
Insbesondere im Vergleich zu den letzten beiden Jahren, also ich
glaube, die Klausuren von uns sind dann doch etwas schwieriger, aber
das ist gar nicht so schlecht, also wenn man viel, viel Zeit
investiert und richtig schön übt und auch so übt, dass man die
Aufgaben dann nachher schnell beantworten kann und nicht nur irgendwie
beantworten kann, sondern schnell und gut, dann sollte das mit der
Klausur auch kein Problem sein.
Genau, das von meiner Seite und der Timo, genau, damit übergehe ich an
Timo.
Danke.
Auch noch ein paar Worte zur Klausur gleich von mir, wenn ich...
Nee, nee, das stimmt nicht.
Okay, noch ein paar, ja genau, also die Klausuren in den letzten
Jahren waren schon sehr einfach, die sind sehr rechenlastig gewesen,
was ich da gesehen habe.
Damit kann man bei uns möglicherweise nicht mal bestehen.
Also bei uns muss man ein bisschen denken.
Sprich, ich würde euch raten, es ist ja eine unheimliche Fülle von
Stoff und ich würde euch raten, nicht tiefensuchmäßig den zu lernen,
sprich nicht bei Seite 1 anzufangen, dann Seite 2 zu lernen, Seite 3
zu lernen, sondern breitensuchmäßig zu lernen.
Erst die Kapitelüberschriften durchschauen, dann die ersten Seiten und
genau.
So kommt ihr dann besser durch.
Ich habe meistens immer tiefensuchmäßig gelernt und das bin nie
durchgekommen.
Und deswegen Rat an euch, breitensuchmäßig zu lernen.
Gut, noch ein paar Organisationssachen zur Klausur.
Anmelden müsst ihr euch, ganz wichtig.
Wer hat sich noch nicht angemeldet und möchte mitschreiben?
Mal kurz Hand hoch.
Alle angemeldet?
Top, weil bei einigen gab es Probleme, also wenn es Probleme gibt, uns
fragen oder E-Mail schreiben an diese beiden Stellen, die hier gezeigt
werden.
Es gab irgendwie Anmeldeprobleme, aber es scheint ja im Großen und
Ganzen ganz gut zu funktionieren zu haben.
Genau, nochmal wiederholen, also für die Klausur braucht ihr einen
roten oder einen schwarzen Stift, einen blauen oder einen schwarzen
Stift, keinen roten und keinen grünen.
Ihr braucht euren Studiausweis und ihr dürft mitnehmen ein
handgeschriebenes Blatt Papier mit allem möglichen drauf, was ihr
wollt.
Letztes Mal habe ich noch einige maschinengeschriebene gesehen, die
sammeln wir diesmal ein.
Das geht nicht.
Also kopieren oder sowas, das geht auch nicht.
Also handschriftlich kopieren natürlich schon.
Okay?
Vorgewarnt.
Für die Klausur gibt es Bonuspunkte, je nachdem, wie gut ihr oder wie
fleißig ihr in den Übungen wart.
Insgesamt habe ich errechnet, dass es 305 Übungspunkte gibt.
Das ist nur bei einem Blatt, glaube ich, schwierig gewesen, bei dem
ersten oder sowas, da gab es plus X, da haben wir dann statt X zwei
eingesetzt, dann kommen 305 raus.
Okay?
Und diese Zusatzpunkte, diese richtig schweren Aufgaben, die sind dann
natürlich nicht enthalten, sprich, wenn man die macht, kommt man eher
auf 100%.
Ja, und dann habe ich das ausgerechnet, je nachdem, wie viele Punkte
ihr habt, gibt es Bonuspunkte in der Klausur, aber nur bis zu 5% der
Klausur, der Klausurpunkte und man kann nicht allein mit diesen
Punkten bestehen.
Sondern man muss erst so bestehen und dann kriegt man bessere Note.
Frage?
Nein?
Okay.
Ich glaube, das waren jetzt die technischen Details.
Jetzt kommt der Programmierwettbewerb.
Und zwar hatten wir ja DNA-Assemblierung dran und hier so kurze
Statistik von dem, es gab insgesamt sieben Teilnehmer, immerhin,
sieben verschiedene Programme, erstaunlich viele Programmiersprachen,
nämlich C, C++, sogar Java, ein Java-Programm, ein C-Sharp-Programm
und sogar ein Basic-Programm.
Also, warum auch nicht?
Okay, und ja genau, verschieden kompliziert, wobei das hier diese,
also das zählt, glaube ich, soweit ich weiß, Leerzeichen nicht mit und
Kommentare auch nicht mit.
Also das sind echte Lines of Code.
Okay.
Genau, diese sieben Einsendungen habe ich bekommen und da das doch
relativ nah beieinander liegende Ergebnisse waren, habe ich insgesamt
zehn Testdurchlaufe machen müssen, um dann auszurechnen, wie groß die
Fehlerabweichung ist.
Und am Ende sieht man dann doch, also das Basic-Programm hatte doch
einen größeren Fehler
und eins von denen terminierte halt über Nacht nicht, in so zehn
Stunden oder sowas, aber okay, das habe ich dann irgendwann mal
abgeschossen.
Und genau, also dieses hier ist doch deutlich drüber über dem Rest und
wenn man jetzt genau anguckt, hier die zwei sind noch relativ gleich
in der Summe aller Fehler, die beiden sind noch mal ein ganzes
Stückchen besser als die beiden und der hier sticht dann doch heraus.
Das ist der Johannes Batzil, der ist jetzt aber schon abgereist zu
seinen Eltern.
Also der hat gewonnen, aber seinen Gutschein kriegt er dann nächste
Woche irgendwann mal bei mir.
Der Nummer zwei war Fabian Miltenberger.
Wo ist der?
Ist der da?
Dann komm mal vor.
Und ihr dürft klatschen.
So,
genau, du darfst uns gleich noch was erzählen, wie du es geschafft
hast.
Du kriegst erstmal deinen Gutschein so überreicht, wunderbar.
Und dann haben wir uns entschieden, da die anderen beiden doch sehr
nahe beieinander sind hier, zwei dritte Plätze zu vergeben.
Sprich, der Julian Labet und der Hauke Hennington kriegen beide den
vierten Platz.
Wo sind sie?
Da hinten.
Bei den dritten Platz, habe ich natürlich gesagt, das habe ich gerade
gesagt.
Jetzt muss ich gucken, ob es den richtigen ist.
Und für Algorithmenbücher einsetzen, ja?
Genau.
Ich kann ja auch noch gratulieren.
So, und dann...
Genau, und mit dem Gewinn kommt aber auch die Verpflichtung, uns zu
erzählen, was du gemacht hast.
Der Johannes hat sich da fein aus dem Staub gemacht, aber der Fabian,
der erzählst uns jetzt ein bisschen, was er gemacht hat.
Also, hier, total unvorbereitet.
Das ist viel Geld.
Und damit man dich auch hört...
Ja,
hört man mich?
Gut, scheint so.
Bevor ich jetzt zu dem komme, wie ich die Aufgabe gelöst habe, werde
ich erst kurz nochmal wiederholen, was eigentlich die Aufgabe war, da
ich die Vermutung habe, dass den meisten die nicht mehr ganz präsent
sein dürfte.
Es ging eben um die menschliche DNA.
Dabei wurde nur ein sehr kleiner Teil betrachtet, dieser DNA.
Und unserem Programm gegeben war einerseits eben so eine Referenz,
eben ein Ausschnitt aus der DNA.
Diese Referenz repräsentiert, wie die DNA an einer bestimmten Stelle
allgemein beim Menschen aussieht.
Weitergegeben sind sogenannte Reeds.
Diese Reeds sind dabei Fragmente aus einer Patientendna.
Und diese Patientendna genau ist gesucht.
Das Ganze ist sogar noch relativ nahe an der Realität, weil in der
Realität will man ja auch manchmal eben die DNA eines Patienten
erfahren.
Doch dummerweise hat man dafür noch keine sonderlich guten Geräte, um
diese herauszufinden.
Daher, die besten Geräte, die man hat, können eben nur solche
Fragmente aus dieser DNA extrahieren.
Und diese sind dann noch zu einem Überfluss fehlerbewertet.
Und man weiß nicht, in welcher Reihenfolge diese zur Patientendna
stehen.
Aufgrund dieser Fehlerbehaftung von ganzen zwei Prozent liegen uns so
viele Reeds vor, dass diese ungefähr die Patientendna zehnmal
abdecken.
Und diese Abweichung von der Patientendna zur Referenz, diese 0,1
Prozent, sind ja etwa das, was unser Programm nachher extrahieren
hätte sollen.
Kurz noch, worum es sich überhaupt handelt bei diesen DNAs.
Das hattet ihr ja schon im Biologieunterricht.
Die DNA besteht eben aus vier verschiedenen Säurebasenpaaren.
Diese werden abgekürzt durch die Buchstaben A, G, C und T.
Und da es sich bei der DNA um so etwas wie eine Kette handelt, lässt
sich diese nun als String repräsentieren.
Das heißt, diese Linien hier sind eigentlich nichts anderes als sehr
lange Strings.
Und in dieser Form waren uns die Daten auch gegeben.
Ein naiver Lösungsansatz hier.
Erstmal, wie man hier vorgehen kann, ist, dass man herausfindet, wie
man die Reads anordnen müsste, damit sie eben an der Stelle stehen, wo
sie der Patientendna nach stehen müssten.
Und anschließend durch Überlagerung von diesen Reads auf die
Patientendna schließt und durch die Überlagerung eben die Fehlerrate
von zwei Prozent eliminiert.
Das Hauptproblem hier ist also, wie ordnet man diese Reads an, damit
eben die Patientendna rauskommt.
Da die Patientendna nicht gegeben, sondern gesucht ist, wird hierfür
die Referenz benötigt.
Ein naiver Ansatz wäre hier, für jedes einzelne Read, für jedes
einzelne Read, dann diese Referenz hier zu bewegen und dabei jeweils
sich die Ähnlichkeit anzusehen und am Ende das Read an die Position
von der Referenz zu schieben, an der eben die größte Ähnlichkeit
vorherrscht.
Dass das jedoch eine relativ schlechte Laufzeit hätte, kann sich jeder
selbst überlegen.
Daher bin ich vorgegangen, indem ich als allererstes die Referenz
indiziert habe.
Dabei geht es darum, für eine Teilsequenz fester Länge aus der DNA
sofort die Frage beantworten zu können, wo überall in der Referenz
tritt diese Teilsequenz auf.
Dafür sind dann einige Vorbereitungen notwendig.
Zuerst einmal, was benutzt man für dieses Indizieren?
Da kommt einem natürlich nichts anderes in den Sinn, als erstmal eine
Hashtabelle zu benutzen.
Und in diese trägt man dann anschließend Teilsequenzen aus der
Referenz ein.
Dieses Qi ist dabei eine Teilsequenz fester Länge.
Fester Länge bedeutet, dass diese Sequenzen, die man hier eben
einträgt, immer die gleiche Länge haben.
Und was das konkret bedeutet, das erwähne ich dann nachher noch.
Diese Teilsequenzen werden also in die Hashtabelle eingetragen und
dabei als Qi verwendet.
Und als Werte verwendet man die Position, wo in dieser Referenz diese
Teilsequenz herkommt.
Dabei ist klar, dass für so einen Eintrag hier mehrere Positionen
möglich sind.
Das heißt, die eigentlichen Werte in dieser Hashtabelle hier sind so
etwas wie Listen von Positionen.
In meinem Fall waren das dann Unbounded Arrays, weil die Cache
-Effizienter sind.
Beispielhaft hat man jetzt hier in der Hashtabelle an dieser Stelle
einen Eintrag.
Und der verweist eben auf die Position, wo diese Teilsequenz in der
Referenz zu finden ist.
Systematisch geht man dabei so vor, dass man eben am Anfang das
aufbaut, indem man hier so durchscannt quasi.
Und dabei diesen Schritt des Eintragens in die Hashtabelle jeweils
vornimmt.
Am Ende könnte das dann so aussehen.
Und damit wäre der Schritt der Indizierung auch schon abgeschlossen.
Und nun kommt die eigentliche und auch zeitaufwendigste Arbeit, der
Zuordnung der Reads zu dieser Referenz.
Dazu nimmt man sich nun ein Read hier her.
Und scannt dieses auch quasi mit diesen Teilsequenzen fester Länge
durch.
Und schaut dabei für jede Teilsequenz, wo überall in der Referenz
diese zu finden ist.
Durch die Hashtabelle funktioniert das ja relativ schnell.
Daraufhin markiert man sich in der Referenz diese Position.
Also die Position, an die man das Read an der Referenz anlegen müsste,
damit eben diese Teilsequenz mit der Referenz und dem Read
übereinstimmt, sich sozusagen überdecken.
Das scannt man jetzt also auch, dieses Read, durch.
Und am Ende könnte das dann so aussehen.
Diese Kreuzungen stehen eben für diese möglichen Positionen.
Das sind Markierungen.
Und die Stelle, die am Ende die meisten Markierungen erhält, die
scheint ja am sinnvollsten zu sein, als Wahl für die Position von
diesem Read.
Also schiebt man da dieses Read dorthin.
Gleich verfährt man nun noch mit den verbleibenden Reads, sodass das
dann vielleicht so aussehen könnte.
Und jetzt kommt auch schon der letzte Schritt, und zwar das
Überlagern.
Hierbei wählt man für jede Position das Säurebasenpaar aus, das von
den Reads hier, die überlagern sich ja hier im Idealfall, am
häufigsten vorgeschlagen wurde.
So versucht man eben diese 2% Fehlerrate von den Reads, diese
Lesefehlern, zu eliminieren.
Das allein wäre ja noch gar nicht so schwierig.
Aber daher noch hier etwas zu den Testdaten erstmal.
Also es gab über 1,6 Millionen Reads, diese roten Linien.
Diese alle zuzuordnen, ist an sich schon zeitaufwendig, aber die
Referenz stammt auch nochmal aus über 52 Millionen Säurebasenpaaren.
Das heißt, es gab auch über 52 Millionen Positionen anfangs, die
möglich waren für jedes Read.
Da wäre auch dieser naive Ansatz, den ich anfangs erwähnt habe, viel
zu zeitaufwendig.
Zu meinem Programm, diese Hash-Tabelle, die ihr gesehen habt, die hat
2 hoch 24 Einträge, also über 16 Millionen.
Diese Keys, also die Teilsequenzen fester Länge, hatten eine Länge von
12 Zeichen.
Und hier sieht man auch, diese 2 hoch 24, hier ist durchaus kein
Zufall.
Weil es sich herausgestellt hat, dass es eben am effizientesten ist,
wenn für jede Teilsequenz genau nur ein Eintrag in dieser Hash-Tabelle
existiert.
Und da es nur 4 verschiedene Zeichen gibt, lässt sich jedes einzelne
mit 2 Bit kodieren.
Und somit so ein Schlüssel aus 12 Zeichen mit Hilfe von 24 Bits
darstellen.
Das Programm, wenn es dann läuft mit diesen Testdaten, benötigt die
ganze Zeit weniger als 2 GB Hauptspeicher.
Das war bei mir insofern sinnvoll, dass die meisten Rechner, die ich
zum Testen zur Verfügung hatte, mit Windows liefen, und dort geht das
irgendwie nicht, dass 32-Bit-Programme mehr als 2 GB Arbeitsspeicher
nutzen können.
Zur Parallelisierung, dieses Zuordnen der Reads konnte man relativ gut
parallelisieren.
Da war es auch sinnvoll, dies zu tun, und auf einem Achtkernrechner
hat das wohl auch einen deutlichen Geschwindigkeitsvorteil gebracht.
Insgesamt hat das Programm ungefähr 520 Sekunden auf dem Testrechner
gebraucht.
Ja, das war akzeptabel.
Und ich habe für mein Programm C verwendet.
Ja, Herr Sanders?
Also die Frage ist, was passiert, wenn für ein Read, für ein Read hier
mehrere Positionen hier die gleiche Bewertung bekommen.
Dafür kann man sich Strategien überlegen, was dann gemacht werden
soll.
Bei mir verwende ich eine, nach der ich, also diese Positionen werden
anhand dieser Keys hier ermittelt.
Ich gehe bei mir so vor, dass wenn eben mehrere Positionen sehr
ähnliche Bewertungen bekommen, für diese noch einmal extra die
einzelnen Zeichen verglichen werden und daraus nochmal eine
Ähnlichkeit ermittelt wird, die Hoffnung hierbei ist eben, dass dabei
dann noch einmal ein etwas klarerer Unterschied zur Ähnlichkeit
herauskommt.
Wenn dem aber nicht der Fall ist, dann hat man ein Problem, das
zumindest ich nicht genauer gelöst habe.
In dem Fall wird einfach zufällig eins gewählt, beziehungsweise immer
die erste Position dann.
Das hier ist jetzt also mein Sourcecode.
Das sind etwas weniger als 500 Zeilen.
Vielleicht nicht das Schönste und falls ihr den hier nicht sofort ganz
nachvollziehen könnt, wird der glaube ich auch nochmal irgendwo
hochgeladen werden.
Lässt sich auf jeden Fall machen.
Wie schon zu Anfang erwähnt wurde, ich bin nicht der Gewinner, also
ich habe nicht den ersten Preis gewonnen, sondern nur den zweiten.
Und was macht jetzt das Gewinnerprogramm aus, also was unterscheidet
dieses von meinem?
Dazu kann ich auch nochmal etwas kurz sagen.
Der Hauptunterschied dürfte wohl sein, dass nicht die Referenz
indiziert wird, sondern die Reads, also diese roten Linien.
Anschließend werden nicht die Reads durchgegangen und zugeordnet,
sondern die Referenz wird durchgegangen und dabei geschaut, welche
Reads eben wo in der Referenz ganz gut passen würden.
Reads, die dabei sehr gut passen, also Ähnlichkeiten von über 99%
aufweisen, werden dabei sozusagen mit der Referenz verschmolzen.
Das heißt für zukünftige, also dabei wird ja auch wieder die Referenz
durchgescannt, und für zukünftige Versuche, Reads der Referenz
zuzuordnen, wird diese Änderung dann auch schon berücksichtigt.
Wenn ein Read noch nicht ganz genau zugeordnet werden konnte, aber nur
mit sehr hoher Wahrscheinlichkeit zugeordnet werden kann, Ähnlichkeit
so über 96%, dann wird das für dieses Read vermerkt, aber dieses Read
wird noch nicht festpositioniert.
Und angenommen, es sollte später nochmal eine Stelle kommen, an die
dieses Read besser passt, dann wird eben dieser Wert aktualisiert.
Der letzte Schritt ist dann wieder relativ ähnlich.
Die Reads, die noch nicht festpositioniert wurden, die werden jetzt an
die Stelle gesetzt, die eben für Sie am wahrscheinlichsten war.
Die festpositionierten Reads, für die hat man schon eine Position.
Zusätzlich kann auch die Referenz sozusagen als Grundlage verwendet
werden, falls keine Reads vorhanden sind an einer Stelle.
Und so erreicht man über Überlagerung dann auch eben die Patienten
-DNA.
Ja, und das war es dann auch schon soweit meinerseits, vielen Dank.
Also vielen Dank, schöner Vortrag.
Das wirkliche DNA-Assemblierungsproblem ist ja nochmal 40 Mal größer
oder so, sprich die ganzen Zahlen hier multiplizieren sich 30 Mal.
Ne, 60 Mal.
Okay, also nochmal gratuliere und wunderbar.
Jetzt kommen noch ein paar relevante Sachen für euch, nämlich eine
kurze Übersicht über die Sachen, die wir hier in der Übung gemacht
haben.
Und zwar ist diese Übersicht jetzt garantiert nicht vollständig.
Also ich kann jetzt nicht nochmal die Übung wiederholen, aber ich kann
sozusagen die Übersicht, die größte Ebene der Breitensuche, die
oberste Ebene der Breitensuche wiederholen.
Und auch einige Sachen tatsächlich jetzt ausschließen.
Die erste Übung war Urkalkül, sehr wichtig natürlich.
Jetzt da nicht im Einzelnen durch.
Was wir garantiert nicht machen in der Klausur ist, euch Karatsuba
-Aufmann diese Rekursionen nachrechnen lassen, die irgendwo im ersten
Übungsblatt, Aufgabe 4 glaube ich, da waren.
Was wir auch natürlich nicht machen, sind generierende Funktionen.
Hat der Chris schon zweimal angekündigt, dass das nicht dran ist.
Der wird schon darauf aufpassen.
Hash-Tabellen und amortisierte Analyse, sehr wichtig.
Was eine Anwendung von Hash-Tabellen ist, ist der Blumenfilter und den
machen wir auch nicht.
Insbesondere nicht diese Wahrscheinlichkeitsformeln, die da irgendwo
in der Übung drin vorkommen.
Und eigentlich mein Lieblingsthema war dieses Average Case Insertion
Sort, was ich euch vorgerechnet habe, das müssen wir leider auch
ausschließen.
Danke!
Aber alle anderen Sorts natürlich, ganz Kernthema.
Bestimmt.
Die fünfte Übung ist irgendwie leer.
Kann man auch nichts ausschließen.
Und Rot-Schwarz-Bäume haben wir auch schon explizit vorher
ausgeschlossen.
Und zwar komplett.
So, und bei Graphen gab es zwei große Übungen dazu.
Alle Details dieser Graph-Partitionierung kommt nicht dran.
Aber das Problem als solches sollte euch bekannt sein.
Aber nicht, wie man es im Detail jetzt löst.
Das kann der Chris.
Und von der Übung, die ich über Graphen gemacht habe, gehen wir nur so
weit, dass wir die einfachen Sätze behandeln.
Sprich, Cayley und Euler und Hamilton-Kreise machen wir nicht.
So, und bei der zehnten Übung, da kamen unsere beiden Kollegen und
haben euch sehr weit über die Vorlesung hinausgehenden Sachen erklärt.
Nämlich die Contraction Hierarchies und den Filterkursgrad.
Beides kommt natürlich nicht dran.
Was aber vielleicht drankommt, sind lineare Programmierungen, also das
Grundkonzept solltet ihr verstanden haben.
Aber natürlich nicht der Dualitätssatz, den habe ich auch gar nicht
erklärt.
So, aus der elften Übung ist dynamische Programmierung natürlich sehr
wichtig.
Aber nicht die Anwendung in dem Viterbi-Algorithmus, den ich euch
gezeigt habe.
Sprich, die ganze WLAN-Geschichte.
Aber einfachere Probleme.
Genau, und heute ist nicht besonders viel übrig.
Genau, was gibt es noch für Fragen?
Das war es nämlich, glaube ich.
Frage?
Peter?
Kapitel, also die Folien der Vorlesung, kapitelindiziert.
Was heißt das?
Nochmal.
Also, soweit ich weiß, die Folien, so eine Art Übersicht, also die
erste Seite der Folie...
Ein Inhaltsverzeichnis, genau.
Müsst ihr euch selber machen, das ist ja nicht so schwierig.
Noch Fragen?
Sonst natürlich später.
Ansonsten sind wir fertig für heute.
Wünschen wir euch noch viel Erfolg beim Lernen und...
Genau, bis in den nächsten Semestern.