So, schönen guten Tag.
Ich begrüße Sie zur Fortsetzung von effizienten Algorithmen.
Leider heute etwas verspätet, weil da einige technische Probleme
waren.
Erst mit meinem Rechner, dann mit dem Beamer.
Aber das haben wir jetzt alles gelöst.
Jetzt kann es also losgehen.
Und dann gucken wir mal, was wir gemacht haben letztes Mal.
Die sind im Kapitel algebraische Probleme.
Und wir hatten uns da ja einiges schon angeguckt.
Wir hatten mit Matrixmultiplikation gestartet und uns das eigentlich
sehr intensiv angeguckt.
Indem wir einmal die Standardverfahren angeguckt haben.
Dann die von Vinograd.
Dann haben wir das Verfahren von Straßen genauer betrachtet.
Das eben darauf aufbaut, dass man mit einem Divide-and-Conquer-Ansatz
in der Lage ist, solche Matrizen schnell zu multiplizieren.
Wenn man also k-Kreuz-k-Matrizen einigermaßen schnell multiplizieren
kann.
Wobei schnell sich im Wesentlichen auf die Anzahl der Multiplikationen
bezieht.
Wenn ich die drücken kann unter n hoch 3, dann habe ich, also unter k
hoch 3 in dem Fall, wenn ich also weniger als k hoch 3
Multiplikationen habe für eine k-Kreuz-k-Matrixmultiplikation, dann
habe ich sofort eine asymptotische Verbesserung von meinem
Matrixmultiplikationsverfahren gegenüber n hoch 3.
Und das ist halt der wesentliche Punkt gewesen.
Das war dieser Standardansatz.
Und die Idee war ja, dass man dann eben für 2-Kreuz-2-Matrizen das
macht.
Da haben wir zufällig jetzt am Wochenende einen interessanten neuen
Artikel gefunden, wo jemand mit evolutionären Algorithmen untersucht
hat, ob man dieses Schema eigentlich auch durch eine solche Meta
-Heuristik finden kann.
Und interessanterweise hat er das alles geeignet kodiert und dann mit
einem evolutionären Ansatz solche Verfahren zur Multiplikation von 2
-Kreuz -2-Matrizen erzeugt.
Und erstaunlicherweise eine Menge solcher Verfahren gefunden, die mit
7 Multiplikationen auskommen.
Auch das von Vinograd, das mit 15 Additionen auskommt, während das von
Strassinger nur 18 hatte.
Da hat er eine ganze Bandbreite von solchen Verfahren gefunden.
Das heißt, man kann also das Interessante, dass man da also mit diesem
Ansatz eben auch für solche Anwendungen interessante Lösungen finden
kann.
Und das war eben nur für 2-Kreuz-2-Matrizen.
Das Interessante ist, das auch für 3-Kreuz-3-Matrizen zu probieren.
Wenn da einer von Ihnen Interesse hat, sich damit zu beschäftigen,
darf er sofort anfangen, daran zu arbeiten.
Das wäre also ein interessanter Ansatz, wie man das mal weiterbringen
könnte.
Wobei sich Leute seit langer Zeit damit beschäftigen, wie man bei 3
-Kreuz -3-Matrizen mit dem Strassenansatz, also diesem Divide-and
-Conquer -Ansatz, eventuell unter die Schranke von Strassen, also 2.81
kommen kann.
Wir wissen, dass man im Prinzip da ist bis auf 2.37, aber mit einer
riesigen Konstante vor diesem Term, sodass das praktisch irrelevant
ist.
Also da praktisch relevante Verfahren zu finden, wäre eine sehr
interessante Thematik.
Aber das nur kurz am Rande.
Es gibt ja noch viele andere Möglichkeiten, die Multiplikation zu
beschleunigen.
Das war dann hier die Matrixmultiplikation mit zweidimensionalen
Feldern.
Da hatte ich Ihnen hier das Verfahren von Kramer und von Löwen
vorgestellt, dass hier so durch drei sich bewegende Matrizen hier
durchläuft.
Ich hatte Ihnen vorher die anderen Verfahren gezeigt, wo man zwei
Matrizen hat, die sich bewegen.
Und wir haben uns dann letztes Mal auch angeguckt, den systematischen
Entwurf von parallelen Algorithmen, inwieweit man durch Analyse der
Datenabhängigkeiten und Ausgehen von so einem Datenabhängigkeitsgraf,
bei dem man an jedem Knoten die Einzelberechnungen im Prinzip drin
hat, wobei eine Einzelberechnung gerade diese Skalarprodukt-Operation
C plus A mal B ist.
Das waren also hier die Einzelberechnungen bei zum Beispiel einer 3x3
Matrix.
Und die Idee einer systematischen Abbildung oder eines systematischen
Entwurfs von Algorithmen ist halt, dass man so einen
Datenabhängigkeitsgraf abbildet auf zweidimensionale Prozessorfelder
und dann halt in der richtigen Art und Weise und richtig heißt unter
Beachtung der logischen Abhängigkeiten dann ein Programm erzeugt, das
auf so einem zweidimensionalen Feld abläuft.
Die Idee war eben mit solchen Transformationsmatrizen zu arbeiten, die
diesen Datenabhängigkeitsgraf sinnvoll abbilden auf Zeit- und
Ortskoordinaten.
Und ich hatte Ihnen dazu auch ein Werkzeug vorgestellt, mit dem man
ein bisschen rumspielen kann.
Das wollte ich jetzt nicht bewegen hier, ich wollte hier weitermachen.
Und ich hatte Ihnen dann als nächstes begonnen etwas zu erzählen über
die Auswertung von Polynomen.
Wir hatten die Problemstellung angeguckt und wir waren genau auf
dieser Folie, das war das letzte gewesen.
Es ging darum, dass wir in der Lage sein wollen, Polynome auszuwerten.
Und die Frage ist ja, was heißt das eigentlich, ein Polynom
auszuwerten?
Algebraische Operationen, die wir hier ausführen müssen.
Und um etwas sagen zu können über so einen Mindestaufwand, den man
treiben muss, muss man sich angucken, was sind eigentlich die
wesentlichen Operationen.
Und das war dadurch gemacht worden, dass man eine Basismenge definiert
hat, diese Menge b, von der man ausgeht.
Und wenn ich eben ausgehe von einer Menge, in der ich als Eingabe, im
Prinzip als Basismenge, bereits alle möglichen Polynome über x und die
Koeffizienten a0 bis a1 zur Verfügung habe, dann brauche ich nichts zu
tun, dann ist das eventuell schon gegeben als mögliche Eingabe.
Wenn ich aber nur solche Skalaelemente habe und diese unbekannten x
bzw.
die Koeffizienten a0 bis a1 und keine weiteren Operationen darauf,
also keine weiteren Elemente zur Verfügung habe, muss ich jedes
weitere Element, das durch Addition, Subtraktion, Multiplikation,
Division von solchen Elementen entsteht, halt explizit berechnen.
Das heißt, alle diese Operationen werden gezählt.
Darum geht es eigentlich.
Welche Operationen zähle ich?
Das heißt, wenn ich ausgehe von dieser Basismenge hier, dann muss ich
halt jede einzelne Operation auf x, a0 bis an und irgendwelchen
Skalaren zählen und komme dann auf diese unterschiedlichen Schemata,
wobei wir wissen, dass wir mit dem Horner-Schema da relativ schnell
das machen können, mit zwei n arithmetischen Operationen, also n
Addition, n Multiplikation.
Und die Idee ist, dass man sich überlegt, geht das eventuell noch
besser?
Und die untere Schranke, die ich Ihnen heute zeigen werde, sagt aus,
es geht nicht besser.
Zumindest dieser Satz von Ostrovsky, den ich jetzt hier nur zitiere,
den ich nachher aber gleich noch zeige, der sagt aus, dass man für die
Auswertung so eines allgemeinen Polynoms, bei dem man also vorher
nichts weiß über x und die Koeffizienten, ausgehend von, es steht hier
f und x in eckigen Klammern, vereinigt mit a0 bis an.
Das heißt, was ist die Eingabemenge?
f von x in eckigen Klammern heißt, dass ich in einem Polynomring über
diesem Körper arbeite.
Polynomring heißt, ich kann also alles, was Polynome in x und Skalaren
sind, also zum Beispiel x natürlich oder 2x² oder auch x³ plus x² plus
3 oder was immer.
Das sind typische solche Polynome über f.
Und dazu kommen noch meine a0 bis an, die ich halt nicht weiter kenne.
Ich habe aber in einem Polynomring eben multiplikativ keine Gruppe,
sondern nur eine Halbgruppe.
Das heißt, ich habe keine Inverse, ich habe also keine Division dort.
Ich habe nur eine Multiplikation.
Ich habe keine Polynom-Division da drin.
In diesem Polynomring f von x, da habe ich nur alle Elemente, die ich
durch Addition, Subtraktion und Multiplikation bekomme, aber nicht
Elemente, die ich durch Division bekomme.
So, wenn ich in diesem Bereich arbeite, auch hier steht das x und a0
bis an in eckigen Klammern, ich möchte also nur Elemente da drin
berechnen, dann ist das die mathematische Formulierung für die
Aussage, ich darf keine Division verwenden.
Ich habe Ihnen das mehrfach versucht zu erzählen, es gibt formale
Modellierungen.
Das ist das, was wir eigentlich ausdrücken wollen, was dann formal
modelliert werden muss.
Die formale Modellierung der Aussage, ich möchte nur Addition,
Subtraktion und Multiplikation zulassen, ist, ich rechne in einem
Polynomring.
Das ist die mathematische Formulierung.
Und dann kann ich alles, was ich über Polynomringe weiß, ausnutzen, um
etwas zu sagen über die Schwierigkeit, solche Berechnungen
durchzuführen.
Aber das, was ich eigentlich machen möchte, ist, ich möchte sagen, ich
arbeite mal nur mit Addition, Subtraktion und Multiplikation und wie
viel Aufwand, wie viel Addition muss ich dann mindestens ausführen, um
so ein Polynom auszuwerten.
Also in so einem Polynom habe ich ja normalerweise von der
Formulierung her nur Addition, Subtraktion und Multiplikation,
deswegen müsste es ja eigentlich ausreichen.
Wir hatten aber zu Beginn mal gesehen, dass es Polynome gibt, bei
denen man durch eine Division auch Operationen sparen kann.
Also insofern ist es nicht naheliegend, dass man mit Division dann
eventuell auch diese N-Additionen bräuchte.
Also keine Division, nur Addition, Subtraktion und Multiplikation.
Und die Aussage ist, dann brauchen wir mindestens N-Additionen.
Und das, was hier steht über Polynomringe und all sowas, ist einfach
nur die mathematische Formulierung.
Wir gehen darauf nur am Rande eigentlich ein, aber ich will Ihnen
einfach zeigen, was ist das mathematische Gerüst, mit dem man dann
tatsächlich etwas sehr exakt beweisen kann.
Es gibt dann einen Satz, der darüber hinaus geht, der sagt dann sogar
aus, dass man für die Berechnung des Polynoms nicht nur den
Polynomring, sondern in der transzendenten Körpererweiterung und
wieder, transzendente Körpererweiterung heißt nur, ich darf addieren,
subtrahieren, multiplizieren und auch dividieren.
Wenn also die runden Klammern stehen, heißt das, das ist eine
Körpererweiterung.
Auch multiplikativ ist es eine Gruppe.
Also zu jedem Element existiert ein Inversus, das heißt, ich kann auch
dividieren.
Dann ist das Horner-Schema ein optimaler Algorithmus in Bezug auf die
Anzahl der Multiplikationen und Divisionen.
Das heißt, das Horner-Schema hat N Multiplikationen, also ist es
optimal.
Und wir wissen, wenn wir nur mit Multiplikationen arbeiten, dann habe
ich insgesamt auch hier mindestens N Additionen zu machen.
Also über diese Sätze kriegt man dann eine Aussage hin, dass das
Horner -Schema insgesamt optimal ist.
Also, das Korollar, das sagt dann ja aus, dass man noch ein bisschen
mehr machen muss.
Also dieser Satz von Ostrowski hat ja noch die Einschränkung, dass
keine Divisionen erlaubt sind.
Da ist noch etwas mehr erforderlich, worauf ich hierbei nicht weiter
eingehe.
Sie haben eine Frage?
Alle, die in F gegeben sind.
F ist irgendein Körper.
Wenn F die reellen Zahlen sind, wenn F der Körper der reellen Zahlen
ist, dann sind alle reellen Zahlen erlaubt.
Aber es kann ja sein, dass wir nicht die reellen Zahlen haben, sondern
nur die rationalen Zahlen.
Oder es kann sein, dass wir nur einen endlichen Körperdritt stehen
haben.
A0 bis AN können reelle Zahlen sein, das ist in der Realität ja.
Aber ich nutze deren, ich habe ja vorweg keine Informationen darüber.
Und ich sehe das als algebraische Operation an.
Das ist einfach als Operation an auf diesen Elementen.
Die werden dort im Prinzip als Unbekannte betrachtet.
Und wenn in dem Ringen schon alle...
Das ist einfach formal ein Unterschied.
Ich verwende also keine Informationen darüber, was A0 bis AN
tatsächlich sind.
Das sind für mich Unbekannte.
Und ich gucke mir einfach an, wie kann ich diesen...
Ich möchte gerne diesen Term, Summe AIXI, den möchte ich erzeugen.
Ich kann das durch alle möglichen Operationen machen.
Ich darf aber Informationen über AI und XI in meinem Berechnungsschema
nicht ausnutzen.
Ich habe einen Algorithmus.
Und der Algorithmus hat keine Vorinformationen über die einzelnen AI
und über das X.
Der hat Informationen, der kann also 2 und 2 multiplizieren und
addieren usw.
Der hat also im endlichen Körper alles, was in F an Elementen drin
ist.
Das kann der alles verwenden.
Sie sehen das gleich, wenn ich diesen Satz von Nostrovsky beweise,
sehen Sie, was das heißt.
Also in welcher Art man hier Operationen einsetzen kann.
Das ist einfach...
Ich habe in dem Algorithmus...
Wenn ich den Algorithmus formuliere, nutze ich keine Informationen aus
darüber, welchen Wert tatsächlich A1 oder A0 bis AN haben.
Das Horner Schema nutzt von der algorithmischen Struktur her nicht
aus, welchen Wert jetzt die einzelnen A0 bis...
also die einzelnen Koeffizienten A0 bis AN haben.
Das läuft egal welche Koeffizienten dort sind, immer gleich ab.
Und das ist eigentlich nur die Aussage, es tauchen in dem Algorithmus
nur diese Koeffizienten auf.
Das können, selbstverständlich in der Realität, sind das dann
irgendwelche Zahlen.
Ich kann die ja real auch tatsächlich auswerten, diese Operationen.
Aber es geht einfach darum, dass der Algorithmus keine weitere
Kenntnis hat über diese Koeffizienten.
Also wenn ich beispielsweise weiß, dass A1 plus A2 meinetwegen gleich
A3 ist.
Wenn ich das wüsste von vornherein, dann könnte ich das ausnutzen,
könnte ich diese Kenntnis ausnutzen.
Und bräuchte zum Beispiel die Addition A1 plus A2 nicht auszuführen.
Das weiß ich aber vorher nicht.
Das wäre so eine typische Information, wenn das jetzt Zahlen wären, 2,
3 und 5.
Dann bräuchte ich, wenn ich jetzt irgendwo den Term A1 plus A2
brauche, dann kann ich da auch A3 für verwenden.
Das geht aber nur, wenn ich diese Information vorher habe.
Die habe ich aber nicht.
Und ich muss um A1, wenn ich dieses nicht weiß, ob das so ist.
Das wäre eine typische Information, die man vielleicht vorher hätte.
Dann kann man den Algorithmus anders machen.
Ich zeige Ihnen heute noch ein Beispiel, was man machen kann, wenn man
die Werte kennt.
Dann sieht der Algorithmus anders aus.
Ich hoffe, dass das dadurch klarer wird.
Ich kann Ihre Frage sehr gut verstehen, weil das ein bisschen
abstrakte Denkweise ist.
Aber es geht einfach darum, wie kann ich diesen Term Summe A IX hoch I
erzeugen?
Wie viele Operationen brauche ich?
Und ich darf dabei nicht Informationen über den konkreten Wert der
einzelnen AIX ausnutzen, weil ich die eben in dem Algorithmus erst als
Eingabe bekomme und der Lauf des Algorithmus davon nicht direkt
abhängen soll.
Gut, also das ist jedenfalls das, was wir hier im Prinzip als
Erkenntnis haben aus diesen beiden Sätzen.
Da ist noch ein bisschen mehr dran zu tun, aber ich will Ihnen nur
einen Einblick geben, was man überhaupt macht, allein um diesen Satz
von Ostowski von vor 50 Jahren zu zeigen.
Und das ist ein relativ einfacher Gedankengang, der Ihnen aber
trotzdem zeigt, glaube ich, wie man hier vorgeht.
Also, was wir machen wollen, ist nur untere Schranke zeigen.
Ich brauche mindestens N Additionen.
Wofür?
Um dieses allgemeine Polynom auszuwerten.
Die Summe A IX hoch I.
Diese Summe A IX hoch I ist ja nur eine Abkürzung für einen längeren
Ausdruck.
Jetzt will ich das Problem vereinfachen.
Eine Vereinfachung z.B.
dadurch, dass ich jetzt sage, ich nehme mal an, ich weiß etwas über X
und nehme mal an, das ist 1.
Wenn das X 1 wäre, dann könnte ich einen neuen Algorithmus
formulieren, A Strich, der der Algorithmus A ist für X gleich 1.
Wenn X gleich 1 ist, dann würde natürlich dieser Algorithmus etwas
anderes ausrechnen.
Der würde nämlich ausrechnen, diese Summe der A I.
Alle X hoch I sind 1, also habe ich nur die Summe der A I
auszurechnen.
So, jetzt habe ich einen Algorithmus, der ein deutlich einfacheres
Problem bearbeiten muss.
Sieht zumindest zunächst so aus.
Und jetzt ist die Überlegung, ich berechne jetzt eine untere Schranke
für dieses Problem.
Das ist ein Problem, das ist sicherlich mindestens so schwer, wie das
Problem.
Also wenn ich etwas weiß über eine untere Schranke für dieses Problem,
dann habe ich auch eine untere Schranke für das Problem hier oben.
Weil wenn ich hierfür N Additionen brauche, nur für die Summe der
Koeffizienten, brauche ich sicherlich auch mindestens N Additionen, um
diesen anderen Algorithmus hier auszuwählen.
Also ich kann den Algorithmus dann einfach darauf reduzieren, ich
gucke mir nur diese Summe der einzelnen Koeffizienten an.
Also A Strich benötigt sicherlich nicht mehr Additionen als A.
Das ist glaube ich eindeutig, das Problem ist einfacher.
Also kann der Algorithmus nicht mehr Additionen brauchen.
Und jetzt ist die Behauptung, dass die Auswertung oder die Berechnung
dieser Summe mindestens N Additionen braucht.
Das ist ja das, was man intuitiv auch sofort sieht.
Ich habe ja hier hinzuschreiben A0 plus A1 plus A3 und so weiter bis A
N.
Das sind genau N Additionen, die da drinstehen und ich brauche auch
genau diese N Additionen.
Das ist die Aussage.
Und jetzt machen wir einen Beweis über Induktion und gucken uns an,
was ist denn für N gleich 0.
Für N gleich 0 habe ich hier nur ein Element drin, nur A0.
Für A0 brauche ich keine Addition.
Das Element ist mir ja gegeben als Eingabe.
Keine Addition erforderlich, das habe ich schon gegeben.
Und jetzt mache ich die Induktionsannahme.
Die Annahme ist, es existiert ein Algorithmus, oder es sei also
bewiesen für alle für N.
Und wir nehmen jetzt an, es gibt ein Algorithmus B.
Das ist jetzt praktisch eine Widerspruchsannahme.
Ich nehme an, dass es ein Algorithmus gibt für N plus 1, der weniger
als N plus 1 Additionen auskommt.
Die Behauptung hier oben ist, ich brauche mindestens N.
Ich nehme an, ich habe das für N gezeigt.
Und jetzt nehme ich an, es gibt ein Algorithmus, der mit weniger
Additionen auskommt für N plus 1.
Bis N ist es gezeigt, dass ich mindestens N brauche für N plus 1.
Nehmen wir an, gibt es jetzt ein Algorithmus, der eine Addition
weniger braucht.
Dann guckt man sich an, wie sieht denn so ein Algorithmus aus.
Egal wie der Algorithmus arbeitet, es ist etwas über beliebige
Algorithmen.
Dieser Algorithmus B, der wird irgendwann eine erste Addition machen.
Irgendwann eine erste Addition heißt, er hat bis dahin, das ist die
erste Addition, er hat bis dahin schon einiges getan.
Er hat nämlich bis dahin irgendwelche anderen Operationen ausgeführt.
Diese anderen Operationen sind irgendwelche Produkte, also
Multiplikationen.
Er kann keine Divisionen machen, er kann nur Addieren und
Subtrahieren...
Quatsch, er kann nur Addieren, Subtrahieren und Multiplizieren.
Er hat noch keine Addition gemacht, natürlich auch keine Subtraktion,
das ist ja im Prinzip das Gleiche, nur Addition des Inversen.
Er kann also nur multipliziert haben.
Wenn er nur multipliziert hat, kann er also nur irgendwelche
Koeffizienten multipliziert haben.
Stehen da noch irgendwelche Exponenten dran?
Das heißt, er hat natürlich A1 mal A1 genommen, das wäre A1².
Oder irgendwas.
Diese Ri hier drin sind irgendwelche Potenzen dieser einzelnen
Koeffizienten.
Er kann nur multipliziert haben.
Und er kann auch mit irgendwelchen Skalaren multipliziert haben, aus
F.
Das ist das C.
Wenn er mehrfach Skalare multipliziert, kommt ein Skalar raus.
Da brauche ich also nur ein Skalar hinzuschreiben.
Skalar heißt Element aus F.
Das heißt, das ist ein Körperelement.
Das ist irgendein Produkt der Koeffizienten.
Da stehen irgendwelche Exponenten oben drin.
Das ist der eine Term.
Und der andere, analog, hat auch irgendwelche Multiplikationen
gemacht.
Und dabei sind also C1, C2 Elemente des Körpers.
Und diese Ri und Si, die Exponenten, sind halt irgendwelche
natürlichen Zahlen.
Kann alles Nullen sein.
Oder bis auf wenige Elemente.
Wenn da ein Exponent Null ist, habe ich halt diesen Koeffizient dort
nicht drin.
Also wenn dort stehen würde zum Beispiel A1 hoch 2 und A2 hoch 0, dann
ist halt klar, dass es einfach nur A1 hoch 2 ist.
Weil ja A2 hoch 0 gleich 1 ist.
Also das sind irgendwelche Potenzen der Koeffizienten, modifiziert mit
irgendeinem Skalarlimit.
Und jetzt ist diese eine Addition da.
Jetzt ist die Überlegung.
Es sind ja Koeffizienten A0 bis A1 plus 1 in dem Fall.
Und wir nehmen einfach an, dass mindestens einer dieser Exponenten,
und wir nehmen an, in dem ersten Term, Ungleich Null ist.
Also wenn die alle gleich Null wären, dann würde es ja keinen Sinn
machen, dann hätte ich ja nur eins stehen.
Dann wäre da kein Koeffizient wirklich mit vorgekommen.
Es muss schon ein Koeffizient vorkommen.
Jetzt nehme ich einfach an, das ist der Koeffizient An plus 1.
Das kann ich ohne Beschränkung der Allgemeinheit...
Das hier heißt, ich hoffe, dass es allen klar ist, ohne Beschränkung
der Allgemeinheit heißt das.
Das heißt, wenn das ein anderer wäre, könnte ich einfach die
Koeffizienten umbenennen und könnte das so umbenennen, dass das gerade
dieses An plus 1 ist.
Das ist also wirklich ohne Beschränkung der Allgemeinheit möglich.
Ich sage nur, es gibt irgendeinen Koeffizienten, der garantiert
vorkommt.
Das heißt, da ist das An plus 1 Ungleich Null.
Also An plus 1 kommt in diesem ersten Produkt vor.
So kann man das immer machen, egal wie der Algorithmus aussieht.
Weil ja die Addition kommutativ ist, darf ich das so hinschreiben.
Und weil ich die Koeffizienten auch irgendwie umordnen könnte, darf
ich sagen, das ist das An plus 1.
So, jetzt ist die Idee, ich betrachte wieder ein spezielleres Problem.
Ich gucke mir den gleichen Algorithmus an, ich verändere den
Algorithmus nicht, vom Ablauf her.
Ich setze einfach nur das An plus 1 auf den Wert Null.
Jetzt nehme ich etwas an, über diesen Koeffizienten An plus 1.
Ich sage, es könnte ja sein, dass der Null ist.
Was würde dann im Algorithmus passieren?
Wenn der Null ist, das darf ich machen, weil ich keine Division habe.
Wenn Divisionen vorkommen könnten im Algorithmus, könnte es sein, dass
das An plus 1 irgendwo im Nenner steht.
Und dann hätte ich auf einmal Division durch Null, das darf natürlich
nicht passieren.
Da ist also die Bedingung wichtig, der Algorithmus erwähne keine
Division.
Was passiert denn dann mit meinem Algorithmus?
Wenn das An plus 1 Null ist und das Rn plus 1 ist ungleich Null, also
der Exponent von dem An plus 1 in diesem Produkt hier, dann steht hier
Null hoch irgendetwas, das ist Null.
Das heißt, dieser ganze erste Term, Pi 1 von A, fällt weg.
Der wird gleich Null.
Sofern An plus 1 gleich Null ist, würde also Folgendes passieren.
Die erste Addition taucht gar nicht mehr auf.
Die ist gleich Null, äh Quatsch, die ist irrelevant, weil dieser erste
Term Null ist, brauche ich die Addition gar nicht auszuführen.
Ich könnte also den Algorithmus, im Algorithmus auf diese erste
Addition verzichten.
Ich weiß jetzt ja, wenn ich weiß, An plus 1 ist Null, dann kann ich
auf diese erste Addition verzichten.
Und nun ist die Frage, was berechnet der Algorithmus denn dann noch,
wenn ich auf die erste Addition verzichte?
Alles andere bleibt ja gleich.
Naja, ich habe ja die Annahme gehabt, An plus 1 ist Null, es wird nur
auf diese Addition verzichtet, alles andere bleibt gleich.
Und was kann dann noch berechnet werden, wenn An plus 1 gleich Null
ist?
Dann berechnet der doch gerade die Summe I gleich Null bis N AI.
Das heißt, er berechnet die Summe für N mit einer Addition weniger.
Wir hatten K-Addition hier oben angenommen.
Jetzt hat er eine Addition reduziert und der Rest des Algorithmus
berechnet gerade die Summe von I gleich Null bis N mit K-Addition.
Das ist dann aber kleiner als N, weil ja K kleiner als N plus 1 ist.
Also K-1 kleiner als N.
Und das heißt, dieser Algorithmus B wäre für diesen Spezialfall An
plus 1 gleich Null in der Lage, die Summe I gleich Null bis N AI mit
weniger als N Additionen zu berechnen.
Und das ist aber ein Widerspruch gegen unsere Induktionsannahme, dass
wir für I gleich Null bis N AI für diese Summe mindestens N Additionen
brauchen.
Das heißt, der Vorgang hier war so, wir haben angenommen, es gibt
einen Algorithmus, der die Summe bis N plus 1 weniger als N plus 1
Additionen berechnen kann.
Und dann können wir zeigen, dann ist ein Algorithmus auch in der Lage,
die Summe I gleich Null bis N mit weniger als N Additionen zu
berechnen.
Und das heißt, das kann nicht stimmen.
Das ist ein Widerspruch gegen die Induktionsannahme.
Das heißt, wir haben damit das, was wir brauchen.
Wir haben gezeigt, man kann nicht mit weniger als N Additionen eine
Summe von I gleich Null bis N AI berechnen.
War das verständlich?
Wir haben einfach nur diesen Spezialfall jetzt angenommen.
A N plus 1 ist Null.
Der Algorithmus ansonsten verändert sich dadurch ja nicht.
Bis auf den einen Punkt, dass ich sage, diese eine Addition, das war
die erste Addition um Algorithmus B, die ist dann irrelevant, auf die
kann ich verzichten.
Dieser Algorithmus B, an der Stelle A N plus 1 gleich Null, kann auch
die Summe I gleich Null bis N AI berechnen, dann mit weniger als N
Additionen.
Und das ist eine Widerspruch zur Induktionsannahme.
Das ist die ganz einfache Überlegung und damit ist dieser Satz von
Ostrowski bewiesen.
Entschuldigung, ich denke das ist ein Überdruck.
Macht nichts.
Ich sehe den Widerspruch nicht so ganz.
Also ich kann das verstehen.
Die Induktionsannahme ist ja die Behauptung bewiesen für N.
Das heißt ich brauche für die Summe I gleich Null bis N AI mindestens
N Additionen.
Das ist die Induktionsannahme.
Und dann muss ich zeigen, den Induktionsschluss machen, ich muss
zeigen, dass ich damit auch für N plus 1 das zeigen kann.
Und ich mache das so, dass ich folgendes annehme, ich nehme an für N
plus 1 gilt es nicht.
Und daraus folgt, es gilt auch nicht für N.
Die typische Induktions- oder das ist doch die übliche Vorgangsweise
bei einer Induktion.
Ich habe den Induktionsanfang für N gleich Null.
Induktionsannahme ist, die Behauptung sei für N bewiesen.
Und jetzt zeige ich, es gilt auch für N plus 1.
Ja.
Und um zu zeigen, es gilt auch für N plus 1, mache ich das genau durch
Kontraposition.
Ich nehme an, es gilt für N plus 1 nicht.
Und kann daraus zeigen, es gilt dann auch nicht für N.
Und wenn ich das zeige, dass also, wenn aus nicht, sagen wir jetzt
Induktionsbehauptung für N plus 1, folgt nicht Induktionsbehauptung
für N, dann ist das doch äquivalent damit, dass aus I von N, I von N
plus 1 folgt.
Kontraposition.
Ja?
Richtig.
Genau.
Das kommt raus.
Das zeigt, es gilt I von N nicht.
I von N in dem Fall wäre also die Induktionsbehauptung, dass ich für
die Summe I gleich Null bis N mindestens N Additionen brauche.
Das ist die Induktionsbehauptung.
Der Induktionsanfang war, für N gleich Null geht es mit Null
Additionen, ohne Additionen.
Jetzt nehme ich an, oder behaupte ich, für N sei das gezeigt, das
typische Induktionsvorgang, für N ist es gezeigt, das heißt für Summe
I gleich Null bis N AI brauche ich mindestens N Additionen.
Und nun zeige ich, dann gilt das auch für N plus 1.
Das zeige ich in diesem Fall so, dass ich mir angucke, das Problem für
N plus 1, also Summe I gleich Null bis N plus 1, und ich nehme an,
dass das hier nicht gilt.
Dass hier das nicht I von N plus 1 gilt, also Induktionsbehauptung für
N plus 1.
Wenn das nicht gilt, heißt das, ich kann mit weniger als N plus 1
Additionen meine Summe berechnen.
Und das war die Annahme.
Also insofern, das ist hier die Annahme, dass das I N plus 1 nicht
gilt.
Deswegen muss es einen Algorithmus B geben, der halt dann mit K
kleiner N plus 1 auskommt.
Und jetzt zeige ich eben, dann kann ich einen Spezialfall
konstruieren, mit dem dieser Algorithmus B genauso arbeiten muss, aber
der braucht eine Addition weniger.
Und berechnet zufälligerweise die Summe I gleich Null bis N AI.
Ich habe den Algorithmus B nicht verändert dabei.
Ich habe nur die eine Addition überflüssig gemacht.
Das ist das, was ich hier angedeutet habe.
Die eine Addition wurde überflüssig für den Spezialfall A N plus 1
gleich Null.
Und dann habe ich halt ein Verfahren, das B an der Stelle A N plus 1
gleich Null, das berechnet dann meine Summe I gleich Null bis N mit
weniger als N Additionen, was ein Widerspruch ist zu der eigentlichen
Annahme, dass das für N gilt.
Also das ist genau diese Aussage hier.
Nicht I von N plus 1 folgt nicht I von N.
Das heißt, aus der Annahme, dass das für N gilt, folgt auch, dass es
gilt für N plus 1.
Das ist einfach Induktion.
Ich denke, ich habe das jetzt eigentlich ausreichend erklärt.
Das ist wirklich Induktionsvorgang.
Machen Sie das, diskutieren Sie das in den Übungen.
Sie können sicher sein, das wird jetzt also auch keine weiteren
ausführlichen Beweise, oder es gibt an einer Stelle nochmal eine
genauere Überlegung.
Aber ich mache nicht ständig solche Beweise.
Wobei das eigentlich kein Problem sein sollte, Beweise durchzuführen.
Aber ich weiß, dass Sie damit normalerweise gewisse Schwierigkeiten
haben.
Ich muss Ihnen zeigen, wie man mit formalen Methoden solche Aussagen
beweisen kann.
Und ich muss manchmal in der Lage sein, etwas zu sagen über untere
Schranken.
Das ist nicht einfach, weil ich halt etwas sage über beliebige
Algorithmen.
Sie haben noch eine Frage da hinten.
Noch eine weiter.
Diese.
Ja.
Richtig.
Hier.
Genau.
Ich
kann...
Also.
Ich sage hier, es gibt...
Also, die Aussage ist, der Algorithmus B für a n plus 1 gleich 0
kann diese Summe hier mit k minus 1 Addition berechnen.
Ja.
Wir haben ja eine Addition rausgestrichen.
Deswegen ist das genau die gleiche Aussage wie hier oben.
Der kann diese Summe hier oben bis n plus 1 mit k kleiner n plus 1
Addition berechnen.
So, das ist genau die Folgerung daraus ist sofort, dass wenn ich also
jetzt an der Stelle n plus 1 betrachte, dann braucht der, weil ich
eine Addition rausgestrichen habe, eben nur k minus 1 Addition.
Der Widerspruch ist zu der Annahme, dass ich das für n eigentlich
bewiesen habe,
für die Summe i gleich 0 bis n brauche ich mindestens n Additionen.
Das ist das i von n.
Das ist die Induktionsannahme.
Ich sagte, die eigentliche Induktionsannahme ist, die Behauptung sei
bewiesen für n.
Das ist hier die eigentliche Induktionsannahme i von n.
Und das, was ich jetzt mache, ist, ich will zeigen, dann gilt das auch
für n plus 1.
Das kommt aus dem Induktionsschluss.
Für den Induktionsschluss muss ich mir angucken, das Problem für n
plus 1.
Und ich muss zeigen, dass jetzt ich auch für n plus 1 zeigen kann, es
gilt i von n plus 1.
Auch für n plus 1 brauche ich für die Summe i gleich 0 bis n plus 1 a
i mindestens n plus 1 Addition.
Ich muss zeigen, aus i von n folgt i von n plus 1.
Und ich mache das so, dass ich zeige, aus nicht i von n plus 1 folgt
nicht i von n.
Kontraposition.
Ich hätte auch sagen können, hier, daraus folgt nicht i von n.
Hier unten.
Das, was ich hier angedeutet habe.
Ganz normale Induktion.
Ich glaube, ich mache an der Stelle Schluss.
Nicht Schluss, sondern mache weiter.
Jetzt kommt nämlich eine Antwort auf die Frage, die Sie vorhin hatten.
Ich weiß doch, wenn ich einen konkreten Algorithmus oder ein Polynom
auswerte, dann sind doch die Werte, die ich dort drin habe, also hier
die Werte in so einem Polynom, das sind doch irgendwelche konkreten
Zahlen.
Wenn Sie sagen, das sind irgendwelche konkreten Zahlen, das könnte ich
ja irgendwie ausnutzen, dann sind diese Koeffizienten keine
Unbekannten, sondern das sind das Elemente meines Körpers.
Und dann kann ich Kenntnisse über die Eigenschaften des Körpers
ausnutzen, um mein Polynom auszuwerten.
Jetzt habe ich also ein Polynom, das ist nicht gegeben als a6x6 plus
a5x5 und so weiter, sondern es stehen Zahlen.
Sie haben es verstanden.
Okay.
Sie müssen mir den Trick verraten, wie Sie das erklärt haben.
Okay, später.
Jetzt gucken wir uns dieses konkrete Problem an.
Jetzt habe ich eine andere Startinformation.
Ich weiß, oh, ich muss dieses Polynom auswerten.
Da stehen ganz konkrete Zahlen drin.
Und jetzt überlege ich mir, ich kenne also die Koeffizienten, ich
kenne das x nicht.
Das x wird mir irgendwann gegeben.
Und ich weiß jetzt, dieses Polynom muss ich meinetwegen ganz oft
auswerten.
Dann werde ich alles daran setzen, dieses spezielle Polynom möglichst
effizient auszuwerten.
Und der Kenntnis der einzelnen Werte, die hier stehen.
Und ich weiß, da sind irgendwelche arithmetischen Beziehungen zwischen
diesen einzelnen Werten, zum Beispiel 4 mal 2 ist 8.
Weiß ich schon, dass ich... also 4 mal a6 ist a5.
All solche Dinge.
Die weiß ich sofort, sehe ich sofort.
Das heißt, ich habe jetzt deutlich mehr Information, wenn ich weiß,
das sind irgendwelche speziellen Zahlen aus meinem Körper, dann heißt
das, ich habe mehr Information.
Das ist der wesentliche Punkt.
Und ich entwerfe jetzt den Algorithmus für dieses Polynom.
Vorher haben wir nur gewusst, ich kriege ganz oft, muss ich immer
wieder machen, Polynome geliefert.
Ich weiß aber vorher nicht, was für ein Polynom das ist.
Ich kenne die einzelnen a0 bis a1, also die einzelnen Koeffizienten
nicht.
Ich kenne das x auch nicht.
Und ich muss, egal was dort kommt, immer den richtigen Wert liefern.
Jetzt habe ich das Problem, ich habe dieses spezielle Polynom p6 und
weiß, egal welches x kommt, es muss der richtige Wert kommen.
Das ist aber viel einfacher.
Oder ein anderes Problem.
Ich habe ja Informationen über die Koeffizienten.
Und jetzt nutze ich die aus.
Zum Beispiel so, dass ich sage, aha, ich kann dieses Polynom etwas
verändern.
Ich stelle fest, ich kann es als ein Produkt darstellen, eines
Polynoms x²-4 mal diesen Polynom vierten Grades, 2xo4 und so weiter,
plus 53.
Also hier sehen Sie zum Beispiel 4 mal 2 hoch...
Also ich weiß halt, aber ich kann hier rechnen.
Ich habe einfach das x²-4 ausgeklammert, dividiert das Polynom durch
x² -4, dann kriege ich diesen Ausdruck.
Wie man darauf kommt, sei jetzt völlig offen, fällt vom Himmel.
Zunächst mal.
Jetzt habe ich also eine andere Darstellung meines Polynoms.
Und jetzt kann ich mir angucken, dieses Polynom vierten Grades.
Und dieses Polynom vierten Grades kann ich ja auch wieder
modifizieren.
Das ist nämlich gerade das Produkt von x²-9 mal 2x² plus 8x plus 1
plus 4.
So, Polynom zweiten Grades.
Jetzt habe ich also insgesamt mein P6 dargestellt als ein Produkt von
Polynomen.
Hier das P4 von x ist ja jetzt auch ein Produkt von Polynomen zweiten
Grades.
Es tauchen also eine Reihe Polynome zweiten Grades auf, wobei die in
der Regel eine einfache Darstellung haben.
Nämlich sowas wie hier nur x²-4 oder x²-9, also irgendein x² plus c.
Irgendein Wert aus f.
Und dann noch ein Polynom, wo dann steht 2x² plus c1x plus irgendwie
diesen c0.
Und dann noch irgendein konstanter Term dahinter.
Und jetzt kann ich mir überlegen, wie kann ich denn so ein Polynom
jetzt ausnutzen.
Ich mache es einfach so, dass ich jetzt einmal x² ausrechne.
Das ist eine Multiplikation.
Das kann ich mit jedem, egal welches x kommt.
Ich muss also x² berechnen.
Dafür brauche ich eine Multiplikation.
Jetzt berechne ich P2 von x.
P2 von x ist dieses Polynom hier.
2x² plus 8x plus 1.
Da habe ich das x² bereits berechnet.
Das muss ich mit 2 multiplizieren.
Dann habe ich 8 mal x zu rechnen.
Und ich muss noch dann diese beiden Werte addieren und eine 1 drauf
addieren.
Das heißt, ich habe 2 Multiplikationen und 2 Additionen zu machen.
Diese beiden Additionen und die beiden Multiplikationen.
Und jetzt habe ich also das P2 von x berechnet und berechne P4 von x.
Und um P4 von x zu berechnen, muss ich diese Addition ausführen.
Ich muss x² plus 9 berechnen.
Ich muss diese Multiplikation ausführen.
x² plus 9 mal P2 von x.
Und ich muss diese Addition da oben ausführen.
Das sind 2 Additionen und 1 Multiplikation.
Und dann als viertes habe ich also P4.
Ja, wiederum eine Addition, eine Multiplikation und nochmal eine
Addition.
Wieder eine Multiplikation und 2 Additionen.
Und habe jetzt insgesamt 5 Multiplikationen und 6 Additionen.
Sieht man das jetzt noch nicht so doll aus.
Statt 6 Multiplikationen und Additionen jeweils habe ich jetzt 5
Multiplikationen und 6 Additionen.
Eine Multiplikation eingespart.
Das sieht noch nicht nach einer dollen Ersparnis aus.
Aber Sie sehen, dass sich hier schon so etwas wie eine Systematik
andeutet.
Ja, hier ist aber der Gratus-Polynoms relativ klein.
Und das Ganze kann ich...
Das ist auf jeden Fall besser als vorhin das Schema.
Das ist also immerhin schon ein Gewinn, den ich habe durch nur einfach
Kenntnis der Koeffizienten.
Jetzt kann ich das Ganze allgemein machen.
Und das allgemeine Schema sieht halt jetzt so aus, wie hier
angedeutet.
Ich fange also an, dass ich einfach von meinem Polynom n-ten Grades so
einen quadratischen Term abspalte.
Da steht jetzt so ein x²-αn.
Das ist jetzt also irgendeine Konstante aus f, eine geeignete.
Das stelle ich so dar als Produkt von zwei Polynomen.
Eins Grad 2, sehr einfach.
Und das andere Grad n-2.
Und dann habe ich hier irgendeinen Restwert.
Und das mache ich so lange, bis ich eben runterkomme auf ein Produkt
von Polynomen, die nur maximal Grad 2 haben.
Und dann werte ich das Ganze aus.
Und dann muss ich halt die ersten beiden Schritte genauso machen wie
vorher.
Ich berechne erst x².
Dann berechne ich das p2 von x.
Das ist halt hier mein Polynom zweiten Grades, das ich dann irgendwie
auswerten muss mit meinen zwei Multiplikationen, zwei Additionen.
Und danach kommen für i gleich 2 bis...
...ja, bis ich dann also oben bin, bis n-Halbe.
Ich habe ja hier p2i jeweils, was ich dann ausrechne.
Das ist gerade dann Auswertung dieses Ausdrucks.
Und das ist eine Multiplikation, zwei Additionen.
n-Halbemal.
Also habe ich n-Halbe mal eine Multiplikation und zwei Additionen.
Und dann noch hier oben diese Additionen obendrauf.
Das heißt, ich habe insgesamt n-Halbe plus zwei Multiplikationen und n
Additionen.
Wenn Sie das alles zusammenzählen, hier von 1, 2 und 3, kommen Sie
genau auf diese Anzahl von Operationen.
Und Sie sehen, wir haben mit diesem Schema die Anzahl der
Multiplikationen um die Hälfte reduziert.
Bis auf 2, also n-Halbe minus 2 haben wir hier wegstreichen können.
Ohne die Anzahl der Additionen zu erhöhen.
Wir müssen aber, um das machen zu können, um so einen Algorithmus zu
konstruieren, zunächst mal diese Zerlegung hinbekommen.
Also diese Zerlegung runter bis auf Pn von x, runter bis auf dieses P2
von x.
Wir müssen überall diese quadratischen Terme da rausstreichen.
Dazu muss man erstmal diese Alpha n bis Alpha 4 dort bestimmen.
Das ist eine gewisse Vorberechnung.
Da muss man einiges tun, um diese Alpha i zu berechnen.
Darauf will ich gar nicht eingehen.
Das kann man machen.
Was ich Ihnen jetzt zeigen möchte, ist einfach nur, wenn ich mehr
Informationen habe, das ist genau die Antwort auf Ihre Frage von
vorhin.
Diese Koeffizienten, die haben doch irgendwelche Werte.
Wenn ich die kenne, bevor ich das Polynom auswerten muss, dann kann
ich den Algorithmus so modifizieren oder so umbauen, dass ich
anschließend, egal welches x ich bekomme, mit weniger Operationen
auskomme.
Ich kann die Anzahl der Multiplikationen um fast die Hälfte
reduzieren.
Das kann für Anwendungen, bei denen man sehr häufig ein spezielles
Polynom auswerten muss, was natürlich in irgendwelchen technisch
-wissenschaftlichen Anwendungen vorkommen kann, dass wir irgendein
Polynom haben, das immer wieder für verschiedene Werte von x
ausgewertet werden muss.
Dann macht es Sinn, da einen gewissen Voraufwand zu betreiben.
Das ist der gewisse Voraufwand für die Berechnung der Alpha-i und
diese Zerlegung.
Und wenn ich die habe, dann kann ich mit Einsparung von n halber
Multiplikation den Rest berechnen, also diese Polynome auswerten.
Ich will Ihnen damit vor allen Dingen zeigen, ich muss immer sehen,
was sind die Informationen, die ich habe, bevor ich meinen Algorithmus
laufen lasse für meinen Anwendungsfall.
Wenn der Anwendungsfall ist ein festes Polynom mit unterschiedlichen
Werten für x auswerten, dann kann ich diese festen Koeffizienten
ausnutzen bei der Formulierung meines Algorithmus.
Wenn ich für jede Anwendung meines Algorithmus mit unterschiedlichen
Koeffizienten rechnen muss und mit einem unterschiedlichen Wert von x,
dann ist das beste das Vornerschema.
Das ist einfach die Aussage.
Gut, also das ist hier dieser Satz, den ich Ihnen dadurch nicht
gezeigt habe, wie dieses allgemeine Verfahren geht, um diese Alpha I
zu bestimmen.
Aber wenn ich mir annehme, wir haben dieses Verfahren, was man also
ausführen kann, das ist ein bisschen mehr Mathematik, was ich hier
nicht machen möchte.
Ich möchte nur zeigen, wenn man diese Information ausnutzen kann, dann
kann ich also in der Hälfte der Multiplikation auskommen.
Das zur Auswertung von Polynomen.
Und es gibt dann auch noch Möglichkeiten, das weiter zu treiben.
Nehmen wir mal an, ich weiß sogar etwas über die Werte von x, für die
ich ein Polynom auswerten muss.
Dann kann ich noch mehr machen.
Also zum Beispiel, wenn ich ein Polynom auswerten muss an den
sogenannten Enten-Einheitswurzeln, was das ist, werden wir gleich
kennenlernen.
Dann kann ich mit noch weniger Operationen auskommen.
Also stellen Sie sich vor, Sie müssen für n verschiedene Werte, x1 bis
xn, müssen Sie ein Polynom auswerten.
Wir hatten jetzt gesehen, jedes Mal brauchen Sie Omega von n
Operationen.
n mal n Operationen heißt n² Operationen.
Wenn ich weiß, ich muss für eine bestimmte Menge von Werten, das sind
jetzt hier die Enten-Einheitswurzeln, irgendwelche x1 bis xn, für die
jetzt mein Polynom auswerten, wenn ich weiß, ich habe eine bestimmte
Menge von unbekannten x, dann kann ich den Algorithmus so
modifizieren, dass ich tatsächlich hier mit n log n arithmetischen
Operationen auskomme insgesamt.
Das heißt, da habe ich wieder Informationen genutzt, in dem Fall über
die Beziehungen zwischen verschiedenen Werten von x, und kann dann
noch mehr machen.
Und das ist einfach das, was ich versuche Ihnen zu vermitteln, bevor
ich einen Algorithmus konstruiere, muss ich mir genau angucken, welche
Informationen stehen mir zur Verfügung vor Ausführung des Algorithmus.
Und die nutze ich aus.
Das ist genauso, wir kommen später noch auf Sortieren, da ist das auch
so, wenn ich etwas weiß von vornherein über die Art der Werte, die
sortiert werden müssen, kann ich deutlich besser sortieren oder
schneller sortieren, als wenn ich nichts weiß.
Und das ist einfach eine Standardgeschichte, die wir uns dort angucken
müssen.
So, jetzt zum nächsten Punkt, Parallelisierung.
Das geht in diesem Fall ganz schnell.
Parallelisierung geht immer schnell, aber in diesem Fall geht auch die
Behandlung des Themas relativ schnell.
Also, wir wollen hier uns angucken, wie kann ich ein Polynom parallel
auswerten.
Und das Problem ist, schauen Sie sich das Horner-Schema an.
Wenn ich also hier mein Horner-Schema betrachte, da habe ich ja hier
so eine Reihe von Klammern.
Dann steht hier a n x plus a n minus 1 mal x und so weiter mal x plus
a 0.
Das ist eine ganz klare Klammerstruktur, die ist inhärent sequentiell.
Da ist völlig klar, wenn ich das nur mit dem Horner-Schema mache, das
kann ich nicht parallelisieren, da muss ich sequentiell durchlaufen.
Das heißt, diese Darstellung vom Horner-Schema so eines Polynoms ist
ungünstig.
Die war optimal für die sequentielle Ausführung.
Für die parallele Ausführung sehen wir, wenn wir das mit dem Schema
machen müssen, können wir nichts parallelisieren.
Dann bleiben wir bei einer Zeit von n.
Also Größenordnung n.
Wenn wir parallelisieren wollen, ist es sinnvoller, ein großes Problem
aufzuteilen in zwei, die vielleicht die halbe Größe haben und dann die
beiden mit der halben Größe vielleicht nebeneinander zu lösen in einem
Schritt.
Dann kann ich dadurch mehr Dinge parallel machen.
Also ich muss irgendwie unabhängige Berechnungen daraus machen.
Das hatten wir schon gesehen bei der Matrix-Multiplikation.
Das Skalarprodukt konnte man über eine Baumstruktur perfekt
parallelisieren.
Dann kamen wir auf Log-n-Operationen für ein Skalarprodukt und Log-n
-Schritte, nicht Operationen, sondern parallele Schritte, während wir
bei der sequentiellen Ausführung n-Schritte brauchen.
Also halbiere ich das Polynom.
Wenn ich ein Polynom halbieren will, muss ich zum Beispiel so
vorgehen, dass ich sage, ich nehme den ersten Teil, klammere dort x
hoch in halbe aus und habe dann also ein Polynom halben Grades und ein
Restpolynom, das hat auch einen halben Grad.
Und wenn ich das jetzt auswerten möchte, dann kann ich natürlich
zunächst mal den Teil auswerten, p in halbe von x.
Ich kann q in halbe von x auswerten, ein anderes Polynom halben
Grades.
Das kann ich parallel machen, die sind völlig unabhängig voneinander.
Und dann muss ich nur das linke Polynom, hier das p, mit x hoch in
halbe multiplizieren.
Das x hoch in halbe kann ich auch parallel zu der Auswertung von den
anderen hier machen, wobei ich das x hoch in halbe natürlich auch
brauche, jeweils in p von in halbe und q von in halbe.
Also das kann ich aber alles im Prinzip parallel hier laufen lassen
und muss halt nur noch hier die eine Multiplikation, die eine Addition
machen.
Das geht in so Größenordnung, beziehungsweise als Rekursionsformel,
die Zeit für die Lösung des Problems der Größe n ist etwa die Zeit, um
Probleme der halben Größe zu lösen.
Das sind hier diese Probleme für p von in halbe und q von in halbe.
Und dann habe ich noch eine Addition und eine Multiplikation zu
machen.
Das heißt, wenn ich mir so eine Formel angucke, dann sieht man sehr
schnell, wenn man so ein bisschen Erfahrung hat damit, wie man mit
solchen Rekurrenzgleichungen umgeht, das sind etwa zwei log n
Schritte.
Wenn Sie mal wieder halbieren, Sie haben pro Ebene nur konstanten
Aufwand.
Die Tiefe des Baumes ist log n, pro Schicht haben Sie konstanten
Aufwand.
Das heißt, Sie haben Größenordnung o log n Aufwand und damit eine
deutliche Reduktion im Zeitaufwand von linear runter auf
logarithmisch.
Das heißt, ich kann es parallelisieren auf eine einfache Art und
Weise.
Ich muss das Polynomen halt einfach so jeweils halbieren und dann
immer so weitermachen und kann dann, habe dadurch unabhängige,
voneinander unabhängige Operationen und kann die halt parallel machen.
Gut, das war alles zur Parallelisierung.
Man könnte auch noch ein bisschen weitere Sachen machen, wenn man
viele Polynome hat, irgendwas mit Pipelining.
Das lasse ich aber weg.
Ich möchte auch von der Thematik her weiterkommen und möchte Ihnen
jetzt ein weiteres Problem noch zeigen, das ich schon kurz angedeutet
habe, nämlich die schnelle Fourier-Transformation.
Warum schnelle Fourier-Transformation?
Das ist ein Problem, das sehr oft auftaucht in technischen
Anwendungen, dass Sie Dinge transformieren müssen.
Da gehe ich im Prinzip in eine Frequenzdarstellung einer Funktion.
Das lasse ich aber völlig raus.
Ich betrachte nicht die allgemeine Fourier-Transformation, sondern die
diskrete Fourier-Transformation und schaue das an für ein
Anwendungsproblem, nämlich das Produkt von zwei Polynomen möchte ich
berechnen.
Das ist das Problem, das ich jetzt als Problem Ihnen darstelle und ich
möchte zeigen, das geht mit dieser schnellen Fourier-Transformation
deutlich schneller, als wenn man das naiv macht.
Wenn ich zwei Polynome multipliziere, dann muss ich irgendwie, also
hier zwei Polynome p und q, dann muss ich ja irgendwie das
Produktpolynom R von x berechnen, das natürlich irgendwelche
Koeffizienten hat, natürlich mehr.
Wenn ich zwei Polynome n-ten Grades habe, hat das Produktpolynom den
Grad 2n.
Das heißt, ich habe dann Koeffizienten c0 bis c2n.
Und jedes ck da drin ist eine Summe von Produkten der Koeffizienten
des Polynoms p und q.
Wenn man also irgendwie diese Koeffizienten a, i, b, i miteinander
multipliziert, entsprechend der Ausmultiplikation eines Polynoms.
Und das kann man sich leicht überlegen, dass das gerade jeweils solche
Summen sind.
Also ich glaube, da brauche ich nicht mit einem Beispiel darauf
einzugehen.
Sie haben von x hoch 2n, das c2n ist gerade an mal bn.
Und von c2n-1 ist es dann natürlich an mal bn-1 plus an-1 mal bn.
Das ist ja klar.
Das c2n-1 ist dann natürlich gerade gleich an mal bn-1 plus an-1 mal
bn.
Das steht hier allgemein natürlich genauso drin.
Wobei es hier etwas allgemein formuliert ist.
Hier steht noch dieses a, i, b, i gleich 0 für j größer n, weil ich
hier bis k gehe.
Ich habe natürlich kein a, n plus 1, a, n plus 2 und so weiter.
Da habe ich in dieser Formel das einfach so erweitert, um das in
dieser Form darstellen zu können.
Sonst wäre diese Formel etwas anders.
Aber das, was da rauskommt, ist einfach z.B.
c2n-1 ist dann genau diese Summe.
c2n-2 hat entsprechend noch mehr Kombinationen von a, i, b, i.
Das ist ein etwas längerer Term.
Und der Term cn ist also eine Summe von n Termen, von n Produkten.
Das heißt, diese Koeffizienten zu berechnen ist ein relativ großer
Aufwand.
Und Sie brauchen, wenn Sie das naiv machen, eine quadratische Anzahl
von Operationen.
Sie haben also jeweils hier Terme zu berechnen, in denen so über den
Daumen Größenordnung n Operationen vorkommen.
Und damit haben Sie insgesamt n Quadrat Operationen.
Und das ist die Standardüberlegung, das so zu machen.
Alternativ versucht man jetzt, eine andere Lösung zu finden.
Und dazu wird jetzt ein klassischer weiterer Ansatz verwendet, um
Probleme anders zu bearbeiten, als man das naiv macht.
Was ist der wesentliche Punkt in diesem Fall?
Ich transformiere meine Darstellung des Polynoms.
Das, was wir hier oben gemacht haben, ist eine Darstellung der
Polynome über Koeffizienten.
Ich habe die ja so gegeben, als Summe aixoi und Summe bixoi.
Das heißt gegeben über die Koeffizienten.
Ich kann aber auch ein Polynom, oder die Funktion, die dadurch
repräsentiert ist, eindeutig charakterisieren durch Werte an einer
Reihe von Punkten.
In diesem Fall mache ich einfach eine Wertedarstellung.
Ich kann es eindeutig durch die Werte an n plus 1 Punkten darstellen.
Das ist die Wertedarstellung eines Polynoms.
Das ist Standardmathematik.
Jetzt kann ich natürlich noch mehr Punkte nehmen.
Ich stelle es einfach da an 2n plus 1 Punkten von x0, px0 bis x2n,
px2n.
Irgendwelche Werte x0 bis x2n nehme ich mir her und berechne dazu
jeweils das p von x0 bis p von x2n.
Ich mache das gleiche mit dem Polynom q.
Und jetzt kann ich daraus ganz einfach eine Wertedarstellung
berechnen, der Summe der beiden Polynome, für diese Argumente x0 bis
x2n.
Ich brauche nämlich nur, um das Rx0 zu berechnen, um irgend so ein RxI
zu berechnen.
Also RxI ist ja gerade einfach gleich p von xI plus q von xI.
Das ist ja einfach.
Das heißt, wenn ich diese Wertedarstellung habe, der beiden Polynome p
und q, dann kann ich die Wertedarstellung des Produktpolynoms mit n
Additionen berechnen.
Äh, Quatsch.
Nein, Entschuldigung.
Multiplikation natürlich.
Entschuldigung, das war nicht...
Es geht nicht um Addition, das wäre einfach.
Multiplikation der Polynomen.
Also es geht um die Multiplikation, ich kann also die Werte des
Produktpolynoms durch Multiplikation der Einzelwerte berechnen, denn
es ist doch das R von xI gerade das p von xI mal q von xI.
Ja, selbstverständlich hier.
Multiplikation.
So, dann habe ich also mit Aufwand n, das ist diese Transformation
hier als O3, Operation 3 angegeben, die Wertedarstellung meines
Produktpolynoms.
Und nun mache ich eine nächste Operation.
Ich transformiere die Wertedarstellung zurück auf die
Koeffizientendarstellung meines Produktpolynoms und habe dann das, was
hier, dieser Weg hier über diese Operation war hier oben angedeutet,
Standardanwendung für Koeffizientendarstellung, da habe ich einen
quadratischen Aufwand.
Und die Frage, jetzt habe ich hier auf dieser Seite, dieser Aufwand
hier runter, dieser Aufwand hat einen Aufwand von O von n, das habe
ich Ihnen gerade angedeutet.
Das sind diese 2n plus 1 Multiplikation.
Das ist die Frage, wie groß ist der Aufwand für O1 und O4.
Und das Interessante ist, also dieses O2 wissen wir hier oben, das ist
der Standardansatz, quadratischer Aufwand.
Das O3 ist lineare Aufwand, 2n plus 1 Multiplikation.
Und wenn ich O1 und O4, also diese beiden Transformationen hier, O1
und O4 mit einer schnellen Fourier-Transformation mache, dann habe ich
jeweils einen Aufwand von n log n.
Und dann ist der Gesamtaufwand, hier einmal rumzulaufen, auch nur n
log n.
Das ist also jetzt das, warum ich Ihnen die schnelle Fourier
-Transformation zeige.
Eine Möglichkeit, wie ich also dadurch indirekt den Aufwand für die
Berechnung des Produkts von 2 Polynomen reduzieren kann von n² auf n
log n.
Und die schnelle Fourier-Transformation ist also da der wesentliche
Punkt.
Diese Transformation von Koeffizientendarstellung in Wertedarstellung.
Und jetzt die Frage, wie kriegt man das hin?
Denn naiv ist es ja so, wenn ich ein Polynom, das in
Koeffizientendarstellung gegeben ist, wenn ich das auswerten will an
diesen Stellen x0 bis x2n, dann muss ich ja 2n plus 1 mal ein Polynom
auswerten.
Und wir wissen, ich brauche für jede Polynom-Auswertung Größenordnung
n arithmetische Operation.
Wir hatten das zwar reduziert auf n½, aber es ist immer noch
Größenordnung n.
Und das heißt, ich habe hier insgesamt, wenn ich das naiv machen
würde, nacheinander, hätte ich einen Aufwand von n².
Die Behauptung ist, in der schnellen Fourier-Transformation geht das
mit n log n.
Und das heißt, das hatte ich schon angedeutet vorhin, es geht nur mit
n log n, weil ich deutlich mehr Informationen habe bei der schnellen
Fourier -Transformation über die Werte x0 bis x2n.
Wenn ich also da spezielle Werte nehmen kann, mit besonderen
Eigenschaften, dann kann ich diesen Aufwand von n² auf n log n
reduzieren.
Und wie man das jetzt macht, kommt also auf den nächsten Folien.
Das ist also jetzt die diskrete Fourier-Transformation.
Da geht es um die Auswertung eines Polynoms an geeignet gewählten
Stellen, nämlich den n-ten Einheitswurzel.
Diese schnelle Fourier-Transformation ist eine klassische
algorithmische Struktur, die man an vielen Stellen einsetzt.
Deswegen ist es sinnvoll, sich das einmal anzugucken.
Dazu muss man sich angucken, was sind diese speziellen Stellen.
Die speziellen Stellen sind also die n-ten Einheitswurzeln.
Der n-te Einheitswurzel ist eine Nullstelle des Polynoms x hoch n
minus 1.
Das heißt, ich schaue mir einen Wert x an, sodass x hoch n minus 1
gleich 0 ist.
Alle Werte, für die x hoch n minus 1 gleich 0 ist, sind n-te
Einheitswurzeln.
Eine solche n-te Einheitswurzel Omega heißt primitiv, genau da, wenn
jedes Omega hoch j ungleich 1 ist.
Es ist natürlich klar, der Wert 1 ist da immer eine Einheitswurzel.
Aber der ist trivial.
Es gibt halt Werte ungleich 1, also minus 1 zum Beispiel.
Minus 1 Quadrat, wenn ich x Quadrat minus 1 betrachte, da ist minus 1
ein Wert, der ist ungleich 1.
Aber minus 1 zum Quadrat ist 1, also ist x Quadrat minus 1 gleich 0.
Und eine solche n-te Einheitswurzel heißt primitiv, wenn ich also alle
anderen im Prinzip daraus bekommen kann.
Es ist also so, wenn Omega eine primitive n-te Einheitswurzel ist,
wenn also alle Omega hoch j ungleich 1 sind für j kleiner als n, dann
ist die Menge dieser Potenzen von Omega die Menge aller n-ten
Einheitswurzeln.
Habe ich damit alle.
Für x Quadrat minus 1 ist es so, dass gerade minus 1.
Also wir haben hier die zweiten Einheitswurzeln gerade minus 1 und 1.
Hier steht ja für alle j aus n minus 1 gilt Omega hoch j ungleich 1.
Minus 1 hoch 1 ist ja gerade minus 1, also ist es ungleich 1.
Minus 1 hoch 2 ist 1, aber das ist ja auch in dem Fall bereits n.
Also minus 1 und 1 sind die zweiten Einheitswurzeln.
Die vierten Einheitswurzeln, da müsste ich dann schon auf den
komplexen Zahlenkörper ausweichen.
Da habe ich dann im komplexen Zahlenbereich also i als primitive
Einheitswurzel, als primitive vierte Einheitswurzel, i Quadrat ist
minus 1, i hoch 3 ist minus i und i hoch 4 natürlich 1.
Damit habe ich also diese vierten Einheitswurzeln gerade vier Stück.
Entsprechend die achten Einheitswurzeln wäre dann gerade die Wurzel
aus i und so weiter.
Kann ich im komplexen Zahlenbereich alles machen oder auch in
irgendwelchen endlichen Körpern.
Es gibt eben auch endliche Körper, in denen ich das so betrachten
kann.
Die Ende der Einheitswurzeln existieren.
Aber man kann auch da einfach mit komplexen Zahlen das machen.
So, das sind jetzt hier solche Enden Einheitswurzeln.
Und jetzt schaue ich mir die Eigenschaften dieser Enden
Einheitswurzeln an, weil ich sagte ja, ich möchte jetzt die Motion
ausnutzen, um meine Polynomauswertung zu beschleunigen.
Die Eigenschaften, die ich hier habe, sind jetzt hier
zusammengestellt.
Ich hoffe, Sie können das einigermaßen lesen.
Sie haben das auch ausgedruckt vor sich wahrscheinlich.
Also, wenn ich eine Ende Einheitswurzel nehme und die zur enthalbten
Potenz erhebe, dann ist das natürlich gerade Minus 1.
Das ist klar.
Das ist ja Omega hoch Enthalbe, weil Omega hoch Enthalbe ist natürlich
gerade 1.
Also das muss ja ungleich 1 sein und deswegen ist es gerade in dem
Fall die Minus 1.
Kann nicht anders sein.
Wenn das aber so ist, wenn das Omega hoch Enthalbe gleich Minus 1 ist,
dann ist natürlich Omega hoch Enthalbe plus irgendein i gleich Minus
Omega hoch i.
Omega hoch Enthalbe mal Omega hoch i und das ist gleich Minus 1 mal
Omega hoch i.
Das ist direkte Folgerung aus dem, was da oben drüber stand.
Außerdem ist Omega Quadrat, also das Omega ist eine primitive Ende
Einheitswurzel, Omega Quadrat ist dann gerade eine primitive
Einheitswurzel für X hoch Enthalbe Minus 1.
Ja, weil ich ja aus Omega Quadrat, wenn ich da von Potenz nehme, sind
das alles gerade Wurzeln für X hoch Enthalbe.
Und dann ist noch eine Eigenschaft, die man sich auch überlegen kann,
wenn ich so ein Polynom auswerte für alle Enteneinheitswurzeln, also
A0 bis An-1, jetzt gehe ich hier nur bis n-1, jetzt habe ich also hier
n Einheitswurzeln, habe ein Polynom n-ersten Grades und dann ist das,
wenn ich mir diese Werte angucke, für alle Enteneinheitswurzeln, dann
kommen hier Werte Y0 bis Yn-1 raus und das ist gerade diese
Vektormatrixmultiplikation, A0 bis An-1 mal zum Beispiel hier, wenn
wir diese Spalte hernehmen, da habe ich gerade das für den Wert Omega
ausgerechnet.
Das wäre also dann im Prinzip P von Omega.
Das hier wäre P von Omega Quadrat.
Das wäre hier hinten dann P von Omega hoch n-1 und so weiter.
Das heißt, ich hätte dann, und hier vorne die erste Spalte, das ist P
von Omega hoch 0.
Omega hoch 0 ist ja 1, deswegen steht hier nur 1.
Also das ist einfach eine andere Darstellung und das Interessante ist,
wenn man sich das so aufschreibt, die inverse Transformation, also
jetzt zurückzugehen von der Wertedarstellung, dieser Y0 bis Yn-1,
zurück auf die Koeffizientendarstellung, hat genau die gleiche
Struktur.
Kann man sich ausrechnen, wenn ich diese Werte hier reinschreibe, die
Omega -1, Omega-2 bis Omega-n-1 und so weiter, hier gerade die
negativen Exponenten reinschreibe, und hier vorne da 1 durch n mal
diesen Werten, dann gibt dieser Ausdruck gerade genau meinen
ursprünglichen A0 bis An-1 wieder.
Das ist eine Eigenschaft, die ich Ihnen jetzt nicht beweise, kann man
sich ausrechnen, können Sie nachsehen, das soll einfach nur andeuten
oder zeigen, dass sowohl die Überführung von Koeffizientendarstellung
in Wertedarstellung als auch die Rückrichtung von Wertedarstellung in
Koeffizientendarstellung eine schnelle Fourier-Transformation ist.
Das ist der wesentliche Punkt hierbei.
Ich kann also, wenn ich ein Schema habe für diese Fourier
-Transformation in der einen Richtung, kann ich sie in der anderen
Richtung auch sofort ausführen.
Das ist das, was ich hiermit andeuten wollte.
Das heißt, ich kümmere mich nur um die eine Richtung, die andere
Richtung ist eine einfache Variante davon.
Und was ich ausnutzen möchte, vor allen Dingen später, ist diese
Eigenschaft hier oben, die hier angedeutet sind, vor allen Dingen das,
was hier steht, dass Omega hoch n halbe plus i gerade gleich minus
Omega hoch i ist.
Das heißt, ich brauche nur die Hälfte der primitiven Einheitswurzeln
von Omega hoch 1 bis Omega hoch n halbe minus 1 zu berechnen.
Und dann habe ich die anderen einfach durch Negation derjenigen, die
ich gerade vorher berechnet habe.
Das ist also minus Omega hoch i.
Das heißt, ich muss nur die Hälfte dieser Potenzen berechnen.
Und das ist das, was man jetzt macht.
Ich zeichne diese Folie jetzt einfach kurz schon mal auf.
Wir werden uns das nächste Mal nochmal genauer angucken.
Was ich also mache, ist, ich nutze diese Eigenschaft aus, die auf der
vorigen Folie stand.
Das heißt, ich teile einfach mein Polynom a0 bis a n minus 1 x n minus
1, das ich an n Stellen auswerten möchte, in zwei Polynome auf, p von
x, pg von x Quadrat und pu von x Quadrat.
Das sind gerade die Polynome mit den geraden Koeffizienten, deswegen
pg, und den ungeraden Koeffizienten, das ist pu.
Also pg ist gerade a0 plus a2 x Quadrat plus a4 x hoch 4 plus a n
minus 2 x hoch n minus 2.
Das ist ein pg von x Quadrat.
Hier stehen einfach die Terme mit den geraden Koeffizienten aus meinem
Polynom p.
Und das ist jetzt ein Polynom, das nur noch halb so viele
Koeffizienten hat und dann von x Quadrat.
Und die ungeraden kann ich genauso machen.
Das ist gerade a1 plus a3 x Quadrat und so weiter.
Jetzt sehen Sie, da stimmen aber die Koeffizienten und die Potenzen
von x nicht richtig.
Es steht a3 x Quadrat.
Ich muss also, um das p von x daraus zu bestimmen, das pg von x
Quadrat mir angucken, das berechnen.
Ich muss das pu von x Quadrat berechnen und muss das noch einmal mit x
modifizieren.
Das wäre übrigens ein anderer Ansatz, um das, was wir vorhin gemacht
haben, Parallelisierung der Polynomauswertung, kann man auch auf diese
Art und Weise machen.
Eine Aufteilung meines Polynoms.
Aber jetzt habe ich also das so gemacht.
Jetzt habe ich also zwei Polynome, die ich für x Quadrat auswerten
muss.
Und jetzt kommt der wesentliche Punkt.
Wenn ich hier x Quadrat betrachte, dann weiß ich, wenn ich eine
primitive N der Einheitswurzel habe, ist Omega Quadrat eine primitive
N -Halb der Einheitswurzel.
Das heißt, ich habe...
Das hier betrachte ich praktisch dann für N-Halb der Einheitswurzeln
und so weiter.
Das heißt, was ich mache ist, ich berechne rekursiv die Werte für Pg
und für Pu für alle N-Halb der Einheitswurzeln.
Ich habe meine Einheitswurzel hier oben, wenn ich betrachte, möchte
ich die Auswertung machen für meine Einheitswurzel Omega.
Das ist die N der Einheitswurzel.
Für Pg und Pu kann ich das für die N-Halb der Einheitswurzeln machen.
Das mache ich rekursiv.
Die werden genauso aufgeteilt.
Und wenn ich diese Werte habe, dann berechne ich mein P von X.
Das muss ich an diesen N-Stellen berechnen.
Für Omega hoch 0 bis Omega hoch N-1.
Omega hoch 0 ist ja gerade 1.
So, und das ist das immer genau mit dem Schema hier oben.
Das ist das Pg von Omega hoch 0 plus Pu von Omega hoch 0.
Das ist ja schon gegeben aus diesem Schritt.
Und dann muss ich das P Omega von 1 berechnen.
Das ist das Pg von Omega quadrat plus Pu von Omega quadrat mal Omega.
Und so weiter bis P von Omega in halbe minus 1.
Das ist gleich P gerade von Omega hoch in halbe plus Pu von Omega hoch
in halbe.
Äh, nicht in halbe, Entschuldigung.
In N-2 natürlich.
In halbe minus 1 zum Quadrat.
Also, ich muss das X-Quadrat betrachten.
Omega hoch in halbe minus 1 zum Quadrat ist gerade gleich Omega hoch N
-2.
Und das hier ebenso.
Omega hoch N-2 mal Omega hoch in halbe minus 1.
Die Werte hier habe ich schon gegeben aus dem rekursiven Schritt.
Und jetzt kommt hier Omega hoch in halbe.
Omega hoch in halbe ist Omega hoch... ja, das ist das Gleiche wie
Omega hoch 0 minus Pu mal Omega hoch 0.
Jetzt kommt das Gleiche hier nochmal wieder.
Und, ähm...
Ich habe...
P Omega hoch in halbe plus 1.
Beweise ich, dass es...
Also, ich brauche ja nur Omega hoch in halbe zum Quadrat.
Warum steht hier Omega hoch 0?
Hier steht Omega hoch in halbe mal Omega hoch in halbe.
Das ist Omega hoch N.
Omega hoch N ist 1.
Ist das Gleiche wie Omega hoch 0.
Ist auch 1.
Ja, deswegen steht hier Omega hoch 0.
Dann habe ich hier Omega hoch in halbe plus 1.
Omega hoch in halbe plus 1 ist aber gerade, das wissen wir, Omega hoch
1.
Das stand auf der vorigen Folie.
Das hier war Omega hoch in halbe plus i ist gleich minus Omega hoch i.
So, und wenn ich das Ganze, wenn ich hier das quadriere, das Omega
hoch in halbe plus 1, habe ich gerade hier praktisch, das ist gleich
Omega Quadrat.
Und jetzt muss ich eben hier modifizieren, eigentlich mit Omega hoch
in halbe plus 1.
Das ist aber minus Omega.
Und genauso habe ich jetzt also hier einfach nur zu modifizieren mit
Omega hoch in halbe minus 1.
Und Sie sehen, dass das, was hier steht, hier unten, das stand hier
oben schon mal.
Und ich brauche diese Produkte, die hier stehen, nicht nochmal zu
berechnen.
Ich habe hier jeweils eine Multiplikation, eine Addition zu machen.
In dem oberen Teil.
Hier unten muss ich nur noch subtrahieren.
Und die Werte, die ich subtrahiere jeweils, das sind die gleiche wie
die, die ich hier oben berechnet habe, die kann ich nochmal verwenden.
Das heißt, ich habe hier für diesen Schritt nur, das steht jetzt, da
steht's, ich habe nur in halbe minus 1 Multiplikationen zu machen und
n Additionen.
Und dadurch bekomme ich eine drastische Reduktion in dem Aufwand.
Ich habe die Anzahl der Multiplikationen rekursiv in jeder Ebene um
die Hälfte reduziert.
Und das führt dann insgesamt zu einem Aufwand von Größenordnung n mal
log n.
Da gehen wir nächstes Mal noch kurz drauf ein.
Das habe ich 5 Minuten überzogen, habe aber auch nicht so spät
angefangen.
Einigermaßen ein Kompromiss bin ich eingegangen.
Vielen Dank für die Aufmerksamkeit.
War ein bisschen viel Mathematik heute, aber ich denke, Sie kommen
damit schon zurecht.
Vielen Dank.