WEBVTT

00:02.100 --> 00:09.240
...und das richtige erste Kapitel aufrufen.

00:09.660 --> 00:12.360
Da sehen Sie, geht es los mit der Einführung.

00:13.820 --> 00:16.920
Vielleicht kurz noch mal die Frage, ist von Ihnen irgendetwas

00:16.920 --> 00:20.360
Organisatorisches noch nachzufragen?

00:20.460 --> 00:21.520
Ist Ihnen irgendwas unklar geblieben?

00:22.120 --> 00:25.240
Wenn irgendwas ist, können Sie sich ja problemlos melden.

00:25.240 --> 00:27.560
So, Einführung.

00:28.100 --> 00:30.600
Hier steht noch mal kurz, was im Vorlesungskommentar aufgeführt ist.

00:31.160 --> 00:34.160
Es geht um eigentlich eine Kernaufgabe für Wirtschaftsingenieure.

00:34.260 --> 00:38.040
Wirtschaftsingenieure sollen ja Abläufe in verschiedensten Stellen,

00:38.160 --> 00:41.720
wirtschaftlichen Bereichen, möglichst kostengünstig planen und

00:41.720 --> 00:45.880
gestalten.

00:46.640 --> 00:48.340
Wir machen das bei Rechnern.

00:49.240 --> 00:51.760
Informationsverarbeitung muss auch möglichst kostengünstig ablaufen,

00:51.760 --> 00:54.660
möglichst effektiv, das heißt die Funktion tatsächlich erfüllen, aber

00:54.660 --> 00:55.560
auch möglichst effizient.

00:56.320 --> 00:59.180
Die Ressourcen müssen möglichst gut ausgenutzt werden, sodass man sich

00:59.180 --> 01:05.700
immer auf der effizientesten Linie der Möglichkeiten bewegt.

01:06.300 --> 01:12.100
Und das, was ich hier mache, was nicht Standard ist, wenn man sich

01:12.100 --> 01:15.780
anschaut, so übliche Vorlesungen über effiziente Algorithmen, das ist

01:15.780 --> 01:19.560
der Teil, der hier unten angesprochen ist, dass sich die Gestaltung

01:19.560 --> 01:22.860
und Bewertung von Algorithmen auf Parallelrechner und Hardware

01:22.860 --> 01:23.400
behandelt.

01:24.340 --> 01:27.700
Es macht sehr viel Sinn, das so zu machen, weil nämlich heutzutage

01:27.700 --> 01:31.040
Algorithmen kaum noch auf sequenziellen Rechnern ausgeführt werden,

01:31.140 --> 01:34.120
sondern in der Regel irgendwo parallel, weil wir ganz viele

01:34.120 --> 01:35.700
Parallelrechner um uns herum stehen haben.

01:36.320 --> 01:39.040
Auch die einzelnen Rechner sind heutzutage sehr häufig schon

01:39.040 --> 01:39.760
Parallelrechner.

01:39.760 --> 01:43.120
Und dann macht es durchaus Sinn, sich mal damit zu beschäftigen, wie

01:43.120 --> 01:48.600
man diese vielfach zur Verfügung stehenden Berechnungseinheiten

01:48.600 --> 01:49.640
sinnvoll nutzen kann.

01:50.540 --> 01:54.600
Also sich nur die Algorithmen sequenziell anzugucken, ist eigentlich

01:54.600 --> 01:56.600
etwas, was nicht mehr ganz zeitgemäß ist.

01:58.460 --> 02:00.860
Schauen wir uns an, was so die Standardaufgaben der

02:00.860 --> 02:02.240
Informationsverarbeitung sind.

02:02.600 --> 02:05.560
Ein Bereich, wichtiger Bereich ist sicherlich, technisch

02:05.560 --> 02:07.020
-wissenschaftliche Berechnungen zu machen.

02:07.020 --> 02:10.520
Und da zählt vieles dazu, zum Beispiel Simulation.

02:11.480 --> 02:17.160
Wenn man komplexe Systeme entwirft, kann man die häufig nicht direkt

02:17.160 --> 02:18.160
bewerten.

02:18.360 --> 02:22.600
Man muss erstmal Dinge simulieren und das muss effizient geschehen.

02:23.180 --> 02:26.140
Man muss etwas visualisieren, im Rechner darstellen, auf dem

02:26.140 --> 02:26.680
Bildschirm.

02:27.440 --> 02:32.040
Das ist nicht immer einfach, auch eine ganz wichtige Aufgabe, um

02:32.040 --> 02:33.980
Verständnis für bestimmte Dinge zu gewinnen.

02:33.980 --> 02:38.060
Man soll etwas optimieren, Standardaufgabe der Wirtschaftsingenieure.

02:38.640 --> 02:41.980
Und auch etwas steuern, in technisch-wissenschaftlichen Bereichen.

02:43.000 --> 02:46.580
Dann gibt es die kommerziell-betriebswirtschaftlichen Bereiche, da

02:46.580 --> 02:48.660
habe ich jetzt einfach mal das Übliche aufgeführt.

02:48.900 --> 02:54.360
Datenverwaltung, Erhebung, Suche, Unternehmensdaten müssen verwaltet

02:54.360 --> 02:54.800
werden.

02:55.380 --> 02:58.640
Es müssen Statistiken erhoben werden, Wissensextraktionen gemacht

02:58.640 --> 03:00.300
werden aus Daten, die zur Verfügung stehen.

03:00.300 --> 03:02.300
Auch hier müssen Daten visualisiert werden, wenn Sie

03:02.300 --> 03:05.560
Wissensextraktionen machen, Data Mining und Ähnliches, dann haben Sie

03:05.560 --> 03:08.080
es mit ähnlichen Aufgaben zu tun, wie in technisch-wissenschaftlichen

03:08.080 --> 03:08.540
Bereichen.

03:09.260 --> 03:11.600
Und auch im kommerziell-betriebswirtschaftlichen Bereich brauchen Sie

03:11.600 --> 03:12.260
Simulationen.

03:12.700 --> 03:15.500
Eigentlich zählt das hier genauso gut hier unten noch ein.

03:15.880 --> 03:18.660
Also das ist nicht nur im technisch-wissenschaftlichen Bereich

03:18.660 --> 03:22.360
wichtig, sondern auch im kommerziell-betriebswirtschaftlichen Bereich.

03:23.740 --> 03:26.520
Kommunikation heutzutage ein wichtiger Lebensbereich.

03:26.520 --> 03:30.280
Wir kommunizieren auf vielfältigste Art und Weise über

03:30.280 --> 03:32.460
unterschiedlichste Ein-Aufgabeschnittstellen.

03:33.460 --> 03:38.680
Wir brauchen grafische Datenverarbeitung, um bestimmte Dinge sinnvoll

03:38.680 --> 03:39.460
darzustellen.

03:39.900 --> 03:42.180
Und wir brauchen Sicherheitsmechanismen.

03:43.020 --> 03:48.140
Und für all das braucht man eine ganze Reihe von Operationen, wie zum

03:48.140 --> 03:49.480
Beispiel hier aufgeführt.

03:50.040 --> 03:53.260
Für technisch-wissenschaftliche Bereiche brauchen Sie Finite-Element

03:53.260 --> 03:53.920
-Methoden.

03:54.500 --> 03:57.120
Wer von Ihnen hat schon mal was von Finite-Element-Methoden gehört?

03:58.060 --> 03:58.820
Noch nicht?

03:58.960 --> 04:03.020
Also wenn Sie zum Beispiel die Tragflächen eines Flugzeugs entwerfen

04:03.020 --> 04:05.900
oder die Oberfläche eines Flugzeugs oder Oberfläche eines Fahrzeugs.

04:07.000 --> 04:09.620
Also Sie haben hier irgend so einen Flügel.

04:10.940 --> 04:16.700
Und um das Verhalten dieses Werkstücks sinnvoll entwerfen zu können,

04:17.080 --> 04:19.020
müssen Sie die Oberfläche simulieren können.

04:19.020 --> 04:20.500
Dazu brauchen Sie viele Punkte.

04:21.400 --> 04:22.840
Und die sind irgendwie verbunden.

04:22.940 --> 04:26.120
Man macht häufig so Dreiecks, Überdeckungen dieser Bereiche wesentlich

04:26.120 --> 04:27.680
feiner, als ich das jetzt hier aufzeichne.

04:28.700 --> 04:34.900
Und hat eine Reihe von Punkten auf der Oberfläche und berechnet das

04:34.900 --> 04:42.940
Verhalten dieser Oberflächen über sogenannte Finite-Element-Methoden.

04:43.100 --> 04:47.480
Das sind praktisch so Darstellungen der Oberflächen von solchen

04:47.480 --> 04:48.240
Objekten.

04:48.240 --> 04:52.480
Und mit Finite-Element-Methoden kann man zum Beispiel Simulationen von

04:52.480 --> 04:53.940
Werkstücken im Windkanal machen.

04:54.400 --> 04:59.520
Und dadurch einiges sehr effizient simulieren.

05:00.060 --> 05:03.620
Was man dafür braucht, sind häufig Multiplikationen von Matrizen und

05:03.620 --> 05:04.100
Vektoren.

05:04.320 --> 05:10.200
Man hat dort numerische Verfahren, bei denen man sehr viel mit

05:10.200 --> 05:11.240
Matrizen umgeht.

05:11.240 --> 05:15.980
Da muss man Matrizen multiplizieren, invertieren, macht Matrix-Vektor,

05:16.480 --> 05:21.880
hat man viele lineare Gleichungssysteme, die man lösen muss.

05:22.100 --> 05:25.240
Das sind einfach solche Operationen, die hier aufgeführt sind, die man

05:25.240 --> 05:26.180
effizient machen muss.

05:27.220 --> 05:31.540
Und viele der Funktionen, die man braucht in technisch

05:31.540 --> 05:35.740
-wissenschaftlichen Bereichen, kann man nicht exakt berechnen oder

05:35.740 --> 05:36.860
exakt auswerten.

05:36.860 --> 05:37.960
Man muss sie approximieren.

05:38.440 --> 05:41.280
In der numerischen Mathematik wird das gemacht.

05:42.620 --> 05:46.040
Und dazu braucht man eben auch geeignete Informatikverfahren, um das

05:46.040 --> 05:46.680
umzusetzen.

05:47.760 --> 05:49.700
Polynome auswerten, auch was Wichtiges.

05:50.440 --> 05:54.500
Wenn Sie Funktionen approximieren, das heißt nicht ganz genau

05:54.500 --> 05:56.820
darstellen, sondern approximieren, machen Sie das in der Regel durch

05:56.820 --> 05:57.640
irgendeinen Polynom.

05:58.820 --> 06:00.880
Irgendeiner Ordnung 2., 4., 6.

06:00.960 --> 06:01.260
oder 8.

06:01.360 --> 06:03.520
Gradus, je nachdem, wie genau Sie anpassen wollen.

06:04.560 --> 06:12.780
Das sind Polynome, also Summe a i x hoch i, und wenn Sie sowas

06:12.780 --> 06:14.780
auswerten wollen, müssen Sie auch das effizient machen.

06:15.500 --> 06:18.960
Das ist eine der Standard-Operationen in solchen Anwendungen.

06:19.840 --> 06:23.020
Und wenn Sie auf Daten zugreifen, müssen Sie wissen, wie man das

06:23.020 --> 06:23.740
sinnvoll macht.

06:23.880 --> 06:27.280
Riesend Datenmengen müssen verwaltet werden heutzutage, nicht nur im

06:27.280 --> 06:28.940
kommerziell -betriebswirtschaftlichen Bereich.

06:29.860 --> 06:34.660
Also zum Beispiel Daten von eBay oder Amazon oder so, das sind riesige

06:34.660 --> 06:36.080
Datenmengen oder Suchmaschinen.

06:36.580 --> 06:39.960
Da muss man wissen, wie man effizient zugreifen kann auf Daten, wie

06:39.960 --> 06:43.400
man erreichen kann, dass so eine einzelne Operation schnell geschieht.

06:43.520 --> 06:48.480
Das ist ein Zugriff, das Auffinden, dass das schnell passiert, damit

06:48.480 --> 06:49.960
man gute Antwortzeiten kriegt.

06:51.820 --> 06:54.540
Sie müssen das auch im technisch-wissenschaftlichen Bereich, müssen

06:54.540 --> 06:59.900
Sie viel auf Daten zugreifen, zum Beispiel in diesen Experimenten, die

06:59.900 --> 07:02.780
die Physiker machen am CERN in Genf.

07:03.320 --> 07:07.900
Da werden diese Collider-Experimente gemacht, also da werden Partikel

07:07.900 --> 07:11.180
aufeinander geschossen und dann werden Daten erhoben, was dort

07:11.180 --> 07:11.720
passiert.

07:11.720 --> 07:16.940
Das sind wahnsinnig viele Daten, also pro Stunde etwa ein Terabit

07:16.940 --> 07:17.340
Daten.

07:18.060 --> 07:23.180
Und die werden dann alle aufgesammelt und abgelegt in eine große Daten

07:23.180 --> 07:24.380
-Data -Grid.

07:24.800 --> 07:29.000
Hier in Karlsruhe ist die erste Senke für dieses Data-Grid, also alle

07:29.000 --> 07:30.680
Daten von CERN werden hierher geschickt.

07:31.200 --> 07:34.320
Das ist eine Riesenaufgabe, die ganzen Daten hier rüber zu schicken,

07:34.400 --> 07:35.560
mehrere Terabyte pro Tag.

07:35.560 --> 07:40.520
Und die werden dann in ein weltweites Data-Grid verteilt.

07:41.360 --> 07:44.820
Und jetzt müssen alle möglichen Wissenschaftler darauf zugreifen

07:44.820 --> 07:46.320
können, in vernünftiger Art und Weise.

07:46.840 --> 07:51.440
Man muss sich das mal vorstellen, man muss in vielen Terabit bzw.

07:51.660 --> 07:59.080
dann Petabit Daten suchen und vernünftig Daten gruppieren,

07:59.260 --> 08:00.140
zusammenstellen können.

08:00.260 --> 08:02.940
All das erfordert sehr effiziente Algorithmen.

08:02.940 --> 08:06.640
Das ist ein ganz wichtiger Bereich, damit man sowas vernünftig machen

08:06.640 --> 08:06.940
kann.

08:07.140 --> 08:10.520
Und dann eben einen guten Zugriff für viele Wissenschaftler auf diese

08:10.520 --> 08:11.960
interessanten Daten ermöglichen kann.

08:12.220 --> 08:17.480
Gerade neulich stand in der Zeitung, dass in den USA an einem

08:17.480 --> 08:22.400
Forschungsinstitut jetzt erstmals nachgewiesen wurde, eine bestimmte

08:22.400 --> 08:28.840
Annahme über so ein Grundmodell der Atomphysik, dass die tatsächlich

08:28.840 --> 08:29.340
zutreffen.

08:29.340 --> 08:36.240
Das ist ausgeführt worden an dem schnellsten physikalischen solchen

08:36.240 --> 08:37.580
Gerät in den USA irgendwo.

08:38.540 --> 08:41.380
Mit Software, mit Verfahren, die hier in Karlsruhe in der Physik

08:41.380 --> 08:45.760
entworfen wurden, ist das dann tatsächlich ausgewertet worden.

08:46.040 --> 08:48.660
Also da braucht man sehr, sehr effiziente Geschichten.

08:50.100 --> 08:52.320
So, suchen, sortieren ist auch wichtig.

08:53.000 --> 08:58.100
Sortieraufgaben sind mit die wesentlichsten Aufgaben in Rechnern,

08:58.180 --> 08:59.680
treten unheimlich häufig auf.

09:00.240 --> 09:03.100
In ganz vielen Bereichen braucht man sehr viel Zeit für.

09:04.240 --> 09:07.360
Und ich erzähle an dieser Stelle immer einige kleine Geschichten von

09:07.360 --> 09:10.350
einem Absolventen der Informatik.

09:11.440 --> 09:14.020
Darauf kommt es auch nicht ganz so an, das war kein guter Absolvent.

09:14.680 --> 09:17.820
Der hat jedenfalls bei einer Bank gearbeitet und hatte den Auftrag,

09:17.940 --> 09:19.200
einen neuen Rechner zu beschaffen.

09:19.200 --> 09:21.960
Wir haben ihn zufällig getroffen und er sagte, die wären nicht mehr in

09:21.960 --> 09:25.620
der Lage, über Nacht die ganzen Daten, die in der Bank anfallen, über

09:25.620 --> 09:28.080
Konto bewegen und solche Dinge alle vernünftig zu sortieren.

09:28.180 --> 09:30.440
Sie bräuchten dafür einen neuen Rechner, weil der zu langsam sei.

09:31.000 --> 09:32.860
Und dann haben wir nachgefragt, was er denn für ein Verfahren

09:32.860 --> 09:33.400
verwendet.

09:33.680 --> 09:37.320
Und eine ganz einfache Auswechslung dieses Verfahrens hat also den

09:37.320 --> 09:42.820
Auftrag überflüssig gemacht, weil man also diesen Sortiervorgang

09:42.820 --> 09:45.640
wesentlich effizienter machen konnte, als es dort geschehen ist.

09:46.740 --> 09:50.560
Wenn man also nicht quadratische Zeit braucht, sondern nur noch N-Log

09:50.560 --> 09:53.480
-N -Zeit braucht für ein Verfahren, dann ist das ein drastischer

09:53.480 --> 09:54.180
Zeitunterschied.

09:54.700 --> 09:56.920
Man muss sich aber darüber im Klaren sein, dass es wichtig ist, so

09:56.920 --> 09:57.720
etwas schnell zu machen.

09:59.000 --> 10:01.420
Dann haben wir Wegesuche in Graphen, Darstellung von Graphen,

10:01.460 --> 10:03.560
Operationen auf geometrischen Objekten.

10:04.100 --> 10:07.220
Wir werden im Laufe der Vorlesungen auf diese Dinge noch eingehen.

10:07.340 --> 10:10.600
All das braucht man in den Anwendungsbereichen, die ich hier genannt

10:10.600 --> 10:10.940
habe.

10:11.700 --> 10:13.720
Und weil man sie braucht, macht es Sinn, sie zu behandeln.

10:14.120 --> 10:16.300
Und es ist immer so die Frage, wie präsentiert man sowas?

10:16.360 --> 10:18.640
Präsentiert man nur die Verfahren oder geht man von den Anwendungen

10:18.640 --> 10:19.020
aus?

10:19.620 --> 10:22.140
Und ich versuche das ein bisschen zu kombinieren, dass man sieht, wir

10:22.140 --> 10:25.360
haben hier bestimmte Anwendungsprobleme und die müssen wir effizient

10:25.360 --> 10:25.940
machen können.

10:27.660 --> 10:31.460
Und dafür macht es Sinn, sich mit bestimmten Algorithmen zu

10:31.460 --> 10:31.720
beschäftigen.

10:33.060 --> 10:35.620
Was sind die Anforderungen an die einzelnen Algorithmen, die wir jetzt

10:35.620 --> 10:38.020
einsetzen werden oder uns angucken werden?

10:38.380 --> 10:41.020
Natürlich, ich sagte, wir wollen sie effizient machen, steht im Titel

10:41.020 --> 10:41.620
der Vorlesung.

10:41.620 --> 10:43.060
Also, geringe Kosten.

10:43.140 --> 10:45.620
Was sind Kosten der Auszügung von Algorithmen?

10:46.200 --> 10:49.400
Kosten sind zum Beispiel, einen geringen Zeitbedarf zu haben.

10:49.580 --> 10:50.400
Sicherlich sehr wichtig.

10:50.540 --> 10:51.060
Möglichst schnell.

10:52.780 --> 10:54.040
Das aber nicht alles.

10:54.760 --> 11:00.800
Wenn Sie sich anschauen, Anwendungen, meinetwegen im Videobereich oder

11:00.800 --> 11:02.020
im Fernsehen.

11:02.140 --> 11:07.200
Sie wollen hochauflösendes Fernsehen haben und da ist es wichtig, dass

11:07.200 --> 11:08.180
Sie einen hohen Durchsatz haben.

11:08.180 --> 11:11.460
Sie müssen die Framerate der Fernsehübertragung unterstützen.

11:12.340 --> 11:18.300
Es kommt nicht so sehr darauf an, dass Sie, wenn Sie hier einen

11:18.300 --> 11:19.440
einzelnen Frame bearbeiten.

11:19.500 --> 11:21.120
Das kann durchaus eine gewisse Zeit dauern.

11:22.140 --> 11:25.160
Aber es ist wichtig, dass Sie nicht mit dem nächsten Frame beginnen,

11:25.400 --> 11:31.480
wenn der erste Frame bearbeitet ist, sondern dass Sie sofort, dass Sie

11:31.480 --> 11:34.680
das ganz schnell nacheinander machen können, dass Sie die Frames mit

11:34.680 --> 11:40.520
einer bestimmten Frequenz anfangen können zu bearbeiten.

11:40.680 --> 11:43.480
Dann kommen die auch in der gleichen Frequenz am Ende wieder raus.

11:44.420 --> 11:48.540
Das heißt, Sie haben einen hohen Durchsatz und es kann durchaus ein

11:48.540 --> 11:55.760
gewisser Zeitversatz sein zwischen dem Senden dieser Frames und dem

11:55.760 --> 11:56.760
Empfangen dieser Frames.

11:56.860 --> 12:00.040
Das ist nicht so schlimm, wenn das eine Millisekunde oder auch eine

12:00.040 --> 12:04.140
Sekunde dauert, bis tatsächlich das Bild bei Ihnen auf dem Fernseher

12:04.140 --> 12:04.620
erscheint.

12:04.700 --> 12:07.640
Aber dann soll es stabil da sein mit der gleichen Framerate, wie es

12:07.640 --> 12:08.340
abgeschickt wurde.

12:09.040 --> 12:10.820
Und dafür braucht man dann einen hohen Durchsatz.

12:11.380 --> 12:14.460
Und das kann man erreichen, indem man Dinge gleichzeitig ausführt oder

12:14.460 --> 12:15.480
im Pipelining-Verfahren.

12:15.600 --> 12:19.580
Etwas, was ich auch bei der Vorlesung Grundlagen der Informatik 2 an

12:19.580 --> 12:23.560
vielen Stellen betont habe, dass Fließbandverarbeitung, Pipelining ein

12:23.560 --> 12:26.640
ganz wichtiger Punkt ist, um einen hohen Durchsatz zu erreichen.

12:26.640 --> 12:30.040
Pipelining wird ja auch in vielen Bereichen eingesetzt.

12:30.220 --> 12:33.480
Aber das heißt, da kommt es dann nicht auf den Zeitbedarf pro Aufgabe

12:33.480 --> 12:33.800
an.

12:34.160 --> 12:38.320
Das wäre hier der Bereich insgesamt, so für eine Aufgabe.

12:38.480 --> 12:42.120
Sondern es kommt darauf an, wie ist die Frequenz der einzelnen

12:42.120 --> 12:42.900
Bearbeitungen.

12:44.440 --> 12:48.480
Kosten haben auch was zu tun mit Speicherplatz, obwohl Speicherplatz

12:48.480 --> 12:51.560
immer größer uns zur Verfügung steht.

12:51.860 --> 12:54.560
Trotzdem kennen wir alle den Effekt, dass die Speicher sofort wieder

12:54.560 --> 12:58.260
volllaufen, weil die Anwendungen alle diesen Speicher dann sehr

12:58.260 --> 12:59.180
großzügig nutzen.

13:00.440 --> 13:05.180
Und deswegen ist es durchaus sinnvoll, aufzupassen, dass man nicht zu

13:05.180 --> 13:06.280
viel Speicherplatz braucht.

13:06.420 --> 13:10.800
Das kostet Platz, kostet aber auch Zeit, um auf große Datenmengen

13:10.800 --> 13:11.420
zuzugreifen.

13:11.520 --> 13:15.340
Wenn man damit sparsam umgehen kann, ist es immer besser.

13:16.580 --> 13:17.700
Wenige Berechnungseinheiten.

13:17.800 --> 13:19.740
Natürlich kostet jede Berechnungseinheit etwas.

13:19.740 --> 13:24.020
Allerdings, wenn Sie sich anschauen auf dem Chip heutzutage, also wenn

13:24.020 --> 13:27.080
Sie sich den Pentium-Chip anschauen, der Platz für den Prozessor, das

13:27.080 --> 13:28.820
ist irgendwo hier so ein kleiner Bereich.

13:29.680 --> 13:33.400
Und der größte Platz wird für alle möglichen weiteren Dinge benötigt.

13:33.460 --> 13:36.960
Ganz viel Platz für den Cache und für Register und all sowas.

13:37.380 --> 13:39.640
Also der Speicherplatz ist da viel wichtiger auf dem Chip.

13:40.440 --> 13:42.820
Und der einzelne Prozessor nimmt gar nicht mehr so viel Platz in

13:42.820 --> 13:43.200
Anspruch.

13:43.400 --> 13:47.920
Deswegen hat man zukünftig immer mehrere Prozessoren auf einem Chip.

13:47.920 --> 13:51.940
Man geht davon aus, dass man zukünftig so 16, 32 oder vielleicht sogar

13:51.940 --> 13:54.220
60 Prozessoren auf einem Chip haben wird.

13:55.440 --> 13:59.180
Das heißt, Parallelverarbeitung wird nicht mehr teuer sein.

14:00.820 --> 14:04.200
Wenn man also das nicht zur Verfügung hat, sondern wenn man einzelne

14:04.200 --> 14:07.940
Prozessoren auf den Chips hat, dann wird es teurer.

14:08.440 --> 14:11.220
Dann hat man mit mehreren Berechnungseinheiten Kommunikationsaufwand.

14:12.020 --> 14:15.080
Und dann trägt das eben auch zu den Kosten mit bei.

14:15.700 --> 14:21.660
Allerdings ist natürlich ein Trade-off da, also ein Zusammenhang

14:21.660 --> 14:25.000
zwischen Anzahl Berechnungseinheiten und Zeitbedarf.

14:25.080 --> 14:27.600
Wenn ich viele Berechnungseinheiten einsetze, kann ich eventuell in

14:27.600 --> 14:29.140
kurzer Zeit eine Aufgabe erledigen.

14:30.060 --> 14:33.360
Oder in wesentlich kürzerer Zeit, als wenn ich das alles auf einem

14:33.360 --> 14:34.940
Prozessor mache.

14:36.040 --> 14:39.480
Genauso ist es so, dass man versucht, bei verteilten Berechnungen mit

14:39.480 --> 14:40.840
wenig Nachrichten auszukommen.

14:41.360 --> 14:43.800
Wenn ich viele Nachrichten verschicken muss, dann dauert das lange

14:43.800 --> 14:44.260
Zeit.

14:44.260 --> 14:47.880
Sie müssen mal messen, wie lange es dauert, bis eine Nachricht von

14:47.880 --> 14:50.820
einem Rechner zum anderen Rechner gewandert ist.

14:50.920 --> 14:54.160
Dann müssen Sie über verschiedene Protokollebenen hinweglaufen, bis

14:54.160 --> 14:56.820
überhaupt eine Nachricht rausgeschickt wird, über irgendein Port mit

14:56.820 --> 14:58.860
TCP -IP ganz runter auf die unterste Schicht.

14:59.200 --> 15:02.160
Und dann tatsächlich ausgeschickt wird und zum anderen Rechner kommt.

15:02.560 --> 15:04.260
Das dauert eine Weile, das ist ein Millisekundenbereich.

15:05.360 --> 15:09.440
Und Sie wissen, dass Sie in der Zeit einer Millisekunde sehr, sehr,

15:09.480 --> 15:11.900
sehr viele Anweisungen ausführen können.

15:11.900 --> 15:14.160
Das heißt, eine Nachricht zu verschicken ist sehr teuer.

15:15.300 --> 15:20.440
Und wenn man stattdessen Dinge lokal berechnen kann, ist das

15:20.440 --> 15:22.920
vielleicht sogar viel effizienter, als diese Nachricht zu verschicken.

15:23.040 --> 15:27.220
Deswegen ist das ein Aufwand, der wichtig ist, bei verteilten

15:27.220 --> 15:32.640
Berechnungen, also Kommunikationsoverhead, möglichst zu reduzieren.

15:32.880 --> 15:35.300
Und wenn er da ist, dann das so zu machen, dass die einzelnen

15:35.300 --> 15:37.740
Berechnungen darauf nicht warten müssen, dass eine Nachricht

15:37.740 --> 15:40.420
verschickt wird, sondern dass die während der Verschickung einer

15:40.420 --> 15:41.960
Nachricht etwas Sinnvolles tun können.

15:42.820 --> 15:47.120
Auf jeden Fall geht es darum, die verfügbaren Ressourcen möglichst gut

15:47.120 --> 15:50.020
auszunutzen, also immer auf der effizienten Linie zu bleiben.

15:50.680 --> 15:52.680
Wirtschaftsingenieure wissen was von Betriebswirtschaftslehre, da

15:52.680 --> 15:54.500
redet man auch über Effizienz.

15:55.220 --> 15:57.680
Und da geht es halt darum, dass man das, was an Ressourcen verfügbar

15:57.680 --> 16:01.000
ist, praktisch optimal ausnutzt.

16:01.100 --> 16:01.840
Das ist Effizienz.

16:01.840 --> 16:04.800
Dann haben sie eine effiziente Linie, häufig mit mehreren Kriterien,

16:05.180 --> 16:09.760
dann haben sie Pareto-optimale Bereiche, und da müssen wir uns

16:09.760 --> 16:14.720
bewegen, da wo es Pareto-optimal ist, und das passiert eben, wenn wir

16:14.720 --> 16:15.780
effizient sind.

16:16.680 --> 16:21.460
Es wird Synonym verwendet, Effizienz und Pareto-Optimalität.

16:22.200 --> 16:24.740
Und in der Informatik reden wir halt auch von Effizienz, häufig ein

16:24.740 --> 16:26.960
bisschen anders, aber es hat schon was miteinander zu tun.

16:28.180 --> 16:31.120
Und ein weiterer Punkt ist natürlich auch, dass man etwas zuverlässig

16:31.120 --> 16:33.620
ausführt, auch bei Auftreten von Störungen.

16:33.820 --> 16:36.680
Das wird immer wichtiger, wenn man mit vielen Rechnern arbeitet, mit

16:36.680 --> 16:39.360
vielen Geräten können die ausfallen, und trotzdem müssen die Aufgaben,

16:39.400 --> 16:41.460
die erfüllt werden, sinnvoll ausgeführt werden.

16:43.480 --> 16:48.580
Anpassungsfähigkeit an unterschiedliche Bedingungen der Ausführung von

16:48.580 --> 16:50.160
Funktionen ist was ganz Wichtiges.

16:50.160 --> 16:56.840
Man kann auch sagen, dass die Geräte, die wir entwickeln, sich

16:56.840 --> 16:58.600
organisch verhalten sollen.

16:59.060 --> 17:01.980
Und dann kommen wir zu einem Gebiet, das wir gerade hier in Karlsruhe

17:01.980 --> 17:07.380
jetzt sehr stark vorantreiben, das Organic Computing.

17:08.340 --> 17:10.620
Muss ich aufhören, weil ich den Bereich koordiniere.

17:11.520 --> 17:14.020
Und in dem Bereich haben wir viele interessante Forschungsthemen.

17:14.020 --> 17:19.380
Also wenn Sie Seminare oder Studienarbeiten oder Diplomarbeiten

17:19.380 --> 17:23.380
schreiben wollen irgendwann, da haben wir einiges anzubieten, was in

17:23.380 --> 17:24.180
dem Bereich liegt.

17:24.340 --> 17:28.340
Was eines der für mich jedenfalls faszinierendsten Herausforderungen

17:28.340 --> 17:32.860
für die Informatik ist, im Bereich Organic Computing die dort

17:32.860 --> 17:35.040
entwickelten Visionen tatsächlich umzusetzen.

17:35.220 --> 17:39.800
Das ist also etwas, was die Informatik ziemlich beeinflussen wird,

17:40.280 --> 17:41.180
hoffentlich positiv.

17:41.180 --> 17:42.560
Das ist der Sinn der ganzen Sache.

17:43.280 --> 17:44.640
Ich kann jetzt nicht zu sehr darauf eingehen.

17:45.060 --> 17:46.900
Ich könnte lange darauf eingehen, aber das mache ich jetzt lieber

17:46.900 --> 17:47.120
nicht.

17:47.240 --> 17:48.760
Sondern ich gehe auf effiziente Algorithmen ein.

17:49.960 --> 17:55.120
Und Effizienzanalyse, also wie teuer ist es etwas zu tun, das kann

17:55.120 --> 17:56.300
sich beziehen auf eine Aufgabe.

17:56.840 --> 17:57.880
Ich möchte sortieren.

17:58.620 --> 18:00.320
Wie teuer ist es eigentlich zu sortieren?

18:00.460 --> 18:01.140
Was kostet das?

18:01.180 --> 18:02.900
Wie hoch ist die Komplexität des Sortierens?

18:05.580 --> 18:11.080
Und es kann sich beziehen auf einzelne Berechnungen.

18:11.860 --> 18:15.040
Also in dem Sinne hier oben, wir haben eine einzelne Berechnung.

18:15.580 --> 18:17.120
Oder eine Gruppe von Berechnungen.

18:17.500 --> 18:20.460
Also eine einzelne Berechnung wäre eben die Zeitspanne für eine

18:20.460 --> 18:21.020
Berechnung.

18:21.360 --> 18:23.740
Die Gruppe von Berechnungen wäre eben das Ganze.

18:24.620 --> 18:25.640
Das zu analysieren.

18:26.280 --> 18:29.040
Oder es kann auch sein, dass ich mir anschaue, wie effizient wird

18:29.040 --> 18:30.700
eigentlich ein Gerät ausgenutzt?

18:31.420 --> 18:33.560
Ist der die ganze Zeit sinnvoll beschäftigt?

18:33.600 --> 18:36.620
Ich kann jedes Gerät beschäftigen, aber ist es sinnvoll beschäftigt?

18:37.320 --> 18:40.960
Das ist so ähnlich wie Sie messen den Output eines Programmierers,

18:41.340 --> 18:43.380
damit wie viele Lines of Code er entwickelt.

18:44.040 --> 18:46.400
Ich kann Ihnen ganz viele Lines of Code produzieren, überhaupt kein

18:46.400 --> 18:46.800
Problem.

18:47.540 --> 18:49.920
Ich kann Ihnen sofort nachweisen, dass Sie sehr produktiv sind, aber

18:49.920 --> 18:51.700
ob das alles sinnvoll ist, ist eine ganz andere Frage.

18:51.840 --> 18:53.160
Aber das zu bewerten ist nicht einfach.

18:55.260 --> 18:58.920
Also es gibt offensichtlich verschiedene Arten, wie man Effizienz

18:58.920 --> 18:59.960
analysieren kann.

19:01.400 --> 19:04.940
Und das, was wir also genauer angucken werden, ist jetzt, wie kann man

19:04.940 --> 19:11.100
Probleme, die ich Ihnen jetzt kurz angesprochen habe, wie kann man die

19:11.100 --> 19:13.900
durch Algorithmen tatsächlich lösen?

19:14.180 --> 19:19.320
Und dann gehen wir mal ganz zurück auf die anfänglichen Definitionen

19:19.320 --> 19:20.780
des Algorithmusbegriffs.

19:22.780 --> 19:25.140
Ich muss mal ganz kurz etwas überprüfen.

19:26.220 --> 19:27.840
Ja, es ist alles in Ordnung.

19:30.660 --> 19:33.420
Der Algorithmusbegriff ist Ihnen bekannt aus den Anfangsvorlesungen

19:33.420 --> 19:34.500
der Informatik.

19:35.220 --> 19:39.500
Es geht um ein endlich beschriebenes, deterministisches Verfahren mit

19:39.500 --> 19:43.360
Ein - und Ausgabe, das für alle zulässigen Eingaben terminiert und

19:43.360 --> 19:44.840
dessen Operationen effektiv sind.

19:44.940 --> 19:47.060
Das ist so unsere intuitive Beschreibung von Algorithmen.

19:47.540 --> 19:50.180
Und da kommen halt hier die wesentlichen Stichwörter vor.

19:50.180 --> 19:53.120
Finitheit der Beschreibung, Effektivität der Operation, sie können

19:53.120 --> 19:55.180
tatsächlich ausgeführt werden in endlicher Zeit.

19:56.000 --> 19:59.720
Terminierung der Ausführung insgesamt beendet oder wird der

19:59.720 --> 20:01.200
Algorithmus tatsächlich beendet.

20:01.700 --> 20:04.000
Und das Ganze muss determiniert sein, d.h.

20:04.200 --> 20:08.600
wenn ich den Algorithmus zweimal mit den gleichen Eingaben ausführe,

20:09.160 --> 20:11.560
dann muss auch das gleiche Ergebnis rauskommen.

20:12.580 --> 20:15.780
Das ist bei Algorithmen heutzutage, also das ist so die klassische

20:15.780 --> 20:18.360
Definition des Algorithmus, das ist bei Algorithmen heutzutage nicht

20:18.360 --> 20:19.560
unbedingt immer der Fall.

20:20.400 --> 20:25.000
Wieso kann es passieren, dass man bei wiederholter Eingabe der

20:25.000 --> 20:28.120
gleichen Daten eventuell unterschiedliche Ergebnisse kriegt?

20:28.200 --> 20:30.440
Und es gibt sogenannte randomisierte Algorithmen.

20:32.220 --> 20:38.200
Und diese randomisierten Algorithmen, die sind heutzutage sehr

20:38.200 --> 20:41.360
wichtig, bei denen will man natürlich auch erreichen, dass immer das

20:41.360 --> 20:42.180
gleiche rauskommt.

20:44.660 --> 20:50.300
Es gibt ein Verfahren zur Primzahlbestimmung, das habe ich bei der

20:50.300 --> 20:52.560
Vorlesung AIA vorgestellt.

20:52.920 --> 20:55.740
Da will man immer das richtige Ergebnis haben, aber es ist mit einer

20:55.740 --> 20:58.540
gewissen Wahrscheinlichkeit möglich, dass auch das falsche Ergebnis

20:58.540 --> 20:59.080
rauskommt.

20:59.940 --> 21:02.740
Ein anderer Bereich, wo man randomisierte Algorithmen einsetzt und

21:02.740 --> 21:05.440
tatsächlich unterschiedliche Ergebnisse haben möchte, das ist der

21:05.440 --> 21:08.200
gesamte Bereich der Metaheuristiken.

21:10.160 --> 21:11.800
Metaheuristiken, was ist das?

21:12.020 --> 21:16.740
Das sind Verfahren, bei denen man auf möglichst einfache Art und Weise

21:16.740 --> 21:19.500
schwierige Probleme löst.

21:20.060 --> 21:23.320
Zum Beispiel die sogenannten evolutionären Algorithmen.

21:26.860 --> 21:31.220
Ein wichtiger Bereich, evolutionäre Algorithmen, bei denen man so die

21:31.220 --> 21:34.560
Prinzipien der Evolution nachbildet, um schwierige Probleme zu lösen,

21:34.880 --> 21:37.860
wie meinetwegen ein Traveling Assessment Problem oder ein Scheduling

21:37.860 --> 21:38.960
Problem oder Ähnliches.

21:39.880 --> 21:43.340
Und bei diesen evolutionären Algorithmen will man ganz bewusst

21:43.340 --> 21:47.640
Zufallskomponenten drin haben, um sich im Suchraum den Bereichen zu

21:47.640 --> 21:52.320
nähern, die tatsächlich sehr gut sind, mit Bezug auf die Zielfunktion.

21:53.040 --> 21:57.100
Und systematisch ist das eine sehr schwierige Aufgabe wegen des sehr

21:57.100 --> 21:58.100
großen Suchraumes.

21:58.100 --> 22:03.440
Deswegen macht man das randomisiert, um auf diese Art und Weise den

22:03.440 --> 22:09.920
Suchraum zwar zufallsbasiert, aber doch relativ systematisch zu

22:09.920 --> 22:11.040
durchforsten, zu durchsuchen.

22:12.520 --> 22:15.940
Und dann wäre es natürlich schlecht, wenn man immer das gleiche

22:15.940 --> 22:16.560
Ergebnis kriegt.

22:16.720 --> 22:21.040
Ich möchte natürlich den möglichst breit mit mir angucken.

22:22.040 --> 22:26.680
Und ich will natürlich schon am Ende die optimale Lösung haben, aber

22:26.680 --> 22:30.040
es kann auch unterschiedliche optimale Lösungen geben.

22:30.740 --> 22:32.140
Die müssen nicht alle identisch sein.

22:32.400 --> 22:34.540
Und ich möchte vor allen Dingen, also ich werde häufig gar nicht die

22:34.540 --> 22:37.960
optimale Lösung kriegen, aber ich möchte häufig eine möglichst große

22:37.960 --> 22:39.540
Vielfalt an guten Lösungen haben.

22:40.040 --> 22:41.840
Einfach um Entscheidungsmöglichkeiten zu haben.

22:41.980 --> 22:46.360
Und das geht halt nur, wenn ich tatsächlich randomisierte Verfahren

22:46.360 --> 22:47.000
einsetze.

22:47.440 --> 22:51.920
Damit habe ich also eine Chance, gute Lösungen zu erzeugen.

22:51.920 --> 22:55.520
Wenn Sie daran Interesse haben an dem Bereich, müssten Sie in die

22:55.520 --> 22:59.140
Vorlesung von Herrn Branke gehen, über naturanaloge verteilte

22:59.140 --> 23:04.760
Optimierungsverfahren, die auch in diesem Semester läuft, montags,

23:04.980 --> 23:05.560
vormittags.

23:06.640 --> 23:09.060
So, andere Formulierungen nochmal etwas einfacher.

23:10.280 --> 23:14.400
Das sind Algorithmen, eine endliche Beschreibung der Ausführung einer

23:14.400 --> 23:16.960
endlichen Folge von Befehlen auf einer abstrakten Maschine.

23:18.600 --> 23:21.240
Sehr einfach ausgeführt oder aufgeschrieben.

23:21.540 --> 23:23.860
Sie wissen, es gibt eine formale Beschreibung über Turing-Maschinen.

23:25.580 --> 23:28.260
Aber das heißt, das was hier oben steht, wir haben also etwas, was

23:28.260 --> 23:34.100
eine endliche Folge von Befehlen, das ist irgendeine Programmstruktur.

23:35.400 --> 23:37.580
Wir müssen unsere Daten irgendwie darstellen.

23:37.980 --> 23:41.980
Das heißt, wir haben eine bestimmte Datenstruktur uns zu überlegen,

23:42.100 --> 23:45.840
mit der wir das, was wir bearbeiten, sinnvoll modellieren.

23:46.320 --> 23:50.040
Und diese beiden zusammenbringen so das, was üblicherweise bei einer

23:50.040 --> 23:53.440
Vorlesung über effiziente Algorithmen untersucht wird.

23:53.500 --> 23:55.460
Was auch sehr viel interessanter Stoff ist.

23:56.140 --> 23:58.560
Und ich lege Wert darauf, dass wir uns auch die Rechnerstrukturen

23:58.560 --> 23:59.080
anschauen.

23:59.700 --> 24:02.000
Ist das ein serieller Rechner oder sequenzieller Rechner?

24:02.100 --> 24:04.700
Ist das ein paralleler Rechner, verteilter Rechner, Hardware oder

24:04.700 --> 24:05.280
ähnliches?

24:05.980 --> 24:09.180
Und wenn wir das alles angucken, wird es halt ein bisschen komplexer,

24:09.400 --> 24:11.800
das Gebilde oder das Gebiet, das wir anschauen müssen.

24:11.800 --> 24:14.640
Aber ich denke, es ist sinnvoll zu sehen, wie man eigentlich sich in

24:14.640 --> 24:21.800
diesem Feld hier diese drei Bereiche bewegen kann, um effizient

24:21.800 --> 24:23.420
Probleme lösen zu können.

24:25.000 --> 24:27.640
Strukturen tauchen also unterschiedlich auf.

24:27.800 --> 24:31.280
Programmstrukturen können sein, das kennen Sie alles.

24:31.780 --> 24:37.420
Einmal die Elemente der prozeduralen Programmiersprachen, die

24:37.420 --> 24:40.520
elementaren Anweisungen, Anweisungsfolgen, Verzweigungen, Schleifen.

24:40.520 --> 24:45.500
Dann Prozeduraufrufe mit Rekursionseffekten drin, natürlich.

24:47.680 --> 24:51.340
Objekterzeugung, Methoden, also Prozedur- und Funktionsaufrufe stehen

24:51.340 --> 24:51.520
drin.

24:51.620 --> 24:54.000
Methoden sind ja eigentlich nichts anderes, nur auf objektorientierte

24:54.000 --> 24:55.000
Programmiersprachen bezogen.

24:56.660 --> 24:59.980
Kommunikationsoperationen, das sind alles so, auch nur eigentlich

24:59.980 --> 25:01.600
spezielle Funktionen.

25:01.640 --> 25:04.580
Dann gibt es die Datenstrukturen, sehr viele verschiedene Dinge.

25:04.580 --> 25:10.820
Sie haben einfache, elementare Strukturen oder elementare Datentypen.

25:11.220 --> 25:15.320
Dann haben Sie tatsächlich strukturierte Datentypen, wie Arrays,

25:15.440 --> 25:20.720
Records, Listen, Queues, Stacks, Bäume, Heaps und Ähnliches, kennen

25:20.720 --> 25:23.020
Sie alles aus den Anfangsvorlesungen.

25:23.420 --> 25:27.120
Gridfiles, Segmentbäume kennen Sie nicht, das sind Dinge, die man in

25:27.120 --> 25:30.620
der algorithmischen Geometrie eingeführt hat, für spezielle

25:30.620 --> 25:31.200
Anwendungen.

25:32.040 --> 25:36.860
Also es gibt viele verschiedene Möglichkeiten, Daten zu strukturieren.

25:36.980 --> 25:42.380
Alle haben ihre besonderen Eigenschaften und man muss sie halt

25:42.380 --> 25:43.200
sinnvoll einsetzen.

25:44.300 --> 25:47.180
Man muss wissen, was es also heißt, wenn man z.B.

25:47.320 --> 25:50.880
eine Liste verwendet oder ein Array, wie sich das auswirkt auf die

25:50.880 --> 25:52.820
Kosten eines Algorithmus.

25:53.260 --> 25:55.440
Interfaces habe ich auch noch zugefügt.

25:55.440 --> 25:58.520
Das geht ja eigentlich auch an, wie ich etwas strukturieren muss, um

25:58.520 --> 26:01.720
zu kommunizieren zwischen verschiedenen Programmkomponenten.

26:02.780 --> 26:05.280
Rechnerstrukturen sind charakterisiert durch die Art, wie ich sie

26:05.280 --> 26:06.800
programmieren kann, durch einen Befehlssatz.

26:06.920 --> 26:09.060
Das gibt eigentlich die Rechnerarchitektur an.

26:09.800 --> 26:11.440
Die Prozessorstruktur ist aber auch wichtig.

26:11.640 --> 26:14.200
Habe ich parallele Funktionseinheiten, habe ich Pipeline und

26:14.200 --> 26:16.960
Ähnliches, das bestimmt, wie effizient so eine Struktur ist.

26:18.200 --> 26:20.840
Verbindungsstrukturen, also wenn ich mehrere Rechner habe, wie

26:20.840 --> 26:22.440
kommunizieren die miteinander?

26:23.660 --> 26:27.880
Da gibt es eine Reihe von klassischen Modellen.

26:28.420 --> 26:30.980
Turing-Maschine, einfachstes Modell, kennen Sie aus den Anfänger

26:30.980 --> 26:31.540
-Vorlesungen.

26:32.220 --> 26:36.340
Random -Axis-Machine, werden wir gleich kennenlernen, ist etwas

26:36.340 --> 26:37.880
Ähnliches wie der von Neumann-Rechner.

26:38.860 --> 26:41.700
PRAM, eine Parallel Random-Axis-Machine, also einfach eine

26:41.700 --> 26:44.540
Vervielfachung der einfachen RAM.

26:44.540 --> 26:50.200
Da haben Sie halt viele solcher Rechner, die nebeneinander sind und

26:50.200 --> 26:54.940
irgendwie miteinander kommunizieren können und hier irgendwelchen

26:54.940 --> 26:56.160
gemeinsamen Speicher haben.

26:56.280 --> 26:58.440
Die können also direkt verbunden sein, können aber auch hier

26:58.440 --> 26:58.740
irgendwie...

26:59.400 --> 27:02.820
Das ist ja also so eine PRAM, bei der Sie viele Prozessoren haben, die

27:02.820 --> 27:04.120
auf Speicher zugreifen können.

27:04.580 --> 27:07.960
Und dieses Verbindungsnetz hier drin, das entscheidet darüber, wie die

27:07.960 --> 27:09.100
Kommunikation abläuft.

27:09.100 --> 27:13.240
Das kann sein, dass das Ganze als Hypercube angeordnet ist.

27:14.580 --> 27:17.360
Ich komme darauf nochmal zu sprechen, deswegen würde ich das jetzt

27:17.360 --> 27:20.040
nicht im Einzelnen ausführen, ganz kurz auf die verschiedenen

27:20.040 --> 27:20.880
Verbindungsstrukturen.

27:22.180 --> 27:25.640
Hier ist nur aufgeführt, dass es dort viele verschiedene Sachen gibt.

27:26.080 --> 27:29.280
Hypercube, Baumrechner, also eine baumartige Strukturierung, eine

27:29.280 --> 27:33.720
gitterartige Strukturierung, ein Torus, Mesh of Trees, Internet,

27:34.240 --> 27:38.540
völlig unstrukturiert, hat aber auch gewisse Struktureigenschaften,

27:38.540 --> 27:39.420
die man sich anschauen kann.

27:40.500 --> 27:43.820
Also das sind alles Dinge, die was damit zu tun haben, wie ich

27:43.820 --> 27:48.160
Aufgaben verteilen kann auf verschiedene Berechnungseinheiten und wie

27:48.160 --> 27:50.800
dann die Kommunikation zwischen diesen Berechnungseinheiten ablaufen

27:50.800 --> 27:51.080
kann.

27:52.440 --> 27:57.120
So, wir nähern uns den Themen der Vorlesung.

27:57.360 --> 27:58.880
Entwurf und Analyse von Algorithmen.

27:59.260 --> 28:00.600
Wie entwirft man Algorithmen?

28:00.760 --> 28:03.360
Da haben Sie Prinzipien kennengelernt in Anfängervorlesungen.

28:03.920 --> 28:09.340
Divide and Conquer, klassisches Prinzip der Aufteilung eines Problems

28:09.340 --> 28:12.020
in eine Reihe von Teilproblemen.

28:12.880 --> 28:16.160
Notwendigerweise des Jungt, meistens schon, oder vorzugsweise des

28:16.160 --> 28:17.220
Jungt, ist aber nicht immer so.

28:18.140 --> 28:21.880
Und dann versucht man halt diese, das macht man halt rekursiv weiter

28:21.880 --> 28:24.640
und dann will man das halt möglichst hier unten, diese Probleme

28:24.640 --> 28:28.540
irgendwann lösen und wird dann die Lösungen wieder nach oben schieben

28:28.540 --> 28:32.960
und kombinieren, sodass man eine Lösung des Ausgangsproblems kriegt

28:33.780 --> 28:38.380
Und es zeigt sich, dass man über diese rekursive Aufteilung eines

28:38.380 --> 28:42.620
Problems in Teilprobleme häufig deutlich effizientere Verfahren

28:42.620 --> 28:45.280
entwickeln kann, als wenn man das versucht von vornherein auf dem

28:45.280 --> 28:46.260
Gesamtproblem zu machen.

28:47.280 --> 28:49.480
Bisschen ähnlich sieht das Dynamic Programming aus.

28:49.660 --> 28:53.960
Da kennen Sie Verfahren, die danach aufgebaut sind.

28:53.960 --> 28:57.960
Reduktion von endlichen Automaten oder der Kocke-Kasame-Yanga

28:57.960 --> 29:03.760
-Algorithmus zur Lösung des Wortproblems in kontextfreien Sprachen.

29:04.200 --> 29:09.040
Dynamic Programming-Verfahren, bei denen man so tabellarisch arbeitet

29:09.040 --> 29:13.980
und erstmal kleine Probleme bearbeitet und so sukzessive

29:13.980 --> 29:16.540
fortschreitend schwierigere Probleme löst.

29:16.540 --> 29:21.560
Die Unternutzung aller einzelnen Lösungen von Teilproblemen, das geht

29:21.560 --> 29:24.860
nicht so rekursiv wie bei Divide & Conquer, sondern da müssen Sie auf

29:24.860 --> 29:28.360
alle einzelnen Lösungen zugreifen können.

29:28.480 --> 29:31.620
Deswegen ist das mit Analysen nicht ganz so einfach wie bei Divide &

29:31.620 --> 29:36.300
Conquer -Verfahren, aber eine sehr systematische Art zu programmieren.

29:37.080 --> 29:41.100
Und Dynamic Programming heißt das nicht, weil es im Sinne so dynamisch

29:41.100 --> 29:43.720
ist, sondern es hat was damit zu tun mit Verfahren aus dem Operations

29:43.720 --> 29:47.600
Research, bei denen man tabellarische Verfahren einsetzt.

29:47.780 --> 29:51.540
Und die wurden irgendwann mal dynamische Programmierverfahren genannt.

29:51.960 --> 29:52.560
Da kommt das her.

29:53.460 --> 29:56.040
Branch & Bound, etwas, was Sie auch kennengelernt haben.

29:56.260 --> 30:00.580
Wenn man Probleme lösen will, macht man das häufig so, dass man

30:00.580 --> 30:04.280
einfach möglichst weit aufteilt, sich im Suchraum hin und her bewegt

30:04.280 --> 30:07.320
und versucht, möglichst früh zu entscheiden.

30:07.320 --> 30:13.260
Dadurch, dass man Teillösungen aufbaut, welche Zweige im Suchraum oder

30:13.260 --> 30:16.140
welche Bereiche im Suchraum von vornherein ausgeschaltet werden

30:16.140 --> 30:16.500
können.

30:16.840 --> 30:24.520
Ab dieses Begrenzen des Suchbereiches und über Branch & Bound kann man

30:24.520 --> 30:28.720
zum Beispiel Optimierungsprobleme durchaus exakt lösen.

30:29.400 --> 30:31.080
Wenn man Pech hat, ist der Aufwand sehr hoch.

30:31.160 --> 30:34.300
Wenn man Glück hat, bekommt man dabei ein vernünftiges Verfahren.

30:34.300 --> 30:40.000
Auch von der Laufzeit her vernünftig, aber es ist eben ein Verfahren,

30:40.140 --> 30:43.120
das ist ganz recht systematische Vorgehensweise.

30:43.300 --> 30:45.840
Es gibt viele vernünftige Branch & Bound Verfahren und man kann die

30:45.840 --> 30:52.120
auch nicht vollständig ausführen und dadurch zu approximierenden

30:52.120 --> 30:52.860
Verfahren kommen.

30:53.880 --> 30:57.300
Greedy Algorithmen kennen Sie zum Teil auch.

30:57.460 --> 31:01.880
Greedy, gierige Algorithmen, bei denen man in jedem Punkt des

31:01.880 --> 31:05.280
Verfahrens immer das Nächstbeste macht.

31:06.100 --> 31:09.760
Wenn ich als Traveling Salesman durch eine Gegend fahre, dann fahre

31:09.760 --> 31:14.160
ich immer zur nächstgelegenen nächsten Stadt und mache also lokal

31:14.160 --> 31:17.480
optimale Entscheidungen, die aber nicht notwendigerweise zu einer

31:17.480 --> 31:21.320
global optimalen Lösung führen müssen, nur für bestimmte Probleme.

31:23.540 --> 31:27.980
Solche Greedy Algorithmen sind aber ein wichtigeres Entwurfsprinzip,

31:28.100 --> 31:30.880
das durchaus günstige Eigenschaften haben kann.

31:31.260 --> 31:34.300
Scanline-Prinzip kennen Sie noch nicht, das werden Sie hier

31:34.300 --> 31:35.420
kennenlernen.

31:36.500 --> 31:39.680
Wenn man die Eigenschaften, zum Beispiel dieses Bildschirms sich

31:39.680 --> 31:43.280
anschauen will, kann man eine Scanline nehmen und kann diese Scanline

31:43.280 --> 31:46.540
über den Bildschirm bewegen und kann an allen Stellen, wo man

31:46.540 --> 31:51.760
irgendein Objekt trifft, einfach das feststellen und hat dadurch

31:51.760 --> 31:55.840
folgendes erreicht, dass man alle Ereignisse oder alles, was auf

31:55.840 --> 31:59.600
diesem zweidimensionalen Bildschirm ist, überführt in Ereignisse auf

31:59.600 --> 32:07.240
einer Linie und das ist eine Reduktion des Problembereiches um eine

32:07.240 --> 32:07.760
Dimension.

32:07.760 --> 32:12.080
Ich habe also das, was auf dem Bildschirm passiert, zurückgeführt auf

32:12.080 --> 32:18.860
eine Folge von Ereignissen auf einer Linie und dieses Prinzip, so in

32:18.860 --> 32:23.440
einer Linie eine Scanline über einen zweidimensionalen Bereich zu

32:23.440 --> 32:26.380
bewegen, das Scanline-Prinzip ist ein wichtiges Prinzip bei

32:26.380 --> 32:29.200
geometrischen Algorithmen, werden wir in dem Teil der Vorlesung

32:29.200 --> 32:29.720
kennenlernen.

32:32.700 --> 32:39.400
Analyse, gerade noch zu sehen unter meinen Annotationen, da geht es um

32:39.400 --> 32:42.780
natürlich die Frage nach der Effizienz, wir wollen feststellen, wie

32:42.780 --> 32:47.280
gut ist mein Algorithmus und was wir dort anschauen, habe ich vorhin

32:47.280 --> 32:53.000
schon kurz aufgeführt, also natürlich die Zeit, den Platz, die Anzahl

32:53.000 --> 32:59.320
der Prozessoren könnte wichtig sein, wobei bei der Zeit nochmal kurz

32:59.320 --> 33:02.160
zurück, was ist die Zeit, Stoppuhr gemessen oder Anzahl

33:02.160 --> 33:05.400
Programmschritte oder was misst man da eigentlich, macht es Sinn zu

33:05.400 --> 33:09.880
messen auf dem Mac, auf dem Windows-basierten Rechner, auf dem Linux

33:09.880 --> 33:14.740
-basierten Rechner, völlig unterschiedliche Zeiten, wie analysiere ich

33:14.740 --> 33:19.320
auf sinnvolle Art und Weise den Zeitbedarf eines Algorithmus, finden

33:19.320 --> 33:23.400
Sie je nachdem, aus welcher Wissenschaftsgemeinde jemand kommt, finden

33:23.400 --> 33:26.900
Sie unterschiedliche Arten Algorithmen, die Zeit von Algorithmen zu

33:26.900 --> 33:30.400
bewerten, ein Informatiker macht das ganz anders als ein Ingenieur,

33:31.080 --> 33:34.500
der Ingenieur guckt eigentlich nur auf die Stoppuhr und sagt, wie

33:34.500 --> 33:40.280
viele Sekunden ein Algorithmus braucht und ist begeistert, wenn er die

33:40.280 --> 33:45.080
Zeit halbiert oder um bestimmten konstanten Faktor reduziert hat oder

33:45.080 --> 33:49.660
irgendwie reduziert hat und der Informatiker schaut, ob er von Groß O,

33:49.780 --> 33:53.880
von irgendwas N hoch 3 auf N hoch 2.81 gekommen ist, das ist ein

33:53.880 --> 33:56.900
fantastisches Ergebnis und der Ingenieur kann damit nichts anfangen.

33:57.080 --> 34:00.040
Da sind manchmal die Sprechweisen in diesem Bereich völlig

34:00.040 --> 34:03.200
unterschiedlich und man muss sehen, dass man das aufeinander überführt

34:03.200 --> 34:07.000
und dann sich schon verständigt, das passiert aber durchaus auch.

34:07.780 --> 34:11.020
So, Anzahl Prozessoren ist auch wichtig bei parallelen Algorithmen,

34:11.440 --> 34:14.020
Fläche ist wichtig, was die Fläche eines Algorithmus, und ich kann

34:14.020 --> 34:18.280
einen Algorithmus als Schaltkreis auf dem Chip realisieren und zum

34:18.280 --> 34:22.400
Beispiel die arithmetisch-logischen Funktionseinheiten im Prozessor

34:22.400 --> 34:27.200
sind Algorithmen, die als Schaltkreise realisiert sind und die

34:27.200 --> 34:28.080
brauchen eine bestimmte Fläche.

34:28.500 --> 34:31.600
Ich kann auch ein komplexeres Verfahren als eine einfache Addition als

34:31.600 --> 34:33.840
Schaltkreis realisieren, ich kann einen Schaltkreis für

34:33.840 --> 34:36.640
Signalverarbeitung machen, ich kann für schnelle Fourier

34:36.640 --> 34:39.500
-Transformationen Schaltkreise machen, für Sortierprobleme kann ich

34:39.500 --> 34:42.040
einen Schaltkreis entwerfen und dann braucht er eine bestimmte Fläche.

34:42.040 --> 34:49.000
Und die Fläche kostet auf dem Silicium-Chip und dann muss ich sehen,

34:49.300 --> 34:49.980
wie ich das bederte.

34:50.560 --> 34:54.460
Volumen wird durchaus wichtiger, etwas, was man schon lange haben

34:54.460 --> 34:59.200
möchte, dass man Schaltkreise nicht nur in der Ebene, also irgendwo

34:59.200 --> 35:04.500
auf so einem Chip, da irgendein Schaltkreis irgendwas hier dargestellt

35:04.500 --> 35:10.400
hat, sondern dass man davon mehrere übereinander machen kann, 3D

35:10.400 --> 35:11.740
-Schaltkreise.

35:12.320 --> 35:15.500
Das Problem ist, dass jeder Schaltkreis, wenn er arbeitet, Wärme

35:15.500 --> 35:19.280
erzeugt und man hat es bis heute nicht im Griff, die entstehende Wärme

35:19.280 --> 35:21.540
sinnvoll abzuleiten, sodass sie zuverlässig arbeiten.

35:22.020 --> 35:25.500
Deswegen hat man zwar inzwischen durchaus ein paar Schichten

35:25.500 --> 35:29.980
übereinander, aber so richtig 3D-Mikroelektronik gibt es noch nicht.

35:30.480 --> 35:34.940
Es gibt Prototypen, aber noch keine wirklich breite Anwendung dieser

35:34.940 --> 35:36.380
dreidimensionalen Technologie.

35:39.980 --> 35:43.080
Ja, Kommunikationsbedarf ist etwas, was wichtig ist, wenn ich mich mit

35:43.080 --> 35:44.500
verteilten Algorithmen beschäftige.

35:44.880 --> 35:48.860
Mache ich in dieser Vorlesung nicht, da gibt es eine extra Vorlesung

35:48.860 --> 35:51.900
von mir, die ich aber zur Zeit nicht anbiete, weil ich einfach nicht

35:51.900 --> 35:53.820
die Lehrkapazität im Augenblick habe.

35:53.900 --> 35:56.580
Ich habe schon so viele andere Vorlesungen, das klappt einfach nicht.

35:56.580 --> 35:58.260
Ich würde sie aber gerne mal wieder anbieten.

35:59.220 --> 36:00.960
Mal gucken, wann ich das wieder hinkriege.

36:02.400 --> 36:07.160
Denn die Berechnung oder die Verteilung von Algorithmen, von Aufgaben

36:07.160 --> 36:10.640
auf viele Knoten im Internet ist eine sehr spannende Frage.

36:11.140 --> 36:13.680
Da muss man sich damit beschäftigen, was das eigentlich alles für

36:13.680 --> 36:15.980
Randbedingungen und für Randprobleme wieder erzeugt.

36:17.120 --> 36:20.220
Und deswegen ist das Thema Verteilt-Algorithmen sehr wichtig.

36:20.220 --> 36:25.600
Sie kennen das Thema, das Grid Computing, das hat was zu tun mit

36:25.600 --> 36:28.020
Kommunikation oder mit verteilten Algorithmen.

36:28.300 --> 36:30.580
Kann ich hier in dieser Vorlesung leider nicht ansprechen.

36:31.780 --> 36:37.660
Wenn ich die Kosten abschätze für einen Algorithmus, dann muss ich mir

36:37.660 --> 36:40.760
anschauen, was macht der eigentlich, wenn er bestimmte Zeit braucht.

36:41.340 --> 36:45.740
Der muss sich ja mit irgendwelchen Eingaben beschäftigen und die

36:45.740 --> 36:48.120
Eingabe hat eine bestimmte Größe, einen bestimmten Umfang.

36:48.120 --> 36:52.380
Und das kann natürlich die Zeit abhängen von der Größe der Eingabe,

36:52.460 --> 36:54.000
deswegen ist das ein wichtiger Punkt.

36:55.220 --> 36:57.900
Und natürlich ist es so, dass der Algorithmus nicht immer das Gleiche

36:57.900 --> 36:58.420
tun wird.

36:59.000 --> 37:03.040
Je nachdem, welche Eingabe, welche Liste sortiert werden soll, wird er

37:03.040 --> 37:04.600
unterschiedlich lange dafür brauchen.

37:04.760 --> 37:06.620
Wenn eine Liste schon sortiert ist, geht das ganz schnell, wenn er

37:06.620 --> 37:07.020
Glück hat.

37:07.580 --> 37:09.320
Wenn sie unsortiert ist, dauert es vielleicht länger.

37:10.460 --> 37:14.100
Und deswegen muss man sehen, dass man einerseits das Verhalten im

37:14.100 --> 37:15.400
schlechtesten Fall analysiert.

37:15.400 --> 37:17.820
Etwas, was ganz wichtig ist in der Prozessverarbeitung,

37:17.940 --> 37:19.160
Prozessdatenverarbeitung.

37:19.600 --> 37:22.140
Da haben Sie Echtzeitanforderungen und müssen sicherstellen, dass

37:22.140 --> 37:27.520
innerhalb einer bestimmten Maximalzeitvorgabe Ihr Algorithmus

37:27.520 --> 37:29.040
tatsächlich die Aufgabe erledigt hat.

37:29.160 --> 37:31.720
Deswegen ist Analyse im schlechtesten Fall ganz wichtig.

37:32.420 --> 37:35.640
Aber für viele Anwendungen reicht es völlig aus zu wissen, gerade wenn

37:35.640 --> 37:40.840
Sie Probleme häufig lösen müssen, also häufig folgen, sortieren

37:40.840 --> 37:43.440
müssen, reicht es aus, wie viel Sie im Schnitt brauchen, im Mittel

37:43.440 --> 37:44.600
brauchen für die Ausführung.

37:45.540 --> 37:48.580
Da müssen Sie allerdings wissen, wie Ihre Eingaben verteilt sind.

37:48.680 --> 37:54.240
Was ist eigentlich der Erwartungswert der Zeit, die Sie einsetzen?

37:55.180 --> 38:01.180
Und entsprechend schaut man sich das halt an und hat dann eine Analyse

38:01.180 --> 38:01.680
im Mittel.

38:05.340 --> 38:10.320
Zeitkomplexität ist etwas, was mit der Bewertung des Aufwandes

38:10.320 --> 38:12.780
eigentlich von Algorithmen zu tun hat.

38:14.500 --> 38:16.360
Schauen wir uns die Zeit jetzt genauer an.

38:17.460 --> 38:18.380
Und wie kann man das messen?

38:18.840 --> 38:24.080
Ich habe einen Algorithmus mit Eingabemenge X, irgendwas, Zahlen, wenn

38:24.080 --> 38:26.760
ich sortieren will, Folgen von Zahlen, wenn ich sortieren möchte.

38:28.080 --> 38:31.940
Und dann muss ich von dieser Menge X angeben, welche Größe die Eingabe

38:31.940 --> 38:35.660
hat, also bei den Folgen von Zahlen, wie viele Elemente habe ich in

38:35.660 --> 38:37.500
der Folge, wie groß sind die einzelnen Elemente.

38:37.500 --> 38:42.680
Und ich stelle fest, wie lange der Algorithmus braucht, bei Eingabe

38:42.680 --> 38:48.880
von einem speziellen Wert, also für eine spezielle Folge, werde ich

38:48.880 --> 38:50.820
eine bestimmte Rechenzeit meines Algorithmus haben.

38:51.540 --> 38:54.620
Und dann kann ich mir anschauen, die Zeitkomplexität im schlechtesten

38:54.620 --> 38:55.000
Fall.

38:55.560 --> 39:00.860
Das heißt, ich schaue mir an, das Maximum oder das Supremum aller

39:00.860 --> 39:04.620
einzelnen Rechenzeiten für alle möglichen Eingaben einer bestimmten

39:04.620 --> 39:05.040
Größe.

39:06.000 --> 39:08.160
Es ist klar, dass ich nur eine bestimmte Größe mich jetzt hier

39:08.160 --> 39:08.860
anschauen kann.

39:10.020 --> 39:12.720
Es kann sein, dass das ein einfaches Maximum ist, es kann sein, dass

39:12.720 --> 39:15.360
ich hier das tatsächliche Supremum anschauen muss.

39:16.480 --> 39:18.900
Und dann kann ich mir auch noch die mittlere Zeitkomplexität

39:18.900 --> 39:19.340
anschauen.

39:19.460 --> 39:24.120
Dafür brauche ich aber natürlich eine Annahme über die

39:24.120 --> 39:25.800
Wahrscheinlichkeitsverteilung der Eingaben.

39:25.960 --> 39:27.860
Was ist eigentlich mein Working Set?

39:28.680 --> 39:31.900
Was sind die Daten, die mit aller größten Wahrscheinlichkeit

39:31.900 --> 39:32.440
auftauchen?

39:32.440 --> 39:37.100
Und dann kann ich etwas sagen über die mittlere Zeitkomplexität.

39:37.920 --> 39:41.660
Häufig macht man hier Annahmen, die sagen, das sind alle gleich

39:41.660 --> 39:42.140
verteilt.

39:42.220 --> 39:43.500
Das muss aber nicht unbedingt zutreffen.

39:45.040 --> 39:47.420
Das, was ich jetzt hier aufgeschrieben habe für die Zeitkomplexität,

39:47.780 --> 39:51.640
kann man genauso für die Platzkomplexität machen und für die anderen

39:51.640 --> 39:53.460
Maße, die ich dort aufgeführt habe.

39:53.540 --> 39:57.420
Kann man alles bezogen auf eine einzelne Eingabe, bezogen auf Eingaben

39:57.420 --> 40:03.120
einer bestimmten Größe und dann eben mittleres Zeitverhalten,

40:03.560 --> 40:04.700
schlechtes Zeitverhalten.

40:04.800 --> 40:07.140
Oder man kann auch das beste Zeitverhalten angeben.

40:07.480 --> 40:10.360
Also die minimale Zeit, die ich brauche, egal welche Eingabe kommt.

40:10.780 --> 40:12.180
Das kann ich mir anschauen.

40:12.580 --> 40:16.280
Das Ziel ist, etwas zu sagen zu können über die Qualität des

40:16.280 --> 40:16.940
Algorithmus.

40:17.660 --> 40:19.220
Ich möchte ja sagen, mein Algorithmus ist gut.

40:20.440 --> 40:23.080
Es nützt nichts zu sagen, ich habe hier einen schönen Algorithmus, der

40:23.080 --> 40:23.720
ist ganz toll.

40:23.720 --> 40:28.220
Das kann man nur bewerten, wie gut er ist, wenn ich weiß, wie gut er

40:28.220 --> 40:30.840
ist im Verhältnis zu irgendetwas anderem.

40:31.520 --> 40:34.860
Das kann ich machen, indem ich ihn vergleiche mit anderen Algorithmen

40:34.860 --> 40:38.380
und sage, der ist besser als der Algorithmus, den Person X gemacht

40:38.380 --> 40:38.660
hat.

40:39.500 --> 40:45.460
Oder ich weiß, ich brauche eine gewisse Mindestzeit für die Lösung

40:45.460 --> 40:48.040
eines Problems.

40:48.760 --> 40:52.920
Und wenn ich nah dran bin an dieser unteren Schranke, dann ist das

40:52.920 --> 40:53.500
sicherlich gut.

40:53.500 --> 40:55.380
Je näher ich dran bin, desto besser werde ich.

40:55.520 --> 40:57.880
Also habe ich zwei Möglichkeiten, Aussagen über die Güte eines

40:57.880 --> 40:58.720
Verfahrens zu machen.

40:59.420 --> 41:01.100
Wie gut bin ich im Vergleich mit einem anderen?

41:01.640 --> 41:05.680
Und wie nah bin ich dran an dem, was mindestens erforderlich ist?

41:06.880 --> 41:11.560
Und erst dann kann ich also tatsächlich Aussagen machen über die Güte

41:11.560 --> 41:13.080
meiner Arbeit.

41:14.060 --> 41:18.840
Dieses Bild, diese Tabelle, die ich Ihnen hier auflege, die sollte man

41:18.840 --> 41:21.780
eigentlich kennen, wenn man sich das erste Mal mit Algorithmenanalyse

41:21.780 --> 41:22.460
beschäftigt.

41:22.840 --> 41:25.980
Müsste eigentlich in Informatik 1 gebracht worden sein, vermutlich

41:25.980 --> 41:26.540
aber nicht.

41:29.000 --> 41:31.480
Hat folgenden Hintergrund.

41:31.580 --> 41:34.980
Ich hatte gesagt, wir schauen uns an, das Verhalten eines Algorithmus

41:34.980 --> 41:38.940
bezogen auf feste Problemgrößen.

41:40.000 --> 41:42.900
Und da schaut man sich an, was man für eine feste Problemgröße für ein

41:42.900 --> 41:43.460
Verhalten hat.

41:43.460 --> 41:46.640
Und hier habe ich vier verschiedene Algorithmen aufgeführt, fiktiv,

41:47.240 --> 41:48.480
für die Lösung des gleichen Problems.

41:49.880 --> 41:51.900
Und diese vier Algorithmen haben sehr unterschiedliche

41:51.900 --> 41:52.800
Ausführungszeiten.

41:52.920 --> 41:56.940
Der eine braucht also 1000 mal n, wobei n die Problemgröße ist,

41:58.180 --> 41:58.960
Millisekunden.

41:59.180 --> 42:03.440
Der andere 200 n log n, einer 10 n² und einer braucht 2 hoch n.

42:04.060 --> 42:07.320
Und wenn Sie ein bisschen Idee haben von Algorithmen, wissen Sie

42:07.320 --> 42:10.500
nachher, also A4 wird ja niemand verwenden, exponentielles

42:10.500 --> 42:13.160
Zeitverhalten, der ist ja wahnsinnig schlecht.

42:13.860 --> 42:15.800
Wir nehmen immer den mit linearem Zeitverhalten.

42:16.300 --> 42:19.480
Und wenn Sie sich das anschauen, dann überlegt man sich, wie kann man

42:19.480 --> 42:20.460
das jetzt bewerten.

42:20.580 --> 42:22.300
Jetzt habe ich eine bestimmte Rechenzeit zur Verfügung.

42:22.500 --> 42:26.100
Ich habe ein Echtzeitproblem und ich muss innerhalb einer bestimmten

42:26.100 --> 42:29.040
Zeitspanne ein Problem lösen.

42:29.800 --> 42:32.100
Dann schaue ich mir an, was ich zum Beispiel innerhalb einer Sekunde

42:32.100 --> 42:34.740
machen kann, wie groß das Problem ist.

42:34.740 --> 42:38.620
Maximale Problemgröße g von x für eine fest vorgegebene Rechenzeit.

42:39.180 --> 42:43.380
Und stelle fest, wenn ich eine Sekunde zur Verfügung habe, dann ist

42:43.380 --> 42:47.980
bei diesen Algorithmen für eine Sekunde Rechenzeit der Algorithmus mit

42:47.980 --> 42:51.540
der größten Problemgröße derjenige, der ein quadratisches Verhalten

42:51.540 --> 42:51.860
hat.

42:52.300 --> 42:56.980
10 n² ist halt erlaubt eine Problemgröße von 10, während der mit 1000

42:56.980 --> 42:59.000
n nur eine Problemgröße von 1 erlaubt.

42:59.220 --> 43:00.100
Nicht gerade sehr groß.

43:00.920 --> 43:06.360
Und Sie sehen, der mit dem exponentiellen Verhalten, der hat eine

43:06.360 --> 43:08.100
Problemgröße von 9, gar nicht so schlecht.

43:08.860 --> 43:12.720
Also der mit dem linearen Zeitverhalten der schlechteste für diese

43:12.720 --> 43:13.920
vorgegebene Rechenzeit.

43:14.680 --> 43:16.280
Und das entwickelt sich natürlich dann weiter.

43:16.800 --> 43:21.060
Man sieht für eine Minute Rechenzeit zur Verfügung steht, verändert

43:21.060 --> 43:21.620
sich das schon.

43:21.700 --> 43:24.600
Das ist aber immer noch der mit der quadratischen Laufzeit immer noch

43:24.600 --> 43:28.020
der, der die größte Problemgröße bearbeiten kann.

43:29.180 --> 43:32.460
Sobald man aber dann auf größere Zeiten geht, stellt man fest, dann

43:32.460 --> 43:35.100
ist das erwartete Verhalten da, dass ich also z.B.

43:35.140 --> 43:39.220
bei 10 Stunden stelle ich fest, da habe ich also eine Problemgröße von

43:39.220 --> 43:43.820
36.000 mit dem linearen Verfahren und nur eine von 21 mit dem

43:43.820 --> 43:45.040
exponentiellen Verfahren.

43:45.200 --> 43:50.480
Also hier sind wir 27 bei 10 Stunden mit dem exponentiellen Verfahren.

43:51.520 --> 43:56.520
Da bestätigt sich halt das so schlechte asymptotische Verhalten.

43:56.520 --> 44:02.820
Aber das interessante ist, der lineare Algorithmus ist optimal für

44:02.820 --> 44:04.820
alle Problemgrößen größer gleich 101.

44:06.140 --> 44:09.340
Der mit dem Verhalten nlog n ist im Vergleich dieser vier Verfahren

44:09.340 --> 44:09.960
nie der beste.

44:11.380 --> 44:15.660
Der mit dem quadratischen Verhalten ist für einen bestimmten Bereich

44:15.660 --> 44:19.540
zwischen 10 und 100 gerade der optimale.

44:19.920 --> 44:24.340
Und der mit dem exponentiellen Verhalten ist für kleine Problemgrößen

44:24.340 --> 44:24.720
hervorragend.

44:24.720 --> 44:29.220
Und das liegt halt daran, dass wir hier jeweils Konstanten davor

44:29.220 --> 44:31.440
stehen haben, die sehr unterschiedlich sind.

44:31.540 --> 44:36.640
Und die Konstanten können halt für bestimmte Problemgrößen sehr

44:36.640 --> 44:43.040
entscheidend sein bezüglich der Entscheidung, welches Verfahren setzt

44:43.040 --> 44:47.600
sich ein in einem bestimmten Anwendungsbereich, in dem ich weiß, meine

44:47.600 --> 44:50.040
Probleme haben eine feste Problemgröße.

44:51.120 --> 44:53.480
Und dann muss ich für diese Problemgröße den besten Algorithmus

44:53.480 --> 44:53.800
finden.

44:53.800 --> 44:56.960
Dann interessiert mich das asymptotische Verhalten eigentlich gar

44:56.960 --> 44:57.340
nicht mehr.

44:57.800 --> 45:01.140
Ein asymptotisches Verhalten ist ja etwas, was wir uns durchaus

45:01.140 --> 45:04.160
anschauen, aber es reicht eben einfach nicht aus.

45:04.880 --> 45:06.520
Und hier ist das nochmal kurz dargestellt.

45:06.900 --> 45:11.740
Also hier steht nochmal Vergleich dieser Verfahren T a4.

45:11.980 --> 45:17.480
Also die Zeit des Algorithmus a4 für Problemgröße 10 ist in etwa die

45:17.480 --> 45:19.180
des Verfahrens a3.

45:20.140 --> 45:26.820
Ziemlich vergleichbar, aber wenn ich mir die Problemgröße 25 anschaue,

45:26.980 --> 45:33.360
dann ist der Algorithmus mit quadratischem Verhalten bereits 5400 mal

45:33.360 --> 45:38.100
schneller als der mit dem exponentiellen Verhalten.

45:38.760 --> 45:41.720
Das heißt, da sind dann drastische Unterschiede.

45:42.720 --> 45:44.780
Und man könnte sagen, sowas passiert ja eigentlich nicht.

45:45.580 --> 45:47.440
Ich werde ja nicht solche großen Bandbreiten haben.

45:48.540 --> 45:51.520
Also zumindest für kleinere Unterschiede sieht man hier sehr schnell,

45:51.680 --> 45:53.760
dass es sowas geben kann.

45:54.500 --> 45:57.400
Schauen Sie sich das Problem an der Polynomauswertung.

45:57.460 --> 45:58.680
Hatte ich vorhin kurz aufgeführt.

45:58.780 --> 46:01.060
Ein wichtiges Problem, das man häufig bearbeiten muss.

46:01.560 --> 46:04.600
Sie wollen eine Summe a, i, x, o, i auswerten, also irgend so ein

46:04.600 --> 46:09.580
Polynom endengerades mit Koeffizienten a, n, a, n-1 bis a, 0.

46:11.060 --> 46:12.600
Das kann man sehr unterschiedlich machen.

46:12.600 --> 46:17.580
Sie können das naiv machen, indem Sie einfach hier von links nach

46:17.580 --> 46:18.620
rechts das auswerten.

46:18.940 --> 46:22.400
Dann rechnen Sie halt a, 0 mal x mal x mal x mal x mal x und so weiter

46:22.400 --> 46:23.360
bis Sie x, o, n haben.

46:23.720 --> 46:25.920
Plus a, n-1 mal und so weiter.

46:26.440 --> 46:28.520
Ganz stur von links nach rechts ausgewertet.

46:28.520 --> 46:37.180
Gibt das n-halbe mal n plus 1 Multiplikation, weil Sie n, n-1, n-2 und

46:37.180 --> 46:44.160
so weiter Summe aller i von 1 bis n hier drin haben, plus n

46:44.160 --> 46:44.520
Additionen.

46:45.120 --> 46:47.020
Und das ist sicherlich quadratisches Verhalten.

46:47.740 --> 46:51.260
Und wenn Sie das geschickter machen und ein bisschen ausklammern, dann

46:51.260 --> 46:55.660
stellen Sie fest, dass Sie hier drin eine Multiplikation machen, dann

46:55.660 --> 47:00.380
eine Addition, dann wieder eine Multiplikation, aber eben mit einem

47:00.380 --> 47:02.520
Klammerausdruck und so weiter.

47:03.520 --> 47:05.580
Dann kommen Sie auf n Multiplikationen und n Additionen.

47:06.380 --> 47:10.540
Nur ein bisschen umgruppieren der einzelnen Berechnungen, ausnutzen

47:10.540 --> 47:15.100
von Distributivgesetz ermöglicht Ihnen hier ein deutlich besseres

47:15.100 --> 47:15.640
Verfahren.

47:15.640 --> 47:22.560
Das heißt, von einem Aufwand, der also methodisch abgeschätzt wird mit

47:22.560 --> 47:27.120
O von n², kommen wir auf O von n arithmetische Operationen.

47:27.200 --> 47:29.600
Lineares Verhalten von quadratischem zu linearem Verhalten durch ein

47:29.600 --> 47:31.420
ganz einfaches Umrechnen.

47:32.200 --> 47:36.580
Und so etwas taucht eben durchaus in der Praxis auf und zeigt, dass

47:36.580 --> 47:41.680
man da sehr aufpassen muss, was man eigentlich macht, wenn man ein

47:41.680 --> 47:42.420
Programm schreibt.

47:42.420 --> 47:47.700
Also solche Ausdrücke zu berechnen, das taucht in vielen Bereichen

47:47.700 --> 47:49.180
auf, Statistik und ähnliches.

47:49.560 --> 47:53.720
Und ich bin sicher, dass die guten Verfahren natürlich alle das

47:53.720 --> 47:56.240
effizient machen, aber Sie können sicher sein, dass es viele Programme

47:56.240 --> 47:58.480
gibt, in denen etwas schlecht gemacht wird.

47:59.100 --> 48:01.500
Und das könnte man dann sehr deutlich verbessern.

48:01.940 --> 48:05.120
Jetzt stehen hier unten so ein paar Dinge in O von n², O von n.

48:06.260 --> 48:08.980
Ich hoffe, dass Ihnen das allen noch bekannt ist.

48:09.020 --> 48:10.920
Nur mal ganz kurz, noch mal zur Wiederholung.

48:11.900 --> 48:17.960
Groß O von f, wenn also f irgendeine Funktion ist, die ganze Zahlen

48:17.960 --> 48:21.340
abbildet in die reellen Zahlen, also irgendeine Kostenfunktion.

48:23.000 --> 48:27.940
Dann ist O von f eine Menge von Funktionen, gerade die Menge aller

48:27.940 --> 48:34.700
Funktionen, die in ihrem Wachstum durch f von n nach oben beschränkt

48:34.700 --> 48:35.020
sind.

48:35.620 --> 48:41.760
Nicht genau, sondern bis auf einen konstanten Faktor und nicht für

48:41.760 --> 48:43.220
alle n, sondern für fast alle n.

48:43.620 --> 48:49.660
Das heißt, es gibt ein n0, ein genügend großes n.

48:49.720 --> 48:52.720
Wenn ich also hier das aufmale, dann kann es also sein, dass ich hier

48:52.720 --> 48:54.620
irgend so eine Funktion habe, f.

48:55.200 --> 48:57.980
Und es kann also durchaus sein, dass wenn das hier das f ist und ich

48:57.980 --> 49:00.900
habe eine Funktion g, die kann durchaus hier irgendwo höher liegen,

49:00.980 --> 49:08.540
weil irgendwann läuft sie unterhalb von f bzw.

49:08.980 --> 49:11.840
unterhalb von irgendeinem c mal f, Konstante mal f.

49:12.540 --> 49:18.660
Das heißt, ich kann im Prinzip das Verhalten der Funktion g für großes

49:18.660 --> 49:22.960
n abschätzen durch das Verhalten von f bis auf eine Konstante.

49:23.280 --> 49:24.300
Das ist also O von f.

49:25.640 --> 49:29.060
Und das kann ich auch, gibt es ja noch mehr, die Groß-O ist ja nur

49:29.060 --> 49:30.920
eine dieser Notationen, Klein-O.

49:31.760 --> 49:35.260
Da habe ich eine wesentlich stärkere Aussage.

49:35.260 --> 49:41.520
Da wächst nämlich f von n wesentlich stärker als meine Funktion g.

49:43.280 --> 49:47.340
Wenn ich also dann n gegen unendlich gehen lasse und das Verhältnis

49:47.340 --> 49:50.000
von g von n und f von n anschaue, bekomme ich eine Nullfolge.

49:50.760 --> 49:51.340
Also z.B.

49:52.080 --> 49:52.680
Wurzeln.

49:53.640 --> 49:58.560
Ich könnte hinschreiben, Wurzeln ist aus Klein-O von n.

49:58.560 --> 50:03.600
Wenn Sie Wurzeln durch n gegen unendlich gehen lassen, bekommen Sie

50:03.600 --> 50:04.780
eine Nullfolge.

50:05.900 --> 50:10.520
Also Wurzeln wächst wesentlich langsamer als n.

50:13.760 --> 50:19.620
Aber das Groß-O sagt nur, das Wachstum ist nicht größer als Konstante

50:19.620 --> 50:20.120
mal f.

50:20.400 --> 50:22.580
Aber es kann durchaus im gleichen Bereich laufen.

50:22.580 --> 50:27.300
Dann haben wir für die umgekehrte Sichtweise auch noch die unteren

50:27.300 --> 50:27.780
Schranken.

50:28.080 --> 50:30.920
Groß -Omega von f, da haben wir einfach nur das Vorzeichen hier

50:30.920 --> 50:31.320
geändert.

50:32.460 --> 50:39.240
Das heißt, die Funktionen g wachsen alle mindestens so stark wie, also

50:39.240 --> 50:41.500
nicht langsamer als das f.

50:43.580 --> 50:53.780
Und Klein-Omega von f heißt, die Funktionen wachsen deutlich schneller

50:53.780 --> 50:54.380
als f.

50:55.580 --> 50:58.220
Da haben wir also genau auch hier wieder dieses Verhältnis.

50:58.780 --> 51:03.240
Und in diesem Fall wächst also die Funktion g wesentlich stärker als

51:03.240 --> 51:05.020
die Funktion f, die hier drin steht.

51:05.600 --> 51:07.020
Ganz systematisch aufgeschrieben.

51:07.400 --> 51:08.680
Warum macht man das überhaupt?

51:08.680 --> 51:12.500
Sie kennen das Ganze ja schon aus Informatik 1.

51:13.460 --> 51:21.160
Man verwendet dies einfach, um die Analyse von Algorithmen etwas

51:21.160 --> 51:25.220
einfacher aufschreiben zu können, um einfach komplizierte Ausdrücke

51:25.220 --> 51:29.820
durch den Term größter Ordnung abschätzen zu können, durch die höchste

51:29.820 --> 51:31.580
Potenz, wenn Sie ein Polynom haben.

51:33.380 --> 51:39.340
Sie müssen also nicht hinschreiben, n hoch 3 mal log²n plus irgendwie

51:39.340 --> 51:43.580
2000 n² usw.

51:43.940 --> 51:47.900
Das schreiben Sie halt in, das ist irgendwas Groß-O von n hoch 3

51:47.900 --> 51:48.580
log²n.

51:50.160 --> 51:54.360
Und Sie können dadurch Ausdrücke einfach vereinfachen und können die

51:54.360 --> 51:55.380
Analyse vereinfachen.

51:56.200 --> 52:00.400
Eins hatte ich noch vergessen hier, Groß-Θ von f ist gerade der

52:00.400 --> 52:05.260
Durchschnitt von Groß-Ω an Groß-Ω, beziehungsweise charakterisiert

52:05.260 --> 52:10.700
dadurch, dass das g von unten und von oben beschränkt wird im Wachstum

52:10.700 --> 52:14.280
durch eine Konstante mal fn bzw.

52:14.560 --> 52:17.660
eine Funktion durch diese Konstante.

52:18.120 --> 52:21.200
Das heißt, ich habe hier das Wachstum von g wesentlich genauer

52:21.200 --> 52:22.580
charakterisiert durch das f.

52:24.120 --> 52:26.620
Und lax kann man das Ganze ein bisschen anders schreiben.

52:27.000 --> 52:30.540
Richtig wäre zu sagen, eine Funktion liegt in O von f, ist ein Element

52:30.540 --> 52:30.940
davon.

52:31.380 --> 52:34.840
Sie finden häufig die Schreibweise g gleich O von f, was aber

52:34.840 --> 52:38.280
natürlich nicht richtig ist, das ist keine symmetrische Relation,

52:39.060 --> 52:40.600
sondern das ist halt so eine Elementrelation.

52:42.820 --> 52:47.180
Und Sie finden eben auch statt Groß-O von f enthaltene Groß-O von g,

52:47.920 --> 52:52.060
schreibt man manchmal Groß-O von f gleich Groß-O von g. Wie gesagt, es

52:52.060 --> 52:57.900
ist nicht symmetrisch, es ist durchaus Groß-O von n enthalten in Groß

52:57.900 --> 52:59.180
-O von n².

53:00.600 --> 53:05.360
Aber natürlich ist es nicht gleich, es sind nicht die gleichen Mengen,

53:06.020 --> 53:10.100
sondern da sind deutlich mehr Funktionen in Groß-O von n² drin als in

53:10.100 --> 53:10.820
Groß -O von n.

53:13.100 --> 53:14.760
Und hier habe ich es nochmal angegeben.

53:15.780 --> 53:22.360
Groß-O von n² ist ungleich Groß-O von n, aber insofern, wenn man das

53:22.360 --> 53:26.140
mit Gleichheitszeichen schreibt, dann darf man das bei Groß-O nur von

53:26.140 --> 53:29.800
links nach rechts lesen und dann muss es richtig sein, dass hier alles

53:29.800 --> 53:30.520
enthalten sein soll.

53:31.400 --> 53:37.260
Man sollte einfach nur diese Notation hier verwenden und nicht das

53:37.260 --> 53:38.600
Gleichheitszeichen, das ist einfach besser.

53:39.920 --> 53:44.280
Das waren jetzt Aufwände für einen Algorithmus und jetzt wollen wir

53:44.280 --> 53:47.640
aber auch den Aufwand für ein Problem abschätzen können.

53:48.320 --> 53:51.280
Komplexität eines Problems, einer Funktion, wie machen wir das?

53:51.900 --> 53:54.420
Da gibt es einerseits eine untere Schranke, hatte ich gesagt, aber

53:54.420 --> 53:57.700
untere Schranke ist etwas Schwieriges, weil wir nämlich etwas sagen

53:57.700 --> 54:01.560
müssen über alle Algorithmen, die ein Problem lösen.

54:01.560 --> 54:05.160
Das heißt, eine untere Schranke für Sortieren, muss etwas sagen über

54:05.160 --> 54:09.760
alle möglichen Verfahren, die ein Sortierproblem lösen, das ist

54:09.760 --> 54:12.720
offensichtlich eine schwierige Aufgabe und man könnte dann sagen, dass

54:12.720 --> 54:17.260
also die Zeitkomplexität des Algorithmus A aus Omega von F liegt.

54:17.480 --> 54:18.860
Dann ist F eine untere Schranke.

54:19.720 --> 54:27.420
Für jeden Algorithmus ist der Zeitaufwand mindestens so groß wie durch

54:27.420 --> 54:28.880
F asymptotisch vorgegeben.

54:28.880 --> 54:34.320
Und es ist eine obere Schranke für die Zeitkomplexität, wenn es einen

54:34.320 --> 54:37.460
Algorithmus mit dieser Zeitkomplexität gibt.

54:38.080 --> 54:41.000
Das heißt, das ist wesentlich einfacher nachzuweisen, sobald Sie einen

54:41.000 --> 54:43.600
Algorithmus haben, der ein Problem löst, haben Sie eine obere Schranke

54:43.600 --> 54:47.680
und dann können Sie Algorithmen vergleichen oder auch zur unteren

54:47.680 --> 54:49.800
Schranke hin vergleichen, wenn Sie eine untere Schranke haben.

54:50.920 --> 54:56.620
Es gibt Probleme, bei denen wir tatsächlich optimale Zeitkomplexität

54:56.620 --> 54:57.320
erreichen können.

54:57.320 --> 55:01.280
Das heißt, wir treffen genau die untere Schranke, nicht nur

55:01.280 --> 55:03.540
asymptotisch, sondern sogar bis auf konstante Faktoren.

55:04.240 --> 55:06.740
Das sind wenige Probleme, bei denen das der Fall ist.

55:06.820 --> 55:07.520
Ich werde Ihnen ein paar davon zeigen.

55:09.680 --> 55:13.640
In der Regel ist es also schwierig, gute untere Schranken zu

55:13.640 --> 55:14.060
bestimmen.

55:16.360 --> 55:19.160
Und das Problem ist natürlich, dass ich ohne Kenntnis unterer

55:19.160 --> 55:21.720
Schranken nicht sagen kann, ob ein Algorithmus optimal ist oder nicht.

55:22.380 --> 55:25.180
Wenn Sie eine untere Schranke können, dann wissen Sie auf jeden Fall,

55:25.260 --> 55:29.440
wenn Sie einen Algorithmus zur Verfügung haben, ob es Sinn macht, noch

55:29.440 --> 55:33.480
in Verbesserungen Aufwand reinzustecken oder ob man bereits am unteren

55:33.480 --> 55:35.140
Ende der Fahnenstange angelangt ist.

55:35.480 --> 55:39.340
Wobei man sich immer eines im Klaren sein muss, die Aussagen über

55:39.340 --> 55:42.520
untere Schranken haben sehr viel damit zu tun, welche Annahmen ich

55:42.520 --> 55:43.420
über das Problem mache.

55:43.520 --> 55:46.720
Und es kann sein, dass einfach Änderungen bei der Problemdefinition

55:46.720 --> 55:53.100
auf einmal zu neuen Schranken führen, die es deutlich einfacher

55:53.100 --> 55:55.120
machen, das Problem zu lösen.

55:56.300 --> 55:57.700
Wie messe ich Zeiten?

55:58.140 --> 55:59.460
Das hatte ich auch schon gesagt.

55:59.520 --> 56:00.720
Man kann es mit der Stoppuhr machen.

56:00.860 --> 56:09.720
Man kann die Laufzeit des Programms irgendwie charakterisieren.

56:09.720 --> 56:15.980
Man kann im Programm spezielle Anweisungen einbauen, um Zeiten zu

56:15.980 --> 56:16.280
messen.

56:16.420 --> 56:18.960
Das ist durchaus sinnvoll, das zu machen, um konkret zu sehen, wie

56:18.960 --> 56:22.460
wirkt sich eine bestimmte Rechenstruktur oder Algorithmus auf die

56:22.460 --> 56:24.120
konkrete Laufzeit aus.

56:25.860 --> 56:29.620
Und die genaueste Messung, wenn Sie jetzt sprechen, Zeit wirklich

56:29.620 --> 56:30.240
messen wollen.

56:30.880 --> 56:33.760
Also Stoppuhr würde ja bedeuten, ich setze mich daneben und messe

56:33.760 --> 56:34.080
einfach.

56:34.160 --> 56:38.160
Das Problem ist nur, im Rechner laufen viele Programme ab, nicht nur

56:38.160 --> 56:38.880
Ihr eigenes Programm.

56:38.880 --> 56:41.800
Und wenn Sie dann messen, dann messen Sie die Rechenzeit von vielen

56:41.800 --> 56:45.220
Programmen und nicht nur von Ihrem, das Sie gerade messen wollen.

56:45.640 --> 56:49.700
Deswegen ist es sinnvoll, in einem einzelnen Programm etwas zu messen

56:49.700 --> 56:53.960
und sogar innerhalb eines Programms einen speziellen Abschnitt zu

56:53.960 --> 56:54.660
messen.

56:54.900 --> 56:59.460
Das Problem ist nur, der Code, den Sie messen wollen, ist eventuell

56:59.460 --> 57:02.180
gar nicht so lang, dass Sie das vernünftig messen können.

57:02.660 --> 57:05.360
Deswegen macht es Sinn, so etwas häufig auszuführen.

57:05.360 --> 57:12.040
Da muss man nur aufpassen, dass Ihnen nicht der Rechner oder der

57:12.040 --> 57:16.320
Compiler solche vielfach wiederholten Schleifen der gleichen Aufgabe

57:16.320 --> 57:17.240
wieder herausoptimiert.

57:18.000 --> 57:19.380
Aber das kann man hinkriegen.

57:21.060 --> 57:25.040
Zu messenden Codes sehr oft ausführen, dann bekommt man eine große

57:25.040 --> 57:27.940
Rechenzeit und dann kann man sagen, was die mittlere Ausführungszeit

57:27.940 --> 57:28.840
ist für dieses Code-Stück.

57:29.500 --> 57:31.700
Das ist etwas, was man auch gut in Übungen machen kann.

57:31.820 --> 57:35.840
Einfach feststellen, wie kann man tatsächlich Laufzeiten messen.

57:36.260 --> 57:38.860
Oder man kann auch eine Profiling-Option bei der Programmausführung

57:38.860 --> 57:41.560
nutzen und feststellen, was sind so kritische Pfade im Programm.

57:42.700 --> 57:45.720
Dazu muss man aber dann Compiler und Laufzeitsysteme ein bisschen

57:45.720 --> 57:46.420
genauer kennen.

57:47.340 --> 57:49.880
Und man muss aufpassen, dass man bei der Messung natürlich

57:49.880 --> 57:53.420
Programmoptimierung ausschaltet, denn es könnte sein, dass Dinge in

57:53.420 --> 57:57.140
Ihrem Programm drin sind, die durch einen Optimierer rausgenommen

57:57.140 --> 57:57.640
werden.

57:58.600 --> 58:06.980
Und die Programmoptimierung kann eventuell Dinge verfälschen in Bezug

58:06.980 --> 58:09.200
auf den Aufwand, den Sie eigentlich messen wollten.

58:10.000 --> 58:13.080
Alternative ist, dass man nicht die Zeit konkret misst, sondern dass

58:13.080 --> 58:18.020
man einfach nur ein Modell macht und sagt, ich nehme irgendetwas an

58:18.020 --> 58:22.480
über Zeiteinheiten einer abstrakten Maschine und da sowieso die

58:22.480 --> 58:25.060
Zeiteinheiten auf verschiedenen Rechnern unterschiedlich lange sein

58:25.060 --> 58:29.900
werden, habe ich dann eine so grobe Abschätzung darüber, was die

58:29.900 --> 58:33.540
erwartete Rechenzeit eines Algorithmus auf einem bestimmten Rechner

58:33.540 --> 58:34.100
sein müsste.

58:34.440 --> 58:36.760
Ich muss da nur die Zeiteinheit kennen, dann kann ich das ineinander

58:36.760 --> 58:37.240
überführen.

58:37.900 --> 58:40.940
Und das ist das, was wir in dieser Vorlesung im Wesentlichen machen

58:40.940 --> 58:43.540
werden, dass wir uns ein geeignetes Berechnungsmodell hernehmen und

58:43.540 --> 58:48.000
dann die Zeiteinheiten in Bezug auf dieses Rechnungsmodell genauer

58:48.000 --> 58:48.380
anschauen.

58:49.080 --> 58:52.620
Und damit sind wir am Ende dieses Kapitels Einführung und auch am Ende

58:52.620 --> 58:53.480
der heutigen Vorlesung.

58:53.620 --> 58:55.480
Vielen Dank für die Aufmerksamkeit, ich hoffe, dass Sie dann auch

58:55.480 --> 58:56.040
nächste Woche wieder da sein werden.