Okay, ich begrüße Sie zur heutigen Vorlesung.
Herr Schmeck ist heute nicht hier, deswegen musste ich ihn vertreten.
Also diese Vorlesung wird auch aufgezeichnet, aber ich verwende nur
meine internal-Mikrofone, da es nicht funktioniert hier.
Aber Sie können auch die Aufzeichnung von letztes Jahr anhören.
Die Aufzeichnungen ab 2004 sind auch in Diva verfügbar.
Und es ist nicht nur wegen der Qualität, sondern auch, da Herr Schmeck
der Dozent ist, ich denke, es ist besser, wenn Sie auch einmal die
genaue Aufzeichnung von Herrn Schmeck hören.
Letztes Jahr habe ich auch die gleiche Vorlesung gehalten, deswegen,
wenn Sie letztes Jahr anhören, ist es die gleiche.
Aber ich versuche so gut wie möglich ihn zu vertreten.
Also letztes Kapitel war Graf-Algorithmen, dann hat Herr Schmeck die
Modellierung, die wichtigsten Begriffe und verschiedene Graf-Probleme
betrachtet.
Und die Sicht hier war von der Informatik-Sicht, weil viele von diesen
Graf -Problemen wissen von Operations Research oder Mathematik
-Vorlesungen, aber hier war der Fokus mehr auf die Informatik-Sicht.
Informatik-Sicht bedeutet zum Beispiel die Komplexität des Verfahrens
oder was passiert, wenn Sie mehr als einen Prozessor zur Verfügung
haben.
Wie können Sie das effizient darstellen?
Und dann, das erste Problem war diese Erreichbarkeits-Matrix.
Und für diese Erreichbarkeits-Matrix haben wir diese Warschalls
-Algorithmus.
Und Sie sehen, also in den Warschalls-Algorithmus, Sie haben diese
dreifache Schleife und das ist ähnlich wie Matrix-Multiplikation, aber
hier sind die Reihenfolge anders.
Und dann hat er auch die Parallel-Variante betrachtet und auch Befehls
-Systole -Array, das war hier diese Instruction-Systole-Array und dann
die Dijkstra und alle Wege zum Ford-Algorithmus und er hat auch dann
kurz betrachtet, ob Mapping-Ansatz für diese Warschalls-Algorithmus
direkt anwendbar ist oder nicht.
Und dann hat er gesagt, dass da hier jetzt keine Uniform
-Abhängigkeiten sind, ist dieser Mapping-Ansatz nicht direkt
anwendbar.
Also ich habe auch wie letztes Jahr diese Capital ein bisschen
erweitert, ein paar mehr Folien hinzugefügt und ich kann vielleicht
einmal durchgehen.
Das war diese Erreichbarkeits-Matrix und in der Erreichbarkeits
-Matrix, dieser direkte naive Ansatz hat die Komplexität n hoch 3 log
n.
Das wissen Sie, wie das funktioniert?
Wie man von n hoch 4 runter auf n hoch 3 log n kommt?
Das wissen Sie alle, ja?
Weil das ist auch eine typische Klausurfrage.
Dann,
das war die Folie von Herr Schmeck.
Das war meine Erweiterung von letztes Jahr.
Also diese Transitive-Folie, wir können auch durch Matrix
-Multiplikation verrechnen.
Und das ist dann ein Zusammenhang zwischen dieser Matrix
-Multiplikation, die Methoden, die Sie vorher gelernt haben, die haben
auch Anwendung hier in Graphen-Algorithmen.
Und Sie können auch in realer Matrix-Multiplikation, das ist c als
Produkt von a mal b, das ist wie hier definiert.
Hat jemand eine Idee, wieso das File nicht funktioniert?
Ja, okay, dann verwende ich das nicht.
Und zwar, es ist hier definiert, cij, das ist dieser Skalar-Produkt.
Aber Sie können auch diese Matrix Tg, das war diese
Erreichbarkeitsmatrix, berechnen, indem Sie von dieser Adjacent-Matrix
Ag, das ist die Adjacent-Matrix von dieser Graph G, und Sie können
das, das ist diese Summe berechnen, Ag hoch 1 plus Ag hoch 2 plus plus
plus Ag hoch n minus 1.
Und dann am einfachen Ende durchgehen und dann dieses zweite Teil
prüfen, ob die Elemente größer als 0 sind oder nicht.
Und dann am Ende diese boolische Vergleiche, am Ende diese logischen
Vergleiche, bekommen Sie entweder 0 oder 1.
Und das ist tatsächlich die Erreichbarkeitsmatrix, die Sie vorher von
diesen naiven Ansätzen, entweder von den naiven Ansätzen oder von den
Wachstumsalgorithmen direkt berechnet haben.
Sie können auch diese Tg ein bisschen anders darstellen, indem Sie nur
einmal potenzieren brauchen, und das ist diese, Sie können auch das
genaue Tg auch so schreiben, dass Sie sagen, dass diese Identität
-Matrix I plus Ag hoch n minus 1 minus I und dann die gesamte Matrix,
die ich hier bekomme, die haben Integerwerte und dann nochmal habe ich
diesen Vergleich, ob die Elemente größer als 0 sind oder nicht.
Und anhand von dieser logischen Operation bekomme ich dann am Ende 0
oder 1.
Und die beide sind dann gleich wie die Tg, die Erreichbarkeitsmatrix,
die Sie von den vorherigen Folien berechnet haben.
Kann jemand hier erklären, wieso soll hier diese Tg, die
Erreichbarkeitsmatrix, wieso ich die Erreichbarkeitsmatrix auch so
berechnen kann, von Adjacent-Matrix?
Weil
es adliere, dann kann man
reichen, dass man die 2 Punkte erreichen kann.
Und wenn ich dann nur die kurzen 0 gebe, dann kann ich am Ende die
überhaupt erreichen.
So Ag hoch die Elemente, Ag hoch K zum Beispiel, die Elemente dort
bedeuten, die Anzahl der Wege, die Länge K, die in dieser Graph
möglich sind.
Und am Ende diese bullische Vergleiche, das macht nur, weil sie
interessieren, nicht über die Anzahl der Länge, sondern nur über das
Endergebnis, ob die überhaupt erreichbar sind, erreichbar ist oder
nicht, ob die 2 Knoten erreichbar sind oder nicht.
Und den zweiten Teil kann ich auch, den zweiten Teil Tg, Sie können
auch das mathematisch beweisen, das ist gleich als Tg.
Aber man hat auch eine andere Erklärung, wenn Sie...
Okay, das war die Erklärung, was die Koeffizienten von einer Potenz
von Ag bedeuten.
So die Koeffizienten von Ag hoch K geben die Anzahl der Wege, die
Länge K, zwischen I und J.
Und wenn ich aber anstatt diese Ag potenziere, anstatt diese Matrix,
wenn ich auch diese zweite Matrix potenziere, I plus Ag, So was
bedeuten die Koeffizienten, meine Frage ist hier, was bedeuten die
Koeffizienten Ey, der Matrix I plus Ag gesamt hoch K.
Das steht nicht hier auf der Folie.
Ja, das ist der Einheit Matrix.
Okay, was bedeutet die Koeffizienten Matrix Ag, das sind entweder 0
oder 1, ob eine direkte Verbindung zwischen zwei Knoten gibt oder
nicht.
Und wenn ich diese Einheitsmatrix dazu addiere, dann...
Selbst, ja, das ist nicht der Fall, in den Graphs sind keine Zyklus,
keine dieser...
Aber wenn ich I plus Ag, das bedeutet, dass die Wege von der Knote I
nach I, das ist auch jetzt möglich, zumindest habe ich es so
definiert.
Und dann, wenn Sie das Matrix potenzieren, zum Beispiel K, I plus Ag,
die beiden Matrixen, hoch K, dann ein Element Ey von dieser Matrix
bedeutet, die Anzahl, die Wege, die Länge, K oder kleiner als K sind.
Weil dadurch Sie haben diese Identitätsmatrix hinzugefügt haben, das
heißt, dass jetzt, wenn Sie potenzieren, dann ist es auch möglich,
dass Sie mehrfach durch diese selben Knoten laufen und dann, das gibt
dann die Gesamtanzahl der Wege, die Länge 1 haben können, 2, 3 bis zum
K.
Das ist der Unterschied, ja.
Und das ist auch dann, die zweite Theorie ist dann auch dadurch
erklärbar, dass jetzt diese Tg, I plus Ag hoch n-1, die Elemente
dieser Matrix geben die Anzahl, die Wege 1, 2, 3 bis zu n-1 und dann
einfach am Ende vergleichen Sie, ob die Elemente größer als 0 sind
oder nicht und dadurch bekommen Sie auch das selbe Ergebnis.
Ich habe ja auch als ein Beispiel hier hinzugefügt, das ist dieser
einfachste Graph, das mit 4 Knoten an 4 Kanten und von dieser
Adjacentmatrix, wie die dann potenzieren kann und am Ende, wie die von
dieser Gesamtmatrix die Erreichbarkeitsmatrix berechnen kann.
Das war dann die Folie von Herr Schmeck, das war der
Warschalsalgorithmus, der Aufwand dort war n hoch 3 und jetzt
vielleicht können Sie alles vergleichen.
Was war der Aufwand hier in den naiven Ansatz?
Also wir haben diese G1, diese Problem der Bestimmung der
Erreichbarkeitsmatrix von G, ein Graph G und der Aufwand, der naive
Ansatz war n hoch 3 mal log n.
Der Aufwand, dieser kluge Ansatz war n hoch 3 und das Verfahren, das
ich jetzt hier vorgestellt habe, das ist diese Verwendung von
Matrixmultiplikation, dann ist der Aufwand gleich wie der Aufwand der
Matrixmultiplikation und das ist dann noch weniger als n hoch 3.
So das ist dann ein noch besseres Verfahren, das unbedingt hier
schwächen müsste.
Für diese Warschalsalgorithmus, für diese Dreifache Schleife, habe ich
auch diese Folie 9 und 10 hinzugefügt.
Das ist auch ein Beispiel, wie die tatsächlich eine solche Matrix oder
diese Potenzierung direkt anhand von dieser Matrix berechnen können.
Und die Idee ist hier, wie können sie Wk aus Wk-1 konstruieren und
indem sie nur die Spalte k betrachten, die gleich 1 sind und die
Reihen und die Seilen k betrachten, die sie 1 sind und dann setzen sie
alle Paare, alle mögliche Kombinationen 1.
So hier sehen sie zum Beispiel, sie haben diese W0, das ist die
Adjacentmatrix dieser Graph und hier sehen sie, dass in die erste
Spalte, k ist 1, in die erste Spalte ist das zweite Element 1 und in
die erste Reihe ist das zweite Element ungleich 0, 1.
Und jetzt von dieses 2 und 2, haben sie wie viele Kombinationen?
Einfach eine Kombination, 2,2.
Und dann setzen sie deswegen in W1 die Element 2,2 auch 1.
Und das ist dieser Teil hier.
Und dann von dieser W1 sehen sie, dass in der zweiten Spalte sind die
ersten zwei Elemente ungleich 0 und in der zweiten Reihe sind die
ersten drei, 1,2,3, die Elemente sind ungleich 0.
Und wie viele Paare können sie von hier bilden?
Das sind insgesamt 6 Paare.
1,1,1,2,1,3,2,1,2,2,2,3 und alle Elemente setzen sie jetzt 1.
Und deswegen sehen sie, dass der 1,3, der hier 0 war, wird jetzt auch
1 gesetzt.
Und am Ende bekommen sie von diesem solchen Verfahren auch diese
Erreichbarkeitsmatrix TG.
Das ist ein einfaches Beispiel, wie sie direkt diesen
Wahrsteinsalgorithmus verwenden kann, auch mit Stift und Papier,
anstatt ein Programm zu schreiben.
Das war auch eine genaue Klausuraufgabe in 2011 oder so.
So, das war auch diese Extrafolie, die ich hier hinzugefügt habe.
Dann habe ich auch hier jetzt ein Beispiel von direkt Satzalgorithmus
hinzugefügt.
Das ist nur für ein detailliert genauer Verständnis, da können Sie
einfach durchgehen.
Und hier, Herr Schmeck hier, das war die letzte Folie, der hat
versucht zu erklären, ob der Mappingansatz zu diesem
Wahrsteinsalgorithmus direkt anwendbar ist.
Ich war nicht hier in der Vorlesung, aber soweit ich gehört habe, hat
er gesagt, dass da jetzt keine Uniformabhängigkeiten sind.
Ist dieser Mappingansatz nicht direkt verwendbar.
Das ist etwas enttäuschend, weil dieses Wahrsteinsverfahren hat so
viel Ähnlichkeit mit Matrixmultiplikation.
Und wenn für die Matrixmultiplikation schon hunderte von Varianten
möglich sind, von diesem Mappingansatz, wieso kann das hier nicht
sein?
Und deswegen habe ich auch erweitert, noch eine Folie hier
hinzugefügt.
Und das ist, dass es doch möglich ist, diesen Mappingansatz zur
Berechnung der Transitive-Rolle, also es ist doch möglich, den
Mappingansatz zu nutzen für diese Berechnung der Transitive-Rolle.
Und das ist ganz interessant.
Und dafür haben wir auch diese gleiche Matrixmultiplikation.
Und das ist die gleiche reale Matrixmultiplikation.
Und ich habe vorher gezeigt und auch versucht zu erklären, dass wieso,
wenn Sie die Transitive-Rolle anhand von dieser Matrixmultiplikation
berechnen, Tg, dann wie können Sie die Transitive-Rolle berechnen.
Und jetzt, die Sache ist, dass Sie können indirekt Mappingansatz schon
nutzen, indem Sie sagen, dass die Transitive-Rolle ist einfach eine
Potenzierung von einer geeigneten Matrix.
Und diese Potenzierung, für diese Potenzierung können Sie dann, für
diese Potenzierung von Matrixmultiplikationen, diese Sie können dann
anhand von diesen geeigneten, effizienten, systemischen Algorithmen
nutzen oder den Mappingansatz nutzen.
Und Sie sehen, das war am ersten Folien, ich denke, hier, in die
sechste Folie, Sie sehen, dass wenn Sie Tg durch wiederholte
Matrixmultiplikationen berechnen, dann brauchen Sie insgesamt log n
Matrixmatrixen zu multiplizieren.
Deswegen war dieser Aufwand hier n hoch 3 mal log n.
Und hier,
deswegen die Matrixen, die Sie multiplizieren mit dieser log n
Matrixmultiplikation, jede Matrixmultiplikation, für jede
Matrixmultiplikation können Sie einen Standardansatz nutzen, zum
Beispiel der Straßenansatz zum Beispiel.
Und dann, dadurch können Sie insgesamt die Komplexität reduzieren auf
einer Seite und auf der zweiten Seite können Sie auch dann den
Mappingansatz nutzen.
Und das ist zum Beispiel hier, wenn Sie das berechnen, das ist die
Komplexität zum Beispiel reduziert von n hoch 3 mal log n zum, ja,
diese beste, bestmögliche Koeffizient mal log n.
So, das heißt, das O of n hoch, wir nehmen an, 2.37 mal log n.
Und wenn wir hier betrachten, dass, ja, das, wir nehmen an, das ist
das bestmögliche, 2.37.
Die weitere, das malige, das lassen wir jetzt weg.
Und dann, wenn Sie mit log n multiplizieren, dann sehen Sie, das ist
schlechter als, ein bisschen schlechter als 2.37, aber jedoch besser
als zum Beispiel 2.37001.
Das wissen Sie, dass der log n wächst asymptotisch langsamer als jeder
beliebige Exponent von n.
Und der zweite Teil hier, hier ist der Extraaufwand hier, in dem
Extraaufwand müssen Sie insgesamt an alle Elemente durchgehen, um zu
sehen, welche Elemente ungleich null sind.
Und dann, die Aufwand, das ist auch, das sind n-quadrate Elemente, und
das ist auch dann n hoch 2, und deswegen läuft das gesamte Verfahren
auch in diese n hoch 2.37 mal log n.
Aber es sind trotzdem jetzt in den letzten Jahren, es sind auch
verschiedene Artikel, die haben auch das verbessert, indem dieser log
n -Term weggefallen ist.
Das heißt, dass das Schlussergebnis, dass die Berechnung, die
Transitive Fülle, ist gleich komplex wie die Matrixmultiplikation.
Aber was hier ist trotzdem etwas anders als der Warshall's
Algorithmus, wenn ich zeige hier die Komplexität n hoch 2.37, dann
bekomme ich auch die Gesamtanzahl 10 mal z.B.
n hoch 2.37,
und hier soll betrachtet werden, dass die Operationen sind hier ein
bisschen anders, als was die Operationen in diesem Warshall's
Algorithmus direkt sind.
Die Operationen hier sind dann die arithmetische Operationen, und die
Operationen in dem Warshall's Algorithmus sind die bitweise
Operationen, und das ist der Unterschied.
Aber unter der Annahme, dass die beide gleich Zeit kosten, ist dieser
Ansatz schon viel besser als die anderen Ansätze.
Ich denke, vor zwei Jahren, als ich diese Vorlesung gehört habe, oder
diese Transitive Fülle Berechnung überlegt habe, dann hatte ich auch
diese Idee, dass vielleicht kann man diese Matrixmultiplikation
verwenden, und ich dachte, ja, das ist toll, und vielleicht hat ja
niemand das gemacht, aber dann habe ich doch Artikel gefunden, in
denen die Autoren haben das gleiche Sache gemacht.
Es ist trotzdem interessant, dass manchmal die Methoden von anderen
Bereichen, von diesen anderen Problemen, z.B.
das algebraische Problem, die können auch hier verwendet werden, für
diese Graph-Algorithmen.
Und deswegen, für diesen Mapping-Ansatz, das finde ich sehr
interessant.
Auf einer Seite ist das nicht anwendbar, auf der anderen Seite ist es
anwendbar.
Das war auch ähnlich für diese boolische Matrixmultiplikation.
Auf einer Seite ist es nicht anwendbar, dass die Operatoren keine
inverse besitzen, aber auf der anderen Seite, durch diese reale
Matrixmultiplikation, ist es doch anwendbar.
Hier ist auch das ähnlich, nur ist das anders, dass wenn wir eine
Aussage über die Verwendbarkeit des Mapping-Ansatz sagen wollen, dann
hier ist anwendbar, das gleiche, reale Matrixmultiplikation, aber auf
die andere, auf die vorherige Folie.
Es ist nicht anwendbar, und das ist nicht wegen inverse oder
ähnlichem.
Der Grund hier ist nicht der gleiche, wie
der Grund für die Nicht-Verwendbarkeit Straßens-Algorithmus für diese
boolische Matrixmultiplikation, sondern der Grund hier ist, dass
dieses Modell nicht uniform ist.
Und von diesem Mapping-Ansatz her brauche ich unbedingt ein uniformes
Kostenmodell.
Uniforme Abhängigkeiten, ja.
Ja, das war's dann, was ich für diese Graph-Algorithmen sagen sollte.
Ich kann auch diese erweiterte Version hochladen, PDF.
Und
dann sind wir in dieser vorletzten inhaltlichen Kapital, und das ist
algorithmische Geometrie.
Welche Bild hier bezieht sich auf diese Kapital?
Das kann auch eine klasse Frage sein.
Eine Warm-Up-Question.
Ja,
also das hier, diese Fisch-Ausstattung, das ist die Methode für diese
algorithmische Geometrie.
Ach nee, algorithmische Geometrie.
In dieser algorithmischen Geometrie, also das Thema ist, dass wir
wollen diese geometrischen Probleme effizienter lösen.
Und jetzt haben wir immer noch eine Informatikschicht.
Das heißt, wir wollen so effizient wie möglich ein Verfahren
entwickeln.
Und es sind verschiedene reale Anwendungen für diese algorithmische
Geometrie, bzw.
die Verfahren, die ich für diese algorithmische Geometrie brauche.
So zum Beispiel, wie kann man eine Galerie oder ein Museum oder
Geschäfte überwachen.
Das dann habe ich zum Beispiel,
wenn ich nur eine konvexe, zum Beispiel dieser Raum, das ist nicht
konvex, diese Ecke ist ein bisschen, das ist die Nicht-Konvexität.
Aber wenn ich eine konvexe Geometrie habe, dann reicht zum Beispiel
Platzierung, irgendwo in der Mitte eine Videokamera, die überall
überwachen kann.
Das heißt, ich brauche nur eine Kamera, eine Videokamera, um den
gesamten Raum zu überwachen.
Aber wenn Sie zum Beispiel diese Raum, für diese Raum, wie viele
Kameras brauchen Sie, wenn Sie die gesamte Nicht-Konvexe Raum
überwachen wollen?
Trotzdem nur eine.
Hier ist keine Kamera, oder?
Wo?
Das ist dann ein bisschen komplexer, dieses Problem.
Aber das macht Sinn für die Nicht-Konvexität, für diese Nicht-Konvexe
Szenarien, wie viele Kameras ich brauche.
Das ist auch eine Wirtschaftlichkeitsaspekte.
Das kann auch dynamisch sein.
Es sind auch Szenarien, in denen diese Geometrie dynamisch verändert
ist.
Es kann auch sein, ich habe mehrere Fußgänger, die sind in einer Panik
-Situation.
Ich kann auch in der Lage sein, die gesamte dynamische Situation zu
überwachen.
Und dann habe ich auch kein erwartetes Problem.
Dann sind auch Probleme, zum Beispiel, welche Punkte sind die größten,
bzw.
die kleinsten Abstände in einer gegebenen Punktmenge?
Alle diese Fragestellungen, die Sie hier sehen, sind sehr elementar.
Das ist wie 1 plus 2 gleicher als 3.
Aber sie haben verschiedene Anwendungen in verschiedenen Bereichen,
zum Beispiel diese Geographical Information Systems oder Ähnliches.
In anderen Bereichen auch.
Welche Objekte zum Beispiel überschneiden sich?
Das kann auch interessant sein.
Wenn die Objekte überhaupt überschneiden, wie groß ist die
überlappende Fläche?
Das ist auch interessant.
Nicht nur von der Fragestellung, sondern auch von der Optimierung.
Das ist ein ganz anderer Bereich.
Und dort habe ich auch diese verschiedenen Rechtecken.
Und dann muss ich irgendwie berechnen, wie groß die gesamte Fläche
ist.
Und anhand dieser Berechnung kann ich auch sehr effiziente
Multikriteriale -Optimierung-Probleme lösen.
Das ist auch eine große Anwendung.
Und es gibt auch andere Probleme, zum Beispiel ob ein Punkt innerhalb
eines gegebenen geometrischen Objekts liegt oder außerhalb.
Oder zum Beispiel die Berechnung der konvexen Hülle.
Das braucht man in tausenden von Applikationen.
Oder wie kann ich ein Puzzle effizient lösen?
Effiziente lösen hier bedeutet die minimale Anzahl der Schritte, die
ich brauche.
Oder wie kann ich den nächsten Teil suchen, zum Beispiel.
Und viele von diesen Problemen, die haben dann...
Es ist sehr einfach für viele von diesen Problemen im
zweidimensionalen Raum unterzusuchen.
Aber in mehreren Dimensionen, normalerweise sind die Probleme viel,
viel komplexer als die zweidimensionalen Szenarien.
Und hier zum Beispiel, das ist auch ein Problem, der heißt...
Klee-Major-Probleme, das ist auch ein Problem zum Beispiel.
Sie haben mehrere Intervalle, die realen Nummer zum Beispiel.
1, 2, 2, 3, 1.5, 7.5, das sind die Intervalle.
Und wie ist die gesamte Länge dieser Intervalle?
Das ist zum Beispiel auch ein eindimensionales Problem.
Und für dieses zweidimensionale Problem würde das zum Beispiel sein,
ich habe Rechteck.
Und wie ist die Gesamtfläche dieser vorhergegebenen Rechteck?
Wie ist die gesamte Fläche oder in allgemeiner Dimension?
Und in allgemeiner Dimension, wie ich gesagt habe, das ist auch sehr
interessant, auch für Optimierung.
Das ist mein Forschungsthema.
Aber dort ist auch dieses Verfahren sehr relevant.
Und dort kann man auch sagen, zum Beispiel zeigen, dass die in
allgemein, in zweidimensional, sind fast alle Probleme in maximaler
NlogN.
Wenn nicht NlogN, dann in N² Zeit immer los war.
Aber in allgemeiner Dimension, wenn Sie diese Dimension Rd betrachten,
dann sind allgemein auch viele von diesen Problemen NP schwer.
Oder die brauchen exponentielle Zeit.
Was wir hier leider nicht betrachten, ist die Konstruktion mit Zirkel
und Linear.
Das ist von dieser klassischen Geometrie, jugendliche Geometrie.
Das ist auch sehr interessant, was kann ich machen, wenn ich nur diese
Zirkel und Linear zur Verfügung habe.
Zum Beispiel, ich kann einen Winkel halbieren, aber ich kann einen
Winkel nicht in drei gleiche Teile zerlegen.
Und was wir hier betrachten, ist wie kann ich ein Programm schreiben,
oder wie kann ich durch eine Lösung ein geeignetes Programm,
beziehungsweise wie kann ich ein Verfahren entwickeln, das nur diese
arithmetische und logische Operationen macht und dann ein Problem
löst.
Der einfachste Grund hier ist, dass Sie nicht direkt mit Zirkel und
Linear in einem Rechner arbeiten können.
Aber alle Eigenschaften, die Sie mit Zirkel und Linear haben, können
Sie geeignet modellieren.
Und dann können Sie auch diese klassische Frage, ob Sie einen Winkel
zum Beispiel in drei gleiche Teile trisektieren können.
Ist trisektieren ein deutsches Wort?
So was kann sein, was ist dann ein deutsches Wort?
Ein Teil, in drei Teile ein Teil.
Das können Sie auch zeigen mit Beweis, aber Sie können auch das
geeignete, diese Zirkel und Linear irgendwie in den Computer
modellieren.
Und dann sind auch verschiedene Beweise, die sind diese Computer
Assisted Proofs.
Das heißt, Sie können auch das Rechner nutzen, um diese klassische
Frage zu beantworten, aber das ist nicht die Sache, die ich hier in
diesem Kapitel betrachte.
Um diese algorithmische Geometrie, wir betrachten die elementare
geometrische Objekte.
Punkte, ja, sind einfach, die Punkte sind in eine die-dimensionale,
euclidische Räume definiert.
Gerade, das sind diese eindimensionale Teilmenge der euclidischen
Raumide.
Und die sind gegeben durch einen Punkt und eine Richtung oder durch
zwei Punkte, das sind die eindimensionale Teilmenge.
Die Punkte sind dann diese nulldimensionale Teilmenge.
Und dann kann ich auch zum Beispiel Linien definieren, das sind
gegeben durch Anfang und Endpunkt, das ist eine Teilmenge dieser
Geraden.
Und dann eine Hyper-Ebene, das ist auch eine die-eindimensionale
Teilmenge der euclidischen Raum.
Aber ich kann auch verschiedene kleine Dimensionen betrachten.
Polygon, also die Polygon, wir nehmen an hier, dass die Polygon, wir
haben die Polygon, das ist eine geschlossene Kantenzüge im
zweidimensionalen euclidischen Raum.
Und nicht nur das, wir nehmen an, das ist das, es ist uns
vorhergegeben durch eine Folge von Eckpunkten.
Und das ist eine Annahme, die wir hier in diesem Kapitel verwenden,
weil ich kann auch sagen, dass ich zum Beispiel nur die Eckpunkte
vorhergegeben habe und nicht in welche Reihenfolge.
Aber um eine Polygon zu definieren, brauche ich auch nicht nur diese
Punkte, sondern auch eine Reihenfolge.
Wir sehen später, woran das entscheidend sein kann.
Und dann kann ich auch Polyeder, Polytop und auch in mehrere
Dimensionen betrachten.
Wie gesagt, die Algorithmen in höheren Dimensionen, die sind dann
viel, viel komplexer als in zwei oder in drei Dimensionen.
Aber hier in diesem Kapitel brauchen wir nur die Grundidee zu
vermitteln und deswegen reicht auch dieses zweidimensionale
euclidische Raum.
Modellierung, wie modelliert ist und was sind die Problemgrößen?
Bei Punktemenge brauche ich nur die Punktemenge und dann muss ich nur
diese Punktemenge speichern und dann sage ich, dass die Problemgröße
die Anzahl der Punkte ist.
Bei Geraden, das sind die Anzahl der Geraden und bei Polygon sind die
Anzahl der Eckpunkte.
Wobei, ich nehme an, dass ich auch die Reihenfolge der Eckpunkte weiß.
Welche Datenstruktur?
Das sind sehr,
sehr wichtig.
Es gibt auch spezielle Vorlesungen über Datenstruktur.
Es gibt auch allgemeine Vorlesungen über Datenstruktur, aber es gibt
auch spezielle Vorlesungen nur über Datenstruktur für solche Probleme.
Datenstruktur für diese Probleme von algorithmischer Geometrie.
Und allgemein habe ich dann, wenn ich eine Menge habe, dann kann ich
auch eine Array speichern.
Aber allgemein sind viele von diesen Problemen in der Bounce-Struktur
gespeichert.
Da ich mit dieser Bounce-Struktur normalerweise in Log-Endzeit eine
Kante löschen kann und auch addieren kann und auch verschiedene andere
Möglichkeiten.
Diese Bounce-Struktur bietet eine vielfältige Möglichkeit.
Und dazu haben wir auch dann verschiedene spezielle Bounce zum
Beispiel.
Zum Beispiel diese R-Bounce, das ist auch sehr bekannt für solche
Probleme.
Wir betrachten nicht die Datenstruktur hier in dieser Vorlesung, aber
es ist nur, dass wir wissen, dass es eine spezielle Datenstruktur
gibt.
Baumbasierte insbesondere für diese algorithmische Geometrie.
Aufwandabstrichung, das sind die Komplexitätsmaße.
Das sind wie üblich, Zeitaufwand oder die Anzahl der arithmetischen
oder logischen Operationen, die ich brauche.
Platzaufwand.
Wir haben auch die Maße für parallele Algorithmen, zum Beispiel wenn
ich mehr als einen Prozessor zur Verfügung habe, dann sind auch diese
Effizienz, Skalierbarkeit und ähnliche Sachen, die sind in der letzten
Folie in Kapitel 2 gesehen.
Aber zusätzlich, nur für diese algorithmische Geometrie, sind auch die
Zeitquantenvorbereitungen sehr wichtig.
Weil es kann sein, dass wenn ich zum Beispiel das gleiche Problem
mehrfach lösen, irgendwie mehrfach einen veränderten Baum lösen will,
dann es mag auch Sinn sein, dass wenn ich auch etwas Zeit stecke in
Vorbereitung.
Und das ist ein extra Aufwand hier.
Und wir sehen, dass es kann sein zum Beispiel manchmal, dass wenn ich
mehr Aufwand in die Vorbereitung reinstecke, dann kann sein, dass ich
dieses Originalproblem schneller lösen kann.
In dem betrachten wir, ich denke, vier oder fünf Probleme.
Das erste Problem, AG1, algorithmische Geometrie-Problem 1.
Und das ist das Problem, dass ich habe gegeben, ein Endpunkt im
zweidimensionalen Euclidischen Raum.
Und dann ein, ja, ich kann diese Wörter nicht pronunzieren, das sind
diese axis-parallel-Restecken.
Und dann ist die Frage, wie viele Punkte der Menge, der vorgegebenen
Menge, liegen innerhalb dieser Resteck.
Das ist eine allgemeine, elementare Frage, die auch in verschiedenen
Anwendungen wichtig ist, aber erstmal nur diese Frage.
Zum Beispiel hier, als ein Beispiel, ich habe diese 8 plus 4, ja, 12
Punkte.
Und dann die Frage, dann habe ich diese Resteck.
Und meine Frage ist, wie viele Punkte jetzt liegen innerhalb dieser
Resteck.
Das ist ein sehr einfaches Problem, das können Sie nicht vergleichen
mit Matrixmultiplikation oder ähnliches.
Ein naiver Satz, der auch sehr sehr schnell ist, im linearen
Zeitaufwand.
Sie können alle Punkte überprüfen, ob die in der Resteck liegen kann
oder nicht, ob sie liegen sind oder nicht, ob sie liegen oder nicht.
Ja, dafür brauche ich Endzeit, also lineare Zeit.
Platz, hier ist das der Speicherplatz, ich muss alle Punkte speichern
und deswegen brauche ich auf jeden Fall einen linearen Platz.
Und Vorbereitung, hier ist keine Vorbereitung notwendig.
Das heißt, dass ich kann einfach überprüfen, ob die Punkte, die
Koordinate dieser Punkte, innerhalb dieser gegebenen Intervalle liegen
oder nicht.
Und das reicht, ja.
Und jetzt ist die Frage, wie kann ich diesen Ansatz verbessern.
Und dafür habe ich diese indirekte Beobachtung und das ist die Anzahl
der Punkte, die in der Resteck liegen.
So, wir sehen hier die Anzahl, das sind diese Koordinaten, diese
Resteck zum Beispiel, das ist diese x'y' zum Beispiel.
Die Anzahl der Punkte, die in der Resteck liegen, sind die Anzahl der
Punkte, die kleiner gleich diese oberen Eckpunkte sind.
So, hier kleiner gleich bedeutet, dass kleiner gleich in alle
Dimensionen.
So, das heißt, alle Punkte, die hier liegen, minus alle Punkte, die
hier liegen und dann minus alle Punkte, die hier liegen und dann, da
ich diesen Teil zweimal subjektiert habe, dann addiere ich nochmal.
Und dann sehen Sie, das ist ein indirekter, aber kluger Ansatz.
Wieso ist das besser, das sehen wir gleich.
Aber das ist, wir können auch diese Punkte-Frage, wir können auch
anhand, wir können auch diese Frage, wie viele Punkte innerhalb dieser
Resteck liegen, anhand von Lösung eine andere Frage, wie viele Punkte,
die kleiner gleich eine gegebene Eckpunkt sind.
Wir können auch dann viermal die Frage antworten und dann habe ich
auch mein vorheriges Problem gelöst.
Ja, hier steht, das Problem ist lösbar, das Problem AG1 ist lösbar
durch vier Punkt-Anfragen für die Eckpunkte der Restecks.
Und jetzt muss ich sagen, ob das besser ist oder nicht.
Und dann, jetzt wie ich vorhin gesagt habe, dass jetzt diese Aufwand,
den linearen Aufwand reduzieren, indem ich eine geschickte
Vorbereitung, ja, durch eine geschickte Vorbereitung.
Und das ist diese Vorbereitung, der ist zwar geschickt, aber nicht so
einfach zu verstehen.
Erstmal zerteile ich die Ebene durch diese Koordinatenlinie der Punkte
in ein Gitter.
Beziehungsweise eine Menge von Restecken.
Dann sehen Sie, dass hier sind die Punkte, für jede Punkte habe ich
jetzt diese, für jede Punkte habe ich diese Ebene zerteilt und dann
bekomme ich diese Gitter.
Und jetzt, ich kann auch gleich zeigen, dass dann habe ich insgesamt
weniger als n Koordinaten Restecken und kleiner gleich 4n
Außerrandflächen.
Ja, dann sehen Sie, dass für jede Punkt habe ich in alle Dimensionen
eine extra Randfläche.
Ja, und dadurch kommt diese 4n.
Der Aufwand für diese Zerteilung und alle, das ist dann der Aufwand
n², indem, wenn ich zerteile, dann nicht nur, ich bekomme auch die
Koordinaten für diese Punkte hier, die überkreuzt sind zum Beispiel.
Dann, der Teil 2 dieser Vorbereitung, ich berechne für jede Resteck,
für jede Resteck, die hier steht, auch die Resteck, in dem kein Punkt
liegt, oder auch die Resteck, der hat keinen Eckpunkt als die vorher
gegebenen Eckpunkte.
Und dann für jede Resteck berechne ich die Anzahl der Punkte, die
Anzahl der dominierenden Punkte, ja, das heißt die Anzahl der Punkte,
die kleiner gleich ein beliebiger Punkt in der Resteck sind.
So, ich spiele zum Beispiel hier in diese Resteck und dann berechne
ich, wie viele Punkte sind hier, wie viele Punkte hier sind
dominierend.
Auch für zum Beispiel den Punkt, für Resteck hier, dann bekomme ich,
wie viele Punkte liegen hier innerhalb in dieser großen Region, ja.
Der Aufwand hier ist auch n², da ist insgesamt, ja, es ist insgesamt
n².
Und wenn Sie naiv das machen, das ist der Aufwand hier viel größer als
n², da Sie jetzt insgesamt n² Resteck haben, aber es kann sein, dass
ein Punkt in mehrere von diesen Resteck liegen kann, ja.
Wenn Sie, wenn Sie für jeden Punkt überprüfen, ob in welche von diesen
n² Resteck liegt, dann ist der Aufwand vielleicht höher.
Aber Sie können auch hier zum Beispiel eine Dividend, nicht Dividend,
Konkurrent, dynamische Programmierung ansatz...
... indem Sie sagen, dass Sie betrachten nur eine dieser Linie und
dann gehen Sie durch, ja.
Das heißt, alle Punkte, die hier liegen, die von diesem Punkt
dominiert sind, sind auch zum Beispiel von diesem Punkt dominiert.
Und deswegen müssen Sie dann nicht das zweite Mal berechnen und das
ist dann dieser Schritt für Schritt dann, Sie können auch das zeigen,
dass der Aufwand für diese Berechnung Nummer zwei, das ist auch dann
n².
Wenn ich das gemerkt habe, dann kann ich die x-Koordinate der Punkte
sortieren und auch die y-Koordinate.
Der Aufwand dafür ist auch dann nlog n, für diesen Sortieraufwand.
Und dann meine Frage, dass wie viele Punkte sind kleiner gleich xy,
ein beliebiges xy, das kann ich antworten, indem ich einfach durch
binäre Suche diese Resteck bekomme, in dem dieser Punkt xy liegt.
Und für diese Resteck habe ich schon vorher die Anzahl der
dominierenden Punkte berechnet und dann gebe ich einfach diese Anzahl.
Und wenn ich diese Frage beantwortet habe, dafür brauche ich hier
diese binäre Suche, das läuft in log n Zeit.
Das heißt, dass ich kann in log n Zeit diese Frage beantworten,
das alle wiederhole ich viermal.
Und das heißt, in viermal log n Zeit kann ich diese Punktfragen
beantworten.
Und deswegen ist der Zeitaufwand hier dann log n.
Der Platzaufwand hier ist jetzt erhöht von n zu n², da ich alle
Resteck speichern muss bzw.
alle Punkte, die kleiner gleich eine beliebige Punkte in dieser Gitter
sind.
Und dann der Vorbereitungsaufwand ist auch hier n hoch 2.
Und dann sehen Sie, durch einen erhöhten Vorbereitungsaufwand und
Platzaufwand haben Sie jetzt den Zeitaufwand sehr runtergeschränkt.
Das ist auch dann in log n Zeit machbar.
Aber der Sinn hier ist diese Frage, wenn Sie eine Resteck vorher
bekommen haben und dann, wenn Sie diese Anzahl der Punkte ändern, das
heißt, jetzt haben Sie diese n Punkte und dann im nächsten Schritt
können Sie diese Punkte verändern.
Und dann können Sie das besser antworten.
Aber dadurch, was ich gesagt habe, nur für diese...
Also Sie müssen auf jeden Fall diese Resteck finden, in dem dieser
Punkt x, y liegt.
Ja?
Was n mal berechnen?
Das war dann der vorherige Aufwand, wenn Sie n mal berechnen.
Das war dieser lineare Aufwand.
Für jede Resteck, weil, wenn Sie...
Also entschuldigen, dann vorher, kurz, halbe Minute, habe ich etwas...
dieses genaue Problem habe ich anders erklärt.
Das Problem hier ist, ich habe diese Punkte, die vorher gegeben sind,
und die bleiben konstant.
Die verändern sich nicht.
Ich habe vor einer Minute gesagt, dass sie sich verändern, aber das
ist falsch, ich nehme das zurück.
Die Punkte sind vorher gegeben und jetzt verändern sich diese Resteck.
Das heißt, in der ersten Frage habe ich diese Resteck und dann gebe
ich eine Resteck und dann muss ich als Antwort bekommen, wie viele
Punkte in dieser Resteck liegen.
Und dann gebe ich nochmal eine neue Resteck und dann muss ich nochmal
diese Anzahl der Punkte berechnen.
Das heißt, dass die Wiederholung hier ist...
Also ich verändere diese Resteck immer, dynamisch zum Beispiel, also
in jedem Schritt.
Und dann, für jeden Schritt brauche ich nur noch Zeit, um zu bekommen,
wie viele Punkte innerhalb dieser Resteck sind.
Die Punkte sind hier fix.
Und da die Punkte hier fixiert sind, deswegen ist auch der Gitter, der
dadurch resultiert, das ist auch fix.
Und wenn diese große Resteck, die hier gezeigt ist, wenn diese Resteck
sich verändert, dann, trotz dieser Veränderung, habe ich es in Log-End
-Zeit geschafft, diese Frage zu beantworten.
Und das ist dann die genaue Erklärung.
Es ist eine kluge Ansage, aber wenn Sie diese Veränderung nicht haben,
dann vielleicht macht es auch keinen Sinn, diese kluge Ansage zu
verwenden.
Dann vielleicht reicht diese Lineare-Überprüfung und das war's.
Wenn Sie nur einmal berechnen wollen.
Die dominierte Punktmenge ändert sich ja nur, wenn auch dieser Gitter
vor einen Punkt liegt.
Das mag auch sein, aber dann...
Aber es ist so, aber dann, wenn Sie diese Lage bekommen, wenn Sie eine
Resteck bekommen, und dann müssen Sie für jede vier Ecken dieser
Resteck, müssen Sie diese Anzahl der dominierten Punkte, Sie sollen in
der Lage sein, für jede dieser Resteck diese Anzahl der dominierten
Punkte zu bewerben.
Das war diese Punktfrage.
Und dadurch diese Resteck verändern kann, das heißt diese Eckenpunkte,
diese Resteck können auch in diese beliebigen von diesen n² Resteck
liegen sein können.
Und um das zu bekommen, brauche ich für jede Resteck, nicht nur für
diese Resteck, in denen dieser Eckpunkt liegt, sondern nur für alle n²
Resteck, die Anzahl der Punkte, die kleiner gleich diese Punkte sind.
Sie sehen hier, die Frage hier ist, also meine Frage hier ist nur
diese Punktanfrage.
Das ist jetzt meine Frage, die ich betrachte.
Mal 4, wenn ich diese Frage antworten kann, dann antworte ich diese
Frage für diese 4 Situationen und dann bekomme ich die Lösung für
meine originale Frage.
Das ist die Idee.
Deswegen habe ich jetzt beschränkt nur auf diese Punktanfrage.
Und das ist dann meine allgemeine Punktanfrage.
Und dadurch kann ich auch sagen, ich habe diese Gitter, ich mache
meine Augen zu und mache hier diese Punkte.
Wie viele Punkte sind jetzt kleiner gleich diese Punkte?
Das heißt, ich muss in der Lage sein, dadurch die Resteck nicht vorher
bekannt ist bzw.
die Resteck sein kann, muss ich in der Lage sein, für jede beliebige
Resteck hier die Anzahl der dominierenden Punkte mitzuteilen.
Und deswegen brauche ich nicht nur für diese Punkte hier, sondern auch
für die insgesamten Punkte.
Es gibt eine geschickte Anordnung, in der Sie sagen können, wenn ich
nur die Anzahl der dominierenden Punkte für diese n Resteck berechnen
kann, dann anhand von dieser Information kann ich auch für alle n²
Elemente die Anzahl der dominierenden Punkte berechnen.
Es gibt auch diese Methode, das können Sie auch.
Aber dann ist der Aufwand jedoch der n².
Und deswegen, es macht Sinn, Sie können auch direkt die Anzahl der
dominierenden Punkte berechnen.
Weil wenn Sie so dieses Problem lösen, das heißt, wenn Sie nur für
diese n lineare Resteck die Anzahl der dominierenden Punkte berechnen,
dann müssen Sie auch extra diese Koordinaten der Punkte speichern.
Weil wenn Sie bekommen zum Beispiel, dass es liegt hier zum Beispiel 5
Punkte oder zum Beispiel hier 3 Punkte, dann müssen Sie auch sagen,
hier in der überlappenden Fläche, wie viele Punkte tatsächlich hier
liegen.
Das heißt, wenn Sie, was Sie vorher gemeint haben, dann so solvieren,
missolvieren, das ist lösen, dann müssen Sie mit extra Aufwand
berechnen, um dann diese überlappende Fläche auch irgendwie mit zu
betrachten.
Und dann ist der Aufwand auch nicht weniger als n².
Sie sind sehr begeistert, oder?
Jetzt können Sie auch hier, hier ist nicht direkt betrachtet, aber Sie
können auch überlegen, das ist nicht nur allgemein für diese
Verfahren, sondern allgemein für die Verfahren, die in dieser
Vorlesung behandelt sind, Sie können auch allgemein überlegen, was
passiert, wenn ich mehr als einen Prozessor zur Verfügung habe.
Kann ich das verbessern, oder nicht?
Oder ist dieses Verfahren inherent sequentiell?
Das ist auch die Frage, die Sie überlegen können.
Frage Nummer 2, bzw.
Frage Nummer 1, können Sie jetzt auch sehen, dass was passieren kann,
z.B.
wenn diese Rechteck nicht parallel ist zu diesen Äxten.
Das heißt, wenn ich Rechteck,
oder solch eine Rechteck, was können Sie dann ändern, bzw.
ist das auch dann lösbar oder nicht?
Solche Fragen müssen Sie dann auch, in diesen Fragen müssen Sie z.B.
etwas nachdenken.
Und solche Fragen, ein, zwei von diesen Fragen sind dann auch für die
Klausur relevant.
Und nur zwischen 1-0 ohne Bonus und 1-0 mit Bonus die zwei Gruppen zu
unterscheiden, weil am Ende ist es doch relevant, ob Sie 1-0 mit Bonus
bekommen haben oder ohne.
Das ist insbesondere auch relevant, wenn wir die Tutorials suchen.
Dann lege ich Wert, wenn jemand 1-0 ohne Bonus bekommen hat.
Das zeigt dann etwas mehr.
Aber hier z.B., was konnte ich hier?
Wie kann ich dann hier diese Probleme lösen?
Perfekt.
Und das geht auch dann in Vorbereitung.
Der Aufwand dafür ist?
Ja?
Für jeden Punkt müssen Sie in diesem transformieren.
Das heißt, Sie können auch das alles machen hier.
Das Verfahren bleibt gleich, der Aufwand bleibt auch, der
asymptotische Aufwand bleibt auch hier gleich, da hier der
Vorbereitungsaufwand mehr als linear ist und deswegen bleibt der
Asymptotische auch gleich und das ist auch okay.
Ja, dann kann ich auch mehr erweitern, was ich von dieser 3 hier habe
z.B.
oder Ähnliches.
Das sind auch die interessanten Fragen, die können auch das ähnliche
Verfahren nutzen, um diese anderen Probleme zu lösen.
Dann auch das zweite Problem, wir haben eine einfachste Polygon
gegeben.
Und meine Frage ist, ob ein Punkt innerhalb oder außerhalb von dieser
Polygon P liegt.
Und eine Polygon ist einfach, wenn der Albene in genau zwei Regionen
zerteilt.
Zwei distinkte Regionen, das heißt z.B.
diese Polygon hier ist nicht einfach, da sie von dieser Mitte nicht
sagen kann, ob das draußen ist oder drinnen.
Das heißt nur, diese Polygon teilt nicht die gesamte Fläche in zwei
distinkte Regionen.
Wir haben diese einfachste Polygon und dafür, die einfachste Methode,
ich habe einen Punkt hier z.B., diesen Punkt X und dann muss ich
beantworten diese Frage, ob dieser Punkt innerhalb oder
außerhalb liegt.
Liegt anscheinend innerhalb, ja.
Davor haben Sie diese Ray-Methode, diese Schale-Methode, die sehr,
sehr einfach ist.
Es gibt trotzdem hier auch Sachen, die Sie betrachten müssen, wenn Sie
das implementieren, das ist hier nicht betrachtet.
Aber in der Schale-Methode betrachte ich eine beliebige Gerade in eine
beliebige Richtung durch diesen Punkt Q.
Und ohne Beschränkung der Allgemeinheit kann ich auch sagen, das ist
diese horizontale Linie.
Und dann, ich bestimme nur die Anzahl der Schnittpunkte der Geraden
mit dieser Kante der Polygons auf dem Weg von Q in irgendwo eine
Richtung.
Z.B.
wenn Q hier liegt, dann ist diese Gerade durch Q und da sind diese
zwei Richtungen und ich kann in jede von diesen Richtungen einfach
gehen und dann kann ich nur bestimmen die Anzahl der Schnittpunkte.
Wenn die Anzahl der Schnittpunkte gerade ist, dann liegt Q außerhalb
von P. Und wenn das ungerade ist, dann liegt innerhalb von P. Und das
ist sehr einfach zu beweisen, das ist nur, wenn Sie außen sind, dann
erstmal in und das zweite Mal out.
Es wiederholt sich, in, out, in, out, in, out und deswegen ist
diese...
Ja, das ist das, was ich gesagt habe, es ist sehr, sehr einfach.
Aber wenn Sie das implementieren, dann müssen Sie sehr, sehr viel hier
betrachten.
Und z.B.
hier, nicht nur die Ecke, kann auch sein, dass dieser Punkt ist hier.
Und das ist der Gerade.
Es kann auch sein, wie viele Schnittpunkte sind hier.
Wie viele Schnittpunkte sind hier?
Das ist dann eine Special Case.
Oder wenn es hier ist, dann ist hier auch eins hinzugefügt, aber Sie
müssen das alles betrachten.
Und deswegen, wenn Sie das codieren, dann ist das sehr erweitert.
Aber es gibt eine Methode hier, die sagt, dass manchmal reicht nur die
Antwort, ob der Punkt sehr nah an dieser Polygon liegt oder nicht.
Das ist innerhalb dieser numerischen Toleranz.
Kann ich auch, ja.
Das kann auch sein, dass ich diese Gerade randomisieren kann.
Und dann kann ich dieses Problem vermeiden.
Aber dann brauchen Sie vielleicht mehr Aufwand.
Weil wenn Sie erstmal versucht haben, dann haben Sie bekommen, ja, es
gibt eine Szene, z.B.
hier.
Sie müssen erstmal versuchen, irgendwie.
Und was müssen Sie versuchen, das kommt genau.
Sie müssen irgendwie versuchen und nur wenn Sie einen Fehler oder eine
Ausnahmefälle entdecken, dann müssen Sie diese Gerade ändern.
Wie viel wollen Sie ändern?
Das ist da die Anzahl der Punkte, die hier aufliegen sind.
Und das hier reicht, wenn Sie eine zufällige Richtung wählen.
Und das sollte reichen, ja.
Und die, ja?
Wo?
Okay.
So, das ist zum Beispiel, ja.
Also hier 1, 2 und 3, ja.
Und 3 ist dann ungerade und deswegen liegt Q innerhalb von P, ja.
Ich überlege kurz, dass vielleicht solche Methode kann auch relevant
sein für diese Puzzle, ja.
Es gibt diese Puzzle manchmal, ja, in dem sie von einem Punkt außen
gehen will, ja.
Kann diese Verfahren auch dort relevant sein?
Ja, für die Labyrinth, ja, genau.
Vielleicht nur um zu wissen, ob sie draußen gehen kann oder nicht.
Ja, wenn Sie alles sehen.
Aber für dort, wenn es Labyrinths sind, auch dann bestimmte sehr gute
Verfahren.
Zum Beispiel, wenn Sie in eine Labyrinth rennen, ja, vielleicht das
geht.
Das ist nicht sehr schön in dieser Vorlesung, aber da Sie Labyrinth
gestoppt haben, ja.
Wenn Sie eine planare Labyrinth in eine planare Labyrinth befinden,
wie können Sie rausgehen?
Zum Beispiel, ja, das ist ein Beweis.
Man hat auch das, Sie können auch die gleiche Frage nehmen, ähnliches.
Und Sie können auch das erweitern, ja.
Und so macht man Studien, ja.
Zum Beispiel, Sie können auch sagen, dass ja, Sie können auch
vielleicht diese Labyrinth-Struktur transformieren.
Und dann, was ist die beste Strategie, wenn Sie an einem unbekannten
Ort sind, von dort irgendwie rauszugehen oder irgendwie die Wege zu
finden, ja.
Zum Beispiel, ich nehme Sie und setze Sie irgendwo in Paris und Sie
haben auch ein Ziel, ja.
Und jetzt hat er diese unbekannte Information.
Und wie können Sie die besten Strategien dort finden, ja.
Dort gibt es auch diese Studien.
Und solche Studien sind sogar einfach zu verstehen, aber die
Ergebnisse, die Strategien, die Wichtigkeit, es ist sehr wichtig.
Also nicht wichtig, aber es ist interessant.
Und Sie können auch dadurch in Nature oder diese sehr, sehr
hochrangigen Zeitschriften dort publizieren, ja.
Zum Beispiel eine einfache Studie, ja.
Oder welche Verfahren man nimmt, wenn man in einer Panik-Situation
ist, ja.
Das ist auch zum Beispiel, die Antwort, diese einfache Frage, sind
sehr, sehr wichtig.
Und die sind auch nicht nur in allgemeinen Zeitschriften publiziert,
sondern in der, in der besten, was es in der Forschung gibt, ja.
Für die Labyrinth ist leider das bekannt.
Sonst hätte es auch das so relevant.
Okay, dann kommen wir hier zurück.
Das war die Strahl-Methode.
Der Zeit-Tischbrauch, n.
Der Platz, n.
Vorbereitung, nicht.
Wenn ich sage hier, ich brauche lineare Zeit, das heißt zum Beispiel
Operationen, ja.
Eine Konstante mal n.
Was sind hier genau diese Operationen?
Also ich sage hier Komplexität, ja.
Da betrachte ich auch die Operationen, ja.
Und was ist genau diese Operation?
Hier.
Oder wieso kommt auch man linear?
Nicht n log n oder n hoch n oder, ja.
Wie können Sie begründen, ja?
Was ist genau diese Operation, ja?
Ja, die Kante.
Ja, perfekt, ja.
Wenn wir diese lineare Kante haben, das heißt jetzt, es ist einfach
eine zweidimensionale, diese lineare Gleichung, die wir lösen müssen.
Nicht schneiden oder nicht, ja.
Und das ist diese Operation, ja.
Und das ist sehr wichtig, welche Operationen Sie hier treffen.
Weil später sehen Sie, es kann auch sein, dass ich kann auch solche
Operationen vermeiden.
Und vielleicht kann ich noch bessere, einfache Operationen verwenden,
ja.
Zum Beispiel man kann auch in verschiedene Probleme, auch hier, Winkel
berechnen, ja.
Oder die Cosinus oder die Sinus von diesen Winkel berechnen, ja.
Wenn Sie das berechnen wollen, dann sind Sie in diese reale
Arithmetik.
Und dann müssen Sie auch die Genauigkeit anpassen, ja.
Aber wenn Sie irgendwie das verändern, dann können Sie auch nur mit
diesen natürlichen Zahlen arbeiten.
Und dadurch können Sie haben ein besseres Verfahren.
Es mag sein, dass die Komplexität gleich ist.
Aber von der Implementierung her kann ich trotzdem ein Verfahren
besser als das andere sein.
Auch die Vorbereitung ist nicht verbesserbar.
Vielleicht können Sie auch überlegen, wenn Sie mehr als einen
Prozessor haben, dann was können Sie besser schaffen oder nicht.
Und jetzt habe ich diese weitere Annahme, das P ist auch konvex.
Und jetzt ist die Frage, ob dann man vielleicht schneller als in
linearer Zeit hinkriegen kann, ob ein Punkt innerhalb oder außerhalb
dieser konvexen Polytope liegt oder nicht.
Und dann habe ich die Konvexität hier so definiert, aber man kann
diese allgemein definieren, aber man kann auch definieren, dass ein
Polygon konvex ist.
Das heißt, wenn ich in die Uhrzeigersinn durchlaufe, dann mag ich nur
Rechte bringen.
Und was heißt Rechte hier?
Zum Beispiel wenn ich hier 1 bin, Punkt 1, 2, dann werde ich das
erweitern in diese Richtung.
Und dann, der nächste Punkt ist bekommen, die Recht von dieser Gerade
oder dieser Halbgerade liegt.
Das ist diese Rechtsdrehung.
Und deswegen sehen Sie, dass diese nicht konvex ist, daher habe ich
Linksdrehungen.
Und die Eigenschaft, dann nutzen wir die Eigenschaft, die konvexe
Polygon, um vielleicht bessere Algorithmen zu sehen, ob ich diese
Frage in schnellerer Linearzeit antworten kann.
Und dann, das ist diese Eigenschaft, dass vor jedem Punkt R, der im
Inneren dieser konvexen Polygon liegt, und wenn ich eine Strahle, eine
Linie hier male, dann schneidet diese Linie, diese Polygon genau
einmal.
Und wie kann ich diese Eigenschaft nutzen?
Jetzt habe ich immer diese extra Vorbereitung.
Und in dieser Vorbereitung, ich bestimme erstmal einen Punkt im
Inneren von Polygon P, eine konstante Aufwand.
Und wie bekomme ich einen inneren Punkt?
Also ich habe diese Koordinaten, diese allen Punkte.
Ich benutze die geometrischen Mitteln, diese Koordinaten-Punkte zum
Beispiel, und dann bin ich automatisch.
Also ich brauche nur einen Punkt R im Inneren von P. Und dann, anhand
von diesem R und anhand von dieser vorgegebenen Polygon, das heißt,
dass die Eckpunkte und die Reihenfolge, ich kann diese Polygon in N
Sektoren teilen.
Ja, das steht hier.
Das ist kein extra Aufwand, da die Polygon schon als Reihenfolge der
Eckpunkte vorher gegeben ist.
Und dann, das ist die Vorbereitung-Aufwand, und dann habe ich dieses
Verfahren.
Ich habe einen Punkt Q, der innerhalb oder außerhalb dieser Polygon,
konvexer Polygon liegen kann.
Und dann suche ich erstmal für diesen Q, in welchem Sektor dieser
Punkt Q liegt.
Das ist auch durch binäre Suche in Log N Zeit machbar.
Jetzt können Sie sich überlegen, wie das genau funktioniert.
Und dann, wenn ich dieses Sektor gefunden habe, zum Beispiel, das ist
dieses Sektor S, dann muss ich irgendwie feststellen, ob Q innerhalb
dieses Sektors liegt oder außerhalb.
Und um das überzuprofen, muss ich sehen, ob Q links oder rechts vor
einer Gerade liegt.
Das heißt, ob Q rechts von dieser, in dem Sinne ist das links, ja.
Ob Q links oder rechts von dieser Gerade liegt, ja, das ist die
Operation.
Aber ich habe vor zwei Jahren nicht verstanden, wie kann man besser
erklären, was ist eine rechte Drehung und was ist eine linke Drehung,
ja.
Und dann habe ich jetzt verstanden, dass es immer in diese lange
Richtung, und immer gerade Nase in diese Richtung, und dann, ob das
links ist oder rechts, ja.
Man kann es auch anders definieren, ja, diese Definition.
Okay, um das festzustellen, ob Q rechts oder links von dieser Gerade
liegt, stelle ich dieses Verfahren hier, ja, aber bevor ich dieses
Verfahren schreibe, habe ich mein eigenes Verfahren hier, das nicht
hier steht.
Und das ist auch sehr einfach, weil wenn Sie vorher bekommen haben,
ja, diese Nummer 1, wenn Sie bestimmen haben, in welchem Sektor Q
liegt, dann muss ich nur betrachten, ob Q innerhalb oder außerhalb
liegt, ja.
Das heißt, dass ich habe auch diesen Punkt R,
ich habe diesen Punkt R,
ich habe diesen Punkt R, und ich habe auch diesen Punkt Q, dann habe
ich diese Strecke von RQ, und dann weiß ich auch diese Pi und Pi plus
1, und dann kann ich auch einfach feststellen, ob die sich schneiden,
überschneiden oder nicht, ja.
Wenn sie sich nicht überschneiden, dann heißt das, dass der Q
innerhalb ist, diese Polygon.
Wenn sie sich schneiden, dann heißt das, dass der Punkt außerhalb ist,
ja.
Um das festzustellen, das kann ich auch in konstanter Zeit, dann habe
ich auch diese zwei lineare Gleichungen und ich kann irgendwie
feststellen, ob das Punkt, ob die sich überschneiden oder nicht.
Das ist eine Möglichkeit.
Und die zweite Möglichkeit ist hier einfach diese
Lagebestimmungsmöglichkeit.
Und hier in die Lagebestimmungsmöglichkeit habe ich immer dieses
vorherige Problem, dass ich muss feststellen von RP, R Richtung Pi
-Vektor, ob Q links oder rechts liegt, ob die Drehung links ist oder
rechts.
Und dafür habe ich auch diese Determinante, einfache Determinante
-Berechnung.
Und anhand von dieser einfachen Determinante-Berechnung kann ich auch
bestimmen, ob Q innerhalb oder außerhalb, ja diese Polygon liegt,
beziehungsweise ob der Q rechts oder links von einer Geraden liegt.
Und dafür habe ich diese Punkte, diese allgemeine Situation R, P und
Q.
Und ich bezeichne diese Fläche, diese Trapez, erstmal die große, diese
Fläche.
Und dann nehme ich diese zweite Fläche, hier addiere ich.
Und dann von diesen zwei subtraktiere ich den Teil YIT, das heißt,
dass die Fläche hier subtraktiert ist.
Und dann bekomme ich die Fläche hier.
Und anhand von dieser Aussage, ob diese Fläche positiv ist oder
negativ, kann ich bekommen, ob Q rechts, ob eine linke Drehung ist
oder eine rechte Drehung.
Und diese Berechnung kann ich auch zeigen, ganz leicht, das ist auch
wie eine determinante Berechnung.
Und anhand von dieser Fläche, der Dreieck, das ist dieser Determinant.
Und anhand von diesem Sign von diesem Determinant, ob das positiv ist
oder negativ, kann ich auch einfach feststellen, ob hier eine linke
Drehung ist oder eine rechte Drehung.
Und sehen Sie hier genau, was haben Sie hier gemacht?
Sie brauchen nur, ob das eine linke Drehung ist oder eine rechte
Drehung.
Sie brauchen mehr nicht.
Deswegen reicht diese einfache Berechnung.
Sie können auch alles gleich per Winkelberechnung bestimmen, ob das
Winkel positiv ist oder negativ.
Aber wenn Sie das Winkel berechnen, dann sind diese arithmetischen
Operationen dort aufwendiger als diese einfachen Operationen hier.
Und Sie sehen auch, was ich vorher gezeigt habe, hier, einfach gesagt
habe, der hier nicht steht.
Um festzustellen, ob das Kuh innerhalb oder außerhalb liegt, kann ich
auch diese zwei Linien zeigen, ob sie sich schneiden oder nicht.
Die Operation dort ist einfach eine Gleichungoperation.
Und dann, anhand von dieser Gleichungoperation, kann ich auch
feststellen, ob es einen Common Point gibt oder nicht.
Das heißt, das ist die Methode.
Das ist auch konstante Zeit.
Aber die Operation ist ein bisschen anders als die Operation, die Sie
hier sehen.
Und das braucht auch eine konstante Zeit.
Und die dritte Methode wäre eine Winkelberechnung.
Das ist auch im Prinzip eine konstante Aufwahl.
Aber von der Arithmetik her, ist es aufwendiger als die Verfahren, die
hier geschrieben werden.
Und was ich auch vorher gesagt habe, dass anhand der Determinante, ob
die Fläche positiv oder negativ ist, zum Beispiel hier ist die Fläche
positiv, aber wenn es hier wäre, dann ist die Fläche negativ.
Und anhand von dieser positiven oder negativen kann ich auch sagen, ob
es eine Linkdrehung ist oder eine Rechtsdrehung.
Und Aufwand, ja, ist Aufwand.
Wir kommen zurück zu dieser Verfahren, die hier in der vorherigen
Folie und in dieser Folie beschrieben ist.
Der Aufwand hier ist Log N.
Und das ist der Aufwand für Lagebestimmung.
Das war die binäre Suche.
Weil der Extraaufwand, um nur diese Determinante zu berechnen, das ist
dann konstant irgendwie.
Sie können sagen, ob das konstant ist, oder Sie können auch sagen,
dass vielleicht das braucht zwei, drei Multiplikationen und
Reduktionen hier.
Aber das ist jeweilig eine konstante Zahl, ja.
Und die Vorbereitung ist auch konstant, weil ich nehme an, dass der
Polygon als eine Folge von Kante vorher gegeben ist.
Und deswegen ist das kein Extraaufwand, ja.
Wenn Sie das nicht wissen, ja, wenn ich sage, dass okay, ich gebe
Ihnen nur N Punkte, N Eckepunkte und ich sage, dass von diesen N
Eckepunkten eine konvexe Polygon möglich ist, ja.
Nur die Information, dass es gibt eine konvexe Polygon, der durch
diese N Punkte beschrieben werden kann, ja.
Aber der Reihenfolge gebe ich nicht, ja.
So, das ist dann eine extra Frage, ja.
Wie kann ich dann diese gleiche Frage beantworten, ob ein Punkt Q
innerhalb oder außerhalb von dieser konvexen Polygon liegt oder nicht?
Wie hoch ist der Aufwand dann?
Dann ist der Aufwand...
Oh, fast vorbei.
Okay, dann ist der Aufwand, der Extraaufwand, Sie müssen das
sortieren, um die richtige Reihenfolge zu bekommen.
Das heißt, dann ist der Aufwand anscheinend N log N.
Aber Sie können dann genau überlegen, ob Sie mit diesem Signal das
gleiche Verfahren verwenden oder nicht.
Oder vielleicht dann die Strahlenmethode, die in linearer Zeit läuft,
ob das schneller sein kann oder nicht.
Ja, dann die Frage 3, ob ein Polygon einfach ist oder nicht.
Diese Frage ist auch hier auf die Folie beantwortet, aber wird von
Herrn Schmeck in der nächsten Vorlesung im Detail erklärt.
Vielen Dank für die Aufmerksamkeit.