Ja, schönen guten Tag!
Ich begrüße Sie zur letzten Sitzung der Vorlesung Effiziente
Algorithmen.
Letztes Mal haben wir uns mit algorithmischer Geometrie beschäftigt.
Und ich habe Ihnen ein bisschen was über die Probleme kurz erzählt,
die man dort behandelt.
Wir haben...
Er mag mich jetzt nicht.
Er mag mich nicht.
Lassen Sie mich das...
Sehr seltsam.
Nochmal.
Jetzt mag er mich.
Ja.
Wir haben die verschiedenen Objekte angeguckt, die dort beachtet
werden oder behandelt werden.
Also von Punkten bis zu Polygonen oder Polytopen oder was immer.
Und wir schauen uns halt...
Wir haben uns der Reihe nach angeschaut, haben uns mit kurz wieder den
erforderlichen Datenstrukturen ganz kurz beschäftigt.
Aufwandsabschätzung ist völlig klar, wie man das macht.
Und dann haben wir verschiedene Probleme angeschaut.
Ich habe das hier mit AG 1 bis 4 bezeichnet.
Die verschiedenen typischen Probleme bei algorithmischer Geometrie.
Das erste sind halt so Punktaufgaben.
Und wir hatten uns angeschaut, wie man eben feststellen kann, wie
viele Punkte in so einem vorgegebenen Rechteck sind.
Wir hatten gesehen, dass man das ein bisschen anders darstellen kann
über sogenannte Punktanfragen.
Und dann in der Lage ist, mit einer entsprechenden Vorbereitung dafür
zu sorgen, dass eine explizite Anfrage für ein Rechteck in Zeit Log N
geht.
Wobei man allerdings einen ganz quadratischen Aufwand reinstecken muss
in die Vorbereitung, um das tatsächlich möglich zu machen.
Dann hatten wir die Probleme, festzustellen,
ob ein Punkt innerhalb oder außerhalb eines einfachen Polygons liegt.
Da haben wir diese Strahlmethode angeschaut, festgestellt, bei
konvexen Polygonen geht das einfacher.
Und sie freuen sich, weil sie nochmal an das Beispiel mit Australien
dachten wahrscheinlich, gerade eben, man braucht immer so typische
Beispiele, um sich klarzumachen, was eigentlich das Wesentliche ist.
Jetzt bei den konvexen Polygonen haben wir gesehen, das geht deutlich
einfacher.
Und dann musste man immer noch feststellen, liegt ein Punkt eigentlich
links oder rechts von einer Geraden?
Und das Problem kann man eben auf völlig unterschiedliche Art und
Weise lösen.
Man kann es rein mathematisch anschauen und da versuchen, irgendwelche
Abstände rauszufinden.
Dann haben wir gesehen, das braucht man überhaupt nicht, sondern es
reicht eigentlich, sich diese Überlegung zu machen, dass man die
Fläche eines Rechtecks bestimmt, bzw.
eigentlich nur feststellt, ist sie positiv oder negativ.
Und diese Fläche ist nicht Fläche eines Rechtecks, sondern Fläche
eines Dreiecks, das aufgespannt wird von den drei Punkten, also zwei
Punkten auf der Geraden und der Punkt, von dem man wissen will, ob er
links oder rechts liegt.
Und dann stellt man fest, es geht nur darum, festzustellen, ob eine
Determinante einer Matrix aus drei, also einer 3x3 Matrix, positiv
oder negativ ist.
Und das ist mit relativ wenig Aufwand auszurechnen.
Man braucht also keinerlei trigonometrische Funktionen auszurechnen,
keine realwertigen Operationen.
Das reicht hier, es sei denn, man hat realwertige Koordinaten.
Aber es reicht eben einfach, diese Abschätzung zu machen, ist dieser
Wert positiv oder negativ?
Und dann hat man die Basisoperation für diese Bestimmung, ob jetzt ein
Punkt innerhalb oder außerhalb eines konvexen Polygons liegt, schon
erledigt.
Und dann kam die Frage, Voraussetzung war immer, dass Polygon einfach
ist.
Wie kann man das eigentlich feststellen?
Das hängt damit zusammen, wie wir feststellen können, dass sich
irgendwelche vorgegebenen Liniensegmente überschneiden.
Und an dem Beispiel habe ich Ihnen dieses Planesweep-Verfahren
vorgestellt.
Das ist ein algorithmisches Prinzip, das man bei geometrischen
Problemen anwendet.
Und
darüber...
Lassen Sie mich ganz kurz mal gucken, ob das hier auch wirklich
aufgenommen wird.
Irgendwas stimmt hier heute nicht.
Die...
Ich bin mir nicht sicher, ob aufgezeichnet wird.
Es wird aufgezeichnet.
Das wird aber anscheinend nicht angezeigt heute in meiner Leistung
hier unten.
Ich war etwas irritiert.
Ist aber in Ordnung.
Hier war also das Problem, wie stelle ich fest, ob sich zwei
Liniensegmente überschneiden.
Und dann festgestellt, das kann man machen mit so einem Planesweep,
indem man im Prinzip ein zweidimensionales Problem reduziert auf eine
Folge von eindimensionalen Problemen.
Und diese eindimensionalen Probleme kann man lösen über eine Art
Suchproblem, das man dann mit Aufwand jeweils log n lösen kann.
Und dann hat man n mal einen Aufwand von log n zu treiben und ist dann
damit...
Irgendwas ist hier heute nicht in Ordnung.
Ich weiß nicht, was hier los ist.
Tut mir leid.
Irgendwas hakt hier.
So, wir hatten uns angeguckt, wie wir das Problem auf ein
eindimensionales Problem reduzieren können.
Wir hatten dann diese Operationen und Haltepunkte angeschaut und
festgestellt, wir können das mit n log n Aufwand machen.
Und jetzt kommen wir endlich zum Problem, das wir uns heute anschauen
wollen.
Nämlich zum
Problem...
So.
Da sind wir wieder in der Vorlesung.
Tut mir leid.
Deutlich verspätet.
Wir hatten eine technische Unterbrechung.
Jetzt geht's weiter und wir wollen uns endlich damit beschäftigen, wie
wir die konvexe Hülle bestimmen können.
Und...
Ja, konvexe Hülle.
In der Punktmenge schauen wir uns das an.
Das ist unsere Punktmenge, die konvexe Hülle.
Da geht's halt darum, den kleinsten Bereich festzustellen, der alle
Punkte enthält.
Die kleinste konvexe Teilmenge der euclidischen Ebene, die alle diese
Punkte enthält.
Und es ist klar, dass wir dann eben eine Menge von Extrempunkten
bestimmen müssen, bzw.
das konvexe Polygon, das den Rand dieser konvexen Hülle bildet.
Darum geht's, das zu bestimmen.
Das heißt, wir müssen einerseits die Extrempunkte bestimmen und wollen
dann auch noch die Reihenfolge haben, sodass wir genau einmal um diese
Menge herumlaufen können.
Deswegen wollen wir das konvexe Polygon bestimmen, die Menge, die zu
den Extrempunkten gehören, und ihre Reihenfolge, sodass wir dieses...
den Rand tatsächlich als Polygon bekommen.
So.
Die Frage ist, wie macht man das?
Und ich stelle Ihnen jetzt mehrere Algorithmen vor, mit denen man das
machen kann.
Dabei werden jeweils unterschiedliche Eigenschaften konvexer Mengen
ausgenutzt.
Also was man hier einfach nochmal lernt an diesem Fall oder an diesem
Beispiel der konvexen Hüllenbestimmung, ist, wie man mathematische
oder geometrische Eigenschaften eines Problems hier ausnutzt.
Ich zeige einfach hier, dass man verschiedene Arten, verschiedene
Ansätze wählen kann, um dieses Problem zu lösen und man bekommt
Algorithmen mit völlig unterschiedlichen Eigenschaften.
So.
Der erste Ansatz, da geht es darum, wenn ich dieses konvexe
Hüllenproblem lösen möchte, nutze ich jetzt diese eine Eigenschaft
aus, die relativ einfach ist.
Wenn ich also einen Punkt habe, x, der in einem Dreieck liegt, aus
anderen Punkten, dann ist das mit Sicherheit kein Extrempunkt.
Also dieser Punkt x hier kann kein Extrempunkt sein, weil er in einem
Bereich liegt, der von den Punkten P, Q und R aufgespannt wird.
Wenn ich also jetzt feststellen möchte, welche Punkte sind
Extrempunkte, ist ein Ansatz festzustellen, liegt ein Punkt in einem
Dreieck aus drei anderen Punkten.
Das kann ich für alle Punkte feststellen, diese Eigenschaft
überprüfen.
Das heißt, ich muss in dem Fall für jeden Punkt von M überprüfen, ob
er in solch einem Dreieck liegt.
In irgendeinem Dreieck.
Irgendein Dreieck, muss also alle möglichen Dreiecke in der Punktmenge
mir anschauen.
Und die Punkte, die in keinem Dreieck aus drei anderen Punkten liegen,
sind dann offensichtlich Extrempunkte.
Also P, Q und R selber liegen nicht in einem Dreieck.
Nur das X.
Also die Eckpunkte selber zählen nicht mit dazu.
Bitte?
Selbstverständlich.
Das, was wir jetzt machen müssen, ist selbstverständlich, dass wir
dass wir für die Verbindung, also um festzustellen, ob er innerhalb
des Dreiecks liegt, müssen wir feststellen, ob er eben links oder
rechts von diesen drei Linien liegt.
Wenn er in dieser Reihenfolge immer auf der richtigen Seite liegt,
dann wissen wir, er ist im Dreieck oder entsprechend außerhalb des
Dreiecks.
So, und die Kanten muss ich natürlich dann auch entsprechend anordnen.
Ich weiß dann also, welche Punkte sind Extrempunkte.
Dann habe ich also hier meine irgendwelche Extrempunkte.
Jetzt die Frage, wie bestimme ich das Polygon?
Dazu muss ich, wähle ich einfach irgendeinen Punkt R im Inneren.
Es wird ja wahrscheinlich mindestens einen Punkt geben, der nicht
Extrempunkt ist.
Oder wenn alle Punkte Extrempunkte sind, dann nehme ich einfach
irgendeinen Punkt hier drin.
Also ich nehme an, ich habe hier irgendeinen Punkt, den wollte ich
jetzt R nennen.
Und von diesem Punkt R aus kann ich jetzt die Strahlen hier zu diesen
anderen Punkten nehmen und kann die radial sortieren.
Bis auf diesen einen Punkt R.
Und habe damit die Reihenfolge der Punkte für das Polygon, das die
Konvexehülle bestimmt.
Und der Aufwand ist klar.
Der erste Aufwand hier, das ist Aufwand O von n hoch 3, weil wir n
hoch 3 mögliche Dreiecke haben.
Und diese Anordnung der Punkte, das ist ein Sortierproblem n log n.
Also hier ist das nochmal angegeben.
Und dass wir hier die Berechnung der Winkel durch die Berechnung der
Determinanten wieder ersetzen, das ist klar, das ist unsere
Basisoperation.
n mal n hoch 3 macht n hoch 4 als Aufwand.
Der Aufwand hier für Sortieren, für h Extrempunkte ist h log h.
Insgesamt der Aufwand n hoch 4, wahnsinnig viel.
Das werden wir sicherlich nicht als Algorithmus akzeptieren.
Es sei denn, wir sagen, wir können ja hier, wir können alle diese
Operationen in Punkt A, die können wir parallel ausführen, die sind
unabhängig voneinander.
Dann könnten wir die im Prinzip, wenn wir also genügend parallele, ja
genügend parallele Ausführungseinheiten zur Verfügung haben, könnten
wir mit n hoch 3, mit n hoch 4 Prozessoren, also n mal n hoch 4
Operationen gleichzeitig ausführen, hätten wir dafür konstanten
Aufwand und mit dem entsprechenden, also PRAM Modell, hätten wir das
in konstanter Zeit erledigt.
Aber mit einem sehr hohen Parallelitätsgrad.
N mal n hoch 3 Bitte?
n ist die Anzahl der Punkte in meiner Punktmenge.
Ja, aber hier ist letzte n, also Wo, von n hoch 3 Nein, nein, n hoch 3
pro Punkt.
Ja, und wir haben n Punkte.
Also das ist eine ganz einfache Über-den-Daumen-Abschätzung.
Es ist klar, die Anzahl der Operationen ist hier exorbitant hoch.
Aber das wäre eine Möglichkeit, das zu machen.
Das wären voneinander unabhängige Operationen, die man hier ausführen
würde.
So könnte man also eine Basis machen für einen parallelen Ansatz.
Aber ich glaube, es ist klar, dass wir das nicht unbedingt so machen
werden.
Zweiter Ansatz.
Gram-Scan aus dem Jahr 1972.
Das ist also ein Ansatz, der häufig ausgeführt wird.
Es wird häufig angewandt.
Was macht man hier?
Wir sortieren unsere Punkte nach ihren Polarkoordinaten.
Wir haben also unsere Punktmenge.
Jetzt will ich die sortieren nach ihren Polarkoordinaten.
Das heißt, ich nehme hier irgendeinen Punkt her.
Völlig egal, irgendeinen Punkt.
Und jetzt sortiere ich die nach ihren Polarkoordinaten.
Jetzt sieht man, dass wir hier...
Das sieht alles sehr schön aus.
Das kann eventuell zu Problemen führen.
Es könnte sein, dass hier Punkte im Prinzip in der gleichen...
also auf einem Strahl liegen.
Mehrere Punkte drauf liegen.
Das schließt man alles aus.
In den theoretischen Annahmen.
Wenn wir genauer hier hingucken, nehmen wir an, dass es immer so schön
aussieht, dass die alle voneinander getrennt sind.
Dass da jeweils unsere Punkte liegen.
Vielleicht auch irgendwo hier.
Aber dass es nicht auftreten kann, dass auf einem solchen Strahl
mehrere Punkte liegen.
Das wird ausgeschlossen.
Da wählen wir uns irgendeinen Punkt, der im Inneren liegt.
Wir können uns irgendwie wahllos drei Punkte herausgreifen.
Oder zwei Punkte und den Mittelpunkt.
Oder drei Punkte und den Mittelpunkt dieser drei Punkte wählen.
Oder wir können auch irgendeinen von diesen Punkten nehmen, der im
Inneren liegt.
Und zu diesem einen Punkt ist alle anderen anordnet.
Auch das ist möglich.
Also das kann man auf jeden Fall so sortieren.
Ich möchte nur gleich darauf hinweisen, dass, wie man an diesem Bild
hier oben schon sieht, dass eine sehr dichte Menge ist.
Diese Polarkoordinaten können sich eventuell nur ganz marginal
unterscheiden.
man kann das aber im Prinzip so machen.
Man kann die entsprechend sortieren.
Und jetzt bestimmt man die Folge der Extrempunkte durch eine
kreisförmige Bewegung um den Ursprung.
Also der Ursprung ist hier unser Zentrum, von dem aus wir diese
Polarkoordinaten bestimmt haben.
Jetzt gehen wir also zum ersten dieser Punkte.
P1.
Und gehen weiter.
Das ist also irgendein zweiter Punkt, P2.
Und ein nächster Punkt, P3.
Die sind ja alle angeordnet.
Wir haben hier unsere Anordnung, meinetwegen in dieser Kreisanordnung,
so um den Ursprung herum.
Dadurch habe ich eine Reihenfolge aller meiner Punkte.
Und es kann also so eine Situation auftreten.
Punkte P1, P2, P3.
In diesem Fall wäre das eine Linksdrehung.
Das heißt, es sieht so aus, als wäre P2 ein Extrempunkt.
Was wir haben wollen, sind die Extrempunkte.
Wenn wir da durch das Polygon herumlaufen, haben wir immer
Linksdrehungen, wenn wir so in dieser Drehrichtung insgesamt
herumlaufen.
Das wäre eine Linksdrehung.
Und der Winkel Alpha, in dem Fall ist dieser Winkel hier gemeint.
Der ist konvex.
Wir machen anschließend weiter mit P2, P3, P4.
Falls P3 ungleich P ist.
Das war hier unser Anfangspunkt, bei dem wir angefangen haben.
Wir wählen hier einen sicheren...
Wie wählen wir den sicheren Extrempunkt P?
Wir können den wählen mit der niedrigsten Koordinate.
Der, der die kleinste Koordinate hat.
Wir wählen ihn in die Y-Richtung.
unter denen nehmen wir den linkesten Punkt.
Den mit der kleinsten X-Koordinate.
So kann man einen sicheren Extrempunkt als erstes auswählen.
Von dem aus geht man weiter.
Wenn das P3 schon wieder der Punkt wäre, wären wir fertig.
So.
Wir nehmen also an, wir haben mindestens drei Punkte hier drin.
Sonst macht das gar keinen Sinn.
So.
Dann haben wir so eine Linksdrehung.
Im Prinzip könnte P2 ein Extrempunkt sein.
Dann könnte es sein, dass wir...
dass diese drei Punkte auf einer Linie liegen.
Wenn die auf einer Linie liegen, dann ist P2 kein Extrempunkt, weil P2
auf der Verbindung liegt zwischen P1 und P3.
Deswegen brauchen wir P2 nicht, um diese konvexe Hülle zu bestimmen.
Dann löscht man P2.
Also dann ist P2 kein Extrempunkt.
Und wir können weitermachen mit irgendeinem fiktiven weiteren Punkt.
Also wird mit P1, P3, P4 weitergemacht.
Das heißt, wir behalten dann P1 bei, wir behalten P3 bei, P2 wird
gelöscht und machen weiter.
Wenn wir
diese Situation haben, P1, P2, P3, eine Rechtsdrehung, dann ist dieser
Winkel Alpha ist Konkav, also größer als 90°.
Und dann ist es völlig klar, P2 kann kein Extrempunkt sein.
Deswegen können wir P2 streichen aus der Menge der möglichen
Extrempunkte.
Ja?
Größe von 180°.
Größe von 180°, Entschuldigung, selbstverständlich.
Natürlich.
Und wir haben also dann P2 gestrichen, weil P2 garantiert kein
Extrempunkt ist.
Die Frage ist, wie müssen wir dann weitermachen?
Wir hatten ja vorher P1 als möglichen Extrempunkt gespeichert.
Das war also nach dem, was wir bisher gesehen hatten, ein potenzieller
Extrempunkt.
Jetzt haben wir P2 gestrichen und haben eine Verbindung von P1 nach
P3.
Wieso müssen wir dann mit P0, P1, P3 weitermachen?
Das heißt, nochmal zurückgehen.
Es könnte ja folgende Situation auftreten, die male ich jetzt mal hier
hin.
P0, P1, P2, P3.
Wir sind von P0, P1, P2, da sind wir rübergelaufen, haben gesehen, wir
haben eine Linksdrehung, haben also P0, P1 und P2 als potenzielle
Extrempunkte, gehen anschließend von P1, P2 P1, P2, P3 gehen da rüber,
stellen fest, das ist eine Rechtsdrehung.
Wir müssen also P2 streichen, haben deswegen jetzt diese Linie
anzugucken und stellen fest, jetzt ist dieser Winkel hier, dieser
Winkel, auch konkav.
Das heißt, wir müssten jetzt diesen Punkt ja auch noch rausstreichen
und hätten nur noch den ersten Punkt und den letzten hier hinten als
potenzielle Extrempunkte, müssten also im Prinzip, wenn wir
weitermachen, wieder zurücklaufen, es sei denn, wir wären schon am
Ende.
Das heißt, wir müssen hier zurückgehen, weil es sein kann, dass durch
das Löschen von P2 und Annahme als potenziellem nächsten Extrempunkt
nach P1, das ist jetzt der Punkt P3, da könnte es eben sein, dass der
Winkel zwischen P0, P1, P3 eventuell konkav wird und deswegen müssen
wir das überprüfen.
Es könnte sein, dass P1 gestrichen werden muss.
Also, wir laufen durchgehend durch alle Punkte durch, führen eine
Liste potenzieller Extrempunkte.
Jeden Punkt, den wir hier angucken, nehmen wir dort zunächst einmal
auf und dann kann es sein, dass wir so einen Punkt eventuell wieder
löschen müssen, weil wir feststellen, wir haben nicht eine
Rechtsdrehung, sondern eine Linkdrehung.
Andersrum, nicht eine Linkdrehung, wie hier gewünscht, als konkaver
Winkel zwischen den drei aufeinander vorliegenden Punkten, sondern
eine Rechtsdrehung, das heißt eine...
keine Linkdrehung, das heißt konvex, sondern eine Rechtsdrehung, das
heißt konkaven Winkel.
So.
War das verständlich?
Dass wir auf diese Art und Weise hier vorgehen können.
Und das, was wir hier ausnutzen, ist halt, dass alle inneren Winkel
zwischen aufeinander folgenden Kanten eines konvexen Polygons,
konvexe, kleiner als 180°, und das heißt, das ist hier die wesentliche
Eigenschaft, die wir ausnutzen.
Warum ist das N-Log-N?
Wir müssen gehen?
Okay.
Warum ist das Ganze N-Log-N?
Der erste Punkt.
Wir sortieren die Punkte nach ihren Polarkoordinaten.
Das ist der Aufwand N-Log-N.
Danach gehen wir durch alle Punkte durch und das ist lineare Aufwand.
Ja, wir haben pro Punkt nur linearen Aufwand.
Jeder Punkt wird einmal in die Liste aufgenommen und dann eventuell
noch einmal rausgenommen.
Aber der Aufwand ist insgesamt linear für Punkt B.
Das heißt, der Gesamtaufwand ist N-Log-N, wegen dieses anfänglichen
Sortierens.
Das Problem...
Ich muss nochmal auf die Folie zurück.
Ein Problem, das hier auftritt, darüber muss man sich einfach im
Klaren sein.
Wenn wir eine ganz grobe Menge haben, wo nur wenige Punkte auftauchen,
ist das kein großes Problem.
Da können wir diese Polarkoordinaten ganz gut bestimmen und die auch
sortieren.
Wenn wir aber eine relativ dichte Menge haben, da ist eben diese
Annahme, dass keine zwei Punkte koordiniar sind, hier bei diesem
anfänglichen Sortieren.
Diese Annahme ist einfach nicht zulässig.
Beziehungsweise man könnte natürlich sagen, wenn ich hier feststelle,
zwei Punkte sind koordiniar, dann streiche ich einen sofort raus.
Auf diese Art und Weise könnte ich hier schon Punkte rausstreichen.
Das Problem ist aber, jetzt liegen hier irgendwie mehrere Punkte ganz
dicht nebeneinander.
Und dann kann es sein, dass ich einfach die Reihenfolge nicht mehr per
Exakt bestimmen kann.
Einfach aus Rechenungenauigkeitsgründen kann es sein, dass bei der
Abschätzung liegt ein Punkt links oder rechts.
Also wenn ich hier mein...
Also das ist hier ein Punkt, da ist noch ein Punkt und der nächste
Punkt liegt da.
Und dann liegt hier noch ein Punkt.
Liegen die...
In welcher Reihenfolge liegen die denn tatsächlich?
Man stellt fest, wenn man den Graham-Scan auf beliebigen Punktmengen
ausführt, dann werden leider in der Realität in solchen Situationen
eventuell falsche Reihenfolgen bestimmt.
Durch Rechenungenauigkeiten.
Bei einer größeren, gröberen Auflösung so eines Strahls habe ich hier
so ein Punktmuster und die Zuordnung, ob ein Punkt jetzt links oder
rechts von der Kante liegt.
Die ist nicht exakt.
Und bei so kleinen Abständen kann es zu Problemen führen, dass wir die
falsche Reihenfolge haben.
Wenn wir aber falsche Reihenfolgen der Punkte jetzt hier drin haben,
dann sind die Winkel, die wir hier oder diese Betrachtung, die wir
hier machen, nicht mehr richtig.
Die sind dann fehlerhaft.
Weil wir auf einmal völlig falsche Reihenfolgen hier drin haben.
Die nacheinander folgen betrachteten Punkte beziehen sich auf eine
andere Situation und wenn man das extrem anguckt, würde man in dem
Fall irgendwie so etwas angucken.
Ich hätte eigentlich, wenn ich diese drei Punkte anschaue, hier
nochmal hinmale, hätte ich sie eigentlich in der Reihenfolge anschauen
müssen.
Schaue sie aber in der Reihenfolge an, die hier aufgemalt ist.
Weil ich die Reihenfolgen falsch gespeichert habe.
Und das führt dann einfach zu falschen Berechnungen der konvexen
Hülle.
Ja.
Man kann es besser hinkriegen.
Bei diesem Verfahren ist es extrem anfällig für solche
Ungenauigkeiten.
Man kann dann versuchen, durch geeignete Veränderungen der Lage der
Punkte, solche Sachen rauszufinden und diese Fehler einfach zu
eliminieren.
Aber das ist ziemlich viel Aufwand und das Problem ist ja einfach,
wenn ich eine sehr dichte Menge habe, habe ich Schwierigkeiten, diese
Sortierung zu Anfang, Punkt A, wirklich exakt zu machen.
Sie haben eine Frage.
Ja, ich frage, wenn ein
Punkt rechts oder links der Linie liegt oder auch der Linie, dann kann
ich ja nicht genau bestimmen, ob er innen sei oder...
Haben Sie völlig recht, das ist auch fehleranfällig.
Aber nicht ganz so...
Ja, also diese Sortierung, da habe ich wesentlich mehr Linien, die
ganz eng beieinander liegen können.
Das ist einfach das Problem bei diesem Verfahren.
Es ist ein Punkt, den man sich nochmal genauer angucken könnte,
inwieweit hier für unterschiedliche Algorithmen für die Konvexe Hülle,
wie stark die jeweils anfällig sind für solche Ungenauigkeiten.
Es gab hier vor zwei Jahren einen interessanten Vortrag von Herrn
Mehlhorn vom Max-Planck-Institut für Informatik in Saarbrücken, der
sich mit diesen Ungenauigkeiten sehr systematisch beschäftigt hat und
dieses Beispiel, den Graham-Scan, genommen hat, um zu zeigen, welche
Probleme da auftreten können.
Und er hat dann eben gezeigt, wie man durch andere algorithmische
Ansätze, also durch gewisse Veränderungen, historische Veränderungen
der Lage der Punkte, dafür sorgen kann, dass diese Probleme aufgedeckt
werden und man zum richtigen Ergebnis kommt.
Noch eine Frage.
Ja, es waren die Punkte, die Sie nennen, die Sie brauchen.
Ja.
Richtig.
Man könnte im Prinzip, das wäre auch so eine Möglichkeit, wie man die
Abstände vergrößern kann.
Da müsst ihr aber eben alles...
Ja.
Das wäre auch ein Ansatz, das zu machen.
Ich wollte einfach nur...
Es ist vielleicht ein bisschen verwirrend, wenn ich Ihnen hier das
erste Mal so einen Algorithmus vorstelle für die konvexe Hülle und
gleich hinweise auf die Probleme, die in der Praxis auftreten können.
Aber ich mache das einfach.
Weil das...
Weil wir eben normalerweise hier mit gewissen Annahmen arbeiten über
die Gutartigkeit der Problemstellungen, die aber eben leider in der
Praxis nicht so auftauchen.
Und ich möchte also vermeiden, dass Sie jetzt sagen, ich habe ganz
tolle Algorithmen kennengelernt, die sind auch schön.
Das sind also mathematisch schöne Algorithmen.
Man stellt fest, wenn man das jetzt umsetzt in der Praxis, dann gibt
es auf einmal Probleme.
Und auf diese Probleme möchte ich Sie gleich hinweisen.
Da wird man sich überlegt, was mache ich denn mit solchen entarteten
Situationen.
So.
Jetzt stelle ich Ihnen einen anderen Algorithmus vor, der wohl weniger
anfällig sein wird.
Habe ich aber selber nicht wissenschaftlich untersucht, ob es
tatsächlich so ist.
Ich werde Ihnen aber sagen, warum ich das meine, dass der weniger
anfällig ist.
Was macht man bei diesem nächsten Ansatz?
Der sogenannte Jarvis Marge.
Der geht wie folgt vor.
Wir nehmen einen linkesten unteren Punkt als Startpunkt.
Das ist also hier unser Startpunkt oder in dem Fall ist es klar, da
finden wir sofort diesen hier.
Was machen wir?
Zu jedem aktuellen Punkt suchen wir einen Punkt PQ, sodass der Winkel
der Linie PQ mit der x-Achse minimal ist.
Das heißt, wir haben einen Punkt gewählt.
Gucken alle anderen Punkte durch.
Zu jedem Punkt bekommen wir einen Winkel mit der x-Achse.
Wir nehmen einfach den Punkt, der den minimalen Winkel mit dieser x
-Achse hat.
Im ersten Fall ist das klar, da kommen wir zu diesem Punkt.
Das ist der nächste Punkt P. Dann gehen wir von dem aus zu allen
anderen Punkten Entschuldigung, das ist jetzt schlecht gemalt.
Wir gehen von dem aus zu allen anderen Punkten
und stellen hier eben auch fest, das sind hier unsere ganzen Winkel.
Es ist klar, das hier ist der minimale.
Hier geht es also, müssen wir nur noch das Minimum bestimmen aus einer
Menge von möglichen Winkeln.
Und auch hier kann es natürlich wenn hier jetzt mehrere Punkte liegen
sollten, können wir hier auch wieder das Problem haben.
Das würde bedeuten, wir hätten am Rand hier eine sehr dichte Menge von
Punkten.
Und bei dem vorigen Algorithmus war es ja so, dass wir Probleme
hatten, wenn hier drin sehr viele sind.
Was sicherlich öfter auftreten wird, dass wir bei so einer Punktwolke
mehr Punkte haben, die bezüglich dieser Sortierung sehr zu diesem
Problem führen.
Das Problem wird hier nicht so sehr auftreten.
So gehen wir jetzt weiter zum nächsten Punkt, von dem aus auch wieder
den Punkt, der den kleinsten Winkel hat und so weiter.
Und so kommen wir sukzessive ganz um diese Menge herum.
Bestimmen auf diese Art und Weise alle Extrempunkte.
Den linkesten unteren Punkt, das ist kein Problem, dazu muss ich auch
nur Minimumbestimmungen machen.
Ich habe also pro Extrempunkt habe ich Größenordnung n Vergleiche,
weil es eine Minimumsbestimmung ist.
Dann wissen wir, dass wir dafür so viele Vergleiche brauchen.
Ich habe insgesamt am Ende h Extrempunkte.
Das kann sein, dass das sehr wenige sind.
Bei vielen praktischen Problemen wird es so sein, dass das vielleicht
sogar deutlich...
dass h sogar aus klein o von n liegt.
Nicht nur aus...
Das kann eine sehr kleine Zahl sein.
Kann sein, dass es eine Konstante ist.
Kann auch sein, dass es eine größere Zahl ist, vielleicht Wurzel n
oder sowas, aber auf jeden Fall liegt das in klein o von n.
Und der Aufwand liegt also irgendwie zwischen Omega von n und o von
n².
Wenn tatsächlich alle Punkte auf der konvexen Hülle liegen, dann habe
ich einen Aufwand von n².
Ansonsten hätte ich halt ein...
Wenn nur wenige Punkte Extrempunkte sind, kann es sein, dass ich einen
linearen Aufwand habe.
Das ist wieder nur die...
Auch wieder nur links oder rechts.
Ich muss das Minimum bestimmen.
Ja?
Und um das Minimum zu bestimmen, muss ich einfach nur vergleichen.
Liegt der Punkt links oder rechts von der Gerade, dann weiß ich, ob er
kleiner oder größer ist.
Wenn ich hier von Vergleichen rede, heißt das wieder, ich muss sehen,
liegt der Punkt links oder rechts, oder liegen die links...
Das ist einfach nur diese übliche Reihenfolgebestimmung.
Das ist unsere Basisoperation.
So, noch eine Frage.
Horizontal, das ist unsere x-Achse hier.
Alles bezogen auf diese Linie.
Sie können irgendeine Linie sich hernehmen.
Ja, ist völlig egal.
Ja, aber Sie haben das...
Das ist richtig, aber Sie müssen sich die Situation hier anschauen.
Selbst wenn ich hier drin, das nicht so sehr genau ist...
Ja, Sie können werden, aber trotzdem...
Also der Punkt, der hier außen liegt...
Natürlich, ich hatte gesagt, wenn hier viele Punkte liegen, an diesem
Bereich, dann wird das schwierig.
Aber wenn die Punkte nur hier drinnen dicht liegen und außen nicht
ganz so dicht, dann ist das Problem mit dieser Ungenauigkeit deutlich
geringer als bei dem Graham-Scan.
Ja, das ist einfach die Behauptung.
Und man kann hier sicherlich feststellen, unter welchen Situationen
das hier auch zu Problemen führt.
Aber die Anfälligkeit bei dem Jarvis-March ist deutlich niedriger als
bei dem Graham-Scan.
Noch ein Entwurfsprinzip.
Die beiden Konker.
Das eine war jetzt diese Berechnung mit den Dreiecken, das andere war
der Graham-Scan, wo wir systematisch alle durchgegangen sind mit
diesen Winkelbetrachtungen.
Dann haben wir jetzt den Jarvis-March.
Wir laufen einfach außenrum und schlagen immer so einen...
Also den nächsten Punkt, den wir da erreichen können, den nehmen wir
als garantiert nächsten Extrempunkt.
Und es ist klar, dass jeder Punkt, also wenn wir nochmal hier
zurückgehen, es ist klar, dass jeder Punkt, den wir hier dann als so
ein Minimum feststellen, jeder dieser Punkte ist garantiert immer ein
Extrempunkt.
Wir werden nicht das Problem haben wie beim Graham-Scan, dass wir
Punkte erstmal aufnehmen, von denen wir später feststellen, sie sind
doch kein Extrempunkt.
Nächster Prinzip.
Die beiden Konker.
Ja.
Können wir bei vielen Problemstellungen einsetzen, geht hier natürlich
auch.
Für eine kleine Punktmenge konstruieren wir einfach die konvexe Hülle
mit einem beliebigen Verfahren.
Das ist für eine konstante Größe ist das völlig egal wie man das
macht, das ist konstanter Aufwand.
Und wenn ich jetzt eine große Menge habe, dann teile ich diese Menge
in zwei etwa gleich große Mengen M1 und M2 auf.
Wie man die aufteilt ist völlig egal.
Das können Sie irgendwie nach der x-Koordinate machen, nach der y
-Koordinate oder sonst irgendwie.
Es sollen nur zwei etwa gleich große Mengen sein.
Irgendwie aufgeteilt.
Und dann bestimme ich die konvexe Hülle der linken oder dieser beiden
Mengen M1 und M2.
Also das ist jetzt hier mein M1, das ist meine Menge M2 und ich habe
dort jeweils die konvexen Hüllen gefunden.
Die können sich beliebig überlappen.
Die müssen nicht notwendigerweise so links und rechts angeordnet sein.
Kann aber sein, dass das so ist.
Jetzt muss ich diese beiden konvexen Hüllen zusammenpacken.
Ich muss die verschmelzen zu einer gemeinsamen konvexen Hülle.
Und es ist die Frage, wie mache ich das denn?
Also wie bestimme ich die konvexe Hülle der Vereinigungsmenge dieser
beiden konvexen Hüllen.
Ich kann ja alle inneren Punkte vergessen.
Welche Schnittpunkte wollen Sie nicht?
Schnittpunkte der konvexen Hüllen liegen dort und dort.
Die sind völlig uninteressant.
Ja?
Das ist die Frage.
Ich habe nur das Problem für die Extrempunkte der Mengen M1 und M2.
Die muss ich jetzt zusammenführen zur Menge der Extrempunkte für diese
konvexe Hülle von M.
Wenn ich Pech habe, liegen alle Punkte, also liegen auf der
Größenordnung N Punkte, auf diesen konvexen Hüllen.
Also wenn ich Pech habe, sind das immer noch sehr viele Elemente.
Ich habe sicherlich hier als Aufwand für als präkosiven Aufwand T von
N halber.
Das ist klar.
Ich habe ja halb so viele Elemente dort drin.
Das mache ich zweimal.
Und dann muss ich eben sehen, was passiert hier der Aufteilungsaufwand
und der Verschmelzungsaufwand.
Wie groß ist der?
Aufteilungsaufwand, das Aufzuteilen, maximal lineare Aufwand und das
Verschmelzen.
Wie kann ich das jetzt hinkriegen?
Die Behauptung ist, das geht in lineare Zeit.
Ja, aber wie wollen Sie das feststellen?
Wenn Sie jetzt jeden Punkt...
Sie haben diese beiden konvexen Hüllen.
Also ich...
Und Sie müssen jetzt feststellen, wie die ineinander liegen.
Sie dürfen ja nicht...
Also wenn Sie nur die Punkte haben, Sie wollen davon die konvexe Hülle
bestimmen.
Das könnten O von N Punkte sein.
Oder Omega von N Punkte sein.
Wir wissen, konvexe Hüllenbestimmung, da brauchen wir mindestens
Aufwand N log N.
Das wäre schlecht.
Wir dürfen nicht Aufwand N log N brauchen.
Wie würden Sie das machen?
Ich würde einfach die Linie entlang kaufen und immer, wenn ich
wieder rauskomme, lasse ich die Punkte.
Wie kriegen wir den Zoll hinab?
Funktioniert noch nicht genau.
Wenn dann der Punkt, der jetzt da unten ist unten, weiter hinlege und
lege, dann wäre das ja nicht konvex.
Da wo die gestrichene Linie unten losgeht, bleiben wir dran.
Wenn ich jetzt weiter oben lege, würde das so nicht funktionieren.
Also eine Situation, bei der wir sowas hätten und die andere die
liegt.
Was würde da passieren?
Also
es ist relativ einfach.
Wir machen eine Trennung der beiden konvexen Hüllen in einen oberen
und einen unteren Teil.
Das können wir hier bei dem Beispiel genauso machen.
Man kann den oberen und unteren Teil
feststellen, das sind zwei konvexe Hüllen.
Wir haben die als Polygone gegeben.
Mit diesen Reihenformeln.
Wir können feststellen, welche Punkte liegen im oberen Teil und welche
im unteren Teil.
Im oberen Teil liegen die, solange wir aufsteigende x-Koordinaten
haben.
Und wenn wir beim Durchlaufen dieser konvexen Hülle in der x
-Koordinate wieder zurückgehen, wieder kleiner werden, sind wir im
unteren Bereich.
Also wenn wir hier durchlaufen, der Reihe nach, dann können wir
eindeutig sagen, was der untere Teil und was der obere Teil ist.
Gucken wir nur die beiden oberen Teile an.
Dann brauche ich die beiden oberen Teile nur da sind ja beide in
diesen Reihenfolgen gegeben, die kann ich einfach
jetzt verschmelzen.
Das sind ja zwei sortierte Folgen.
Zwei sortierte Folgen von Punkten zu verschmelzen ist lineare Aufwand.
Zunächst mal habe ich hier diese 1, 2, 3 und A, B, C.
Das wären meine oberen Punkte.
Jetzt muss ich aber feststellen, wie sind die in Bezug auf ihre x
-Koordinaten hier angeordnet.
Und jetzt verschmelze ich die in Bezug auf ihre x-Koordinaten.
Dazu brauche ich nur der Reihe nach hier durchzulaufen.
Ich verschmelze diese beiden Mengen.
Das ist überhaupt kein Problem, das kann ich in linearer Zeit machen.
Das ist ein einfacher Verschmelzungsvorgang zweier sortierter Folgen
von Punkten, die jeweils nach ihren x-Koordinaten sortiert waren.
Dann habe ich diese Reihenfolge der Punkte und dann brauche ich
darauf, nur ein Graham-Scan zu machen.
Ein Graham-Scan hieß ja, ich gehe der Reihen nach durch, schaue diese
verschiedenen...
Nee, das würde ich also so hier durchlaufen.
Darüber, darüber, darüber und so.
Das wäre dann der obere Teil.
Und bei diesem Durchlaufen würde ich ja schon feststellen, dass das
hier kein Extrempunkt ist, dass das kein Extrempunkt ist, sondern nur
die beiden übrig bleiben.
Hier würde ich absteigen.
Da steige ich auch ab.
Da steige ich ab.
Hier zwischen diesen beiden Punkten steige ich auch ab.
Das funktioniert nicht.
Aber der Graham-Scan funktioniert hier.
Ich brauche nur der Reihen nach hier durchzulaufen und schaue mir die
entsprechenden Winkel an.
Weil ich mich nur an der oberen Hälfte bewege, ist dieses Kriterium,
habe ich hier einen Konvex- oder Konkarven Winkel, in diesem Fall in
Ordnung.
Ja, und ich habe pro Punkt, den ich betrachte, konstanten Aufwand,
also insgesamt linearen Aufwand.
Lieber, zunächst mal würden Sie ja denken, dass dieser Punkt hier,
dass der dazugehört.
Sie müssen ja feststellen, der Punkt gehört nicht dazu, der gehört
auch nicht dazu.
Ja, ich schaue mir auch die x-Ubstoff-Vorlagen an.
Und bringe dann Gruppen und das wird immer...
Nein, sagen Sie.
Obwohl die x- und die y-Ubstoff-Vorlagen größer werden, die muss ich
vorher behalten.
Wenn ich weit zu links bin, kann ich ihn auch behalten.
Also, dass der Punkt hier oben, dann denken Sie zunächst, dieser Punkt
muss drin bleiben.
Der hat in diesem Fall die Maximale.
Dass der drin bleibt, ist auch klar.
Das ist ein sicherer Extrempunkt.
Aber wie machen Sie dann weiter?
Ist das auch ein sicherer Extrempunkt?
Dieser hier?
Der?
Ist das ein sicherer Extrempunkt?
Nein.
Das ist nicht.
Es kann sein, dass das kein sicherer Extrempunkt ist.
Auf diese Art und Weise kommen Sie nicht zurecht.
Es kann sein, könnte sein.
Also noch ein anderes Beispiel.
Wenn wir jetzt hier sowas haben und unsere
andere...
Ja, das sah so aus.
Und das sieht hier so aus.
Dann wäre der Punkt der untere Punkt von der aber er wäre sicherlich
kein Extrempunkt.
Richtig.
Ich habe im Prinzip für das Verschmelzen einen Gram-Scan.
Ja.
Genau.
Und das Wesentliche ist, dass wir hier für diesen Gram-Scan den ersten
Schritt nicht machen müssen.
Wir müssen nicht sortieren.
Ja, sondern dadurch, dass wir die Extrempunkte ja bereits in einer
sortierten Reihenfolge haben, in den beiden konvexen Hüllen, die wir
jetzt hier beim Zusammenschmelzen haben, da sind die bereits sortiert,
haben wir nur noch linearen Aufwand, der dahinter kommt.
Das können Sie sich aussuchen, wie Sie das machen wollen.
Da habe ich keine Lösung, die ich Ihnen jetzt da vorschlagen würde.
Da können Sie irgendwas nehmen.
Ja, kann man ausprobieren, was am sinnvollsten ist.
Also...
Irgendeine Konstante.
10, 15, 20.
Da muss man einfach sehen, wie sieht das aus mit der Konstanten, die
ich hier bekomme.
Das ist einfach ein kurzes Ausprobieren.
Das K in dem Fall müsste ein Parameter sein für den Algorithmus.
Man probiert das einfach für verschiedene Verfahren oder für
verschiedene Beispiele aus.
Wie stark...
Also wo jetzt der beste Punkt ist für diese...
für das K.
Ja.
So.
Hier steht es nochmal.
Das ist also der Ansatz für die Vereinigung der beiden oberen Ränder.
Dass man hier den Graham-Scan einsetzt.
Das, was ich Ihnen gerade erzählt habe, steht auf der Folie nochmal
drauf.
Weil wir eben hier auf das Sortieren verzichten können, haben wir hier
den Graham-Scan mit linearem Aufwand einsetzen können.
Und das heißt, das Verschmelzen geht mit linearem Aufwand und dass
dann das Gesamtverfahren Zeit n log n hat, ist klar aufgrund dieser
Rekursionsform.
Einfaches...
so wie beim... wie wir das Sortieren kennen, einfach Folge von
Verschmelzungsoperationen.
Typische Rekursion für die beiden Konke.
So, das war also jetzt dieser...
dieses Verfahren die beiden Konke-Ansatz.
Und jetzt stelle ich Ihnen noch ein völlig anderes Verfahren vor.
Ein Wegwerfprinzip.
Noch ein anderes Prinzip.
Und dieses Wegwerfprinzip geht danach, ich versuche, aber auch ein
Prinzip, das wir kennen, wenn wir es mit einer großen...
mit einem großen Problem zu tun haben.
Wollen wir durch Operationen möglichst in der Lage sein, die
Problemgröße, die wir noch betrachten müssen, zu reduzieren.
Wie kann ich das Restproblem, das ich betrachten muss, durch
irgendeine Operation, also durch irgendwelche Operationen ganz stark
reduzieren?
Wir kennen das Problem von der binären Suche, das ist das
Eingangsbeispiel für viele Algorithmen für Vorgehensweisen bei der
binären Suche.
Da versucht man immer durch eine Abfrage die Hälfte der möglichen
Punkte rauszuwerfen.
Hier versuche ich...
Bitte?
Ja.
Genau.
Im Prinzip, Ihr Ansatz funktionierte da nicht so direkt.
So.
Okay.
Hier folgender Ansatz.
Wir bestimmen einfach Extrempunkte E1 bis E8 in den 8
Himmelsrichtungen hier, also 4 und die Zwischenwerte auch, Norden,
Nordosten, Osten und so weiter, wie sie hier eingezeichnet sind.
Solche Extrempunkte kann ich bestimmen.
Das ist einfach eine Maximumsbestimmung.
In der entsprechenden Richtung.
So.
Diese Punkte zu bestimmen geht also mit...
Das ist linearer Aufwand.
Da steht es.
Und jetzt eliminiere ich alle Punkte von M im Inneren des konvexen
Polygons, das durch diese 8 Extrempunkte aufgespannt wird.
Ich kann für jeden Punkt feststellen, ob er im Inneren dieses Polygons
liegt.
Das ist einfach wieder mit unseren Determinantenberechnungen
feststellen.
Nicht links oder rechts von der...
von einer Kante eines Polygons.
Also das wissen wir, wie man das feststellt, ob die Punkte drin
liegen.
ich kann also bei B...
Ich habe hier diese 8 verschiedene Punkte.
Dieser Aufwand ist linear.
Für jeden Punkt muss ich feststellen, liegt er drin oder draußen.
Das ist also auch im Prinzip einfach machbar mit linearem Aufwand.
Jetzt gibt es einige Punkte, die liegen nicht im Inneren dieses
Polygons.
Wenn ich Pech habe, waren alle meine Punkte irgendwo hier am Rand.
Aber das ist extrem unwahrscheinlich.
Zumindest, wenn ich annehme, die sind einigermaßen gleichmäßig in der
Ebene verteilt.
Dann werden nur wenige Punkte noch außerhalb dieses konvexen Polygons
liegen, dass ich hier mit E1 bis E8 bestimmt habe.
Jetzt muss ich einfach in den sauren Apfel beißen und für die
restlichen Punkte die konvexe Hülle bestimmen.
Diese Menge der restlichen Punkte kann aber schon relativ klein sein.
Wenn ich Pech habe, habe ich hier nochmal den Aufwand mlog n.
Wenn ich aber Glück habe, sind das nur sehr wenige Punkte und dann ist
der Aufwand im Mittel halb linear.
Also für eine gleich verteilte Punktmenge bekomme ich hier insgesamt,
weil ich dann nur konstant viele Elemente hier draußen liegen habe,
habe ich insgesamt linearen Aufwand als Erwartungswert.
Deswegen ist das für die Praxis oder der Annahme, ich habe gleich
verteilte Punkte dort liegen, ein sehr effizientes Verfahren.
Gut.
Also.
Das wäre jetzt so ein Blut-Force-Ansatz.
Ich gehe einfach daran, male mir so ein paar Punkte einfach rein, von
denen ich weiß, das sind garantiert Extrempunkte.
Ob ich jetzt diese 8 nehme oder 16 oder nur 4, ist eigentlich völlig
egal.
Nicht ganz egal, je mehr Punkte ich nehme, desto weniger bleiben
übrig.
Aber ich erhöhe natürlich dadurch die Konstante bei diesen beiden
Punkten mit linearer Zeit.
Weil ich ja für jeden dieser 8 Punkte natürlich feststellen muss.
Oder ich muss diese 8 Punkte jeweils feststellen, jeweils lineare
Aufwand.
Das heißt, ich habe insgesamt die Anzahl der Extrempunkte als
Konstante hier mit drin.
Gut.
Ich glaube, das ist auch klar, wie das funktioniert.
Und damit habe ich Ihnen jetzt alle Verfahren vorgestellt, die ich
Ihnen vorstellen wollte.
Dass man das unterschiedlich machen kann.
Übrigens nochmal, das hier könnte man natürlich auch problemlos
parallelisieren.
Also das ist
einfach zu parallelisieren.
Warum ist das einfach zu parallelisieren?
Weil ich ja hier, das würde ich jetzt also so machen, ich habe 16
Prozessoren zur Verfügung.
Da würde ich einfach 16 solche Extrempunkte bestimmen lassen.
Parallel.
Und würde anschließend mit irgendeinem parallelen Ansatz die, oder
vielleicht sogar nur auf einem Rechner, für die Restmenge das
feststellen lassen.
Also das ist, Punkte A und B kann ich hervorragend parallelisieren.
Und Punkt C kann ich auf einem Rechner machen.
Dann kann ich da das sehr schön parallel ausführen.
Untere Schranke für konvexe Höhlen.
Kann man sich auch einfach überlegen.
Untere Schranke für den schlechtesten Fall.
Ich konstruiere einfach einen schlechtesten Fall.
Wie folgt, ich konstruiere mir eine Punktmenge P1 bis Pn x1 bis xn
oder eine Punktmenge P1 bis Pn die jeweils gerade auf einer ähm
Parallel liegen.
xi, xi² Das sind also hier meine Elemente.
Und wenn ich jetzt die konvexe Hülle bestimmen will, dann ist es klar,
dass ich, das einzige was ich machen muss, ist diese Punkte zu
sortieren.
Die konvexe Hülle in dem Fall ist die sortierte Reihenfolge der
Punkte, sortiert im Bezug auf die x-Koordinaten.
Das ist alles.
Und das heißt, dass die untere Schranke für die Bestimmung der
konvexen Hülle einer beliebigen Punktmenge im schlechtesten Fall n log
n sein muss.
Genauso wie die untere Schranke für Sortieren n log n ist.
Also das Problem zur Bestimmung der konvexen Hülle kann nicht
einfacher sein als das Problem eine Punktmenge zu sortieren.
Also haben wir hier diese einfache Verfolgerung.
Untere Schranke für konvexe Hülle ist im schlechtesten Fall n log n.
Allerdings bekommt man hier, wenn man das mittlere Verhalten sich
anschaut, bekommt man nur Omega von n als untere Schranke raus.
Wir haben ja auch gerade gesehen, wir hatten ja ein Verfahren, bei dem
wir als mittleres Verhalten lineares Verhalten hatten.
Also das ist insofern etwas einfacher als Sortieren.
Aber für schlechtesten Fall haben wir n log n als untere Schranke.
Gut.
Das ist es, was ich Ihnen über algorithmische Geometrie erzählen
wollte.
Ich hatte zu Anfang begonnen mit diesen Galerie-Problemen, die haben
wir überhaupt noch nicht betrachtet.
Ja, aber das würde ein bisschen zu weit führen, wenn ich die auch noch
alle betrachten würde.
Das sind aber interessante Aufgaben.
Und das, was ich gemacht habe, ist, dass ich Ihnen eben noch so ein
paar algorithmische Prinzipien dabei versucht habe zu verdeutlichen,
wie diesen Planesweep-Algorithmus oder Planesweep-Ansatz.
Also die Problemlösung durch Reduktion einer Problemlösung auf eine
Folge von Problemlösungen, die jeweils ein verkleinertes Problem
anschauen.
Und in dem Fall eben diese Betrachtung von Problemen auf Hyper-Ebene.
Und man braucht in diesem Gebiet eine ganze Reihe neuer
Datenstrukturen, die ich Ihnen nur angedeutet habe, für diesen
Planesweep, auf dieser Geraden, die man da durchschiebt, baut man eine
Suchstruktur, um solche Intervallüberschneidungsprobleme zu lösen.
Das sind sogenannte Intervallbäume, die man dann aufbaut, die speziell
für diese geometrischen Ansätze gebraucht werden.
Man hat hier einiges an neuen Ideen entwickelt.
Und ich hoffe, dass ich Ihnen das einigermaßen vermitteln konnte.
Und das ist das, was wir hier in diesem Kapitel machen wollen.
So, und damit sind wir mit diesem Kapitel fertig.
Ich will das hier beibehalten.
Jetzt funktioniert hoffentlich alles.
Jetzt muss ich Ihnen noch ganz kurz etwas zu abschließendes erzählen.
Ich hoffe, dass das jetzt funktioniert.
Da ist es.
Ich hoffe, dass es mir gelungen ist, Ihnen zu vermitteln, dass
Algorithmik ein interessantes Gebiet ist.
Ich fand, wir haben hier viele interessante Diskussionen gehabt.
Sie haben viel nachgefragt.
Das fand ich gut.
Geht in der kleinen Runde.
Ich hätte eigentlich gerne mehr Hörer.
Aber eine kleine Runde hat auch ihren Vorteil, dass man halt mehr
diskutieren kann.
Offensichtlich, das haben wir auch festgestellt, das haben wir gerade
festgestellt, unsere Rechner werden zwar immer leistungsfähiger, aber
offensichtlich sind die Rechner nie schnell genug.
Wir finden immer genügend komplexe Aufgaben, die dann auf einmal dazu
führen, dass die Rechner nicht groß genug sind, nicht schnell genug
sind, Speicher sind nie groß genug.
Die Problemstellungen, die wir anpacken wollen, werden immer größer.
Und deswegen lohnt es sich, nach effizienten Lösungen zu suchen.
Ich habe einmal ein Erlebnis gehabt, da wurde über Probleme im Bereich
der künstlichen Intelligenz gesprochen.
Im Bereich der künstlichen Intelligenz werden häufig, es geht um
Auswertung von logischen Formeln, viele dieser Ansätze brauchen
exponentielle Zeit.
Es sei denn, Sie müssen sich mit Hornformeln beschäftigen, dann können
Sie in linearer Zeit Erfüllbarkeit ausrechnen, aber wenn Sie allgemein
Erfüllbarkeitsprobleme betrachten, wissen Sie, das sind NP
-vollständige Probleme und dann sind Sie gleich in einem Bereich, wo
Sie deterministisch, zumindest nach heutiger Kenntnis, exponentielle
Zeit brauchen.
Und bei einer Diskussion über solche Verfahren hat ein Wissenschaftler
gesagt, also nach effizienten Lösungen, nach effizienten Algorithmen
brauchen wir eigentlich gar nicht zu suchen, es reicht doch darauf zu
warten, dass die Rechner wieder schneller werden, dann ist doch das
Problem beseitigt, der hohen Laufzeit.
Und das halte ich wirklich für völlig daneben, weil wir wissen, eine
Beschleunigung eines Rechners führt nur dazu, dass wir um konstanten
Faktor runterkommen in der Laufzeit.
Wenn es uns aber gelingt, zum Beispiel bei der Matrix-Modifikation von
n hoch 3 auf n hoch 3 minus x zu kommen, dann ist das ein wirklicher
Fortschritt, der sich für große Probleme auswirkt.
Das andere sind konstante Veränderungen, weil wir in der Realität ja
immer nur um Faktor 2, 3 oder irgendetwas schneller werden.
Trotzdem, wenn man sich anschaut, die Leistungsfähigkeit der Rechner
vor 10 Jahren oder 15 Jahren und heute, das sind gewaltige
Fortschritte gewesen.
haben wir eine Beschleunigung oder eine Vergrößerung der
Rechengeschwindigkeit, Faktor 2, so alle 18 Monate etwa, 18 bis 24
Monate nach dem motion Gesetz.
Da hat sich schon sehr viel getan, aber mit effizienten Algorithmen
kann man nachhaltig deutlich mehr machen, denn die effizienten
Algorithmen werden mit der neuen Rechner-Generation auch alles
schneller.
Deswegen lohnt sich die Investition in effiziente Algorithmen immer
und die Analyse von Algorithmen sollte eigentlich viel einfacher sein,
als die Analyse von zum Beispiel irgendwelchen Unternehmensstrukturen,
was eine Aufgabe, die Wirtschaftsingenieure sehr gerne angucken und
Vorschläge machen, wie man Unternehmensstrukturen verbessern kann,
effizienter machen kann.
Das ist ein wesentlich komplexeres Gebilde, als so ein Algorithmus,
den man von Menschenhand sich ausgedacht hat und konstruiert hat.
Da sich die Kosten anzugucken und über Verbesserungen nachzudenken ist
eigentlich wesentlich einfacher und es lohnt sich, gerade bei
Aufgaben, die häufig bearbeitet werden müssen.
Also, wir hatten gesehen, Entwurfe und Analyse von Algorithmen sind
abhängig vom Berechnungsmodell, was habe ich eigentlich für eine
Berechnungsstruktur zugrunde liegen, was für Datenstrukturen kann ich
einsetzen und die Prinzipien, die wir bei diesen vielen verschiedenen
Problemen angeschaut haben, waren eben verschiedene sequenzielle
parallele Verfahren anzuschauen, Hardware-Algorithmen auch zu
betrachten.
Das haben wir nur am ganzen Rande mal betrachtet.
Bei den Sortierverfahren, habe ich Sie darauf hingewiesen, oder auch
bei den Batterie-Produktionsverfahren waren wir sehr nah dran an
Hardware -Algorithmen, weil es keinen Sinn macht, so feingranulare
parallele Algorithmen auf einem Parallelrechner wie, ich glaube bei
uns, einem Superrechner im Rechenzentrum einzusetzen, sondern die wird
man direkt in Hardware kompilieren und dann hat man den
Kommunikationsaufwand deutlich reduziert.
Wenn man ansonsten zwischen unabhängigen Rechnern kommunizieren will,
ist der Kommunikationsaufwand halt deutlich größer als der
Rechenaufwand.
Untere, obere Schranken haben wir angeschaut.
Wir haben Beispiele gesehen, wo die unteren und oberen Schranken
zusammengefallen sind, wo wir die also ganz scharf über Algorithmen
identifizieren konnten, die tatsächlich optimal sind und genau die
Konstante erreichen der unteren Schranke.
Ich habe Ihnen den Mapping-Ansatz vorgestellt.
Wir haben viel die Weidel-Conquer-Verfahren gesehen.
Ich habe Ihnen den Sweep-Line-Ansatz vorgestellt.
Und insofern haben Sie hoffentlich ja einiges gelernt, was man heute
für ein Bereich auch einsetzen muss, der eben ganz stark im Kommen
ist.
Das habe ich zu Anfang auch schon oft gesagt.
Die Multicore-Rechner- Architekturen werden immer stärker präsent sein
in Desktops, in Laptops und so weiter.
Und da muss man in der Lage sein, diese Multicore- Architekturen
sinnvoll einzusetzen.
Man muss wissen, wie kann man effizient Aufgaben verteilen auf viele
unabhängige Rechenkerne.
Und ich denke, dafür habe ich Ihnen ja einige Anregungen gegeben.
Vielleicht sollte ich die Vorlesung zukünftig umbenennen in
Algorithmen für Multicore-Architekturen.
Dann wäre der Hörsaal vielleicht voller.
Aber die Verfahren wären sehr ähnlich.
Okay.
Das ist aus meiner Sicht eigentlich, was die Inhalte angeht, erstmal
alles.
Ich kann Sie noch ganz kurz hinweisen auf das, was wir im Institut
machen.
Wissen Sie vielleicht auch, also mein Bereich Effiziente Algorithmen
ist klar.
Der Bereich von Herrn Oberweis und Herrn Stucki.
Herr Stucki ist ja schon jetzt ausgeschieden, aber ist in der Lehre
durchaus noch präsent.
Betriebliche Informations- und Kommunikationssysteme.
Die wissensbasierten Systeme von Herrn Studer.
Semantic Web.
Web 2.0, 3.0 und so weiter.
Wichtiges Thema von Herrn Studer.
Eine neue Gruppe von Herrn Tai.
Ökonomie, Technologie der E-Organisation.
Hier geht es vor allen Dingen um Services.
Auch ein wichtiges Thema der Informatik.
Komplexitätsmanagement von Herrn Seese.
Also wie kann ich komplexe Strukturen möglichst gut gestalten und
managen.
Und meine Gruppe Effiziente Algorithmen beschäftigt sich halt mit
einer Vielfalt von Themen, wo es um Effizienz geht.
Ich habe hier nochmal die Vorlesung aufgeführt.
Die haben Sie jetzt gerade gehört.
Einige von ihnen sind in Organic Computing drin.
da geht es halt gerade hat auch was zu tun mit der Beherrschbarkeit
komplexer Systeme, aber vor allen Dingen mit adaptiven Systemen und
mit gesteuerter Selbstorganisation.
Ein Thema, das uns immer stärker verfolgen wird.
Verteilte Algorithmen habe ich im Prinzip im Angebot als Vorlesung,
aber leider in den letzten Jahren nicht mehr gemacht, weil ich nicht
die Kapazität habe.
Kann nicht alle Vorlesungen machen.
Diese Vorlesung, die Natur- und Spielwert- Optimierungsverfahren,
genetisch - revolutionäre Algorithmen, sind Ansätze, die in der Praxis
inzwischen sich durchgesetzt haben für Probleme, bei denen man die
Struktur des Suchraums nicht ausreichend kennt, aber durch diese
Ansätze sehr schnell gute Lösungen kriegt.
Und Vorlesung hier, Computational Economics von Herrn Branke.
Eine Anwendung von Simulationen in ökonomischen Bereichen, auch das
muss effizient gestaltet werden.
Das sind so Lehranwendungen, also Lehrthemen, die wir anpacken.
Sie können bei unseren Seminaren und Teleseminaren natürlich, wobei
Teleseminare mache ich eigentlich kaum noch, habe ich ein paar Mal
gemacht.
Mit Kollegen an anderen Orten zusammen.
Aber in unseren Seminaren tauchen also immer die wesentlichen
Forschungsthemen auf, die wir bearbeiten.
Und zur Zeit ist das wesentliche Thema eigentlich Organic Computing.
Mit allen möglichen Facetten.
Und ein anderes Thema, Serviceorientierte Architekturen.
Wir machen hier unser KIM-Projekt, Carceral Integrated Informations
Management, wo es darum geht, eine serviceorientierte Architektur
aufzubauen für alle Dienste der Universität.
Und in dem Zusammenhang laufen eigentlich in den letzten Semestern
immer irgendwelche Praktika.
Und ab und zu läuft auch was zum Organic Computing als Praktikum.
Und Sie können natürlich bei uns Diplomarbeiten machen, wenn Sie das
hier weiter treiben wollen.
Diplomarbeiten zu allen Themen, die hier angesprochen werden, sind
hier nochmal aufgeführt.
Einige sind in Kooperation mit der Industrie.
Ich hatte jetzt interessante Arbeiten mit einem Karlsruher
Softwarehouse, die sich mit die Personen untersucht haben wollten, wie
sich spezielle Datenstrukturen auswirken auf Möglichkeiten,
Suchoperationen zu machen aus sehr großen Datenmengen.
Haben wir sogenannte Skip-Listen untersucht und Skip-Trees und solche
Dinge.
Also spezielle Datenstrukturen, das waren interessante Arbeiten.
Aber die wesentlichen, also die meisten meiner Arbeiten beziehen sich
oder Diplomarbeiten beziehen sich eigentlich hier auf diese
Anwendungen im Bereich Organic Computing und Evolutionäre Verteilte
Optimierung.
Wenn Sie Diplomarbeit machen wollen, ich weiß nicht mit welchen
Semestern Sie jeweils sind, aber man sollte sich relativ früh damit
beschäftigen, wo man eigentlich etwas machen will, wann man dann auch
sein Studium entsprechend gestalten kann.
Dann schafft man sich halt das Know-How, das man braucht, um eine
interessante Arbeit tatsächlich machen zu können.
Wobei ich damit nicht sagen will, dass das eine Voraussetzung für die
Diplomarbeiten bei mir ist, dass man alle meine Vorlesungen gehört
hat.
Aber man sollte schon sehen, dass man das irgendwie aus Studium
natürlich sinnvoll abstimmt.
Uns, was hier auch noch steht, ist, dass Sie nicht warten müssen, bis
Sie alle Prüfungen gemacht haben, bevor Sie sich um die Arbeit
kümmern.
Sie können die Arbeit auch schreiben und anschließend noch weitere
Lehrveranstaltungen machen.
Nur abgeben, also als Wirtschaftsingenieur dürfen Sie die Arbeit erst
abgeben, wenn Sie alle Prüfungen gemacht haben.
Das ist ein anderer Punkt.
So, das war das, was ich Ihnen hier präsentieren wollte.
Haben Sie noch Fragen?
Keine Fragen.
Das ist auch schon ein Nachviertel nach.
Ich danke Ihnen für Ihre Aufmerksamkeit.
Ich danke Ihnen insbesondere, dass Sie das ganze Semester
durchgehalten haben.
Auch wenn ich nicht alle gesehen habe.
Zum Teil eben als entfernter Hörer ist ja auch in Ordnung.
Und ich hoffe, dass Sie einfach weitersagen, dass das eine
interessante Vorlesung ist.
Wie könnte man erreichen, dass hier mehr Leute angesprochen sind?
Woran liegt es, dass einige meinen, das wäre hier zu anstrengend?
Ich finde es nicht anstrengend.
Ja, die Noten hier sind eigentlich meistens relativ gut.
Aber es liegt auch daran, dass die Leute, die hier kommen, wirklich
Interesse haben.
Und dann macht man gute Noten.
Vielen Dank auch nochmal, dass Sie mir die Fragen beantworten.
Schön.