WEBVTT 00:04.070 --> 00:05.580 Also, schönen guten Tag. 00:06.700 --> 00:12.320 Ich begrüße Sie zur letzten Vorlesungsstunde über effiziente 00:12.320 --> 00:15.000 Algorithmen in diesem Sommersemester. 00:18.080 --> 00:21.260 Ganz kurz, wie beim letzten Mal auch schon, noch ein Hinweis zu 00:21.260 --> 00:22.080 organisatorischen Dingen. 00:22.220 --> 00:26.140 Die Einladung zu den mündlichen Prüfungen ist noch nicht rausgegangen. 00:27.340 --> 00:30.060 Die mündlichen Prüfungen werden aber nächste in einer Woche 00:30.060 --> 00:30.700 stattfinden. 00:30.700 --> 00:36.960 Ich werde die Einladung noch dafür sorgen, dass die möglichst heute 00:36.960 --> 00:38.100 noch rausgehen oder morgen. 00:38.660 --> 00:41.760 Ich habe leider nicht von allen die E-Mail-Adressen, deswegen muss das 00:41.760 --> 00:43.120 schriftlich erfolgen. 00:43.760 --> 00:49.120 Es werden also alle Prüfungen am 3.8. 00:49.580 --> 00:51.120 stattfinden, Donnerstag. 00:53.340 --> 00:58.260 Einer oder zwei hatten gebeten um eine Prüfung im September. 00:58.960 --> 01:00.340 Da habe ich den 22. 01:00.640 --> 01:02.880 September als Termin ausgeguckt. 01:03.100 --> 01:05.740 Andere Termine sind Ende September bei mir nicht möglich. 01:07.340 --> 01:12.800 Und dieser Termin wird demnächst dann mitgeteilt. 01:13.800 --> 01:17.300 Also wer dann am 3.8. 01:17.480 --> 01:21.040 den Termin nicht wahrnehmen kann, sollte sich auf jeden Fall sehr 01:21.040 --> 01:26.460 schnell abmelden und bekommt dann einen weiteren Termin im September 01:26.460 --> 01:27.840 mitgeteilt. 01:28.500 --> 01:36.400 Gut, wir sind jetzt bei dem Kapitel Algorithmische Geometrie. 01:36.580 --> 01:38.520 Ich habe einiges dazu bereits erzählt. 01:38.520 --> 01:42.120 Wir hatten diese verschiedenen geometrischen Objekte ja zunächst 01:42.120 --> 01:42.760 betrachtet. 01:42.980 --> 01:44.720 Mit Punkten haben wir uns beschäftigt. 01:45.420 --> 01:50.940 Mit Linien, Schnittproblemen und haben also Polygone betrachtet. 01:51.340 --> 01:52.620 Gehen wir nochmal kurz da durch. 01:52.740 --> 01:56.720 Das war das Problem festzustellen, wie viele Punkte innerhalb eines 01:56.720 --> 01:58.100 beliebigen Rechtecks liegen. 01:58.640 --> 02:01.440 Innerhalb so einer Ebene, in der Punkte irgendwie verstreut sind. 02:01.940 --> 02:06.760 Ein Problem, wo man sich leicht die praktische Anwendung vorstellen 02:06.760 --> 02:07.140 kann. 02:07.140 --> 02:10.300 Dass man irgendein Fenster auf einem Bereich hat. 02:10.380 --> 02:13.580 Und man muss sehen, welche Objekte liegen eigentlich in diesem 02:13.580 --> 02:17.320 Fenster, das die Sichtbarkeit gerade charakterisiert. 02:18.180 --> 02:20.240 Und wir hatten dann gesehen, wie man das durch gewissen 02:20.240 --> 02:24.340 Vorbereitungsaufwand deutlich beschleunigen kann. 02:24.420 --> 02:24.560 Bzw. 02:24.700 --> 02:27.560 wie man die einzelnen Anfragen, wie viele Punkte jetzt in so einem 02:27.560 --> 02:29.700 Rechteck liegen, deutlich beschleunigen kann. 02:29.920 --> 02:32.600 Das kostet allerdings erhebliche Vorbereitungszeit. 02:32.600 --> 02:35.680 Nur wenn man viele solche Punktanfragen hat, ist das durchaus 02:35.680 --> 02:36.400 vorteilhaft. 02:37.680 --> 02:44.500 Das zweite war dann die Frage, bezogen auf Polygone, und zwar einfache 02:44.500 --> 02:48.040 Polygone, ob ein Punkt innerhalb oder außerhalb so eines Polygons 02:48.040 --> 02:48.360 liegt. 02:48.620 --> 02:53.800 Was nicht immer so einfach ist, selbst wenn das Polygon einfach ist. 02:53.980 --> 02:58.500 Aber ein einfaches Polygon muss ja keineswegs so einfache geometrische 02:58.500 --> 03:01.880 Formen haben, wie das hier ja auch gut zu sehen ist. 03:02.560 --> 03:06.580 Wir hatten gerade gesehen, dass man mit der Strahlmethode hier das 03:06.580 --> 03:07.800 entscheiden kann. 03:08.280 --> 03:13.300 Allerdings muss man halt feststellen, mit welchen Kanten sich ein 03:13.300 --> 03:14.500 solcher Strahl schneidet. 03:14.740 --> 03:18.000 Und das kostet halt einen linearen Aufwand in der Anzahl der Kanten. 03:18.900 --> 03:21.080 Für konvexe Polygone war das dann einfacher. 03:21.340 --> 03:25.280 Da konnten wir Sektoren bestimmen, in denen wir nur entscheiden 03:25.280 --> 03:28.880 müssen, ob der Punkt innerhalb oder außerhalb so eines Vektors liegt. 03:29.380 --> 03:33.140 Und das war dann wieder mit Log-In-Aufwand zu machen. 03:33.280 --> 03:37.980 Also diese einzelne Anfrage, auch das Feststellen, in welchem Sektor 03:37.980 --> 03:42.440 dieser Punkt liegt, das ist mit Log-In-Aufwand zu machen. 03:42.560 --> 03:45.680 Und die Entscheidung, ob links oder rechts von der Kante, ist halt mit 03:45.680 --> 03:46.880 konstantem Aufwand zu machen. 03:48.580 --> 03:51.440 Dieses Überprüfen, ob ein Punkt links oder rechts von einer Kante 03:51.440 --> 03:57.320 liegt, ging halt mit der Determinanten von den drei beteiligten 03:57.320 --> 03:57.880 Punkten. 03:59.100 --> 04:00.700 Aufgefüllt mit einer Eins-Spalte. 04:01.740 --> 04:04.980 Und damit hatten wir entweder positives oder negatives Vorzeichen. 04:05.300 --> 04:08.380 Der Wert ist eigentlich gar nicht so wichtig, wesentlich kommt es 04:08.380 --> 04:11.300 darauf an, ob wir einen positiven oder negativen Wert haben. 04:11.400 --> 04:13.360 Sobald man das festgestellt hat, ist man eigentlich fertig. 04:14.620 --> 04:19.320 Und deswegen ist das eine sehr effiziente Art, diese Bestimmung zu 04:19.320 --> 04:19.540 machen. 04:19.760 --> 04:23.380 Insbesondere ohne jeden Rückgriff auf trigonometrische Funktionen. 04:23.380 --> 04:26.620 Was man zunächst, wenn man an Geometrie denkt, eigentlich immer 04:26.620 --> 04:29.080 vermutet, dass man die brauchen würde. 04:29.920 --> 04:35.080 Wir hatten dann uns überlegt, wie kann ich feststellen, ob ein Polygon 04:35.080 --> 04:35.960 einfach ist. 04:37.440 --> 04:39.460 Dazu muss ich halt wissen, ob sich Kanten überschneiden. 04:39.540 --> 04:41.760 Das hatten wir mit dem Plane-Sweep gemacht, das war eine weitere 04:41.760 --> 04:42.300 Methode. 04:43.060 --> 04:45.600 Entschuldigung, da ist ein anderes Programm dazwischen geraten. 04:47.580 --> 04:49.600 Wir hatten festgestellt... 04:57.690 --> 04:58.170 So, 05:01.230 --> 05:02.090 jetzt geht's weiter. 05:02.790 --> 05:03.810 Also das war das Polygon. 05:04.370 --> 05:06.710 Wir hatten hier den... ich war ja noch gar nicht im 05:06.710 --> 05:07.790 Präsentationsmodus, richtig. 05:09.410 --> 05:10.690 Also, machen wir hier weiter. 05:11.330 --> 05:15.290 Der Plane-Sweep, eine weitere Methode, algorithmische Methode, um ein 05:15.290 --> 05:19.610 Problem, das hier ein zweidimensionales Problem ist, zu reduzieren auf 05:19.610 --> 05:20.890 ein eindimensionales Problem. 05:21.170 --> 05:24.750 Diese Methode kann man genauso anwenden, um ein d-dimensionales 05:24.750 --> 05:29.190 Problem auf ein d-1-dimensionales Problem zu reduzieren, was durchaus 05:29.190 --> 05:32.610 zu effizienteren Verfahren führen kann. 05:33.530 --> 05:41.250 Und ich hatte das halt hier kurz erläutert, wobei ich auf die genaue 05:41.250 --> 05:44.890 Ausführung, die einzelnen Operationen an den Haltepunkten, gar nicht 05:44.890 --> 05:46.350 so explizit eingegangen war. 05:46.450 --> 05:50.310 Das Wesentliche ist, dass man das Überschneidungsproblem von Geraden 05:50.310 --> 05:53.730 oder von Liniensegmenten hier überträgt in ein 05:53.730 --> 05:56.210 Intervallschneideproblem. 05:56.810 --> 06:00.350 Und das ist halt ein Intervallschneideproblem auf einer Geraden, was 06:00.350 --> 06:03.690 deutlich einfacher zu lösen ist, insbesondere wenn man eine geeignete 06:03.690 --> 06:08.590 Datenstruktur hat, als das Problem festzustellen, welche Kanten sich 06:08.590 --> 06:09.210 überschneiden. 06:09.210 --> 06:12.690 Und der Aufwand war dann halt, hier nochmal Aufwandbehalt reduziert 06:12.690 --> 06:14.210 worden, dann auf NlogN. 06:14.850 --> 06:17.750 Im Wesentlichen der Aufwand, um die Haltepunkte in sortierte 06:17.750 --> 06:18.690 Reihenfolge zu bringen. 06:21.070 --> 06:25.750 Schließlich haben wir dann uns begonnen damit zu beschäftigen, wie man 06:25.750 --> 06:28.050 eine konvexe Hülle einer Punktmenge bestimmt. 06:28.170 --> 06:34.370 Ein Problem, das häufig auftritt, dass man die umhüllende Linie einer 06:34.370 --> 06:35.470 Punktmenge braucht. 06:36.150 --> 06:43.310 Und diese konvexe Hülle konnte man in verschiedener Art definieren. 06:43.510 --> 06:49.450 Als kleinste konvexe Teilmenge, die die Punkte alle enthält. 06:50.130 --> 06:56.650 Oder über das Polygon, das außenrum läuft und konvex ist. 06:57.830 --> 07:03.250 Dafür braucht man die Menge der Extrempunkte, die die Eckpunkte des 07:03.250 --> 07:04.930 Polygons bilden. 07:04.930 --> 07:08.850 Und ich hatte Ihnen hier einen Ansatz kurz vorgestellt, der sich sehr 07:08.850 --> 07:10.190 leicht parallelisieren ließ. 07:10.330 --> 07:14.310 Allerdings sehr viel Rechenoperationen braucht, weil wir nämlich hier 07:14.310 --> 07:18.490 überprüfen für jeden Punkt, ob er innerhalb eines Dreiecks aus 07:18.490 --> 07:20.910 beliebigen drei anderen Punkten liegt. 07:21.730 --> 07:25.750 Und die Punkte, die halt in keinem Dreieck liegen, sind genau die 07:25.750 --> 07:26.040 Extrempunkte. 07:26.040 --> 07:33.840 Dass das hier parallel sehr effizient zu machen ist, also parallel in 07:33.840 --> 07:35.700 kurzer Zeit, aber mit sehr viel Aufwand. 07:36.120 --> 07:38.920 Die Effizienz ist relativ niedrig, weil ich das vergleichen muss mit 07:38.920 --> 07:41.160 den besten, optimalen Verfahren. 07:41.280 --> 07:43.260 Und da werden wir sehen, es geht durchaus noch besser. 07:44.600 --> 07:47.560 Und es ist auf jeden Fall ein Ansatz, den man verwenden kann. 07:48.580 --> 07:51.140 Und es ist einfach interessant zu sehen, was es für geometrische 07:51.140 --> 07:54.100 Eigenschaften gibt, die man ausnutzen kann, um so ein Problem zu 07:54.100 --> 07:54.420 lösen. 07:54.420 --> 07:57.720 Das nächste Verfahren war das von Graham. 07:57.900 --> 08:07.240 Der Graham-Scan, der uns ein bisschen erinnert an diese Strahlmethode, 08:07.440 --> 08:10.540 um festzustellen, ob ein Punkt innerhalb oder außerhalb eines konvexen 08:10.540 --> 08:11.340 Polygons liegt. 08:12.100 --> 08:16.520 Hier werden zunächst einmal alle Punkte radial sortiert um einen 08:16.520 --> 08:19.760 beliebigen Punkt, der irgendwo eigentlich liegt. 08:19.760 --> 08:20.880 Es ist völlig egal, wo der liegt. 08:20.980 --> 08:24.920 Man nimmt normalerweise irgendeinen Punkt aus der Menge und sortiert 08:24.920 --> 08:27.500 alle anderen Punkte der Menge radial. 08:28.160 --> 08:32.140 Das Problem dabei ist allerdings, darauf hatte ich hingewiesen, wenn 08:32.140 --> 08:35.720 solche Punkte sehr nah zusammenliegen, was natürlich in diesem Fall, 08:36.000 --> 08:39.000 der hier oben angedeutet ist, natürlich dann immer auftreten kann, 08:39.480 --> 08:44.140 dann mag es aufgrund von Rechenungenauigkeiten schwierig sein, 08:44.960 --> 08:51.140 tatsächlich die radiale Sortierung durchzuführen. 08:51.140 --> 08:59.580 Es mag schwierig sein, exakt zu entscheiden, ob zwei Punkte links oder 08:59.580 --> 09:05.540 rechts voneinander liegen, weil einfach die Rechenungenauigkeit zu 09:05.540 --> 09:06.900 falschen Ergebnissen führen kann. 09:08.440 --> 09:10.460 Also das ist ein Problem bei diesem Graham-Scan. 09:10.600 --> 09:13.580 Wenn wir annehmen, dass diese Probleme nicht auftreten, dann können 09:13.580 --> 09:14.820 wir so vorgehen, wie es hier steht. 09:14.820 --> 09:22.120 Man geht einfach kreisförmig, wie es hier angedeutet war, durch alle 09:22.120 --> 09:25.200 diese Punkte hindurch und hat dann diese drei Situationen zu 09:25.200 --> 09:26.020 unterscheiden. 09:27.000 --> 09:31.800 Die erste Situation war so, dass man einen Konvexenwinkel im Prinzip 09:31.800 --> 09:37.400 gegangen ist, der darauf hindeutet, dass der Punkt P2 ein Extrempunkt 09:37.400 --> 09:37.660 ist. 09:37.660 --> 09:40.160 Man nimmt an, P1 ist auch ein Extrempunkt. 09:41.340 --> 09:44.280 Und dann macht man halt entsprechend anschließend weiter. 09:44.840 --> 09:48.780 Wenn man eine andere Situation hat, dass die drei auf einer Linie 09:48.780 --> 09:51.900 liegen, vergisst man den mittleren, also streicht den raus, das ist 09:51.900 --> 09:52.840 kein Extrempunkt. 09:53.540 --> 09:57.020 Und wenn man die Situation hat, wie sie hier unten angedeutet ist, 09:57.140 --> 10:02.720 dass wir einen konkaven Winkel haben, dann ist der Punkt P2 garantiert 10:02.720 --> 10:05.180 kein Extrempunkt und wird rausgestrichen. 10:05.180 --> 10:10.420 Und dann geht man halt zurück, betrachtet den Winkel P0, P1, P3 und 10:10.420 --> 10:15.260 hat dabei, wenn man Pech hat, wieder einen konkaven Winkel, sodass 10:15.260 --> 10:18.020 dieses Rausstreichen eventuell sich fortsetzen kann. 10:18.840 --> 10:23.060 Aber es ist klar, dass jeder Punkt nur einmal aufgenommen werden kann 10:23.060 --> 10:27.420 als potenzieller Extrempunkt und eventuell später einmal wieder 10:27.420 --> 10:28.360 gelöscht werden kann. 10:28.760 --> 10:30.440 Danach muss man ihn nie wieder besuchen. 10:34.120 --> 10:38.860 Die wesentliche Überlegung ist also, ob ich bei diesem Graham-Scan um 10:38.860 --> 10:47.000 diese Punkte außen herum einen konkaven oder konvexen Winkel finde, 10:47.520 --> 10:49.580 oder ich kann auch sagen, ob ich eine Linksdrehung oder eine 10:49.580 --> 10:54.340 Rechtsdrehung mache, wenn ich diese Punkte P1, P2, P3 betrachte, wobei 10:54.340 --> 10:57.900 das jeweils die aktuellen Punkte sind, die ich gerade anschauen muss. 10:57.900 --> 11:02.640 Der Aufwand ist halt NlogN, um die radiale Sortierung zu machen. 11:03.240 --> 11:05.980 Haben Sie da noch eine Frage zu gehabt? 11:10.720 --> 11:14.900 Ich muss ja die radiale Sortierung erst einmal machen, das bringt das 11:14.900 --> 11:17.760 NlogN, der Rest ist dann mit linearem Aufwand zu machen. 11:20.120 --> 11:27.040 Das war die letzte Folie vom vorigen Mal und jetzt machen wir mit 11:27.040 --> 11:27.960 dieser Folie weiter. 11:29.360 --> 11:34.680 Die Eigenschaft, die wir hier genutzt haben, ist die Eigenschaft, die 11:34.680 --> 11:39.400 hier oben noch einmal angedeutet ist, alle inneren Winkel zwischen 11:39.400 --> 11:44.480 aufeinanderfolgenden Kanten eines konvexen Polygons sind konvex, also 11:44.480 --> 11:45.940 kleiner als 180 Grad. 11:46.140 --> 11:50.080 Das ist halt gerade alles solche Winkel, wenn das hier das Innere ist 11:50.080 --> 11:52.680 und das hier das Äußere. 11:57.020 --> 12:04.500 Und auf diese Art und Weise kann man halt gerade die Extrempunkte 12:04.500 --> 12:04.800 finden. 12:05.640 --> 12:10.160 Ein anderer Ansatz ist, dass man nicht nach Extrempunkten sucht, 12:10.240 --> 12:10.880 sondern nach Kanten. 12:11.780 --> 12:14.860 Also jetzt haben wir versucht, sukzessive herauszufinden, welche der 12:14.860 --> 12:16.080 Punkte sind Extrempunkte. 12:16.440 --> 12:18.700 Dadurch, dass wir die Winkel betrachtet haben, gesehen haben, ob eine 12:18.700 --> 12:21.320 Linksdrehung oder eine Rechtsdrehung, konnten wir feststellen, ob ein 12:21.320 --> 12:25.280 Punkt, der gerade Kandidat ist, Extrempunkt zu sein, tatsächlich einer 12:25.280 --> 12:25.820 ist oder nicht. 12:26.920 --> 12:29.680 Was man natürlich auch machen kann, ist, man sucht von vornherein die 12:29.680 --> 12:36.160 Kanten, die garantiert in diesem umfließenden Polygon drin sind. 12:36.940 --> 12:39.820 Natürlich findet man implizit auch bei der anderen Methode die Kanten, 12:39.980 --> 12:42.460 aber man macht es hier schon anders. 12:43.140 --> 12:46.640 Also, die Eigenschaft, die wir jetzt ausnutzen, ist hier angedeutet. 12:48.860 --> 12:51.620 Und die sagt jetzt folgendes aus. 12:52.080 --> 12:57.800 Wenn wir eine Kante haben, unserer konvexen Hülle, also hier ist 12:57.800 --> 13:02.800 irgendeine Kante, so und wir haben hier irgendeine Kante. 13:04.040 --> 13:04.900 Was passiert dann? 13:05.000 --> 13:09.640 Dann liegen alle Punkte von M auf der gleichen Seite der Geraden durch 13:09.640 --> 13:11.900 P und Q oder auf PQ. 13:11.900 --> 13:16.980 Das sind die beiden Punkte P und Q, hier, da und da. 13:17.800 --> 13:23.220 Und wenn wir hier die Gerade betrachten, dann liegen alle Punkte also 13:23.220 --> 13:27.940 entweder auf der gleichen Seite der Geraden, nämlich alle in diesem 13:27.940 --> 13:31.760 Fall in diesem Bereich, oder halt auf der Geraden. 13:31.900 --> 13:34.200 Das waren genau die Punkte, die wir vorhin auch hatten. 13:34.300 --> 13:36.120 Wenn Punkte auf der Geraden liegen, dann wurden sie halt 13:36.120 --> 13:36.800 rausgestrichen. 13:37.680 --> 13:38.440 So. 13:39.740 --> 13:41.160 Das nutzen wir einfach aus. 13:41.800 --> 13:43.480 Wie kann ich denn so eine Kante finden? 13:43.980 --> 13:47.700 Ich nähe mich einfach, ich gehe von einem Punkt aus, lege da 13:47.700 --> 13:52.880 irgendeine Gerade rein und bewege diese Gerade nach links. 13:57.020 --> 14:06.100 Ich vergrößere praktisch diesen Winkel mit der X-Achse immer mehr, bis 14:06.100 --> 14:13.700 ich einen Punkt finde, Punkt Q, der auch in der Menge liegt. 14:14.100 --> 14:18.560 Sobald ich zwei Punkte habe, fange ich also mit dem Punkt Q an und 14:18.560 --> 14:22.140 schiebe einfach so eine Gerade darum. 14:22.140 --> 14:25.040 Im Prinzip ist das, was man mit einem Lineal machen würde. 14:26.520 --> 14:29.300 Und das ist etwas, was sich jetzt nicht GramScan nennt. 14:29.900 --> 14:31.660 GramScan hatte die Punkte ja radial sortiert. 14:32.140 --> 14:33.760 Das ist jetzt der Jarvis-Marge. 14:34.860 --> 14:37.740 Also einer Jarvis hat das herausgefunden oder hat sich diesen 14:37.740 --> 14:38.880 Algorithmus überlegt. 14:39.560 --> 14:41.940 Und das heißt, wir gehen jetzt so vor, dass wir einen Punkt wählen. 14:42.000 --> 14:43.420 Zum Beispiel diesen Punkt hier unten. 14:45.140 --> 14:55.380 Und dann sucht man einen Punkt Q dazu, sodass der Winkel dieser Linie 14:55.380 --> 14:59.900 oder der Geraden, die zwischen P und Q geht, mit der X-Achse minimal 14:59.900 --> 15:00.300 ist. 15:00.920 --> 15:02.900 Also hier ist es andersherum formuliert. 15:03.700 --> 15:08.160 Hier geht man durch alle Punkte durch und sucht sich denjenigen, 15:08.420 --> 15:09.200 der... 15:09.900 --> 15:16.140 Also ich habe hier alle möglichen Punkte drin und ich gehe praktisch 15:16.140 --> 15:23.040 immer weiter rüber, bis ich den Punkt habe, bei dem der Winkel zur X 15:23.040 --> 15:24.640 -Achse minimal ist. 15:26.720 --> 15:27.140 So. 15:27.820 --> 15:31.820 Und wenn das der Fall ist, dann habe ich ja gerade diese Gerade 15:31.820 --> 15:32.180 gefunden. 15:32.280 --> 15:36.180 Dann liegen alle anderen Punkte auf der linken Seite dieser Gerade. 15:37.920 --> 15:40.440 Und das ist im ersten Fall halt hier die horizontale. 15:40.500 --> 15:43.380 Das wäre dann diese Gerade. 15:43.480 --> 15:44.360 Das sollte eine Gerade sein. 15:46.660 --> 15:49.820 Und wenn ich halt diesen Punkt gefunden habe, mache ich das wieder so. 15:49.820 --> 15:53.140 Dann werde ich irgendwann diesen Punkt finden und komme zu dieser 15:53.140 --> 15:54.360 Kante. 15:55.860 --> 15:59.460 Anschließend finde ich diese Kante, dann finde ich die Kante, ich 15:59.460 --> 16:02.860 finde die Kante, die Kante und die Kante und bin fertig. 16:04.100 --> 16:10.260 Und das Interessante ist, dass ich pro Extrempunkt nur diese 16:10.260 --> 16:11.360 Vergleiche machen muss. 16:12.320 --> 16:17.800 Vorher habe ich bei dem Gram-Scan, musste ich durch alle Punkte 16:17.800 --> 16:20.240 durchgehen und jeweils gucken, ob ich eine Linksdrehung oder eine 16:20.240 --> 16:20.920 Rechtsdrehung habe. 16:22.000 --> 16:25.580 Hier fange ich bei einem sicheren Extrempunkt an, das ist der 16:25.580 --> 16:29.920 linkeste, unterste Punkt, und suche von dem aus den nächsten 16:29.920 --> 16:30.740 Extrempunkt. 16:30.740 --> 16:39.860 Der Aufwand pro Extrempunkt ist linear und das heißt, wie ist der 16:39.860 --> 16:40.880 Gesamtaufwand? 16:40.980 --> 16:43.580 Ich muss für jeden Extrempunkt, wenn wir annehmen, wir haben h 16:43.580 --> 16:48.420 Extrempunkte, muss ich linearen Aufwand betreiben. 16:49.060 --> 16:51.580 Je nachdem, wie viele Extrempunkte vorkommen, habe ich also einen 16:51.580 --> 16:55.820 Aufwand, der im besten Fall linear sein kann, im schlechtesten Fall 16:55.820 --> 16:57.100 ist er quadratisch. 16:57.100 --> 17:00.160 Wenn ich in Größenordnung N Extrempunkte habe. 17:00.220 --> 17:04.320 Aber wenn ich Glück habe, ist die Anzahl der Extrempunkte relativ 17:04.320 --> 17:04.780 niedrig. 17:05.640 --> 17:07.060 Und dann geht das Verfahren recht schnell. 17:08.600 --> 17:15.700 Das ist ein interessantes Verfahren, wobei wir hier das Problem, das 17:15.700 --> 17:21.660 wir vorher beschrieben haben, mit diesen Ungenauigkeiten, das tritt 17:21.660 --> 17:23.000 hier nicht ganz so stark auf. 17:23.460 --> 17:25.540 Wir müssen hier nur das Minimum bestimmen. 17:26.400 --> 17:27.980 Kann natürlich da auch passieren. 17:28.060 --> 17:32.540 Wenn wir hier jetzt Punkte haben, die sehr nah beieinander liegen, 17:32.660 --> 17:35.960 also ob ich hier jetzt irgendwelche kleinen Punkte habe, das kann sich 17:35.960 --> 17:37.860 auch noch verändern. 17:38.080 --> 17:39.960 Also insofern können die Probleme auch hier auftreten. 17:40.280 --> 17:43.620 Aber ich betrachte ja nur die Extrempunkte. 17:43.700 --> 17:45.640 Von denen aus gehe ich an die anderen ran. 17:48.600 --> 17:51.800 Ich habe das nicht untersucht, aber es wäre interessant, das 17:51.800 --> 17:58.000 algorithmisch zu untersuchen, wie anfällig die verschiedenen Verfahren 17:58.000 --> 18:05.260 zum Rechnen der konvexen Hülle sind, bezüglich der Ungenauigkeiten bei 18:05.260 --> 18:06.380 den Gleitpunktberechnungen. 18:07.620 --> 18:10.240 Also das ist ein Problem, das ist so noch nicht untersucht worden. 18:10.340 --> 18:13.800 Kann man sich mal angucken, wäre ein Thema für eine mögliche 18:13.800 --> 18:14.420 Diplomarbeit. 18:22.720 --> 18:26.160 Also diese Problematik mit den Ungenauigkeiten, die durch 18:26.160 --> 18:31.520 Gleitpunktoperationen auftreten, das wird zur Zeit angeguckt und ist 18:31.520 --> 18:33.900 aber hier in Bezug auf diese Fragestellung so noch nicht betrachtet 18:33.900 --> 18:34.260 worden. 18:35.820 --> 18:39.920 So, jetzt kommt, ich glaube das Verfahren ist klar gewesen, wie man 18:39.920 --> 18:40.300 das macht. 18:40.440 --> 18:41.860 Da brauche ich nicht weiter darauf einzugehen. 18:41.920 --> 18:43.820 Jetzt kommt das nächste Prinzip, die beiden Konker. 18:43.900 --> 18:45.000 Das haben wir uns immer angeguckt. 18:45.600 --> 18:49.220 Wie kann man mit Problemen umgehen? 18:49.880 --> 18:53.400 Wir sind gerade eben mehr so iterativ da durchgelaufen, haben uns 18:53.400 --> 18:55.340 sukzessive die einzelnen Punkte angeschaut. 18:55.980 --> 18:58.840 Jetzt machen wir das anders, so wie der Informatiker gerne vorgeht. 18:58.840 --> 19:01.160 Er hat ein großes Problem und sagt, das ist mir viel zu schwer. 19:01.680 --> 19:06.360 Ich teile es auf, mache daraus zwei oder mehr kleinere Probleme, die 19:06.360 --> 19:07.200 ich auch lösen kann. 19:08.180 --> 19:10.260 Und wenn sie mir immer noch zu schwer sind, teile ich es halt weiter 19:10.260 --> 19:10.480 auf. 19:10.600 --> 19:11.880 Also das ist die beiden Konker-Prinzip. 19:12.520 --> 19:18.220 Und jetzt ist einfach wie üblich die Idee, wenn ich ein genügend 19:18.220 --> 19:22.500 leichtes Problem habe, also die Menge, die Anzahl der Punkte ist 19:22.500 --> 19:26.480 kleiner gleich K, dann nehme ich irgendein Verfahren, um die komplexe 19:26.480 --> 19:27.360 Hülle zu konstruieren. 19:28.740 --> 19:35.200 Aber wenn es zu groß wird, dann mache ich daraus zwei Hälften und in 19:35.200 --> 19:38.180 irgendeiner Weise teile ich die Menge auf. 19:38.240 --> 19:39.480 Sie sehen, das ist hier angedeutet. 19:40.140 --> 19:42.380 Es wird also in etwa aufgeteilt. 19:42.460 --> 19:45.820 Sie sehen, dass es hier nicht genau gleichmäßig sein muss, aber so in 19:45.820 --> 19:47.900 etwa mittig wird das aufgeteilt. 19:49.340 --> 19:50.320 M1 und M2. 19:50.420 --> 19:53.940 Hätten wir also hier die Menge M1, da hätten wir die Menge M2. 19:54.620 --> 19:59.420 Und das Problem ist, also ich mache es rekursiv weiter, da kann ich 19:59.420 --> 20:03.040 natürlich jetzt rekursiv die konvexen Hüllen bestimmen. 20:03.500 --> 20:07.220 Dann habe ich die konvexen Hüllen von M1 und von M2. 20:08.200 --> 20:11.980 Und die Frage ist, wie baue ich denn daraus jetzt die gesamte konvexe 20:11.980 --> 20:12.200 Hülle? 20:12.200 --> 20:15.860 Also das Aufteilen ist einfach, das ist sicherlich mit linearem 20:15.860 --> 20:16.660 Aufwand zu machen. 20:17.900 --> 20:22.640 Ich muss ja nur festlegen für jeden Punkt, ob er in der Menge M1 oder 20:22.640 --> 20:23.340 M2 liegt. 20:24.120 --> 20:29.860 Und dann muss ich halt rekursiv weiterarbeiten und muss anschließend 20:29.860 --> 20:31.600 die beiden konvexen Hüllen verschmelzen. 20:31.960 --> 20:36.020 Im Prinzip ist das nicht Merge Sort, sondern ein Verschmelzen von 20:36.020 --> 20:36.760 konvexen Hüllen. 20:38.440 --> 20:41.160 Und da muss man sich angucken, wie groß der Aufwand ist dafür. 20:45.660 --> 20:50.260 Also wenn der Schritt für das Verschmelzen linear ist, was hier 20:50.260 --> 20:57.160 angenommen ist, also O von N, und wir müssen zweimal Aufwand für halbe 20:57.160 --> 21:00.000 Größe machen, wissen wir, kommen wir mit N log N hin. 21:01.220 --> 21:03.040 Das wäre natürlich ein gutes Ergebnis. 21:03.480 --> 21:04.820 N log N für die konvexe Hülle. 21:06.280 --> 21:09.580 Hier steht sogar, man kann das verbessern auf N log H, also nur die 21:09.580 --> 21:14.360 logarithmische Anzahl der Extrempunkte. 21:15.980 --> 21:17.760 Aber selbst N log N ist schon nicht schlecht. 21:18.760 --> 21:21.640 Wir hatten ja vorher Verfahren gehabt, das war der N hoch 4. 21:22.720 --> 21:24.620 Jarvis-March hatte bis N². 21:26.360 --> 21:32.180 Und auch der Gram-Scan lag bei N log N. 21:33.580 --> 21:37.940 Insofern, hier wäre es auch wieder N log N, aber ein völlig anderer 21:37.940 --> 21:38.440 Ansatz. 21:39.380 --> 21:42.020 Und auch hier könnte man sich überlegen, welche Rolle spielen hier 21:42.020 --> 21:43.020 wieder diese Ungenauigkeiten. 21:46.050 --> 21:47.630 So, wie macht man das? 21:48.490 --> 21:52.830 Wie konstruiert man eine konvexe, oder wie verschmilzt man zwei 21:52.830 --> 21:53.610 konvexe Hüllen? 21:57.280 --> 21:58.420 Da muss man sich mal überlegen. 21:58.940 --> 22:00.300 Wir haben zwei konvexe Hüllen. 22:01.200 --> 22:02.540 Hier sieht es so einfach aus. 22:02.600 --> 22:05.800 Ich brauche ja nur hier oben diese eine Linie zu malen und hier unten 22:05.800 --> 22:08.680 eine Kante rein zu zeichnen und ich bin fertig. 22:09.600 --> 22:11.140 Es kann natürlich auch ganz anders aussehen. 22:12.620 --> 22:15.840 Also ich werde immer irgendeine neue Kante da reinziehen müssen. 22:16.740 --> 22:21.580 Aber es ist halt immer die Frage, wie viele Kanten der konvexen Hüllen 22:21.580 --> 22:22.600 gehen dann verloren. 22:22.700 --> 22:24.300 Was sind eigentlich die neuen Extrempunkte? 22:28.500 --> 22:30.320 Und, ja, wie macht man das? 22:30.520 --> 22:32.400 Wir haben die beiden konvexen Hüllen gegeben. 22:33.280 --> 22:36.220 Das heißt, wir wissen, fängt meinetwegen hier irgendwie an. 22:37.820 --> 22:42.140 P1, P2, P3, P4 und so weiter. 22:42.360 --> 22:50.300 Und hier hätten wir meinetwegen Q1, na, hier unten wäre Q1, Q2, Q3, Q4 22:50.300 --> 22:50.860 und so weiter. 22:51.620 --> 22:53.820 Das heißt, wir haben schon mal zwei reine Folgen gegeben. 22:55.480 --> 22:59.140 Das heißt, wir hätten also zwei konvexe Hüllen. 22:59.200 --> 23:00.560 Da können wir erst mal Folgendes machen. 23:01.220 --> 23:04.420 Wir können die einfach voneinander trennen, die obere und die untere 23:04.420 --> 23:04.820 Hälfte. 23:05.880 --> 23:09.280 Und betrachten einfach erst mal nur den oberen Rand. 23:12.190 --> 23:17.330 Ich weiß ja, was ist der obere Rand der konvexen Hülle von M1, was ist 23:17.330 --> 23:19.270 der obere Rand der konvexen Hülle von M2. 23:20.210 --> 23:24.850 Das kann man leicht feststellen beim Durchlaufen, welche Punkte zum 23:24.850 --> 23:26.270 oberen Rand gehören. 23:28.990 --> 23:33.750 Ich sehe das einfach, wenn ich da durchlaufe, wie lange werden die x 23:33.750 --> 23:34.450 -Werte größer. 23:34.530 --> 23:37.810 Sobald sie kleiner werden, bin ich im unteren Rand angekommen. 23:38.810 --> 23:39.690 Das ist also einfach. 23:40.390 --> 23:44.850 Das ist kein Sortieraufwand, die sind bereits in dieser Reihenfolge 23:44.850 --> 23:45.130 gegeben. 23:45.190 --> 23:47.810 Ich muss nur einmal durchlaufen und habe festgestellt, wie die 23:47.810 --> 23:48.590 Reihenfolge ist. 23:49.350 --> 23:53.830 Dann habe ich also diese Punkte alle so angeordnet. 23:55.650 --> 23:58.570 Im Prinzip habe ich so eine Folge von x-Koordinaten. 23:59.230 --> 24:02.510 Und da liegen jetzt meine Punkte drauf. 24:07.240 --> 24:12.660 Das sind meinetwegen die y-Koordinaten zu diesen x-Koordinaten, die 24:12.660 --> 24:14.640 wir hier gerade festgestellt haben. 24:14.720 --> 24:17.960 Der beiden konvexen Hüllen, die jetzt verschmolzen werden sollen. 24:19.640 --> 24:20.440 Und was mache ich dann? 24:20.440 --> 24:28.100 Ich gehe einfach jetzt von links nach rechts in einer Reihenfolge 24:28.100 --> 24:35.220 dadurch und stelle fest, habe ich hier jeweils die richtigen Winkel. 24:36.220 --> 24:42.040 Ich mache im Prinzip einen Gram-Scan auf diesen beiden oberen Teilen 24:42.040 --> 24:42.800 der konvexen Hülle. 24:43.660 --> 24:50.560 Und sobald ich einen konkaven Winkel habe, kann ich den sofort 24:50.560 --> 24:51.120 streichen. 24:51.720 --> 24:54.780 Dann hätte ich wieder einen konkaven Winkel. 24:55.320 --> 24:57.680 Ich würde auch die Linie rausstreichen. 24:58.220 --> 25:00.820 Ich würde hier hingehen, hätte wieder einen konkaven Winkel. 25:01.800 --> 25:04.520 Würde hier hingehen, hätte wieder einen konkaven Winkel. 25:05.500 --> 25:08.840 Und würde dann hier die letzte Kante dazunehmen. 25:09.580 --> 25:14.260 Und hätte damit, mit dem Gram-Scan im Prinzip, angewandt auf diese 25:14.260 --> 25:23.240 oberen beiden konvexen Hüllen-Teile, die gemeinsame konvexe Hülle 25:23.240 --> 25:24.900 gefunden, für den oberen Teil. 25:25.380 --> 25:28.840 Und für den unteren Teil macht man es dann entsprechend genauso. 25:30.400 --> 25:32.980 Und der Aufwand, den wir gerade eben zu machen hatten, war linear. 25:34.560 --> 25:38.880 Wir müssen nur von links nach rechts durch die Punkte durchgehen. 25:39.020 --> 25:41.860 Wir können jeweils feststellen, ob es eine Links- oder Rechtsdrehung 25:41.860 --> 25:43.800 ist, also konkaver oder konvexer Winkel. 25:44.600 --> 25:47.320 Und bei den konkaven Winkeln müssen wir halt entsprechend Punkte 25:47.320 --> 25:47.700 vergessen. 25:48.040 --> 25:49.920 Bei konvexen Winkeln können wir weitermachen. 25:50.700 --> 25:53.580 Und damit ist der Aufwand linear, so wie das hier auch steht. 25:53.760 --> 25:57.040 Auch der Aufwand für das Verschmelzen ist in linearer Zeit zu machen. 25:57.420 --> 25:59.160 Und damit haben wir insgesamt Aufwand N log N. 26:00.420 --> 26:05.660 Auch hier könnte man gucken, inwieweit dieses Verfahren numerisch sich 26:05.660 --> 26:08.920 stabiler verhält als irgendeins der anderen. 26:11.370 --> 26:16.710 Gut, ich denke, das ist ein sehr naheliegendes Verfahren. 26:17.150 --> 26:19.990 Brauche ich nicht weiter darauf einzugehen. 26:21.010 --> 26:23.310 Hier steht das Verfahren nochmal beschrieben. 26:24.630 --> 26:29.270 Das ist also genau das, was ich gerade eben erläutert habe, dass man 26:29.270 --> 26:34.050 die beiden Ränder bestimmt, die oberen Ränder, und dann der Reihe nach 26:34.050 --> 26:34.950 einfach dadurch läuft. 26:36.710 --> 26:38.110 Jetzt haben wir noch ein Verfahren. 26:39.290 --> 26:44.150 Ein Verfahren, das nenne ich, das ist das Verfahren, das nach dem 26:44.150 --> 26:45.570 Wegwerfprinzip arbeitet. 26:46.710 --> 26:48.910 Das Prinzip habe ich Ihnen bisher noch verschwiegen. 26:48.910 --> 26:52.210 Das Wegwerfprinzip ist aber auch ganz interessant. 26:55.610 --> 27:00.790 Man könnte sagen, das ist so ein bisschen ähnlich wie Branch and 27:00.790 --> 27:01.190 Bound. 27:01.810 --> 27:06.870 Es ist einfach die übliche Idee, ich möchte mein Problem möglichst 27:06.870 --> 27:13.310 stark reduzieren, indem ich irgendeine Operation darauf ausführe, die 27:13.310 --> 27:17.610 mir Informationen liefert, sodass ich einen großen Teil der Punkte 27:17.610 --> 27:20.370 wegwerfen kann, also gar nicht mehr berücksichtigen muss. 27:20.830 --> 27:23.370 Ich will das Problem durch ein paar Operationen möglichst drastisch 27:23.370 --> 27:23.910 reduzieren. 27:24.930 --> 27:29.950 Und das macht man in diesem Fall so, dass wir uns anschauen, die Menge 27:29.950 --> 27:30.490 der Punkte. 27:31.910 --> 27:36.090 Ich habe hier einfach mal so ein Rechteck da drum gemalt. 27:37.550 --> 27:41.850 Und wir suchen ja die konvexe Hülle dieser Punkte. 27:42.990 --> 27:45.410 Jetzt machen wir einfach eine Approximation. 27:46.870 --> 27:50.990 Wir suchen einfach Extrempunkte, die relativ einfach zu bestimmen 27:50.990 --> 27:51.290 sind. 27:51.450 --> 27:56.150 Nämlich mit jeweils linearem Aufwand. 27:57.630 --> 28:04.690 Wir suchen acht Extrempunkte im Norden, Nordosten, Osten, Südosten, 28:04.810 --> 28:06.290 Südwesten, Westen, Nordwesten. 28:07.040 --> 28:14.610 Dann haben wir diese Punkte hier, E1, E2, E3 bis E8. 28:21.010 --> 28:22.550 So, jetzt haben wir also acht Punkte. 28:24.150 --> 28:30.750 Und der Aufwand, um diese Punkte zu finden, ist jeweils linear, weil 28:30.750 --> 28:35.250 wir feststellen müssen, was ist also der Punkt in der entsprechenden 28:35.250 --> 28:38.470 Richtung, also jeweils der Extrempunkt. 28:39.290 --> 28:42.130 Das kann man mit linearem Aufwand feststellen. 28:42.250 --> 28:50.370 Ich muss nur in der entsprechenden Richtung die Distanz vom Zentrum 28:50.370 --> 28:50.970 feststellen. 28:51.070 --> 28:52.810 Ich muss also einen mittleren Punkt irgendwie wählen. 28:52.890 --> 28:55.850 Dann kann ich von dem aus die Sektoren mir angucken und kann die 28:55.850 --> 28:57.450 Punkte berechnen. 28:58.550 --> 29:02.330 Und dann habe ich so eine approximierte, konvexe Hülle. 29:03.250 --> 29:12.830 Die gestrichelten Linien hier, das können bereits die Linien sein, die 29:12.830 --> 29:19.690 nachher auch meine Kanten sind der konvexen Hülle. 29:20.810 --> 29:25.610 Ich weiß auf jeden Fall, die Extrempunkte E1 bis E8 sind sicherlich 29:25.610 --> 29:26.750 tatsächlich Extrempunkte. 29:26.750 --> 29:28.870 Es kann sogar sein, dass welche von denen zusammenfallen. 29:29.570 --> 29:34.290 Wenn das also eine sehr einfache Figur ist, dann würden die 29:34.290 --> 29:34.810 zusammenfallen. 29:34.950 --> 29:39.730 Also das Rechteck außenrum, was ich da gezeichnet habe, da hätten wir 29:39.730 --> 29:41.230 nur vier solcher Extrempunkte. 29:42.930 --> 29:45.610 Also da würden einige dieser Punkte zusammenfallen. 29:47.430 --> 29:52.070 Aber hier haben wir jetzt also einen Fall angenommen, da haben wir 29:52.070 --> 29:53.270 jetzt diese acht Punkte. 29:53.270 --> 29:57.590 Und dann kann es natürlich sein, dass es noch weitere Punkte gibt, die 29:57.590 --> 30:00.870 sind hier in dem Bereich dort zu sehen. 30:01.990 --> 30:08.130 Ein paar Punkte fallen nicht unter diese acht Extrempunkte, liegen 30:08.130 --> 30:13.870 aber außerhalb unseres Polygons, das wir jetzt eingezeichnet haben, 30:13.950 --> 30:15.360 aus diesen acht sicheren Extrempunkten. 30:18.200 --> 30:22.680 Aber die ganzen Punkte, die hier drin liegen, die hier im Innern 30:22.680 --> 30:29.220 liegen, dieses approximierten konvexen Polygons, die kann ich alles 30:29.220 --> 30:29.560 vergessen. 30:29.880 --> 30:30.700 Die kann ich wegwerfen. 30:32.960 --> 30:37.120 Und die Erwartung ist halt, dass die meisten Punkte innen liegen 30:37.120 --> 30:41.200 werden und nur wenige Punkte irgendwo mal draußen liegen. 30:41.260 --> 30:44.180 Da haben wir noch einen, da haben wir noch einen, die hier angedeutet 30:44.180 --> 30:45.840 sind, das sind sie dann auch. 30:46.960 --> 30:52.360 Das heißt, ich werfe alle Punkte weg, die im Innern dieses gestrichelt 30:52.360 --> 30:53.920 angedeuteten Polygons liegen. 30:55.040 --> 31:01.660 Das ist mit linearem Aufwand machbar, weil ich ja... ich habe nur acht 31:01.660 --> 31:05.420 solche Kanten, die ich betrachten muss, oder nur sieben solche Kanten. 31:06.780 --> 31:08.700 Acht Punkte durch sieben Kanten verbunden. 31:10.940 --> 31:15.500 Und das heißt, ich muss nur feststellen, welche Punkte liegen halt im 31:15.500 --> 31:16.640 Innern dieses Polygons. 31:18.120 --> 31:23.180 Das ist also relativ einfach zu machen, auf jeden Fall mit linearem 31:23.180 --> 31:23.660 Aufwand. 31:27.160 --> 31:31.600 Ich habe acht Punkte... Entschuldigung, ja, beim Kreis habe ich acht 31:31.600 --> 31:32.140 Kanten, ja. 31:32.660 --> 31:36.300 Da habe ich mich gerade... Manchmal hat man solche... Danke, ja. 31:36.300 --> 31:38.460 Also es sind selbstverständlich acht Kanten. 31:39.440 --> 31:42.640 Weil ich ja... Ich habe ja E1 und E8 nicht identifiziert. 31:43.300 --> 31:44.620 Dann wären es sieben Kanten. 31:45.500 --> 31:46.720 Selbstverständlich sind es acht Kanten. 31:47.680 --> 31:50.720 Also habe ich... auf jeden Fall habe ich also acht Mal diesen Aufwand 31:50.720 --> 31:54.000 zu machen, festzustellen, ob die Punkte links oder rechts liegen. 31:54.600 --> 31:58.280 Und diejenigen, die also im Innern von allen... also im Innern dieses 31:58.280 --> 32:02.000 ganzen Polygons liegen, bei denen weiß ich dann, die kann ich 32:02.000 --> 32:02.500 wegwerfen. 32:02.500 --> 32:05.420 Und die, die draußen liegen, die muss ich halt noch weiter 32:05.420 --> 32:05.650 berücksichtigen. 32:06.220 --> 32:10.480 Das heißt, dann habe ich eine Restmenge und dann nehme ich irgendein 32:10.480 --> 32:12.480 Verfahren, das einen Aufwand nlog n hat. 32:13.120 --> 32:16.000 Oder nlog h, wie wir gerade gesehen haben, das Verfahren davor. 32:18.440 --> 32:24.460 Und wenn wir... also da das... wenn wir jetzt annehmen, dass das 32:24.460 --> 32:24.840 wenig... 32:24.840 --> 32:27.300 oder wenn das wenig sind, wenn wir irgendwie schließen können, das 32:27.300 --> 32:29.940 sind relativ wenig Punkte, die außen liegen, dann hätten wir also 32:29.940 --> 32:34.640 hiermit zwar nlog n, aber bezogen auf die Anzahl der Punkte in der 32:34.640 --> 32:35.200 Restmenge. 32:36.020 --> 32:38.820 Und das heißt, das wäre bezogen... wenn r die Anzahl der Punkte in der 32:38.820 --> 32:41.380 Restmenge ist, dann wäre das ein Aufwand rlog r. 32:42.660 --> 32:48.180 Und wenn wir jetzt noch annehmen, dass die Punkte im Wesentlichen 32:48.180 --> 32:55.080 gleich verteilt sind in unserer Ebene, dann ist der Erwartungswert für 32:55.080 --> 32:56.280 den Aufwand linear. 32:57.980 --> 33:03.920 Weil wir dann nämlich davon ausgehen können, dass nur ein sehr, sehr 33:03.920 --> 33:05.840 kleiner Anteil außen liegt. 33:06.880 --> 33:10.720 Und das ist insbesondere also weniger... also dass die Anzahl, dass 33:10.720 --> 33:11.320 das r... 33:11.320 --> 33:20.960 Wenn das r liegt in klein o von n, dann habe ich kein Problem mit dem 33:20.960 --> 33:21.400 Aufwand. 33:22.600 --> 33:25.680 Und davon kann ich ausgehen, wenn ich Gleichverteilung habe der 33:25.680 --> 33:28.760 Punkte, dann liegen nur sehr wenige außerhalb. 33:31.180 --> 33:34.720 Im schlechtesten Fall natürlich nlog n, aber ich denke, das ist ein 33:34.720 --> 33:38.600 ganz interessantes Verfahren, weil man hier eben einfach so ne grobe 33:38.600 --> 33:43.280 Abschätzung macht, wie könnte in etwa so über den Daumen erstmal die 33:43.280 --> 33:44.320 konvexe Hülle aussehen. 33:44.980 --> 33:47.840 Und das, was man dann auch an Ungenauigkeiten drin hat, muss man halt 33:47.840 --> 33:48.080 korrigieren. 33:49.040 --> 33:50.240 Das ist halt Teil c. 33:50.960 --> 33:52.000 Und dann ist man damit fertig. 33:54.880 --> 33:58.900 Und das Interessante ist eben, dass man sieht, man kann dieses 33:58.900 --> 34:03.520 Problem, die Bestimmung der konvexen Hülle, wirklich mit sehr viel 34:03.520 --> 34:07.920 verschiedenen Verfahren machen. 34:08.220 --> 34:12.320 Man nutzt unterschiedliche Eigenschaften dieser konvexen Hülle aus 34:12.320 --> 34:18.900 oder dieser Punktmenge aus und kann dadurch dieses Problem lösen. 34:19.000 --> 34:21.720 Auch dieses Problem hier ist relativ gut parallel zu machen. 34:22.280 --> 34:27.480 Also diese Entscheidung, die 8 Extrempunkte zu bestimmen, das kann ich 34:27.480 --> 34:28.720 unabhängig voneinander machen. 34:28.720 --> 34:33.340 Auch festzustellen, welche Punkte im Innern liegen, das kann ich gut 34:33.340 --> 34:35.780 parallelisieren, auch mit einem geringen Parallelitätsgrad. 34:38.060 --> 34:41.160 Und bringt mir also durchaus einige Vorteile. 34:42.880 --> 34:51.160 Gut, damit haben wir uns eigentlich jetzt alle Verfahren angeschaut, 34:52.080 --> 34:53.800 die ich Ihnen vorstellen wollte. 34:53.920 --> 34:56.080 Ein Problem ist noch die untere Schranke. 34:56.620 --> 34:59.240 Das hatten wir uns auch ein paar Mal angeschaut. 34:59.400 --> 35:01.520 Wie ist der minimale Aufwand? 35:02.140 --> 35:03.340 Was kann ich darüber aussagen? 35:03.480 --> 35:06.300 Und hier steht es schon, ich habe diese Folie nicht animiert, deswegen 35:06.300 --> 35:08.180 ist gleich alles zu sehen. 35:08.300 --> 35:10.660 Ich möchte also bestimmen, eine untere Schranke für den schlechtesten 35:10.660 --> 35:11.020 Fall. 35:12.920 --> 35:17.420 Und da nehme ich einfach eine Menge von Punkten her, irgendeine Menge 35:17.420 --> 35:23.220 von Punkten, x1 bis xn, das waren einfach irgendwelche ganzen Zahlen, 35:23.220 --> 35:29.180 oder sogar natürliche Zahlen, also nicht negative, und ich definiere 35:29.180 --> 35:31.060 einfach Punkte auf einer Parabel. 35:32.700 --> 35:36.660 Und wenn ich Punkte auf einer Parabel betrachte, dann weiß ich, die 35:36.660 --> 35:39.560 liegen in etwa so, wie das hier angedeutet ist. 35:40.540 --> 35:47.200 Und wenn ich die konvexe Hülle bestimmen möchte von dieser Punktmenge, 35:47.680 --> 35:51.540 dann weiß ich, jeder Punkt in dieser Menge ist ein Extrempunkt. 35:53.880 --> 35:57.580 Die konvexe Hülle hat keinen Punkt, liegt im Inneren, sie sind alle 35:57.580 --> 35:58.100 auf dem Rand. 35:59.720 --> 36:03.820 Und dadurch wird das Problem, die konvexe Hülle zu bestimmen, 36:04.360 --> 36:10.020 eigentlich festgelegt durch das Problem, die Punkte zu sortieren, also 36:10.020 --> 36:11.280 die x-Koordinaten zu sortieren. 36:11.840 --> 36:16.820 Wenn ich die in dieser Reihenfolge anordnen kann, habe ich die konvexe 36:16.820 --> 36:17.780 Hülle bereits gefunden. 36:19.440 --> 36:25.760 Und das heißt, egal welches Verfahren ich betrachte, ich muss in der 36:25.760 --> 36:31.460 Lage sein, auch für dieses Polygon oder für diese Punktmenge die 36:31.460 --> 36:32.560 konvexe Hülle zu bestimmen. 36:33.360 --> 36:36.260 Und die Bestimmung der konvexen Hülle hier ist mindestens so schwer 36:36.260 --> 36:40.560 wie das Problem, die Endpunkte dieser Menge zu sortieren. 36:40.560 --> 36:46.080 Und wir wissen, wenn wir keine anderen Informationen haben als eben 36:46.080 --> 36:53.540 den Vergleich der Werte dieser Punkte, wir können nicht davon 36:53.540 --> 36:58.380 ausgehen, dass wir hier mehr ausnutzen können, dann haben wir also 36:58.380 --> 37:02.840 untere Schranke NlogN für den schlechtesten Fall zur Bestimmung der 37:02.840 --> 37:03.500 konvexen Hülle. 37:04.760 --> 37:11.620 Also das ist klar, dass wir damit die untere Schranke haben, Omega von 37:11.620 --> 37:12.200 NlogN. 37:13.500 --> 37:20.080 Im Mittel ist es aber so, dass wir durchaus Omega von N haben. 37:20.900 --> 37:24.360 Wir hatten ja gerade eben gesehen, es gibt Verfahren, bei denen wir 37:24.360 --> 37:31.180 unter gewissen Annahmen eine lineare Laufzeit garantieren können. 37:32.080 --> 37:35.280 Der Greifprinzip war so ein Verfahren. 37:35.800 --> 37:39.320 Das heißt, hier haben wir im Mittel lineare Laufzeit, anders als beim 37:39.320 --> 37:39.720 Sortieren. 37:39.820 --> 37:42.600 Das ist also schon etwas anders als das Sortierproblem, aber im 37:42.600 --> 37:45.240 schlechtesten Fall untere Schranke NlogN. 37:47.860 --> 37:51.840 Und damit bin ich schon am Ende angekommen von diesem ganzen Kapitel 37:51.840 --> 37:53.140 über algorithmische Geometrie. 37:53.140 --> 37:55.480 Ich hätte durchaus noch mehr Sachen machen können. 37:56.160 --> 38:05.400 Ich hätte dieses Problem mit den Versuchen, auch bei entarteten oder 38:05.400 --> 38:08.400 ungünstigen Problemstellungen exakte Ergebnisse zu kriegen, noch ein 38:08.400 --> 38:09.260 bisschen genauer machen können. 38:09.940 --> 38:16.700 Ich will das aber angesichts der Temperaturen zur Zeit und anderer 38:16.700 --> 38:18.960 Gründe diesmal lassen. 38:18.960 --> 38:24.040 Ich hoffe, dass Sie gesehen haben, dass algorithmische Geometrie auch 38:24.040 --> 38:26.740 ein interessantes Gebiet ist, dass man dort interessante Probleme 38:26.740 --> 38:27.500 angucken kann. 38:28.400 --> 38:33.760 Für jemanden, der an Geometrie Interesse hat und an Informatik, ist 38:33.760 --> 38:35.240 das ein ideales Betätigungsfeld. 38:35.620 --> 38:37.440 Es gibt viele interessante Probleme zu bearbeiten. 38:38.920 --> 38:44.200 Man hat für dieses Gebiet einige interessante neue Lösungstechniken 38:44.200 --> 38:45.160 für Probleme entwickelt. 38:45.160 --> 38:49.200 Also dieses Planesweep-Verfahren macht natürlich nur Sinn bei solchen 38:49.200 --> 38:50.380 geometrischen Problemen. 38:50.540 --> 38:55.220 Reduktion eines Problems auf ein Problem niedrigerer Dimensionen und 38:55.220 --> 39:03.540 systematische Lösung des Problems durch eine Folge von Problemhalt 39:03.540 --> 39:05.240 niedrigerer Dimensionen. 39:05.300 --> 39:11.140 Und das führt also zu durchaus besseren Verfahren und zu guten 39:11.140 --> 39:11.620 Laufzeiten. 39:11.620 --> 39:15.880 Planesweep ist ein interessanter Ansatz, den man auch in anderen 39:15.880 --> 39:17.100 Bereichen einsetzen kann. 39:17.560 --> 39:19.480 Ich habe Ihnen das Wechselprinzip nochmal vorgestellt. 39:20.060 --> 39:24.980 Was ich nicht vorgestellt habe, sind die neuen Datenstrukturen, die 39:24.980 --> 39:27.540 für den Bereich algorithmischer Geometrie entwickelt wurden. 39:30.080 --> 39:35.160 Segmentbäume und Intervallbäume sind entwickelt worden. 39:36.640 --> 39:40.520 Ich denke aber, das reichte als Einblick in die Problemstellungen, die 39:40.520 --> 39:42.380 hier von Interesse sind. 39:43.440 --> 39:47.980 Und damit bin ich am Ende dieses Kapitels und kann jetzt eigentlich 39:47.980 --> 39:48.420 nur noch... 39:49.400 --> 39:51.600 Es sei denn, Sie haben noch Fragen zu dem Bereich algorithmischer 39:51.600 --> 39:52.120 Geometrie. 39:53.040 --> 39:59.160 Jetzt komme ich nur noch schnell zu einem abschließenden Kapitel. 39:59.920 --> 40:04.160 Das müsste hier eigentlich auch noch in meinem... 40:09.830 --> 40:11.070 Na, wo habe ich es? 40:14.890 --> 40:15.890 Einmal sortieren... 40:16.450 --> 40:16.950 Genau. 40:19.110 --> 40:21.960 Das ist... 40:21.960 --> 40:25.160 Gehe ich mal lieber auf die andere Datei. 40:26.140 --> 40:26.980 Auf diese hier. 40:29.660 --> 40:31.900 Abschließende Bemerkung ganz kurz. 40:35.230 --> 40:37.910 Das Algorithmik ein zentrales Gebiet der Informatik ist, ich denke, 40:38.030 --> 40:39.730 das ist durchaus jedem klar. 40:41.210 --> 40:44.710 Informatik lebt davon, dass wir effizient mit den Ressourcen umgehen 40:44.710 --> 40:45.090 können. 40:45.950 --> 40:49.010 Wenn wir Mathematik und Informatik vergleichen, dann geht es in der 40:49.010 --> 40:51.990 Informatik halt darum, dass man Ressourcen effizient verwendet. 40:52.290 --> 40:55.570 Mathematiker interessieren sich dafür, ob ein Problem prinzipiell 40:55.570 --> 40:56.290 lösbar ist. 40:56.290 --> 41:00.290 Aber da geht es weniger darum, die Kosten abzuschätzen. 41:01.170 --> 41:03.290 Und wir wissen, dass die Rechner nie schnell genug sind. 41:03.570 --> 41:08.370 Ich habe durchaus schon mal Menschen, die durchaus ernsthaft 41:08.370 --> 41:13.330 Wissenschaft machen, sagen hören, naja, um Effizienz brauchen wir uns 41:13.330 --> 41:16.410 nicht zu kümmern, die Rechner werden doch immer schneller und damit 41:16.410 --> 41:17.210 ist das erledigt. 41:17.210 --> 41:26.150 Wir wissen, dass eine Wachstumskurve, die so läuft, durchaus Nachteile 41:26.150 --> 41:28.230 hat gegenüber einer, die so läuft. 41:28.990 --> 41:35.170 Logarithmisch oder etwas, was deutlich stärker wächst als linear. 41:35.990 --> 41:40.650 Das sind schon für große Probleme Unterschiede, die sehr, sehr wichtig 41:40.650 --> 41:41.050 sind. 41:41.050 --> 41:45.130 Und wir hatten durchaus Beispiele gesehen, wo man sehr große 41:45.130 --> 41:50.030 Unterschiede hat zwischen einem Aufwand für naive Algorithmen und für 41:50.030 --> 41:53.050 etwas intelligentere Algorithmen. 41:53.630 --> 41:56.450 Also es lohnt sich immer, nach effizienten Lösungen zu suchen. 41:57.450 --> 42:03.550 Man muss aber natürlich immer aufpassen, wenn wir solche Kurven haben, 42:03.550 --> 42:07.590 da kann es halt sein, dass man sich genau anschauen muss, in welchem 42:07.590 --> 42:13.750 Bereich betrachte ich denn eigentlich meine Probleme, wo sind die 42:13.750 --> 42:15.690 Problemgrößen, für die ich mich interessieren muss. 42:17.710 --> 42:22.590 Und da muss ich sehen, wie sehen dort die Kosten aus. 42:22.710 --> 42:27.250 Also Kostenanalyse darf nicht nur asymptotisch sein, sondern muss auch 42:27.250 --> 42:34.870 die Kosten in dem Bereich betrachten, in dem ich meine Anwendungen 42:34.870 --> 42:35.710 habe. 42:36.930 --> 42:41.610 Und es ist klar, dass Entwurf und Aufwand gucken müssen, was ist das 42:41.610 --> 42:42.410 Berechnungsmodell. 42:43.190 --> 42:46.530 Da hatten wir RAM angeguckt, als elementares Berechnungsmodell, aber 42:46.530 --> 42:48.530 eben auch die ganzen parallelen Berechnungsmodelle. 42:49.270 --> 42:52.010 Und wenn ich Parallelrechner zur Verfügung habe, muss ich sehen, in 42:52.010 --> 42:55.870 welcher Form kann ich dort Kosten reduzieren. 42:56.570 --> 42:59.550 Und was muss ich dafür an anderer Stelle bezahlen. 43:00.850 --> 43:03.950 Und dann haben wir halt das Problem, dass wir unterschiedliche 43:03.950 --> 43:05.490 Datenstrukturen verwenden können. 43:06.590 --> 43:10.750 Und natürlich, also Rechnerstrukturen ist im Berechnungsmodell 43:10.750 --> 43:12.430 eigentlich auch schon mit abgegolten. 43:13.770 --> 43:22.510 Also wir müssen sehen, was sind die Strukturen, die uns erlauben, die 43:22.510 --> 43:26.100 Probleme darzustellen, damit umzugehen, welche Operationen habe ich 43:26.100 --> 43:29.260 auf diesen Strukturen auszuführen, wie kann ich das so machen, dass 43:29.260 --> 43:33.600 insgesamt der Aufwand für die Lösung eines Problems dann klein bleibt. 43:35.260 --> 43:37.620 Die Probleme, die wir betrachtet haben, sind hier nochmal aufgelistet. 43:39.040 --> 43:42.600 Algebraische Probleme, Graphprobleme, recht kurz, Such- und 43:42.600 --> 43:46.900 Sortierverfahren und die algorithmische Geometrie. 43:48.200 --> 43:52.240 Und was wir gemacht haben, sind hier nochmal die Prinzipien, die ich 43:52.240 --> 43:55.100 Ihnen vorgestellt habe, algorithmische Entwurfsprinzipien. 43:55.800 --> 44:00.540 Ich habe Ihnen systematische Verfahren für den Entwurf von parallelen 44:00.540 --> 44:04.340 Algorithmen vorgestellt, den Mapping-Ansatz, bei dem wir gesehen 44:04.340 --> 44:08.040 haben, wie man also einfach durch affine Transformationen von 44:08.040 --> 44:14.000 Problemstellungen, also von Abhängigkeitsstrukturen tatsächlich 44:14.000 --> 44:17.160 Algorithmen entwerfen kann, so dass man eine ganze Vielfalt von 44:17.160 --> 44:20.240 verschiedenen parallelen Realisierungen, meinetwegen der Matrix 44:20.240 --> 44:23.980 -Multiplikation, einfach durch solche unterschiedlichen affinen 44:23.980 --> 44:29.740 Transformationen halt erzeugen konnte, was ein ganz wichtiger Punkt 44:29.740 --> 44:29.960 ist. 44:30.020 --> 44:33.480 Dadurch ist man in der Lage, systematisch, ingenieurmäßig tatsächlich 44:33.480 --> 44:34.960 Algorithmen zu entwerfen. 44:36.820 --> 44:40.760 Ja, das waren so die verschiedenen Themen, die verschiedenen 44:40.760 --> 44:41.460 Prinzipien. 44:42.540 --> 44:44.680 Und was kann man bei uns noch alles machen? 44:45.520 --> 44:51.400 Das sind so die verschiedenen Bereiche, die bei uns am Institut 44:51.400 --> 44:54.220 vorhanden sind. 44:54.900 --> 45:01.160 Mein Bereich halt effiziente Algorithmen, wobei das Thema effiziente 45:01.160 --> 45:03.680 Algorithmen in unterschiedlichster Form bei uns behandelt wird. 45:04.640 --> 45:08.200 Ich glaube, das wissen Sie auch, dass wir also sehr viel, ich weiß gar 45:08.200 --> 45:10.740 nicht, was ich hier jetzt noch an weiteren Folien habe. 45:11.640 --> 45:13.100 Gehe ich nur mal kurz darauf ein. 45:15.540 --> 45:17.780 Ich komme gleich noch auf die verschiedenen Themen der Forschung, die 45:17.780 --> 45:18.180 wir machen. 45:19.260 --> 45:24.340 Also unsere Vorlesungsthemen kennen Sie, glaube ich, auch. 45:24.520 --> 45:25.900 Welche Vorlesung haben Sie gemacht? 45:27.600 --> 45:28.360 Bisher nur diese. 45:28.500 --> 45:31.460 Aha, dann kann ich Ihnen also die Vorlesung natürlich auch empfehlen. 45:32.680 --> 45:35.960 Angewandte Informatik 2, Informatikwerkzeuge für elektronischen Handel 45:35.960 --> 45:40.160 oder Algorithms for Internet Applications auf Englisch. 45:40.160 --> 45:45.640 Da geht es halt um Algorithmen, speziell in verteilten Systemen, sehr 45:45.640 --> 45:49.980 speziell in verteilten Systemen, speziell also im Internet. 45:50.940 --> 45:55.300 Und dann gibt es noch eine Vorlesung verteilter Algorithmen, der man 45:55.300 --> 45:58.840 speziell Probleme in verteilten Systemen anschaut. 45:59.000 --> 46:02.160 Die biete ich aber sehr, sehr unregelmäßig an, weil ich einfach nicht 46:02.160 --> 46:06.400 die Lehrkapazität habe, um alle diese Vorlesungen anzubieten. 46:07.200 --> 46:11.060 Naturanaloge Verteilte Optimierungsverfahren läuft immer parallel zu 46:11.060 --> 46:11.640 dieser hier. 46:12.640 --> 46:17.680 Da geht es halt um Meteoristiken, um schwierige Probleme zu lösen. 46:18.400 --> 46:21.720 Und das, was wir eben sehr stark machen, sind die genetischen oder 46:21.720 --> 46:24.320 evolutionären Algorithmen und Ameisenalgorithmen. 46:25.440 --> 46:27.600 Oder auch Kombinationen von diesen Dingern. 46:28.120 --> 46:32.400 Und eine Vorlesung, die Herr Branke, mein Assistent, gemeinsam mit 46:32.400 --> 46:35.520 einem Assistenten aus der Informationswirtschaft macht. 46:35.520 --> 46:36.860 Computational Economics. 46:37.560 --> 46:40.880 Agentenbasierte Simulation von wirtschaftlichen Problemen. 46:42.420 --> 46:45.280 Sehr interessante Verfahren, die dort eingesetzt werden. 46:45.820 --> 46:47.980 Das ist unser Lehrprogramm zur Zeit. 46:48.400 --> 46:49.780 Natürlich auch Seminare. 46:51.000 --> 46:53.280 Wobei, Sie sehen, ich habe das nicht aktualisiert. 46:54.120 --> 46:56.080 Das stimmt jetzt natürlich nicht ganz. 46:56.180 --> 46:59.280 Was machen wir im Seminar zur Zeit? 47:00.720 --> 47:04.860 Also, wenn ich hier ein Oberthema hinschreiben soll, dann sind die 47:04.860 --> 47:08.420 Themen, die wir zur Zeit betrachten, haben alle zu tun mit Organic 47:08.420 --> 47:08.980 Computing. 47:11.400 --> 47:13.680 Ich weiß nicht, ob ich Ihnen schon mal von Organic Computing erzählt 47:13.680 --> 47:14.120 habe. 47:15.640 --> 47:17.320 Insofern wissen Sie etwas darüber. 47:20.860 --> 47:23.320 Lebensähnliche Systeme, die sich anpassen können. 47:23.320 --> 47:26.800 Und das spielen die Themen, die hier stehen, eine Rolle. 47:27.280 --> 47:32.020 Was wir jetzt im kommenden Wintersemester machen, ist das Thema 47:32.020 --> 47:41.480 gesteuerte Selbstorganisation oder Controlled Self-Organization. 47:43.020 --> 47:46.100 Klingt wie ein Widerspruch, ist aber genau das, was wir in Organic 47:46.100 --> 47:47.660 Computing behandeln müssen. 47:47.660 --> 47:52.840 Wie kann ich Systeme, die selbstorganisierend arbeiten, einfach weil 47:52.840 --> 47:56.320 sie nicht zentral gesteuert werden können, wie kann ich die trotzdem 47:56.320 --> 47:59.580 noch beherrschbar halten, wie kann ich sie beeinflussen, sodass sie 47:59.580 --> 48:05.300 immer das tun, was ich will und nicht auf einmal in Verhaltensbereiche 48:05.300 --> 48:08.040 abdriften, die eigentlich nicht gewünscht sind. 48:08.300 --> 48:11.140 Ein Thema, das in der Literatur immer wieder behandelt wird. 48:11.140 --> 48:15.100 Die außer Kontrolle geratenen technischen Systeme. 48:15.560 --> 48:19.400 Wenn Sie das Buch Beute oder Prey kennen, dann wissen Sie, wovon die 48:19.400 --> 48:19.880 Rede ist. 48:21.760 --> 48:24.900 Und man muss halt sehen, dass man Mechanismen entwirft, sodass so 48:24.900 --> 48:26.620 etwas wie in Prey nicht vorkommen kann. 48:26.760 --> 48:28.280 Deswegen die gesteuerte Selbstorganisation. 48:29.040 --> 48:33.980 Und damit beschäftigen wir uns im Wintersemester, also Wintersemester 48:33.980 --> 48:36.520 2006 -07. 48:36.520 --> 48:41.140 Seminar Praktika hatten wir im letzten Wintersemester Service 48:41.140 --> 48:42.260 -orientierte Architekturen. 48:42.960 --> 48:48.040 Das bezog sich auf unser Projekt KIM, diese Karlsruhe-integrierte 48:48.040 --> 48:51.590 Informationsmanagement -Systeme. 48:52.980 --> 48:56.530 Und in diesem Wintersemester machen wir ein Seminar über Spamfilter. 49:01.150 --> 49:02.470 Spamfilter für E-Mail. 49:03.470 --> 49:05.690 Was ist daran interessant, das sind Lernverfahren, die man dabei 49:05.690 --> 49:07.470 einsetzt, unterschiedlichste Lernverfahren. 49:07.470 --> 49:12.470 Und da sollen einfach mal ein paar solches Filter gebaut werden. 49:12.570 --> 49:14.730 Im Prinzip sollen also Lernverfahren implementiert werden. 49:15.270 --> 49:17.030 Das ist also jetzt in diesem Wintersemester. 49:19.010 --> 49:21.590 Das sind die beiden Seminar, also Seminar und Seminarpraktikum. 49:22.930 --> 49:28.390 Und Themen zum Oberthema Organic Computing oder Service-orientierte 49:28.390 --> 49:31.770 Architekturen oder Autonomic Computing, das sind so die Themen, die 49:31.770 --> 49:32.830 uns zur Zeit beschäftigen. 49:32.830 --> 49:37.890 Und dann gibt es natürlich auch noch Diplomarbeiten, die Sie 49:37.890 --> 49:38.990 irgendwann mal machen können. 49:39.730 --> 49:41.050 Da dürfen Sie gerne zu uns kommen. 49:41.290 --> 49:43.630 Auch die haben sehr viel zu tun mit unserem wesentlichen 49:43.630 --> 49:45.890 Forschungsgebiet und das ist halt zur Zeit Organic Computing. 49:47.130 --> 49:51.990 Und da spielen aber viele verschiedene Themen rein. 49:52.790 --> 49:55.390 Ich hatte gesagt, ein Thema, das auch interessant sein könnte, wäre 49:55.390 --> 50:00.790 diese Untersuchung der Robustheit oder Stabilität von Verfahren in der 50:00.790 --> 50:01.710 algorithmischen Geometrie. 50:01.710 --> 50:06.950 Also speziell, wie wirken sich verschiedene Verfahren der konvexen 50:06.950 --> 50:09.960 Höhlenbestimmung aus auf die numerische Stabilität. 50:11.230 --> 50:12.690 Kann man sich ein bisschen angucken. 50:14.050 --> 50:17.450 Die anderen Themen hier, Grid Computing, da bauen wir einen 50:17.450 --> 50:22.710 Jobscheduler, der in einer intelligenten Art und Weise Jobs verteilt 50:22.710 --> 50:23.190 im Netz. 50:23.190 --> 50:29.570 Oder bei Informationsdienstleistung, IT-Controlling, arbeiten wir in 50:29.570 --> 50:36.630 Kooperation mit einem lokalen Dienstleister im Bankbereich. 50:37.790 --> 50:40.990 Und dort werden halt Verfahren zur effizienten Nutzung der 50:40.990 --> 50:48.290 Rechenressourcen in so einem großen Informationsdienstleistungszentrum 50:48.290 --> 50:49.190 entwickelt. 50:49.910 --> 50:53.410 E -Learning ist ein bisschen mehr an den Rand gegangen, auch da gibt 50:53.410 --> 50:54.170 es aber Arbeiten. 50:55.170 --> 50:59.870 Das sogenannte Activity Tree Harvesting wird dort gemacht. 51:00.510 --> 51:04.270 Mobile Anwendungen haben wir im Augenblick etwas in den Hintergrund 51:04.270 --> 51:07.630 gerückt, aber hat ein bisschen auch mit Organic Computing zu tun. 51:07.790 --> 51:11.290 Das Projekt Notebook University ist ja nicht mehr so akut. 51:11.590 --> 51:15.950 Allerdings haben wir im Bereich KIM durchaus Themen, die man da auch 51:15.950 --> 51:17.190 betrachten kann. 51:17.190 --> 51:22.930 Und dann ist es so, dass wir eine ganze Reihe unserer Themen in 51:22.930 --> 51:24.310 Kooperation mit der Industrie machen. 51:24.590 --> 51:29.470 Wer vielleicht über Praktikum oder ähnliches schon Kontakte mit der 51:29.470 --> 51:33.710 Industrie hat, kann gerne zu uns kommen, sofern das Thema zu den 51:33.710 --> 51:36.610 Themen meiner Gruppe passt. 51:39.670 --> 51:43.570 Und die Thematik hier oben, Informationsdienstleistung, IT 51:43.570 --> 51:46.810 -Controlling, das sind alles Themen in Kooperation mit der Industrie. 51:49.150 --> 51:53.270 Ja, das also zu der Gruppe soweit. 51:54.330 --> 51:55.890 Forschungsthemen habe ich kurz angesprochen. 51:57.210 --> 51:59.830 Dann kann ich nur noch fragen, ob Sie Fragen haben. 52:04.690 --> 52:06.990 Ja, also Fragen zur Klausur können Sie auch gerne stellen, 52:07.390 --> 52:08.590 beziehungsweise zur möglichen Prüfung. 52:08.590 --> 52:09.290 Ja. 52:31.930 --> 52:36.190 Man müsste sich natürlich überlegen, wie würde man daran gehen, die 52:36.190 --> 52:41.850 untere Schranke für die Zeit zu bestimmen, wenn ich so ein System von 52:41.850 --> 52:43.030 Rekurrenzgleichungen habe. 52:44.890 --> 52:45.970 Wie würden Sie das denn machen? 52:46.050 --> 52:47.990 Wie würden Sie dann versuchen, so eine untere Schranke zu finden? 52:49.250 --> 52:50.010 Wissen Sie nicht. 52:51.070 --> 52:55.230 Wie haben wir das denn gemacht bei dem... also was ist denn ein... 52:55.230 --> 53:00.190 wenn man sich das anschaut, was wir da betrachtet haben. 53:01.270 --> 53:05.550 Ich habe irgendein... also das, was wir betrachten, ist doch immer so 53:05.550 --> 53:06.910 ein Datenabhängigkeitsgraf. 53:08.010 --> 53:10.610 Ja, das waren doch relativ reguläre Strukturen. 53:12.450 --> 53:16.230 Und das heißt, wir haben hier irgendwelche Abhängigkeiten, 53:16.370 --> 53:17.870 irgendwelche Daten, die hier durchlaufen. 53:18.950 --> 53:22.870 Und ich weiß, wie groß mein Gitter ist. 53:23.890 --> 53:29.050 Also ich habe ja irgendeine Indexmenge, über die ich überhaupt laufen 53:29.050 --> 53:29.410 kann. 53:31.090 --> 53:31.270 Ja. 53:32.450 --> 53:33.710 Die Indexmenge kenne ich ja. 53:34.750 --> 53:40.210 Und ich weiß doch, ich kann davon ausgehen, dass ich über jede Kante 53:40.210 --> 53:42.290 mindestens eine Verzögerung habe. 53:42.870 --> 53:44.470 Konstante Verzögerung funktioniert nicht. 53:44.550 --> 53:49.750 Wir machen hier keine MIDI-Automaten, das sind alles Moor-Automaten, 53:49.850 --> 53:51.030 diese Knoten. 53:51.390 --> 53:54.650 Ich kann nicht im gleichen Takt zwei Berechnungen machen, die 53:54.650 --> 53:55.810 voneinander abhängig sind. 53:55.890 --> 53:56.470 Das geht nicht. 53:57.250 --> 53:58.970 Da braucht es mindestens einen Takt dazwischen. 53:58.970 --> 54:03.010 Ich habe also mindestens, überall weiß ich, habe ich hier größer 54:03.010 --> 54:05.330 gleich eins als Verzögerung. 54:06.430 --> 54:09.150 Das sieht ja nicht unbedingt immer so einfach aus wie hier. 54:09.250 --> 54:12.410 Es kann sein, dass es auch mal irgendwelche längeren Kanten gibt da 54:12.410 --> 54:12.670 drin. 54:14.230 --> 54:17.350 Dann, wenn die Datenabhängigkeiten nicht Distanz 1 sind, sondern 54:17.350 --> 54:20.850 Distanz 2 oder irgendwas, oder noch größer, kann ja auch sein. 54:26.090 --> 54:30.270 Aber ich weiß doch etwas darüber, was hier gemacht wird. 54:30.450 --> 54:35.710 Ich weiß, jeder Punkt hier drin ist doch eine Berechnung, die 54:35.710 --> 54:36.790 ausgeführt werden muss. 54:39.910 --> 54:44.690 Und damit weiß ich doch etwas über die minimale Zeit, die ich brauche, 54:44.950 --> 54:46.510 um alle Berechnungen auszuführen. 54:46.510 --> 54:47.870 Was wäre denn das? 54:48.790 --> 54:53.670 Wenn Sie so einen Graphen haben, dann gibt es doch irgendwelche 54:53.670 --> 54:54.690 Punkte, wo das Ganze losgeht. 54:55.770 --> 54:58.610 Also zum Beispiel, wenn ich hier, da geht es in meinen Bereich rein, 54:59.170 --> 54:59.690 zum Beispiel. 55:00.570 --> 55:05.550 Wenn das so eine Struktur wäre, wüsste ich doch, es gibt also 55:05.550 --> 55:09.370 irgendeine Berechnung, das ist die erste Berechnung, die losgehen 55:09.370 --> 55:09.650 kann. 55:10.890 --> 55:16.030 Man muss doch eigentlich nur gucken, was der längste Weg ist. 55:16.630 --> 55:19.890 Also, welcher Wert ist das im Graphen? 55:22.110 --> 55:27.210 Was ist der längste, welchen Wert muss ich bestimmen, um hier 55:27.210 --> 55:31.470 festzustellen, was eine untere Schranke ist für die Zeit, die ich 55:31.470 --> 55:31.890 brauche? 55:35.230 --> 55:48.190 Ja, also ist doch im Prinzip der längste, kürzeste Weg zwischen diesen 55:48.190 --> 55:48.990 Knoten. 55:50.170 --> 55:58.170 Und also der längste, der minimale längste Weg in diesem gerichteten 55:58.170 --> 55:59.070 Graphen. 55:59.710 --> 56:03.990 Von irgendeinem Anfangspunkt halt zu der Senke dieses Weges. 56:05.370 --> 56:07.830 Und das heißt doch, ich muss den Durchmesser bestimmen. 56:12.210 --> 56:14.390 Ja, ich muss nur diesen kritischen Pfad im Prinzip finden. 56:15.490 --> 56:18.210 Und der liefert mir genau die untere Schranke für die Zeit. 56:19.070 --> 56:21.830 Und das war bei der Matrix-Multiplikation gerade die, wenn man sich 56:21.830 --> 56:23.630 das da anschaut, das ist gerade 3,1,-2. 56:26.950 --> 56:33.690 Ja, das ist, kann man sich da relativ einfach an diesem Kubus, den ich 56:33.690 --> 56:36.710 Ihnen da aufgemalt habe, dieses dreidimensionale Gebilde, kann man 56:36.710 --> 56:49.370 sich daran sehr einfach überlegen, dass man 3,1,-2 hat als maximal 56:49.370 --> 56:52.870 kürzesten Weg zwischen zwei Knoten da drin. 56:53.690 --> 56:55.570 Und das gibt genau die untere Schranke für die Zeit. 56:55.650 --> 56:59.830 Denn so lange brauche ich mindestens, um von der ersten Berechnung, so 56:59.830 --> 57:04.290 eines Berechnungspfades, bis zur letzten Berechnung zu kommen. 57:17.110 --> 57:18.430 Gut, hoffen wir mal. 57:19.850 --> 57:23.790 Also, wenn Sie noch Fragen haben, Sie können ja auch noch Frau Moster 57:23.790 --> 57:24.430 geben, fragen. 57:25.450 --> 57:27.270 Sie können auch nochmal bei mir in die Sprechstunde kommen, wenn Sie 57:27.270 --> 57:27.610 wollen. 57:28.570 --> 57:33.370 Ich denke, Sie waren jetzt immer hier, die anderen haben sich das zu 57:33.370 --> 57:34.330 Hause angeguckt. 57:34.750 --> 57:35.650 Sie konnten Fragen stellen. 57:35.690 --> 57:36.830 Sie haben nicht viele Fragen gestellt. 57:37.070 --> 57:40.170 Also eigentlich, es ist ein bisschen schwer, so von diesem Frontal 57:40.170 --> 57:42.170 -Präsentationssystem wegzukommen. 57:42.170 --> 57:47.490 Man kann natürlich auch so vorgehen, dass ich Konserven verteile, wo 57:47.490 --> 57:49.990 die Vorlesung irgendwie aufgezeichnet ist. 57:50.090 --> 57:51.590 Und dann diskutiert man hier nur über die Probleme. 57:51.730 --> 57:52.970 Aber im Prinzip machen Sie das in den Übungen. 57:54.310 --> 57:58.130 Dass Sie in den Übungen nochmal die einzelnen Problemstellungen 57:58.130 --> 57:58.410 diskutieren. 58:03.450 --> 58:07.710 Da ich bei dieser Vorlesung eigentlich in den letzten Jahren immer 58:07.710 --> 58:10.690 mündliche Prüfungen gemacht habe, gibt es keine alten Klausuren. 58:34.140 --> 58:39.820 Also es ist ja so, wenn Sie eine Übungsaufgabe haben, da kann man von 58:39.820 --> 58:42.820 ausgehen, da können Sie sich mal eine Stunde dran setzen. 58:44.060 --> 58:49.480 Es ist einfach auch so, man muss ja gewisse Techniken des 58:49.480 --> 58:50.780 Algorithmenentwurfs hier lernen. 58:51.060 --> 58:54.300 Und wenn man die noch nicht beherrscht, dann sitzt man halt da und 58:54.300 --> 58:55.400 kommt nicht auf die richtige Idee. 58:57.060 --> 58:59.480 Das kann man nur lernen, indem man das immer wieder macht, immer 58:59.480 --> 59:00.520 wieder Aufgaben bearbeitet. 59:00.720 --> 59:05.980 Aber in einer mündlichen Prüfung kann ich natürlich nicht davon 59:05.980 --> 59:09.240 ausgehen, dass Sie erst mal eine Stunde überlegen, wie die Antwort ist 59:09.240 --> 59:10.180 für irgendeine Frage. 59:10.360 --> 59:13.840 Also alle Fragen, die ich stelle, müssen in kurzer Zeit so antwortbar 59:13.840 --> 59:14.120 sein. 59:14.920 --> 59:18.200 Und wenn ich feststelle, Sie kommen nicht auf den richtigen Weg, dann 59:18.200 --> 59:20.860 kann ich ja durch meine Fragen Sie dahinführen. 59:21.640 --> 59:23.280 Ja, ich kann ja Hinweise geben. 59:24.060 --> 59:27.860 Insofern ist eine mündliche Prüfung etwas sehr Adaptives. 59:28.820 --> 59:32.420 Ich passe mich immer dem an, was ich sehe, an Rückmeldungen von dem 59:32.420 --> 59:33.040 Prüfling. 59:34.600 --> 59:38.180 Weil ich sehe ja, was als Reaktion kommt und kann dann entsprechend 59:38.180 --> 59:38.980 darauf reagieren. 59:39.560 --> 59:44.760 Es geht mir darum, ob Sie mit dem Stoff umgehen können, den ich Ihnen 59:44.760 --> 59:47.520 vermittelt habe, oder zumindest versucht habe zu vermitteln. 59:48.260 --> 59:51.420 Und das ist halt einiges, was Sie einfach wissen sollten. 59:52.620 --> 59:56.200 Aber eine ganze Reihe anderer Sachen sind auch so, da kann ich Fragen 59:56.200 --> 01:00:00.160 stellen, wo ich einfach feststelle, ob Sie gewisse Prinzipien 01:00:00.160 --> 01:00:00.960 verstanden haben. 01:00:02.920 --> 01:00:04.680 Fragen beider Art werden vorkommen. 01:00:05.900 --> 01:00:10.660 Aber es geht mir nicht darum, dass Sie jetzt Beweise auswendig gelernt 01:00:10.660 --> 01:00:10.900 haben. 01:00:10.980 --> 01:00:11.820 Darauf kommt es nicht an. 01:00:13.500 --> 01:00:19.640 Sondern die wichtigen Überlegungen für den Algorithmenentwurf, die 01:00:19.640 --> 01:00:20.820 muss man verstanden haben. 01:00:20.920 --> 01:00:23.040 Und natürlich sollte man auch ein paar Einsichten gewonnen haben, wenn 01:00:23.040 --> 01:00:24.160 man so einen Beweis macht. 01:00:24.500 --> 01:00:26.560 Was nutzt man eigentlich für Eigenschaften dabei aus? 01:00:28.780 --> 01:00:32.920 Aber wie der Beweis konkret jetzt funktioniert dafür, dass irgendwas 01:00:32.920 --> 01:00:37.620 in der unteren Schranke ist, oder wir hatten das bei dem 01:00:37.620 --> 01:00:42.800 Straßenverfahren, da die Abschätzung, wie nun genau die Laufzeit 01:00:42.800 --> 01:00:47.860 aussieht, oder auch die Untersuchungen für mittleren Aufwand von 01:00:47.860 --> 01:00:50.920 Verfahren, das ist manchmal recht kompliziert. 01:00:51.600 --> 01:00:56.140 Und wenn Sie an Hiebsort, mittleres Verhalten denken, auf die Idee zu 01:00:56.140 --> 01:00:58.760 kommen, dass man das nun gerade so ansetzt, wie ich es dort gemacht 01:00:58.760 --> 01:01:03.380 habe, das ist halt auch Intuition, dann hat man halt diese Idee und 01:01:03.380 --> 01:01:05.040 dann läuft das. 01:01:09.120 --> 01:01:12.060 Also genau diesen Ansatz zu finden, das werde ich nicht in einer 01:01:12.060 --> 01:01:13.320 möglichen Prüfung nachfragen. 01:01:15.920 --> 01:01:21.140 Aber man muss halt wissen, was man angucken muss, wenn man Aussagen 01:01:21.140 --> 01:01:24.420 über das mittlere Verhalten macht, was man für Informationen braucht. 01:01:25.320 --> 01:01:30.560 Und worauf es mir auch ankommt, ist, dass man sich klar macht, dass 01:01:30.560 --> 01:01:36.520 die Menge an Informationen, die man hat über ein Problem, halt genau 01:01:36.520 --> 01:01:38.940 bestimmt, was für Lösungsverfahren ich einsetzen kann. 01:01:39.320 --> 01:01:42.480 Wenn ich halt mehr Informationen habe, muss ich die auch ausnutzen und 01:01:42.480 --> 01:01:45.540 sollte sie ausnutzen, weil die eventuell zu einer deutlichen 01:01:45.540 --> 01:01:48.000 Vereinfachung des Problems beitragen können. 01:01:48.000 --> 01:01:51.300 Das haben wir gesehen bei den Sortierverfahren, wenn man halt vom 01:01:51.300 --> 01:01:54.060 allgemeinen Sortierproblem auf ein spezielles Sortierproblem geht, 01:01:54.540 --> 01:01:55.100 wurde es einfacher. 01:01:55.260 --> 01:02:00.260 Wenn man vom allgemeinen Polynom auf spezielle Polynome ging, wurde es 01:02:00.260 --> 01:02:01.040 deutlich einfacher. 01:02:01.960 --> 01:02:05.880 Und das ist halt in vielen Fällen der Fall, man sollte sich genau 01:02:05.880 --> 01:02:09.920 angucken, was für eine Problemstellung man hat, und dann kann man 01:02:09.920 --> 01:02:15.900 damit auch entscheiden, was für Verfahren sind dort sinnvoll 01:02:15.900 --> 01:02:16.460 einsetzbar. 01:02:17.160 --> 01:02:20.360 Was ich jetzt überhaupt nicht angesprochen habe in dieser Vorlesung, 01:02:21.200 --> 01:02:25.280 sind die wirklich schwierigen Probleme, nämlich NP-vollständige 01:02:25.280 --> 01:02:27.200 Probleme, die haben wir ganz draußen vorgelassen. 01:02:28.740 --> 01:02:31.320 Natürlich kann man sagen, das sind ja auch die Probleme, bei denen ich 01:02:31.320 --> 01:02:33.500 keine effiziente Lösung zur Verfügung habe. 01:02:34.640 --> 01:02:37.780 Für die Praxis ist es natürlich wichtig, dass ich auch in der Lage 01:02:37.780 --> 01:02:40.100 bin, bei solchen schwierigen Problemen, die ja leider häufig 01:02:40.100 --> 01:02:44.980 auftreten, einigermaßen in vernünftiger Zeit gute Lösungen zu finden. 01:02:44.980 --> 01:02:51.600 Das ist aber mehr ein Thema bei der Vorlesung über die naturnalogen 01:02:51.600 --> 01:02:52.980 Optimierungsverfahren. 01:02:54.360 --> 01:02:58.140 Aber es gibt da noch eine Fülle von Themen, die man anschauen kann, 01:02:58.820 --> 01:03:04.780 wie man den Lösungsaufwand oder den Bearbeitungsaufwand für diese 01:03:04.780 --> 01:03:07.000 wirklich schwierigen Probleme minimieren kann. 01:03:07.560 --> 01:03:10.580 Da gibt es also sehr viel im ganzen Bereich der randomisierten 01:03:10.580 --> 01:03:11.240 Verfahren. 01:03:12.000 --> 01:03:15.780 Es gibt Approximationsverfahren für solche schwierigen Probleme. 01:03:16.520 --> 01:03:18.920 Das geht also weit über das hinaus, was ich in dieser Vorlesung 01:03:18.920 --> 01:03:19.740 präsentieren konnte. 01:03:23.430 --> 01:03:27.370 Gut, dann sehen wir uns in der Prüfung am 3.8. 01:03:28.350 --> 01:03:32.510 und ich denke, dass das ein positives Erlebnis sein wird. 01:03:32.930 --> 01:03:34.530 Für beide hoffe ich das. 01:03:35.650 --> 01:03:41.710 Gut, dann bis zum nächsten Donnerstag und ich hoffe, Sie hatten 01:03:41.710 --> 01:03:43.030 einigermaßen Spaß an der Vorlesung. 01:03:43.370 --> 01:03:45.030 Bis zum nächsten Mal.