WEBVTT

00:04.260 --> 00:05.120
Schönen Tag!

00:05.200 --> 00:11.060
Ich begrüße Sie zur Vorlesung effizienter Algorithmen und wiederhole

00:11.060 --> 00:13.140
wie üblich kurz, was wir gemacht haben letztes Mal.

00:13.800 --> 00:17.040
Aus irgendeinem Grund sieht man den Bildschirm.

00:19.160 --> 00:23.980
So, wir haben uns letztes Mal beschäftigt mit algebraischen Problemen

00:23.980 --> 00:29.660
und haben uns Matrix-Multiplikationen angeschaut.

00:29.660 --> 00:31.240
Da sind wir schon ziemlich weit gekommen.

00:31.480 --> 00:34.320
Wir hatten gesehen, wie man das normalerweise macht mit der

00:34.320 --> 00:35.040
Schulmethode.

00:35.840 --> 00:40.540
Wir hatten uns die Kosten...

00:40.540 --> 00:42.020
Da habe ich aber jetzt die falsche Version.

00:42.340 --> 00:45.640
Ich will gar nicht diese Datei haben, sondern die andere Datei.

00:45.720 --> 00:48.020
Kleinen Augenblick...

00:48.940 --> 00:51.320
Die möchte ich speichern.

00:55.520 --> 00:59.460
Also, wir hatten uns letztes Mal mit den Matrix-Multiplikationen

00:59.460 --> 01:02.960
beschäftigt und ich hatte Ihnen dazu auch etwas erzählt zu den

01:02.960 --> 01:03.880
Datenstrukturen.

01:04.620 --> 01:08.460
Wir hatten die Schulmethode angeschaut mit den üblichen

01:08.460 --> 01:11.140
Größenordnungen n hoch 3 Zugriffen.

01:11.260 --> 01:14.000
Wir hatten uns ein bisschen genauer beschäftigt mit den Zugriffen auf

01:14.000 --> 01:16.800
die Matrix-Komponenten festgestellt, dass es doch relativ viele

01:16.800 --> 01:21.440
Operationen geben kann, je nachdem, welche Datenstruktur man hat.

01:21.440 --> 01:25.820
Man hat unterschiedliche Anzahl von Operationen, die man durchaus auch

01:25.820 --> 01:26.700
berücksichtigen muss.

01:26.780 --> 01:29.280
Dann haben wir das Verfahren von Binograd betrachtet, nur als

01:29.280 --> 01:33.340
Beispiel, um zu sehen, was man alles so machen kann.

01:34.920 --> 01:39.600
Zunächst naheliegende Umsetzungen zur Berechnung einer Formel

01:39.600 --> 01:44.300
eigentlich gar nicht notwendigerweise die einzige Möglichkeit

01:44.300 --> 01:46.600
darstellen, einen Wert zu berechnen, sondern dass es viele

01:46.600 --> 01:48.120
verschiedene Möglichkeiten dafür gibt.

01:49.520 --> 01:54.540
Hier hatten wir gesehen, dass man durch eine etwas andere Darstellung

01:54.540 --> 01:58.400
erreichen kann, dass in diesem Fall die Zahl der Multiplikationen

01:58.400 --> 01:59.320
reduziert wird.

01:59.820 --> 02:03.280
Wir hatten dann einen ganz anderen Ansatz betrachtet, den Weiden

02:03.280 --> 02:04.700
-Conker -Ansatz von Straßen.

02:05.380 --> 02:08.660
Auch das eben nicht offensichtlich, dass man das so macht, aber die

02:08.660 --> 02:11.580
Idee ist eben genial.

02:12.280 --> 02:15.100
Es sind viele Leute vorher nicht darauf gekommen, dass man bei diesen

02:15.100 --> 02:16.760
numerischen Problemen auch so vorgeht.

02:16.760 --> 02:19.160
In der Informatik bei den kombinatorischen Problemen macht man das

02:19.160 --> 02:23.900
selbstverständlich, aber in der numerischen Mathematik hat man die

02:23.900 --> 02:26.140
Weiden -Conker-Ansätze eigentlich nie so richtig betrachtet.

02:26.520 --> 02:27.580
Der Straßen hat es gemacht.

02:28.080 --> 02:32.020
Er hat eben festgestellt, dass man mit diesem sehr allgemeinen Ansatz

02:32.020 --> 02:36.260
über so ein Standardverfahren für eine feste Matrixgröße in der Lage

02:36.260 --> 02:44.120
ist, die Anzahl der Operationen wirklich drastisch zu reduzieren,

02:44.120 --> 02:46.460
nämlich dass man dadurch runterkommen kann.

02:46.620 --> 02:52.240
Das war ja der wesentliche Satz auf N hoch.

02:52.360 --> 02:56.980
Und dann stand da so ein Ausdruck, Logarithmus zu Basis K, der Anzahl

02:56.980 --> 03:02.020
der Multiplikationen, die in diesem Verfahren für diese Standardgröße

03:02.020 --> 03:04.360
für K-Kreuz-K-Matrizen gebraucht werden.

03:04.800 --> 03:08.820
Und für den schönen Fall, dass man 2-Kreuz-2-Matrizen hat, ganz

03:08.820 --> 03:14.580
einfach kann man durch die Reduktion von 8 auf 7 Multiplikationen für

03:14.580 --> 03:21.220
ein Matrixprodukt dann auf den Wert 2.81 im Exponenten, also eine

03:21.220 --> 03:26.740
methodische Verbesserung gegenüber N hoch 3 der Schulmethode.

03:27.500 --> 03:29.760
Und wenn man das dann noch ein bisschen weiter verbessert hat, kann

03:29.760 --> 03:35.660
man tatsächlich für Problemgrößen ab etwa N gleich 40 bereits zu

03:35.660 --> 03:39.160
deutlich besseren Laufzeiten dieses Verfahrens.

03:39.640 --> 03:46.380
Was eben zeigt, dass man hier wirklich ein gutes Verfahren gefunden

03:46.380 --> 03:46.700
hat.

03:47.120 --> 03:50.780
Es ist wichtig zu sehen, die Konstanten, die dabei eine Rolle spielen,

03:51.960 --> 03:55.560
führen dazu, dass man für kleinere Problemgrößen mit Straßen nicht

03:55.560 --> 03:57.960
unbedingt besser liegt, aber eben für große Problemgrößen.

03:58.280 --> 04:02.660
Je größer die Matrizen werden, desto höher wird der Zeitgewinn, den

04:02.660 --> 04:03.000
man hat.

04:03.000 --> 04:09.700
Und bei einem Wachstum von N hoch 3, da gehen die Anzahl Operationen

04:09.700 --> 04:12.300
halt wirklich sehr, sehr stark hoch mit wachsendem N.

04:12.460 --> 04:14.060
Da muss man sich im Klaren sein.

04:14.160 --> 04:17.780
Wenn man dann im Exponenten runtergehen kann, dann hat das wirklich

04:17.780 --> 04:19.260
sehr, sehr große Auswirkungen.

04:20.520 --> 04:23.260
Dann hatten wir noch kurz gesehen, dass man auch andere Operationen

04:23.260 --> 04:26.980
damit schnell hinbekommen kann, nämlich Matrix-Inversion und damit

04:26.980 --> 04:27.820
auch die...

04:28.400 --> 04:30.380
Ich glaube, das Ding stört hier etwas.

04:41.100 --> 04:44.940
Also damit, wenn man Inversionen und Matrix-Multiplikationen mit

04:44.940 --> 04:47.220
diesem Aufwand hinbekommen kann, dann natürlich auch Lösungen von

04:47.220 --> 04:48.120
Gleichungssystemen.

04:48.120 --> 04:52.680
Und damit war das wichtige Ergebnis, und das war eben der Titel der

04:52.680 --> 04:56.520
Originalarbeit, dass die Gauss'sche Elimination nicht optimal ist.

04:57.060 --> 05:00.160
Und das war, hatte ich schon gesagt, für Mathematiker ein

05:00.160 --> 05:05.580
erstaunliches Ergebnis und hat dazu geführt, dass Algorithmik

05:05.580 --> 05:08.220
tatsächlich als interessant angesehen wurde.

05:08.460 --> 05:11.400
Jetzt kommen wir zu dem nächsten Punkt.

05:11.400 --> 05:17.340
Ich hatte ja gesagt, wir fahren uns alle Algorithmen nicht nur an in

05:17.340 --> 05:22.280
Bezug auf sequenzielle Ausführungen, sondern auch in Bezug auf

05:22.280 --> 05:23.360
parallele Ausführungen.

05:23.460 --> 05:27.680
Ich hatte Ihnen schon in den einführenden Stunden etwas erzählt über

05:27.680 --> 05:32.120
Möglichkeiten, das auf der PRAM zu machen, beziehungsweise eben ganz

05:32.120 --> 05:32.620
parallel.

05:33.420 --> 05:34.820
Jetzt machen wir das mal ein bisschen anders.

05:35.600 --> 05:40.000
Also wir wissen, das hatte ich schon gesagt, auf PRAM geht es mit O

05:40.000 --> 05:44.500
von Log N Schritten, mit N hoch 3 durch Log N Prozessoren.

05:44.600 --> 05:50.620
Das war ja im Prinzip die Darstellung, bei der wir die einzelnen

05:50.620 --> 05:52.500
Multiplikationen gemacht haben.

05:53.300 --> 05:56.340
Also hier einzelne Multiplikationen, und dann haben wir die

05:56.340 --> 06:00.780
zusammengefügt und konnten auf die Art und Weise, also hier waren es

06:00.780 --> 06:04.840
Multiplikationen, hier waren es Additionen, und dadurch konnten wir

06:04.840 --> 06:11.520
über diesen Baum in Log N parallelen Schritten tatsächlich die

06:11.520 --> 06:15.200
Matrixmultiplikationen erledigen, mit N hoch 3 durch Log N

06:15.200 --> 06:15.880
Prozessoren.

06:16.020 --> 06:16.960
Relativ hoher Aufwand.

06:18.220 --> 06:22.380
Das ist klar, irgendwo müssen ja diese Operationen, die erforderlich

06:22.380 --> 06:23.800
sind, auch ausgeführt werden.

06:24.760 --> 06:27.800
Aber man kann eben die Zeit, die Anzahl der Zeitschritte, die man

06:27.800 --> 06:31.040
braucht, durch Parallelverarbeitung deutlich reduzieren.

06:31.740 --> 06:34.520
Und jetzt kann man das Ganze aber auch auf anderen Feldern machen.

06:34.620 --> 06:35.740
Auch das hatte ich Ihnen schon mal gezeigt.

06:35.800 --> 06:43.600
Ich hatte Ihnen dieses hexadiagonale Feld gezeigt.

06:44.040 --> 06:49.500
Da hatten wir dieses Feld, um Bandmatrizen zu modifizieren.

06:49.500 --> 06:52.620
Jetzt schauen wir uns ein anderes Feld an, ein einfaches

06:52.620 --> 06:53.900
zweidimensionales Feld.

06:55.100 --> 07:02.880
N mal N Prozessoren, für ein N mal N Matrizenprodukt, sehr einfach zu

07:02.880 --> 07:03.160
machen.

07:04.860 --> 07:12.840
Also hier ist angedeutet, dass die Daten der beiden Matrizen in

07:12.840 --> 07:16.120
zeitlich etwas versetzter Form hier eingegeben werden sollen.

07:16.120 --> 07:24.040
Hier ist angedeutet, dass also zur Zeit die Elemente A14 und B41

07:24.040 --> 07:29.000
praktisch an den Eingängen für das Element oben 1A1 sind.

07:29.080 --> 07:32.680
Wenn man das hier mit 1A1 nummeriert, nehmen wir an, dass links oben

07:32.680 --> 07:35.260
das Komponente 1A1 ist.

07:36.560 --> 07:39.880
Und rechts dann hier die 1N und so weiter.

07:40.040 --> 07:42.220
Also zeilenweise durchnummeriert die Prozessorelemente.

07:42.220 --> 07:44.900
Obwohl die Nummerierung der Prozessorelemente keine große Rolle

07:44.900 --> 07:45.180
spielt.

07:45.240 --> 07:48.280
Das kann man ja immer benennen, wie man will.

07:48.720 --> 07:51.380
Im ersten Schritt würden also jetzt diese beiden Elemente dort

07:51.380 --> 07:53.600
eingegeben werden, würden multipliziert werden.

07:54.500 --> 07:59.540
Und dann sieht man schon, stehen an diesem jetzt als nächstes die

07:59.540 --> 08:03.680
beiden Elemente A13 und B31 zur Verfügung.

08:04.400 --> 08:08.860
Könnten also aufaddiert werden auf das Produkt von A14 und B41.

08:09.560 --> 08:13.900
Und an den anderen beiden, jetzt hier, da, diese beiden Elemente, da

08:13.900 --> 08:16.820
stehen jetzt die Elemente A24 und B42.

08:18.500 --> 08:21.280
Beziehungsweise, also von außen.

08:21.880 --> 08:26.700
Und von links hier oben sieht man, da kommt jetzt das Element, wenn

08:26.700 --> 08:33.120
das A weitergeschoben wird, wird also A14 mit B42 kombiniert werden.

08:33.260 --> 08:38.700
Und hier unten würde A24 kombiniert werden mit B41.

08:38.940 --> 08:45.180
Das heißt, da werden dann die Elemente vermutlich C21 und C12 in

08:45.180 --> 08:46.800
diesen beiden gerade berechnet.

08:46.980 --> 08:53.780
Also hier unten in diesem das C21 und hier oben das C12.

08:53.780 --> 08:56.340
So läuft das halt jetzt sukzessive weiter.

08:56.460 --> 08:58.100
Die Matrizen werden hier durchgeschoben.

08:59.000 --> 09:00.800
Und jetzt ist hier oben das Feld leer.

09:00.900 --> 09:04.740
Das heißt, hier steht in diesem Augenblick das C11 fertig berechnet

09:04.740 --> 09:05.060
drin.

09:05.820 --> 09:07.300
Und das geht jetzt so weiter.

09:08.380 --> 09:11.400
Und wenn die Matrizen hier ganz durchgelaufen sind, dann haben wir,

09:11.520 --> 09:15.160
das ist nicht bis zum Ende durchgeführt hier, dann haben wir also in

09:15.160 --> 09:19.840
diesen Feldern, die jetzt leer sind, jeweils die Cij fertig berechnet.

09:20.360 --> 09:24.520
Die Zeit, um das Ganze auszuführen, kann man sich einfach ausrechnen.

09:24.580 --> 09:26.900
Wie lange dauert das, bis die Daten hier durchgelaufen sind?

09:27.540 --> 09:29.160
Die werden eingegeben.

09:29.860 --> 09:33.160
Das sind N-Takte, damit sie hier bis ganz nach rechts gelaufen sind.

09:33.760 --> 09:40.200
Dann muss ich noch hier runterlaufen.

09:41.200 --> 09:52.460
Und das sind jetzt 2 N-1-Takte und dann fehlen noch N-1-Takte.

09:52.600 --> 09:56.160
Ich könnte es auch anders sagen können, bis das letzte Element, das

09:56.160 --> 10:02.000
A11, ganz links eingegeben wurde.

10:04.360 --> 10:10.620
Im Takt N wird das Element A11 eingegeben, links oben.

10:11.140 --> 10:14.440
Dann braucht man N-1-Takte, um bis ganz nach rechts zu kommen und

10:14.440 --> 10:18.220
nochmal N-1-Takte, um ganz nach unten zu kommen mit den entsprechenden

10:18.220 --> 10:20.100
anderen Werten.

10:20.180 --> 10:25.540
Also bis das A41 dann ganz unten rechts da ist.

10:25.720 --> 10:29.760
Und das sind dann insgesamt gerade die 3 N-2-Takte.

10:30.860 --> 10:37.980
Nach 3 N-2-Takten hat man also die Elemente C, I, J in diesen

10:37.980 --> 10:39.240
Prozessorelementen drin stehen.

10:39.380 --> 10:42.740
Also hier das C12, hier das C21 und so weiter.

10:43.760 --> 10:46.560
Wenn man sie ausgeben wollte, wenn man sie draußen zur Verfügung haben

10:46.560 --> 10:50.060
wollte, müsste man sie natürlich noch irgendwie dort raus bewegen.

10:51.400 --> 10:54.120
Dazu könnte man sie alle irgendwie nach rechts rausschieben oder nach

10:54.120 --> 10:55.100
oben oder nach links.

10:55.660 --> 10:58.620
Dann ist es nicht klar, dass man direkt zugreifen kann auf die

10:58.620 --> 10:59.860
einzelnen Prozessorelemente.

11:00.540 --> 11:04.360
Wenn man sie rausschieben müsste, wären das nochmal mindestens N

11:04.360 --> 11:06.140
-Takte, um sie alle auszulesen.

11:06.780 --> 11:11.120
Dann hätten wir also 4N-2 als Zeit, wenn wir tatsächlich alle Elemente

11:11.120 --> 11:12.220
ausgegeben haben wollen.

11:13.540 --> 11:17.420
Dann habe ich hier angegeben, S von N, Sie erinnern sich, S von N, das

11:17.420 --> 11:20.420
war der Zeitgewinn, Speedup.

11:20.420 --> 11:28.380
Zeitgewinn war schnellste sequentielle Zeit bzw.

11:28.400 --> 11:32.840
die optimale sequentielle Zeit durch Zeit des parallelen Algorithmus.

11:33.280 --> 11:37.620
Zeit des parallelen Algorithmus ist Größenordnung N, also linear.

11:39.020 --> 11:42.880
Zeit des besten sequentiellen wissen wir ja nicht so genau.

11:42.880 --> 11:49.680
Der optimale, der beste war ein N hoch 2.37 oder so etwas.

11:50.100 --> 11:54.780
Das können wir schlecht nehmen, deswegen in diesem Fall nimmt man als

11:54.780 --> 11:56.620
Vergleich die Schuhmethode.

11:57.500 --> 11:59.240
Und das ist natürlich eigentlich nicht ganz richtig.

12:00.180 --> 12:07.200
Also schon beim ersten Beispiel, wo ich Ihnen zeige, was für ein

12:07.200 --> 12:11.340
Speedup man kriegt, weiche ich ab von dieser Vorschrift, das optimale

12:11.340 --> 12:12.640
sequentielle Verfahren zu nehmen.

12:13.480 --> 12:15.220
Also das beste uns Bekannte wäre der Strassen.

12:17.600 --> 12:22.120
Aber es ist üblich, dass man bei der Matrixmultiplikation vergleicht

12:22.120 --> 12:26.340
mit der Methode, bei der man N hoch 3 Operationen braucht, mit der

12:26.340 --> 12:26.900
Schuhmethode.

12:28.100 --> 12:31.020
Ansonsten, man könnte es anders machen, dann wäre der Zeitgewinn nicht

12:31.020 --> 12:31.640
ganz so groß.

12:31.640 --> 12:35.420
Hier haben wir also ein Zeitgewinn in O von N².

12:37.060 --> 12:39.620
Also größer als N² kann etwas nicht sein.

12:41.120 --> 12:48.380
Und die Effizienz, naja, die Anzahl der Prozessoren ist N².

12:48.760 --> 12:52.680
Dann haben wir also eine konstante Effizienz, was gut ist.

12:53.460 --> 12:58.780
Das ist also irgendwas, ein Halb, ein Drittel oder zwei Drittel.

12:58.860 --> 13:01.680
Genaue Konstante habe ich jetzt gar nicht geguckt, welche das ist.

13:01.740 --> 13:07.280
Auf jeden Fall haben wir hier eine Konstante als Effizienz und das ist

13:07.280 --> 13:08.000
ein sehr guter Wert.

13:08.100 --> 13:12.260
Wir werden später Beispiele sehen, wo wir bei der Effizienz nicht so

13:12.260 --> 13:15.500
gut aussehen.

13:16.660 --> 13:22.200
Das zu dem einfachen Verfahren ist ein Standardverfahren auf solchen

13:22.200 --> 13:24.880
zweidimensionalen Prozessorfeldern für Matrix-Modifikation.

13:25.420 --> 13:26.440
Hier ist ein anderes Beispiel.

13:27.520 --> 13:30.820
Das ist jetzt schon die dritte Methode auf solchen zweidimensionalen

13:30.820 --> 13:32.380
Feldern, die Sie hier gleich sehen werden.

13:32.920 --> 13:38.040
Wir hatten also einmal dieses Beispiel von den Anfangsfolien, wo wir

13:38.040 --> 13:39.400
so ein hexagonales Netz hatten.

13:40.520 --> 13:44.440
Und dann war das gerade eben das zweidimensionale getterverbundene

13:44.440 --> 13:44.760
Feld.

13:44.760 --> 13:48.800
Hier ist nochmal so ein getterverbundenes Feld, aber hier sehen die

13:48.800 --> 13:50.240
Operationen ein bisschen anders aus.

13:50.520 --> 13:53.220
Hier bewegen sich auch die Elemente C.

13:54.520 --> 13:57.900
Die Matrix A bewegt sich also von unten nach oben.

13:58.480 --> 14:01.920
Die Matrix B von oben nach unten, die kommt also da oben rein.

14:02.560 --> 14:09.200
Und das C-Ergebnis, also dass der Wert überrechnet wird, also das

14:09.200 --> 14:12.680
Produkt von A und B, wird auf C aufaddiert und nach rechts ausgegeben.

14:13.520 --> 14:16.520
Das ist also ein bisschen ähnlich wie das, was wir auf dem hexagonalen

14:16.520 --> 14:18.380
Netz gesehen haben, nur das ist ein anderes Netz hier.

14:18.440 --> 14:19.440
Das ist ein rechtwinkliges Netz.

14:20.620 --> 14:22.020
Und hier läuft das jetzt so...

14:22.020 --> 14:27.080
Also natürlich werden jetzt links nicht Elemente C eingegeben, sondern

14:27.080 --> 14:29.040
wir werden zu Anfang Nullen eingegeben.

14:29.340 --> 14:31.820
Also es könnte sein, die werden mit Null initialisiert.

14:32.680 --> 14:37.080
Also wird irgendwann hier eine Null eingegeben und dann wird da das

14:37.080 --> 14:37.580
draufaddiert.

14:37.580 --> 14:39.140
Also nach einigen Schritten.

14:39.680 --> 14:45.780
Jetzt haben wir einen Takt davor, dass tatsächlich A11 und B11 sich

14:45.780 --> 14:47.620
treffen, hier in diesem Prozessor.

14:48.460 --> 14:54.200
Und das C11 mit Null initialisiert wird dann draufaddiert auf das

14:54.200 --> 14:56.060
Produkt von A11 und B11.

14:56.940 --> 14:58.060
Und dann geht das so weiter.

14:58.200 --> 15:02.960
Jetzt haben wir hier die nächsten Produkte und wieder die nächsten.

15:03.080 --> 15:04.700
Sie sehen, das wandert also schön durch.

15:04.700 --> 15:08.640
Sie sehen, dass jeder zweite Prozessor hier aktiv ist.

15:10.340 --> 15:14.540
Bei dem anderen Beispiel mit dem zweidimensionalen Feld, das wir

15:14.540 --> 15:18.700
gerade vorher betrachtet hatten, da war in jedem Takt, war eigentlich

15:18.700 --> 15:20.560
jeder Prozessor aktiv.

15:20.760 --> 15:24.060
Zumindest zu einem gewissen Zeitpunkt waren also fast alle Prozessoren

15:24.060 --> 15:24.540
aktiv.

15:25.080 --> 15:26.640
Hier ist immer nur jeder zweite aktiv.

15:27.820 --> 15:29.940
Da kann man sich überlegen, woran das liegt, ob man das nicht besser

15:29.940 --> 15:30.760
hinkriegen könnte.

15:33.720 --> 15:37.620
Da muss man sich einfach mal angucken, was passiert, wenn man zwei

15:37.620 --> 15:42.420
Datenströme gegenläufig bewegen lässt und man weiß, welche miteinander

15:42.420 --> 15:43.460
kombiniert werden müssen.

15:44.060 --> 15:46.900
In diesem Fall geht es einfach nicht anders.

15:48.000 --> 15:51.660
Sie können sich nur in jedem zweiten Takt so, oder nur jeweils in

15:51.660 --> 15:53.300
jedem zweiten Prozessor so treffen.

15:54.520 --> 15:57.780
Und Sie sehen ja auch hier gewisse Lücken bei der Eingabe.

15:57.780 --> 16:01.100
Nur in jedem zweiten Takt werden sie dort eingegeben, an den einzelnen

16:01.100 --> 16:01.580
Eingängen.

16:02.580 --> 16:05.180
Also das läuft jetzt hier drei nach durch.

16:05.620 --> 16:11.320
Und nach vier Takten, also vier Takten nachdem die Null hier vorne

16:11.320 --> 16:15.060
eingegeben wurde, kommt hier hinten das C11 bzw.

16:15.540 --> 16:23.120
die Summe der AB-Komponenten für das Element C11 hier rechts raus.

16:23.120 --> 16:27.980
Und so weiter, bis dann alle berechnet worden sind.

16:28.600 --> 16:33.420
Und hier haben wir jetzt tatsächlich am Ende dieser Berechnung alle

16:33.420 --> 16:34.540
Werte ausgegeben.

16:35.060 --> 16:36.720
Also als letztes das C44.

16:37.940 --> 16:42.880
Und wir haben in diesem Fall also 4N-2 als Zeit.

16:42.880 --> 16:49.100
Und auch darauf kann man einfach abzählen, wie lange dauert es, bis

16:49.100 --> 16:53.620
hier das letzte Element da eingegeben wurde.

16:54.760 --> 16:59.320
Also bis dann der Wert, der hier an der Stelle berechnet wurde, bis

16:59.320 --> 17:00.720
der hier ganz durchgelaufen ist.

17:01.080 --> 17:03.340
Das kommt gerade auf diese 4N-2 Takte.

17:04.280 --> 17:05.440
Kann man einfach nachrechnen.

17:06.100 --> 17:10.300
Also nach 4N-2 Takten im Prinzip die gleiche Zeit, die man bei dem

17:10.300 --> 17:13.060
zweidimensionalen Feld braucht, das wir vorhin vorbetrachtet hatten,

17:13.260 --> 17:16.300
um insgesamt auch die Werte ausgegeben zu haben.

17:17.920 --> 17:19.940
Ja, da hätte man ja auch noch die Werte rausschieben können, dann

17:19.940 --> 17:23.060
wären wir auch auf diese 4N-2 Takte gekommen.

17:23.600 --> 17:27.060
Also auch Zeitgewinn und Effizienz gleich, aber ein ganz anderes

17:27.060 --> 17:27.600
Verfahren.

17:28.860 --> 17:33.480
Und jetzt ist die Frage, wie kommt man auf solche Verfahren?

17:33.480 --> 17:34.820
Übrigens noch eine Bemerkung.

17:37.760 --> 17:40.840
Wir haben ja hier gesehen in diesem Algorithmus, da ist nur jeder

17:40.840 --> 17:42.880
zweite Prozessor aktiv in jedem Takt.

17:44.540 --> 17:45.120
Das ist doch schlecht.

17:45.340 --> 17:47.320
Nur die Hälfte der Prozessoren ist beteiligt.

17:47.460 --> 17:50.200
Die Effizienz ist also eigentlich, die kann gar nicht so hervorragend

17:50.200 --> 17:52.140
sein, die müsste man verbessern können.

17:52.960 --> 17:54.300
Man kann folgendes machen.

17:54.900 --> 18:01.200
Man kann einfach dafür sorgen, dass hier eine weitere Matrix

18:01.200 --> 18:02.200
eingegeben wird.

18:02.760 --> 18:04.400
Ich male das mal einfach hier noch ein.

18:04.480 --> 18:10.360
Man kann hier einfach noch eine weitere Matrix mit Elementen 1,4, 1,3,

18:10.600 --> 18:12.580
1,2, 1,1 eingeben.

18:13.140 --> 18:16.720
Um einen Takt versetzt, hier auch jeweils.

18:16.720 --> 18:20.360
Und könnte dann zwei Produkte berechnen.

18:20.440 --> 18:25.460
A mal B gleich C und A mal B gleich C.

18:25.880 --> 18:29.980
Und könnte die ineinander versetzt ablaufen lassen.

18:30.180 --> 18:34.500
Und dann hätte man, wenn man sich die Ausführungszeiten hier aufmalt,

18:34.560 --> 18:37.740
hätte man also hier einmal die Zeit für eine Berechnung, für eine

18:37.740 --> 18:38.600
Matrixmultiplikation.

18:38.740 --> 18:42.580
Man würde direkt anschließend die nächste Matrixmultiplikation

18:42.580 --> 18:42.960
beginnen.

18:42.960 --> 18:47.160
Müsste dann warten, bis die beide durchgelaufen sind und könnte dann

18:47.160 --> 18:50.160
mit den nächsten beiden weitermachen.

18:50.340 --> 18:52.140
Würde dadurch den Durchsatz erhöhen.

18:52.460 --> 18:56.000
Die Zeit pro Berechnung wäre identisch, aber der Durchsatz wäre

18:56.000 --> 18:58.380
deutlich erhöht, also verdoppelt.

18:59.640 --> 19:01.420
Und es wären alle Prozessoren aktiv.

19:02.820 --> 19:05.160
Insofern kann man auch hier erreichen, dass alle Prozessoren

19:05.160 --> 19:06.060
ausgelastet sind.

19:06.060 --> 19:09.100
Allerdings macht das nur Sinn, wenn man mehrere

19:09.100 --> 19:12.400
Matrixmultiplikationen, die unabhängig voneinander sind, so

19:12.400 --> 19:14.040
miteinander kombinieren möchte.

19:14.980 --> 19:16.840
Also man kann noch weitere Sachen damit machen.

19:17.040 --> 19:21.600
Man kann zum Beispiel, wenn man sagt, das ist auch noch ein Problem,

19:21.660 --> 19:22.760
das man sich angucken kann.

19:23.160 --> 19:27.860
Stellen Sie sich vor, Sie haben sehr, sehr große Matrizen, die Sie

19:27.860 --> 19:28.820
modifizieren wollen.

19:32.050 --> 19:33.890
Haben aber nur ein kleines Feld zur Verfügung.

19:33.890 --> 19:37.830
Dann müssen Sie das irgendwie partitionieren.

19:39.650 --> 19:44.670
Für diese kleinen Matrixmultiplikationen jeweils, da könnten Sie das

19:44.670 --> 19:45.290
Feld einsetzen.

19:46.630 --> 19:52.090
Sie könnten also so weit gehen, dass Sie gerade mit der Größe dieser

19:52.090 --> 19:56.190
einzelnen Komponentenmatrizen auf das Feld passen.

19:57.830 --> 20:01.070
Und dann haben Sie unabhängig voneinander ablaufende

20:01.070 --> 20:04.470
Matrixmultiplikationen und könnten das ausnutzen, dass Sie die so

20:04.470 --> 20:05.570
aneinander verschränken können.

20:05.850 --> 20:11.670
Dann könnten Sie also dieses Feld wirklich effektiv einsetzen für die

20:11.670 --> 20:15.290
überlappende Ausführung mehrerer Teilmultiplikationen.

20:16.010 --> 20:21.690
Und da wir ja gesehen haben, hier diese Matrix C, die kam ja

20:21.690 --> 20:22.830
ursprünglich mal hier rein.

20:23.590 --> 20:25.950
Die muss ich ja nicht unbedingt mit Nullen vorbelegen.

20:25.950 --> 20:30.410
Da kann ich genauso gut, wenn ich jetzt so ein größeres Skalarprodukt

20:30.410 --> 20:37.050
machen will, wenn ich also komponentenweise eine partitionierte

20:37.050 --> 20:42.910
Matrixmultiplikation mache, dann würde ich eben eine Teilmatrix Cij

20:42.910 --> 20:49.250
berechnen als Skalarprodukt von Teilmatrizen.

20:49.250 --> 20:58.570
Hätte dann eben hier meine Ai1 mal Wkj, also all solche Teilprodukte.

20:59.090 --> 21:01.370
Und müsste ich das auch so mit Zwischensummen machen, die

21:01.370 --> 21:02.070
aufsummieren.

21:03.530 --> 21:09.270
Und da kann ich natürlich diese Zwischensummen jeweils hier, im

21:09.270 --> 21:14.690
Prinzip so ein großes Cijk, eine Zwischensumme da jeweils eingeben.

21:15.610 --> 21:19.830
Und dann das draufaddieren auf die nächste Teilberechnung.

21:20.370 --> 21:23.070
Das muss man geeignet organisieren, kann man alles hinkriegen und kann

21:23.070 --> 21:28.530
dann dieses Cell sehr effizient ausnutzen, um so eine partitionierte

21:28.530 --> 21:29.950
Matrixmultiplikation zu machen.

21:31.910 --> 21:37.410
Das ist nur um anzudeuten, allein dieses Verfahren ist schon ganz

21:37.410 --> 21:37.870
interessant.

21:37.870 --> 21:41.070
Aber jetzt muss man sehen, wie kann man das wirklich einsetzen, um

21:41.070 --> 21:42.870
auch größere Matrizen zu multiplizieren.

21:43.350 --> 21:46.290
Das ist ja eine feste Hardware, die ich hier habe, die Matrizen in der

21:46.290 --> 21:47.730
Realität sind aber unterschiedlich groß.

21:48.770 --> 21:51.390
Und dann muss man sich anschauen, wie kann ich eigentlich durch so ein

21:51.390 --> 21:55.410
Feld tatsächlich eine Beschleunigung hinbekommen, auch für größere

21:55.410 --> 21:58.510
Problemgrößen, als sie hier auf dieses Feld passen, dadurch, dass ich

21:58.510 --> 21:59.510
geeignet partitioniere.

21:59.630 --> 22:03.310
Ein ganz wichtiges Problem der Berechnungsorganisation, das man sich

22:03.310 --> 22:12.090
normalerweise anguckt, also Problem der Partitionierung von solchen

22:12.090 --> 22:14.110
Operationen.

22:16.550 --> 22:21.150
Gut, jetzt haben wir diese vielen verschiedenen Verfahren gesehen für

22:21.150 --> 22:22.350
die Matrixmultiplikation.

22:23.110 --> 22:27.330
Und die Frage ist, wie denkt man sich sowas aus?

22:28.150 --> 22:30.410
Also die Leute, die sich das zu Anfang ausgedacht haben, die hatten

22:30.410 --> 22:34.010
tatsächlich sich überlegt, ich habe jetzt hier dieses Feld und dafür

22:34.010 --> 22:34.910
möchte ich auch etwas machen.

22:35.010 --> 22:38.070
Die hatten die Idee, wie man die Daten geeignet kombiniert, sodass

22:38.070 --> 22:44.210
dann die Operation oder die Werte, die berechnet werden müssen,

22:44.330 --> 22:45.890
tatsächlich ausgeführt werden können.

22:46.490 --> 22:52.750
Aber das ist ja eigentlich etwas, was man vermeiden möchte, dass das

22:52.750 --> 22:56.290
Ganze auf Intuition beruht, sondern man möchte ja etwas als Ingenieur

22:56.290 --> 22:57.550
systematisch machen können.

22:58.550 --> 23:03.910
Nun gut, wir hatten gesehen, es gibt Leute, die verstehen das Problem

23:03.910 --> 23:07.450
ein bisschen besser und können die Formeln manipulieren und können

23:07.450 --> 23:12.570
dadurch irgendwie besser den Algorithmus organisieren, den Algorithmus

23:12.570 --> 23:13.110
entwerfen.

23:14.210 --> 23:21.250
Und eine Idee ist, dass man da ganz systematisch rangeht und diese

23:21.250 --> 23:24.970
parallelen Algorithmen für die Matrix-Modifikation durch ganz

23:24.970 --> 23:28.210
systematische Transformation des Ausgangsproblems macht.

23:28.270 --> 23:30.590
Das heißt, man möchte das Ausgangsproblem möglichst allgemein

23:30.590 --> 23:35.830
spezifizieren und dann ganz systematisch daraus unterschiedlichste

23:35.830 --> 23:38.270
Berechnungsmöglichkeiten erzeugen.

23:38.990 --> 23:44.950
Also die Idee ist, ich möchte parallele Algorithmen auf ganz

23:44.950 --> 23:47.850
systematische Art und Weise erzeugen können.

23:50.170 --> 23:55.990
Und dazu geht man wie folgt vor, man definiert das Problem.

23:57.490 --> 24:00.390
Also das Problem kennen wir doch, das war doch hier, das Problem ist

24:00.390 --> 24:05.690
doch, wir müssen diese Skalarprodukte berechnen, aik mal bkj, haben

24:05.690 --> 24:08.570
Sie jetzt schon sehr häufig gesehen, diese Summe.

24:09.230 --> 24:11.190
Das ist doch die Problemdefinition.

24:11.730 --> 24:14.850
Nun kann man die ein bisschen anders formulieren, durch Systeme von

24:14.850 --> 24:17.150
Rekurrenzgleichungen oder iterativen Algorithmen.

24:17.150 --> 24:20.030
Also wenn Sie an die innerste Schleife denken oder an den Rumpf der

24:20.030 --> 24:23.790
innersten Schleife denken, bei der Matrixmultiplikation, Schulmethode,

24:24.170 --> 24:27.670
das ist ein iterativer Algorithmus, n hoch 3 Ausführungen im Prinzip

24:27.670 --> 24:32.650
dieser inneren Schleife bewirkt die Matrixmultiplikation.

24:35.030 --> 24:38.650
Und wenn man solche Rekurrenzgleichungen hat oder iterative

24:38.650 --> 24:42.290
Algorithmen, dann stellt man fest, dass dort gewisse Abhängigkeiten

24:42.290 --> 24:42.710
auftauchen.

24:42.710 --> 24:43.470
Also wie war das nochmal?

24:43.590 --> 24:51.430
Wir hatten hier unser cij gleich irgendein cij plus, und dann musste

24:51.430 --> 24:56.370
da drin stehen aik mal bkj.

24:56.750 --> 24:58.210
Wo sehe ich denn hier Datenabhängigkeit?

24:58.710 --> 24:59.770
Sehe ich nicht direkt.

25:00.290 --> 25:08.490
Ich sehe nur eine Abhängigkeit zwischen diesen beiden Verwendungen von

25:08.490 --> 25:08.930
cij.

25:09.770 --> 25:13.670
Nun kann man das noch expliziter machen und schreibt dann noch eine

25:13.670 --> 25:14.770
dritte Variable hin.

25:15.750 --> 25:17.210
Und hier ein k-1 dran.

25:18.830 --> 25:20.650
Dann habe ich also hier eine Abhängigkeit.

25:20.770 --> 25:24.310
Ich habe einen Wert in einer Variablen cij k-1.

25:25.450 --> 25:27.810
Und ich brauche einen Wert cijk.

25:28.530 --> 25:32.390
Und da drin tauchen auf noch Variablen aik und bkj.

25:33.110 --> 25:35.130
Da sehe ich noch keine Abhängigkeiten.

25:37.870 --> 25:39.670
Aber man kann das also erweitern.

25:40.090 --> 25:41.890
Man kann die auch mit drei Indizes darstellen.

25:42.010 --> 25:45.610
Dann kriegt man da auch solche Datenabhängigkeiten rein.

25:46.290 --> 25:49.110
Auf jeden Fall stellt man fest, man kann...

25:49.110 --> 25:51.050
Also das, was ich jetzt hier hinschreibe, ist eine sogenannte Single

25:51.050 --> 25:51.790
-Assignment -Form.

25:52.370 --> 25:54.390
Auf der nächsten Folie steht es nochmal genauer.

25:55.150 --> 25:56.530
Ich habe hier eine Single-Assignment-Form.

25:56.630 --> 25:59.230
Das heißt, jeder Variablen wird jetzt nur noch einmal einen Wert

25:59.230 --> 25:59.810
zugewiesen.

25:59.890 --> 26:01.770
Dem cijk wird ein Wert zugewiesen.

26:02.390 --> 26:03.810
Und im Schritt danach wird der Wert verwendet.

26:03.810 --> 26:07.850
Aber das wird nicht zweimal einer Variablen cijk einen Wert

26:07.850 --> 26:08.370
zugewiesen.

26:08.990 --> 26:13.730
Jetzt kann ich mir angucken, wie oft... also wie eine Variable

26:13.730 --> 26:14.570
verwendet wird.

26:15.170 --> 26:18.670
Und über diese Verwendung einer Variablen auf der rechten Seite einer

26:18.670 --> 26:19.750
solchen Gleichung...

26:19.750 --> 26:23.310
habe ich eine Datenabhängigkeit praktisch etabliert.

26:24.310 --> 26:27.370
Und solche Datenabhängigkeiten kann man als Graph aufmalen.

26:27.830 --> 26:30.350
Und kann das dann darstellen über eine Matrix.

26:30.350 --> 26:35.230
Und kann jetzt ganz systematisch durch algebraische Transformationen

26:35.230 --> 26:36.150
von Indexräumen...

26:36.150 --> 26:40.530
kann man Algorithmen erzeugen.

26:40.650 --> 26:42.070
Das klingt jetzt alles sehr abstrakt.

26:42.290 --> 26:44.190
Deswegen machen wir das gleich wesentlich konkreter.

26:45.330 --> 26:49.130
Also man kann jetzt verschiedene Operationen anwenden,

26:49.230 --> 26:50.210
Transformationen.

26:50.710 --> 26:53.870
Man kann projizieren, man kann Retiming machen und ähnliches.

26:54.470 --> 26:55.950
Und wir werden sehen, wie das funktioniert.

26:55.950 --> 26:59.730
Das ist ein Ansatz, den man auch Mapping-Ansatz nennt, also

26:59.730 --> 27:00.830
Abbildungsansatz.

27:01.530 --> 27:05.050
Ich bilde im Prinzip das Problem ab auf unterschiedliche

27:05.050 --> 27:06.210
Realisierungsmöglichkeiten.

27:06.870 --> 27:08.510
Und das kann man ganz systematisch machen.

27:09.090 --> 27:10.750
Jetzt kommen wir nochmal zu unserem Beispiel.

27:11.650 --> 27:14.410
Die verschiedenen Darstellungen.

27:14.490 --> 27:19.830
Iterative Lösung ist also dieses Programmstück, das Sie nun schon

27:19.830 --> 27:20.790
mehrfach gesehen haben.

27:21.430 --> 27:26.130
Hier also nochmal in einer Algol-ähnlichen Sprache, oder Pascal

27:26.130 --> 27:27.830
-ähnlich, oder wie immer man das nennen möchte.

27:27.930 --> 27:29.130
Also prozedural aufgeschrieben.

27:29.830 --> 27:35.490
Hier ist unsere innere Schleife mit dem Rumpf.

27:36.190 --> 27:38.130
Und da steht, was gemacht werden muss.

27:38.450 --> 27:40.590
Jetzt ist es noch nicht die Form, die wir haben wollten, die Single

27:40.590 --> 27:41.430
Assignment Form.

27:42.350 --> 27:45.650
Für den Schleifenrumpf sieht es so aus, dass wir diesen dritten Index

27:45.650 --> 27:46.870
dazufügen, das K.

27:47.270 --> 27:49.090
Da steht es, K und da K-1.

27:49.090 --> 27:54.990
Jetzt habe ich also Variablen Cij1 bis Cijn.

27:55.910 --> 27:57.810
Und denen wird jetzt etwas zugewiesen.

27:59.910 --> 28:01.070
Wohl nur einmal.

28:01.830 --> 28:03.430
Oder das kann ich noch anders hinschreiben.

28:03.550 --> 28:05.170
Ich kann daraus Rekurrenzgleichungen machen.

28:06.010 --> 28:13.970
Bei Rekurrenzgleichungen habe ich wirklich nur noch diese Variablen

28:13.970 --> 28:15.170
mit jeweils drei Indizes.

28:15.170 --> 28:18.250
Hier ist meine Gleichung für die Cij.

28:19.470 --> 28:21.230
Da steht jetzt IKJ.

28:22.170 --> 28:24.930
Ich habe jetzt das K in die Mitte eingefügt.

28:25.230 --> 28:26.930
Ist egal, welche Reihenfolge man das macht.

28:30.090 --> 28:31.850
Jetzt haben wir es also so aufgeschrieben.

28:32.510 --> 28:36.590
CIKJ und hier steht CIK-1J.

28:40.670 --> 28:44.390
Und hier haben wir unsere Variablen A und B.

28:45.290 --> 28:46.910
Auch mit drei Indizes.

28:47.910 --> 28:53.650
Da steht jetzt IKJ-1 und B und B I-1KJ.

28:53.950 --> 28:56.690
Wir hatten eigentlich gestehen BKJ und AIK.

28:58.530 --> 29:02.950
Und haben die dritte Variable, die auftaucht, da haben wir jetzt auf

29:02.950 --> 29:04.850
einmal eine Abhängigkeit drin.

29:07.630 --> 29:09.470
Hier haben wir den Index J.

29:10.590 --> 29:15.130
Und da brauchen wir eine Variable J-AIKJ-1.

29:16.610 --> 29:19.790
Das ist eine rekursive Gleichung.

29:20.210 --> 29:22.150
Man nennt das in diesem Fall Rekurrenzgleichung.

29:23.250 --> 29:25.290
Jetzt müssen wir sehen, wie geht das denn weiter.

29:26.270 --> 29:29.170
Also das AIKJ, dafür brauchen wir auch eine Rekurrenzgleichung.

29:29.530 --> 29:32.190
AIKJ ist gleich AIKJ-1.

29:32.910 --> 29:37.490
Und das BIKJ ist gleich BI-1KJ.

29:38.230 --> 29:39.270
Es ändert sich also nichts.

29:39.530 --> 29:41.090
Die Werte werden nur weitergegeben.

29:41.890 --> 29:43.650
Und ich muss Anfangswerte angeben.

29:45.270 --> 29:48.230
AIK0, ich habe also auch einen Index 0.

29:48.710 --> 29:52.470
Da habe ich gerade das AIK stehen, die Matrixkomponente.

29:52.690 --> 29:57.170
Das heißt an irgendeiner Stelle initialisiere ich diese Variable AIK0.

29:57.170 --> 30:04.850
Alle anderen A-Variablen werden jetzt dadurch auf diesen Wert gesetzt.

30:07.150 --> 30:09.390
Und für das B mache ich das analog.

30:10.390 --> 30:15.770
Und für das CI0J, da schreibe ich einfach 0 rein.

30:17.110 --> 30:18.890
Das heißt, das wird mit 0 initialisiert.

30:19.050 --> 30:22.690
Jetzt habe ich alle Variablen, die hier vorkommen mit diesen

30:22.690 --> 30:26.130
Rekurrenzgleichungen, mit Anfangswerten versehen.

30:26.130 --> 30:28.590
Und ich kann so sukzessive da durchlaufen.

30:30.650 --> 30:37.890
Jetzt habe ich für jeden Index, also für IKJ, für den Index IKJ, habe

30:37.890 --> 30:39.130
ich Datenabhängigkeiten.

30:39.790 --> 30:41.630
Und die sehen so aus.

30:42.330 --> 30:44.230
Hier ist IKJ, das ist mein Index.

30:45.290 --> 30:50.990
Und für diesen Index IKJ habe ich für die Variable A eine Abhängigkeit

30:50.990 --> 30:53.490
zum Index IKJ-1.

30:53.490 --> 30:58.570
Für die Variable B eine Abhängigkeit zum Index I-1KJ.

30:59.490 --> 31:03.590
Und für die Variable C eine Abhängigkeit zum Index IK-1J.

31:04.650 --> 31:08.130
Also hier, ich kann das aufmalen als ein dreidimensionales Gebilde.

31:09.230 --> 31:15.210
Die Richtungen, die Dimensionen, sind hier durch die einzelnen Indizes

31:15.210 --> 31:17.430
IK und J aufgespannt.

31:17.430 --> 31:27.510
Ich habe also hier das I von links nach rechts aufgemalt, das J, so

31:27.510 --> 31:30.910
diagonal, und die K-Richtung vertikal.

31:33.570 --> 31:39.990
Diese hier visuell dargestellten Datenabhängigkeiten kann ich auch auf

31:39.990 --> 31:47.590
dem Index, das ist ja eigentlich ein Z hoch 3, ein Indexraum, oder

31:47.590 --> 31:53.910
eine Teilmenge des Z hoch 3, nämlich gerade die Indizes 1, 1, 1 bis N,

31:53.930 --> 31:54.310
N, N.

31:54.970 --> 31:56.670
Oder die Nullen kamen auch noch vor.

31:58.710 --> 32:03.730
Gewisse Indizes oder Elemente des Z hoch 3, für die habe ich also

32:03.730 --> 32:04.970
diese Abhängigkeiten hier drin.

32:05.230 --> 32:10.530
Und ich kann das auch als Vektoren aufschreiben, dass ich hier für die

32:10.530 --> 32:18.710
einzelnen Variablen C, A und B Datenabhängigkeiten als Vektoren

32:18.710 --> 32:19.490
hinschreibe.

32:19.830 --> 32:22.130
Das sind also meine drei Datenabhängigkeitsvektoren.

32:23.130 --> 32:30.270
Für C, da war es die Abhängigkeit in der mittleren Variablen, für A im

32:30.270 --> 32:36.490
dritten Index und für B im ersten Index.

32:36.490 --> 32:40.910
Und zwar der Abstand war immer gerade 1.

32:43.070 --> 32:45.750
Sie können sich vorstellen, dass man andere Rekurrenzgleichungen in

32:45.750 --> 32:49.730
irgendwelchen Schleifen haben könnte, wo ich nicht nur einen Abstand

32:49.730 --> 32:54.030
von 1 habe, sondern vielleicht 2 oder 27 oder irgendwas, je nachdem

32:54.030 --> 32:55.690
wie kompliziert die Berechnungen sind.

32:56.250 --> 33:00.810
Aber es gibt im technisch-naturwissenschaftlichen Bereich viele

33:00.810 --> 33:05.630
Probleme, die man auf diese Art und Weise beschreiben kann, wo ich

33:05.630 --> 33:12.690
also iterativ etwas berechne und die Abhängigkeiten, häufig ist es ein

33:12.690 --> 33:14.850
Abstand von 1, kann aber auch größer sein.

33:16.850 --> 33:20.890
Und was man auch sieht ist, dass diese ganzen Abstände völlig

33:20.890 --> 33:25.590
unabhängig davon sind, welches Index-Tupel ich mir angucke.

33:27.010 --> 33:29.990
Für jedes IKJ sind das die gleichen Abhängigkeiten, die gleichen

33:29.990 --> 33:30.570
Abstände.

33:30.570 --> 33:34.550
Das heißt, wenn ich meine Berechnungen organisiere, kann ich das

33:34.550 --> 33:38.110
machen, indem ich einfach so das für ein IKJ mir einmal betrachte,

33:38.230 --> 33:41.530
welche Abhängigkeiten habe ich da und daraus kann ich jetzt so einen

33:41.530 --> 33:47.390
Datenabhängigkeitsgraf aufmalen und ich kann den dann modifizieren.

33:47.470 --> 33:49.890
Wie würde ein Datenabhängigkeitsgraf hierfür aussehen?

33:50.470 --> 33:53.470
Das ist ein ganz einfaches Gebilde, das ist hier ein Ausschnitt, 3x3

33:53.470 --> 33:56.930
in drei Richtungen.

33:57.790 --> 34:05.210
Das wäre also hier der mittlere Knoten und da sieht man die einzelnen

34:05.210 --> 34:05.790
Abhängigkeiten.

34:05.930 --> 34:08.370
Natürlich gilt das für jeden Knoten, dass diese Abhängigkeiten da

34:08.370 --> 34:08.570
sind.

34:08.670 --> 34:12.530
Die sind hier farbig, genau wie vorher gekennzeichnet, blau, rot und

34:12.530 --> 34:18.530
grün, entsprechend den Richtungen, über die die Elemente A, B und C

34:18.530 --> 34:21.570
hier in ihren Abhängigkeiten zu sehen sind.

34:22.210 --> 34:24.290
Was gibt jetzt jeder einzelne Knoten an?

34:24.290 --> 34:27.730
Wenn wir uns irgendeinen Knoten betrachten, dann gibt dieser Knoten

34:27.730 --> 34:34.430
an, schauen wir nochmal auf die vorige Folie, ich habe zu jedem IKJ

34:34.430 --> 34:39.390
Berechnungen auszuführen, und zwar eine Berechnung, die angegeben ist

34:39.390 --> 34:43.130
in diesem Fall durch diese drei Gleichungen.

34:43.850 --> 34:47.530
Ich muss für die Variablen C, A und B irgendwelche Operationen

34:47.530 --> 34:53.930
ausführen und zwar für die Operation A und B nur eine Kopieroperation.

34:54.990 --> 34:57.170
Das sind also Werte von den Nachbarn, das ist also die Trivial

34:57.170 --> 34:57.710
-Operation.

34:58.330 --> 35:01.570
Und für die Variable C muss ich eine Multiplikation machen und eine

35:01.570 --> 35:02.150
Addition.

35:03.350 --> 35:06.110
Das sind die Berechnungen, die ausgeführt werden müssen, für jedes

35:06.110 --> 35:06.750
IKJ.

35:07.270 --> 35:12.130
Das heißt, in diesem Datenabhängigkeitsgraf sehe ich an jedem Knoten

35:12.130 --> 35:16.850
eine Berechnung, die ausgeführt werden muss, um meine Matrix

35:16.850 --> 35:18.910
-Multiplikation auszuführen.

35:20.390 --> 35:26.810
Und jetzt geht man daran, diesen Datenabhängigkeitsgraf geeignet

35:26.810 --> 35:29.950
abzubilden auf ein Prozessorfeld.

35:30.750 --> 35:34.590
Also ich muss jetzt einzelne Prozessoren, wenn ich hier irgendeinen

35:34.590 --> 35:39.430
Prozessor habe, dann muss ich irgendwie diesem Prozessor einige der

35:39.430 --> 35:40.410
Berechnungen zuordnen.

35:40.410 --> 35:44.490
Sie erinnern sich an diese Beispiele, das waren zweidimensionale

35:44.490 --> 35:48.610
Felder, und in jedem Prozessor wurden einige dieser Operationen

35:48.610 --> 35:49.230
ausgeführt.

35:49.990 --> 35:52.970
Und welche ausgeführt werden und zu welchem Zeitpunkt sie ausgeführt

35:52.970 --> 35:57.630
werden, das muss ich festlegen, indem ich jede Berechnung, also jeden

35:57.630 --> 36:03.030
einzelnen Knoten, einem Prozessor zuordne und eine Zeit zuordne, wann

36:03.030 --> 36:04.570
diese Berechnung ausgeführt werden soll.

36:05.630 --> 36:09.410
Und das ist das, was man dann rein algebraisch machen kann.

36:09.410 --> 36:14.750
Man macht eine Transformation, die jedem Index ikj, also jedem Knoten,

36:14.810 --> 36:17.770
eine Zeit t und einen Ort xy zuordnet.

36:18.290 --> 36:21.510
Und das kann man auffassen als eine einfache Matrixtransformation.

36:22.450 --> 36:26.770
Ich habe ein Z3 als Indexraum und ich mache dort eine

36:26.770 --> 36:34.010
Matrixtransformation und interpretiere die erste Zeile als eine

36:34.010 --> 36:39.270
Abbildung auf Zeitpunkte und die nächsten beiden Zeilen als eine

36:39.270 --> 36:41.270
Abbildung auf Orte.

36:41.410 --> 36:46.130
Also wenn ich jetzt...

36:46.130 --> 36:50.910
Dadurch, dass ich das hier, meinetwegen, modifiziere mit irgendeinem

36:50.910 --> 37:00.250
ikj, bekomme ich einen... also für ikj würde ich hier bekommen als

37:00.250 --> 37:05.370
Zeitpunkt i plus k plus j, nämlich gerade die erste Zeile mal diesen

37:05.370 --> 37:05.810
Vektor.

37:06.770 --> 37:09.770
Das heißt, zum Zeitpunkt i plus k plus j würde die Berechnung

37:09.770 --> 37:10.610
ausgeführt werden.

37:11.090 --> 37:12.790
Und wo würde sie ausgeführt werden?

37:13.710 --> 37:19.310
Da hätte ich jetzt einmal hier den Wert k, also 010 mal ikj.

37:20.310 --> 37:26.530
Das wäre der nächste Wert, also k und unten drunter steht i minus j.

37:27.290 --> 37:28.050
Das wäre der Ort.

37:30.430 --> 37:30.990
So.

37:31.930 --> 37:36.070
Und wenn man sich das anschaut, welche Zuordnung das ergibt, dann

37:36.070 --> 37:40.450
bekomme ich ein Feld, das wir uns eigentlich noch gut erinnern

37:40.450 --> 37:40.750
müssten.

37:41.030 --> 37:47.790
Das hier gibt genau an, also die Zuordnungen, die entstehen, wenn ich

37:47.790 --> 37:50.830
diese Transformation T, die hier beispielsweise angegeben ist,

37:50.910 --> 37:57.110
ausführe auf dem Z3, dann werden die einzelnen Berechnungen so

37:57.110 --> 38:01.850
zugeordnet, dass die Matrix A sich schön von unten nach oben bewegt.

38:02.730 --> 38:08.410
Die Matrix B in diesem Fall von oben nach unten.

38:09.310 --> 38:13.090
Die Matrix B geht in der Richtung und die Matrix C in der Richtung.

38:13.170 --> 38:14.030
Das hat man doch gerade gesehen.

38:14.150 --> 38:18.510
Das war doch dieser eine Algorithmus von Kuhn und Leiserson, wo die

38:18.510 --> 38:22.310
sich so schön durchbewegten und jeder zweite Prozessor hatte immer was

38:22.310 --> 38:22.690
zu tun.

38:24.210 --> 38:29.330
Und jetzt hätte ich allein durch so eine Matrix-Transformation den

38:29.330 --> 38:30.630
Algorithmus erzeugt.

38:32.010 --> 38:36.350
Und jetzt kann man sich vorstellen, wenn ich jetzt diese Werte in

38:36.350 --> 38:38.170
meiner Matrix T modifiziere,

38:41.830 --> 38:47.470
andere Abbildungen für die Zeit reinschreibe oder andere Orte

38:47.470 --> 38:51.670
reinschreibe in die Ortsabbildung, bekomme ich andere Algorithmen.

38:54.190 --> 38:57.450
Und auf die Art und Weise kann ich unterschiedlichste Sachen erzeugen,

38:57.530 --> 39:05.210
da kann ich dieses hexagonale Feld erzeugen, ich kann das

39:05.210 --> 39:08.050
zweidimensionale Feld erzeugen, wo die Matrizen von links und rechts

39:08.050 --> 39:10.970
reinkamen und das C stillgeblieben ist und so weiter.

39:11.110 --> 39:12.410
Das kann man alles machen.

39:14.430 --> 39:16.150
Dann gibt es natürlich ein paar Anforderungen.

39:16.490 --> 39:18.130
Man kann nicht jede beliebige Matrix nehmen.

39:19.510 --> 39:22.310
Man muss natürlich dafür sorgen, dass die Abbildungen vernünftig sind.

39:22.950 --> 39:36.110
Und vernünftig heißt zunächst mal, es dürfen also nicht zwei

39:36.110 --> 39:43.250
Berechnungen auf genau den gleichen Wert abgebildet werden.

39:43.870 --> 39:47.670
Das würde bedeuten, am gleichen Ort zur gleichen Zeit müssten

39:47.670 --> 39:49.950
unterschiedliche Berechnungen stattfinden.

39:50.970 --> 39:54.970
Nicht nur für i, k, j, sondern für noch irgendeinen i', k', j'.

39:57.590 --> 40:00.790
Das erlaubt man nicht, sondern es muss injektiv sein.

40:09.290 --> 40:11.930
Also das T muss injektiv sein auf dem Ganzen, genau.

40:11.930 --> 40:18.810
Wenn es nicht injektiv wäre, hätte ich zum gleichen Zeitpunkt

40:18.810 --> 40:26.930
Verletzungen dieser ganzen Datenabhängigkeiten.

40:28.110 --> 40:31.990
Also es darf pro Takt, pro Prozessor höchstens eine Berechnung

40:31.990 --> 40:32.550
stattfinden.

40:33.170 --> 40:36.630
Wenn ich natürlich jetzt Prozessoren hätte, wenn ich Multiprozessor

40:36.630 --> 40:39.950
-Chips hätte und ich wollte darauf eine Zuordnung machen, dann könnte

40:39.950 --> 40:43.010
man sagen, es dürfen so und so viele Berechnungen gleichzeitig dazu

40:43.010 --> 40:43.670
geordnet werden.

40:43.750 --> 40:44.830
Das wäre aber noch ein anderes Problem.

40:45.190 --> 40:48.350
Wir gehen davon aus, wir können pro Takt, pro Prozessor höchstens eine

40:48.350 --> 40:49.210
Berechnung ausführen.

40:49.570 --> 40:50.970
Deswegen muss das injektiv sein.

40:52.410 --> 40:55.090
Dann darf ich den Datenabhängigkeiten nicht widersprechen.

40:56.510 --> 41:00.790
Ich habe so Abhängigkeiten, dass ich den Wert z.B.

41:00.910 --> 41:08.430
CIK-1J zur Verfügung haben muss als Wert, damit ich CIKJ berechnen

41:08.430 --> 41:08.710
kann.

41:10.830 --> 41:16.890
Also darf nicht das CIK-1J zu einem späteren Zeitpunkt berechnet

41:16.890 --> 41:19.370
werden als das CIKJ.

41:20.550 --> 41:22.190
Darauf muss ich achten in meiner Abbildung.

41:23.110 --> 41:27.730
Und das kann man hinbekommen, indem man fordert, dass das Thema D, D

41:27.730 --> 41:30.510
ist jeweils einer dieser Datenabhängigkeitsvektoren, die wir vorhin

41:30.510 --> 41:33.130
aufgemalt hatten, die müssen alle größer gleich 0 sein.

41:33.690 --> 41:34.690
Sonst funktioniert das nicht.

41:37.980 --> 41:38.800
Und das ist schon alles.

41:43.300 --> 41:46.300
Was ist der Vorteil so eines Ansatzes?

41:46.300 --> 41:47.840
Ich gebe Ihnen gleich noch Beispiele.

41:47.920 --> 41:54.120
Wir haben ein kleines Werkzeug, mit dem man diese Abbildungen ein

41:54.120 --> 41:55.560
bisschen ausprobieren kann.

41:56.820 --> 42:01.160
Vorteile so eines Ansatzes sind, dass ich hier korrektheitserhaltende

42:01.160 --> 42:06.520
Transformationen habe, auf einer recht abstrakten, sehr problemnahen

42:06.520 --> 42:07.260
Beschreibung.

42:08.500 --> 42:11.980
Das heißt, die Algorithmen, die nachher herauskommen, sind garantiert

42:11.980 --> 42:14.040
korrekte Berechnungen der Matrixmodifikation.

42:15.040 --> 42:18.080
Und wenn Sie sich vorstellen, Sie kriegen also nur den Algorithmus

42:18.080 --> 42:21.940
geliefert von Kung und Leiserson oder von irgendwelchen anderen Leuten

42:21.940 --> 42:26.800
da diese verschiedensten Überlegungen, wie man dort Daten kombiniert,

42:26.900 --> 42:30.640
sodass die Matrizen modifiziert werden, da sehen Sie nicht sofort,

42:30.760 --> 42:31.860
dass das korrekt ist.

42:32.900 --> 42:35.620
Von der Rekurrenzgleichung sehen Sie sofort, das ist genau die

42:35.620 --> 42:38.400
mathematische Formulierung meines Ausgangsproblems.

42:38.400 --> 42:42.900
Und wenn ich das dann korrektheitserhalten transformiert habe, ist das

42:42.900 --> 42:44.060
Ergebnis auch korrekt.

42:45.660 --> 42:49.000
Und ich habe natürlich die Möglichkeit, eine Vielfalt verschiedener

42:49.000 --> 42:53.640
Algorithmen zu erzeugen, basierend auf dem gleichen Berechnungsschema.

42:54.880 --> 42:56.680
Jetzt muss man sich eine Sache nochmal anschauen.

42:56.880 --> 43:01.180
Ich muss nochmal kurz hier zurückgehen zu... war das diese Seite?

43:01.540 --> 43:02.520
Ja, genau.

43:05.740 --> 43:11.140
Wenn man dieses Rekurrenzgleichungssystem sich hier aufmalt, da hat

43:11.140 --> 43:15.900
man eine ganze Reihe von Freiheitsgraden da drin, das unterschiedlich

43:15.900 --> 43:16.300
zu machen.

43:16.440 --> 43:18.340
Ein Punkt, den man in den Übungen mal ein bisschen ausprobieren

43:18.340 --> 43:18.700
könnte.

43:20.660 --> 43:25.780
Also, ich habe ja auf einmal hier gesagt, wie das A und das B, wie

43:25.780 --> 43:30.780
dort der dritte Index eingebaut wird, auch bei dem C, da ist ein

43:30.780 --> 43:33.340
dritter Index dazu gekommen, der vorher gar nicht da war, bei der

43:33.340 --> 43:35.620
Version, wo es nicht Single Assignment Form war.

43:36.520 --> 43:40.520
Es liegt nahe, das so zu machen, wie das hier steht, mit K-1 und K.

43:41.320 --> 43:43.540
Ich könnte genauso gut es andersrum machen.

43:45.400 --> 43:48.580
Ich könnte von N nach 1 runterzählen.

43:49.120 --> 43:49.900
Wäre auch möglich.

43:50.500 --> 43:56.700
Und genauso bei den beiden Gleichungen für A und B.

43:58.720 --> 44:02.300
Da könnte ich also in der Richtung von, das würde sich hier so

44:02.300 --> 44:05.620
eindeuten, ob ich jetzt von links nach rechts das B durchschiebe und

44:05.620 --> 44:10.340
das A so diagonal von vorne nach hinten, oder andersrum, ist

44:10.340 --> 44:11.500
eigentlich völlig egal.

44:12.640 --> 44:14.440
Das kann ich unterschiedlich hinschreiben.

44:15.220 --> 44:17.900
Und das wären unterschiedliche Formulierungen meines Ausgangsproblems.

44:17.900 --> 44:20.780
Dann würden sich also diese Rekurrenzgleichungen hier ändern.

44:21.480 --> 44:24.460
Und damit würden sich alle transformierten Geschichten auch ändern.

44:24.600 --> 44:30.120
Das heißt, dann hätte ich unterschiedliche Möglichkeiten für diese

44:30.120 --> 44:34.200
Matrixmultiplikationen, die aber dadurch unterschiedlich sind, dass

44:34.200 --> 44:37.500
ich die Rekurrenzgleichungen unterschiedlich aufgeschrieben habe.

44:39.220 --> 44:41.780
Also da habe ich durchaus noch einige Freiheitsgrade, wie ich das

44:41.780 --> 44:42.340
formuliere.

44:43.680 --> 44:46.840
Man hätte ja auch die Schleifenrümpfe anders formulieren können.

44:46.840 --> 44:48.960
Es muss ja nicht unbedingt so sein wie hier.

44:49.040 --> 44:50.420
Man kann das ganz anders aufschreiben.

44:50.540 --> 44:53.500
Das haben wir gesehen bei dem Vinograd, das hat eine völlig andere

44:53.500 --> 44:54.140
Formel gehabt.

44:55.800 --> 44:59.020
Daraus würde man auch andere parallele Algorithmen kriegen.

44:59.140 --> 45:03.300
Also man hat hier noch gewisse intuitive oder vielleicht auch

45:03.300 --> 45:08.220
systematische Möglichkeiten, an der Ausgangsformulierung zu drehen.

45:08.220 --> 45:12.980
Und daraus erzeugt man dann auf die Art und Weise, die wir jetzt hier

45:12.980 --> 45:16.340
gesehen haben, unsere Algorithmen.

45:17.120 --> 45:21.340
Also wir haben systematisch die Möglichkeit, eine Vielfalt von

45:21.340 --> 45:25.720
Algorithmen zu erzeugen, basierend auf dem gleichen Berechnungsschema.

45:26.040 --> 45:29.420
Aber wir haben durchaus bei dem Berechnungsschema eine Möglichkeit,

45:30.980 --> 45:33.820
häufig jedenfalls Möglichkeiten, das noch ein bisschen unterschiedlich

45:33.820 --> 45:34.240
zu machen.

45:34.240 --> 45:38.260
Und es gibt auch Ansätze, bei denen man diese Freiheitsgrade möglichst

45:38.260 --> 45:43.420
lange offen hält, bis möglichst spät in dem ganzen Entwurfsprozess und

45:43.420 --> 45:48.840
erst am Ende festlegt, wo genau die Eingaben gemacht werden für unsere

45:48.840 --> 45:49.240
Berechnung.

45:51.320 --> 45:52.000
Nachteil?

45:53.120 --> 45:55.540
Genau, ich habe ein linearisiertes Berechnungsschema.

45:56.100 --> 45:59.140
Das heißt, die Möglichkeiten der Parallelverarbeitung sind nur

45:59.140 --> 46:00.300
eingeschränkt nutzbar.

46:01.070 --> 46:05.060
Die Linearisierung heißt für unseren Berechnungsablauf, ich habe hier

46:05.060 --> 46:08.600
eine Multiplikation gemacht zu Anfang.

46:09.640 --> 46:11.480
Dann wird das...

46:12.760 --> 46:15.680
Also eigentlich habe ich hier einen Anfangswert, in dem Fall die Null.

46:16.200 --> 46:19.600
Habe eine Multiplikation gemacht, das Ganze addiert.

46:20.220 --> 46:22.900
Dann mache ich hier die nächste Multiplikation, addiere.

46:23.640 --> 46:27.440
Und habe hier wieder eine Multiplikation und addiere und so weiter.

46:27.440 --> 46:30.740
Also einen linearisierten Berechnungsablauf.

46:31.980 --> 46:35.080
Wir hatten gesehen, für eine volle Ausnutzung der Möglichkeiten der

46:35.080 --> 46:38.440
Parallelverarbeitung brauche ich nicht so einen entarteten Baum,

46:38.600 --> 46:41.060
sondern einen möglichst vollständigen Baum, bei dem die

46:41.060 --> 46:43.020
Multiplikationen etwas anders angeordnet sind.

46:46.520 --> 46:51.120
Hier sind also jeweils die Elemente, die modifiziert werden.

46:52.420 --> 46:56.800
Also ich habe hier eigentlich Möglichkeiten der Parallelverarbeitung

46:56.800 --> 47:00.080
ein bisschen reduziert für das einzelne Skalarprodukt.

47:00.780 --> 47:03.720
Aber ich habe ja viele unabhängige Skalarprodukte und habe da

47:03.720 --> 47:09.360
unabhängige Berechnungen, die ich im Prinzip pipeline kann, sodass ich

47:09.360 --> 47:15.040
durch die Nebeneinanderausführung vieler solcher einzelner

47:15.040 --> 47:18.100
Skalarprodukte tatsächlich einen guten Ablauf kriege.

47:19.080 --> 47:22.320
Trotzdem muss man sich klar machen, dass man eben schon einige Dinge

47:22.320 --> 47:24.240
durch das Rekurrenzschema festgelegt hat.

47:24.240 --> 47:26.600
Und das hatte ich ja gerade eben gesagt, das kann man ein bisschen

47:26.600 --> 47:30.000
modifizieren und kriegt dadurch noch ein bisschen Vergrößerung des

47:30.000 --> 47:30.700
Entwurfsraumes.

47:31.940 --> 47:34.680
Und dann muss man sich natürlich auch klar machen, ich habe hier

47:34.680 --> 47:38.500
natürlich eine sehr eingeschränkte Klasse von Algorithmen oder von

47:38.500 --> 47:41.780
Problemen, nämlich nur solche, bei denen ich sehr homogene

47:41.780 --> 47:42.780
Berechnungen habe.

47:43.960 --> 47:47.140
Die gleiche kleine Teilberechnung wird oft wiederholt.

47:48.600 --> 47:50.460
Man kann das Ganze ausweiten.

47:51.340 --> 47:54.300
Man kann da auch ein bisschen kompliziertere Sachen machen.

47:55.920 --> 47:59.720
Man kann, wie gesagt, das ist nur ein Ausschnitt elementarer

47:59.720 --> 48:00.160
Techniken.

48:03.020 --> 48:05.440
Es muss nicht unbedingt alles uniform sein.

48:05.560 --> 48:08.920
Man kann auch die Abhängigkeiten, die könnten unterschiedlich sein, je

48:08.920 --> 48:10.320
nachdem, an welchem Indexraum ich bin.

48:11.180 --> 48:15.660
Dann kommt man zu einer Vielfalt von Ansätzen für die systematische

48:15.660 --> 48:17.380
Erzeugung von parallelen Algorithmen.

48:18.260 --> 48:22.220
Das ist in dem Buch von Herrn Zehentner sehr ausführlich gemacht

48:22.220 --> 48:25.900
worden, eigentlich das Standardwerk über diese Ansätze.

48:27.780 --> 48:34.340
Es gibt immer noch wieder neue Literatur dazu, aber ich werde das

48:34.340 --> 48:39.220
jetzt nur insoweit weiter vertiefen, dass ich noch schnell gehen

48:39.220 --> 48:49.740
möchte auf das Applet.

48:50.020 --> 48:53.740
Dazu muss ich aber erstmal dafür sorgen, dass ich überhaupt Verbindung

48:53.740 --> 48:55.780
zum Netz bekomme.

48:57.520 --> 49:01.520
Dazu muss ich erstmal meinen VPN-Client aufmachen.

49:02.420 --> 49:04.240
Das dauert einen kleinen Augenblick.

49:07.380 --> 49:08.140
Und

49:13.440 --> 49:14.860
da ist er schon.

49:25.680 --> 49:31.620
Dann können wir da wieder rauf gehen und uns einfach mal das angucken.

49:33.680 --> 49:37.620
Also hier haben wir eine

49:44.650 --> 49:49.830
Webseite.

49:50.550 --> 49:59.750
Das ist ein Link auf eine Webseite, auf der ein größerer Vortrag

49:59.750 --> 50:00.910
angegeben ist.

50:01.170 --> 50:03.970
Also hier sind verschiedenste Sachen angegeben zu parallelen

50:03.970 --> 50:04.510
Algorithmen.

50:04.710 --> 50:05.850
Können Sie sich gerne auch angucken.

50:06.330 --> 50:08.390
Ausführlichere Darstellung von parallelen Algorithmen.

50:09.390 --> 50:13.250
Und wir haben hier eine Reihe von...

50:13.250 --> 50:17.710
Wenn Sie hier auf irgendeine Folie gehen, dann sehen Sie hier kurz

50:17.710 --> 50:19.290
angegeben die einzelnen Folien.

50:20.410 --> 50:23.170
Und zum Beispiel, wenn wir hier rauf gehen, sehen Sie, da ist jetzt

50:23.170 --> 50:27.950
eine solche Folie angegeben in einem etwas anderen Format, als Sie das

50:27.950 --> 50:29.130
jetzt kennen.

50:30.270 --> 50:32.590
Aber ich habe hier also externe Applets dabei.

50:32.790 --> 50:35.970
Hier zufällig ist ein externes Applet, auf das Sie jetzt...

50:36.870 --> 50:37.970
Da geht es um Verbindungsstrukturen.

50:38.870 --> 50:40.550
Können Sie sich auch gerne angucken, mit rumspielen.

50:40.550 --> 50:46.190
Aber ich möchte eigentlich jetzt hier auf das andere Applet, bei dem

50:46.190 --> 50:50.910
es geht um die Matrix-Multiplikation.

50:54.380 --> 50:55.520
Das kommt jetzt.

50:56.980 --> 50:59.880
Dauert einen kleinen Augenblick, bis das geladen ist.

51:00.540 --> 51:02.380
Und hier ist unser Konzept.

51:02.480 --> 51:05.340
Hier sehen wir drei verschiedene Anwendungen.

51:05.440 --> 51:08.880
Sortieren, Matrix-Vektor-Multiplikation und Matrix-Multiplikation.

51:08.880 --> 51:12.940
Das ist also jetzt die Oberfläche für die Matrix-Multiplikation.

51:14.240 --> 51:17.400
Und hier sehen Sie genau wieder das Bild, das ich auf den Folien

51:17.400 --> 51:17.680
hatte.

51:18.460 --> 51:23.640
Nämlich in einzelnen Knoten und die Datenrichtungen farbig markiert.

51:25.400 --> 51:31.800
B, Blau, A, Rot, C, Grün sind hier genauso modelliert wie vorher auch.

51:32.340 --> 51:34.480
Hier oben sehen Sie nochmal diese Richtungen.

51:34.480 --> 51:38.300
Da sehen Sie hier oben durch jeweils Rot gekennzeichnet, auf welche

51:38.300 --> 51:47.320
Datenrichtung sich die Komponenten dieser drei Indexbereiche beziehen.

51:47.920 --> 51:50.980
Also der linke Index bezieht sich auf die horizontale Richtung, der

51:50.980 --> 51:55.140
mittlere auf die vertikale, der rechte auf die diagonale

51:55.140 --> 51:55.980
Datenrichtung.

51:56.680 --> 51:59.360
Und jetzt können wir eine Zuordnung machen.

51:59.360 --> 52:01.680
Zum Beispiel, was war das?

52:01.880 --> 52:09.080
1, 1, 1 als Zeitzuordnung und als Prozessorzuordnung.

52:09.140 --> 52:10.700
Ich weiß gar nicht mehr, welche wir hatten.

52:12.840 --> 52:16.060
Das war 0, 1, 0.

52:19.130 --> 52:24.170
1, 0 und hier unten war es 1, 0 und hier minus 1.

52:26.710 --> 52:30.370
Und dann sagen wir Apply und da haben wir genau das Feld.

52:31.570 --> 52:32.810
Das ist jetzt erzeugt worden.

52:33.650 --> 52:40.330
Ist hier also angedeutet, dass D steht für Delay, also ein Schritt

52:40.330 --> 52:41.170
Verzögerung.

52:44.290 --> 52:47.450
Und Sie sehen, hier haben wir als Datenrichtung von oben nach unten.

52:48.230 --> 52:52.470
Dann haben wir bei dem Grünen, geht in diesem Fall von links nach

52:52.470 --> 52:52.790
rechts.

52:52.790 --> 52:54.870
Das waren die C-Elemente.

52:55.930 --> 52:59.150
Und das Rote läuft von unten nach oben in der Richtung.

52:59.610 --> 53:00.990
Das können Sie natürlich auch anders hinmalen.

53:01.110 --> 53:06.610
Ich könnte zum Beispiel, wenn ich jetzt hier die 0 hinschreibe und

53:06.610 --> 53:09.850
meinetwegen hier eine 1.

53:11.130 --> 53:12.090
Was gibt das?

53:13.950 --> 53:14.810
So ein Feld.

53:16.030 --> 53:17.190
Eine andere Anordnung.

53:17.330 --> 53:21.070
Hier würden also die Elemente der Matrix B von oben nach unten

53:21.070 --> 53:21.710
weiterhin laufen.

53:21.710 --> 53:22.870
Da haben wir auch nichts dran verändert.

53:24.490 --> 53:29.030
Die Elemente der Matrix C, die bleiben am Ort stehen.

53:29.730 --> 53:30.710
Die verändern sich gar nicht.

53:32.350 --> 53:35.710
Das ist hier mit dem Pfeil jeweils aus dem einzelnen Element heraus

53:35.710 --> 53:36.610
angegeben.

53:36.710 --> 53:37.790
Die bleiben an dem Ort.

53:39.030 --> 53:47.570
Und die Elemente der Matrix A, die laufen hier so diagonal durch.

53:49.690 --> 53:50.830
Auch eine Möglichkeit.

53:52.130 --> 53:57.770
Oder ich hätte hier an dieser Stelle die Minus 1 rauslassen können und

53:57.770 --> 53:59.130
da einfach eine 0 hinschreiben.

54:00.370 --> 54:01.710
Dann sehen wir so ein Feld.

54:02.630 --> 54:06.110
Jetzt haben wir genau das, was wir vorhin gesehen haben.

54:07.090 --> 54:10.030
Die Matrix B läuft von oben nach unten.

54:10.150 --> 54:11.670
Die Matrix A von links nach rechts.

54:11.810 --> 54:13.850
Und die Elemente der Matrix C bleiben am Ort.

54:16.770 --> 54:18.310
Das können wir genauso gut verändern.

54:18.470 --> 54:21.470
Dann können wir also das A am Ort lassen und B und C.

54:21.490 --> 54:23.010
Wenn wir A am Ort lassen wollen.

54:24.250 --> 54:27.010
A bezog sich auf die rechte Komponente.

54:27.590 --> 54:29.770
Dann müssten wir hier eine 0,0 hinschreiben.

54:30.250 --> 54:34.670
Also auf einen konstanten Ort im Prinzip lassen.

54:37.830 --> 54:43.410
Wir wollten das in der einen Richtung laufen lassen.

54:43.790 --> 54:45.930
Das A in der anderen.

54:47.530 --> 54:51.770
Jetzt hätten wir das B von oben nach unten nach wie vor.

54:52.310 --> 54:53.830
Jetzt würde die Matrix C wandern.

54:54.350 --> 54:56.570
Und die Elemente A würden konstant liegen bleiben.

55:00.500 --> 55:01.500
Auch das kann man machen.

55:03.040 --> 55:06.280
Durch diese Transformation kann man eine Vielfalt von

55:06.280 --> 55:08.280
unterschiedlichsten Berechnungen erzeugen.

55:08.660 --> 55:13.900
Sie müssen nicht lange überlegen, wie müssen die einzelnen Anweisungen

55:13.900 --> 55:14.840
in den Prozessor sein.

55:15.120 --> 55:17.740
Die können Sie alle ganz systematisch erzeugen.

55:19.860 --> 55:22.420
Dieses Applet können Sie sich angucken im Netz.

55:22.780 --> 55:24.160
Sie können damit rumspielen, so viel Sie wollen.

55:24.160 --> 55:31.860
Und sehen, wie man auf diese Art und Weise systematisch solche

55:31.860 --> 55:32.940
Algorithmen erzeugen kann.

55:33.040 --> 55:38.300
Die Beispiele hier sind angegeben für Matrix-Multiplikation, Matrix

55:38.300 --> 55:39.520
-Vektor -Multiplikation.

55:40.180 --> 55:45.660
Das ist also noch ein anderer Datenabhängigkeitsgraf.

55:45.840 --> 55:50.220
Oder eben für das Sortieren kann man auch Rekurrenzgleichungen machen.

55:50.720 --> 55:52.500
Dann hat man einen solchen Datenabhängigkeitsgraf.

55:52.500 --> 55:58.640
Wobei das jeweils eine bestimmte Art der Formulierung des Problems

55:58.640 --> 56:01.120
über einen iterativen Algorithmus voraussetzt.

56:01.600 --> 56:03.340
Und das kann man unterschiedlich machen.

56:03.500 --> 56:06.020
Aber wenn man es gemacht hat, kann man daraus sehr systematisch

56:06.020 --> 56:08.420
verschiedene Algorithmen erzeugen.

56:10.020 --> 56:10.660
Gut.

56:11.780 --> 56:13.760
Ich hoffe, das hat das ein bisschen anschaulicher gemacht, was ich

56:13.760 --> 56:16.700
vorher nur so rein abstrakt beschrieben habe.

56:17.700 --> 56:23.300
Und es ist wichtig zu wissen, Algorithmenentwurf kann man ganz

56:23.300 --> 56:28.720
systematisch machen über solche Transformationen von Indexräumen.

56:31.690 --> 56:34.670
Das ist also nicht nur Intuition, wie man Algorithmen entwirft.

56:36.710 --> 56:37.030
Gut.

56:37.290 --> 56:44.790
Gehen wir zurück zu unserer Vorlesung.

56:44.790 --> 56:47.750
Damit ist die Matrix-Modifikation erstmal abgeschlossen.

56:48.770 --> 56:50.230
Da haben wir eigentlich schon viel gemacht jetzt.

56:50.330 --> 56:55.950
Wir haben Ihnen einige Hinweise gegeben, wie man systematisch

56:55.950 --> 56:57.850
Algorithmen entwerfen kann.

56:58.650 --> 57:00.910
Wir hatten gesehen, man kann Formeln manipulieren.

57:01.170 --> 57:03.150
Das entspricht dem unterschiedlichen Darstellen aus

57:03.150 --> 57:04.030
Rekurrenzgleichungen.

57:04.130 --> 57:07.770
Wir haben gesehen, man kann solche systematischen Transformationen

57:07.770 --> 57:07.990
machen.

57:08.870 --> 57:12.090
Man kann dadurch im parallelen Bereich eine große Vielfalt

57:12.090 --> 57:13.610
verschiedener Algorithmen erzeugen.

57:15.210 --> 57:17.670
Jetzt kommen wir zu dem nächsten Problem.

57:19.430 --> 57:19.950
Polynomauswertung.

57:20.210 --> 57:21.990
Auch das habe ich Ihnen schon einmal präsentiert.

57:22.830 --> 57:25.030
In der ersten oder zweiten Vorlesungsstunde.

57:25.990 --> 57:28.810
Bei dem kleinen Beispiel, als wir geguckt haben, was heißt es

57:28.810 --> 57:32.350
eigentlich, unterschiedliche Algorithmen zu haben für ein Problem.

57:33.230 --> 57:36.650
Die Polynomauswertung bezieht sich darauf, dass wir irgendein Polynom

57:36.650 --> 57:38.170
endengerades berechnen wollen.

57:38.270 --> 57:39.590
Summe a i x o i.

57:41.230 --> 57:43.550
Wie beschreiben wir solch ein Polynom?

57:43.830 --> 57:45.110
Wodurch ist es charakterisiert?

57:45.830 --> 57:46.970
Durch die Koeffizienten.

57:49.330 --> 57:51.710
Also Koeffizienten a 0 bis a n.

57:52.650 --> 57:55.050
Wir brauchen eigentlich nur die Koeffizienten anzugeben.

57:55.590 --> 57:57.810
Und die Variable x.

57:59.450 --> 58:03.150
Wir könnten jetzt also bei festen Koeffizienten für unterschiedlichste

58:03.150 --> 58:04.850
Variablen x etwas ausrechnen.

58:04.850 --> 58:08.610
Wir könnten auch eine feste Variable x haben und könnten uns

58:08.610 --> 58:12.130
unterschiedliche Variablen anschauen.

58:12.690 --> 58:15.450
Also unterschiedliche Koeffizienten, hätten wir unterschiedliche

58:15.450 --> 58:15.950
Polynome.

58:16.570 --> 58:21.170
Für ein x würden wir unterschiedliche Polynome auswerten.

58:22.330 --> 58:24.450
Und man kann natürlich auch hier versuchen, das möglichst schnell zu

58:24.450 --> 58:24.690
machen.

58:26.030 --> 58:28.850
Auch hier könnte man das Ganze aufschreiben als Rekurrenzgleichung.

58:30.330 --> 58:32.790
Dann würde man das systematisch machen.

58:34.150 --> 58:38.070
Aber nach dem Ansatz, den wir gerade kennengelernt haben, darauf gehe

58:38.070 --> 58:38.810
ich hier gar nicht ein.

58:44.850 --> 58:47.150
Normalerweise schauen wir zunächst mal an, wie ist das Problem

58:47.150 --> 58:48.650
überhaupt beschrieben.

58:48.890 --> 58:50.910
Wir hatten auch bei der Matrixmodifikation gesagt, wie ist die

58:50.910 --> 58:51.550
Datenstruktur.

58:52.170 --> 58:55.830
Hier wäre die Datenstruktur in der Regel ein eindimensionales Feld für

58:55.830 --> 58:56.830
unsere Koeffizienten.

58:57.970 --> 59:00.850
Und die Frage ist, wie viele arithmetische Operationen brauche ich, um

59:00.850 --> 59:01.810
Polynomen zu berechnen.

59:02.450 --> 59:05.390
Nach den Erfahrungen mit der Matrixmodifikation müssen wir vorsichtig

59:05.390 --> 59:05.730
sein.

59:06.590 --> 59:08.930
Da hatten wir zunächst gesagt, es ist doch klar, dass man n hoch 3

59:08.930 --> 59:09.930
Operationen braucht.

59:10.850 --> 59:12.270
Wegen dieser einzelnen Skalarprodukte.

59:12.350 --> 59:13.810
Jedes Skalarprodukt mindestens n Operationen.

59:15.330 --> 59:18.370
n² Skalarprodukte, also weiß jeder, n hoch 3 Operationen brauche ich.

59:18.450 --> 59:19.530
Wir hatten gesehen, das stimmt nicht.

59:20.310 --> 59:25.570
Wir können auch mit n hoch 2.81 oder noch weniger auskommen.

59:26.150 --> 59:29.330
Also beim Polynomen müssen wir auch ein bisschen aufpassen, ob man da

59:29.330 --> 59:30.590
eventuell was reduzieren kann.

59:31.730 --> 59:36.950
Und dann sieht man, Horner Schema, achso, das haben wir schon mal

59:36.950 --> 59:39.690
kennengelernt, das waren n Modifikationen, n Additionen.

59:41.050 --> 59:43.890
Jetzt schauen wir uns spezielle Polynome an.

59:44.410 --> 59:47.270
Also das Polynomen Summe i gleich 0 bis n x hoch i.

59:49.070 --> 59:50.210
Das ist eine Reihe.

59:53.380 --> 59:56.880
Und wir wissen, wie man das zu einer Reihe in geschlossener Form

59:56.880 --> 59:57.700
aufschreiben kann.

59:58.240 --> 01:00:01.400
Als x hoch n plus 1 minus 1 durch x minus 1.

01:00:02.560 --> 01:00:08.060
Das heißt, für spezielle Koeffizienten meines Polynoms bin ich

01:00:08.060 --> 01:00:12.520
vielleicht in der Lage, sehr effizient das auszuwerten.

01:00:13.160 --> 01:00:16.720
Da würde niemand das als Summe i gleich 0 bis n x hoch i auswerten.

01:00:17.740 --> 01:00:20.540
Das ist natürlich in diesem geschlossenen Ausdruck.

01:00:20.540 --> 01:00:25.600
Und dann hätte ich nämlich nur 2 einfache Additionen, Subtraktionen zu

01:00:25.600 --> 01:00:27.340
machen, also dieses minus 1 jeweils.

01:00:28.920 --> 01:00:32.420
Ich muss natürlich eine Potenzierung machen, das x hoch n plus 1 muss

01:00:32.420 --> 01:00:33.100
ich ausrechnen.

01:00:33.800 --> 01:00:37.540
Das geht aber mit kleiner gleich 2 log n Modifikationen.

01:00:40.640 --> 01:00:43.760
Ich glaube, ich gehe darauf gar nicht ein.

01:00:43.860 --> 01:00:49.160
Ist Ihnen klar, wie Sie, wenn Sie also irgendeine Zahl, so ein x hoch

01:00:49.160 --> 01:00:52.500
n berechnen wollen, wie Sie das mit log n Modifikationen machen

01:00:52.500 --> 01:00:52.800
können?

01:00:53.980 --> 01:00:54.940
Eine von Ihnen Idee?

01:00:56.040 --> 01:00:58.220
Sieht ja zunächst mal so aus, als würde man dafür n minus 1

01:00:58.220 --> 01:00:59.240
Modifikationen brauchen.

01:01:04.220 --> 01:01:12.020
Normalerweise ist das n, aber gleich irgendeine Summe bi 2 hoch i,

01:01:12.440 --> 01:01:17.140
binärer Stellung des n, der Zahl n.

01:01:18.180 --> 01:01:25.740
Das heißt, das hier ist gleich x hoch Summe bi 2 hoch i.

01:01:27.140 --> 01:01:35.920
Dann ist das aber gleich dem Produkt x hoch bi 2 hoch i.

01:01:38.120 --> 01:01:38.680
Nachvollziehbar?

01:01:39.780 --> 01:01:43.300
Einfache Potenzrechnung, wenn Sie oben im Exponenten addieren, können

01:01:43.300 --> 01:01:44.700
Sie die Potenzen modifizieren.

01:01:46.980 --> 01:01:50.860
So, und jetzt haben wir hier die bi's, das ist entweder 0 oder 1.

01:01:52.500 --> 01:01:58.260
Und das heißt, was wir hier haben, ist ein Produkt von Potenzen von x,

01:01:59.000 --> 01:02:02.180
und zwar gerade Potenzen, das sind solche 2 hoch i's.

01:02:03.120 --> 01:02:07.660
Wie bekomme ich x hoch 2 hoch i, alle x hoch 2 hoch i?

01:02:08.400 --> 01:02:16.920
Ganz einfach, indem ich x ausrechne, x², x hoch 4 und so weiter, x

01:02:16.920 --> 01:02:18.680
hoch 2 hoch i.

01:02:19.340 --> 01:02:21.420
Eine Reihe von Quadrierungen.

01:02:22.540 --> 01:02:26.860
Das heißt, ich quadriere jeweils, denn das x hoch 2 hoch i ist ja

01:02:26.860 --> 01:02:37.320
gerade gleich x hoch 2 hoch i minus 1 mal x hoch 2 hoch i minus 1.

01:02:38.540 --> 01:02:39.780
Es quadriert einfach.

01:02:41.560 --> 01:02:45.460
Das heißt, wenn das n gleich irgendeiner Zweierpotenz wäre, bräuchte

01:02:45.460 --> 01:02:47.160
ich nur log n mal zu quadrieren.

01:02:48.320 --> 01:02:49.320
Und ich habe das x hoch n.

01:02:50.020 --> 01:02:53.460
Wenn es keine Zweierpotenz ist, also keine einzelne, dann ist es so

01:02:53.460 --> 01:02:55.160
ein Produkt von Zweierpotenzen.

01:02:55.580 --> 01:02:58.240
Das sind aber nur log n verschiedene, und die kann ich alle

01:02:58.240 --> 01:02:58.440
modifizieren.

01:02:59.020 --> 01:03:01.320
Dann habe ich insgesamt maximal zwei log n Modifikationen.

01:03:03.760 --> 01:03:08.980
Also so potenziert man durch Quadrieren und Modifizieren.

01:03:11.400 --> 01:03:16.000
Also diese 332 log n Modifikationen kann man ganz einfach hinkriegen

01:03:16.000 --> 01:03:17.100
bei der Potenzierung.

01:03:17.220 --> 01:03:23.200
Das heißt, ich habe bei dieser Darstellung meines Polynoms die

01:03:23.200 --> 01:03:28.160
Möglichkeit, mit deutlich weniger Operationen auszukommen als bei

01:03:28.160 --> 01:03:30.180
meinen n Modifikationen und n Additionen.

01:03:33.340 --> 01:03:36.500
Vorausgesetzt, eine Division ist tatsächlich eine einfache Operation.

01:03:37.720 --> 01:03:40.260
Davon kann man aber auf vielen Rechnen ausgehen.

01:03:42.740 --> 01:03:45.460
Das heißt, wir müssen auch da vorsichtig sein, was wir tatsächlich

01:03:45.460 --> 01:03:45.760
machen.

01:03:47.100 --> 01:03:51.260
Und wenn wir uns jetzt die Problemstellung genauer angucken, dann geht

01:03:51.260 --> 01:03:52.580
es jetzt schon wieder mit Mathematik los.

01:03:52.940 --> 01:03:56.480
Aber da macht man einfach mathematische Annahmen, um bestimmte

01:03:56.480 --> 01:03:57.900
Eigenschaften zu postulieren.

01:03:57.900 --> 01:04:04.200
Also wir sagen, was wir uns angucken, ist ein Problem, bei dem wir uns

01:04:04.200 --> 01:04:05.660
in einem Körper bewegen.

01:04:06.460 --> 01:04:07.740
Sie erinnern sich an die Mathematik?

01:04:08.800 --> 01:04:13.240
Ein Körper ist Ihnen in der Mathematik der Begriff Körper präsentiert

01:04:13.240 --> 01:04:14.720
worden, müsste eigentlich präsentiert worden sein.

01:04:15.080 --> 01:04:16.180
Sollte eigentlich bekannt sein.

01:04:16.260 --> 01:04:16.860
Linear Algebra.

01:04:17.880 --> 01:04:21.080
Also das heißt aber, was uns interessiert ist eigentlich nur, dass

01:04:21.080 --> 01:04:23.780
alle vier arithmetischen Operationen erlaubt sind.

01:04:24.440 --> 01:04:30.400
Also ich kann addieren und multiplizieren, das ist wichtig.

01:04:30.840 --> 01:04:33.100
Ich habe aber auch die inversen Operationen zur Verfügung.

01:04:34.620 --> 01:04:37.460
Ich habe also nicht nur einen Ring mit Addition und Multiplikation,

01:04:37.600 --> 01:04:38.320
sondern ich habe einen Körper.

01:04:38.900 --> 01:04:44.260
Das heißt bezüglich Addition und bezüglich Multiplikation ist das F

01:04:44.260 --> 01:04:45.240
jeweils eine Gruppe.

01:04:45.860 --> 01:04:48.540
Ich habe also das Inverse auch zur Verfügung.

01:04:48.780 --> 01:04:53.060
Also Subtraktion und Division stehen auch zur Verfügung.

01:04:54.140 --> 01:04:57.280
Wenn ich also davon rede, dass ich in einem Körper arbeite, heißt das

01:04:57.280 --> 01:05:01.760
nur, ich kann addieren und multiplizieren und ich habe auch jeweils

01:05:01.760 --> 01:05:05.020
die inversen Operationen, Subtraktionen und Divisionen zur Verfügung.

01:05:07.960 --> 01:05:10.820
Kommt noch etwas Mathematisches.

01:05:11.800 --> 01:05:16.560
Ich nehme an, dass die Koeffizienten a0 bis an und x transzendent über

01:05:16.560 --> 01:05:17.100
f sind.

01:05:19.500 --> 01:05:21.760
Mathematisch ist das die richtige Ausdrucksweise.

01:05:23.460 --> 01:05:24.940
Was will ich damit sagen?

01:05:25.760 --> 01:05:30.940
Dass ich keine zusätzlichen Informationen habe über das, was ich

01:05:30.940 --> 01:05:31.820
eigentlich sagen möchte.

01:05:32.820 --> 01:05:34.320
Die sind unabhängig voneinander.

01:05:35.260 --> 01:05:36.740
Ich habe keine Beziehungen dazwischen.

01:05:37.500 --> 01:05:39.980
Das heißt, ich muss wirklich jeden Wert mir explizit angucken.

01:05:41.700 --> 01:05:44.200
Und ich habe also keine zusätzlichen Informationen.

01:05:45.080 --> 01:05:47.360
Bei dem einen Beispiel vor, wusste ich über alle eins.

01:05:48.000 --> 01:05:48.680
Habe ich hier nicht.

01:05:49.220 --> 01:05:50.140
Ich weiß nichts darüber.

01:05:50.140 --> 01:05:52.220
Die sind also nicht irgendwie Nullstellen.

01:05:52.760 --> 01:05:54.140
Hier oben steht es mathematisch.

01:05:55.020 --> 01:05:57.400
Keine Nullstellen eines Polynoms über f.

01:05:58.540 --> 01:06:04.300
Wenn so ein Koeffizient eine Nullstelle eines Polynoms über f wäre,

01:06:04.700 --> 01:06:09.080
könnte ich das ausnutzen, um Berechnungen zu vereinfachen.

01:06:09.860 --> 01:06:10.960
Kann ich aber nicht.

01:06:11.240 --> 01:06:12.320
Ich weiß nichts darüber.

01:06:13.320 --> 01:06:25.700
Und das heißt, wir berechnen unser Polynom in diesem mathematischen

01:06:25.700 --> 01:06:30.680
Bereich, in einer mehrfachen, transzendenten Körpererweiterung von f.

01:06:32.020 --> 01:06:33.020
Was heißt das?

01:06:33.880 --> 01:06:38.380
Es dürfen vorkommen in unseren Berechnungen, in dem Programm, das wir

01:06:38.380 --> 01:06:42.600
schreiben, sämtliche Elemente von f.

01:06:44.180 --> 01:06:46.340
Also eins, zwei, drei, irgendwelche.

01:06:46.440 --> 01:06:52.220
Zum Beispiel könnten das sein, alle rationalen Zahlen könnten

01:06:52.220 --> 01:06:52.660
vorkommen.

01:06:52.780 --> 01:06:55.060
Oder alle reellen Zahlen könnten vorkommen.

01:06:56.440 --> 01:06:59.460
Das wären also jetzt irgendwelche Zahlen, Grundwerte.

01:07:00.060 --> 01:07:05.120
Es können vorkommen alle Koeffizienten a0 bis an.

01:07:06.200 --> 01:07:14.080
Und es kann das x vorkommen.

01:07:15.140 --> 01:07:23.040
Und ich kann sämtliche Ausdrücke mit diesen Elementen hinschreiben.

01:07:23.180 --> 01:07:26.040
Ich habe eine Körpererweiterung.

01:07:26.560 --> 01:07:30.540
Ich kann also jede Körperoperation mit diesen Elementen machen.

01:07:30.760 --> 01:07:34.480
Ich kann addieren, subtrahieren, multiplizieren und dividieren.

01:07:36.920 --> 01:07:43.120
Das Polynom selber ist dann ja auch so ein Element von diesem Bereich,

01:07:43.580 --> 01:07:49.580
weil ich hier ausgehend von meinen Elementen, ich habe hier also die

01:07:49.580 --> 01:07:53.020
einzelnen Koeffizienten a0 bis an drin stehen, die werden

01:07:53.020 --> 01:07:55.260
multipliziert mit solchen x-Werten.

01:07:55.380 --> 01:07:57.720
Die x-Werte werden auch noch wieder oder die x-Variaten werden

01:07:57.720 --> 01:07:58.420
multipliziert.

01:07:58.420 --> 01:08:05.060
Das sind alles Operationen, die ich in dieser transcendenten

01:08:05.060 --> 01:08:06.620
Körpererweiterung von f machen kann.

01:08:07.760 --> 01:08:11.020
Und ich kann also auch Polynome durcheinander dividieren.

01:08:11.140 --> 01:08:13.740
Alle diese Operationen sind hier erlaubt.

01:08:14.020 --> 01:08:14.940
Mehr heißt das nicht.

01:08:15.140 --> 01:08:18.520
Ich darf also diese vier arithmetischen Operationen, Addition,

01:08:18.740 --> 01:08:24.240
Subtraktion, Multiplikation, Division, beliebig ausführen auf

01:08:24.240 --> 01:08:30.180
irgendwelchen Ausdrücken, in denen diese einzelnen Zahlen vorkommen.

01:08:32.300 --> 01:08:36.260
Jetzt weiß ich also, was ein allgemeines Polynom Endengerades über f

01:08:36.260 --> 01:08:36.600
ist.

01:08:37.920 --> 01:08:43.680
Und die Auswertung des allgemeinen Polynoms Endengerades ist nun

01:08:43.680 --> 01:08:54.020
gerade die Konstruktion dieses Elementes ausgehend von einer Teilmenge

01:08:54.020 --> 01:08:54.660
b.

01:08:57.320 --> 01:09:02.560
Das heißt, ich habe irgendeine Menge von Elementen zur Verfügung und

01:09:02.560 --> 01:09:06.960
überlege mir, wie kann ich ausgehend von dieser Teilmenge durch

01:09:06.960 --> 01:09:11.040
Anwendung der arithmetischen Operationen mein Element Summe a i x hoch

01:09:11.040 --> 01:09:11.520
i bekommen.

01:09:13.220 --> 01:09:18.460
Wenn das b zum Beispiel gleich das f, also diese Körpererweiterung

01:09:18.460 --> 01:09:23.020
wäre, das f von x a 0 bis a n, dann wäre das ja schon ein Element

01:09:23.020 --> 01:09:26.520
meines Ausgangsbereiches, dann bräuchte ich gar nichts zu tun.

01:09:26.580 --> 01:09:28.160
Dann greife ich es mir einfach her und ich habe es.

01:09:29.700 --> 01:09:31.300
Dann brauche ich keine Operation auszuführen.

01:09:31.300 --> 01:09:35.100
Wenn das b aber ganz elementar ist, muss ich sehr viele Operationen

01:09:35.100 --> 01:09:36.120
ausführen, um dahin zu kommen.

01:09:37.360 --> 01:09:38.580
Gebe ich Ihnen gleich Beispiele.

01:09:38.720 --> 01:09:39.440
Also nochmal für f.

01:09:42.080 --> 01:09:45.300
Typische Beispiele wären...

01:09:45.920 --> 01:09:47.720
Also wieso schraube ich denn hier z hin?

01:09:47.980 --> 01:09:49.740
Z ist natürlich...

01:09:50.580 --> 01:09:52.440
Z ist ein Ring, ist kein Körper.

01:09:53.640 --> 01:09:57.460
Ja, aber q und r oder endliche Körper.

01:09:57.460 --> 01:10:01.120
Also, das z vergessen wir mal.

01:10:01.700 --> 01:10:02.520
Das ist nur ein Ring.

01:10:03.780 --> 01:10:05.120
Ich weiß nicht, warum ich das da hingeschrieben habe.

01:10:09.450 --> 01:10:09.970
Also...

01:10:14.080 --> 01:10:20.980
Wer von Ihnen weiß nicht, was hier der gf 2 oder gf 2 8 verbirgt,

01:10:21.120 --> 01:10:21.780
wissen Sie nicht.

01:10:21.980 --> 01:10:22.560
Sie wissen das.

01:10:23.400 --> 01:10:23.900
Auch nicht.

01:10:25.840 --> 01:10:27.520
Gf steht für Galower Feld.

01:10:28.520 --> 01:10:30.980
Haben Sie schon mal was von einem Herrn Galower gehört?

01:10:31.820 --> 01:10:32.300
Auch nicht.

01:10:34.140 --> 01:10:37.660
Also, Herr Galower war ein französischer Mathematiker.

01:10:38.680 --> 01:10:42.960
Das steht also für Galower Feld.

01:10:45.440 --> 01:10:47.280
Also Feld für Körper.

01:10:49.680 --> 01:10:53.940
Und der Herr Galower war ein französischer Mathematiker, der einige

01:10:53.940 --> 01:10:55.140
geniale Ideen hatte.

01:10:56.880 --> 01:10:59.000
Leider ist er früh verstorben.

01:10:59.720 --> 01:11:00.840
Und zwar hat er sich duelliert.

01:11:02.380 --> 01:11:07.860
Der war höchstens in den 20ern, ich glaube sogar weniger als 20 Jahre

01:11:07.860 --> 01:11:08.400
alt geworden.

01:11:09.020 --> 01:11:11.540
Hat aber sehr viele interessante Ideen gehabt.

01:11:11.720 --> 01:11:15.620
Hat die alle aufgeschrieben auf Zetteln.

01:11:17.100 --> 01:11:19.900
Und da hat er die Theorie der Körpererweiterung aufgeschrieben.

01:11:20.680 --> 01:11:23.380
Wie kann ich also ausgehen von einem ganz einfachen Körper,

01:11:23.960 --> 01:11:27.220
meinetwegen nur mit zwei Elementen, 0 und 1.

01:11:27.700 --> 01:11:29.520
Aus 0 und 1 kann ich einen Körper machen.

01:11:30.780 --> 01:11:34.660
Das ist also Gf2, der kleinste Körper.

01:11:34.940 --> 01:11:38.580
Also Körper heißt wieder Addition, Multiplikation und die Inverse

01:11:38.580 --> 01:11:39.340
müssen auch da sein.

01:11:40.620 --> 01:11:44.980
Wie kann ich sukzessive so einen Körper erweitern zu den

01:11:44.980 --> 01:11:46.340
nächstgrößeren Körpern?

01:11:46.340 --> 01:11:52.000
Und da kommt man darauf, dass man für bestimmte, wie jede Zweierpotenz

01:11:52.000 --> 01:11:54.320
zum Beispiel, einen Körper erzeugen kann.

01:11:54.760 --> 01:11:55.860
Das sind dann endliche Körper.

01:11:57.840 --> 01:12:01.360
Und im Prinzip geht es darum, ob man den...

01:12:01.360 --> 01:12:04.340
Also man kann das so formulieren, ich möchte...

01:12:05.180 --> 01:12:08.340
das ist jetzt ein bisschen weit hergeholt vielleicht...

01:12:09.840 --> 01:12:20.700
Es geht um Konstruktionen mit Zirkel und Lineal.

01:12:21.700 --> 01:12:23.600
Das steckt im Prinzip dahinter.

01:12:23.840 --> 01:12:29.380
Man hat sich überlegt, wie kann ich irgendwelche Winkel mit Zirkel und

01:12:29.380 --> 01:12:30.360
Lineal aufteilen.

01:12:31.740 --> 01:12:33.360
Das kann man mathematisch aufschreiben.

01:12:33.980 --> 01:12:36.480
Da kann man die Theorie der Körpererweiterung sich überlegen.

01:12:37.940 --> 01:12:40.460
Und der Herr Gallower hat das alles gemacht, hat das alles

01:12:40.460 --> 01:12:41.580
aufgeschrieben.

01:12:42.100 --> 01:12:44.560
Man hat dann diese Zettel bei ihm gefunden, als er leider beim Duell

01:12:44.560 --> 01:12:45.300
ums Leben kam.

01:12:47.080 --> 01:12:50.320
Und hat das dann weiter ausgeführt und das ist die Theorie der

01:12:50.320 --> 01:12:51.460
Gallower Felder geworden.

01:12:52.340 --> 01:12:53.700
Der hat irgendwann im 18.

01:12:53.880 --> 01:12:54.840
Jahrhundert, glaube ich, gelebt.

01:12:58.420 --> 01:13:00.900
Und diese Gallower Felder spielen eine große Rolle.

01:13:01.560 --> 01:13:02.520
Das sind endliche Körper.

01:13:02.680 --> 01:13:03.480
Warum spielen die eine Rolle?

01:13:03.480 --> 01:13:08.260
In der Informatik haben wir häufig Zahlenbereiche, die endlich sind.

01:13:09.360 --> 01:13:14.120
Wir haben zum Beispiel, wenn Sie in Java sich überlegen, ganz zahlige

01:13:14.120 --> 01:13:17.540
Bereiche wie Byte oder Short.

01:13:18.160 --> 01:13:19.240
Short heißt das, glaube ich.

01:13:19.840 --> 01:13:21.080
Das ist gerade 8 Bit.

01:13:21.780 --> 01:13:26.100
Oder Sie haben Normal Integer oder Sie haben Long Integer.

01:13:26.360 --> 01:13:27.520
Ich weiß gar nicht, wie das da heißt.

01:13:27.520 --> 01:13:31.440
Jedenfalls haben Sie unterschiedliche Zahlenbereiche, je nachdem wie

01:13:31.440 --> 01:13:33.800
viele Bits Sie zur Verfügung stellen, für die Darstellung der

01:13:33.800 --> 01:13:34.520
einzelnen Zahl.

01:13:35.640 --> 01:13:37.060
Das sind also endliche Bereiche.

01:13:37.980 --> 01:13:40.800
Und es ist interessant zu sehen, wie kann ich eigentlich darauf, auf

01:13:40.800 --> 01:13:44.740
diesen endlichen Bereichen rechnen, dort also Operationen ausführen,

01:13:44.940 --> 01:13:47.020
ohne dass ich aus dem Bereich rauslaufe.

01:13:47.840 --> 01:13:51.760
Also kann ich dort addieren, multiplizieren, dividieren, ohne dass ich

01:13:51.760 --> 01:13:54.340
aus dem Bereich rauslaufe, sondern ich bleibe immer schön in meinem

01:13:54.340 --> 01:13:58.640
Bereich von meinetwegen 208 Elementen.

01:13:59.340 --> 01:14:01.640
Sowas braucht man in der ganzen Reihe von Anwendungen.

01:14:02.540 --> 01:14:04.500
Eine wichtige Anwendung ist heute die Kryptographie.

01:14:05.160 --> 01:14:14.120
Der AES-Algorithmus, Advanced Encryption Standard, setzt insbesondere

01:14:14.120 --> 01:14:21.920
Arithmetik im Galois-Feld 208 ein, einfach weil dort auf Bytes

01:14:21.920 --> 01:14:22.700
operiert wird.

01:14:23.540 --> 01:14:30.420
Kann man über diese GF 208 Arithmetik darstellen.

01:14:32.140 --> 01:14:35.260
Und insofern sind das Bereiche, die muss jeder, der sich mit

01:14:35.260 --> 01:14:39.620
Informatik beschäftigt, eigentlich kennen, weil man damit sehr viel

01:14:39.620 --> 01:14:42.480
machen kann, was mit endlichen Zahlenbereichen zu tun hat.

01:14:42.580 --> 01:14:44.740
Und als Informatiker beschäftigt man sich sehr viel mit endlichen

01:14:44.740 --> 01:14:45.480
Zahlenbereichen.

01:14:48.100 --> 01:14:49.880
Gut, Galois-Felder.

01:14:50.180 --> 01:14:52.680
Sie sehen, ich muss ein bisschen ausholen an verschiedenen Stellen.

01:14:54.800 --> 01:14:57.840
Jetzt haben wir also hier...

01:14:59.560 --> 01:15:02.140
Es ging darum, dass wir irgendwelche Körper zugrunde liegen haben.

01:15:02.700 --> 01:15:05.740
Wenn wir vom Polynom reden, meinen wir normalerweise, naja, da habe

01:15:05.740 --> 01:15:07.660
ich wahrscheinlich irgendwelche reellen Zahlen drin.

01:15:08.800 --> 01:15:10.620
Ich könnte auch komplexe Zahlen noch drin haben.

01:15:10.800 --> 01:15:14.160
Also wie gesagt, Zahlenbereiche, die dort vorkommen können für F, sind

01:15:14.160 --> 01:15:17.300
irgendwelche dieser uns bekannten Zahlenbereiche.

01:15:17.900 --> 01:15:20.720
Und zu den uns bisher bekannten oder Ihnen bisher bekannten sind jetzt

01:15:20.720 --> 01:15:22.300
noch die endlichen Körper dazu getreten.

01:15:24.000 --> 01:15:24.480
Beispiele.

01:15:27.020 --> 01:15:30.500
Hatte ich schon gesagt, wenn diese Menge B, aus der wir etwas

01:15:30.500 --> 01:15:37.000
berechnen wollen, gleich unserem erweiterten Zahlenbereich ist, diesem

01:15:37.000 --> 01:15:41.560
F von 0 bis a n, dann brauchen wir gar nichts zu tun.

01:15:41.660 --> 01:15:48.460
Dann steht uns dieses Element Summe a i x hoch i bereits als Element

01:15:48.460 --> 01:15:52.340
von diesem Körper zur Verfügung.

01:15:53.120 --> 01:15:57.500
Keine Operation erforderlich, um das aus dem zu erzeugen.

01:15:57.780 --> 01:16:01.280
Wenn das B gerade der Körper selbst ist, das sind dann unsere Skalale,

01:16:02.180 --> 01:16:06.560
sowie die Variable x, a 0 bis a n, dann müssen wir einiges tun.

01:16:07.280 --> 01:16:09.760
Dann müssen wir diese Operationen ausführen, zum Beispiel so

01:16:09.760 --> 01:16:11.420
hingeschrieben, wie ich das hier getan habe.

01:16:12.480 --> 01:16:15.260
Sie erinnern sich an unsere erste Vorlesungsstunde.

01:16:16.020 --> 01:16:17.400
Auswertung von links nach rechts.

01:16:17.400 --> 01:16:21.780
Da würden wir das x hoch n als Folge von n-1 Multiplikationen ansehen.

01:16:22.160 --> 01:16:24.700
Hätten wir O von n² arithmetische Operationen.

01:16:26.580 --> 01:16:27.460
Zweite Möglichkeit.

01:16:28.720 --> 01:16:30.120
Ich kann es ja anders anordnen.

01:16:30.260 --> 01:16:34.400
Ich muss nur irgendwie das Element Summe a i x hoch i erzeugen.

01:16:35.720 --> 01:16:38.560
Da kann ich ja auch erstmal erzeugen meine Potenzen.

01:16:39.820 --> 01:16:41.460
x, x² bis x hoch n.

01:16:41.920 --> 01:16:43.400
Dazu brauche ich n Multiplikationen.

01:16:44.720 --> 01:16:46.180
Oder n-1 Multiplikationen.

01:16:47.180 --> 01:16:49.660
Die alle nacheinander zu erzeugen.

01:16:49.960 --> 01:16:53.380
Das sind also n-1 verschiedene neue Werte, die ich brauche.

01:16:53.800 --> 01:16:55.140
Genau die erzeuge ich mir hier.

01:16:56.040 --> 01:16:57.060
Die brauche ich sicherlich.

01:16:58.580 --> 01:17:03.600
Und dann berechne ich die Produkte a 1 x, a 2 x² bis a n x hoch n.

01:17:04.620 --> 01:17:06.240
Nochmal n Multiplikationen.

01:17:07.300 --> 01:17:08.940
Und dann addiere ich die einfach.

01:17:10.060 --> 01:17:11.500
Hier, das ist meine Addition.

01:17:12.300 --> 01:17:13.800
n-1 Addition.

01:17:13.900 --> 01:17:18.500
Ich habe 3 n-1 arithmetische Operationen, um das auszuwerten.

01:17:19.280 --> 01:17:20.500
Der dritte...

01:17:21.060 --> 01:17:23.120
Also hier nochmal zur Auswertung ist klar.

01:17:23.660 --> 01:17:27.900
Wenn ich jetzt das b ein bisschen erweitern würde, und würde hier als

01:17:27.900 --> 01:17:35.180
Ausgangselemente auch alle rationalen Funktionen über x mit zulassen,

01:17:36.320 --> 01:17:39.720
dann hätte ich die Potenzen automatisch mit drin und bräuchte nur

01:17:39.720 --> 01:17:43.420
diese beiden Schritte zu machen, weil ich ja die Potenzen bereits zur

01:17:43.420 --> 01:17:43.960
Verfügung hätte.

01:17:45.600 --> 01:17:46.320
Das ist einfach nur...

01:17:47.220 --> 01:17:52.380
Also man spielt praktisch mit den Informationen, die ich zur Verfügung

01:17:52.380 --> 01:17:55.180
habe, um ein Problem zu lösen.

01:17:56.140 --> 01:17:58.740
Und das ist eine der elementarsten Dinge, wenn ich einen Algorithmus

01:17:58.740 --> 01:18:02.800
entwerfe, dass ich mir anschaue, welche Informationen stehen mir über

01:18:02.800 --> 01:18:05.500
meine Problemstellung eigentlich zur Verfügung.

01:18:06.140 --> 01:18:08.140
Und die versuche ich möglichst gut auszunutzen.

01:18:09.560 --> 01:18:12.060
Und das, was mir zur Verfügung steht an Informationen, ist also über

01:18:12.060 --> 01:18:15.180
das b jeweils hier charakterisiert.

01:18:16.800 --> 01:18:19.980
Je mehr Informationen ich habe, desto weniger muss ich noch dazufügen.

01:18:22.500 --> 01:18:24.280
Vornerschema hatte ich Ihnen ja schon mal vorgestellt.

01:18:24.420 --> 01:18:28.420
Das ist hier also eine einfache algorithmische Formulierung des

01:18:28.420 --> 01:18:29.120
Vornerschemas.

01:18:30.020 --> 01:18:31.000
So könnte man es auch machen.

01:18:31.000 --> 01:18:40.060
Dann fange ich an mit a n und modifiziere dann sukzessive mit x und

01:18:40.060 --> 01:18:41.200
füge noch ein a i dazu.

01:18:43.600 --> 01:18:45.740
Sie sehen also, Sie könnten das hier genauso gut als

01:18:45.740 --> 01:18:49.320
Rekurrenzgleichung aufschreiben, könnten dann mit diesem Mappingansatz

01:18:49.320 --> 01:18:54.160
unterschiedlichste Algorithmen erzeugen, auf Parallelrechnung für

01:18:54.160 --> 01:18:55.520
dieses Schema.

01:18:57.200 --> 01:19:00.180
So, jetzt haben wir das Problem ein bisschen genauer angeguckt.

01:19:01.000 --> 01:19:04.440
Hier ist klar, braucht man nur zwei n arithmetische Operationen, das

01:19:04.440 --> 01:19:05.120
ist ganz einfach.

01:19:07.480 --> 01:19:09.500
Und die Frage ist, kann man es noch mehr reduzieren?

01:19:10.600 --> 01:19:11.260
Geht das noch besser?

01:19:11.540 --> 01:19:14.840
Bei der Matrixmultiplikation haben wir gesehen, man muss vorsichtig

01:19:14.840 --> 01:19:15.200
sein.

01:19:16.520 --> 01:19:17.760
Jetzt kommen wir zu unteren Schranken.

01:19:18.880 --> 01:19:20.200
Also das ist heute ein bisschen mathematisch.

01:19:23.540 --> 01:19:27.900
Aber ich erwarte nicht, dass Sie jetzt den Satz, den ich Ihnen hier

01:19:27.900 --> 01:19:31.040
zeige, dass Sie den Beweis, den ich Ihnen auch zeigen werde, dass Sie

01:19:31.040 --> 01:19:33.740
den später hin- und auswendig beherrschen.

01:19:34.740 --> 01:19:39.370
Aber was ich Ihnen vermitteln muss, ist, dass es Möglichkeiten gibt,

01:19:40.000 --> 01:19:42.200
auch etwas zu sagen über untere Schranken.

01:19:42.920 --> 01:19:45.390
Oder eben auch diese anderen Dinge, wie kann ich es charakterisieren,

01:19:45.900 --> 01:19:48.720
dass ich bestimmte Informationen über ein Problem zur Verfügung habe.

01:19:49.660 --> 01:19:55.260
Hier wird ein Satz formuliert, ein sehr alter Satz, schon 52 Jahre

01:19:55.260 --> 01:19:57.240
alt, von Ostrowski.

01:19:58.520 --> 01:20:00.320
Der hat folgendes gesagt.

01:20:01.300 --> 01:20:04.560
Jeder Algorithmus für die Auswertung des allgemeinen Polynoms,

01:20:05.600 --> 01:20:10.480
Entengrades, in F von, es steht das hier in eckigen Klammern, vorher

01:20:10.480 --> 01:20:11.380
waren das runde Klammern.

01:20:12.280 --> 01:20:15.520
Das hat durchaus Bedeutung, ob ich dort runde oder eckige Klammern

01:20:15.520 --> 01:20:15.850
hinschreibe.

01:20:17.020 --> 01:20:20.000
Die eckigen Klammern beziehen sich auf einen Polynom Ring.

01:20:21.600 --> 01:20:25.100
Mit runden Klammern war das der Körper, hier ist es nur ein Ring.

01:20:25.100 --> 01:20:29.900
Das heißt, ich habe bei der Addition auch die Inversen zur Verfügung,

01:20:30.180 --> 01:20:33.200
bei der Multiplikation aber nicht die Inversen zur Verfügung.

01:20:33.440 --> 01:20:36.520
Da habe ich nur die Multiplikation.

01:20:37.700 --> 01:20:41.480
Ich kann also die Division nicht anwenden.

01:20:42.280 --> 01:20:48.060
Wenn ich also in diesem Zahlbereich das allgemeine Polynom Entengrades

01:20:48.060 --> 01:20:53.180
auswerten möchte, ohne Verwendung der Division, weil das nur ein

01:20:53.180 --> 01:20:58.760
Polynom Ring ist, ausgehend vom Polynom Ring, der nur durch

01:20:58.760 --> 01:21:02.880
Erweiterung mit x entsteht, und noch diesen Variablen oder

01:21:02.880 --> 01:21:06.520
Koeffizienten a0 bis an, dann brauche ich dafür mindestens n

01:21:06.520 --> 01:21:07.740
Additionen.

01:21:10.270 --> 01:21:16.970
Das heißt, wenn ich das weiß, weiß ich, egal wie ich meine Berechnung

01:21:16.970 --> 01:21:20.090
mache, ich muss mindestens n Additionen ausführen.

01:21:23.900 --> 01:21:27.300
Also hier steht es nochmal, Berechnung mit Polynom Ringen, angedeutet

01:21:27.300 --> 01:21:31.200
durch die eckigen Klammern, mathematische Standardnotation, keine

01:21:31.200 --> 01:21:32.420
Division erlaubt.

01:21:33.900 --> 01:21:40.920
Und aufbauend auf diesen Satz hat Pahn 1966 gezeigt,

01:21:45.040 --> 01:21:51.340
dass man auch für die Multiplikation gilt, dass man mindestens n

01:21:51.340 --> 01:21:52.600
Multiplikationen braucht.

01:21:53.920 --> 01:21:57.220
Und er hat gezeigt, dass für die Berechnung des Polynoms in jetzt

01:21:57.220 --> 01:22:03.080
wieder dem Körper, ausgehend von, selbst wenn man auf diese

01:22:03.080 --> 01:22:08.120
Einschränkung mit den Divisionen verzichtet, dann ist das Horner

01:22:08.120 --> 01:22:11.400
Schema ein optimaler Algorithmus in Bezug auf die Anzahl der

01:22:11.400 --> 01:22:12.600
Multiplikationen und Divisionen.

01:22:13.700 --> 01:22:23.280
Das heißt, ich kann nicht unter diese Mindestzahl von n Additionen und

01:22:23.280 --> 01:22:24.800
n Multiplikationen kommen.

01:22:25.460 --> 01:22:27.880
Das Horner Schema erreicht genau diese Zahl.

01:22:27.880 --> 01:22:33.760
Das heißt, mit dem Horner Schema habe ich einen Algorithmus, der ein

01:22:33.760 --> 01:22:39.920
Problem exakt mit so vielen Operationen löst, wie ich als untere

01:22:39.920 --> 01:22:41.560
Schranken nachweisen kann.

01:22:43.740 --> 01:22:49.940
Nun weiß man, es geht nicht besser, wenn ich nicht mehr weiß, dass ich

01:22:49.940 --> 01:22:52.500
n Koeffizienten habe und eine Variable.

01:22:52.500 --> 01:22:56.160
Ich kann die Anzahl der Additionen und Multiplikationen nicht

01:22:56.160 --> 01:22:58.160
reduzieren, egal wie ich mich anstrenge.

01:23:00.740 --> 01:23:08.420
Damit habe ich eben den Satz, dass ich mit dem Horner Schema optimal

01:23:08.420 --> 01:23:08.860
bin.

01:23:09.580 --> 01:23:13.440
Selbst wenn ich alle möglichen Potenzen zulasse von x, das steht da

01:23:13.440 --> 01:23:16.640
noch, selbst dann ist das Horner Schema noch optimal.

01:23:17.720 --> 01:23:21.640
Ich brauche mindestens diese n Multiplikationen und Additionen.

01:23:22.540 --> 01:23:28.600
Das ist also eine wichtige Erkenntnis, dass man hier bei einem Problem

01:23:28.600 --> 01:23:31.620
tatsächlich die Übereinstimmung von oberen und unteren Schranken

01:23:31.620 --> 01:23:32.200
hinbekommt.

01:23:34.620 --> 01:23:37.700
Ich will Ihnen einfach zeigen, wie man so etwas machen kann.

01:23:38.940 --> 01:23:43.020
Wie man zeigen kann, dass man diese Mindestanzahl von Additionen

01:23:43.020 --> 01:23:43.340
braucht.

01:23:43.340 --> 01:23:46.140
Das ist hier unser Polynom.

01:23:52.500 --> 01:23:55.140
Jetzt vereinfachen wir das Problem einfach.

01:23:56.460 --> 01:23:57.920
Wie kann ich das vereinfachen?

01:23:58.380 --> 01:24:00.660
Ich ersetze einfach das x durch 1.

01:24:02.920 --> 01:24:06.140
Das ist ein spezieller Wert, ein spezielles Polynom.

01:24:07.220 --> 01:24:13.840
Wenn ich auch für das spezielle Polynom, also für mein Problem, bei

01:24:13.840 --> 01:24:18.620
dem ich jetzt das x mit 1 substituiert habe, zeigen kann, ich brauche

01:24:18.620 --> 01:24:22.440
die mindestens n Additionen, dann brauche ich sicherlich diese n

01:24:22.440 --> 01:24:25.140
Additionen auch für das allgemeinere Problem.

01:24:26.120 --> 01:24:27.040
Das wird ja nicht einfacher.

01:24:28.140 --> 01:24:30.380
Ich habe also angenommen, ich habe irgendeinen ganz beliebigen

01:24:30.380 --> 01:24:32.660
Algorithmus zur Auswertung dieses Polynoms.

01:24:32.660 --> 01:24:39.440
Und betrachte diesen Algorithmus jetzt an der Stelle, wo x den Wert 1

01:24:39.440 --> 01:24:39.740
hat.

01:24:40.620 --> 01:24:45.340
Dann habe ich jetzt also ein Algorithmus A' der berechnet mein Polynom

01:24:45.340 --> 01:24:48.600
enden gerades für x gleich 1.

01:24:49.100 --> 01:24:51.440
Das wäre dann natürlich nur noch die Summe dieser Ai.

01:24:52.160 --> 01:24:55.200
Das heißt, die Aussage reduziert sich darauf, die ich beweisen möchte.

01:24:55.920 --> 01:25:00.920
Die Summe dieser Ai kann ich nur berechnen mit n Additionen.

01:25:01.540 --> 01:25:02.660
Anders geht es nicht.

01:25:05.380 --> 01:25:09.220
Und es ist offensichtlich, dass das A' nicht mehr Additionen brauchen

01:25:09.220 --> 01:25:10.920
wird als der Originalalgorithmus.

01:25:11.700 --> 01:25:13.640
Ich habe ja höchstens etwas reduziert, ich habe nichts Neues

01:25:13.640 --> 01:25:14.340
dazugefügt.

01:25:15.760 --> 01:25:19.800
Und die Behauptung ist also, dass ich hierfür mindestens n Additionen

01:25:19.800 --> 01:25:20.160
brauche.

01:25:21.400 --> 01:25:23.340
Das beweisen Sie induktiv über n.

01:25:24.060 --> 01:25:27.240
Für n gleich 0 habe ich eine leere Summe, da brauche ich gar nichts zu

01:25:27.240 --> 01:25:27.380
tun.

01:25:27.380 --> 01:25:29.620
Beziehungsweise habe ich nur das A0 stehen, da brauche ich gar nichts

01:25:29.620 --> 01:25:30.100
zu addieren.

01:25:30.880 --> 01:25:34.460
Und jetzt nehme ich an, dass ich einen Algorithmus habe, einen

01:25:34.460 --> 01:25:38.740
Algorithmus B, irgendeinen, der tatsächlich in der Lage ist, diese

01:25:38.740 --> 01:25:45.080
Summe bis n plus 1 mit weniger als n plus 1 Additionen zu berechnen.

01:25:46.920 --> 01:25:49.060
Und das ist jetzt auch ein Standardansatz.

01:25:50.000 --> 01:25:53.360
Ich habe ja irgendeinen solchen Algorithmus mir hergenommen, der kann

01:25:53.360 --> 01:25:55.660
das mit weniger als n plus 1 Additionen.

01:25:55.660 --> 01:25:59.360
Aber irgendwann habe ich die erste Addition zu machen in dem

01:25:59.360 --> 01:25:59.900
Verfahren.

01:26:00.860 --> 01:26:05.100
Und ich schaue mir einfach an, die erste Addition im Algorithmus B.

01:26:09.200 --> 01:26:11.560
Die erste Addition, d.h.

01:26:11.700 --> 01:26:13.940
davor habe ich nur Multiplikationen ausgeführt.

01:26:15.100 --> 01:26:19.240
Wenn ich nur Multiplikationen ausführe auf diesen A0 bis A n plus 1,

01:26:19.240 --> 01:26:24.240
dann habe ich also irgendein Produkt oder irgendwelche zwei Produkte,

01:26:25.580 --> 01:26:29.920
der A0 bis A n plus 1, die jetzt addiert werden.

01:26:30.660 --> 01:26:37.140
Diese Produkte können so formuliert werden, dass dort sicherlich jeder

01:26:37.140 --> 01:26:41.080
einzelne Koeffizient kann eventuell dort mehrfach multipliziert worden

01:26:41.080 --> 01:26:41.480
sein.

01:26:41.900 --> 01:26:42.140
D.h.

01:26:42.200 --> 01:26:46.660
ich habe dort irgendein Potenz stehen, das Ri, also irgendein Potenz

01:26:46.660 --> 01:26:47.640
von dem Ai.

01:26:49.540 --> 01:26:51.880
Und die sind alle irgendwie multipliziert.

01:26:51.960 --> 01:26:54.520
Kann sein, dass eine ganze Reihe von diesen Ri's Null sind.

01:26:54.680 --> 01:26:54.900
D.h.

01:26:55.080 --> 01:26:56.720
einige Koeffizienten tauchen gar nicht auf.

01:26:58.400 --> 01:27:01.360
Aber ich habe auf jeden Fall irgend solche Produkte, diese

01:27:01.360 --> 01:27:03.840
Koeffizienten, die werden jetzt addiert in dem Verfahren.

01:27:05.000 --> 01:27:07.640
Es kann sein, dass einfach nur A1 mit A2 multipliziert wird.

01:27:08.680 --> 01:27:10.860
Es kann auch sein, dass da deutlich größere Ausflüge stehen.

01:27:11.480 --> 01:27:17.760
Also diese C1,

01:27:21.100 --> 01:27:21.860
C2...

01:27:22.560 --> 01:27:24.880
Wieso habe ich denn hier C1, C2 nicht drin stehen?

01:27:28.170 --> 01:27:34.370
Also eigentlich müsste dort noch drinstehen C1 mal diesen Pi1 von A

01:27:34.370 --> 01:27:37.250
und C2 mal diesen Pi2 von A.

01:27:38.510 --> 01:27:40.830
Das muss an irgendeiner Stelle mal rausgefallen sein.

01:27:41.130 --> 01:27:41.710
Tut mir leid.

01:27:42.030 --> 01:27:43.990
Ich kann ja auch mit Skalaren multiplizieren.

01:27:44.830 --> 01:27:47.550
Ja, also deswegen steht ja das C1 und C2.

01:27:49.050 --> 01:27:51.310
Das steht im Prinzip hier noch davor.

01:27:51.430 --> 01:27:54.670
C1 mal dem plus C2 mal dem anderen.

01:27:55.350 --> 01:27:57.010
Werden auch Produkte, die erlaubt sind.

01:27:58.270 --> 01:28:02.410
Und die Ri, Si sind, wie gesagt, das sind die Exponenten.

01:28:03.490 --> 01:28:08.670
Und jetzt nehmen wir an, dass das Rn plus 1 ungleich Null ist.

01:28:08.670 --> 01:28:14.950
Das heißt, es wird insbesondere der Koeffizient An plus 1 verwendet.

01:28:15.070 --> 01:28:17.750
Und zwar in dem ersten Summanden.

01:28:18.570 --> 01:28:21.630
In diesem ersten Summanden hier, Pi1 von A quer.

01:28:22.170 --> 01:28:24.290
Da nehmen wir an, kommt das An plus 1 vor.

01:28:26.150 --> 01:28:28.530
Und jetzt kommt der nächste Trick.

01:28:29.990 --> 01:28:32.430
Ich ersetze einfach An plus 1 durch Null.

01:28:34.290 --> 01:28:37.330
Das darf ich, weil ich keine Division erlaubt habe.

01:28:38.810 --> 01:28:41.010
Das sind ja nur Modifikationen vorgekommen.

01:28:41.710 --> 01:28:42.450
Keine Division.

01:28:43.350 --> 01:28:46.350
Ich ersetze einfach das An plus 1 durch Null.

01:28:46.430 --> 01:28:49.090
Ich weiß, das tauchte in dem ersten Summanden auf.

01:28:49.610 --> 01:28:54.050
Wenn ich das An plus 1 durch Null ersetze, dann habe ich den

01:28:54.050 --> 01:28:56.010
Algorithmus an einer bestimmten Stelle betrachtet.

01:28:57.350 --> 01:29:01.030
Und für den Fall, dass das An plus 1 gleich Null ist, und das tauchte

01:29:01.030 --> 01:29:05.930
ja in dem Pi1 von A quer auf, wird natürlich das Pi1 von A quer zu

01:29:05.930 --> 01:29:06.210
Null.

01:29:08.330 --> 01:29:09.810
Zu einem Faktor.

01:29:10.190 --> 01:29:13.110
Wenn der Null ist, ist das ganze Produkt Null.

01:29:14.510 --> 01:29:17.910
Und damit habe ich diese erste Addition eliminiert.

01:29:20.310 --> 01:29:28.010
Wenn das An plus 1 aber nicht vorkommt in diesem linken Term, also

01:29:28.010 --> 01:29:31.390
mindestens in dem linken, hatte ich angenommen, taucht es auf.

01:29:31.470 --> 01:29:34.170
Wenn es auch in dem rechten vorgekommen wäre, wäre es auch eliminiert.

01:29:34.250 --> 01:29:36.810
Aber ich habe auf jeden Fall die erste Addition eliminiert.

01:29:37.650 --> 01:29:40.770
Und dann weiß ich, dass ich jetzt den Algorithmus betrachte, B an der

01:29:40.770 --> 01:29:42.330
Stelle An plus 1 gleich Null.

01:29:43.850 --> 01:29:49.090
Wenn aber An plus 1 gleich Null ist, dann wird berechnet eine Summe i

01:29:49.090 --> 01:29:50.490
gleich Null bis N a i.

01:29:51.550 --> 01:29:53.490
Ich habe aber die erste Addition eliminiert.

01:29:53.490 --> 01:29:56.470
Ich habe also jetzt k-1 Additionen.

01:29:57.750 --> 01:30:01.670
Und k-1 ist dann kleiner als N.

01:30:02.750 --> 01:30:10.130
Und damit habe ich die Summe meiner a i von i gleich Null bis N mit N

01:30:10.130 --> 01:30:17.110
-1, also mit weniger als N Additionen berechnet.

01:30:17.430 --> 01:30:19.190
Also k-1 ist kleiner als N.

01:30:19.950 --> 01:30:25.590
Und damit habe ich einen Widerspruch zu der Induktionsannahme, dass

01:30:25.590 --> 01:30:29.490
ich für die Auswertung oder für die Berechnung von Summe i gleich Null

01:30:29.490 --> 01:30:31.950
bis N a i mindestens N Additionen brauche.

01:30:32.710 --> 01:30:37.550
Also kann es nicht sein, dass ich einen Algorithmus habe, der die

01:30:37.550 --> 01:30:41.250
Summe bis N plus 1 mit weniger als N plus 1 Additionen berechnet.

01:30:41.410 --> 01:30:45.390
Damit habe ich das bewiesen, dass ich für diese Summe mindestens N

01:30:45.390 --> 01:30:47.290
Additionen brauche.

01:30:48.510 --> 01:30:49.850
Ist ein bisschen kompliziert.

01:30:50.510 --> 01:30:53.410
Zeigt nur, untere Schranken zu beweisen ist nicht einfach.

01:30:54.010 --> 01:30:54.850
Aber man kann es machen.

01:30:55.910 --> 01:30:59.010
Ja, und ich garantiere Ihnen, ich werde nur an einer einzigen Stelle

01:30:59.010 --> 01:31:01.130
nochmal eine untere Schranke beweisen, nämlich beim Sortieren.

01:31:01.550 --> 01:31:03.070
Aber das geht ganz einfach.

01:31:04.190 --> 01:31:04.670
In dem Fall.

01:31:04.970 --> 01:31:07.430
Das hier war ein bisschen kompliziert, weil Mathematik muss man

01:31:07.430 --> 01:31:07.970
manchmal machen.

01:31:08.170 --> 01:31:10.890
Aber Sie sehen, man macht das, um eigentlich ganz einfache

01:31:10.890 --> 01:31:13.650
Eigenschaften irgendwie formulieren zu können.

01:31:14.410 --> 01:31:15.210
Das war's für heute.

01:31:15.290 --> 01:31:15.630
Vielen Dank.