Schnelle Fourier-Transformation, eine klassische Methode, um bestimmte
technische Anwendungen sinnvoll zu machen.
Also Fourier-Transformation macht man, um eine Funktion in
Frequenzanteile zu zerlegen.
Und man kann das Ganze diskret machen.
Und dann kann man es eben auch schneller machen.
Die schnelle Fourier-Transformation ist eine ganz wichtige Methode.
Es sind dicke Bücher darüber geschrieben worden.
Die wesentlichen Ideen kann ich Ihnen hier auf wenigen Folien
darstellen.
Und ich nutze die schnelle Fourier-Transformation für ein anderes
Problem.
Und zwar ist das Problem, das ich jetzt Ihnen zur Motivation gebe, ich
möchte zwei Polynome modifizieren.
Zwei Polynome enden gerade.
Wenn ich die modifiziere, ich habe keine weiteren Informationen jetzt
hier, also allgemeine Polynome enden gerade.
Polynome p und q möchte ich modifizieren mit Koeffizienten a, i und b,
i.
Und was dann rauskommt, ist ein Polynom des Gerades 2n,
selbstverständlich, mit irgendwelchen Koeffizienten ck.
Und die einzelnen ck sind halt berechnet aus den entsprechenden
Koeffizienten der Potenzen von x, die ich halt bei diesem
Ausmultiplizieren gerade kombinieren muss.
Und das müssen ja immer Koeffizienten sein, deren Indizes zusammen
genau k ergeben.
Also habe ich eine Reihe von Kombinationen dieser Koeffizienten, a, i,
b, k minus i, die Summe aller dieser Kombinationen, gibt gerade
jeweils eine Potenz x hoch k, deswegen der Wert ck.
Und es ist offensichtlich, wenn ich hier mir anschaue, wie groß dieser
Aufwand ist, hier treten im schlimmsten Fall n Terme auf, n Produkte,
und das nicht nur einmal, sondern in der Größenordnung n treten hier
halt in der Größenordnung n häufig mal solche Koeffizienten auf,
solche Summen auf, das heißt ich habe insgesamt quadratisch viele
Operationen auszuführen, um die Koeffizienten c, k zu berechnen.
Alle diese c, k.
Also der Einzelne, jedes Einzelne braucht im schlechtesten Fall n
Operationen, also sogar etwas mehr, 2n, aber insgesamt sogar 2n
Koeffizienten, quadratische Anzahl von arithmetischen Operationen.
Und nun ist das, was ich Ihnen jetzt darstelle, eine interessante
Methode, wie man Probleme anders berechnen kann.
Das ist ein weiterer genereller Ansatz, wie ich bei der Lösung von
Problemen vorgehen kann, um etwas zu vereinfachen.
Und in diesem Fall betrachten wir folgendes, das Problem, das ich
Ihnen gerade dargestellt habe, ist dieses Problem.
Zwei Polynome p und q, dargestellt durch die Koeffizienten, oder
natürlich durch irgendeinen x, die möchte ich transformieren in das
Produkt r, mit den Koeffizienten c0 bis c2n.
Die Frage ist, wie berechne ich diese c0 bis c2n aus den Koeffizienten
a, i und b.
Und wir haben gerade gesehen, der Aufwand für diesen Vorgang ist
offensichtlich n².
Und jetzt ist die Idee, ich kann ja ein Polynom auf verschiedene Art
und Weise darstellen.
Ich kann das machen mit den Koeffizienten.
Ich kann aber auch ein Polynom darstellen durch die Werte an einer
bestimmten Anzahl von Stellen.
Wenn ich also eine Funktion darstelle durch die Werte an n Stellen,
oder n plus 1 Stellen, kann ich dadurch eindeutig ein Polynom
endengerades leben.
Damit sind die Koeffizienten eindeutig bestimmt.
Das heißt, ich kann eine Koeffizienten-Darstellung von Polynomen auch
durch eine Werte-Darstellung ersetzen.
Hier habe ich sogar nicht nur n plus 1 Stellen genommen, sondern 2n
plus 1 Stellen.
Warum?
Weil ich hier unten eine Darstellung haben möchte meines
Produktpolynoms an 2n plus 1 Stellen, c0 bis c2n.
Wenn ich aber die Werte-Darstellung habe, die mit irgendeinem Aufwand
hergestellt werden kann, naja, der naive Aufwand wäre, ich muss jetzt
an 2n plus 1 Stellen das Polynom auswerten, das ist jeweils lineare
Aufwand, macht also quadratischen Aufwand.
Quadratischer Aufwand, um erstmal die Darstellung meines Problems zu
verändern, bringt ja noch nicht viel.
Das Interessante ist aber, wenn ich jetzt diese Werte-Darstellung habe
meiner beiden Polynome p und q, dann brauche ich ja nur jeweils die
Werte an den entsprechenden Stellen zu multiplizieren und bekomme die
Werte des Produktpolynoms.
Also das r von x ist da gleich p von x mal q von x.
Das mache ich für jeden dieser Punkte, das sind aber gerade 2n plus 1
Operationen.
Das heißt, dieser Aufwand hier ist linear.
Da muss ich dummerweise nochmal zurück transformieren, das geht durch
entsprechend wieder, aufgrund dieser Darstellung mit 2n plus 1
Punkten, kann ich eindeutig die Koeffizienten eines Polynoms
bestimmen, das genau durch diese Punkte geht.
Und damit habe ich hier den Aufwand dafür, diese Interpolation oder
diese Bestimmung der Koeffizienten, ist wieder quadratischer Aufwand
in der klassischen Vorgehensweise.
Und das Interessante ist, wenn ich O1 und O4 mir angucke in diesen
beiden Operationen, für die kann ich eine schnelle Fourier
-Transformation anwenden.
Das heißt, das ist das, was hier das Wesentliche ist, ich kann von
quadratischem Aufwand für die Darstellung oder für die Transformation
der Darstellung eines Polynoms von Koeffizienten in Wertedarstellung,
kann ich die schnelle Fourier-Transformation verwenden, das geht in 2n
log n.
Dann brauche ich hier nochmal linearen Aufwand für die Multiplikation.
Die Rücktransformation ist vom algorithmischen Schema her das Gleiche
wie die Hintransformation.
Und ich kann das mit dem gleichen Aufwand n log n machen.
Und habe dann insgesamt auf diesem Wege hier einen Aufwand von n log
n.
Der Aufwand hier direkt runter war quadratisch, also ist der Umweg
über diese Transformation in eine andere Darstellung ein deutlicher
Zeitgewinn.
Das ist eben auch eine wichtige Erkenntnis, man sollte, wenn man ein
schwieriges Problem zu lösen hat, zunächst mal sehen, ein
Lösungsansatz ist häufig einfach das Problem anders darzustellen, was
sich dann auf einmal andere algorithmische Möglichkeiten ergeben.
Und das sehen wir eben hier am Beispiel dieser Multiplikation von
Polynomen, die kann ich offensichtlich auf die Art und Weise
verbessern.
Kleine Randbemerkung, wenn ich allgemein irgendwelche Zahlen
modifizieren möchte, große Zahlen, wenn ich die modifizieren möchte,
haben sie mit klassischem Ansatz, also wenn Sie zwei n Bezahlen
modifizieren, Aufwand n².
Das hat sehr viel zu tun auch mit dieser Polynom-Modifikation, wobei
Sie bei einer Modifikation von Zahlen ja nicht die Koeffizienten
einfach so stehen lassen können, sondern Sie haben da ja
Einschränkungen für die Werte der Koeffizienten.
Das sind ja gerade die entsprechenden Darstellungen in der
entsprechenden dezimalen oder binären Darstellung.
Also da müssen Sie entsprechend noch die Überträge rüberschieben und
so weiter.
Das ist noch ein bisschen aufwendiger.
Aber man kann tatsächlich zeigen, mit einem etwas intelligenteren
Einsatz von schnellen Fourier-Transformationen kann man auch das
Produkt von zwei Zahlen in Zeit n log n hinbekommen, wobei n die
Anzahl der Bits ist.
Das ist aber nicht trivial.
Ehe ich von der schnellen Fourier-Transformation reden kann, muss ich
jetzt mal die diskrete Fourier-Transformation darstellen.
Und das ist das, was wir hier machen.
Die Auswertung eines Polynoms an geeignet gewählten Stellen.
Und jetzt kommt also dieser Begriff der enden Einheitswurzeln.
Was sind das für besondere Stellen?
Das sind Werte von x, die zur enden Potenz erhoben gerade 1 ergeben.
Also über den komplexen Zahlen oder über einem endlichen Körper.
Jede Nullstelle dieses Polynoms x hoch n minus 1 ist eine sogenannte
ende Einheitswurzel.
Einheitswurzel, deswegen, weil das eine Wurzel ist von x hoch n, ist
gleich 1.
Und für x² ist es einfach, da haben Sie einfach plus und minus 1.
Quadrat jeweils ergibt 1.
Und wenn ich also jetzt ende Einheitswurzeln habe, dann nenne ich eine
solche Einheitswurzel primitiv.
Genau dann, wenn für alle diese J aus n minus 1 gilt.
Also diese Darstellung habe ich Ihnen, glaube ich, schon mal gesagt,
dass diese ganze Zahl in eckigen Klammern heißt, das sind die Werte
von 1 bis n minus 1.
Also 1 bis zu dem Wert, der da steht.
Also eine ende Einheitswurzel heißt primitiv, wenn alle ihre Potenzen
ungleich 1 sind, solange das J dieser Exponent kleiner als n minus 1
ist und ungleich 0.
Also Omega hoch J ungleich 1 für alle Werte ungleich 0 oder n.
Also für die, wenn wir uns das anschauen, also das ist klar, wenn das
so ist, dann habe ich n, wenn das eine primitive Ende Einheitswurzel
ist, dann ist also die, das Produkt, Quatsch, die Menge aller solchen
Potenzen dieser primitiven Einheitswurzel, gerade die Menge aller
enden Einheitswurzeln.
Also es kann keine weiteren Einheitswurzeln geben, die sind dann alle
durch diese, da sind ja gerade n solche verschiedenen, und es kann,
für x hoch n minus 1 gibt es halt maximal n verschiedene Werte von x,
die diese Gleichung erfüllen und entsprechend haben wir dann, wenn das
primitiv ist, haben wir hier gerade ja Omega hoch 0 wäre oder Omega
hoch n ist 1 und die Omega von hoch 1 bis Omega hoch n minus 1 sind
alle ungleich 1.
Das heißt, die sind alle verschieden und damit ist das genau die Menge
der enden Einheitswurzeln.
Also wenn ich hier Omega hoch i hernehme, irgendein Omega hoch i, dann
ist das eine ende Einheitswurzel, weil ich natürlich Omega hoch i,
wenn ich das hoch n nehme, die ende Potenz davon, dann ist das ja
gleich Omega hoch n und das hoch i genommen und das ist gleich 1.
Also das ist eine einfache Überlegung und die einfachen Beispiele sind
halt die zweiten Einheitswurzeln, minus 1 und plus 1, minus 1 ist die
primitive zweite Einheitswurzel, weil minus 1 hoch 1 ist minus 1,
minus 1 hoch 2 ist schon 1, mehr gibt es dann nicht, ich habe gesagt
2, die vierten Einheitswurzeln, da ist i, genau, i ist hier die
primitive Einheitswurzel, primitive vierte Einheitswurzel, wenn Sie i
Quadrat nehmen, ist das minus 1, i hoch 3 ist minus i, i hoch 4 ist 1,
minus 1 Quadrat.
Achten Einheitswurzeln entsprechend, Wurzel aus i und so geht das
systematisch weiter.
Das sind also die enden Einheitswurzeln und die primitiven enden
Einheitswurzeln.
Und wenn Sie sich das genauer anschauen, dann stellen Sie ein paar
Eigenschaften fest.
Sie stellen zum Beispiel fest, Sie können hier jeweils in der Mitte
einen Strich machen
und stellen fest, die erste Hälfte und die zweite Hälfte, ups, ich
wollte nicht das minus 1 durchstreichen, also hier, da wollte ich
durchgehen.
Wenn Sie die erste Hälfte, die linke Hälfte anschauen und die rechte
Hälfte, ist die rechte Hälfte gerade die erste Hälfte und überall ein
Minuszeichen davor.
Also mal minus 1 genommen.
Das heißt eigentlich brauchen Sie nur die erste Hälfte zu kennen.
Damit haben Sie schon alle.
Und es ist so, wenn Sie eine primitive Einheitswurzel quadrieren, also
eine primitive Ende Einheitswurzel quadriert, ist eine primitive
Enthalte Einheitswurzel.
Ja, das ist also auch einfach.
Und diese Eigenschaften nutzen wir gleich aus.
Das heißt, wir können einerseits sagen, ich brauche mir eigentlich nur
die ersten 4 anzugucken oder die ersten N-Halbe anzugucken.
Die anderen sind einfach nur die ersten N-Halbe mit negativen
Vorzeichen.
Also mal minus 1, nicht mit negativen Vorzeichen, mal minus 1
genommen.
Und außerdem komme ich von den Enten-Einheitswurzeln zu den N-Halbten
Einheitswurzeln durch Quadrierung.
Das sind die Eigenschaften, die ich hier ausnutze.
Also das ist hier das Erste.
Erst mal Omega hoch N-Halb ist natürlich minus 1.
Deswegen haben wir genau diese Eigenschaft, dass in der zweiten Hälfte
alle gerade minus 1 mal Omega hoch i sind.
Und das Omega-Quadrat ist gerade eine primitive Enthalte
Einheitswurzel.
Und wenn ich mir das jetzt anschaue, wie ich eigentlich diese
Auswertung eines Polynoms mache für alle Enten-Einheitswurzeln, dann
heißt das im Prinzip, ich habe hier meinen Vektor der Koeffizienten
Jetzt habe ich also hier ein Polynom N-ersten Grades, das ich auswerte
für die Enten-Einheitswurzeln.
Dann muss ich dieses Polynom auswerten für Omega hoch 0, das sind
alles Einsen.
Also Omega hoch 0 ist 1, deswegen sind alle Potenzen von 1 auch 1.
Das ist genau das Produkt dieser Koeffizienten mit der ersten Spalte.
Für Omega hoch 1 ist also das Polynom an der Stelle Omega, da habe ich
genau hier die Potenzen von Omega.
Und entsprechend für Omega-Quadrat und so weiter, das sind die ganzen
Enten -Einheitswurzeln bis Omega hoch N-1.
Also das hier entspricht Omega hoch 0 und hier habe ich Omega hoch N
-1.
Und das sind entsprechend genau diese Berechnungen, die ich machen
muss.
Und ich berechne hierbei jeweils den Wert des Polynoms für die
jeweilige Einheitswurzel.
So kann ich diese diskrete Fourier-Transformation darstellen an den
Enten -Einheitswurzeln.
Polynom N-ersten Grades.
Das Interessante ist, wenn ich die Rücktransformation machen möchte,
ich möchte aus den Werten, den N-Werten an den Enten, die ich also
vorher berechnet habe, jetzt möchte ich daraus die Koeffizienten
meines Polynoms zurückrechnen.
Dann bekomme ich das durch diese Berechnung, die hier unten steht.
Ich muss also diesen Werte-Vektor nehmen, den durch N dividieren und
entsprechend mit einer Matrix multiplizieren, deren Elemente ganz
ähnlich aussehen wie das, was ich hier vorher hatte.
Da steht aber jetzt nicht Omega hoch 1, sondern da steht Omega hoch
minus 1, hoch minus 2.
Das heißt, hier habe ich wieder N-Werte und das ist im Prinzip eine
gleichartige Transformation, das ist wieder eine Fourier
-Transformation von der Struktur her.
Das heißt, ich kann sowohl die Transformation von Koeffizienten in
Werte -Darstellung, als auch die Transformation von Werte in
Koeffizienten -Darstellung, als auch eine diskrete Fourier
-Transformation darstellen.
Und diese diskrete Fourier-Transformation wollen wir jetzt durch einen
sinnvollen algorithmischen Ansatz beschleunigen.
Das, was wir hier stehen haben, braucht zunächst mal quadratische
Zeit.
Und jetzt machen wir das effizienter und wollen auf N log N
runterkommen.
Und das können wir nur, indem wir genau diese Eigenschaften, die hier
oben stehen, ausnutzen.
Jetzt werden Sie gleich sehen, wie das funktioniert.
Also die schnelle Berechnung funktioniert wieder so, dass wir einen
Divide -and-Conquer-Ansatz machen.
Aber ein bisschen anders als vorher.
Wir machen hier einen Ansatz, dass wir uns unser Polynom hernehmen.
Das ist das Polynom.
Ich mal das mal anders hin.
Also hier steht es natürlich.
Ich mal das mal einfach hier hin.
Wenn wir hier jetzt A0, A1, A2, A3, A4 hätten und A5, dann würde ich
das aufteilen in zwei Polynome.
Das eine, das schreibe ich jetzt A0, A2, A4 hin.
Und das andere, da schreibe ich jetzt hin A1, A3, A5.
Das heißt, ich habe die auseinandergezogen.
A0 habe ich übernommen.
A1 habe ich darüber geschoben.
A2 habe ich übernommen.
A3 darüber geschoben.
A4 habe ich dahin genommen.
Und A5 bleibt da drin.
Und diese Operation, die ich hier mache, ist eine Operation, die man
auch nennen kann ein Perfect, in diesem Fall, Unshuffle.
Was hat das damit zu tun?
Was ist ein Perfect Shuffle?
Das kennen Sie aus dem Kartenspiel.
Sie haben zwei Kartenstapel.
Hier so zwei Kartenstapel.
Und jetzt wollen Sie die zusammenbringen.
Gehen Sie einmal so durch.
Und Sie haben die zusammengebracht.
Das heißt, wenn ich zwei Kartenstapel habe, will ich die einfach
ineinander verschränken.
Und ein Perfect Unshuffle ist genau das Gegenteil, dass ich die
auseinanderziehe.
So ist es.
Also eine einfache Operation, eine Standardoperation, die Sie in
vielen algorithmischen Ansätzen wiederfinden werden.
Und die wird uns noch ein paar Mal begegnen, insbesondere bei
Parallelalgorithmen.
Eine sehr einfache Operation.
Wir nehmen gerade die geraden Koeffizienten und die ungeraden
Koeffizienten.
Da wir die Hälfte der Koeffizienten nehmen, betrachten wir einfach
zwei Polynome des halben Grades.
Und ich habe also jetzt ein Polynom mit den geraden Koeffizienten.
Das betrachte ich an der Stelle x².
Und an den ungeraden Koeffizienten auch an der Stelle x².
Und ich habe dann also a0 plus a2x² plus a4x04 plus an-2xn-2.
Und ich habe das an den ungeraden Koeffizienten a1 plus a3x² plus
a5x04 und so weiter bis plus an-1xn-2.
Und wenn ich jetzt das gesamte Polynom daraus berechnen möchte, habe
ich also jetzt das Polynom mit den geraden Koeffizienten zu nehmen,
den Wert plus den Wert, den ich mit den ungeraden Koeffizienten
ausgerechnet habe für x².
Da muss ich aber noch einmal mit x modifizieren, damit ich die
richtigen Kombinationen habe.
Da fehlt ja jeweils ein x.
Also Pu x² mal x.
Und jetzt finden wir also hier wieder so eine Darstellung wie sie
vorhin bei der parallelen, bei der Überlegung, wie kann ich parallel
ein Polynom auswerten.
Da hatten wir das auch so gehabt.
Da hatten wir aufgeteilt in zwei Polynome halben Grades und kam da
genau so eine Darstellung.
Jetzt schauen wir uns das nochmal spezieller an.
Das x sind in diesem Fall ente Einheitswurzeln.
Und jetzt müssen wir diese Polynome Pg und Pu, das sind jetzt Polynome
halben Grades, die müssen wir jetzt für die enthaltenen
Einheitswurzeln ausrechnen.
Das machen wir einfach rekursiv nach dem gleichen Verfahren.
Dann habe ich diese Werte und kann also jetzt mein Polynom, das ich
eigentlich berechnen möchte, das P an diesen Stellen der enten
Einheitswurzeln, berechnen für Omega hoch 0.
Das ist das Gerade-Polynom an der Stelle Omega hoch 0.
Zum Quadrat ist aber das Gleiche.
Entsprechend Omega hoch 0 obendrauf addiert mal Omega hoch 0, das ist
1.
Also das ist einfach.
P von Omega ist Pg von Omega Quadrat plus Pu von Omega Quadrat mal
Omega.
Und entsprechend für alle anderen Potenzen dieser enten Einheitswurzel
auch.
Zunächst mal bis zur Hälfte, das ist also P hoch Omega in halbe minus
1.
Das P hoch Omega in halbe ist ja gerade minus 1.
Also P hoch Omega in halbe minus 1, das ist dann entsprechend das
Gerade -Polynom für Omega hoch in halbe minus 1 Quadrat ist M minus 2.
Und entsprechend das Ungerade-Polynom hier Omega hoch N minus 2
ebenfalls.
Und das mal Omega hoch in halbe minus 1.
Diese Werte habe ich aber gerade für Omega hoch 0 bis Omega hoch N
minus 2.
Das sind ja gerade die enthalbten Einheitswurzeln.
Weil das Quadrat einer Einheitswurzel, einer enten Einheitswurzel eine
enthalbte Einheitswurzel ist.
Da ich hier jeweils die Quadrate betrachtet habe, muss ich also hier
die in halbe Werte Omega hoch 0 bis Omega hoch N minus 2 betrachten.
Und das habe ich hier oben in 2 berechnet.
Und dann muss ich anschließend das gleiche noch machen für die
restlichen Einheitswurzeln.
Das sind jetzt aber Omega hoch in halbe bis Omega hoch N minus 1.
Und da wissen wir, das sind gerade die negativen Werte derjenigen, die
ich vorher schon gehabt habe.
Die werden jetzt nur quadriert.
Wenn die quadriert werden, sind das genau die gleichen nochmal.
Das heißt, dieses Gerade-Polynom muss nochmal hier hingeschrieben
werden für Omega hoch 0 bis Omega quadrat bis Omega hoch N minus 2.
Und das Ungerade genauso.
Aber ich muss hier mit minus 1 mal Omega modifizieren.
Und das heißt, ich habe hier jeweils ein Minus dran stehen und da
hinten genau das, was ich vorher auch schon berechnet hatte.
Und offensichtlich können wir uns hier ein bisschen Berechnungen
sparen.
Insgesamt kommen wir auf wie viele Operationen.
Ich habe hier jeweils eine, das hier sind in halbe, mal, muss ich was
machen, eine Addition und eine Multiplikation.
Und hier unten, da brauche ich eigentlich nur noch in halbe mal was zu
machen, jeweils eine Addition.
Die Produkte habe ich vorher alles schon berechnet.
Das heißt, ich habe nur in halbe Multiplikation zu machen und
insgesamt in Addition.
Und wenn ich das jetzt mir für N gleich 2 hoch K anschaue, habe ich
also den ersten Schritt, das ist dieses Perfect-And-Shuffle.
Das ist kein Berechnungsaufwand, das ist nur Adressieren der
entsprechenden Elemente meines Arrays, meiner Liste, in der die
Koeffizienten stehen.
Dann habe ich zweimal den Aufwand für schnelle Fouillet-Transformation
mit einem Polynom halben Grades.
Und dann muss ich in halbe minus eins Multiplikation machen.
Bei dem ersten hier auf der vorigen Folie, hier oben hatte ich ja
keine, also da brauche ich nur eine Addition, keine Multiplikation zu
machen.
Also minus eine Multiplikation.
Und dann habe ich also hier meinen Aufwand für den Schritt drei.
Und wenn ich mir jetzt das genaue anschaue, die Anzahl der
Multiplikation, die Anzahl der Addition, dann habe ich bei den
Multiplikationen stehen, ich brauche zweimal den Aufwand,
Multiplikation für Grad in halbe, plus in halbe minus eins und ich
brauche zweimal bei den Additionen, zweimal die Additionen für
Polynomen von Grad in halbe plus n.
Und für Polynomen zweiten, also für n gleich zwei, habe ich hier eins
und zwei stehen.
Das heißt, insgesamt bin ich bei einem Aufwand bei den
Multiplikationen etwas weniger als in halbe mal log n.
Auch das kann man sich leicht überlegen, wenn ich zweimal den Aufwand
für in halbe habe, plus noch einen linearen Aufwand dazu.
Dann ist das auf jeder, denn ich habe ja hier mein großes Problem, das
teile ich auf in Probleme halber Größe, das auch wieder in Probleme
halber Größe.
Und jeweils der Aufwand ist linear, das sehen wir hier, der Aufwand
ist jeweils linear in der Größe des Problems.
Da die Größe sich jeweils reduziert, ist der Aufwand in jeder Stufe
hier jeweils O von n.
Und insgesamt habe ich gerade log n Schichten, das heißt ich habe
Aufwand n log n.
Ganz einfach.
Ups.
Also habe ich insgesamt n log n als Aufwand und ich bin damit fertig,
ich habe gezeigt, die schnelle Fourier-Transformation geht in der Zeit
n log n.
Das ist ein relativ klarer Ansatz.
Ich muss das eine Polynom, das ich an diesen n Stellen auswerten
möchte, muss ich einfach geschickt aufteilen in zwei Teilpolynome und
dann kann ich die Eigenschaften der Enten-Einheitswurzeln ausnutzen,
dadurch, dass ich die im Prinzip berechne für die quadrierten Enten
-Einheitswurzeln, jeweils Polynome halben Grades und damit habe ich
dann insgesamt den Aufwand deutlich reduzieren können.
Und damit habe ich hier diesen Satz, dass die schnelle Fourier
-Transformation O von n log n arithmetische Operationen braucht.
Das ist also eine der klassischen, schnellen Algorithmen und das
Wesentliche ist eben hier wieder der Konker-Ansatz.
Und das Problem, das wir eigentlich bearbeiten wollten, war die
Multiplikation von Polynomen.
Und das geht durch diesen Transformations-Ansatz dann eben auch in
Zeit n log n, besser als quadratische Zeit.
Jetzt schauen wir uns noch was weiteres an und das ist die Struktur
dieses Algorithmus, die Kommunikationsstruktur.
Ausgangspunkt sind unsere n-Koeffizienten, a0 bis an-1.
Die muss ich jetzt verwenden, um FFT für jeweils Polynome halben
Grades zu berechnen.
Und zwar halben Grades, einmal für diese geraden Polynome und einmal
für die ungeraden Polynome.
Das heißt, hier habe ich dieses unshuffled zu machen.
Und das, was da rauskommt, die Werte, die da rauskommen, muss ich
entsprechend dieser Formel multiplizieren, also ein Ergebnis von Pg,
darauf muss ich addieren das entsprechende Ergebnis von Pu,
und dass dieses Pu mal entsprechend der jeweiligen Einheitswurzel
modifiziert.
Also ich muss dieses Pu mal der Einheitswurzel nehmen und darauf das
Pg addieren.
So rum war das.
Das heißt, ich habe eine Kombination dieser Werte.
Und das Interessante ist, dass diese Struktur eine ganz allgemeine
Struktur ist, das sogenannte Butterfly-Netzwerk, das
Schmetterlingsnetzwerk.
Wir haben also hier so eine Struktur, ich habe hier diese Werte
zusammengefasst zu zwei Komponenten und anschließend die so wieder
kombiniert.
Und das sehen Sie hier mehrfach, wir haben hier einmal so eine
Darstellung.
Und wenn wir das jetzt betrachten für rekursiv, da unten drunter,
haben wir die Darstellung hier nochmal und da auch.
Und hier im Prinzip nochmal.
Das heißt, das ist ein rekursives Netzwerk.
Für n gleich 8 sieht das so aus.
Hier habe ich praktisch die Eingänge hier vorne umgruppiert, sodass
wir das Perfect Shuffle schon gemacht haben.
Und Sie sehen hier diese sehr einfache Struktur.
Und das Interessante ist, dass dieses eine Struktur ist, die Folgendes
erlaubt.
Sie können eine beliebige Permutation der Eingänge vornehmen, indem
Sie einfach hier jeweils eine Pfad anschauen durch diesen Graphen,
durch dieses Butterfly-Netzwerk.
Also wenn Sie von hier nach dort wollen, wie funktioniert das?
Das ist in dem Fall, dann müssen Sie entsprechend so runter, darauf
und darüber.
Und so finden Sie für je zwei Positionen einen Pfad durch dieses
Netzwerk, das die beiden Positionen verbindet.
Wenn ich mir hier diesen angucke und meinetwegen den hier unten, wie
sind die verbunden?
Auch so, so und so.
Das heißt, Sie können eine beliebige Permutation sich hier nehmen, der
Eingänge auf die Ausgänge.
Das sind jetzt hier unsere Eingänge, das sind die Ausgänge.
Ich möchte eine beliebige Permutation machen oder eine beliebige
Kommunikationsstruktur realisieren.
Dann finde ich hier genau entsprechende Pfade.
Das kann ich natürlich alles entsprechend gleichzeitig machen.
Das Interessante ist nur, wenn Sie sich vorstellen, Sie wollen die 5,
nehmen wir mal welche anderen her.
Wir nehmen mal hier die 6, die soll verbunden werden mit der 7.
Hier, die beiden.
Dann geht das über diesen Pfad.
Und die 2 soll verbunden werden mit der 3.
Dann geht das über diesen Pfad.
Das heißt, wir haben hier in der Mitte eine Kante, die von beiden
Pfaden benutzt wird.
Jetzt ist das, ich sage das ist ein Permutationsnetzwerk, eine ganz
wichtige Verbindungsstruktur für Parallelrechner.
Wenn Sie sich vorstellen, Sie würden Informationen schicken hier rüber
in der Richtung.
Sie könnten ja in jedem Schritt von jedem Knoten aus eine Nachricht im
Prinzip hier rüberschicken.
Da geht eine Nachricht los, da geht eine Nachricht los.
Und die eine soll hier unten hinkommen, die andere sollte gerade dort
hinkommen.
Die können zwar beide gleichzeitig losgeschickt werden, kommen Sie
hier aber an und der kann die nur nacheinander bearbeiten.
Sie haben also nicht, wie man zunächst mal erwarten könnte, genau so
viele Stationen, wie Sie hier Spalten in dem Betaflight-Netzwerk
haben.
Sondern es kann sein, dass Sie solche Engpässe hinkriegen.
Zunächst mal denkt man, ich habe für jede Permutation Pfade der Länge
Log N.
Das sind genau Log N-Stufen hierbei.
Das ist ja gerade die Idee bei dem Betaflight-Netzwerk.
Da könnte ich ja jede Permutation mit Log N-Schritten ausführen, wenn
ich so von links nach rechts hier durchlaufe.
Das Problem ist aber, dass ich hier Kanten habe, die für mehrere
solche Verbindungen gebraucht werden.
Und das Dumme ist, wenn Sie sich ein allgemeines Betaflight-Netzwerk
der Größe N anschauen, dann kann es sein, dass Sie in der Mitte bis zu
Wurzel N Pfade haben, die sich eine Kante teilen müssen.
Wenn Sie sich jetzt anschauen, wie lange das dauert, um dann eine
solche Permutation auszuführen, dann müssen Sie ja hier diese Wurzel N
-Schritte alle nacheinander machen.
Das heißt, Sie haben nicht Log N als Zeit, sondern insgesamt kommt man
dann auf Wurzel N.
Das ist nicht in jeder Schicht Wurzel N, deswegen ist es nicht Wurzel
N mal Log N, sondern insgesamt addiert sich das auf eine Zeit von
Wurzel N, im schlechtesten Fall.
Das heißt, Sie haben, wenn man annimmt, ich kann in jedem Takt nur
eine Nachricht verschicken, für solche Permutationen, für so ein
schönes Permutationsnetzwerk, das Problem, dass ich nicht die Zeit Log
N erreichen kann, die man vermuten würde, wenn ich einfach nur von
einem Knoten zu einem anderen gehen möchte, dann geht es in Zeit Log
N.
Aber wenn ich gleichzeitig für jeden Knoten erlauben möchte, dass der
eine Nachricht schickt, zu einem beliebigen anderen, dann habe ich
hier solche Engpässe auf diesen Leitungen.
Und das Interessante ist, man kann sich anschauen, die Menge aller
Permutationen, und dann gibt es Permutationen, die genau diese
schlechten Fälle, Wurzel N, erzeugen.
Das ist eine Teilmenge.
Das Dumme ist, dass genau solche Permutationen auftauchen in typischen
Divide -and-Conquer-Ansätzen und ähnlichen Dingen.
Das heißt, dass Sie so bei typischen algorithmischen Strukturen, wo
Sie also Kommunikationsstrukturen entstehen lassen, auf Basis von
irgendwelchen solchen systematischen Divide-and-Conquer-Ansätzen,
landen Sie immer genau in der Menge derjenigen Permutationen, die
schwierig auszuführen sind.
Wenn Sie eine zufällige Permutation machen, dann kommen Sie in Zeitlog
N durch.
Dann haben Sie weniger Beschneidungen.
Und es gibt eine interessante Idee.
Ich mache einfach aus der Kommunikation, wenn ich also hier
sicherstellen möchte, ich möchte gerne von dort nach dort eine
beliebige Permutation doch gerne in Zeitlog N hinbekommen.
Das geht für diese schlechtesten Fälle hier nicht.
Der Erwartungswert für eine beliebige Permutation ist allerdings Log
N.
Also mache ich folgende Idee.
Ich schicke, wenn ich also jetzt hier meine, ich male mal hier diese
Punkte auf, die wollen zu irgendeinem anderen Punkt hin, dann schicke
ich die erstmal zu einem beliebigen Punkt, zufällig, und anschließend
dürfen die von dem zufälligen Punkt zu dem eigentlichen Zielpunkt.
Das heißt, ich führe nicht eine systematische Permutation aus, sondern
ich mache eine Folge von zwei Permutationen.
Der hier möchte eigentlich dorthin, muss aber erstmal zu irgendeinem
anderen Knoten laufen und darf erst von dort dann dorthin laufen.
Diese beiden Permutationen, die ich jetzt ausführe, sind aber
randomisiert.
Und dadurch, dass sie jetzt eine Zufallsstruktur haben, ist der
Erwartungswert für beide randomisierten Permutationen jeweils Log N.
Und ich bin um diesen schlechten Fall herumgekommen.
Genau das wird in einigen Parallelrechnern gemacht, die eine solche
Struktur verwenden als Verbindungsstruktur, die schicken die
Nachrichten erstmal an einen zufälligen Knoten und von dem geht es
dann an den eigentlichen Zielknoten.
Das ist so die Idee, wenn Sie in der Urlaubszeit Verkehrsstaus
vermeiden wollen, dann lassen Sie jeden Autofahrer zu Beginn erstmal
zufälligen Ziel wählen.
Da muss er erstmal hinfahren und von da aus darf er dann an sein
eigentliches Ziel fahren.
Dann hätten wir keine Staus mehr.
Das wären Zufallsverteilungen der Fahrzeuge und Sie hätten das
Stauproblem beseitigt.
Das ist so die Übertragung eines theoretischen Ergebnisses auf ein
praktisches Problem.
Funktioniert vielleicht nicht genauso, aber es würde sicherlich, da
Sie eine zufällige Verteilung hinbekommen, würde das eine Verbesserung
der Verkehrssituation bringen.
So, jetzt noch eine andere Idee zu diesem Kommunikationsnetzwerk.
Wir wissen, eine Randomisierung der Operationen bringt einen Gewinn.
Jetzt kann ich aber auch einfach sagen, naja, ich verändere einfach
mein Netzwerk.
Ich wähle einfach einen zufälligen nächsten Knoten.
Ich randomisiere mein Netzwerk und führe dann ganz normal meine
Kommunikation aus.
Ich mache das ein bisschen umfangreicher dadurch auch, kommt ein paar
mehr Leitungen rein, aber die Verbindungen sind etwas randomisiert.
Und dadurch, dass ich die Verbindungen in dem Netzwerk randomisiere,
habe ich den Effekt, den ich vorgeschrieben habe, ich randomisiere die
Permutation und führe sie auf einem solchen Weiterverleihungsnetzwerk
aus, habe ich verändert in, ich führe meine normale Permutation aus
auf einem randomisierten Netzwerk und ich bekomme dadurch als
erwartungswert immer Log N raus.
Und damit habe ich also dann ein neues Netzwerk gebaut.
Das sind interessante Sachen, an die man sich alle überlegen kann,
habe ich jetzt hier nur so verbal erwähnt, kann man sich alles
durchlesen in Veröffentlichungen über Verbindungsnetzwerke.
Wenn Sie rumspielen wollen mit diesen Verbindungsnetzwerken, dann
müssen Sie sich unser Applet anschauen.
Das ist also hier unser schönes Applet, ein weiteres, mit dem man in
Verbindungsstrukturen arbeiten kann.
Also hier, da haben wir ein Butterfly-Netzwerk, das ist genau dieses
für N gleich 8.
Acht solche Punkte.
Und jetzt kann man hier folgende Sachen überlegen für ein allgemeines
Verbindungsnetzwerk.
Wir wollen zum Beispiel gucken, beste Pfade.
Ich möchte von diesem Punkt, von dem Punkt, muss ich raufklicken, zu
dem Punkt und Sie sehen, das ist der beste Pfad.
Oder nochmal, ich möchte von dem, Sie können jetzt beliebige Knoten
nehmen, zu dem Punkt, dann haben Sie hier auch einen besten Pfad.
Sie können also beliebige Punkte anklicken und sehen, beste Pfade.
Das ist auch immer, Sie können sogar verschiedene beste Pfade hier
wählen, es gibt also in dem Fall zwei Möglichkeiten.
Und Sie können auch einen Broadcast machen, Sie können sich anschauen,
ich habe hier diesen Knoten, der möchte allen anderen etwas mitteilen.
Ein Broadcast in einem Verbindungsnetzwerk.
Dann schauen Sie sich an, in einem Schritt kann er seine direkten
Nachbarn informieren.
Die können in einem Schritt wieder jeweils ihre direkten Nachbarn
informieren.
In einem Schritt wieder die direkten Nachbarn.
Jetzt waren Sie da.
Und dann wieder die direkten Nachbarn, nochmal die direkten Nachbarn
und nochmal die direkten Nachbarn.
Es ist klar, wir haben hier dieses Problem mit dem Baum, dass wir
erstmal ganz hier oben hinlaufen mussten und dann wieder zurück.
Das kann man auch für andere, also Sie bekommen ja auch noch eine
Strukturinformation, wie das Ding aussieht, Knotenzahl, Schrittzahl,
Broadcast, Anzahl, beste Pfade usw.
Ist ja allgemein dargestellt.
Und Sie können das natürlich auch für andere Strukturen machen, zum
Beispiel für, das war das erste Bild, das Gitter.
Wenn Sie hier irgendeinen, gehen wir mal auf Broadcast, wenn Sie hier
einen Broadcast machen wollen, ist klar, das ist hier relativ einfach.
Da können Sie hier so durchlaufen und Sie haben alle Elemente
erreicht.
Wenn Sie beste Pfade machen wollen, Sie wollen von diesem Punkt zu dem
Punkt, dann haben Sie hier einen besten Pfad und offensichtlich gibt
es hier sehr viele verschiedene beste Pfade, weil jeder Pfad in diesem
Manhattan -Netzwerk gleich lang ist.
Wenn Sie also sich nach rechts und unten bewegen, wenn das Ihre
einzige Art ist, wie Sie durchlaufen, haben Sie hier ganz viele beste
Pfade.
So können Sie damit rumspielen, nur dass Sie sich ein bisschen
Informationen anschauen, darüber, was hier für Sachen sind.
Also hier haben Sie dann Knotenzahl, Länge mal Breite, Schrittzahl,
Broadcast ist hier auch dargestellt, Anzahl, beste Pfade steht hier
auch, maximale Länge eines besten Pfades, ist also Länge plus Breite
minus 1.
Das ist also praktisch die maximale Länge einer kürzesten Verbindung
zwischen zwei Knoten.
Und das sind wichtige Eigenschaften, weil Ihnen das zeigt, wie lange
dauert es, eine Nachricht von einem Knoten zu einem anderen zu
schicken.
Dazu müssen Sie sich anschauen, wie lange dauert das maximal auf einer
kürzesten Verbindung.
Deswegen ist das eine wichtige Eigenschaft, das ist der Durchmesser
eines Graphen.
Gut, gehen wir zurück zu unserer fünf Minuten Zeit, können wir noch
ganz kurz das hier abfließen.
Das ist schon abgeschlossen, das Kapitel.
Und jetzt kommen wir nämlich auf das nächste Kapitel, was ich Ihnen
auch gestern Abend noch schnell reingestellt habe in den VAB.
Das ist ein ganz einfaches Kapitel, wo ich genau das nochmal
darstellen möchte, was ich heute mehrfach erwähnt habe.
Wir haben häufig Rekurrenzgleichungen, mit denen wir Zeitabschätzungen
machen.
Und die haben immer eine ziemlich einfache Struktur.
Und da müssen wir nicht lange überlegen, was da rauskommt für eine
Funktion, die den Wert darstellt, sondern das können wir eigentlich an
der Struktur der Formel sofort sehen.
Wir haben das bei dem Straßenalgorithmus explizit ausgerechnet.
Gerade eben habe ich das gar nicht explizit ausgerechnet, ein bisschen
argumentiert, warum das jeweils...
Da war das Log N oder N-Log N.
Und man kann das ganz allgemein machen.
Ich möchte also ein Problem mit divide-and-conquer-Ansatz lösen.
Das ist mein Problem, das ich lösen möchte.
Das ist mein Problem, die Lösung möchte ich bestimmen.
Und mit divide-and-conquer mache ich das so, dass ich das aufteile in
eine Anzahl von kleineren Teilproblemen, die jeweils rekursiv löse,
das ist der Teil B.
Und wenn ich klein genug bin, löse ich es direkt, dann komme ich hier
auf die Lösungen.
Und die muss ich jetzt kombinieren, das ist der dritte Teil zur Lösung
L.
Wir haben das gesehen bei Straßen, da hatten wir sieben Teilprobleme,
der Größe N-Halbe.
Wir hatten bei Polynomen-Auswertung, waren das zwei Teilprobleme, der
Größe N-Halbe.
Aber es muss eben nicht immer sein, dass wir genau zwei Teilprobleme
größer N-Halbe kriegen.
Bei Straßen hatten wir sieben Teilprobleme, der Größe N-Halbe.
Das kann also irgendein allgemeiner Aufwand sein, das heißt, wir haben
einmal den Aufwand für die kleinen Probleme.
Wenn wir annehmen, das N lässt sich direkt durch C, ist also eine
Potenz von C, dann kommen wir am Ende auf ein Teilproblem, das die
Größe 1 hat, das lösen wir mit Aufwand A.
Und dann müssen wir uns anschauen, den Aufwand für das Aufteilen und
den Aufwand für das Kombinieren.
Das heißt, ganz unten für das kleine Problem haben wir einen Aufwand
A.
Und dann müssen wir K-Teilprobleme lösen, der Größe N durch C.
Das sind hier diese K-Teilprobleme, der Größe N durch C, die wir
jeweils lösen müssen.
Und dazu kommt der Aufwand für das Aufteilen und für das
Zusammensetzen.
Und das ist der Aufwand in der D von N.
Und das ist der gesamte Zeitaufwand.
Das heißt, wir haben bei divide-and-conquer-Algorithmen in der Regel
genau solche Formeln auszurechnen.
Und daraus kann man in einigen Fällen sehr schnell abschätzen, welcher
Wert das tatsächlich ist.
Das hatte ich schon gesagt, dass das die typischen Formeln sind.
Wenn wir uns das anschauen, also zunächst mal ganz allgemein, kann man
das ausrechnen und kommt dann auf eine solche Formel.
Wenn Sie sich zurückerinnern an den Straßenalgorithmus und wie wir
dort den Aufwand berechnet haben, da kamen genau solche Formeln raus.
A mal K hoch M, das ist also die Anzahl der Teilprobleme, jeweils
tritt der Aufwand A auf, das ist A mal K hoch M.
Ich habe ja K hoch M insgesamt dann Teilprobleme dort drin, wobei M
gerade die Potenz von C ist, die ich brauche, um auf N zu kommen.
Deswegen habe ich die A mal K hoch M als Aufwand.
Das sind die vielen Einzelprobleme, die ich lösen muss.
Und dann habe ich den ganzen Aufwand, um zusammenzubauen.
Das ist der ganze Aufwand.
Auf jeder Ebene muss ich zusammenbauen.
Und ich habe immer größere Teilprobleme, die ich dort betrachte, aber
auch immer weniger.
Also K hoch J mal DN durch C hoch J.
Und den ganzen Aufwand für dieses Zusammenbauen, diese Ds, muss ich
alle aufsummieren.
Das ist also diese allgemeine Formel für die Zeit, die man da
rauskriegt, nur aus der sieht man noch nicht so viel.
Jetzt kann man sich das ein bisschen spezieller anschauen.
Und ich will nur das hier, diese eine Folie nur noch zeigen.
Das ist das hier.
Wenn wir einen konstanten Aufwand haben.
Das war das, was wir hatten bei dem Verfahren für die parallele
Polynomauswertung.
Da stand jeweils T von N halbe plus zwei.
Konstanter Aufwand.
So, wenn das K gleich eins ist, das war bei der Polynomauswertung der
Fall, dann kommt Log N raus.
Wenn das K größer als eins ist, wenn wir zweimal T einen Fall, wir
hätten plus zwei, dann kommt N hoch Log zur Basis C von K raus.
Log zur Basis C von K.
C in dem Fall bei der Polynomauswertung war N halbe.
Zwei Probleme.
In dem Fall ist Log zur Basis C von K gerade eins.
Bei diesem Beispiel, das ich da im Kopf hatte, also wenn wir hier
haben T von N gleich zweimal T von N halbe plus zwei.
Wenn wir das nicht parallel machen würden, sondern beides
nacheinander, dann haben wir gerade N hoch eins, also linearen
Aufwand.
Sehr einfach.
Und wenn das D von N lineare Aufwand ist, wie wir das bei einigen
Problemen haben, dann kann ich je nachdem, welches Verhältnis K und C
stehen, also hier haben wir K gleich C.
Wenn das bei der Parallelenauswertung war, das war dann nicht zwei,
sondern eins.
Das wäre dieser Fall, K kleiner C.
Und wenn wir K gleich C haben, kommt N log N raus.
Wenn K größer C ist, kommt N hoch Log zur Basis C von K raus.
Und das kann man sich genau überlegen, kann man beweisen, kann man
ähnlich beweisen, wie wir das bei Straßen gemacht haben.
Das ist relativ einfach.
Das will ich nicht im Einzelnen ausführen.
Ich werde nächstes Mal Ihnen noch eine weitere Darstellung zeigen.
Das ist die nächste Folie, wo man hier ein Mastertheorem, wo man noch
für allgemeinere Fälle solche Rekursionsgleichungen entsprechend
auflösen kann.
Also das ist einfach sehr praktisch, wenn man weiß, ich habe ein
Problem oder Algorithmus analysiert und komme auf eine solche
Darstellung für die Zeitkomplexität.
Dann kann ich mit diesen Spezialfällen sofort sagen, welcher Wert dann
rauskommt und für das, was wir nächstes Mal sehen werden, halt dann
noch für allgemeinere Fälle.
Und der Aufwand hängt halt ab von dem Aufwand für die direkte Lösung
beim Abbruch des Verfahrens und dann eben von dem Aufwand für das
Aufteilen und das Zusammensetzen.
Und auch von dem Verhältnis der Anzahl der Teilprobleme zur Größe n
durch c der Teilprobleme.
Wenn also beim Straßenalgorithmus das k kleiner als c gewesen wäre,
wir hätten weniger als zwei Teilprobleme gehabt, dann hätten Sie ein
deutlich besseres Verhältnis.
k war dort wesentlich größer, 7 und 2.
Dann kamen Sie genau auf diesen Fall mit log zur Basis c von k.
Das war der log zur Basis 2 von 7.
Das sind genau die Abschätzungen, die man dann kriegt.
Das Master-Theorem, das guckt sich halt so ein paar verschiedene Fälle
an.
Die Problemstellung ist hier nochmal dargestellt.
Das ist also unsere Gleichung, die wir haben.
Die Basisgleichung habe ich hier weggelassen.
Für konstante Größe haben wir natürlich irgendeinen Anfangsaufwand a,
der hier auftaucht.
Wir wissen, dass wir also da eine Formel hinschreiben können.
Derart a mal k hoch m, wobei das k die Anzahl der Teilprobleme ist.
Das m, wir nehmen an, dass n gleich c hoch m ist.
Also dieses m ist gerade gleich log zur Basis c von n.
Dann haben wir also hier das a mal k hoch m.
Der Aufwand für dieses in jeder Stufe k-fach aufgeteilt.
Und dann jedes Mal ganz unten an den Blättern der Aufwand a und das k
hoch m mal.
Plus der Aufwand für das Aufteilen und Zusammenführen, das ist in der
Summe hier dargestellt.
Und die einfacheren Ausdrücke für diese Summe, für diese Funktion, die
sind dann hier angegeben, dass man das abschätzen kann von der
Größenordnung her.
Und die Voraussetzungen sind eben, dass k größer gleich 1 ist.
Das ist natürlich mindestens ein Teilproblem.
Wir verringern, um tatsächlich ein...
Also 1 macht ja gar keinen Sinn, c muss größer als 1 sein.
Dann bei dem Aufwand, da stand hier immer z nach z.
Ich kann aber als Wert natürlich auch irgendeine beliebige positive
reelle Zahl haben.
Das muss hier keine ganze Zahl sein, der Wert des Aufwands für das
Aufteilen und Zusammensetzen.
Und da steht in Ihren Folien noch ein z.
Ich habe das durch r plus ersetzt, weil das einfach so auch sein muss.
Und die Formel, die Rekursionsformel sieht halt so aus.
Wobei wir hier das n durch c, für ein beliebiges n ist das natürlich
keine ganze Zahl.
Wenn das eine ganze Zahl sein soll, dann nehmen wir dazu halt entweder
Ceiling oder Floor, also die nächstgrößere ganze oder die
nächstkleinere ganze Zahl, n durch c.
Und dann können wir also folgende Aussagen machen.
Jetzt hängt also der Wert oder der Ausdruck für das asymptotische
Wachstum der Funktion t, der Zeitfunktion hier oder die durch diese
Rekurrenzgleichung beschriebene Funktion t, hängt halt davon ab,
welches Wachstum diese Funktion d hat.
Der Aufwand fürs Zerteilen und wieder Zusammenfügen.
Und wenn dieser Aufwand, jetzt sehen Sie, jedes Mal abhängig von n
hoch log zur Basis c von k.
Im Prinzip ist das hier gleich dieses k hoch m.
Das heißt, das guckt man sich im Wesentlichen an.
Wenn also das d von n, wir wissen das k hoch m, das m ist log zur
Basis c von n.
Und dieses n hoch log zur Basis c von k ist halt gleich k hoch log zur
Basis c von n.
Das wissen Sie, haben wir beim Straßenverfahren schon mal
hingeschrieben.
Einfache Umformung und das ist also gerade hier gleich k hoch m unter
dieser Annahme.
Und das heißt, wir schauen uns immer diesen Term an.
Wie sieht diese Funktion d aus im Verhältnis zu dem Term?
Und wenn das d, hier steht jetzt ein minus epsilon, n hoch log zur
Basis c von k minus epsilon.
Irgendein reeller Wert, der dort abgezogen wird.
Das heißt, das d von n wächst langsamer oder wächst nicht so schnell
wie n hoch log zur Basis c von k.
Da steht dann minus epsilon in der Potenz.
Dann ist der Aufwand bestimmt durch genau diesen Term, n hoch log zur
Basis c von k.
Weil das Wachstum von d von n, dieser Summe hier, spielt dann im
Vergleich zu dem k hoch m hier vorne oder zu diesem n hoch log zur
Basis c von k keine Rolle.
Das Wachstum wird bestimmt durch den ersten Term.
Wenn das d von n in der gleichen Größenordnung wächst, wie dieses n
hoch log zur Basis c von k, dann habe ich im Prinzip log n mal diesen
Aufwand.
Das heißt, dann ist das ganze n hoch log zur Basis c von k mal log n,
was in der gleichen Größenordnung ist.
In jeder Stufe habe ich im Prinzip diesen Aufwand, der durch dieses d
von n hier bestimmt wird.
Und wenn das d von n stärker wächst als dieser Term, n hoch log zur
Basis c von k, also log das hier plus epsilon steht, und es wächst,
ist aber dieses, wenn ich mir das d von n anschaue, das d von n durch
c, ich teile ja in k Teilprobleme auf, k mal das d von n durch c ist
kleiner gleich alpha mal d von n für ein alpha kleiner 1.
Das heißt, dieser Aufwand wächst nicht zu schnell.
Wenn das gilt für ein alpha kleiner 1 und für alle genügend großen n,
also ab irgendeiner gewissen Größe n, dann ist diese Funktion n von
der gleichen Größenordnung wie das d von n.
Dann dominiert also hier dieser Term hier alles andere.
So, und das sind diese drei Fälle, die etwas allgemeiner sind als das,
was wir vorgesehen haben.
Das waren ja nur diese Fälle, dass d von n konstant ist oder dass das
linear ist.
Hier ist es ein bisschen allgemeiner.
Und jetzt schauen wir uns das mal an mit ein paar Beispielen.
Hier ist eine Bemerknummer dargestellt, die eben davon abhängt, ob die
Funktion d oder dieses n hoch log zur Basis c von k stärker wächst.
Und wenn wir uns jetzt ein Beispiel angucken, 9 mal t n Drittel plus
n.
Also in dem Fall ist das hier k, das hier ist c und das hier ist d von
n.
Also n hoch log zur Basis c von k, 9.
Das hier ist gleich n Quadrat.
d von n ist linear.
Also d von n ist aus, sicherlich aus o von n Quadrat, sogar aus n
Quadrat minus 1, o von n Quadrat minus 1.
Ich habe hier ein Epsilon gefunden, sodass das d von n aus, weil das
hier ist linear, also aus o von n hoch 2 minus 1, hätte auch 2 minus
irgendwas hinschreiben können, stimmt das immer noch, auf jeden Fall
kann ich hier einen Potenz kleiner als 2 hinschreiben, größer als 1,
größer gleich 1.
Und das heißt, hier kommt raus n hoch log zur Basis c von k, also n
Quadrat.
Daraus folgt t von n aus o von n Quadrat.
Das ist das, was hier steht.
So, einfache Anwendung, das ist der Fall A unseres Theorems.
Zweite, t von n ist 1 mal t von 2n Dribbel plus 1.
Was haben wir denn hier stehen?
Schauen wir uns das mal genauer an.
In dem Fall ist k gleich 1.
c ist gleich 3 Halbe.
So, n durch c.
Das n hoch log zur Basis c von k, Das k ist 1.
Naja, das heißt, das ist gleich 0.
Logarithmus zu irgendeiner Basis von 1 ist 0.
Und das heißt, das d hier, das d von n ist eine Konstante.
Also haben wir in diesem Fall, d von n ist aus, sicherlich aus o von,
nun n hoch 0 ist 1.
Sogar aus Theta von 1.
Das d von n ist eine Konstante 1.
Also ist das aus Theta von 1, das ist der Fall Nummer B.
Und dann kommt hier raus, n hoch log zur Basis c von k, das ist 0, mal
log n.
Dann n hoch 0 ist 1, kommt hier raus, das t von n in dem Fall ist aus
o von log n.
Wenn ich mich nicht verrechnet habe, müsste das stimmen.
Und das war also der Fall B.
Und dann haben wir noch den dritten Fall, das dritte Beispiel.
Das dürfen Sie gerne selber sich ausrechnen.
Also da kann man ja auch einen dieser Fälle anwenden.
2 mal t von n halber, da ist k gleich c.
Also log zur Basis c von k ist in dem Fall gleich 1.
Und dann haben Sie hier noch n log n stehen, da muss man ein bisschen
hin und her überlegen.
Aber das kriegt man auch gleich raus.
Also dass Sie nur sehen, wie kann man dieses Theorem anwenden.
Man bekommt dann einfach, wenn man das mal ein paar Mal gemacht hat,
sieht man das in der Formel sofort an, was da rauskommt.
Man braucht nicht lange Beweise zu machen, welche Funktion das
tatsächlich ist.
Und für unsere Zwecke sind das meistens relativ einfache
Abschätzungen.
Achso, hier nochmal, wenn Sie da genauer nachlesen wollen, es gibt
viele Bücher drüber.
Buch von Coleman Leiser von Rivest, die haben dort einiges drinstehen
über Rekurrenzgleichungen.
Schauen Sie sich eines an, für viele verschiedene Beispiele.
In den Übungen dürfen Sie auch noch sich mit solchen Formeln
rumschlagen und sehen, was da für Funktionen rauskommen.
Einfach ein bisschen damit Übungen zu bekommen, wie man das abschätzen
kann.
Das ist einfach wichtig, dass man auf einfache Art und Weise
abschätzen kann, die Größenordnung des Wachstums von Funktionen.
Wenn man das einfach weiß, nach welchem Muster das funktioniert, man
könnte sagen, das ist ein Rezept, ein Rezept-Theorem, dann hat man das
halt einfach leichter zu sagen, wie eine Funktion wächst.
Gut, gibt es Fragen dazu?
Sie sind alle konsterniert, weil ich da mit den Formeln so rumgespielt
habe.
Ich mache trotzdem weiter.
Sie haben keine Fragen, dann haben Sie Pech gehabt, wenn Sie keine
Fragen haben.
Dann mache ich weiter mit dem nächsten Kapitel.
Das nächste Kapitel ist jetzt ein Thema, das bei vielen Vorlesungen
über effiziente Algorithmen ganz zu Anfang kommt, nämlich ein
einfaches Problem suchen und sortieren.
Sie kennen das aus Grundlagen der Informatik 1.
Oder der Informationswirt kennt das aus Informatik 2 vermutlich.
Und hier wollen wir uns das jetzt mal genauer angucken.
Bisschen anders, als Sie das bisher gesehen haben.
Nicht nur die üblichen sequenziellen Verfahren, sondern wie immer auch
parallele Verfahren.
Also suchen und sortieren.
Und ehe wir darüber reden können, müssen wir wissen, was das
eigentlich ist.
Also, worüber reden wir?
Wir reden über Listen von Elementen einer geordneten Menge.
Wir müssen die in der Größe vergleichen können.
Geordnet heißt, es sind je zwei Elemente vergleichbar.
Also keine partiell geordnete Menge, sondern eine geordnete Menge.
Partiell geordnete Mengen sind auch interessant.
Das Sortieren in partiell geordneten Mengen.
Insbesondere wenn Sie zum Beispiel solche Arten von Problemen haben.
Das sind Probleme, die Sie bekommen, wenn Sie zum Beispiel ein Problem
optimieren wollen bezüglich zweier Kriterien.
Multikriterielle Optimierung, da haben Sie zwei Kriterien.
Und da sind Sie interessiert an zum Beispiel der Front, die hier unten
so liegt, die sogenannte Pareto-optimale Front bezüglich zweier
solcher Kriterien.
Und was Sie da machen, ist, dass Sie einfach sortieren bezüglich einer
Dominanzrelation.
Das ist Sortieren in partiell geordneten Mengen.
Topologisches Sortieren in partiell geordneten Mengen.
Auch klassische Art des Sortierens.
Wir machen das aber einfacher.
Wir gucken uns den einfachen Fall an, dass die so schön angeordnet
sind.
Wir können eine klare lineare Ordnung angeben für unsere Elemente.
Also Spezialfall des Sortierens.
Wir haben eine geordnete Menge.
Macht das Leben viel einfacher.
Also Sortieren in partiell geordneten Mengen ist etwas aufwendiger,
gibt es aber auch klassische Verfahren für.
Also wir haben eine Ordnung.
Hier zwei Elemente sind vergleichbar.
Das U hier drin, die geordnete Menge, steht halt für Universum.
Irgendwas ist da drin.
Wir können den irgendwie vergleichen.
Wir haben irgendein Attribut eines Objektes, das wir nehmen können, um
sich zu vergleichen.
Dieses Attribut kann sein irgendein Suchschlüssel.
Bei irgendwelchen Kundendaten die Kundennummer.
Oder irgendwas.
Irgendein Name, irgendeine Zahl.
Sie haben also irgendwelche größeren Datensätze, Records oder Objekte.
Und es gibt ein Attribut, das Sie nehmen, um zu vergleichen.
Und da können wir uns auch darauf beschränken.
Wenn wir sagen, ich kann Elemente vergleichen, dann kann ich auch
gleich sagen, ich nehme einfach ganze Zahlen dafür.
Das ist die Vereinfachung.
In der Realität haben Sie wahrscheinlich irgendwelche größeren
Objekte, aber das ist natürlich einfach, das zu machen.
Sie werden das gleich sehen, dass wir das genauso dann machen werden.
Die Problemgröße in dem Fall ist die Länge der Liste.
Also wie viele Elemente müssen sortiert werden.
Und die Datenstruktur.
Was nehmen wir da?
Die Datenstruktur, die werden üblicherweise irgendwie als eine Folge
von Zahlen gegeben sein.
Irgendsowas, irgendeine Folge von Zahlen.
Das könnte ein Array sein oder ein Vektor.
Oder das heißt wahlfreier Zugriff.
Das macht das Leben leicht.
Könnte sein, dass wir eine Datenstruktur mit sequenziellem Zugriff
haben.
Wenn die Daten irgendwo in einer Datei sind, dann haben wir
sequenziellen Zugriff.
Das könnte eine linear verkettete Liste sein.
Das heißt, wir können immer nur von einem Element zum nächsten rüber
laufen.
Und müssen also, wenn wir ein Element auf ein Element zugreifen
wollen, wenn wir suchen wollen nach einem Element, müssen wir von
vorne bis hinten durchgucken.
Wenn wir wahlfreien Zugriff haben, dann können wir so schön mit
binärer Suche in die Mitte gehen und dann, wenn die Elemente sortiert
sind, können wir also bei einer sortierten Folge früher mit binärer
Suche arbeiten.
Wenn es noch nicht sortiert ist, können wir nicht mit binärer Suche
arbeiten.
Wenn wir einen sequenziellen Zugriff haben, müssen wir immer
sequenziell durchlaufen.
Doppelt verkettet würde bedeuten, wir hätten dann auch zurück hier die
Möglichkeit zu laufen.
Oder wir haben einen Baum.
Das ist natürlich auch nicht schlecht.
Was ist der Vorteil von einem Baum?
Wenn wir einen Baum nehmen, um Elemente zu speichern, dann ist halt
das Suchen so, dass wir uns anschauen müssen, wie ist der längste Pfad
durch so einen Baum, wenn wir suchen.
Und wenn wir also den Baum schön angeordnet haben, ist die Länge des
längsten Pfades logarithmisch in der Anzahl der Elemente im Baum oder
in der Anzahl der Blätter.
Und dann haben wir eine logarithmische Zeit für diese Operation.
Sie kennen das alles, Baumstrukturen sind schöne Strukturen.
Und wir werden solche auch noch genauer kennenlernen und sehen, was da
eigentlich so die Besten sind, wenn man suchen möchte.
Welche Operation haben wir?
Wir wollen zugreifen auf ein Element.
Also wir haben hier irgendeine Datenmenge und wir wollen irgendein
Element X finden.
Das wäre ein Zugriff auf irgendeine Komponente, wenn wir eine
Datenstruktur haben, wo wir hier sagen können, das ist die Komponente
mit dem Index I.
Dann wollen wir auf die IT-Elemente zugreifen, das wäre Select in der
Liste L, das Element I, die IT-Komponente.
Es könnte sein, dass wir einfach nur vergleichen wollen.
Wie kann man vergleichen?
Also Größenvergleich, welcher ist größer als der andere.
Und dann müssen wir gucken, wie groß ist der Aufwand dafür.
Wenn wir Glück haben, haben wir konstanten Aufwand, um zuzugreifen
oder zu vergleichen.
Wenn wir also wahlfreien Zugriff haben.
Wenn wir einen Baum haben, ist logarithmisch.
Wenn es eine Kette ist, ist es linear.
Das heißt, die Datenstruktur hat hier ganz starke Auswirkungen.
Und jetzt haben wir die etwas größeren Probleme über Zugriff und
Vergleich hinaus.
Das ist eigentlich die Basis-Operation.
Jetzt wollen wir uns größere Probleme anschauen.
Wir haben eine Liste der Länge N.
S hat mit Liste mnemonisch nichts zu tun.
Eigentlich müsste man das mnemonisch bezeichnen.
S steht hier für Liste zum Suchen oder Sortieren.
Deswegen S.
Also schon ein bisschen was mit dem Problem zu tun.
Jetzt suchen wir das k-größte Element dieser Liste.
Größte, zweitgrößte, drittgrößte, viertgrößte und so weiter.
Wir wollen also K von S berechnen.
Das k-größte Element dieser Liste.
Sie wissen, das größte zu berechnen ist einfach, einmal durchgucken,
linearer Aufwand.
Zweitgrößte, größte rausschmeißen.
Das zweitgrößte, immer noch linearer Aufwand.
Das drittgrößte, immer noch linearer Aufwand.
Sobald wir aber jetzt das erste Quartil haben wollen, dann müssen wir
das entvierteln.
Dann hätten wir schon quadratischen Aufwand.
Macht das Sinn, wenn wir uns genauer angucken?
Oder das mit den Medien zu bestimmen?
Wenn wir naiv auf n² kommen, das ist sicherlich nicht gut.
Also, das ist Suchen, das Suchproblem.
Schauen wir uns das später genauer an.
Sortierproblem, wenn wir uns das gleich genauer anschauen.
Sortieren kann man auf verschiedene Art und Weisen.
Wir müssen uns überlegen, wie wir das angeordnet haben wollen.
Und ich kann also sagen, ich möchte das gerne in Aufsteigen oder in
nicht fallender Ordnung haben.
Das wäre also das n von S, das n-größte oder kleinste Element.
Und das letzte ist das 1 von S, also das größte Element.
Oder andersherum, dann würde ich mit dem größten anfangen und
absteigen zum kleinsten.
Also entweder aufsteigend oder absteigend.
Und das andere wäre, ich möchte zwei sortierte Listen verschmelzen.
Ich habe zwei sortierte Listen und möchte die verschmelzen zu einer
sortierten Liste.
Wie macht man das?
Sie kennen das, wenn Sie zwei Fahrspuren haben, die auf eine Fahrspur
gehen, gibt es ein Reißverschlussprinzip.
Immer schön abwechselnd.
Und wenn Sie, ich male das anders auf.
Wenn Sie so zwei sortierte Listen haben und Sie machen
Reißverschlussprinzip nach Priorität.
Also alle Mercedes zuerst, danach kommen die BMW, danach kommen die VW
und so weiter.
Ganz einfach, Sie gehen in die erste Liste, die ersten dürfen alle
durch.
Dann ist die Liste dran, da dürfen auch einige durch.
Dann geht es da wieder weiter, da dürfen einige durch.
Das heißt, wir haben so ein Reißverschlussverfahren.
Nach Größe sortiert, es dürfen immer bis zu einer, solange die in der
linken Liste kleiner sind als das erste in der rechten Liste, dürfen
die aus der linken los, dann die rechten, solange hier das erste
größere kommt als das aktuelle Element in der linken Liste.
Das ist so ein naives Verschmelzen von zwei Listen zu einer sortierten
Liste.
Und da kommt also insgesamt eine sortierte Liste raus.
Und das geht selbstverständlich in Aufwand linear an der Länge der
beiden Listen.
Das ist auch relativ einfach.
Reißverschlussverfahren mit Priorität ist also klassisches Merge
-Verfahren.
Interessant wird es, wenn man das parallelisieren will.
Dann kriegt man also interessante Verfahren, das werden wir später
genauer anschauen.
Jetzt ein anderes Problem, ich möchte von einer Menge feststellen, ob
dort ein bestimmtes Element drin ist.
Ich suche einfach, möchte feststellen, ist ein bestimmtes Element A in
dieser Suchmenge S drin.
Ergebnis soll einfach nur angeben Ja oder Nein, True oder False.
Etwas mehr wäre, ich möchte nicht nur wissen, S ist drin, ich möchte
auch wissen, ich möchte es gerne rausholen.
Warum möchte ich ein Element rausholen?
Naja, es ist so, dass ich ja sagte, wir haben normalerweise größere
Objekte, die haben irgendeinen Suchschlüssel und ich möchte nicht nur
feststellen, ob ein Element mit diesem Suchschlüssel drin ist, sondern
ich möchte das Element mit diesem Suchschlüssel auch rausholen, den
Datensatz.
Aus einem Lexikon möchte ich den Eintrag rausholen, der zu einem
bestimmten Wort gehört.
Deswegen, das ist ein Search, heißt also, ich hole tatsächlich das
Objekt, das mit A versehen ist als Suchschlüssel, das hole ich da
jetzt raus.
Dann könnte es sein, dass ich etwas einfügen möchte in eine Liste.
Also ich habe eine Suchmenge oder Liste oder was immer und ich möchte
dort ein Element A einfügen.
Das kann relativ einfach sein, es kann sein, dass ich einfach eine
Liste habe, ich füge dort ein Element ein, brauche nur das A da hinten
dran zu schreiben.
Wenn ich aber eine aufsteigend sortierte Liste habe, die hier
irgendwie schön aufsteigend sortiert ist und ich möchte das Element A
jetzt irgendwo hier einfügen, dann muss ich natürlich alles, was da
stand, um eins nach rechts schieben und dann kann ich das A hier
reinschreiben, dann ist alles um eins nach rechts geschoben.
Das heißt aber, ich muss alle diese Elemente nach rechts schieben.
Aufwand, linearer Aufwand in der Anzahl der Elemente, die dort sind.
Wenn ich da ein Array habe oder sowas.
Also einfügen kann aufwendig sein, je nachdem, welche Eigenschaften
meine Menge in der Datenstruktur hat.
Das andere ist, ich möchte etwas löschen.
Das ist der gleiche Aufwand.
Ich könnte natürlich sagen, okay, wenn das Element hier schon drin
ist, ich möchte es löschen, streiche ich einfach hier raus, ich kann
den ganzen Rest einfach lassen.
Ich markiere einfach das Feld damit, dass es nicht mehr gültig ist.
Einfache Art zu löschen.
Nur irgendwann muss ich dann meine Liste wieder konsolidieren, die
ganzen gelöschten Elemente tatsächlich rauswerfen.
Aber so kann man das auch machen.
Auf jeden Fall ist das auch eine Operation, die ist interessant.
Wie kann ich also etwas löschen?
Ich muss erst mal finden, ob es drin ist.
Wenn es drin ist, das Element löschen.
Oder ich möchte das kleinste oder größte Element aus der Liste
entfernen, rausholen.
Prioritätswarteschlange.
Ich möchte immer das größte Element haben.
Heap kennen Sie, Heap-Struktur, haben Sie immer das größte Element an
der Wurzel und Sie wollen immer dieses Element rausholen, das größte
Element.
Müssen Sie dafür sorgen, dass anschließend das größte Element wieder
einfach zugreifbar ist.
Also das ist dann schon die Datenstruktur für Xmin oder Xmax.
Immer das kleinste rausholen oder das größte Element.
Oder ich sage, ich weiß ja nicht, ob das Element wirklich drin ist.
Ich suche in einem Lexikon nach dem nächsten Eintrag, nach dem
nächstliegenden Eintrag.
Also, das Element B will ich haben, das Objekt, das durch B bezeichnet
ist.
Und B ist der Schlüssel, der am nächsten dran liegt, nach dem ich
eigentlich suche.
Ich suche nach dem A und ich finde halt nur ein B.
Aber ich bin ja einverstanden damit, dass ich das B habe, das ist halt
am nächsten dran an dem A.
Muss aber eine Distanzfunktion auf den Schlüsseln haben.
Also auch das sind so typische Operationen, die man hat, wenn es darum
geht, etwas zu suchen oder auch zu sortieren.
Und dann ist das häufig miteinander vermengt, weil die Datenstrukturen
für das Suchen häufig eine sortierte Struktur haben.
Und das Interessante ist eben, dass diese Aussage, circa ein Drittel
der Rechenzeit, nehmen Sie die bitte nicht ganz wörtlich, das ist
keine genaue Messung des aktuellen Zustands.
Das ist eine Aussage, die galt schon vor 30 Jahren.
Aber es wird heute immer noch gelten.
Es ist einfach der Zugriff auf Datenmengen deutlich einfacher, wenn
Sie sortieren können.
Wenn Sie etwas sortiert haben.
Und auch das Suchen ist ein großer Aufwand.
Es kann sogar sein, dass heute der Aufwand für das Suchen noch
deutlich höheren Anteil ausmacht.
Schauen Sie sich an den ganzen Aufwand für Suchmaschinen.
Das ist ein riesiger Anteil der aktuellen Operationen, wenn Sie sich
anschauen, was wird eigentlich alles getan im Internet, in der
Informationsverarbeitung.
Suchen ist ein ganz wesentlicher Anteil und deswegen ist es wichtig zu
wissen, wie man das effizient machen kann.
Heutzutage reden wir eben insbesondere von Suchen in sehr großen
Datenmengen.
Terabyte von Daten oder petabyte.
Und das ist eine wirkliche Herausforderung, sinnvoll auf großen
Datenmengen Zugriffe zu gestalten.
Big Data spreche ich hier nicht explizit an in der Vorlesung, ist aber
ein ganz großes Thema.
Sortieren ist auch ein ganz großes Thema.
Peter Sanders hier von der Fakultät für Informatik hat also den
Weltrekord im Sortieren riesig großer Datenmengen.
Ja, der kann das ganz schnell.
Durch eine geschickte Art der Aufteilung der Mengen und des Hin- und
Herschiebens zwischen Daten, zwischen Hintergrundspeicher und
Hauptspeicher.
Wenn Sie in dem Hauptspeicher sortieren können, das geht schnell.
Das Problem ist immer, wenn Sie dann noch Operationen haben, die viel
Zeit brauchen zwischendrin, wenn Sie also Sachen nach draußen schieben
müssen in den Hintergrundspeicher, das dauert ja um mehrere
Größenordnungen länger.
Und das geeignet hinzukriegen, dass Sie viel Aufwand, möglichst viel
im Hauptspeicher machen können, das ist ganz wesentlich.
Und Sie wissen, es gibt heutzutage auch ein Thema, sogenannte In
-Memory -Datenbanken.
Oder Hauptspeicherdatenbanken.
Das heißt, wenn Sie die ganze Datenbank, die ganze Datenrepository im
Hauptspeicher halten können, haben Sie es wesentlich besser, können
Sie schnell zugreifen.
Insbesondere Suchmaschinen können dann schnell antworten.
Aber Suchmaschinen sind viel zu groß, sodass die gar nicht alle
reinkriegen.
Da müssen Sie geeignet das aufteilen.
Sehr interessante Thematik.
Wir tun so, als könnten wir das alles immer ganz einfach machen, alles
im Hauptspeicher.
Die Thematik schauen wir uns hier gar nicht an, sondern wir schauen
uns das Sortieren erstmal als Grundlagenoperation an, aber dann eben
auch parallel und so weiter.
Es gibt also Operationen Insert, Search, Delete.
Das sind sogenannte Dictionary- oder Lexikon-Operationen.
Wie gesagt, klassische Operationen für Suchverfahren oder für
Suchprobleme.
Prioritätswarteschlagen sind X-Mean, Insert und Delete.
Und das Komplexitätsmaß hierbei ist im Wesentlichen die Anzahl der
Vergleiche beziehungsweise die Pfadlängen im Entscheidungsbaum.
Sie erinnern sich, dass wir die Entscheidungsbäume hatten und wir
hatten einfach nur diese linearen Operationen bei algebraischen
Problemen.
Da waren es einfach lineare Listen von Zuweisungen.
Und hier sind es halt die Entscheidungsbäume.
Die Anzahl der Vergleichsoperationen ist das wesentliche Maß.
Und wir müssen natürlich auch gucken, wie der Aufwand für die Zugriffe
ist.
Wenn Sie eine lineare Liste haben und Sie schauen sich nur die Anzahl
der Vergleiche an, dann haben Sie den Zugriffsaufwand nicht mit drin.
Der Zugriffsaufwand kann linear sein, selbst wenn die Anzahl der
Vergleiche nur logarithmisch ist.
Und dann natürlich bei parallelen verteilten Algorithmen, bei
parallelen Algorithmen die Anzahl der Schritte, die ich brauche.
Da habe ich also parallele Operationen drin, bei verteilten
Algorithmen die Anzahl der Nachrichten.
Da muss man sehen, was ist meine Rechnerstruktur.
Und dann kriegt man da interessante Ergebnisse raus.
Und wir fangen jetzt einfach an mit den Sortierverfahren.
Und ich fange wirklich mit einfachen Verfahren an.
Also, wenn ich rede von Sortierverfahren, es kommt das Gleiche wie
das, was wir gemacht haben bei den Polynomen oder auch bei
Matrixmultiplikationen.
Wir nehmen zunächst mal an, wir wissen gar nichts über die zu
sortierenden Mengen.
Wenn ich mehr weiß, kann ich auch mehr tun.
Wenn ich weiß, ich muss zwei bereits vorsortierte Listen verschmelzen,
ist das deutlich einfacher, als wenn ich eine lange Folge sortieren
muss.
Also ich nehme an, ich habe ein allgemeines Sortierverfahren, ist mir
nichts bekannt über die Elemente.
Also ich weiß auch nicht, ob das ganze Zahlen sind oder Farben oder
sonst irgendetwas.
Ich weiß nur, ich kann sie vergleichen.
Es gibt eine Funktion, die mir für zwei Elemente sagt, welches das
größere ist.
Im Prinzip habe ich zwei Funktionen.
Ich habe eine Funktion min von a, b und max von a, b.
Die beiden Operationen brauche ich.
Ich muss das Minimum und das Maximum von zwei Elementen feststellen
können.
Dann kann ich sagen, dann weiß ich also, welches das größere, welches
das kleinere.
Also eins von beiden reicht mir schon.
Dann brauche ich einen wahlfreien Zugriff.
Ich gehe also davon aus, wir haben die einfachste Datenstruktur.
Wir nehmen an, dass alle Elemente verschieden sind.
OBDA, ohne beschränkte Allgemeinheit, nehmen wir sogar an, dass das
die Zahlen 1 bis N sind, wenn wir eine Liste der Länge N haben.
Das können irgendwelche anderen Sachen sein.
Aber ich nehme einfach an, das ist 1 bis N, ich nehme an, die sind
alle verschieden.
Was mache ich denn, wenn ich eine Liste habe, wo drin steht 1, 1, 1,
1?
Da sind viermal die gleichen Elemente drin.
Aber das steht an der Position 1, an der Position 2, an der Position
3, an der Position 4.
Ich kann also über die Position in der Liste die Elemente einfach
unterschiedlich machen.
Dann habe ich hier vier verschiedene Elemente.
1, 1 ist natürlich kleiner als 1, 2.
Und kleiner als 1, 3 und kleiner als 1, 4.
So kann ich eine Reihenfolge festlegen.
Ich brauche immer ein Kriterium, sodass ich Reihenfolgen festlegen
kann und ich nehme an, ich kann das immer.
Deswegen sage ich einfach 1 bis N.
Wenn das mal nicht die Annahme ist, werden wir darauf explizit
hinweisen.
Und jetzt schauen wir uns einfach typische, einfache Beispiele an.
Sortieren durch Auswahl, das ist wirklich sehr, sehr einfach.
Sortieren durch Auswahl heißt, ich möchte aus einer Liste einfach...
oder ich möchte die sortieren, indem ich einfach immer das Minimum
raushole.
Sie sehen, ich habe das hier voranimiert, das hätte ich gar nicht so
schnell machen wollen, ist egal.
Ich habe also eine Schleife für K gleich 1 bis N minus 1, möchte ich
jeweils das Minimum bestimmen der jeweiligen Menge SK bis SN.
Das Minimum, ich möchte ja aufsteigend sortieren, ich hole mir erst
das Minimum raus, dann von der Folge S2 bis SN, das Minimum treibt das
an die erste Position, also vertausche Smin und SK und so weiter.
Also, für das erste heißt das, das ist meine Folge, ich suche mir das
Minimum, das ist die 1, die schreibe ich an die erste Position, die
ist also durch Animation, irgendwie ist das in der falschen Position,
aber ist egal.
Das ist hier unten alles nach rechts gerutscht.
Die 1 kommt dorthin.
Dann gehe ich auf die Restfolge, da finde ich die 2, die kommt dahin.
Ich gehe auf die Restfolge, da finde ich die 3, die ist schon in der
richtigen Position, die 4 ist da hinten, die rutscht hier nach vorne.
Dann habe ich die 5, die rutscht nach vorne und ich bin fertig.
Sehr einfaches Verfahren.
Der Aufwand, eine einfache Schleife, man könnte sagen, das ist ein
linearer Aufwand, aber ich muss ja das Minimum bestimmen jeweils.
Also, wie groß ist der Aufwand?
N-mal für jede Position der Aufwand für das Minimum.
Wie bestimme ich das Minimum einer Folge von Zahlen?
Wie viele Vergleiche brauche ich dafür?
Ja, da gibt es einfache Überlegungen, wie man das machen kann.
Und es gibt das einfache Lemma.
Jeder Algorithmus, der nur mit binären Vergleichen arbeitet, braucht
mindestens N-1 Vergleiche für die Bestimmung des Minimums oder des
Maximums.
Das kennen Sie auch.
Ich mache einen ganz einfachen Beweis.
Sie haben einen Wettkampf und Sie sagen, der Sieger ist derjenige, der
nie verliert.
Die Frage ist, wie viele Spiele muss ich machen, damit einer
identifiziert werden kann, der nie verliert.
Das geht ja nur so, wenn bei N-Spielern N-1 Spieler verloren haben und
ein Spieler nie verloren hat.
Also muss ich mindestens N-1 Spiele machen, damit N-1 Spieler als
Verlierer gelten können.
Das ist offensichtlich.
Also das ist ganz einfach.
Der Beste darf nie verlieren, N-1 Spieler müssen mindestens einmal
verlieren, pro Spiel verliert genau ein Spieler, also N-1 Spiele.
Das ist trivial.
Jetzt machen wir das parallel.
Wie viele Schritte brauchen wir?
Wenn Sie so ein Tennistournament machen, wie viele Stufen haben Sie,
bis Sie ganz oben sind?
Na ja, das ist doch ganz einfach.
Bei jedem Spiel sind zwei beteiligt.
Das ist doch ganz einfach.
Ich brauche doch nur hier so einen Baum und dann habe ich jeweils ein
Spiel.
Also das ist ja ganz einfach.
Logarithmische Zahl von Schritten.
Ist die Frage, geht das besser?
Kann ich besser als in logarithmischer Zeit das bestimmen?
Also das ist erstmal hier, das mit N-1 ist klar.
Sequenziell, dass wir hier, ich komme gleich auf das Parallel wieder
zurück, sortieren durch Auswahl ist also ein quadratisches Verfahren.
Das wissen wir sequenziell, quadratisch und geht nicht besser.
Sortieren durch Auswahl ist immer quadratisch.
Auch im Mittel geht es nicht besser.