WEBVTT

00:00.060 --> 00:01.660
So, schönen guten Morgen.

00:01.780 --> 00:06.820
Ich begrüße Sie zur letzten Sitzung der Vorlesung Effiziente

00:06.820 --> 00:07.420
Algorithmen.

00:08.140 --> 00:11.660
Letztes Mal haben wir uns mit verschiedenen Themen beschäftigt.

00:11.780 --> 00:15.380
Ich habe einerseits noch mal kurz was erzählt zu der parallelen

00:15.380 --> 00:24.640
Variante des Wortschallalgorithmus, wie man das macht mit dieser

00:24.640 --> 00:28.660
wellenartigen Programmierung des zweidimensionalen Feldes, um den

00:28.660 --> 00:31.260
Wortschallalgorithmus so im Pipelining-Verfahren durchzuführen.

00:31.920 --> 00:34.380
Ich hoffe, dass das dadurch etwas klarer geworden ist.

00:34.460 --> 00:36.480
Wir haben uns dann mit der algorithmischen Geometrie weiter

00:36.480 --> 00:37.160
beschäftigt.

00:37.660 --> 00:43.760
Da hatten wir uns zunächst mal beschäftigt gehabt mit genau diesem

00:43.760 --> 00:50.780
Problem hier, mit dem Problem, wie man feststellen kann, ob ein Punkt

00:50.780 --> 00:54.040
innerhalb eines einfachen Polygons liegt oder nicht, beziehungsweise

00:54.040 --> 00:55.280
eines konvexen Polygons.

00:55.380 --> 00:56.560
Beim einfachen war es etwas schwieriger.

00:57.300 --> 01:01.000
Dummerweise muss ich beim Abspeichern oder beim Beenden der

01:01.000 --> 01:04.660
Präsentation letztes Mal auf den falschen Knopf gedrückt haben und

01:04.660 --> 01:06.920
gesagt haben, Annotationen verwerfen.

01:07.540 --> 01:11.500
Das heißt, die Annotationen sind in den folgenden Seiten leider nicht

01:11.500 --> 01:11.980
vorhanden.

01:12.100 --> 01:13.640
In der Aufzeichnung sind sie natürlich da.

01:14.340 --> 01:15.560
Insofern ist das kein Problem.

01:16.300 --> 01:19.340
Aber sie sind halt leider nicht auf den Folien.

01:19.360 --> 01:20.360
Ist, glaube ich, nicht ganz so schlimm.

01:20.460 --> 01:21.500
Sie haben das in der Aufzeichnung.

01:22.600 --> 01:25.620
Ich weiß nicht, ob wir die Fenster offen lassen können.

01:25.740 --> 01:27.700
Das ist ziemlich laut von der Seite.

01:28.900 --> 01:30.280
Ich glaube, das stört doch etwas.

01:30.980 --> 01:33.820
Es ist zwar auch ziemlich warm, aber es ist auch von draußen warm.

01:34.360 --> 01:36.860
Also noch kann es sein, dass es hier im Hörsaal etwas kühler ist als

01:36.860 --> 01:37.160
draußen.

01:38.280 --> 01:41.440
Deswegen ist es nicht unbedingt ein Vorteil, die Fenster offen zu

01:41.440 --> 01:41.660
haben.

01:43.320 --> 01:44.020
Vielen Dank.

01:44.700 --> 01:48.340
So, jetzt haben wir... Es klingt ganz anders sofort.

01:49.100 --> 01:50.520
In dem Raum ist es halt etwas stärker.

01:52.020 --> 01:54.580
Gut, wir können das alles sehen dort.

01:54.980 --> 01:59.920
Wir haben also jetzt mit diesem Problem das letzte Mal beschäftigt

01:59.920 --> 02:00.180
gehabt.

02:00.240 --> 02:03.340
Ich hatte Ihnen gezeigt, wie man die wesentliche Operation dabei

02:03.340 --> 02:06.380
bearbeitet, nämlich festzustellen, ob ein Punkt links oder rechts von

02:06.380 --> 02:07.200
einer Geraden liegt.

02:07.600 --> 02:09.660
Das haben wir gesehen, kann man über die Berechnung einer

02:09.660 --> 02:13.720
Determinanten aus den drei Punkten oder aus drei Punkten feststellen.

02:14.300 --> 02:17.580
Wenn man also die zwei Punkte für eine Gerade hat, kann man also

02:17.580 --> 02:22.680
feststellen, beziehungsweise man kann feststellen, ob der Winkel QRPI

02:22.680 --> 02:25.380
eine Linksdrehung oder Rechtsdrehung ist.

02:25.460 --> 02:26.600
Das ist das Wesentliche.

02:27.180 --> 02:29.200
Und das braucht man halt an vielen Stellen.

02:29.320 --> 02:33.520
Wir hatten das gesehen, dass das relativ einfach zu berechnen ist und

02:33.520 --> 02:37.100
hatten uns dann mit dem Problem beschäftigt, die Überschneidung von

02:37.100 --> 02:38.140
Kanten festzustellen.

02:38.140 --> 02:41.860
Eigentlich ist das hier, was ich Ihnen gezeigt habe, der Algorithmus

02:41.860 --> 02:46.140
von Bentley-Ottmann, ein Algorithmus, um alle Schnittpunkte von

02:46.140 --> 02:47.780
Liniensegmenten festzustellen.

02:48.300 --> 02:51.420
Ich habe das hier angewandt auf das Problem festzustellen, ob ein

02:51.420 --> 02:53.140
Polygon einfach ist oder nicht.

02:53.500 --> 02:56.600
Aber das ist eben einfach eine Anwendung dieses Algorithmus, um alle

02:56.600 --> 03:00.880
sich schneidenden Linien oder alle Schnittpunkte von Liniensegmenten

03:00.880 --> 03:02.940
zu bekommen.

03:03.560 --> 03:06.900
Und wir hatten gesehen, dass man hier eben dieses schöne Sweep-Line

03:06.900 --> 03:09.760
-Verfahren hat, bei dem man im Wesentlichen eine Folge von

03:09.760 --> 03:15.780
eindimensionalen Problemen löst, um ein zweidimensionales Problem zu

03:15.780 --> 03:16.400
bearbeiten.

03:17.180 --> 03:20.080
Wir hatten uns dann kurz noch darüber unterhalten, inwieweit man das

03:20.080 --> 03:21.400
auch parallelisieren kann.

03:22.160 --> 03:25.360
Es ist klar, dass man das Problem der Bestimmung von Schnittpunkten

03:25.360 --> 03:28.920
von Kanten parallelisieren kann, indem man einfach alle möglichen

03:28.920 --> 03:30.680
Kanten paarweise vergleicht.

03:30.680 --> 03:32.660
Das ist also ein einfacher paralleler Ansatz.

03:33.240 --> 03:36.580
Dieses Verfahren, das Sweep-Line-Verfahren zu parallelisieren, habe

03:36.580 --> 03:37.640
ich so nicht gefunden.

03:37.740 --> 03:39.940
Ich habe nochmal ein bisschen gesucht, habe das aber nicht gefunden.

03:40.040 --> 03:41.880
Vielleicht hat es einer von Ihnen mal versucht.

03:42.120 --> 03:43.680
Ich habe dazu also nichts gesehen.

03:44.360 --> 03:46.860
Das ist natürlich ein inhärent sequenzielles Verfahren.

03:47.000 --> 03:50.600
Das, was da auf das Sweep-Line abläuft, ist immer der Zustand, der

03:50.600 --> 03:54.580
aktuell eingetreten ist, nachdem man vollständig von links nach rechts

03:54.580 --> 03:56.040
bis zu dem Punkt gelaufen ist.

03:56.040 --> 04:00.020
Und insofern ist dieses Sweep-Line-Verfahren eben inhärent sequenziell

04:00.020 --> 04:04.580
und damit auch schwer zu parallelisieren, beziehungsweise da muss sich

04:04.580 --> 04:07.060
halt diese sequenzielle Struktur aufrechterhalten.

04:07.180 --> 04:10.700
Das heißt, man könnte vielleicht mit Pipelining oder sowas

04:10.700 --> 04:14.420
unterschiedliche solche Probleme bearbeiten, nacheinander, aber das

04:14.420 --> 04:15.920
bringt im Augenblick hier nichts.

04:16.380 --> 04:19.180
Wäre trotzdem interessant zu sehen, was man daran machen kann, habe

04:19.180 --> 04:21.360
ich aber hier nicht weiter behandelt.

04:21.440 --> 04:23.980
Wir hatten dann als nächstes Problem uns angeguckt, das Problem der

04:23.980 --> 04:24.580
konvexen Hülle.

04:26.000 --> 04:34.260
Und bei der konvexen Hülle ist eben das Problem, ich habe eine Menge

04:34.260 --> 04:37.240
von Punkten, möchte sehen, was sind die Extrempunkte, beziehungsweise

04:37.240 --> 04:41.160
was ist eigentlich die kleinste umschließende Fläche.

04:42.040 --> 04:45.900
Und das ist ein klassisches Problem aus der Geometrie, braucht man an

04:45.900 --> 04:49.420
vielen Stellen und insbesondere muss man dann eben sehen, wie man das

04:49.420 --> 04:54.300
mit Methoden der algorithmischen Geometrie auf dem Rechner sinnvoll

04:54.300 --> 04:55.020
machen kann.

04:55.400 --> 04:59.280
Ich hatte Ihnen dazu einen Ansatz vorgestellt, bei dem man einfach

04:59.280 --> 05:03.620
sagt, was ist ein Extrempunkt oder was ist kein Extrempunkt.

05:03.720 --> 05:06.360
Das ist ein Punkt, der halt im Inneren liegt und ein Punkt liegt im

05:06.360 --> 05:09.480
Inneren, wenn er zum Beispiel im Inneren eines Dreiecks aus drei

05:09.480 --> 05:10.140
Punkten liegt.

05:10.140 --> 05:13.640
Das war also einfach dann die Idee, nehme ich nochmal diese Erkenntnis

05:13.640 --> 05:19.480
und überprüfe eigentlich einfach alle möglichen Dreiecke aus drei

05:19.480 --> 05:22.640
Punkten der Menge und stelle fest, ob ein Punkt X innerhalb eines

05:22.640 --> 05:23.500
solchen Dreiecks liegt.

05:23.860 --> 05:26.260
Sobald ich eins gefunden habe, weiß ich, das ist kein Extrempunkt.

05:26.700 --> 05:30.620
Geht parallel hervorragend, aber leider mit einem sehr hohen

05:30.620 --> 05:34.960
Gesamtaufwand, nämlich Aufwand N4, weil ich für N Punkte diese

05:34.960 --> 05:38.380
Probleme bearbeiten muss, könnte man sicherlich noch etwas reduzieren,

05:38.440 --> 05:42.500
den Aufwand, weil man da viele Sachen redundant macht, aber das

05:42.500 --> 05:45.740
Wesentliche war, es geht hervorragend parallel, ist ein möglicher

05:45.740 --> 05:49.100
Ansatz, aber hat halt hohen Aufwand, weil ich eben viele solche

05:49.100 --> 05:51.900
Probleme bearbeiten muss und bei denen mache ich eigentlich einigen

05:51.900 --> 05:53.760
Aufwand, überflüssigerweise.

05:54.120 --> 05:57.380
Und dass es überflüssig ist, sieht man also bei dem Gram-Scan, bei dem

05:57.380 --> 06:01.620
ich Ihnen dann gezeigt habe, wie man einfach durch Anordnung der

06:01.620 --> 06:12.340
Punkte in einer Reihenfolge dafür sorgt, dass man im Prinzip außenrum

06:12.340 --> 06:15.960
läuft und immer so drei aufeinanderfolgende Punkte anguckt und

06:15.960 --> 06:19.020
feststellt, habe ich hier einen konvexen Winkel oder einen konkarven

06:19.020 --> 06:19.280
Winkel.

06:19.400 --> 06:25.000
Sobald ich einen konkarven Innenwinkel habe, ist es halt kein

06:25.000 --> 06:29.700
Extrempunkt, der Punkt in der Mitte, das war der Fall in dieser

06:29.700 --> 06:34.740
Situation hier unten, da war der Punkt 2 halt ein Eckpunkt eines

06:34.740 --> 06:39.240
konkarven Winkels, während hier, da ist der Punkt 2 der Eckpunkt eines

06:39.240 --> 06:42.820
konvexen Winkels, also eine Linksdrehung, im Konkarven Fall eine

06:42.820 --> 06:45.860
Rechtsdrehung, wenn wir eben von rechts nach links rumlaufen, gegen

06:45.860 --> 06:49.840
den Uhrzeiger sind und auf diese Art und Weise konnte man zunächst mal

06:49.840 --> 06:54.280
von einem sicheren Extrempunkt starten und dann bekam man eine Folge

06:54.280 --> 06:58.120
von potenziellen Extrempunkten, die man immer wieder dann halt

06:58.120 --> 06:58.800
angeguckt hat.

06:59.340 --> 07:01.720
Ich habe Ihnen, das will ich nochmal kurz jetzt hier aufmalen, ich

07:01.720 --> 07:05.740
gehe mal hier auf den Präsentationsmodus, ich hatte Ihnen ja gezeigt,

07:05.860 --> 07:17.840
wie wir das machen und der Ansatz war so gewesen, dass wir hier die

07:17.840 --> 07:20.400
Menge der Punkte hatten und ich hatte gesagt, okay, wir nehmen hier

07:20.400 --> 07:25.820
irgendeinen Punkt in der Mitte zum Beispiel und ordnen jetzt alle

07:25.820 --> 07:31.080
anderen Punkte darum herum an und haben dann so eine radiale Anordnung

07:31.080 --> 07:32.060
aller Punkte der Menge.

07:32.640 --> 07:33.540
Das kann man so machen.

07:34.000 --> 07:35.060
Es geht aber auch anders.

07:35.860 --> 07:37.980
Also ich kann natürlich auch, wenn ich hier irgendeine Punktmenge

07:37.980 --> 07:43.220
habe, kann ich auch einfach sagen, ich betrachte zunächst mal den

07:43.220 --> 07:47.620
linkesten Punkt, das ist dieser hier, und den rechtesten Punkt, das

07:47.620 --> 07:49.360
ist dieser hier, nur in Bezug auf die x-Koordinaten.

07:49.360 --> 07:54.480
Und ich weiß, der linkeste und der rechteste Punkt sind garantiert

07:54.480 --> 07:55.360
Extrempunkte.

07:56.600 --> 07:58.280
Ich brauche nur die x-Koordinaten anzugucken.

07:58.860 --> 08:02.540
Und jetzt kann ich das, was ich gerade eben gemacht habe, mit dieser

08:02.540 --> 08:06.520
radialen Wanderung außen herum, genauso machen, indem ich entweder

08:06.520 --> 08:12.540
hier anfange und diese Winkel hier jeweils angucke und so weiter.

08:13.120 --> 08:17.740
Ich laufe praktisch so einfach von oben herum bis zu diesem Punkt hier

08:17.740 --> 08:18.020
drüben.

08:18.080 --> 08:20.380
Oder ich kann das entweder in der Richtung machen oder in der

08:20.380 --> 08:21.380
Richtung, das ist völlig egal.

08:23.480 --> 08:27.560
Und ich laufe praktisch außen herum, aber ich gucke praktisch immer

08:27.560 --> 08:28.460
von oben drauf.

08:29.140 --> 08:31.300
Und ich habe dabei den gleichen Effekt wie vorher auch.

08:31.400 --> 08:33.480
Das heißt, ich muss nicht unbedingt diese radiale Anordnung machen,

08:33.580 --> 08:36.160
ich kann genauso gut sagen, ich mache das zunächst mal für die obere

08:36.160 --> 08:40.520
konvexe Hülle und dann kann ich das Gleiche nochmal machen für die

08:40.520 --> 08:40.840
untere.

08:42.540 --> 08:44.180
Auch entweder von links oder von rechts.

08:44.920 --> 08:47.660
Dann habe ich die obere und die untere Hülle und ich bin fertig.

08:48.760 --> 08:51.840
Das heißt, der Aufwand ist ja für das Sortieren der x-Koordinaten ein

08:51.840 --> 08:55.080
bisschen einfacher als der Aufwand, um diese radiale Anordnung zu

08:55.080 --> 08:57.040
machen, weil ich da immer feststellen muss, nicht ein Punkt links oder

08:57.040 --> 08:58.580
rechts von einer geraden.

08:59.980 --> 09:02.260
Vom konstanten Aufwand, den ich von hier was machen muss, um diese

09:02.260 --> 09:04.100
Frage zu entscheiden, ist da der Aufwand höher.

09:04.560 --> 09:07.760
Deswegen ist eigentlich diese Variante, wo ich einfach von links nach

09:07.760 --> 09:10.320
rechts laufe, etwas einfacher.

09:11.380 --> 09:14.640
Nur als kleine Bemerkung dazu.

09:14.780 --> 09:20.300
Ansonsten haben wir hier den Graham-Scan soweit behandelt und dann ist

09:20.300 --> 09:21.960
das die erste neue Folie für heute.

09:22.720 --> 09:27.580
Die Eigenschaft, die wir eben hier ausnutzen in dem Graham-Scan ist,

09:28.300 --> 09:31.940
dass alle inneren Winkel zwischen aufeinanderfolgenden Kanten eines

09:31.940 --> 09:33.720
konvexen Polygons konvex sind.

09:34.420 --> 09:42.900
Wissen Sie, das alleine reicht nicht aus, um tatsächlich diese

09:42.900 --> 09:44.860
Probleme zu lösen, also da muss man aufpassen.

09:45.300 --> 09:51.000
Aber auf jeden Fall, wenn also die inneren Winkel alle konvex sind

09:51.000 --> 09:54.280
oder bei einem konvexen Polygon sind sie alle konvex, das ist völlig

09:54.280 --> 09:54.700
klar.

09:55.320 --> 09:59.460
So ein Polygon, bei dem sind halt die inneren Winkel hier alles

09:59.460 --> 10:01.100
konvexe Winkel.

10:02.500 --> 10:08.580
Ein anderer Ansatz ist, dass wir nicht nach Extrempunkten suchen,

10:08.780 --> 10:11.620
sondern nach Kanten der konvexen Hülle.

10:12.940 --> 10:13.720
Was ist der Unterschied?

10:13.980 --> 10:16.760
Wenn wir nach Extrempunkten suchen, suchen wir hier nach diesen

10:16.760 --> 10:17.200
Punkten.

10:17.300 --> 10:21.640
Wir haben geguckt, ein Punkt hier drin, das wäre also einer, der ist

10:21.640 --> 10:23.380
nicht Extrempunkt, deswegen haben wir den verworfen.

10:24.240 --> 10:25.720
Wir mussten aber alle Punkte angucken.

10:27.260 --> 10:30.560
Jetzt ist die Frage, kann man das etwas anders machen, wenn man sagt,

10:30.600 --> 10:33.800
ich gehe nicht nach den Punkten, Extrempunkten und ich suche die

10:33.800 --> 10:34.120
Kanten.

10:34.920 --> 10:39.620
Die Kanten sind ja hier, die Kante, die Kante, die Kante, die Kante,

10:40.120 --> 10:40.620
die Kante.

10:40.960 --> 10:41.680
Was ist der Unterschied?

10:42.060 --> 10:42.800
Gar nicht so groß.

10:42.860 --> 10:45.700
Die Extrempunkte liegen außen, die Kanten liegen auch außen.

10:46.960 --> 10:55.480
Aber trotzdem, was ich feststelle ist, wenn ich eine solche Kante der

10:55.480 --> 11:02.840
konvexen Hülle habe, hier, dann weiß ich doch, dass alle Punkte meiner

11:02.840 --> 11:07.920
Menge auf der gleichen Seite dieser Geraden durch diese Kante liegen.

11:08.960 --> 11:12.020
Beziehungsweise sie liegen auf dieser Geraden, die beiden Eckpunkte

11:12.020 --> 11:12.900
der Kante.

11:14.440 --> 11:18.080
Das heißt, das ist eine Eigenschaft, die man sich auch angucken muss.

11:19.500 --> 11:22.520
Das ist die Eigenschaft, die eine Kante der konvexen Hülle

11:22.520 --> 11:23.160
auszeichnet.

11:23.320 --> 11:26.720
Alle Punkte der Menge liegen auf der gleichen Seite dieser Kante.

11:28.320 --> 11:29.680
Zwei Punkte liegen genau drauf.

11:31.340 --> 11:36.300
Und das ist die Eigenschaft, die bei dem Ansatz von Jarvis genutzt

11:36.300 --> 11:36.600
wird.

11:37.320 --> 11:41.660
Jarvis -March, das ist der Gram-Scan, das ist der Jarvis-March.

11:41.660 --> 11:43.340
Das müssen aber schöne Namen haben.

11:44.300 --> 11:47.340
Also der Herr Jarvis hat sich das Folgende ausgedacht.

11:48.520 --> 11:52.260
Er wählt den zum Beispiel linkesten unteren Punkt von M als

11:52.260 --> 11:52.820
Startpunkt.

11:54.740 --> 11:58.840
Linkesten unteren Punkt, also ich könnte den Punkt hier nehmen, könnte

11:58.840 --> 11:59.500
auch mit dem anfangen.

11:59.600 --> 12:01.400
Hier, wenn die beiden gleich sind, ist es so.

12:01.680 --> 12:04.140
Nehmen wir mal an, der hier ist ein bisschen tiefer, fangen wir mit

12:04.140 --> 12:04.660
dem hier an.

12:05.740 --> 12:10.640
Und dann weiß ich, das ist ein sicherer Extrempunkt, bzw.

12:10.760 --> 12:13.820
der Anfangspunkt einer Kante der konvexen Hülle.

12:14.060 --> 12:15.720
Ich suche jetzt mal die Kanten der konvexen Hülle.

12:17.360 --> 12:21.840
Und ich weiß, alle Punkte meiner Menge müssen links davon liegen.

12:23.440 --> 12:27.720
Also suche ich einfach jetzt zu diesem aktuellen Punkt, das ist dieser

12:27.720 --> 12:35.680
hier, einen anderen Punkt, irgendeinen Punkt M, den suche ich

12:35.680 --> 12:41.620
natürlich hier, sodass der Winkel mit der x-Achse minimal ist.

12:44.560 --> 12:46.800
Also ich gebe mir alle möglichen Punkte, viele verschiedene Punkte

12:46.800 --> 12:47.360
sind hier drin.

12:48.340 --> 12:52.440
Und ich habe also sehr viele verschiedene solche Winkel zu betrachten.

12:52.440 --> 12:58.560
Und ich suche mir den Punkt raus, bei dem ich den minimalen Winkel mit

12:58.560 --> 12:59.400
der x-Achse habe.

12:59.880 --> 13:05.840
Beziehungsweise den Punkt, bei dem alle anderen auf der gleichen Seite

13:05.840 --> 13:08.800
liegen, nämlich links von dieser Kante.

13:09.240 --> 13:13.960
Ich laufe wieder in dieser Richtung hier rum, fange mit dieser Kante,

13:14.100 --> 13:17.900
die Kante suche ich als erstes, suche also die Kante, sodass alle

13:17.900 --> 13:19.640
Punkte links davon liegen.

13:20.740 --> 13:28.200
Und dann bin ich anschließend bei diesem Punkt und ich suche wieder

13:28.200 --> 13:34.400
den Punkt meiner Menge, der einen minimalen Winkel mit der x-Achse

13:34.400 --> 13:34.660
hat.

13:35.860 --> 13:38.280
Das ist in dem Fall der Punkt, da habe ich dieses hier als nächste

13:38.280 --> 13:38.600
Kante.

13:39.360 --> 13:45.200
Und ich suche wieder den Punkt, also hier alle Kanten betrachte ich,

13:45.200 --> 13:46.740
alles potenzielle Kanten.

13:48.640 --> 13:53.120
Und ich finde den Punkt hier, der den minimalen Winkel mit der x-Achse

13:53.120 --> 13:53.340
hat.

13:54.680 --> 13:56.640
Und dann bin ich dort und so weiter.

13:57.280 --> 14:00.180
Der Winkel wird zwar ziemlich groß dann hier, trotzdem ist das der

14:00.180 --> 14:00.960
minimale Winkel.

14:03.840 --> 14:06.880
Beziehungsweise alle Punkte liegen auf der gleichen Seite.

14:08.540 --> 14:09.740
Das ist also die gleiche Eigenschaft.

14:11.340 --> 14:12.820
So, wie groß ist der Aufwand dafür?

14:12.820 --> 14:21.140
Wenn ich also feststellen will, welcher Punkt der richtige ist für

14:21.140 --> 14:24.800
diese Kante, für den Endpunkt der Kante, dann suche ich eigentlich nur

14:24.800 --> 14:25.380
ein Minimum.

14:26.060 --> 14:29.840
Wie man ein Minimum bestimmt, wissen wir, das sind bei N Elementen N-1

14:29.840 --> 14:30.820
Vergleiche.

14:31.640 --> 14:37.080
Und ich habe also der Reihe nach Minimumsprobleme zu lösen.

14:38.120 --> 14:44.700
Ich habe für jeden Extrempunkt, beziehungsweise für jede Kante,

14:46.940 --> 14:50.680
beziehungsweise für jede Kante, O von N Vergleiche.

14:51.460 --> 14:53.920
Ich kann natürlich sagen, für jeden Extrempunkt, weil ich an jedem

14:53.920 --> 14:58.320
Extrempunkt suche, was ist der nächste Punkt in dem Polygon, das ich

14:58.320 --> 14:59.100
da bestimmen will.

15:00.560 --> 15:03.460
Ich habe also ein Minimum zu bestimmen.

15:03.460 --> 15:05.240
Ich muss mit allen Punkten vergleichen.

15:06.220 --> 15:08.680
Nicht wirklich allen, aber mit sehr vielen.

15:08.800 --> 15:11.460
Einige sind natürlich schon weg, von denen ich weiß, die liegen schon

15:11.460 --> 15:12.800
auf der convexen Hülle.

15:14.180 --> 15:16.780
Und jetzt habe ich also für jeden Extrempunkt diesen Aufwand zu

15:16.780 --> 15:18.020
treffen oder zu machen.

15:18.180 --> 15:22.500
Wenn ich den gefunden habe, oder wenn ich das Minimum gefunden habe,

15:22.980 --> 15:25.040
dann bin ich bei dem nächsten Extrempunkt.

15:25.960 --> 15:27.700
Ich muss wieder eine Minimumsaufgabe machen.

15:28.360 --> 15:29.840
Ich bin beim nächsten Extrempunkt.

15:30.560 --> 15:34.800
Ich habe nicht, wie bei dem Gram-Scan, das Problem, dass ich

15:34.800 --> 15:38.760
nacheinander so ein Stack von Punkten aufbaue, bei denen ich weiß, das

15:38.760 --> 15:43.180
sind potenzielle Extrempunkte, die vielleicht irgendwann später sich

15:43.180 --> 15:45.520
als Nicht-Extrempunkte erweisen.

15:46.440 --> 15:50.600
In diesem Fall ist jeder Punkt, den ich hier tatsächlich feststelle,

15:50.760 --> 15:51.660
ein Extrempunkt.

15:52.500 --> 15:55.340
Weil alle Punkte links von dieser Kante liegen.

15:56.440 --> 16:00.320
Und das heißt, ich muss für jeden Extrempunkt einen linearen Aufwand

16:00.320 --> 16:00.780
betreiben.

16:02.140 --> 16:09.240
Und damit habe ich, wenn ich H-Extrempunkte habe, einen Aufwand in O

16:09.240 --> 16:10.940
von H mal N.

16:11.480 --> 16:13.060
H, die Anzahl der Extrempunkte.

16:13.560 --> 16:14.260
Steht das hier irgendwo?

16:15.580 --> 16:16.660
Sollte eigentlich irgendwo stehen.

16:17.360 --> 16:18.880
Hier sehe ich das jetzt nicht.

16:21.910 --> 16:27.110
H gleich Anzahl Extrempunkte.

16:31.210 --> 16:39.450
Also, das ist in diesem Fall ein Aufwand, der ist nicht N log N, wie

16:39.450 --> 16:40.550
bei Gram-Scan.

16:41.050 --> 16:44.930
Im schlechtesten Fall, wenn wir N Extrempunkte haben, also

16:44.930 --> 16:48.450
Größenordnung N Extrempunkte haben, haben wir quadratischen Aufwand.

16:49.310 --> 16:55.750
Wenn wir aber eine konstante Zahl von Extrempunkten haben, dann ist es

16:55.750 --> 16:57.030
ein linearer Aufwand.

16:58.050 --> 17:00.430
Deswegen ist das eine sehr interessante Geschichte.

17:01.270 --> 17:04.750
Wenn Mengen so aussehen, wie hier immer so angedeutet, dass ich da

17:04.750 --> 17:07.730
irgendeine Wolke habe und ich will eigentlich nur die paar Punkte

17:07.730 --> 17:12.130
außenrum haben, dann habe ich relativ wenige Extrempunkte.

17:12.130 --> 17:15.570
Es kann sein, dass es tatsächlich nur ein Bruchteil oder sogar eine

17:15.570 --> 17:18.090
konstante Zahl von Extrempunkten ist.

17:18.410 --> 17:20.750
Und in dem Fall habe ich dann eben wirklich ein sehr schnelles

17:20.750 --> 17:21.130
Verfahren.

17:23.510 --> 17:27.930
Also es ist einfach, ich habe eine andere Eigenschaft genommen, die

17:27.930 --> 17:29.710
meinen Algorithmus beeinflusst.

17:30.830 --> 17:32.470
Das ist das, was ich versuche rüberzubringen.

17:32.570 --> 17:36.990
Ich stelle Ihnen diese verschiedenen Ansätze vor, jeweils mit einer

17:36.990 --> 17:40.310
Erkenntnis als Kern des Algorithmus, als Startpunkt für den

17:40.310 --> 17:42.570
Algorithmus und dann schaut man, wie man diese Erkenntnis, diese

17:42.570 --> 17:46.090
Eigenschaft sinnvoll ausnutzen kann, um das Problem zu lösen.

17:46.270 --> 17:48.930
Und es gibt halt unterschiedliche Eigenschaften, entsprechend kriegen

17:48.930 --> 17:49.930
wir unterschiedliche Algorithmen.

17:52.810 --> 17:56.910
Ein anderer Ansatz, den Sie alle kennen, haben wir uns schon mehrfach

17:56.910 --> 18:00.690
angeguckt, ist der übliche Algorithmenentwurfsansatz, die beiden

18:00.690 --> 18:01.030
kommen.

18:02.010 --> 18:05.810
Der übliche Ansatz ist, das Problem ist uns viel zu schwer, wir teilen

18:05.810 --> 18:08.650
es auf in zwei Teilprobleme.

18:09.750 --> 18:15.350
Also wir teilen M in zwei gleich große Teilmengen, es sei denn, die

18:15.350 --> 18:19.750
Anzahl der Punkte war klein, dann machen wir das irgendwie mit wenig

18:19.750 --> 18:20.210
Aufwand.

18:21.070 --> 18:25.670
Wenn die Anzahl der Punkte groß ist, größer als irgendein K, das man

18:25.670 --> 18:28.970
irgendwie festlegen kann, das ist jetzt nicht so relevant, teilen wir

18:28.970 --> 18:32.830
das in zwei gleich große Teilmengen auf und bestimmen jetzt rekursiv

18:32.830 --> 18:35.810
die beiden konvexen Hüllen für M1.

18:36.490 --> 18:39.570
Das ist hier also zum Beispiel jetzt, wenn das hier M1 ist, wäre das

18:39.570 --> 18:43.450
hier eine solche Hülle, M1, das hier M2.

18:45.170 --> 18:51.710
Jetzt habe ich zwei konvexe Hüllen, habe also diese beiden Ränder, und

18:51.710 --> 18:55.690
jetzt muss ich sehen, dass sich die beiden verschmelzen zu einer

18:55.690 --> 18:56.310
konvexen Hülle.

18:58.630 --> 19:00.230
Wie macht man das?

19:00.430 --> 19:04.090
Also wir wissen, aufteilen ist eine, lösen und zusammensetzen.

19:06.950 --> 19:10.070
Wie ist der Aufwand, um zwei konvexe Hüllen zu verschmelzen?

19:11.610 --> 19:12.770
Ist gar nicht so schwer.

19:14.310 --> 19:17.870
Ich habe bei jeder konvexen Hülle, nehmen wir mal an, ich fange hier

19:17.870 --> 19:25.310
an, 1, 2, 3, 4, 5, 6 in dem Fall, und hier auch A, B,

19:34.670 --> 19:36.770
C, D, E.

19:38.110 --> 19:40.770
Das sind unsere Reihenfolgen der Polygonen.

19:40.890 --> 19:42.530
Das heißt, ich habe Reihenfolgen dieser Punkte,

19:45.650 --> 19:49.570
und jetzt mache ich folgendes, ich trenne das Ganze einfach mal durch,

19:49.570 --> 19:54.390
ich betrachte die obere konvexe Hülle und die untere.

19:56.630 --> 20:00.890
Wenn ich mir die obere anschaue, dann habe ich hier eine geordnete

20:00.890 --> 20:07.730
Folge 1, 2, 3, das waren diese drei Punkte, und eine geordnete Folge

20:07.730 --> 20:12.490
A, B, C, geordnet in Bezug auf die X-Koordinaten.

20:14.550 --> 20:17.350
Jetzt kommt das, was ich vorhin ganz kurz schon mal angedeutet habe,

20:17.350 --> 20:18.450
bei dem Graham-Scan.

20:19.030 --> 20:22.010
Im Prinzip wenden wir jetzt den Graham-Scan an, gehen meinetwegen

20:22.010 --> 20:25.290
jetzt mal von links nach rechts, und gehen hier einfach oben durch,

20:25.410 --> 20:27.830
auf der verschmolzenen Folge.

20:28.390 --> 20:33.610
Wir verschmelzen einfach die beiden konvexen Hüllen in Bezug auf die X

20:33.610 --> 20:38.510
-Koordinaten, da, da, da, da, da und da, das sind unsere X

20:38.510 --> 20:43.930
-Koordinaten, sortieren die einfach um, also verschmelzen die, und

20:43.930 --> 20:46.230
dann gehen wir hier der Reihe nach durch, mit dem Graham-Scan.

20:46.990 --> 20:49.150
Diesen Weg von 1 nach 2 kein Problem.

20:49.870 --> 20:53.430
Also das ist der Punkt hier, das garantiert einen Punkt der konvexen

20:53.430 --> 20:55.390
Hülle, der Vereinigung der beiden konvexen Hüllen.

20:56.510 --> 21:01.230
Der nächste, 2 in dem Fall auch, dann müssen wir hier hinlaufen, dann

21:01.230 --> 21:04.750
denken wir, dass 2 auch noch einer ist, und dann gehen wir weiter,

21:06.190 --> 21:10.730
dieser Punkt A, kommen anschließend zu diesem hier, und stellen fest,

21:10.790 --> 21:15.270
aha, das ist schon mal keiner, der Punkt A fällt raus, dann denken

21:15.270 --> 21:19.990
wir, Punkt 3 könnte einer sein, wir gehen zu B, stellen fest, Punkt 3

21:19.990 --> 21:24.630
fällt auch raus, wir haben also dies hier als neue Kante, und laufen

21:24.630 --> 21:26.010
anschließend noch hier rüber, sind fertig.

21:26.810 --> 21:31.350
Einfach der Graham-Scan auf den verschmolzenen, oberen konvexen

21:31.350 --> 21:31.550
Hüllen.

21:33.150 --> 21:36.190
Das geht in lineare Zeit, Verschmelzen von zwei Folgen der

21:36.190 --> 21:40.070
Größenordnung, Länge Größenordnung n, geht in lineare Zeit, Graham

21:40.070 --> 21:43.290
-Scan ist auch in lineare Zeit, sind wir in lineare Zeit fertig, das

21:43.290 --> 21:48.030
heißt, wir haben linearen Aufwand, um die beiden Lösungen, die beiden

21:48.030 --> 21:51.550
konvexen Hüllen zu verschmelzen, einmal für die obere Hülle, einmal

21:51.550 --> 21:54.290
für die untere Hülle, also die Konstante ist schon ein bisschen größer

21:54.290 --> 21:59.550
hier, und dann müssen wir natürlich rekursiv zwei Probleme der halben

21:59.550 --> 22:04.070
Größe lösen, und wir wissen, was da rauskommt, das ist die klassische

22:04.070 --> 22:05.370
Rekursionsformel für N-Logging.

22:07.150 --> 22:11.910
Wir haben also noch ein weiteres Verfahren, wie wir konvexe Hülle mit

22:11.910 --> 22:13.390
Aufwand N-Log N lösen können.

22:13.950 --> 22:21.270
Nun haben wir hier im Prinzip auch den Graham-Scan angewandt, für das

22:21.270 --> 22:25.310
Verschmelzen der oberen konvexen Hüllen, den Graham-Scan hätten wir

22:25.310 --> 22:28.650
auch direkt anwenden können, durch einfach einmal Sortieren der ganzen

22:28.650 --> 22:32.910
X -Koordinaten und dann oben einmal rüberlaufen, das heißt, der Divide

22:32.910 --> 22:36.610
-and -Conquer-Ansatz bringt in diesem Fall nicht wirklich etwas.

22:37.330 --> 22:41.850
Ich kann es allerdings etwas verbessern, kann hier sogar auf N-Log H

22:41.850 --> 22:45.550
gehen, aber das ist jetzt eine Kleinigkeit.

22:46.670 --> 22:50.230
Aber im Prinzip heißt das, es geht auch mit Divide-and-Conquer, das

22:50.230 --> 22:53.210
ist ein typischer Ansatz dafür, auch ein sinnvoller, dann kann man das

22:53.210 --> 22:58.070
natürlich auch, also hier kann man es auch parallelisieren, ja, mit

22:58.070 --> 23:02.690
Divide -and-Conquer-Ansatz kann ich immer parallelisieren, und dieses,

23:03.330 --> 23:07.310
dann muss ich halt den Graham-Scan entsprechend durchführen, das ist

23:07.310 --> 23:09.190
wiederum etwas Sequenzielles.

23:10.430 --> 23:14.390
Da könnte ich natürlich für jeweils Punkte gucken, ob ich da jeweils

23:14.390 --> 23:19.050
drei benachbarte Punkte, ob das ein konvexer oder konkaber Winkel ist,

23:20.830 --> 23:26.070
hilft mir aber nicht hundertprozentig etwas, und man kann hier noch

23:26.070 --> 23:28.010
ein bisschen was parallelisieren, habe ich hier aber auch nicht

23:28.010 --> 23:28.450
vertieft.

23:29.390 --> 23:31.610
Es ging mir im Wesentlichen darum, Ihnen verschiedene Ansätze zu

23:31.610 --> 23:34.890
zeigen für die konvexe Hülle, zunächst mal im sequenziellen Fall.

23:36.250 --> 23:38.430
Hier steht es nochmal, wie man das macht, die Vereinigung der beiden

23:38.430 --> 23:41.110
konvexen Hüllen, das ist aber das, was ich Ihnen gerade eben erläutert

23:41.110 --> 23:44.350
habe, steht hier nochmal beschrieben, dass ich halt die oberen Ränder

23:44.350 --> 23:47.230
bestimme, die beiden verschmelzen bezüglich ihrer X-Koordinaten und

23:47.230 --> 23:50.630
dann darauf ein Graham-Scan mache und habe dann den linearen Aufwand

23:50.630 --> 23:50.870
dafür.

23:51.050 --> 23:52.030
Das ist also nicht weiter schlimm.

23:53.030 --> 23:55.570
Es kommt noch ein Algorithmus mit einem neuen Prinzip, ich muss Ihnen

23:55.570 --> 23:59.550
nochmal jedesmal ein neues schönes Prinzip präsentieren, das Wegwerf

23:59.550 --> 23:59.930
-Prinzip.

24:00.470 --> 24:01.710
Was ist das für ein Prinzip?

24:02.050 --> 24:05.750
Im Prinzip ist das etwas, was wir unheimlich gerne machen als

24:05.750 --> 24:06.390
Informatiker.

24:07.530 --> 24:10.810
Bei zum Beispiel Branch and Bound könnte man auch sagen, das ist ein

24:10.810 --> 24:11.510
Wegwerf -Prinzip.

24:12.030 --> 24:15.050
Weil bei Branch and Bound versuche ich, möglichst frühzeitig

24:15.050 --> 24:18.230
festzustellen, welchen Teil des Suchraums ich wegwerfen kann.

24:19.310 --> 24:23.030
Indem ich irgendwelche Lösungen finde und feststelle, aha, ich bin in

24:23.030 --> 24:26.090
einem Teilbereich, wo ich sicher bin, ich brauche nicht

24:26.090 --> 24:29.210
weiterzumachen, weil das, was ich dort noch machen könnte, ist

24:29.210 --> 24:30.510
schlechter, als das, was ich schon weiß.

24:30.810 --> 24:32.370
Und dann werfe ich einen ganz großen Bereich weg.

24:34.070 --> 24:37.150
Und das ist eigentlich immer unser Ziel, ein Problem möglichst klein

24:37.150 --> 24:41.690
zu machen, indem ich Informationen ausnutze und alles andere, was ich

24:41.690 --> 24:46.810
dann dadurch als irrelevant erkennen kann, werfe ich halt schon mal

24:46.810 --> 24:46.970
weg.

24:48.110 --> 24:52.790
Und hier ist der Ansatz wiederum ganz anders, als das, was man sich

24:52.790 --> 24:54.250
sonst immer überlegt.

24:55.030 --> 24:59.410
Ich hatte vorhin schon mal gesagt, wir wissen, bei den Extrempunkten

24:59.410 --> 25:04.810
einer konvexen Hülle ist die Anzahl der Extrempunkte häufig relativ

25:04.810 --> 25:05.270
klein.

25:05.850 --> 25:07.570
Im Vergleich zur Anzahl aller Punkte.

25:08.550 --> 25:11.110
Wenn wir so annehmen, wir haben zum Beispiel alle Punkte irgendwie

25:11.110 --> 25:15.010
gleichmäßig verteilt, gleichwahrscheinlich in irgendeinem Bereich

25:15.010 --> 25:21.710
verteilt, und jetzt wollen wir die Extrempunkte bestimmen, die konvexe

25:21.710 --> 25:21.950
Hülle.

25:22.650 --> 25:25.090
Dann machen wir zunächst mal eine Approximation.

25:26.550 --> 25:29.430
Wir sagen, naja, ich kann ja zunächst mal in einigen Richtungen

25:30.370 --> 25:31.150
Extrempunkte suchen.

25:32.490 --> 25:36.250
Ich gehe also, gucke mir das einmal nach unten an und finde diesen

25:36.250 --> 25:36.570
Punkt.

25:37.390 --> 25:40.630
Gucke mir den Extrempunkt in nördlicher Richtung an und finde den

25:40.630 --> 25:40.930
Punkt.

25:42.050 --> 25:44.730
Suche den in östlicher Richtung und finde diesen Punkt.

25:46.250 --> 25:48.290
Suche den in westlicher Richtung und finde den Punkt.

25:49.510 --> 25:51.290
Das könnte ich damit schon aufhören.

25:51.430 --> 25:52.510
Ich mache es doch ein bisschen weiter.

25:53.430 --> 25:58.950
Okay, ich gehe jetzt auch noch zum Nordosten, ich finde den, gehe zum

25:58.950 --> 26:04.290
Südosten, zum Südwesten, zum Nordwesten.

26:04.830 --> 26:08.350
Habe jetzt acht Richtungen jeweils Extrempunkte gefunden.

26:09.650 --> 26:10.930
Ich könnte es noch mehr verteilen.

26:11.210 --> 26:12.690
Das kann ich übrigens alles parallel machen.

26:13.850 --> 26:14.990
Das ist eine völlig unabhängige Operation.

26:17.930 --> 26:23.670
Und der Aufwand, um diese Extrempunkte zu finden, der ist nicht sehr

26:23.670 --> 26:23.910
groß.

26:24.050 --> 26:25.090
Das ist jeweils lineare Aufwand.

26:26.570 --> 26:29.750
Weil ich ja nur ein Maximum bestimmen muss in Bezug auf eine bestimmte

26:29.750 --> 26:30.630
Koordinatenrichtung.

26:31.950 --> 26:33.250
Das ist alles kein Problem.

26:33.350 --> 26:34.490
Das kann ich in linearer Zeit machen.

26:34.590 --> 26:36.310
Linear ist immer sehr schön.

26:37.490 --> 26:41.770
Und jetzt kann ich mit linearem Aufwand Folgendes machen.

26:41.850 --> 26:46.910
Ich kann alle Punkte, die im Inneren liegen, dieses Polygons, das

26:46.910 --> 26:53.330
aufgespannt wird von diesen acht Extrempunkten, alle Punkte, die hier

26:53.330 --> 26:55.010
im Inneren liegen, die kann ich alle rausstreichen.

26:56.230 --> 26:58.330
Die kann ich mit linearem Aufwand bestimmen.

26:58.830 --> 27:01.410
Das ist eine konstante Anzahl von Kanten.

27:02.830 --> 27:05.610
Ich kann alle Punkte, die im Inneren liegen, rauswerfen.

27:07.310 --> 27:10.610
Ich weiß ja, bei das...

27:10.610 --> 27:13.870
Gut, ich muss im Prinzip alle, die jeweils rechts, wenn ich hier in

27:13.870 --> 27:16.410
der Reihe nach so damit anfange, dann die nehmen, dann die nehmen und

27:16.410 --> 27:16.650
so weiter.

27:17.030 --> 27:18.910
Im Prinzip alle, die rechts davon liegen, werfe ich raus.

27:19.450 --> 27:21.190
Und da gibt es einige, die bleiben übrig.

27:21.330 --> 27:21.990
Hier zum Beispiel.

27:22.510 --> 27:23.650
Da haben wir einige, die bleiben übrig.

27:23.850 --> 27:24.690
Da bleibt einer übrig.

27:24.830 --> 27:25.790
Da bleiben welche übrig.

27:26.190 --> 27:27.230
Vielleicht noch irgendwo anders.

27:29.150 --> 27:32.990
Einige liegen halt nicht auf der gleichen Seite dieser Kante wie alle

27:32.990 --> 27:33.290
anderen.

27:35.110 --> 27:39.010
Das sind ja noch nicht notwendigerweise die Extremkanten oder die

27:39.010 --> 27:39.870
Kanten der konvexen Hülle.

27:41.050 --> 27:43.170
Und jetzt mache ich einfach Folgendes.

27:44.010 --> 27:46.770
Ich schaue mir die Restmenge an.

27:48.390 --> 27:49.810
Da bleiben einige Punkte übrig.

27:49.970 --> 27:51.230
Also alles, was hier drin ist, ist weg.

27:52.150 --> 27:54.050
Es bleibt nur das übrig, was hier außen liegt.

27:54.450 --> 27:55.570
Was hier eingekringelt ist.

27:56.050 --> 27:57.530
Der Bereich, der Bereich, der Bereich.

27:57.850 --> 28:00.150
Vielleicht liegt da auch noch irgendwas da, da und da.

28:00.770 --> 28:02.290
Aber das ist ein relativ schmaler Bereich.

28:04.090 --> 28:08.290
Und ich muss nur für die Punkte, die übrig bleiben, jetzt die konvexe

28:08.290 --> 28:08.770
Hülle bestimmen.

28:11.550 --> 28:11.690
Ja.

28:13.090 --> 28:14.430
Und das ist ja nicht weiterspielen.

28:14.490 --> 28:15.230
Wir wissen, wie das geht.

28:15.650 --> 28:21.010
Die restlichen Punkte seien R und dafür mache ich zum Beispiel ein

28:21.010 --> 28:21.470
Gram -Scan.

28:22.910 --> 28:23.790
R log R.

28:24.050 --> 28:24.590
Ganz einfach.

28:25.970 --> 28:27.590
Also wenn ich einfach ein normales Verfahren mache.

28:28.830 --> 28:31.710
Wenn ich Glück habe, sind das konstant viele.

28:32.710 --> 28:34.570
Dann bin ich schon fertig mit linearem Aufwand.

28:34.570 --> 28:36.350
Nur ganz wenige Punkte.

28:36.630 --> 28:45.130
Wenn ich Pech habe, sah meine Punktmenge irgendwie so aus.

28:46.410 --> 28:46.690
Ja.

28:47.330 --> 28:48.490
Dann hat mir das nichts gebracht.

28:49.810 --> 28:54.070
Dann sind die, ist im Innern fast nichts und dann liegen die meisten,

28:54.110 --> 28:58.390
liegen viele Punkte außerhalb dieser approximativen, konvexen Hülle.

28:59.390 --> 29:00.530
Aber das ist ein Extremfall.

29:01.390 --> 29:02.950
So wird das normalerweise nicht aussehen.

29:03.590 --> 29:07.990
Und das heißt, ich habe hier in dem schlechtesten Fall natürlich immer

29:07.990 --> 29:11.710
noch den Aufwand N log N, wenn viele Punkte außerhalb dieser

29:11.710 --> 29:13.330
approximativen, konvexen Hülle liegen.

29:14.130 --> 29:19.950
Aber wenn ich davon ausgehe, dass ich gleichverteilte Punkte habe in

29:19.950 --> 29:24.850
einem gewissen Bereich, dann habe ich insgesamt einen Aufwand von O

29:24.850 --> 29:25.170
von N.

29:26.650 --> 29:27.470
Linearen Aufwand.

29:27.550 --> 29:28.770
Dann ist das hier das beste Verfahren.

29:29.030 --> 29:31.250
Aber hängt eben davon ab, wie die Punkte verteilt sind.

29:31.870 --> 29:34.710
Das heißt, was man hier im Prinzip macht, wir haben diesen Wegwerf

29:34.710 --> 29:39.450
-Prinzip, ich mache jetzt mal eine approximative Lösung und dann

29:40.110 --> 29:43.510
entscheide ich aufgrund dieser Lösung, was muss ich noch als

29:43.510 --> 29:49.910
Restaufgabe bearbeiten und der Aufwand ist dann im Schnitt sehr klein.

29:50.550 --> 29:52.850
Das heißt, der erwartete Aufwand ist im Fall linear.

29:54.330 --> 29:57.310
Also das ist das letzte Verfahren zur konvexen Hülle, was ich Ihnen

29:57.310 --> 29:58.090
präsentieren wollte.

29:58.090 --> 30:04.470
Auch dies kann man sehr schön parallelisieren und damit haben wir also

30:04.470 --> 30:08.550
hier ein weiteres Prinzip nochmal uns überlegt.

30:08.730 --> 30:12.770
Also erst approximativ lösen und dann den Rest mit einem exakten

30:12.770 --> 30:13.230
Verfahren.

30:14.830 --> 30:16.810
Und jetzt kommt noch eine weitere Überlegung.

30:18.390 --> 30:22.450
Wir haben jetzt gesehen, wir können das sogar im besten Fall in

30:22.450 --> 30:23.450
linearer Zeit entkriegen.

30:24.250 --> 30:25.550
Das war auch beim Jarvis Marsch.

30:25.550 --> 30:26.490
Der erste Fall war linear.

30:27.730 --> 30:30.010
Hier hatten wir jetzt ein Wegfahrt-Prinzip, das auch in linearer Zeit

30:32.630 --> 30:36.990
im erwarteten, also im besten Fall natürlich in linearer Zeit.

30:37.890 --> 30:40.530
Und jetzt geht es darum, was ist eigentlich eine untere Schranke für

30:40.530 --> 30:41.650
den schlechtesten Fall.

30:43.150 --> 30:46.210
Und dazu konstruiere ich mir die folgende Menge, die hier angedeutet

30:46.210 --> 30:46.550
ist.

30:47.350 --> 30:51.130
Da in diesem Bild sieht man die Menge, die wir hier uns aufbauen.

30:52.270 --> 30:56.810
Wir bilden eine Menge, die gerade in diesem Fall zum Beispiel eine

30:56.810 --> 30:58.390
Parabel bildet.

30:58.610 --> 30:59.530
Ein Stück einer Parabel.

31:00.430 --> 31:02.350
Funktion x².

31:03.770 --> 31:07.230
Dann liegen die Punkte hier so schön aufgereiht.

31:08.290 --> 31:08.370
So.

31:09.470 --> 31:10.390
Irgendeine Punktmenge.

31:12.350 --> 31:13.970
Ich habe ja diese Parabel nicht.

31:14.270 --> 31:16.110
Ich habe also nur eine Menge von Punkten.

31:17.110 --> 31:20.350
Und wenn ich jetzt die konvexe Hülle bestimmen möchte, muss nicht eine

31:20.350 --> 31:23.570
Reihenfolge, hier, ich habe es mal andersrum gemacht, muss also eine

31:23.570 --> 31:27.930
Reihenfolge festlegen, das wäre diese konvexe Hülle.

31:29.030 --> 31:30.270
Einmal drumherum gelaufen.

31:31.690 --> 31:37.030
Damit ich das machen kann, muss ich aber meine Punkte x1 bis xn, das

31:37.030 --> 31:38.150
sind beliebige Punkte,

31:41.190 --> 31:45.510
beziehungsweise die Punktmenge xi, xi², beliebige Punktmenge, die muss

31:45.510 --> 31:47.410
ich entsprechend bezüglich der x-Koordinaten sortieren.

31:47.410 --> 31:51.130
Wenn ich das gemacht habe, bin ich fertig.

31:51.270 --> 31:53.030
Dann habe ich die Reihenfolge des Polygons.

31:54.430 --> 31:59.930
Und das heißt aber, ich muss, um die konvexe Hülle zu bekommen, ein

31:59.930 --> 32:00.930
Sortierproblem lösen.

32:02.410 --> 32:06.670
Und damit habe ich den schlechtesten Fall, oder eine untere Schranke

32:06.670 --> 32:09.270
für den schlechtesten Fall, das ist die gleiche untere Schranke für

32:09.270 --> 32:10.590
das Sortieren am schlechtesten Fall.

32:11.810 --> 32:16.150
Und damit habe ich also gezeigt, dass ich bei der konvexen Hülle eine

32:16.150 --> 32:17.870
untere Schranke habe von n log n.

32:19.790 --> 32:24.530
Das gilt natürlich auch im Mittel, also ich habe hier eine untere

32:24.530 --> 32:28.410
Schranke für den schlechtesten Fall.

32:29.330 --> 32:31.750
Oh, das ist anders als...

32:31.750 --> 32:32.650
aber ich habe aber...

32:33.410 --> 32:34.570
was falsch gesagt habe ich.

32:35.030 --> 32:38.010
Es ist hier Omega von n, eine scharfe untere Schranke für das mittlere

32:38.010 --> 32:38.410
Verhalten.

32:39.070 --> 32:41.110
Das kann man als mittlere Verhalten heißen, ich habe irgendeine

32:41.110 --> 32:45.490
beliebige Anordnung der Punkte und dann habe ich also im Mittel

32:45.490 --> 32:52.890
tatsächlich Omega von n als Mindestaufwand und nicht dieses n log n.

32:55.510 --> 32:55.850
Gut.

32:56.350 --> 32:58.230
Diese untere Schranke für den schlechtesten Fall dürfte sehr

32:58.230 --> 32:59.010
einsichtig sein.

32:59.970 --> 33:03.870
Und damit bin ich eigentlich am Ende dieses Teils über algorithmische

33:03.870 --> 33:04.410
Geometrie.

33:06.190 --> 33:10.050
Ich denke, was ich Ihnen gezeigt habe, ist, dass man hier eine ganze

33:10.050 --> 33:13.110
Reihe interessanter Problemstellungen zu packen hat, oder zu

33:13.110 --> 33:13.890
bearbeiten hat.

33:15.550 --> 33:18.910
Du könntest sagen, Galerieprobleme sind nicht so interessant, aber es

33:18.910 --> 33:22.110
gibt viele Probleme, die wir heutzutage bearbeiten, wenn wir irgendwo

33:22.110 --> 33:26.350
Dinge auf dem Bildschirm darstellen und irgendwelche Überlappungen von

33:26.350 --> 33:27.610
Objekten machen und ähnliches.

33:27.690 --> 33:30.470
Da stecken überall Probleme drin, die man mit diesen Methoden

33:30.470 --> 33:30.910
bearbeitet.

33:32.610 --> 33:36.150
Man muss ein bisschen aufpassen, darauf hatte ich auch schon mal

33:36.150 --> 33:40.670
hingewiesen, die meisten Algorithmen im Bereich der algorithmischen

33:40.670 --> 33:44.670
Geometrie gehen davon aus, dass ich keine Sonderfälle habe.

33:45.370 --> 33:48.110
Sonderfälle sind eben so Dinge, die ich schon mal erwähnt hatte.

33:48.710 --> 33:54.430
Ich möchte also Punkte irgendwie anordnen und habe jetzt festgestellt,

33:54.550 --> 33:58.890
ich mache jetzt Radialkoordinaten von dem Punkt aus und wenn ich jetzt

33:58.890 --> 34:03.970
eben feststelle, naja, diese, ups, das war jetzt keine Gerade, aber

34:03.970 --> 34:06.670
dieses Problem, dass Punkte sehr nah beieinander liegen.

34:07.330 --> 34:10.910
Ich möchte feststellen, ich kann es auch so aufmalen, eine Kante und

34:10.910 --> 34:13.650
ich möchte feststellen, liegt ein Punkt links oder rechts, das ist

34:13.650 --> 34:17.050
einfach, aber liegt der Punkt oder der Punkt oder der Punkt oder der

34:17.050 --> 34:20.110
Punkt oder der Punkt linke links oder rechts von dieser Kante.

34:21.770 --> 34:26.110
Wenn das realwertige Koordinaten sind, kann das eben Probleme geben,

34:26.610 --> 34:29.450
dann bekomme ich fehlerhafte Entscheidungen und dann muss man sehen,

34:29.510 --> 34:31.870
wie man mit solchen Problemen in der Realität umgeht.

34:31.870 --> 34:35.550
Das ist noch ein Problem, das man in den letzten Jahren sehr intensiv

34:35.550 --> 34:40.670
angeguckt hat und das sind also dann so die Übertragungen dieser

34:40.670 --> 34:45.530
Algorithmen, die für angenehme Fälle hervorragend laufen, aber eben in

34:45.530 --> 34:47.130
solchen Extremfällen manchmal nicht.

34:47.750 --> 34:49.610
Da muss man die dann für die Praxis robust machen.

34:50.450 --> 34:53.670
Es gibt dazu eine große Bibliothek von Verfahren, kann ich auch noch

34:53.670 --> 35:00.130
kurz aufschreiben, also die Bibliothek Leda ist eine große Bibliothek

35:00.130 --> 35:01.190
für Verfahren.

35:02.170 --> 35:09.010
The Library of Efficient Data Structures and Algorithms ist also eine

35:09.010 --> 35:14.210
Riesenbibliothek von effizienten Algorithmen, die man einfach nutzen

35:14.210 --> 35:14.470
kann.

35:14.590 --> 35:18.190
Da haben zig Wissenschaftler daran gearbeitet, um so etwas als

35:18.190 --> 35:23.810
praktisch große Bibliothek für Algorithmen zu machen, damit man sich

35:23.810 --> 35:26.810
die einfach da runterziehen kann und anwenden kann für sein Problem.

35:28.330 --> 35:31.470
Es sind für algorithmische Geometrie auch eine Reihe neuer

35:31.470 --> 35:35.450
Datenstrukturen entworfen worden, insbesondere für Suchverfahren,

35:35.590 --> 35:39.390
Suchbäume in geometrischen Strukturen.

35:39.810 --> 35:41.210
Die habe ich Ihnen alle gar nicht vorgestellt.

35:42.030 --> 35:44.010
Das würde auch jetzt etwas zu weit führen.

35:44.410 --> 35:48.810
Ich wollte Ihnen im Wesentlichen dieses Gebiet ein bisschen aufmachen,

35:48.990 --> 35:54.230
zeigen, was für Probleme dort existieren und ich hoffe, dass ich Ihr

35:54.230 --> 35:55.810
Interesse dafür etwas geweckt habe.

35:55.810 --> 35:57.990
Wie auch für die anderen Bereiche.

35:58.390 --> 36:00.550
Damit sind wir am Ende des Abschnitts.

36:00.750 --> 36:04.170
Diesmal soll das beibehalten werden, nicht verworfen werden.

36:05.210 --> 36:12.650
Und bevor wir jetzt zur abschließenden Kapitel kommen, nämlich zu dem

36:12.650 --> 36:19.090
Kapitel 8, abschließende Bemerkungen, will ich Ihnen noch ganz kurz

36:20.030 --> 36:22.290
die Rückmeldung aus der Evaluation geben.

36:22.390 --> 36:27.410
Sie haben ja die Evaluation bewertet und es ist der Auswertungsbericht

36:27.410 --> 36:31.750
da und wir haben hier ein hervorragendes Ergebnis, ein

36:32.770 --> 36:34.270
Lehrqualitätsindex von 100.

36:35.150 --> 36:37.310
Ich weiß nicht, ob Ihnen der Lehrqualitätsindex etwas sagt.

36:38.510 --> 36:40.810
Der Lehrqualitätsindex sagt Ihnen nichts.

36:41.410 --> 36:44.210
Dann werde ich Ihnen das einmal kurz darstellen.

36:45.130 --> 36:50.090
Der Lehrqualitätsindex ist etwas, was neu eingeführt wurde.

36:50.710 --> 36:51.870
Man kann das alles indizieren.

36:52.670 --> 36:55.130
Perfekte Aufgabe Wirtschaftsingenieur kann sowas ganz toll.

36:56.170 --> 37:00.290
Und dann gibt es jetzt eine ganze Reihe von Gewichtungen der Antworten

37:00.290 --> 37:03.010
auf bestimmte Fragen, die Ihnen gegeben wurden.

37:03.510 --> 37:05.630
Also, da haben wir die Gesamtnote.

37:06.630 --> 37:08.790
Das war irgendeine Frage.

37:08.970 --> 37:10.690
Wie beurteilen Sie die Vorlesung insgesamt?

37:11.250 --> 37:11.870
Gibt 50%.

37:13.470 --> 37:17.050
Dann haben wir den notwendigen Arbeitsaufwand 12,5%.

37:17.050 --> 37:18.370
Das finde ich ein bisschen heikel.

37:19.150 --> 37:20.850
Der notwendige Arbeitsaufwand.

37:21.510 --> 37:23.430
Wenn Sie sagen, das ist viel zu schwer.

37:23.870 --> 37:25.190
Und ich sage, das muss aber so sein.

37:25.310 --> 37:25.890
Das ist ganz toll.

37:26.070 --> 37:27.810
Das macht die Qualität der Vorlesung aus.

37:28.270 --> 37:29.030
Dann ist das schwierig.

37:29.190 --> 37:31.050
Aber man sagt, das muss so etwa ein Mittel sein.

37:31.310 --> 37:32.490
Wenn es zu leicht ist, ist es nicht gut.

37:32.550 --> 37:33.830
Wenn es zu schwer ist, ist es auch nicht gut.

37:34.570 --> 37:37.170
Also, ich weiß nicht, wie das hier tatsächlich reingeht, aber

37:38.250 --> 37:41.390
angemessen, unangemessen, da muss man ein bisschen aufpassen, wie man

37:41.390 --> 37:41.870
das bewährt.

37:42.790 --> 37:46.510
Struktur der Lehrveranstaltung geht auch mit 12,5% ein.

37:47.010 --> 37:50.050
Engagement und Motivation des Dozenten, Eingehen des Dozenten auf

37:50.050 --> 37:52.370
Fragen und Belange der Studierenden, das geht also alles ein.

37:52.410 --> 37:56.010
Da will man sehen, inwieweit ist die Lehrveranstaltung auf die

37:56.010 --> 37:57.910
Interessen der Studierenden abgestimmt.

37:58.750 --> 37:59.950
Das bestimmt die Lehrqualität.

38:00.810 --> 38:09.730
Jetzt hat man entsprechend das hier dann genauer in Skalen eingesetzt

38:09.730 --> 38:11.250
und hat dann Folgendes.

38:11.350 --> 38:15.470
Man hat hier sogenannte Follow-up, man kann ja nicht einfach das

38:15.470 --> 38:16.830
Deutsch bezeichnen, das geht ja nicht.

38:17.490 --> 38:18.550
Das sind also Follow-up-Gruppen.

38:18.770 --> 38:23.010
Fug 1 ist 100%, ganz breit.

38:23.370 --> 38:32.130
Fug 2, das ist von 75 bis 100, Fug 3 von 50 bis 75, Fug 4 von 25 bis

38:32.130 --> 38:35.770
50 und Fug 5, das sind die ganz schlechten.

38:36.770 --> 38:37.610
Man kann auch sagen, das ist Unfug.

38:37.770 --> 38:40.310
Aber das ist nicht Unfug, das ist Fug.

38:41.010 --> 38:42.370
Mit Fug und Recht.

38:43.570 --> 38:49.470
Und dann gibt es hier noch genauere Qualitätsrichtlinien und

38:49.470 --> 38:50.110
Anzahlfragebögen.

38:50.290 --> 38:55.430
So etwas wird also dann der Fakultät mitgeteilt als Ergebnis dieser

38:55.430 --> 38:55.950
ganzen Evaluation.

38:57.050 --> 39:00.070
Und dann kommen hier am Ende, hier ist nochmal eine genaue Erläuterung

39:00.070 --> 39:02.430
für Lehrqualitätsindex von 100.

39:02.770 --> 39:07.010
Erläuterung, die Veranstaltungen, die in allen einen

39:07.010 --> 39:10.450
Lehrqualitätsindex von 100 erreicht haben, diese Veranstaltungen sind

39:10.450 --> 39:13.170
generell so positiv, dass wir diese Veranstaltungen als gänzlich

39:13.170 --> 39:14.430
unkritisch einstufen.

39:15.070 --> 39:18.110
Also, perfekt, diese Vorlesung ist gänzlich unkritisch.

39:18.770 --> 39:22.190
Empfehlung, jetzt kommt es aber, um die Qualität dieser Veranstaltung

39:22.190 --> 39:24.850
mit hervorragender Konzeption, denen es gelingt, die unterschiedlichen

39:24.850 --> 39:29.970
Lernbedürfnisse der Studierenden zu integrieren, zu erhalten, wird,

39:30.110 --> 39:33.370
wie bereits eingangs im Allgemeinteil erläutert, eine regelmäßige

39:33.370 --> 39:38.750
Reflexion und der kollegiale Austausch wie auch die regelmäßige

39:38.750 --> 39:41.850
jährliche Teilnahme an hochpädagogischen Workshops aus Modul 2

39:41.850 --> 39:42.510
empfohlen.

39:43.510 --> 39:45.030
Ich muss mich immer noch weiterbilden.

39:45.450 --> 39:48.530
Wenn man gut ist, muss man noch immer sehen, dass man das auch erhält.

39:49.570 --> 39:52.670
Zielsetzung, Reflexion des Erfolgs und die Lernkompetenz weiter

39:52.670 --> 39:53.290
auszubauen.

39:53.370 --> 39:54.970
Wir sind nie zufrieden, sondern wir müssen es immer noch besser

39:54.970 --> 39:55.290
machen.

39:56.230 --> 39:58.930
Das Gleiche steht bei Hellgrün, also wir sind auch schon recht gut,

39:58.990 --> 40:03.050
auch unkritisch und auch bei dem steht jährlich Teilnahme an

40:03.050 --> 40:04.890
hochpädagogischen Workshops aus Modul 2.

40:05.510 --> 40:07.410
Ich muss gestehen, ich weiß nicht, welche das sind.

40:07.470 --> 40:08.490
Meine Mitarbeiter wissen das.

40:08.610 --> 40:10.830
Die gehen zu diesen Workshops hin und machen dort eine

40:10.830 --> 40:11.810
hochschuldidaktische Ausbildung.

40:12.690 --> 40:17.590
Als ich in der Altersstufe war, in der Qualifikationsstufe, da gab es

40:17.590 --> 40:19.390
sowas noch nicht, da haben wir es uns selbst beigebracht.

40:20.730 --> 40:27.490
Dann sehen Sie, gibt es eben hier die Erklärungen für Gelb und hier

40:27.490 --> 40:31.210
kann man sich eine Einzelberatung im hochschuldidaktischen Zentrum

40:31.210 --> 40:31.810
buchen.

40:33.630 --> 40:36.670
Und dann geht es zu Orange und am Ende Rot.

40:37.770 --> 40:40.970
Den Lehrenden wird unbedingt geraten, die Ergebnisse ihrer Evolution

40:40.970 --> 40:43.310
mit den befragten Studierenden usw.

40:43.590 --> 40:46.370
intensiv zu nutzen und ihre Veranstaltungen zu verbessern.

40:46.810 --> 40:49.350
Hier kann die Moderation durch Experten des hochschuldidaktischen

40:49.350 --> 40:50.770
Zentrums erfolgen.

40:50.910 --> 40:53.730
Die verstärkte Auseinandersetzung ist unabdingbar, also die armen

40:53.730 --> 40:55.770
Leute, die da unten landen, aber ich glaube, da gibt es keinen in der

40:55.770 --> 40:57.250
Fakultät, der so schlecht ist.

40:58.010 --> 41:00.650
Also das Wesentliche ist, diese haben diese Vorlesung recht gut

41:00.650 --> 41:01.370
bewertet.

41:02.250 --> 41:05.510
Mit 100 und das zeigt sich dann hier halt in den einzelnen

41:05.510 --> 41:09.390
Auswertungen, dass sie hier überwiegend recht gute Noten gegeben

41:09.390 --> 41:09.810
haben.

41:10.930 --> 41:13.730
Irgendwo war mal etwas...

41:13.730 --> 41:21.410
Achso, Arbeitsaufwand ist eher etwas hoch und auch ein bisschen wird

41:21.410 --> 41:22.290
eher...

41:22.290 --> 41:23.310
Na gut, das ist in der Mitte hier.

41:23.670 --> 41:25.590
Der Mittelwert, die Bewertung ist in der Mitte.

41:26.350 --> 41:29.670
Aber das ist ein bisschen ein kritischer Punkt.

41:30.290 --> 41:32.150
Und wenn man sich das anguckt, dann hier am Ende

41:35.350 --> 41:36.150
in der...

41:36.590 --> 41:38.510
Das Wesentliche für mich sind immer die Freitextantworten.

41:39.650 --> 41:41.290
Das finde ich immer am interessantesten.

41:42.370 --> 41:43.590
Und, wo kommen Sie endlich?

41:43.790 --> 41:44.930
Da kommt irgendetwas.

41:45.890 --> 41:47.370
Fragen zu Lehrveranstaltungen.

41:47.650 --> 41:50.810
Hilfsmittel, hätten mein Lernen besser unterstützt, wenn...

41:50.810 --> 41:51.910
Aufzeichnung sehr gut.

41:52.310 --> 41:52.430
Oh.

41:55.070 --> 41:56.610
Da hat einer sich anscheinend vertan.

41:56.930 --> 41:59.390
Also, wenn Aufzeichnung sehr gut, ich meine, der meint das anders.

41:59.510 --> 42:01.290
Der meint, dass die Aufzeichnung sehr gut ist, da nicht alle zur

42:01.290 --> 42:02.070
Vorlesung kommen können.

42:02.730 --> 42:04.110
Okay, das steht auch hier im...

42:04.470 --> 42:06.730
Ups, das steht auch hier im nächsten Teil drin.

42:08.550 --> 42:10.410
Vorlesung gut gefallen hat mir vor allen Dingen die

42:10.410 --> 42:11.690
Vorlesungsaufzeichnungen.

42:15.230 --> 42:19.450
Und hier steht Übungsbetrieb fördert Verständnis.

42:23.610 --> 42:26.850
Aufgaben selbst bearbeiten.

42:27.710 --> 42:28.030
Okay.

42:28.670 --> 42:30.590
Das ist anscheinend nicht mehr üblich.

42:31.410 --> 42:35.850
Das ist ein Punkt, der also etwas schwierig ist.

42:36.510 --> 42:39.890
Übungen sollten eigentlich, da haben wir den Zweck, dass man Aufgaben

42:39.890 --> 42:40.670
selbst bearbeitet.

42:40.830 --> 42:41.230
Was sonst?

42:41.430 --> 42:44.470
Selbstständige Beschäftigung mit dem Stoff einer Vorlesung.

42:44.930 --> 42:46.970
Nur damit lernt man intensiver den Stoff kennen.

42:46.970 --> 42:50.010
Aber das scheint immer weniger in Übungen der Fall zu sein.

42:50.090 --> 42:51.790
Da wird vorgeführt, wie man eine Aufgabe löst.

42:52.150 --> 42:53.430
Daraus lernt man nicht viel.

42:53.870 --> 42:54.770
Man muss es selber machen.

42:55.450 --> 42:58.190
Und wir geben halt Rückmeldung, soweit das geht.

42:59.410 --> 43:02.770
Und wollen Ihnen helfen, dabei mit dem Stoff selbstständig umzugehen.

43:02.850 --> 43:03.930
Das ist das, was wir vermitteln müssen.

43:04.330 --> 43:07.970
Was wir leider in den Grundvorlesungen in dem Umfang einfach nicht

43:07.970 --> 43:08.490
mehr schaffen.

43:09.130 --> 43:12.230
Und wir haben auch ein weiteres Problem in den Grundvorlesungen, dass

43:12.230 --> 43:17.430
wir dort, wenn wir dort sagen, wir lassen die Aufgaben abgeben und

43:17.430 --> 43:20.050
geben dann irgendeinen Bonus für eine bestimmte Anzahl von erfolgreich

43:20.050 --> 43:23.950
bearbeiteten Aufgaben, dann haben auf einmal alle den Bonus, weil wir

43:23.950 --> 43:27.010
relativ viele identische Aufgaben oder Lösungen bekommen.

43:27.670 --> 43:30.170
Da wird nicht mehr selbst bearbeitet, sondern nur noch selbst

43:30.170 --> 43:30.550
geschrieben.

43:31.290 --> 43:33.230
Und die Bearbeitung haben andere gemacht.

43:34.130 --> 43:35.590
Und das ist leider so.

43:35.750 --> 43:37.470
Und deswegen sind wir dazu übergegangen, dass wir diese

43:37.470 --> 43:38.610
Anwesenheitsübungen machen.

43:39.210 --> 43:43.730
Und die Bonusklausur, die praktisch ersetzen soll, die Überprüfung

43:43.730 --> 43:47.050
oder die praktischen Bonus geben dafür, dass man sich selbstständig

43:47.050 --> 43:49.210
beschäftigt hat mit dem Stoff der Vorlesung.

43:49.870 --> 43:54.090
Mein Ideal ist eigentlich, in kleinen Übungsgruppen intensiv sich mit

43:54.090 --> 43:54.950
dem Stoff zu beschäftigen.

43:55.030 --> 43:56.770
Ich habe das als Student selbst so kennengelernt.

43:57.150 --> 43:59.830
Ich hatte während der ersten vier Semester meines Studiums in der

43:59.830 --> 44:03.890
Mathematik damals Übungsgruppen mit Mathematik, da waren sieben bis

44:03.890 --> 44:07.610
zehn Leute drin, in den einzelnen Übungsgruppen, bei 500 Studenten in

44:07.610 --> 44:08.430
der Vorlesung.

44:09.130 --> 44:14.530
Das war ein massiver Übungsbetrieb und aus dem Jahrgang sind

44:14.530 --> 44:17.250
überdurchschnittlich viele hervorragende Wissenschaftler

44:17.250 --> 44:17.830
hervorgegangen.

44:18.250 --> 44:23.170
Sehr viele Leute, die mittlerweile Abiturant- Professoren wurden.

44:24.170 --> 44:27.550
Vermutlich auch noch sind, aber nicht mehr lange, weil irgendwann die

44:27.550 --> 44:28.930
Altersgrenze naht.

44:29.070 --> 44:32.950
Aber das war also, wenn man intensiv sich mit dem Stoff beschäftigen

44:32.950 --> 44:35.730
darf, hat das einfach ganz tolle Effekte.

44:36.130 --> 44:40.970
Und das ist das Ideal einer Universität, dass man zum selbstständigen

44:40.970 --> 44:41.890
Denken angeregt wird.

44:42.570 --> 44:48.450
Wir haben einigermaßen viel Tutorien, denke ich, und bieten auch die

44:48.450 --> 44:49.770
Chance, das selbstständig zu machen.

44:50.770 --> 44:51.750
Hier insbesondere.

44:51.990 --> 44:54.190
In den kleineren Vorlesungen kann man das tun und das finde ich ganz

44:54.190 --> 44:55.630
wichtig, das zu machen.

44:56.510 --> 44:59.250
Dann gibt es hier Nicht gut gefallen hat mir.

45:00.110 --> 45:02.150
Schwierig zu beurteilen, welche Themen wichtig sind.

45:02.890 --> 45:03.770
Alle Themen sind wichtig.

45:05.150 --> 45:07.190
Also es ist nun mal so.

45:07.650 --> 45:10.970
Natürlich ist es so, dass nicht, wenn ich sage, alle Themen sind

45:10.970 --> 45:16.930
wichtig, wenn ich bei zum Beispiel diesem algebraischen Problem Ihnen

45:16.930 --> 45:20.730
einen Satz gezeigt habe oder bewiesen habe, dass ich mindestens so und

45:20.730 --> 45:25.270
so viele Additionen brauche, um ein Polynom auszuwerten.

45:25.510 --> 45:26.950
Da wurde ein Beweis vorgeführt.

45:27.370 --> 45:29.910
Ich werde in einer Klausur niemals verlangen, dass Sie einen

45:29.910 --> 45:33.250
komplizierten Beweis jetzt nochmal genau nachvollziehen.

45:33.830 --> 45:38.030
Was ich frage in Klausuren, das ist aber eigentlich auch sollte

45:38.030 --> 45:40.830
allgemein bekannt sein, was man in Klausuren fragt, das sind

45:40.830 --> 45:44.570
eigentlich so wesentliche Erkenntnisse, wesentliche Ideen, die man

45:44.570 --> 45:48.550
versucht hat in der Vorlesung rüberzubringen und die man dann abfragt

45:48.550 --> 45:53.870
oder abfragt, ist der Student oder die Studentin in der Lage diese

45:53.870 --> 45:56.630
Ideen sinnvoll einzusetzen, das umzusetzen.

45:57.670 --> 46:01.770
Das heißt, was wir normalerweise fragen, ist, entweder Sachen direkt

46:01.770 --> 46:04.410
nochmal wiederzugeben, die in der Vorlesung schon drin waren oder dran

46:04.410 --> 46:08.930
waren, oder eben Dinge zu übertragen auf ähnliche Problemstellungen,

46:09.010 --> 46:12.450
wie man sie zum Beispiel in den Übungsaufgaben bearbeitet hat oder wie

46:12.450 --> 46:13.850
sie in der Vorlesung behandelt wurden.

46:14.450 --> 46:20.410
Und ich kann jetzt nicht sagen, dass Graph-Algorithmen unwichtig sind

46:20.410 --> 46:24.170
oder Algorithmische Geometrie oder Algorithmatische Probleme.

46:25.950 --> 46:26.630
Das ist...

46:27.070 --> 46:30.990
Überall habe ich versucht, Ihnen wesentliche Prinzipien für den

46:30.990 --> 46:32.970
Algorithmenentwurf zu vermitteln.

46:33.190 --> 46:38.950
Oder auch die, meinetwegen, O-Notation oder diese Abschätzung von

46:38.950 --> 46:39.830
Rekurrenzgleichungen.

46:40.310 --> 46:43.730
Das ist auch wichtig, dass man weiß, wie man damit umgegangen ist, wie

46:43.730 --> 46:44.770
man Sachen abschätzen kann.

46:45.150 --> 46:46.750
Deswegen kann ich nicht sagen, das ist nicht relevant.

46:48.090 --> 46:53.130
Aber ich werde von Ihnen nicht verlangen, dass wir beweisen, warum zum

46:53.130 --> 46:58.310
Beispiel bei Straßen warum jetzt bei Straßen genau diese Formel da

46:58.310 --> 47:01.170
rauskommt für die Laufzeit.

47:01.970 --> 47:05.150
Das war eine etwas kompliziertere Darstellung, Abschätzung dieser

47:05.150 --> 47:06.850
Aufwände.

47:07.050 --> 47:10.310
Da haben wir diese Summen angeguckt, umgeformt, kriegten dann raus,

47:10.410 --> 47:15.990
der Aufwand ist in dieses N hoch Log zur Basis K von M von K.

47:16.450 --> 47:18.210
Wo bei M von K die Anzahl der Multiplikationen war.

47:19.550 --> 47:22.350
Das haben wir später gesehen anhand des Master-Theories.

47:22.350 --> 47:24.730
Hätten wir uns auch da direkt ableiten können.

47:25.550 --> 47:29.630
Also solche Sachen, komplizierte Beweise, frage ich nicht.

47:30.830 --> 47:33.950
Und ich denke, das ist das Wesentliche, dass man sagt, die Ideen sind

47:33.950 --> 47:40.570
wichtig und ob man in der Lage ist, so wesentliche Prinzipien aus der

47:40.570 --> 47:44.210
Vorlesung anzuwenden, das kann man an relativ einfachen

47:44.210 --> 47:46.050
Problemstellungen abfragen.

47:46.410 --> 47:51.390
Und das hoffen wir in den Klausuren auch immer hinzukriegen.

47:53.730 --> 47:55.250
Es sind halt jetzt immer Klausuren.

47:55.590 --> 47:58.470
Eigentlich mache ich lieber mündliche Prüfungen, weil man da viel

47:58.470 --> 47:59.670
besser ein Gespräch führen kann.

47:59.770 --> 48:01.850
Und das war bei dieser Thematik eigentlich auch sehr sinnvoll.

48:02.250 --> 48:04.850
Aber wir können auch entsprechende Aufgaben in Klausuren machen.

48:06.890 --> 48:08.410
Da steht hier etwas über eine Übung.

48:08.570 --> 48:10.830
Schlechte Übung, kann ich wenig zu sagen.

48:10.910 --> 48:12.630
Ich war bei den Übungen nicht direkt dabei.

48:14.470 --> 48:20.530
Da muss Herr Schukler sich über die Kritik, die da gekommen ist

48:20.530 --> 48:25.190
Gedanken machen und sehen, was da konkrete Kritik gewesen ist, wie man

48:25.190 --> 48:26.810
das verbessern kann.

48:27.970 --> 48:31.210
Man ist nie perfekt und bei Übungen muss man vieles erklären und

48:31.210 --> 48:36.050
erläutern und das klappt natürlich nicht immer perfekt und sofort.

48:37.690 --> 48:42.450
Dann haben wir an der Vorlesung noch etwas zu verbessern.

48:42.930 --> 48:46.010
Steht hier praktische Beispiele aus heutiger Industrie.

48:48.410 --> 48:55.410
Ja, ich kann Ihnen natürlich zu jedem Algorithmus, der dort vorkommt,

48:55.430 --> 48:58.850
ein Beispiel nennen aus der Industrie, wo man genau solch einen

48:58.850 --> 48:59.810
Algorithmus braucht.

48:59.970 --> 49:03.790
Ich habe zu Anfang versucht, so ein bisschen darzustellen, wo

49:03.790 --> 49:07.730
eigentlich die Problemstellungen herkommen, mit denen wir uns hier

49:07.730 --> 49:08.210
beschäftigen.

49:08.870 --> 49:11.810
Ich habe das nachher nicht mehr so jedes Mal gesagt.

49:12.290 --> 49:13.930
Bei algorithmischer Geometrie habe ich es noch mal gesagt.

49:14.150 --> 49:16.690
Bei Graph-Problemen gehe ich davon aus, das wissen Sie alle als

49:16.690 --> 49:21.130
Wirtschaftsingenieure, wo man solche Graph-Probleme bearbeiten muss.

49:21.810 --> 49:25.270
Aber das sind die Probleme, die ich hier rausgeguckt habe, das sind

49:25.270 --> 49:30.170
alles Kernprobleme der Informatik, die an ganz vielen

49:30.170 --> 49:31.370
Anwendungsstellen auftauchen.

49:32.370 --> 49:34.990
Und deswegen ist es wichtig, da eben zu wissen, wie kann ich

49:34.990 --> 49:36.750
systematisch solche Probleme lösen.

49:37.850 --> 49:42.090
Dann steht hier Formeln in besserer Schrift, zum Beispiel Times New

49:42.090 --> 49:43.990
Roman mit Hech.

49:45.250 --> 49:46.950
Es gibt eine Regel.

49:48.170 --> 49:51.650
Auf Folien verwendet man eine serifenfreie Schrift.

49:53.550 --> 49:56.370
Serifenfrei heißt nicht Times New Roman.

49:58.430 --> 50:01.750
Ich weiß, dass bei den Formeln manchmal gewisse Schwierigkeiten

50:01.750 --> 50:06.050
dadurch sind, dass da die Serifenfreiheit dazu führt, dass zum

50:06.050 --> 50:11.630
Beispiel ein i und ein j manchmal in der Schrift Areal schwer zu

50:11.630 --> 50:15.230
unterscheiden sind, weil die in der Auflösung auf der Folie manchmal

50:15.230 --> 50:16.570
fast identisch aussahen.

50:17.090 --> 50:18.410
Das ist ein kleines Problem.

50:19.670 --> 50:24.450
Aber ansonsten denke ich, die Formel ist lesbar, ob sie jetzt in Times

50:24.450 --> 50:28.310
New Roman oder in Areal oder Kalibri oder sonst irgendwas geschrieben

50:28.310 --> 50:28.810
ist.

50:29.730 --> 50:32.350
Das finde ich, kann ich nicht so ganz nachvollziehen.

50:32.930 --> 50:34.710
Ich weiß nicht, wie die Anwesenden hier das sehen.

50:35.450 --> 50:36.810
Ob das für sie ein Problem war?

50:37.590 --> 50:38.730
Ja, nicht.

50:39.430 --> 50:40.990
Das hört man natürlich gerne.

50:41.130 --> 50:42.690
Super Vorlesung, spannend usw.

50:43.210 --> 50:46.370
Allerdings gewisse Angst vor der Klausur.

50:47.070 --> 50:49.210
Deswegen bin ich gerade ein bisschen mehr auf die Klausur eingegangen.

50:50.010 --> 50:51.130
Bezüglich Machbarkeit.

50:52.590 --> 50:55.230
Einige Kommilitonen haben deshalb aufgegeben.

50:55.550 --> 50:56.630
Das bedauere ich sehr.

50:57.410 --> 51:00.990
Es waren tatsächlich zu Anfang deutlich mehr Anmeldungen in den

51:00.990 --> 51:02.370
Übungen da, als jetzt am Ende.

51:02.410 --> 51:04.170
Wir haben 30 Anmeldungen für die Klausur.

51:06.110 --> 51:08.790
Ich weiß nicht, warum diese Angst da ist.

51:09.670 --> 51:10.750
Sie sind alles Wirtschaftsingenieure.

51:10.790 --> 51:12.210
Also überwiegend Wirtschaftsingenieure.

51:12.310 --> 51:15.410
Nicht alle, auch Wirtschaftsmathematiker und Informationsleute ein

51:15.410 --> 51:15.530
bisschen.

51:16.410 --> 51:20.190
Aber sie haben eine gute formale Ausbildung.

51:20.350 --> 51:24.810
Die Wirtschaftsingenieure sind diejenigen, die am besten quantitativ

51:24.810 --> 51:27.130
-methodisch ausgebildet sind, wenn man sich irgendwelche

51:27.130 --> 51:28.730
Wirtschaftswissenschaftler anguckt, weltweit.

51:29.490 --> 51:34.530
Es gibt keine anderen, die solch eine formale Ausbildung bekommen, wie

51:34.530 --> 51:35.370
hier in Karlsruhe.

51:36.130 --> 51:38.430
Es ist weltweit eine einzigartige Ausbildung.

51:40.470 --> 51:44.110
Und das kann sich problemlos messen mit dem, was die Mathematiker

51:44.110 --> 51:46.350
bekommen an mathematischer Ausbildung und ähnlichen Dingen.

51:46.910 --> 51:48.050
Also daran kann es nicht liegen.

51:50.010 --> 51:55.010
Und ich weiß genau, dass oft so Vorbehalte sind, ach, wieder diese

51:55.010 --> 51:56.490
Algorithmen und das ist alles so schwierig.

51:57.070 --> 51:58.890
Aber eigentlich ist das gar nicht so schwierig.

51:59.270 --> 52:02.990
Wenn man sich anguckt, was man da für Gedanken machen muss, das sind

52:03.530 --> 52:06.950
die gleichen Gedanken, die sie sich machen, wenn sie komplexe Systeme

52:06.950 --> 52:11.610
analysieren, komplexe reale Systeme, komplexe Unternehmensstrukturen

52:11.610 --> 52:12.330
und ähnliches.

52:12.750 --> 52:16.290
Das tägliche Brot von Wirtschaftsingenieuren, sich komplexe Systeme

52:16.290 --> 52:19.490
anzuschauen, zu verstehen, zu analysieren, Schwachpunkte zu entdecken,

52:20.730 --> 52:24.550
also Performance von irgendwelchen tollen Unternehmen zu beurteilen,

52:25.090 --> 52:29.890
Ratingagenturen, ein ganz wichtiges Thema, die sind in der Lage, zu

52:29.890 --> 52:32.890
sagen, wie gut ein ganz komplexes Unternehmen im Augenblick dasteht,

52:32.930 --> 52:33.490
oder ein Staat.

52:34.310 --> 52:37.590
Wahrscheinlich machen die das nicht so formal, sondern machen das über

52:37.590 --> 52:40.350
den Daumen, aber das ist ein anderer Punkt.

52:41.090 --> 52:45.210
Ich wollte nur damit sagen, die Aufgaben, die sind nicht so schwer.

52:45.570 --> 52:47.230
Ich weiß, wir haben jetzt die Übungsaufgaben gemacht.

52:48.070 --> 52:52.570
Übungsaufgaben, die man zu Hause bearbeitet, abgibt usw., die können

52:52.570 --> 52:54.910
natürlich anders sein als das, was man in der Klausur macht.

52:55.390 --> 53:00.150
In der Klausur mache ich eine Reihe von Aufgaben, sodass die Punkte

53:01.610 --> 53:04.350
oder Quatsch, dass ich eine ganze Reihe von Aufgaben habe, die

53:04.350 --> 53:07.890
Vielfalt von Aufgaben, dass nicht jemand, der an einer Stelle ein

53:07.890 --> 53:12.830
schwarzes Loch hat oder ein Blackout hat, dann reinrasselt und die

53:12.830 --> 53:13.670
Klausur nicht bestehen kann.

53:13.790 --> 53:17.930
Das muss immer so sein, dass man eine Vielfalt von Themen hat.

53:18.030 --> 53:20.890
Das muss eine Reihe Aufgabe sein, verteilt auf eine Stunde.

53:21.530 --> 53:24.730
Das heißt, in der Regel ist die Anzahl der Punkte, die man mit einer

53:24.730 --> 53:26.710
Aufgabe kriegen kann, kleiner gleich 15.

53:27.950 --> 53:29.970
Die Anzahl der Punkte ist 60 bei uns.

53:30.150 --> 53:34.050
Die Anzahl der Punkte entspricht der Zeit, die man braucht, um die

53:34.050 --> 53:35.110
Aufgaben zu bearbeiten.

53:36.960 --> 53:41.670
die meisten Aufgaben haben irgendwas zwischen, wenn ich die

53:41.670 --> 53:46.650
Gesamtaufgaben angucke, zwischen 8 und 11, 12 oder sowas Punkte.

53:48.090 --> 53:52.750
Und das heißt, ich habe pro Aufgabe in der Regel, wenn ich mir die

53:52.750 --> 53:56.910
gesamte Aufgabe angucke, vielleicht maximal 10 Minuten, maximal 15

53:56.910 --> 54:01.110
Minuten, nie mehr als das pro Aufgabe, um das alles hinzuschreiben, zu

54:01.110 --> 54:04.030
lesen, zu verstehen, zu lösen und hinzuschreiben.

54:05.270 --> 54:06.510
Und das ist machbar.

54:07.170 --> 54:08.110
Das überprüfen wir vorher.

54:08.390 --> 54:12.150
Das heißt, die Aufgaben sind jeweils einzeln nicht so sehr schwer.

54:13.070 --> 54:16.350
Da werden wichtige Prinzipien abgefragt, aber man kann das machen.

54:17.710 --> 54:22.050
Und dann haben wir das in der Regel so, dass die Aufgaben aufgeteilt

54:22.050 --> 54:23.890
sind auf eine Reihe von Einzelaufgaben.

54:24.510 --> 54:28.850
Aufgaben teilen zu einem ähnlichen Thema, wo man dann jeweils

54:28.850 --> 54:32.330
vielleicht drei oder vier oder einen Punkt kriegt.

54:32.770 --> 54:37.130
Das heißt, wo man kleine Fragen beantworten kann, hinschreiben hat ein

54:37.130 --> 54:38.490
oder zwei oder auch vier Punkte.

54:39.910 --> 54:41.330
Je nachdem, wie aufwendig das ist.

54:41.390 --> 54:45.590
Aber das sind kleine Häppchen, die man dort abfragt und das ist nicht

54:45.590 --> 54:46.130
so schwer.

54:47.590 --> 54:51.030
Also diese Angst, die ist eigentlich, ich sehe nicht, dass die

54:51.030 --> 54:51.810
gerechtfertigt ist.

54:51.930 --> 54:55.350
Sie können gerne nachher im Forum mir sagen, ob das gerechtfertigt

54:55.350 --> 54:55.690
war.

54:56.330 --> 54:59.090
Ich denke, die Klausur, die nächste Woche geschrieben wird, die ist

54:59.090 --> 55:03.090
ganz normal, wie sonst auch immer und die sind nicht sehr schwer.

55:05.190 --> 55:08.490
Natürlich ist es erforderlich, dass man etwas verstanden hat.

55:09.690 --> 55:11.110
Dass man etwas anwenden kann.

55:11.670 --> 55:15.490
Das ist immer so, dass man gewisse Dinge einfach zeigen muss, man kann

55:15.490 --> 55:18.930
gewissen Transfer machen, man kann Fertigkeiten erworben.

55:19.350 --> 55:21.950
Das andere ist zu zeigen, dass man Dinge auch gelernt hat.

55:22.050 --> 55:22.870
Man muss wissend sein.

55:23.490 --> 55:24.910
Und daraus eine geeignete Kombination.

55:26.570 --> 55:32.770
Also insofern, tut mir leid, wenn dieser Eindruck entsteht, aber

55:32.770 --> 55:35.410
eigentlich sollten Wirtschaftsingenieure und auch

55:35.410 --> 55:39.470
Wirtschaftsmathematiker und auch Informationswirte keiner mehr Angst

55:39.470 --> 55:41.430
haben vor etwas, was ein bisschen formaler ist.

55:42.690 --> 55:45.530
Denn das ist von der Beurteilung hier alles ganz einfach.

55:46.090 --> 55:46.690
Das ist formal.

55:47.250 --> 55:51.190
Da kommt es nicht auf irgendwelche Einstellungen oder Meinungen an

55:51.190 --> 55:53.790
oder ähnliches, die man schwer beurteilen kann, wie in einigen anderen

55:53.790 --> 55:55.010
Fächern, mit denen wir zu tun haben.

55:56.630 --> 56:03.910
Hier geht es um ganz klar abschätzbare Antworten und das ist

56:03.910 --> 56:05.530
eigentlich nicht so schwer.

56:05.870 --> 56:08.350
Das, was hier dann steht, die runden Übungsblätter auf Klausurniveau

56:08.350 --> 56:11.550
herausgeben, das hat Herr Schucht aber einmal gemacht.

56:11.670 --> 56:14.510
Er hat eine Klausur Ihnen zur Verfügung gestellt, wo Sie Aufgaben,

56:14.670 --> 56:17.330
also Klausuraufgaben im Prinzip sich angeguckt haben, bearbeitet

56:17.330 --> 56:17.690
haben.

56:18.050 --> 56:19.730
Klausuren stehen ja in der Regel auch zur Verfügung.

56:20.550 --> 56:25.550
Sie wissen also, was für Klausuraufgaben im Prinzip entstehen.

56:25.930 --> 56:30.190
Bei dieser Vorlesung vielleicht nicht ganz so viele Klausuren, die

56:30.190 --> 56:33.510
online verfügbar sind, weil wir relativ häufig auch nur mündliche

56:33.510 --> 56:35.810
Prüfungen gehabt haben aufgrund kleiner Teilnehmerzahlen.

56:36.270 --> 56:38.650
In den letzten Jahren sind die Teilnehmerzahlen deutlich hochgegangen

56:38.650 --> 56:40.950
und deswegen waren es jetzt immer Klausuren.

56:41.170 --> 56:44.610
Ich weiß gar nicht, ob die Klausuren online verfügbar sind, aber ich

56:44.610 --> 56:48.050
denke eigentlich, dass Sie zumindest, hatten Sie jetzt in der

56:48.050 --> 56:50.470
Übungsgelegenheit, sich Klausuren anzuschauen.

56:52.590 --> 56:53.670
Es gibt eine oder zwei Klausuren.

56:54.050 --> 56:54.370
Eine.

56:54.930 --> 56:55.450
Aha.

56:56.170 --> 56:56.410
Gut.

56:57.910 --> 57:00.450
Ich weiß noch nicht, wie Sie das einschätzen, die wenigen Anwesenden,

57:00.970 --> 57:03.890
ob Sie das als besonders schwierig ansehen im Vergleich zur anderen

57:03.890 --> 57:04.350
Vorlesung.

57:05.670 --> 57:06.510
Ohne die Vorlesung haben wir nix.

57:07.190 --> 57:12.030
Wir würden sagen, oh, das hört so schlecht aus.

57:12.610 --> 57:14.030
Das stimmt aber nicht, oder?

57:15.550 --> 57:16.170
Ich weiß es nicht.

57:17.750 --> 57:18.330
Ja, ich weiß das.

57:18.750 --> 57:25.670
Es hat bei mir mal ein Kommentar, stand mal drin im Forum, bei meinen

57:25.670 --> 57:29.330
Klausuren, da wäre das so, dass man vorher ganz viel gelernt haben

57:29.330 --> 57:33.250
kann und trotzdem muss man in der Klausur noch nachdenken und hat

57:33.250 --> 57:36.390
nicht die Garantie, dass man eine Eins macht oder eine Zwei.

57:36.390 --> 57:40.030
Aber nur durchs Lernen macht man keine gute Note.

57:40.150 --> 57:41.890
Man muss eben auch ein bisschen verstanden haben.

57:43.050 --> 57:49.270
Und wenn es ausreichen würde, nur durch auswendig Lernen von Stoff in

57:49.270 --> 57:53.030
der Vorlesung alle Klausuren hervorragend zu bestehen, dann wäre

57:53.030 --> 57:54.470
irgendwas falsch in unserem Studium.

57:55.210 --> 57:56.410
Das ist nicht die richtige Ausbildung.

57:57.970 --> 58:03.970
Ja, und ich meine aber auch, dass die Klausuren nicht so schlecht

58:03.970 --> 58:04.790
ausgefallen sind.

58:05.830 --> 58:07.830
Ich habe jetzt keine Statistik da.

58:08.430 --> 58:11.450
Könnte ich raussuchen, aber das ist ein wichtiger Punkt.

58:13.750 --> 58:16.810
Naja, jedenfalls die Leute, die da waren, waren anscheinend mit der

58:16.810 --> 58:19.850
Vorlesung zufrieden, sonst hätten wir nicht den Lehrqualitätsimmer von

58:19.850 --> 58:20.630
100 gekriegt.

58:21.430 --> 58:24.330
Diejenigen, die nicht zufrieden waren, die waren offensichtlich dann

58:24.330 --> 58:27.710
nicht mehr in der letzten Vorlesung und haben deswegen die Qualität

58:27.710 --> 58:28.490
nicht runtergezogen.

58:29.030 --> 58:31.810
Also ich danke Ihnen auf jeden Fall für die gute Bewertung.

58:31.810 --> 58:37.350
Okay, das also zur Vorlesung und Übungen behandle ich hier nicht.

58:37.470 --> 58:38.690
Da gab es ein paar Kritikpunkte.

58:39.850 --> 58:43.810
Ich weiß nicht, ob wir die, wir können die eventuell im VAB

58:43.810 --> 58:50.230
bereitstellen, die Ergebnisse der Evaluation und dann können Sie da

58:50.230 --> 58:50.930
selber nochmal drauf gucken.

58:52.830 --> 58:59.970
Gut, jetzt zu abschließenden Bemerkungen.

59:01.810 --> 59:07.790
Was ich versucht habe, Ihnen zu vermitteln, ist, dass die Algorithmik

59:07.790 --> 59:10.250
ein zentrales Gebiet der Informatik ist.

59:10.330 --> 59:13.810
Das wussten Sie auch schon vorher, denke ich jedenfalls, dass Ihnen

59:13.810 --> 59:14.830
das vorher bekannt war.

59:15.990 --> 59:21.030
Es kommt darauf an, dass man Methoden beherrscht, Probleme zu lösen.

59:21.570 --> 59:24.270
Wir brauchen die Algorithmen überall, die Rechner sind nicht schnell

59:24.270 --> 59:26.390
genug, die Speicher sind nicht groß genug.

59:26.590 --> 59:27.710
Wir müssen das effizient machen.

59:27.710 --> 59:32.490
Ich habe mal aus einem Bereich, der sich künstliche Intelligenz nennt,

59:33.310 --> 59:38.110
bei einem Workshop die Aussage eines Vertreters der künstlichen

59:38.110 --> 59:42.850
Intelligenz gehört, diese ganzen Überlegungen zur Komplexität von

59:42.850 --> 59:49.090
Algorithmen wären völlig unsinnig, die Rechner werden alle anderthalb

59:49.090 --> 59:52.930
Jahre wieder um Faktor 2 schneller, darum bräuchte man sich gar nicht

59:52.930 --> 59:53.330
zu kümmern.

59:54.510 --> 59:58.810
Und das in einem Bereich, wo die meisten der naiv angewandten

59:58.810 --> 01:00:01.430
Algorithmen exponentielle Laufzeit haben.

01:00:02.530 --> 01:00:02.630
Ja?

01:00:04.490 --> 01:00:06.210
Also, man fasst nicht am Kopf.

01:00:06.390 --> 01:00:08.810
Oder zumindest sind die dort mindestens NP-vollständig.

01:00:09.530 --> 01:00:15.270
Die Verfahren, die häufig angewandt wurden, sind wirklich überwiegend

01:00:15.270 --> 01:00:17.690
exponentiell, sogar superexponentiell und ähnliche Dinge.

01:00:17.870 --> 01:00:19.750
Gerade im Bereich der künstlichen Intelligenz.

01:00:20.790 --> 01:00:23.970
Und da kommt das so sehr darauf an, dass man versucht, das effizienter

01:00:23.970 --> 01:00:26.550
zu machen und da Teilbereiche zu finden.

01:00:26.610 --> 01:00:29.610
Inzwischen ist die Wissenschaft der künstlichen Intelligenz da

01:00:29.610 --> 01:00:32.590
deutlich weitergekommen und die ernstzunehmenden Leute haben das

01:00:32.590 --> 01:00:34.450
erkannt, dass es darauf ankommt.

01:00:35.030 --> 01:00:38.270
Aber zu sagen, die Rechner werden ja immer schneller, wir brauchen uns

01:00:38.270 --> 01:00:44.210
darum nicht zu kümmern, das ist, wissen Sie, ist einfach naiv und wenn

01:00:44.210 --> 01:00:48.470
ich einen Algorithmus verbessern kann von n hoch 3 auf n², ist das ein

01:00:48.470 --> 01:00:52.690
toller Fortschritt, da reicht mir keine Verbesserung eines Rechners,

01:00:52.990 --> 01:00:54.610
um das zu erreichen.

01:00:55.770 --> 01:00:57.910
Also es lohnt sich immer, nach effizienten Lösungen zu suchen.

01:00:58.870 --> 01:01:02.030
Natürlich müssen die Verfahren zunächst mal etwas korrekt machen

01:01:02.030 --> 01:01:02.290
können.

01:01:02.750 --> 01:01:03.390
Das ist das erste.

01:01:03.750 --> 01:01:04.210
Korrekt.

01:01:05.110 --> 01:01:06.930
Das muss effektiv sein, das Verfahren.

01:01:07.510 --> 01:01:09.430
Und dann muss es auch noch kostengünstig sein.

01:01:10.730 --> 01:01:13.530
Aber das kostengünstig ist etwas, was durchaus eine Rolle spielt.

01:01:13.990 --> 01:01:16.810
Wenn ich mir anschaue, zum Beispiel jetzt Energiesystem.

01:01:17.930 --> 01:01:21.810
Ich muss die ganzen Entscheidungen über den Einsatz von Verbrauchern,

01:01:22.050 --> 01:01:25.630
die Mahnzeitmanagement und ähnliche Dinge, da brauche ich

01:01:26.270 --> 01:01:28.230
Echtzeitentscheidungen oder fast Echtzeitentscheidungen.

01:01:28.790 --> 01:01:30.310
Das muss extrem effizient sein.

01:01:31.550 --> 01:01:35.870
Eventuell auf Kosten der Optimalität und ähnlichen Dingen, aber da das

01:01:35.870 --> 01:01:37.550
effizient hinzukriegen, ist extrem wichtig.

01:01:38.470 --> 01:01:43.330
Nochmal, wenn ich also ein Thema hier hinschreibe, das ganze Thema

01:01:43.330 --> 01:01:47.990
Green IT ist ein Thema, was mit Effizienz zu tun hat.

01:01:48.890 --> 01:01:52.390
Wir haben inzwischen einen Energieaufwand, wenn wir uns den gesamten

01:01:52.390 --> 01:01:55.990
Primärenergieverbrauch angucken, 2% für Informationsverarbeitung.

01:01:57.970 --> 01:01:59.270
Ja, das ist wahnsinnig viel.

01:02:01.030 --> 01:02:04.690
Jede Suchanfrage bei Google kostet ziemlich viel Energie.

01:02:06.110 --> 01:02:07.270
Das muss man reduzieren.

01:02:08.210 --> 01:02:09.990
Das geht nur mit effizienten Algorithmen.

01:02:10.970 --> 01:02:16.750
Also Energieeffizienz, Green IT ist im Prinzip ein anderes Wort für

01:02:16.750 --> 01:02:17.650
effiziente Algorithmen.

01:02:19.770 --> 01:02:26.830
Und dann gibt es noch ein anderes Wort, das heißt Green by IT.

01:02:28.850 --> 01:02:31.430
Das ist interessant.

01:02:32.330 --> 01:02:36.150
Also Green IT heißt, ich möchte gerne in Rechenzentren weniger Energie

01:02:36.150 --> 01:02:36.730
verbrauchen.

01:02:36.810 --> 01:02:39.270
Ich möchte gerne im Laptop weniger Energie verbrauchen.

01:02:40.350 --> 01:02:44.770
Wesentlich in Rechenzentren bei Google oder bei Yahoo oder sonst

01:02:44.770 --> 01:02:48.110
irgendwo oder irgendwelchen Riechenzentren im ganzen Cloud-Computing

01:02:48.110 --> 01:02:51.790
-Bereichen möglichst effizient, möglichst wenig Energie verbrauchen

01:02:51.790 --> 01:02:53.050
bei der Informationsverarbeitung.

01:02:54.290 --> 01:02:57.190
Der andere Punkt ist Green by IT.

01:02:58.430 --> 01:03:05.210
Ich habe eine Fertigungsstraße und jetzt kann ich die steuern, je

01:03:05.210 --> 01:03:08.050
nachdem wie gerade der Energiebedarf ist.

01:03:09.630 --> 01:03:12.410
Beziehungsweise wie gerade die Windeinspeisung ist, oder die

01:03:12.410 --> 01:03:14.890
Stromeinspeisung aus Windkraft und Sonnenkraft.

01:03:15.150 --> 01:03:17.330
Im Augenblick dürfte sehr viel Sonnenenergie da sein.

01:03:17.730 --> 01:03:23.770
Schätzungsweise, heute wird das 10 bis 12 Gigawatt wahrscheinlich

01:03:23.770 --> 01:03:24.090
sein.

01:03:25.690 --> 01:03:28.330
Und können Sie sich angucken bei Transparency EEX.

01:03:28.630 --> 01:03:29.190
Kennen Sie vermutlich.

01:03:30.250 --> 01:03:32.410
Da sieht man jeweils den aktuellen Energieverbrauch.

01:03:33.390 --> 01:03:36.910
Der Energieverbrauch muss reduziert werden, muss angepasst werden.

01:03:37.490 --> 01:03:41.510
Das heißt, Green by IT heißt, Energieverbrauch reduzieren, schädliche

01:03:41.510 --> 01:03:47.030
Treibhausgase reduzieren und Verbrauch anpassen an vorgegebene

01:03:47.030 --> 01:03:47.670
Lastkurven.

01:03:48.270 --> 01:03:49.710
Das geht nur mit IT.

01:03:50.410 --> 01:03:52.290
Das geht nur mit effizienten Verfahren.

01:03:52.530 --> 01:03:55.850
Muss nämlich so sein, dass der Zusatzaufwand, den ich brauche, um

01:03:55.850 --> 01:03:59.310
solche Verfahren zu steuern, dass der möglichst klein ist.

01:04:00.130 --> 01:04:01.530
Also mit effizienten Verfahren.

01:04:02.090 --> 01:04:06.410
Also effiziente Algorithmen sind wirklich der Kern von all diesen

01:04:06.410 --> 01:04:07.290
Fragestellungen.

01:04:08.310 --> 01:04:10.590
Und das ist etwas, was immer wichtiger wird.

01:04:10.630 --> 01:04:15.550
Übrigens ist es so, dass abgeschätzt wird, der Energieaufwand für

01:04:16.550 --> 01:04:19.690
Informationsverarbeitung und Kommunikation, der wächst natürlich.

01:04:20.250 --> 01:04:23.550
Wenn man sich das anguckt, hier irgendein Diagramm, jetzt nur

01:04:24.230 --> 01:04:29.930
angedeutet, der Energieaufwand, der geht meinetwegen etwa so hoch hier

01:04:29.930 --> 01:04:31.010
für IT.

01:04:32.970 --> 01:04:40.130
Aber die Einsparung, Energieeinsparung, wenn man sich anguckt, ich

01:04:40.130 --> 01:04:43.450
kann das unterschiedlich sagen, wenn ich sage, ich trage das mal

01:04:43.450 --> 01:04:47.790
negativ auf, das, was ich bekomme an Einsparungen, das geht also so

01:04:47.790 --> 01:04:48.490
drastisch runter.

01:04:50.350 --> 01:04:54.530
Das heißt, ich habe immer größere Einsparungen durch den Einsatz von

01:04:54.530 --> 01:04:59.110
Informationsverarbeitung und ich habe etwas mehr Aufwand für

01:04:59.110 --> 01:05:02.230
Informationsverarbeitung, aber den Gewinn, den ich erzielen kann,

01:05:02.870 --> 01:05:06.250
durch zusätzlichen effizienten Einsatz von Informationsverarbeitung,

01:05:06.390 --> 01:05:11.470
ist um ein Vielfaches höher als das, was ich eben extra einsetze, wenn

01:05:11.470 --> 01:05:12.550
ich es geschickt mache.

01:05:13.870 --> 01:05:18.290
Und deswegen ist also effiziente Algorithmen, wie gesagt, sind

01:05:18.290 --> 01:05:18.830
unheimlich wichtig.

01:05:20.190 --> 01:05:23.650
Das, was wir hier angeguckt haben, war, dass wir natürlich uns immer

01:05:23.650 --> 01:05:26.110
anschauen müssen, Berechnungsmodell, Datenstrukturen,

01:05:26.230 --> 01:05:29.630
Rechnerstrukturen und wir haben dann eine ganze Reihe von Themen

01:05:29.630 --> 01:05:33.490
bearbeitet, insbesondere die algebraischen Probleme, Graph-Probleme,

01:05:33.550 --> 01:05:36.270
Such -Sortier-Verfahren, algorithmische Geometrie, Standardprobleme,

01:05:36.330 --> 01:05:37.610
die man halt sich anguckt.

01:05:38.110 --> 01:05:41.350
Ich habe eben nicht das Demand-Side-Management als Thema genommen.

01:05:41.930 --> 01:05:44.910
Was man beim Demand-Side-Management macht, ist im Prinzip Aufgaben

01:05:44.910 --> 01:05:46.410
bearbeiten, die hier mit drinstecken.

01:05:46.750 --> 01:05:50.550
Da muss ich irgendwelche Polynome bearbeiten, da muss ich Sachen

01:05:50.550 --> 01:05:54.030
sortieren, da muss ich auch mit Graph-Problemen zu tun und ähnlichen

01:05:54.030 --> 01:05:54.270
Dingen.

01:05:54.830 --> 01:05:57.510
Nicht mit algorithmischer Geometrie, aber mit einer Reihe anderer

01:05:57.510 --> 01:05:58.050
Problemen.

01:05:59.050 --> 01:06:02.130
Ich habe Ihnen diese verschiedenen Datenstrukturen so ein bisschen am

01:06:02.130 --> 01:06:05.690
Rande vorgestellt, vor allen Dingen aber, und das ist etwas, was

01:06:05.690 --> 01:06:11.990
eigentlich für diese Vorlesung besonders ist, diese Vielfalt von

01:06:11.990 --> 01:06:15.190
verschiedenen algorithmischen Ansätzen, je nachdem, welche

01:06:15.190 --> 01:06:17.650
Rechnungsstrukturen wir zur Verfügung haben.

01:06:18.110 --> 01:06:21.350
Das Ausnutzen der zur Verfügung stehenden Infrastruktur ist eben ein

01:06:21.350 --> 01:06:22.010
wichtiger Punkt.

01:06:22.530 --> 01:06:25.710
Habe ich nur einen Rechner, habe ich einen Software -Rechner, habe ich

01:06:25.710 --> 01:06:28.390
verteiltes Netz, auf dem ich arbeiten kann.

01:06:29.750 --> 01:06:32.710
Entsprechend zu sehen, dass die algorithmischen Ansätze darauf

01:06:32.710 --> 01:06:35.830
angepasst werden müssen, wenn ich sogar einen Hardware-Algorithmus

01:06:35.830 --> 01:06:38.450
habe, das direkt in Hardware implementiere, sind die Anforderungen

01:06:38.450 --> 01:06:39.150
wiederum anders.

01:06:39.690 --> 01:06:42.650
Das ist ein wichtiger Punkt, den ich wirklich versucht habe, Ihnen zu

01:06:42.650 --> 01:06:43.150
vermitteln.

01:06:43.810 --> 01:06:46.610
Wir müssen bei dem Entwurf von Algorithmen darauf achten, wie kann ich

01:06:46.610 --> 01:06:49.870
die Infrastruktur, die zur Verfügung stehen, sinnvoll ausnutzen, was

01:06:49.870 --> 01:06:52.690
kann ich durch Parallelität erreichen, durch Pipeline und ähnliche

01:06:52.690 --> 01:06:53.010
Sachen.

01:06:53.750 --> 01:06:56.370
Wir haben uns angeguckt, untere und obere Schranken, ich habe Ihnen

01:06:56.370 --> 01:06:59.330
den Mapping-Ansatz vorgestellt, auch das ist wichtig, ingenieurmäßiger

01:06:59.330 --> 01:07:03.950
Entwurf, sicherer Entwurf, dadurch, dass ich eine klare, formale

01:07:03.950 --> 01:07:07.630
Darstellung habe, Spezifikation eines Problems, die Matrix

01:07:07.630 --> 01:07:08.330
-Multiplikation.

01:07:09.390 --> 01:07:11.390
Viele andere Beispiele dafür sind möglich.

01:07:12.450 --> 01:07:15.550
Und dann einfach eine mathematische Transformation dieser

01:07:15.550 --> 01:07:20.970
Problemstellung, aus der dann automatisch ein richtiger, paralleler

01:07:20.970 --> 01:07:21.990
Algorithmus rauskommt.

01:07:22.770 --> 01:07:27.310
Das ist also ein Ansatz, der ganz wichtig ist, der zukünftig noch

01:07:27.310 --> 01:07:29.710
stärker entwickelt werden wird, im Zusammenhang mit den Multi- und

01:07:29.710 --> 01:07:30.650
Many -Core-Anwendungen.

01:07:31.850 --> 01:07:34.750
Dann die üblichen Verfahren, wie divide und conquer, das kennen Sie

01:07:34.750 --> 01:07:35.010
alles.

01:07:35.210 --> 01:07:36.630
Cycline -Verfahren habe ich vorgestellt.

01:07:36.870 --> 01:07:37.650
Was ist hier noch?

01:07:37.810 --> 01:07:39.010
Achso, das habe ich hier gar nicht aufgeführt.

01:07:39.890 --> 01:07:43.230
Ich habe Ihnen halt die verschiedenen parallelen Strukturen

01:07:43.230 --> 01:07:46.630
vorgestellt und das waren also einige dieser Prinzipien.

01:07:46.630 --> 01:07:50.390
Ich denke, das haben Sie zur Genüge gemerkt, dass mir diese Prinzipien

01:07:50.390 --> 01:07:51.190
das Wesentliche sind.

01:07:51.750 --> 01:07:55.990
Und die einzelnen Verfahren dann auch wichtig, aber mehr Vehikel, um

01:07:55.990 --> 01:07:59.210
diese algorithmischen Entwurfsprinzipien kennenzulernen.

01:07:59.790 --> 01:08:02.290
Lassen Sie mich ganz kurz nochmal aufs Institut eingehen.

01:08:03.050 --> 01:08:04.430
Was können Sie hier noch alles machen?

01:08:04.610 --> 01:08:06.910
Also insbesondere in meiner Gruppe.

01:08:08.550 --> 01:08:10.470
In den anderen Gruppen am Institut natürlich auch.

01:08:11.110 --> 01:08:14.390
Also bei Herrn Oberweis, ein bisschen noch bei Herrn Stucki, der ist

01:08:14.390 --> 01:08:17.110
ja schon ein paar Semester emeritiert.

01:08:17.590 --> 01:08:20.030
Hier betriebliche Informations-Kommunikationssysteme, wissensbasierte

01:08:20.030 --> 01:08:21.610
Systeme.

01:08:22.310 --> 01:08:26.710
Das Thema Ökonomie und Technologie der E-Organisation kann man kürzer

01:08:26.710 --> 01:08:28.730
fassen, wenn man sich Anrufe zur Teilen macht.

01:08:29.090 --> 01:08:30.390
Service-Oriented Computing.

01:08:30.970 --> 01:08:32.250
Das ist das, was er im Wesentlichen macht.

01:08:32.650 --> 01:08:33.690
Komplexitätsmanagement bei Herrn Seese.

01:08:34.250 --> 01:08:36.850
Und bei mir gibt es halt eine Reihe Vorlesungen, die Sie machen

01:08:36.850 --> 01:08:37.210
können.

01:08:37.610 --> 01:08:38.610
Diese haben Sie gerade gehört.

01:08:39.150 --> 01:08:41.350
Organic Computing, sind einige von Ihnen auch schon drin.

01:08:42.090 --> 01:08:43.210
Oder drin gewesen.

01:08:43.350 --> 01:08:44.130
Oder wollen das noch machen.

01:08:44.630 --> 01:08:48.570
Diese Vorlesung hier, Ergolds von Internet-Applications, ist auch eine

01:08:48.570 --> 01:08:50.630
Vorlesung aus meinem Standardprogramm.

01:08:50.890 --> 01:08:54.290
Die werde ich im Wintersemester etwas umbauen in Richtung mehr

01:08:54.290 --> 01:08:55.510
Energieanwendungen.

01:08:55.850 --> 01:08:59.530
Weil das heutzutage so Sachen gibt wie Internet

01:09:04.890 --> 01:09:05.430
of...

01:09:05.430 --> 01:09:06.290
Nee, nicht of Data.

01:09:06.550 --> 01:09:08.010
Of Data ist das Normale.

01:09:08.490 --> 01:09:09.490
Das ist das Normale.

01:09:09.570 --> 01:09:13.830
Dann gibt es etwas Internet of Things und Internet of Energy.

01:09:15.910 --> 01:09:18.170
Also das sind so die Sachen, die man sich auch noch anguckt.

01:09:18.290 --> 01:09:21.490
Und dieses Internet of Things und Internet of Energy, das sind Themen,

01:09:21.610 --> 01:09:24.250
die ich dort in der Vorlesung im Wintersemester auch noch mit einbauen

01:09:24.250 --> 01:09:27.130
werde und dafür ein paar andere Sachen etwas reduzieren werde vom

01:09:27.130 --> 01:09:27.370
Umfang.

01:09:27.990 --> 01:09:31.050
Dann gibt es eine Vorlesung Natur-inspirierte Optimierungsverfahren.

01:09:31.830 --> 01:09:35.930
Das macht Herr Schukla zusammen mit Frau Mostagim, wo es um eben

01:09:37.670 --> 01:09:41.390
Meteoristiken geht, für die Lösung von schwierigen Problemen, im

01:09:41.390 --> 01:09:43.710
Wesentlichen von empfehlvollständigen Problemen.

01:09:44.570 --> 01:09:47.170
Und da sind eben die üblichen Verfahren, die genetischen und

01:09:47.170 --> 01:09:49.590
evolutionären Algorithmen oder auch Ameisenalgorithmen oder

01:09:49.590 --> 01:09:54.150
Schwarmalgorithmen, also Schwarmintelligenz, also Particle Swarm

01:09:54.150 --> 01:09:56.650
Optimization und ähnliche Dinge.

01:09:57.910 --> 01:10:02.150
Und dann eine Vorlesung Computational Economics.

01:10:02.750 --> 01:10:06.070
Eine Vorlesung, die gemeinsam gemacht wird mit einem, also von Herrn

01:10:06.070 --> 01:10:09.070
Schukla zusammen mit Herrn Katen vom Lehrstuhl Weinhardt.

01:10:09.150 --> 01:10:13.050
Das heißt, diese Vorlesung kann sowohl als BWL-Vorlesung oder als

01:10:13.050 --> 01:10:15.370
Informatik -Vorlesung angerechnet werden.

01:10:15.790 --> 01:10:18.970
Man muss allerdings dafür entscheiden, was man machen will und bekommt

01:10:18.970 --> 01:10:21.650
dann am Ende auch unterschiedliche Klausuren, die also vom Schwerpunkt

01:10:21.650 --> 01:10:22.610
her ein bisschen unterschiedlich sind.

01:10:23.050 --> 01:10:25.790
Wenn man es als Informatik-Vorlesung haben möchte, mehr Informatik

01:10:25.790 --> 01:10:26.190
-lastig.

01:10:26.790 --> 01:10:29.590
Wenn man es als BWL-Vorlesung macht, mehr BWL-lastig.

01:10:29.650 --> 01:10:33.310
Da geht es halt um Agentensysteme und Simulationsverfahren für

01:10:33.310 --> 01:10:34.290
ökonomische Probleme.

01:10:35.490 --> 01:10:37.590
Das ist die Lehre, was Vorlesungen angeht.

01:10:37.650 --> 01:10:38.910
Dann haben wir noch eine Reihe Seminare.

01:10:39.830 --> 01:10:44.890
Aktuell ein Thema, das ist jetzt hier für das nächste Wintersemester,

01:10:44.990 --> 01:10:46.630
Verlässlichkeit im Energiesystem der Zukunft.

01:10:47.450 --> 01:10:51.190
In zwei Stunden ist die Vorbesprechung, da können Sie hingehen und

01:10:51.190 --> 01:10:57.790
sich das angucken, was wir dort für Vortragsthemen haben.

01:10:58.490 --> 01:11:01.910
Dann gab es dieses Semester ein Seminar über Special Topics in

01:11:01.910 --> 01:11:03.110
Autonomic Organic Computing.

01:11:04.750 --> 01:11:08.310
Also die Seminare sind immer ausgerichtet an so aktuellen

01:11:08.310 --> 01:11:11.570
Forschungsthemen bei uns und dann haben wir noch so etwas, was wir

01:11:11.570 --> 01:11:12.730
Seminarpraktika nennen.

01:11:13.350 --> 01:11:16.350
Die können also sowohl als Praktikum oder auch als Seminar angerechnet

01:11:16.350 --> 01:11:16.690
werden.

01:11:16.750 --> 01:11:17.930
Das machen wir da ein bisschen flexibel.

01:11:18.710 --> 01:11:21.510
Da gibt es ein inzwischen schon Standardpraktikum Realisierung

01:11:21.510 --> 01:11:24.970
innovativer Dienste für Studierende, wo weitere Dienste für das

01:11:24.970 --> 01:11:26.190
Studierendenportal entwickelt werden.

01:11:26.190 --> 01:11:29.530
Dann diese YouSubscribe und Seminaranmeldung und so verschiedenste

01:11:29.530 --> 01:11:33.130
Sachen sind da entwickelt worden, entstanden aus dem KIM-Projekt.

01:11:33.850 --> 01:11:38.590
Organic Computing Learning Robots, das gibt es also auch jetzt auf ein

01:11:38.590 --> 01:11:44.510
paar Semester mit unseren Befahren für Schwarmroboter.

01:11:44.810 --> 01:11:47.850
Revolutionäre Robotik, kann man sich auch mit beschäftigen.

01:11:48.070 --> 01:11:50.270
Energiemanagement in Smart Homes hatten wir dieses Semester.

01:11:51.090 --> 01:11:53.330
Auch das hängt also zusammen mit dem, was wir hier in unseren

01:11:53.330 --> 01:11:58.210
Energieprojekten machen, um zu sehen, wie man dort sinnvoll Informatik

01:11:58.210 --> 01:11:58.930
einsetzen kann.

01:11:59.630 --> 01:12:02.930
Also das sind die aktuellen Seminarthemen, die immer ausgerichtet sind

01:12:02.930 --> 01:12:04.510
an aktuellen Forschungsthemen in der Gruppe.

01:12:05.470 --> 01:12:06.550
Was habe ich hier noch mit drauf?

01:12:07.090 --> 01:12:10.590
Abschlussarbeiten, Bachelor, Master, Diplom zu allen Themen in der

01:12:10.590 --> 01:12:10.870
Gruppe.

01:12:11.530 --> 01:12:14.570
Ein wesentlicher Bereich ist Organic Computing, aber natürlich auch

01:12:14.570 --> 01:12:17.870
effiziente Algorithmen, Parallelalgorithmen, Grid Computing,

01:12:19.430 --> 01:12:24.930
Verkehrssteuerung mit normalerweise Methoden des Organic Computing.

01:12:25.450 --> 01:12:30.950
E-Energy, E-Mobility, wichtige Themen, also effiziente Energiesysteme,

01:12:32.290 --> 01:12:35.210
Elektromobilität, da haben wir jetzt gerade wieder ein neues, großes

01:12:35.210 --> 01:12:35.890
Projekt bekommen.

01:12:36.950 --> 01:12:41.610
Und das, was wir zum Teil auch machen, sind Themen in Kooperation mit

01:12:41.610 --> 01:12:46.330
der Industrie, häufig angestoßen durch Studierende, die ein Praktikum

01:12:46.330 --> 01:12:50.450
gemacht haben und da auf ein Thema gestoßen sind, manchmal auch von

01:12:50.450 --> 01:12:51.610
uns ausgeschrieben.

01:12:53.250 --> 01:12:57.050
Und das geht natürlich auch dann zum Beispiel im FZI, da bin ich auch

01:12:57.050 --> 01:13:00.510
mit aktiv, kann also im Forschungszentrum Informatik auch Arbeiten

01:13:00.510 --> 01:13:02.810
schreiben, die dann stärker mit der Industrie zusammen sind.

01:13:03.390 --> 01:13:05.010
Kann das aber auch bei mir direkt am Lehrstuhl machen.

01:13:05.910 --> 01:13:10.830
Alle Studenten, die eine Abschlussarbeit machen, egal ob sie jetzt

01:13:10.830 --> 01:13:13.310
Bachelor, Master oder Diplom-Studenten sind, kommen bei uns ins

01:13:13.310 --> 01:13:14.210
Diplomanden -Seminar.

01:13:14.710 --> 01:13:16.250
Den Begriff werden wir auch aufrechterhalten.

01:13:16.250 --> 01:13:19.110
Auch die Bachelor und Master sind im Prinzip Diplomanden.

01:13:20.010 --> 01:13:21.910
Den Begriff wollen wir nicht aufgeben.

01:13:22.630 --> 01:13:26.770
Es wäre doof zu sagen, das ist jetzt ein Abschlussarbeiter-Seminar.

01:13:27.190 --> 01:13:28.010
Wie hört sich das an?

01:13:28.590 --> 01:13:29.430
Ja, das wäre nicht gut.

01:13:30.130 --> 01:13:34.430
Und ich würde Ihnen immer raten, sich frühzeitig um Abschlussarbeiten

01:13:34.430 --> 01:13:39.110
zu kümmern, weil Sie sich mit den Themen dann intensiver beschäftigen

01:13:39.110 --> 01:13:42.910
können und Sie können das relativ früh, macht gut im Bachelor-Bereich,

01:13:42.910 --> 01:13:45.650
macht das keinen Sinn, vor dem fünften Semester eine Bachelor-Arbeit

01:13:45.650 --> 01:13:46.130
zu schreiben.

01:13:46.730 --> 01:13:49.170
Aber man sollte damit nicht zu lange warten, nicht erst sechs Semester

01:13:49.170 --> 01:13:51.430
studieren und sagen, wo kann ich jetzt eine Arbeit machen?

01:13:51.830 --> 01:13:53.790
Das sollte man frühzeitig gemacht haben.

01:13:53.970 --> 01:13:56.970
Genauso im Masterstudium kann man im Prinzip gleich zu Anfang

01:13:56.970 --> 01:13:59.790
überlegen, wo will ich eigentlich meine Masterarbeit machen und dann

01:13:59.790 --> 01:14:03.350
kann man sich entsprechend auch im weiteren Verlauf des Masterstudiums

01:14:03.350 --> 01:14:06.970
darauf ausrichten, dass man sagt, entweder ich will intensiv jetzt

01:14:06.970 --> 01:14:09.970
genau etwas machen, was zu dem Masterarbeitsthema passt, oder ich

01:14:09.970 --> 01:14:13.650
mache ganz bewusst etwas, was das noch anderweitig ergänzt, dass man

01:14:13.650 --> 01:14:14.790
dann so ein breiteres Spektrum hat.

01:14:15.070 --> 01:14:17.770
Das muss man sich selber überlegen, aber man sollte sich frühzeitig

01:14:17.770 --> 01:14:18.350
darum kümmern.

01:14:20.010 --> 01:14:22.930
Und dann kann ich nur noch sagen, dass ich hoffe, dass Sie hier

01:14:22.930 --> 01:14:26.190
einiges gelernt haben, dass es Ihnen Spaß gemacht hat.

01:14:26.630 --> 01:14:29.210
Mir machen Vorlesungen immer Spaß, ich hoffe, das merken Sie, dass ich

01:14:29.210 --> 01:14:31.910
gerne Vorlesungen halte, dass es mir ein Anliegen ist, etwas

01:14:31.910 --> 01:14:32.650
rüberzubringen.

01:14:32.930 --> 01:14:36.510
Was ich manchmal vergesse, das ist leider auch dumm, ich sage zwar,

01:14:36.630 --> 01:14:39.750
Rückmeldungen sind mir immer willkommen, aber ich bin häufig in der

01:14:39.750 --> 01:14:42.670
Vorlesung so in Fahrt, dass ich gar nicht Ihnen Gelegenheit gebe,

01:14:42.790 --> 01:14:43.490
Fragen zu stellen.

01:14:44.210 --> 01:14:48.650
Und das ist ein Punkt, da müssen Sie einfach, machen Sie hier in einer

01:14:48.650 --> 01:14:52.350
relativ kleinen Anwesenheit, machen Sie das ja auch, aber das ist

01:14:52.350 --> 01:14:54.090
wirklich wichtig, auch ins Gespräch zu kommen.

01:14:54.670 --> 01:15:01.910
Eigentlich sind die Zeiten, wo man etwas macht wie eine Vorlesung, ja,

01:15:02.710 --> 01:15:06.830
das ist etwas völlig anachronistisches, das kommt aus Zeiten, wo man,

01:15:07.970 --> 01:15:11.470
wo das Wissen aufgeschrieben war, und das aufgeschriebene Wissen war

01:15:11.470 --> 01:15:12.470
nur wenigen verfügbar.

01:15:13.570 --> 01:15:17.810
Die hatten da den Zugriff auf die ganzen großen Bücher und haben den

01:15:17.810 --> 01:15:18.950
Studenten das vorgelesen.

01:15:19.850 --> 01:15:21.030
Die hatten keinen Zugriff darauf.

01:15:21.290 --> 01:15:24.470
Die hatten keine Möglichkeit, das aufgeschriebene Wissen irgendwie

01:15:24.470 --> 01:15:26.210
sich selbst anzugucken.

01:15:26.930 --> 01:15:28.370
Heutzutage ist alles verfügbar.

01:15:29.130 --> 01:15:32.530
Sie können sich alles, was an Wissen aufgeschrieben ist, können Sie

01:15:32.530 --> 01:15:33.290
aus dem Netz holen.

01:15:33.690 --> 01:15:34.490
Sie können sich alles angucken.

01:15:35.350 --> 01:15:37.670
Ich muss Ihnen nichts mehr vorlesen.

01:15:38.330 --> 01:15:40.930
Und deswegen müsste man eigentlich etwas völlig anderes machen.

01:15:41.250 --> 01:15:43.810
Ich erzähle Ihnen die ganze Zeit etwas, eigentlich müsste ich sagen,

01:15:44.290 --> 01:15:47.070
nächstes Mal machen wir den und den Teil und dann reden wir anderthalb

01:15:47.070 --> 01:15:49.770
Stunden darüber, was Sie sich vordurchgelesen haben.

01:15:50.710 --> 01:15:51.830
Und diskutieren drüber.

01:15:51.910 --> 01:15:56.030
Das wäre mehr so insgesamt etwas, was ein Tutorial oder Übung oder

01:15:56.030 --> 01:15:57.290
interaktive Übung wäre.

01:15:58.310 --> 01:16:01.510
Nur, das würde bedeuten, Sie müssen erstmal zu Hause etwas durchlesen

01:16:01.510 --> 01:16:04.710
und dann hier noch die Zeit etwas diskutieren, dann noch Aufgaben

01:16:04.710 --> 01:16:05.170
bearbeiten.

01:16:05.270 --> 01:16:07.030
Das heißt, der Aufwand wird eigentlich fast größer.

01:16:07.610 --> 01:16:14.390
Trotzdem, ich halte gerne Vorlesungen, aber ich denke, es kommt in

01:16:14.390 --> 01:16:18.050
Vorlesungen nicht mehr so sehr darauf an, dass man sehr viel Stoff

01:16:18.050 --> 01:16:18.530
schafft.

01:16:19.690 --> 01:16:23.410
Sondern es kommt darauf an, dass man Methodik vermittelt, dass man

01:16:23.410 --> 01:16:28.390
Zugänge vermittelt dazu, wie man den Stoff oder wie man den Zugang

01:16:28.390 --> 01:16:32.290
kriegt zu dem so weit verteilt verfügbaren Wissen.

01:16:32.830 --> 01:16:35.890
Wenn man das hinkriegt, wenn man Prinzipien vermittelt und sagt, wenn

01:16:35.890 --> 01:16:40.390
man diese Sachen gelernt hat, dann kann man eigentlich sinnvoll sich

01:16:40.390 --> 01:16:41.450
weitere Dinge erarbeiten.

01:16:41.890 --> 01:16:45.090
Dann denke ich, hätten wir etwas Gutes erreicht und die richtigen

01:16:45.090 --> 01:16:47.890
Methoden dafür, da sind wir alle am Schwimmen.

01:16:48.010 --> 01:16:53.270
Was mich manchmal etwas wundert, ist, dass die Offenheit von jungen

01:16:53.270 --> 01:16:56.730
Kolleginnen und Kollegen, die in den neuen Lehrkörper eintreten, für

01:16:56.730 --> 01:17:01.830
andere Lehransätze als die klassische Vorlesung, dass die Offenheit

01:17:01.830 --> 01:17:03.250
oft überhaupt nicht da ist.

01:17:04.750 --> 01:17:08.870
Und das ist etwas Erstaunliches, dass gerade, wenn ich so sehe,

01:17:08.950 --> 01:17:11.610
Berufungsvorträge oder Ähnliches, wenn man dann fragt, was haben sie

01:17:11.610 --> 01:17:15.050
für Lehrkonzepte, dass die gar nicht wissen, worum es geht.

01:17:16.230 --> 01:17:19.630
Dass man auch andere Lehrkonzepte machen kann als nur eine Vorlesung,

01:17:20.290 --> 01:17:24.590
dass es da verschiedenste Ideen gibt, ist anscheinend einigen nicht

01:17:24.590 --> 01:17:25.030
bekannt.

01:17:25.610 --> 01:17:30.510
Liegt auch daran, dass der Weg zum Hochschullehrer ist sehr schwer,

01:17:30.690 --> 01:17:33.630
mit viel Arbeit geflastert, da hat man keine Zeit, sich so viel um die

01:17:33.630 --> 01:17:34.290
Lehre zu kümmern.

01:17:35.250 --> 01:17:37.630
Aber es ist ein wichtiger Punkt.

01:17:38.810 --> 01:17:40.570
Und das war eine Vorlesung.

01:17:41.690 --> 01:17:44.910
Und ich hoffe, dass Sie da trotzdem, obwohl es nicht perfekt war in

01:17:44.910 --> 01:17:48.870
allen Richtungen, laut Lehrqualitätsindex war es 100%, also beim

01:17:48.870 --> 01:17:52.550
Wasperfekt, ja, ich wünsche Ihnen viel Erfolg in der Klausur.

01:17:52.930 --> 01:17:54.790
Wenn Sie noch Fragen haben, können Sie mich gerne stellen.

01:17:55.630 --> 01:17:56.810
Und das war es von meiner Seite.

01:17:56.970 --> 01:17:57.650
Vielen Dank.

01:17:59.250 --> 01:17:59.610
Applaus

01:18:02.730 --> 01:18:04.470
Ja, haben Sie noch Fragen?

01:18:06.210 --> 01:18:06.570
Nicht?

01:18:07.370 --> 01:18:08.430
Gut, dann mach ich mal.