So, Prozesse.
Das letzte Mal haben wir über Prozesse gesprochen.
Und die Idee ist einmal, dass man den Prozess auffasst als die
Aktivität, die ein aktives Element, nämlich unser Prozessor, oder die
Dynamik, die ein Prozessor, unser Programm verleiht, in dem einfach
jetzt Anweisung für Anweisung ausgeführt wird.
Und wir hatten den Begriff der Aktivitätsbahn eingeführt, als den Weg,
den wir durch ein Programm durchführen, also die Folge der
Anweisungen, die wir durchführen.
So, das reicht ja zunächst mal aus, um eine gewisse Vorstellung zu
entwickeln, was passiert mit dem Programm, wenn ich es jetzt zum
Ablauf bringe.
Ja, aber wir gehen noch einen Schritt weiter.
Wir gehen noch einen Schritt weiter.
Wenn wir nämlich in der Lage sind, selbst solche Aktivitätsbahnen zu
starten, dann kriegen wir plötzlich auch Kontrolle darüber, wie die
Abläufe vor sich gehen, insbesondere auch, ob wir beispielsweise, wenn
uns mehrere Prozessoren zur Verfügung stehen oder wenn wir irgendwie
warten müssen, dass wir also mehrere Aktivitätsbahnen parallel laufen
lassen können und dass wir natürlich auch irgendwie mal veranlassen
müssen, dass eine gewisse Organisation über solche parallel laufenden
Prozesse gezogen wird.
So, da haben wir eingeführt, in Java können wir tatsächlich eine
solche Kontrolle ausüben, indem wir Thread-Objekte definieren, dann
Threads einrichten und schließlich auch Threads ablaufen lassen.
Jetzt gebe ich mal hier ein Beispiel, das ist zwar nicht mit Threads
dargestellt, aber wir können uns leicht vorstellen, wie wir eine
solche Organisation mit Threads bewirken können, und zwar die
parallele Ausführung von Programmen.
Am einfachsten ist es natürlich, wenn wir tatsächlich mehrere Rechner
zur Verfügung haben oder mehrere Prozessoren zur Verfügung haben, dann
können wir ein Programm nehmen und wenn dieses Programm inhärent
Eigenschaften besitzt, die sich für eine Parallelisierung eignen, dann
können wir natürlich diese Teile, die sich parallelisieren lassen, auf
die verschiedenen Prozessoren verteilen.
Das gilt ganz besonders dann, wenn wir zum Beispiel ein Rechnernetz
haben, mit mehreren Knoten, die den Rechnern zur Verfügung stehen.
Ich hatte Ihnen etwa erzählt, das letzte Mal, dass seit neuestem so
etwas wie das Computing Grid besteht, dass wir also einfach unsere
Rechner ins Netz reinstellen, dann stellen wir sie zur Verfügung, und
wenn immer freie Zeit ist, dann meldet sich unser Rechner irgendwo bei
einem Planer oder Scheduler an und dieser Planer, der hat jetzt die
Aufgabe, eben große, anstehende Aufgaben irgendwie zu verteilen.
Das heißt, zu sehen, wo ist im Augenblick freie Kapazität, ein Teil,
der parallelisierbar ist, mit anderen rauszunehmen, an diesen
Rechnerknoten zu schicken, und dann bearbeitet er die zunächst mal
nach Maßgabe der Kapazität, die ihm zur Verfügung steht, und schickt
das Ergebnis zurück.
Im Augenblick ist etwa in der Bioinformatik, insbesondere in der
Genomforschung, tun sich im Augenblick eine Menge große Rechenzentren
Europas zusammen, um eben über solche Grids dann die extrem hohen
Rechneraufwände zu leisten, indem man einfach Teile parallelisiert.
Wenn wir uns das jetzt auf kleiner Ebene ansehen würden, dann würden
wir zum Beispiel einen Java-Thread haben, und da könnten wir jetzt
neue Threads einrichten, indem wir jeweils gewisse Aufgaben, die
parallelisierbar sind, in diesen Threads verankern, und dann haben wir
hoffentlich auch eine genügend große Zahl von Prozessoren, um diese
Threads auch tatsächlich parallel laufen lassen zu können.
Was wir auch gesehen haben, das letzte Mal, war noch so eine verzahnte
Ausführung.
Wir haben zwar nur einen Prozessor, aber den Prozessor teilen wir nach
Priorität oder nach Wartezeiten oder nach irgendeinem
Zeitscheibenverfahren den verschiedenen Prozessen zu.
Und auch da ist durchaus denkbar, insbesondere in Wartezeiten zu
überbrücken sind, dass dann die parallele Ausführung, diese verzahnte
Ausführung insgesamt schneller zu einem Ergebnis führt, als wenn wir
nur einen einzigen sequentiellen Thread durchlaufen würden.
Und übrigens auch, was Sie selbst bei Ihren PCs ja häufig sehen
können, gewisse Hintergrundjobs, wie zum Beispiel das Drucken, die
werden eben auch über solche parallelen Threads abgewickelt, meistens
auch über, oder häufig auch über einen eigenen Prozessor.
So, aber das funktioniert nicht immer.
Sondern wir müssen uns jedes Problem genauer ansehen, daraufhin lässt
es sich tatsächlich parallelisieren, oder es ist inhärent so
sequentiell, dass wir keine Chance haben, irgendeine Verbesserung
durch Parallelisierung zu erreichen.
Also selbst wenn uns die Ressourcen, mehrere Prozessoren zur Verfügung
stehen, mag trotzdem sich das Problem nicht eignen für eine
Parallelisierung.
Also was müssen wir denn dann zunächst mal fordern?
Wir müssen erstmal fordern, dass wir ein Problem haben, das zerlegen
wir wieder wie üblich in Teilprobleme, divide and conquer, teil und
herrsche.
Aber jetzt müssen wir mehr erfüllen, wir müssen nämlich zeigen, dass
diese Teilprobleme völlig unabhängig voneinander zu lösen sind.
Wenn sie unabhängig sind, dann kann ich das eine Teilproblem dem einen
Prozessor übergeben, oder dem einen Thread nächstes Mal, und das
zweite Teilproblem in einem zweiten Thread unterbringen, das dritte
Teilproblem in einem dritten Thread, dann laufen die unabhängig
voneinander los, und liefern schließlich am Schluss ihr Ergebnis
wieder gemeinsam ab, bei irgendeiner Stelle, die dann auch die
Ergebnisse zusammenführen muss.
Also, wir müssen zeigen, dass sie unabhängig sind, und unabhängig
heißt nichts anderes, als die Reihenfolge ist gleichgültig, in der ich
diese Teilprobleme löse.
So, dann, wenn ich die Teilprobleme habe, jedes Teilproblem eigene
Recheneinheit, und mein Ziel der Parallelisierung ist, dass ich
beschleunige.
Und wir müssen uns also insbesondere dann ansehen, wird durch die
Parallelisierung, selbst wenn ich jetzt unabhängige Teilprobleme habe,
ist am Ende das Ergebnis schneller erzielt worden, oder nicht.
Es geht also jetzt im Wesentlichen um Geschwindigkeit.
Man kann das messen.
Es gibt auch bestimmte Maße, die man entweder berechnen oder messen
kann, und die einem dann Aufschluss darüber geben, ob man tatsächlich
eine Verbesserung erzielt oder nicht.
Und die Maße sind die folgenden.
Die eine sagt also, wir sind in der Lage zu beschleunigen.
Und dann müssen wir fragen, ja, um wie viel beschleunigen wir denn nun
tatsächlich.
Jetzt nehmen wir mal Folgendes an.
Wir hätten hier einen Aufwand für ein Problem der Größe n, und wir
prüfen nach, wie viel brauchen wir denn an Zeit für einen Prozessor,
wenn uns nur ein einziger Prozessor zur Verfügung steht, wenn wir es
also tatsächlich sequenziell ausführen müssen.
Und wie hoch ist denn der Rechenaufwand, wenn wir eine bestimmte Zahl
von Prozessoren, beispielsweise P-Prozessoren, zur Verfügung haben.
Wir ermitteln also deshalb den Aufwand für die P-Prozessoren.
Also beispielsweise könnte das eine O von n und das andere O von n²
sein.
Und dann haben wir offenbar immerhin als Gewinn den Faktor n.
Schauen wir uns also an, wie groß der ursprüngliche Aufwand, wenn uns
ein Prozessor zur Verfügung steht, wie groß der Aufwand, wenn uns P
-Prozessoren zur Verfügung stehen.
Und daher hoffentlich der Aufwand mit P-Prozessoren um einiges
geringer ist, als mit einem Prozessor, jedenfalls bei den Problemen,
für die wir uns interessieren, ergibt sich dann ein Speed-up, der
mindestens 1 und hoffentlich größer 1 ist.
Den nennen wir S von P. Also der Speed-up bei P-Prozessoren.
Und am schönsten wäre es natürlich, wenn Folgendes rauskäme, dass der
Speed -up proportional der Zahl der Prozessoren ist.
Das heißt, wenn wir für das gleiche Problem P-Prozessoren einsetzen,
und wir nutzen die Leistung jedes Prozessors voll aus, dann müssen wir
einen Gewinn von P haben.
Jetzt wird es natürlich nicht immer ganz so ideal ablaufen, und dann
interessiert uns häufig noch ein zweites Maß, die sogenannte
Effizienz, die besagt einfach, wie gut laste ich denn meine
Prozessoren aus.
Und da kann man wieder sagen, da interessiert uns natürlich die
mittlere Auslastung, und wir müssen infolgedessen uns ansehen, der
Speed -up, den dividieren wir einfach durch die Zahl der Prozessoren
und erhalten dann die Auslastung.
Und das könnte man natürlich auch durch diese Formel ausdrücken.
Und jetzt sehen wir wieder, wenn es uns gelingt, proportional der Zahl
der Prozessoren die Beschleunigung zu erreichen, dann scheint es ja zu
sein, dass wenn wir tatsächlich diesen Faktor P gewonnen, dass auch
jeder Prozessor aktiv ist, denn sonst käme ja nicht die Beschleunigung
dem Faktor P zustande.
Also sehen wir auch deutlich, dass die Auslastung dann, wenn SP gleich
P ist, dann ist sie genau 1, und wenn der Speed-up unter P fällt, dann
würde entsprechend auch die Auslastung etwas geringer werden.
Also eigentlich kein unabhängiges Maß, aber gelegentlich ist es ganz
sinnvoll, sich auch die Auslastung anzusehen.
Jetzt hatte ich ja schon gesagt, wir können nur mit Problemen
arbeiten, die sich parallelisieren lassen, und zwar leicht möglichst,
und jetzt ist natürlich als nächstes die Frage, hier habe ich
irgendein Problem, lässt sich das parallelisieren oder nicht?
Es ist keineswegs so trivial, dass man sich irgendein Problem ansieht
und dann sagt, naja, ist ganz offensichtlich, dass es sich
parallelisieren lässt oder nicht.
Häufig ist die Fantasie gefragt.
Häufig muss man das Problem möglicherweise auch etwas umformulieren,
um festzustellen, ist es nun tatsächlich parallelisierbar oder nicht
parallelisierbar.
Hier ist ein Beispiel.
Die Maximumsuche.
Wir haben also eine Menge von Zahlen, hier sind also Elemente A1 bis
AN gegeben, und wir suchen das maximale Element.
Und Sie kennen natürlich alle, das Programm haben wir uns schon x-mal
angesehen.
Ich führe irgendeine Variable mit, in der führe ich das Maximum.
Ich vergleiche, indem ich durch die Reihe und durchmarschiere, jedes
Element mit dem aktuellen Maximum.
Und wenn das Element selbst größer ist als das aktuelle Maximum, dann
wird das neue Element zum Maximum.
So marschiere ich durch, also ist natürlich die Komplexität N.
Immerhin könnte ich auch folgendermaßen vorgehen, ich könnte also mit
Z -Teile und Herrsche vorgehen und könnte sagen, das Maximum, ich
betrachte immer das Maximum von zwei Zahlen, von zwei Werten.
Wenn ich also das Maximum einer, sagen wir mal, von acht Elementen
betrachten werde, dann vergleiche ich zunächst mal das Maximum der
ersten vier und der letzten vier Werte.
Und das kann ich erneut wiederholen, also habe ich dann das Maximum
dieser zwei Werte jeweils zu betrachten und schließlich komme ich auf
das Einzelelement.
Also ganz typisches Teile-und-Herrsche-Problem.
Und wir sehen auch schon deutlich, was hier zu tun ist.
Wir kriegen so ein N-log-N-Verhalten oder ein Log-N-Verhalten an
dieser Stelle, ganz offensichtlich.
Das Logarithm ist zwei.
Aber wir können auch gleich entdecken, dass ich beim ersten Vergleich,
bei der ersten Maximumbildung, eine Parallelisierung erreiche, derart,
dass ich vier Prozessoren brauche.
Dann brauche ich nur noch zwei, das heißt zwei werden schon gar nicht
mehr ausgelastet.
Und am Ende habe ich nur noch einen einzigen Prozessor, das heißt drei
Prozessoren werden nicht mehr ausgelastet.
Man kann sich also auch so auf die Art schnell überlegen, dass es
unmöglich sein kann, dass der Gewinn-Linear mit P steigt, das bietet
ab, sondern muss geringer sein.
Das ist so eine schnelle Überlegung, nutze ich meine Prozessoren
wirklich aus, dann brauche ich wie viele Prozessoren, um sich ein Bild
zu machen, wie gut eigentlich der Speed-up und auch die Ausnutzung
ist.
So, wir können uns das schnell überlegen.
Und wir sehen also, wenn wir jetzt mit einem Prozessor arbeiten, dann
müssen wir insgesamt n Elemente miteinander vergleichen, das sind also
n -1 Vergleiche.
Also kann ich sagen, ist der Aufwand O von n.
Genau, n-1.
Wenn ich umgekehrt n Prozessoren, n halbe Prozessoren, das war ja
unser erster Schritt, wenn ich nochmal zurückgehe, unser erster
Schritt besagt ja, ich unterteile in die Hälfte der Prozessoren, das
heißt ich brauche also in diesem Fall, wir sehen genau n halbe
Prozessoren, dann ist deutlich, dann ist der Aufwand eben Logarithmus
zur Basis 2 von n.
So, und jetzt brauchen wir das nur in unsere Formel einzutragen, die
Ausnutzung ist dann eben genau diese hier, nämlich Tn von 1, das ist n
-1, dann wissen wir den Aufwand für n bei der Hälfte und müssen das
selbst nochmal mit n halben multiplizieren und erhalten dann eine
Ausnutzung, die eben 1 über dem Logarithmus zur Basis 2 ist.
Das war jetzt ein einfaches Problem, würde wahrscheinlich auch niemal
jemand machen, aber jetzt schauen wir uns mal etwas anders an.
Die erste Frage, die sich noch stellt, ist, ob wir eigentlich jetzt
auch mit weniger als n halben Prozessoren ausgeben.
Ist doch ganz klar, wenn wir tatsächlich weniger als n halbe
Prozessoren brauchen würden, dann gelänge es, die Ausnutzung höher zu
treiben.
Fragen lasse ich unbeantwortet, aber es ist eine typische Frage, die
man sich stellen muss, das heißt, wenn man schnell, also mit Teil und
Herrscher beispielsweise recht schnell, eine Parallelisierung findet,
dann muss man immer bedenken, mit Teil und Herrscher unterteilt man
normalerweise immer in Hälften und deshalb kommt halt ein Aufwand oder
eine Ausnutzung zustande, die am Anfang recht hoch ist, aber immer
weiter absackt.
Und leider ist es so, dass viele Probleme, für die man recht schnell
eine Parallelisierung findet, eben gerade nach diesem Teil- und
Herrscherprinzip vorgehen.
Das könnte man ja auch beim parallelen Sortieren machen, aber ich
führe mal vor, dass beim parallelen Sortieren sich auch ein bisschen
was Besseres einfallen lassen kann.
Und zwar, der Ausgangspunkt ist der folgende.
Wenn wir Sortieren durch Mischen betrachten, dann kann man sich
fragen, ist das nun wirklich für parallele Sortierung geeignet oder
nicht?
Und dann kann man sich gleich überlegen, ich kann ja eigentlich jede
Hälfte für sich unabhängig sortieren.
Und das kann ich wieder schrittweise weiter tun.
Das heißt, ich kann wieder die Sortierung selbst parallelisieren, bis
runter auf ein oder zwei Elemente.
Aber dann habe ich anschließend auch noch ein Mischen, ein
Mischvorgang dabei.
Und jetzt erhebt sich ja die Frage, wie bringe ich denn den
Mischvorgang unter?
Ist der auch einer Parallelisierung dann noch zugänglich oder stört er
zumindest nicht die vorangegangene Parallelisierung, die Unterteilung
beim eigentlichen Sortiervorgang?
Und das haben sich auch schon andere gefragt, um möglichst schnell,
also parallel sortieren zu können.
Und die Frage, die man sich dann stellt, ist, ob man die Prozessoren
so verbinden kann, dass schnelles paralleles Mischen möglich wird.
Schauen wir uns mal an, wie das geht.
Also wir nehmen mal an, das parallele Sortieren haben wir irgendwie
gelöst, mit Teile und Herrsche, also wiederum kommt da ein
logarithmisches Verhalten ins Spiel und jetzt machen wir uns ans
Mischen.
Und wir geben uns vor, zwei Folgen, die also schon sortiert sind,
nämlich A1 bis AN ist eine Folge und eine zweite Folge B1 bis BN.
Und im Übrigen werden wir auch noch zulassen, dass mehrfach Vorkommen
möglich ist.
Und der Grundgedanke sieht jetzt folgendermaßen aus.
Wir könnten ja Folgendes tun, wir gehen jetzt durch A durch und
betrachten die ungeraden und die geraden Positionen getrennt.
Wir fangen z.B.
mit der ungeraden Position an, vergleichen also die ungeraden
Positionen und bei der ungeraden Position macht es zunächst einmal das
kleinere Element.
Etwa, das ist also hier jetzt die rote Linie und die rote Linie, wie
man sieht, führt zunächst mal auf diese 1 und diese 1 taucht dann an
dieser Stelle auf.
Jetzt ist die nächste Frage, wo vergleichen wir jetzt weiter?
Wir könnten jetzt zunächst einmal fortschreiten und die geraden
Elemente vergleichen.
Wenn wir die geraden Elemente vergleichen, dann haben wir hier 2 und
3, aber zunächst besteht ja auch noch die Möglichkeit, dass von den 2
übrig gebliebenen, dass das übrig gebliebene ungerade Element, das ist
ja auch noch nicht einsortiert worden, dass das möglicherweise kleiner
ist als das nächste ungerade Element.
Also müssen wir offensichtlich, wenn wir gerade Positionen nehmen,
immer zunächst einmal vergleichen, ist noch ein Element übrig
geblieben aus der ungeraden Position.
Und jetzt wenn wir wieder zum ungeraden übergehen, wiederholt sich
genau die gleiche Überlegung.
Das heißt, wir müssen immer mit dem vorangegangenen, übrig gebliebenen
Element den Vergleich durchführen.
Jetzt können wir überlegen, ob wir mit dieser Grundidee, ob wir mit
der es schaffen,
ein Mischen vorzunehmen, das sich parallelisieren lässt.
So, das ist nochmal ein bisschen formal dargestellt.
Also wenn wir uns ein gerades Element jetzt, wenn wir Folgendes uns
vorstellen.
Wir nehmen hier die geraden Elemente, hier sind die ungeraden
Elemente.
Die ungeraden Elemente ergeben also insgesamt 1, 2, 5 und 6.
Das ist hier sortiert.
Und die geraden Elemente ergeben jetzt an dieser Stelle 3 und 4.
Das ist das Element und das Element hier.
Und dann nochmal in der letzten Position 7 und 8.
Wenn wir uns also vorstellen, dass wir zunächst einmal die ungeraden
Elemente jeweils nochmal sortieren.
Und die geraden Elemente, dann gilt Folgendes, dass in der
tatsächlichen Ergebnisliste, die hat ja sowohl die geraden wie die
ungeraden Elemente umfasst, die also die Länge x2i hat, dass dort
gilt, das gerade Element an der Position i ist auf jeden Fall größer
oder gleich den geraden Elementen, die davor liegen und den ungeraden
Elementen, die davor liegen.
Und das ungerade Element jetzt an der nächsten Position ist größer
oder gleich allen ungeraden Elementen, die davor liegen und allen
geraden Elementen, die davor liegen unterhalb der Position i.
Und jetzt müssen wir eben nur noch diesen Vergleich führen.
Kommt eher das gerade Element an der Position gi oder das ungerade
Element an der Stelle ui plus 1 in Frage und dementsprechend wird das
eine nach x2i und das andere nach x2i plus 1 transportiert.
So, jetzt führe ich das mal hier vor.
Wir nehmen uns jetzt erstmal die ungeraden Elemente und die geraden
Elemente der Reihe nach raus und sortieren sie.
Dann haben wir also hier zunächst einmal für die geraden Indizes,
wobei das hier brauchen wir gar nicht explizit aufzubauen, sondern wir
ordnen nur am Ende an.
Wir fangen also an und beginnen jetzt erstmal mit dem ungeraden
Element.
Das erste ungerade Element macht das Rennen, das ist hier die 1.
So, jetzt rücken wir vor um eine Position und vergleichen das gerade
Element mit dem ungeraden Element.
Das heißt, wir rücken jetzt vor zu dem ungeraden Element, zur 2, das
ist also hier, und vergleichen die jetzt mit dem geraden Element
davor.
Und das gerade Element an dieser Stelle ist 3.
Also, das ist genau dieser Vergleich hier.
Und da qualifiziert sich die 2, also ist das x1, x2, x3.
Wir transportieren also nach i plus 1 jetzt das Element 3.
So, jetzt rücken wir wieder um eine Position vor.
Und das ist jetzt an dieser Stelle wieder die gerade Position an
dieser Stelle und die ungerade Position u plus 1.
Also, wir vergleichen jetzt 4 und 5 und ordnen wieder hier
entsprechend die 4 und die 5 an.
Dann rücken wir hier wieder an eine Position weiter, vergleichen
wieder mit dem letzten Element bei u.
Das ist 6 und 7, also werden die hier unten untergebracht und
schließlich bleibt nur noch ein gerades Element übrig.
Das ist die 8.
So, und dieses Zwischenergebnis, das brauchen wir nur gedanklich
fortzuführen, indem wir eben einfach hier entsprechend die Indizes
fortschalten.
Und wir sehen insbesondere jetzt Folgendes.
Dieser Vergleich ist immer lokal und er betrifft immer ganz bestimmte
Positionen.
Und jetzt müssen wir uns die Frage stellen, ob dieser Vergleich, der
ganz bestimmte Positionen angeht, ob wir den in beliebiger Reihenfolge
durchführen können oder nicht.
Wenn die Antwort lautet Ja, dann können wir das parallelisieren.
Und wenn die Antwort lautet Nein, dann können wir diesen Teil des
Mischens nicht parallelisieren.
Also, was Sie jetzt meinen, sind die unabhängig die Vergleiche, sind
die unabhängig voneinander oder nicht?
Ja?
Bitte?
Ja?
Die sind unabhängig, weil man es ja deutlich sieht.
Die arbeiten auf ganz bestimmten Positionen.
Und die Positionen sind ja vornherein fest vorgegeben.
Das heißt, wir könnten jetzt zum Beispiel ein Prozessor-Netzwerk
bauen, das uns erlaubt, einfach diese Verbindung jetzt per Vergleich
in einem Zug durchzuführen.
Wir würden wahrscheinlich keine Threads dafür einrichten, aber man
könnte sich zum Beispiel Hardwarelösungen, die hat es auch gegeben,
dafür vorstellen.
Hier sieht man so ein Mischnetzwerk.
Und sehen jetzt, dass wir an dieser Stelle hier mit unserer sortierten
Folge B und A reinkommen.
Dann ist das, was ich jetzt genannt habe, nämlich dieses Mischen der
geraden und ungeraden Zahlen, erfolgt erstmal, hier werden die geraden
Indizes und hier die ungeraden Indizes reingepackt.
Und dann kommt hier einfach die ganzen Vergleiche, die jetzt wiederum
parallel erfolgen können.
Und man kann also auf die Art sehr große und lange Sortierfolgen sehr
schnell mischen.
Also kann man zum Beispiel, wenn das ein Problem ist, das besonders
häufig vorkommt, da kann man zum Beispiel einfach spezielle Hardware,
speziellen Chip für den Zweck bauen.
Wenn wir uns vorstellen, dass wir an vielen Stellen heute ja
Prozessoren haben und dass manche eben auch Echtzeitverhalten, also
sehr schnelles Verhalten zeigen müssen, nehmen wir mal an, vielleicht
im Flugzeug, dann werden einfach solche speziellen ASICs gebaut, die
dann eben solche speziellen Verbindungen einfach besitzen.
Und dann gießen wir einfach so einen Mischvorgang oder nicht in
Software, wie wir es bisher gewohnt waren, sondern wird es in Hardware
gegossen.
Beschäftigen sich unzählige Leute, auch zum Beispiel mein Kollege
Tischi, die beschäftigen sich eben damit, wie man jetzt bestimmte
Probleme parallelisieren kann, was bei den heutigen Rechnernetzwerken
und bei der Tatsache, dass viele unserer Rechner heute auch sehr viele
Prozessoren besitzen, ganz interessant ist, wie viel kann ich
tatsächlich Algorithmen beschleunigen, kriege ich sie zum Beispiel
auch in der Berechnungskomplexität runter, zum Beispiel von
quadratisch nach linear, durch solche Parallelisierungen.
So, wir können hier jetzt wieder einen Vergleich durchführen.
Und wir sehen erstmal, der einzelne Vergleich ist natürlich auch von
1, völlig klar.
Dann wissen wir allerdings etwas Schlimmeres, nämlich, wenn wir n plus
n Eingänge haben, also Folgen, dann brauchen wir dazu n plus n, eine
halbe Mischnetzwerke, da stimmt irgendwas nicht.
Ach, stimmt, richtig, rekursives Vorgehen.
Und insgesamt haben wir dann auf die Art Log n Ebenen, und jetzt
können wir wieder rechnen, und zwar, wie wir das schon kennen, mit der
Rekurrenzrelation.
Wir wissen also, für ein Netzwerk von 2, also n gleich 2, haben wir
den linearen Aufwand von 1.
Und ansonsten haben wir, wenn wir n haben, dann haben wir genau
zweimal die Hälfte zu mischen.
Und dazu kommt dann noch dieser Aufwand, nämlich das Mischen über
diese einzelnen Netzwerke.
Das heißt, wir haben hier einmal den Aufwand zu treiben für zweimal
die halben Mischnetzwerke, und dann kommt noch das Mischen selbst,
nämlich dieses Austauschen der Elemente über die geraden und ungeraden
Elemente, das ist eine halbe minus eins.
Und wenn man die löst, dann kommt eben n log n heraus.
Und von den Prozessoren kommt eben auch heraus, dass wir bei n Ebenen
n log n Prozessoren benötigen.
Und wenn man jetzt wieder die Effizienz rausmisst, nämlich wie sieht
die Auslastung aus, dann sieht man halt wieder, es kommt eigentlich
keine besonders gute Auslastung heraus.
Und zwar, je größer n ist, umso schlechter fällt sie aus.
So, das war jetzt doch so ein schneller Ausflug in die
Parallelisierung, der Ihnen einfach mal zeigen soll, dass wir prüfen
müssen, ob sich ein Problem parallelisieren lässt.
Das tun wir dadurch, indem wir zunächst mal das Problem in
Teilprobleme zerlegen, dann schauen wir an, ob diese Probleme
tatsächlich auch unabhängig bearbeiten lassen.
Wenn sie sich unabhängig bearbeiten lassen, dann können wir erst mal
sehen, ob wir sie in parallele Threads packen, die dann auf
unterschiedliche Prozessoren verteilen.
Und dann sollten wir aber nachmessen, was haben wir denn tatsächlich
erreicht und wie viel schneller lösen wir das Problem und welche
Auslastung der Prozessoren erreichen wir.
So, ich hatte ja gesagt, ich springe mit dem Kapitel 17 vor.
Jetzt gehen wir zurück zum Kapitel 15, das ist das letzte, mit dem wir
uns nochmal mit Algorithmen beschäftigen.
Und zwar werden wir uns jetzt noch ein paar geometrische, einfache
geometrische Algorithmen ansehen.
Wir kehren also nochmal zurück an Stellen, an denen wir schon vorher
waren.
Und wenn wir über geometrische Objekte sprechen, dann müssen wir
erstmal sagen, was ist das, worüber wir sprechen.
Und wir sprechen üblicherweise bei Geometrie über einen
enddimensionalen Raum, meistens einen dreidimensionalen Raum.
Häufiger erreicht auch schon zweidimensionaler Raum.
Und da sprechen wir über Punkte, die sich also durch irgendwelche
Koordinaten in unserem enddimensionalen Raum auszeichnen.
Wir sprechen über Geraden, das ist irgendeine Linie, die zu zwei
Punkten geführt wird.
Wir sprechen über Strecken, das sind nämlich Linien, die eben durch
zwei Punkte berandet werden, also durch zwei Endpunkte gegeben sind.
Dann sprechen wir über Streckenzüge, nämlich wir müssen gelegentlich
ja eine Strecke von einem Punkt zum nächsten legen, dann setzen wir
aber die Strecke fort, oder nicht die Strecke, sondern wir marschieren
weiter zum nächsten Punkt und die Strecken, die wir so der Reihe nach
durchlaufen, die bilden dann einen Streckenzug.
Und insbesondere sollte sich herausstellen, dass dieser Streckenzug
geschlossen ist, dann sprechen wir von einem Polygon.
Jetzt interessiert gelegentlich, ob sich ein Punkt, den wir
beispielsweise irgendwo anlegen wollen, ob der sich in einem Polygon
oder außerhalb befindet.
Also müssen wir auch sagen, was ist denn überhaupt innerhalb eines
Polygons und was bezeichnen wir als außerhalb des Polygons.
Und wir können sagen, ein Polygon, bei dem sich die Kanten nicht
kreuzen, da kann man tatsächlich von innen sprechen, in dem
Augenblick, in dem sie sich kreuzen, ist das etwas schwierig zu sagen,
was da innen sein soll, aber solange sie sich nicht kreuzen, können
wir sagen, das ist die Fläche, die von dem Streckenzug, der das
Polygon ausmacht, umrandet wird.
Also, wenn wir sowas haben, dann ist das da halt innen.
Und dann kann man auch noch von einem konvexen Polygon sprechen.
Ein konvexes Polygon ist eines, bei dem wir feststellen, dass jede
Strecke zwischen zwei Punkten unseres Polygons komplett in seinem
Inneren liegt.
Also auch wieder hier.
Da können wir zum Beispiel diese Linie ziehen, sie liegt komplett im
Inneren.
Die können wir ziehen, komplett im Inneren.
Die liegt komplett im Inneren.
Und der Rest ist auf jeden Fall, wenn wir den Rand auch nach innen
legen, liegt er, ist also da auch innen.
Als Schreibweise werde ich noch nehmen, Punkt, einfach durch seine
Koordinaten beschrieben.
Jetzt sehen wir schon, dass ich zweidimensional werde, ohne Strecke
eben dann durch die beiden Endpunkte gegeben.
Einer der beliebtesten geometrischen Objekte sind Schaltpläne.
Wenn Sie sich einen Chip ansehen, dann wird der Chip ja irgendwann,
der wird mal entworfen.
Und früher oder später müssen wir uns mit der Geometrie des Chips
beschäftigen.
Und da gibt es heute, oder da gibt es schon seit 30 Jahren, 25 Jahren
zumindest, ausgekochte Programme.
Die ältesten Programme waren noch nicht mal auf der Chip-Ebene,
sondern die haben folgende Frage gestellt.
Ich habe da so ein Board und jetzt müssen die Boards verdrahtet
werden.
Und wie verdrahte ich, jetzt wenn ich nämlich dann die Kupferbahnen
aufbringe, wie erreiche ich, dass die Bahnen sich nicht kreuzen?
Oder man könnte sogar die Frage stellen, habe ich überhaupt eine
Chance, dass sich die Leiterbahnen nicht kreuzen?
Also die erste Frage ist, gibt es überhaupt eine kreuzungsfreie
Lösung?
Und die zweite Frage ist dann, wie sieht die kreuzungsfreie Lösung
aus?
Und jetzt könnte noch was Drittes kommen, nämlich ich muss noch
Zusatzbedingungen auferlegen, dass zum Beispiel kein Übersprechen
erfolgt, kapazitiv oder induktiv, dass die Leiterbahn eine bestimmte,
zwischen zwei Anschlüssen, eine bestimmte Länge nicht überschreitet.
Und Sie sehen, das werden umsetzlich komplizierte Programme.
Die könnte man auch heute über so ein Grid erledigen, indem ich
einfach Teile davon irgendwo auslagere und jeweils getrennt berechnen
lasse.
Hier ist jetzt beispielsweise so ein Schaltplan und man könnte sagen,
so ein Schaltplan, so wie er da ist, der stellt ja auch eine Menge von
Polygonen dar.
Und jetzt haben wir hier zwei Punkte und die Frage ist jetzt, lassen
sich zwischen den zwei Punkten, lässt sich da noch eine Leiterbahn,
möglichst optimal angeordnet, da noch unterbringen oder nicht?
So, jetzt können Sie probieren.
Wir könnten jetzt probieren, ob das tatsächlich der Fall ist.
Ich schaue gerade mal nach.
Rauskommen tun wir hier.
Kommen wir auch rein?
Ja, wie lautet denn die Antwort?
Nein, also ich finde auch nichts.
Jetzt ist das aber natürlich so eine Glückssache.
Also das ist ja noch überschaubar.
Wenn es noch etwas komplizierter wäre, dann wäre es nicht mehr ohne
weiteres überschaubar.
Infolgedessen muss man zu einer systematischen Antwort kommen.
Eine Antwort könnte beispielsweise folgendermaßen lauten, ich muss mir
das als Polygon mal genauer ansehen und dann, wenn beide Punkte
innerhalb eines Polygons liegen, dann kann ich sie verbinden und wenn
sie beide außerhalb eines Polygons sich befinden, kann ich sie auch
verbinden.
Da muss ich dann noch ein bisschen modifizieren, je nachdem.
Aber wir werden einfach die Frage stellen, innen oder außen von einem
gegebenen Polygon.
Also, hier haben wir jetzt grün markiert ein Polygon.
Das hängt eigentlich ganz schön zusammen, das konnte man vorher auch
nicht so richtig sehen.
Das war gar nicht so ganz klar zu sehen.
Jetzt haben wir es mal ausgefüllt.
Wir können in der Tat bei diesen grünen Dingen von einem Polygon
sprechen.
Jetzt erhebt sich als nächstes die Frage, ist der schwarze Punkt,
jetzt ist nur noch einer da, ist dieser schwarze Punkt innen oder
innerhalb oder außerhalb des grünen Polygons?
Innerhalb heißt also, er liegt in der Fläche, die umrandet ist von dem
Polygon.
Und zwar innerhalb dieser Umrandung.
Und außerhalb heißt halt, dass er sich eben nicht innerhalb befindet.
In dem Fall der grünen Fläche.
Jetzt sehen wir alle, er liegt innerhalb der grünen Fläche.
Können wir das auch systematisch feststellen?
Nun, das Vorgehen ist das folgende, das sehen wir gleich hier.
Wir ziehen eine Linie, eine Gerade, durch unseren schwarzen Punkt,
irgendwie von außen her.
Also wir wissen zumindest, wenn wir weit genug rausgehen, dann sind
wir außen.
Und jetzt schauen wir einfach nach, und zwar auf folgende Weise.
Jedes Mal, wenn wir eine Polygonkante kreuzen, ändern wir von außen
nach innen oder von innen nach außen.
Und am Ende, wenn wir außen beginnen und wir erreichen schließlich
unseren Punkt, dann gilt eben genau das letzte Merkmal, also innen
oder außen, als Charakteristikum für diesen schwarzen Punkt.
Also fangen wir mal an.
Wir beginnen außen.
Jetzt kommen wir ja hier zuerst mal innen, dann gehen wir wieder nach
außen.
Wir wechseln wieder nach innen, wir wechseln wieder nach außen.
So, und jetzt wissen wir, der Punkt liegt außen.
Das ist doch eigentlich ganz interessant.
Jetzt müssen wir natürlich nachsehen, er liegt da tatsächlich nach
außen, denn wie wir sehen, kämen wir ja da raus.
So, und jetzt müssen wir einen Beweis führen, dass das Verfahren auch
ausreicht, dass also selbst wenn wir jetzt noch weiterlaufen, dass wir
trotzdem außen bleiben.
Hier können wir ja auch vorgehen.
Hier können wir auch sagen, außen, innen, außen.
Jetzt haben wir hier allerdings noch eine Stelle, da ist ein Problem,
da betreffen wir auf dem Punkt Tangential.
Also noch die Frage, wie wir vorgehen, wenn wir auf Tangentialpunkte
stoßen.
Und da gilt auch folgende Regel, nämlich wenn beide Kanten auf
derselben Seite liegen, dann ändern wir die Beschreibung der
Augenblicke nicht und sonst ändern wir.
Jetzt schauen wir mal an, wir sind hier wieder außen, dann gehen wir
hier wieder innen, dann haben wir hier wieder außen.
Und jetzt kommen wir hier an eine Stelle, die erfüllt offensichtlich
diese Bedingung hier, zwar jetzt auf der rechten Seite, nicht auf der
linken Seite, also bleibt es unverändert, also ist das hier außen.
Wir laufen wieder nicht weiter, also müssen wir doch nachgewiesen
werden, dass wir in der Tat gar nicht mehr weiterlaufen brauchen, also
den Rest nicht mehr zu betrachten haben und trotzdem garantiert das
korrekte Ergebnis haben.
Zunächst, jetzt erhebt sich also die Frage, jetzt geben wir uns mal
ein allgemeines Polygon vor, die grundsätzliche Vorgehensweise kennen
wir ja und wir geben uns ein Polygon als eine Folge von N Punkten vor
und wir fragen uns, ob ein Punkt UV, den wir auch vorgeben, ob der
also jetzt innerhalb oder außerhalb des Polygons liegt, so gerade wie
wir es jetzt gezeigt haben.
Und jetzt können wir einen Algorithmus hinschreiben, nämlich wir sehen
gerade eine Halbgerade, nehmen wir von UV,
setzen den Ort jetzt erstmal 1 gleich außen und dann laufen wir
einfach durch und betrachten die einzelnen Kanten und schauen nach,
indem wir jetzt hier das Polygon der Reihe nach durchlaufen, jede
Kante, schauen wir nach, und zwar entsprechend der Abfolge, die wir
hier haben, falls sich unsere Halbgerade und die neue Kante schneiden
und dies aber nicht in einem dieser Eckpunkte tun, dann ändern wir
einfach den Ort ab, das heißt wir gehen von außen nach innen oder von
innen nach außen und setzen das halt so lange fort, bis wir den Punkt
erreicht haben, beziehungsweise bis wir alle Kanten abgearbeitet haben
und wenn wir eben den Punkt selbst tangential schneiden, dann wird
eben gerade diese Prüfung gemacht, die ich Ihnen gesagt habe, nämlich
wenn die auf der gleichen Seite von H sind, dann setzen wir genau um.
Jetzt muss ich gerade noch ansehen, auf der gleichen Seite von H,
stimmt das überhaupt?
Denn wir hatten ja diese Situation hier,
hier hat man gesagt, hier wird gewechselt, hier wird gesagt, hier
bleiben wir auf der gleichen Seite, also dürfte es einfach nicht
wechseln und insofern sind wir ganz sicher, ob das stimmt.
Haben Sie mal nachgesehen, Herr Pfeiffer?
Ich überlege nämlich gerade, ob das überhaupt stimmt, was ich da
stehen habe.
Ich bin ja hier, gehen wir mal nochmal los.
Wir haben hier ein Polygon, jetzt probieren wir es mal aus.
Wir nehmen mal hier ein ganz einfaches Polygon.
Wir nehmen hier den Punkt H, ziehen eine Halbgerade,
jetzt ziehen wir die Halbgerade mal zu, das ist H.
So, dann gehen wir zum Beispiel hier los, nehmen als erstes diese
Kante, schneidet überhaupt nicht, also ändert sich nichts, wir
schneiden diese Kante hier in ein, und zwar liegen sie jetzt beide auf
der gleichen Seite.
K
und...
das heißt, liegen auf der gleichen Seite, nee, das müsste sein auf
verschiedenen Seiten.
Behaupte ich mal.
Aber Sie dürfen nochmal nachprüfen.
Mir erscheint in der Eile jedenfalls, dass das verschieden heißen
müsste.
Naja, aus meinem Augenblick glaube ich das auch, aber ich muss mir das
nochmal genau anschauen.
Wir prüfen nochmal nach.
Ich habe den Eindruck, es müsste verschieden heißen.
Oder nicht auf gleicher Seite, was immer.
So, konstanter Aufwand.
Jetzt gehen wir mal einen Schritt weiter, jetzt haben wir also Punkte
bestimmt, wir haben einen Algorithmus, der besagt, liegt etwas in oder
außerhalb eines Polygons.
In Wirklichkeit interessiert es uns in der Tat mehr, gibt es zwei
Punkte, die auf der gleichen Seite liegen, die ich also verbinden
kann.
Oder, wenn das nicht der Fall ist, dann kreuze ich offenbar
Leiterbahnen.
Jetzt kommen wir auf das nächste, was uns interessiert.
Wir geben hier mal eine Punktmenge vor.
Und wir fragen uns, kann ich da ein Polygon durchlegen.
Jetzt ist ja nichts eindeutig an dieser Stelle.
Beliebige Zahl von Polygonen, die ich hier durchlegen kann, manche
ekelhaft und manche weniger ekelhaft.
Die Frage ist also einfach, kann ich auch konvexe Polygone da
durchlegen.
Das ist deshalb interessant, weil Sie beispielsweise eben
computergesteuerten CAD konstruieren, weil Sie ja mehrere
Darstellungen haben für Körper.
Und eine Darstellung nimmt zum Beispiel nur die Eckpunkte.
Die Eckpunkte definieren zunächst mal ja nicht eindeutig einen
geometrischen Körper, sondern relativ viele.
Und die Frage ist also, können wir trotzdem nach irgendeiner
Gesetzmäßigkeit eindeutig einen geometrischen Körper für eine solche
Punktmenge angeben.
Zum Beispiel, das könnte einer sein.
Nicht besonders schön, aber immerhin.
Er ist insbesondere konvex.
Er ist auch nicht konvex, das stimmt auch nicht.
Aber er hat keine Kanten, die sich überschneiden.
Er könnte auch so aussehen.
Also wir brauchen jetzt Kriterien, die sagen, welcher davon ist für
uns der geeignetste.
Und der ist besonders miserabel, denn da schneiden sich nun die
Kanten.
Beispielsweise könnte es so sein, dass wir mal ein Problem haben, bei
dem wir sagen, wir müssen einen Vollkörper irgendwie erzeugen und das
da ist auf keinen Fall produzierbar.
Also angenommen, wir wollen zumindest eine Forderung erfüllen, nämlich
die, es soll überschneidungsfrei sein.
Hier habe ich einen ganz einfachen Algorithmus.
Sie wissen ja, wir sagen, wenn das ein Problem einfach aussieht,
vielleicht löst auch schon Brute Force, also mit Gewalt.
Und Greedy Algorithmus ist ein solcher Algorithmus, der mit Gewalt
eine Lösung liefert.
Nämlich, wir fangen mit der beliebigen Kante an und wenn das Polygon
noch nicht fertig ist, dann müssen wir halt eine weitere Kante
hinzufügen.
Das heißt, wir ziehen eine weitere Kante zwischen dem Endpunkt, den
wir erreicht haben, und einem weiteren Punkt.
Jetzt können wir die Kante noch irgendwie anordnen, zum Beispiel nach
der Länge, um dann tatsächlich einen Greedy Algorithmus zu erhalten.
Wir fügen die Kante hinzu, die keine vorhandene Kante schneidet und
nicht vorzeitig das Polygon schließt, also nicht noch irgendwelche
Punkte übrig lässt.
Jetzt wenden wir das hier bei unserer Punktmenge mal an.
Da haben wir eine Kante gezogen, kein Problem.
Wir ziehen eine weitere Verbindung, wir setzen noch lieber fort, wir
ziehen einfach Kanten erstmal.
Wir ziehen noch eine Kante, wir ziehen noch eine Kante.
Jetzt wird es schon etwas schwieriger, aber zum Beispiel hier
funktioniert es auch noch.
Die funktioniert noch.
Jetzt haben wir eigentlich auch nur noch einen einzigen Punkt übrig.
Den hier, nur haben wir jetzt leider zwei getrennte Streckenzüge,
jetzt müssen wir schließen.
Und schließen müssen wir ja, wir sehen, dass das ein Endpunkt ist.
Das ist ein Endpunkt.
Nein, da haben wir auch noch einen, richtig.
Aber wir haben jetzt hier noch Endpunkte.
Und die letzte Kante kriegen wir nicht mehr geschlossen, der hält
nicht mehr hin, ohne dass es zu einer Kreuzung kommt.
Also der Algorithmus ist irgendwie, scheinbar im Allgemeinen nicht zu
funktionieren.
Jetzt können wir Folgendes machen.
Wir legen doch so los, wie ich gerade beschrieben habe, aber wir
versuchen dann anschließend, Kreuzungen loszuwerden.
Zum Beispiel nehmen wir an, wir hätten da jetzt zwei Streckenzüge, den
hier und den hier hätten wir schon konstruiert.
Und jetzt fangen wir an, noch zwischen den offenen Punkten
Verbindungen zu ziehen und es kommt zum Beispiel so eine Kreuzung
zustande.
Das heißt, wir hätten erst die eine Linie gezogen und beim Versuch,
die zweite Linie zu ziehen, kommt es zu einer Kreuzung.
Dann sähe das halt so aus.
Ich muss einfach eine Änderung vornehmen und wir nennen diese Änderung
Auflösen von Kreuzungen.
Das heißt, wir gehen einfach erst mal da unseren Gridi-Algorithmus
vor.
Man könnte sowas als ein optimistisches Verfahren nennen, nach dem
Motto, es wird schon gut gehen.
Und wenn wir am Schluss schauen, es ist wirklich gut gegangen und an
den Stellen, an denen es nicht gut gegangen ist, dort lösen wir die
Kreuzungen auf.
In diesem Fall ist das ganz einfach.
Wir lösen die Kreuzungen auf und probieren jetzt mal eine andere
Verbindung.
Leider kann eigentlich mal sowas passieren.
Wir sind wieder so weit wie zuvor, nur jetzt ist das ein bisschen
anders.
Und da oben gibt es also auch schon so eine Stelle, wo auch schon
Verbindungen erzeugt haben.
Und wenn ich jetzt die Kreuzung auflöse, dann habe ich prompt an
dieser Stelle neue Kreuzungen erzeugt.
Jetzt könnte man uns die Frage stellen, so what?
Dann muss ich halt diese Kreuzungen auch auflösen.
Das heißt, ich erzeuge möglicherweise neue Kreuzungen, aber ich setze
das Ganze eben fort.
Ich erarbeite jetzt die weiteren Kreuzungen ab und insbesondere
schlage ich halt Neukreuzungen, die hier beim Auflösen entstehen, eben
wieder der Liste der Kreuzungen zu.
Frage, endet das irgendwann?
Sind wir am Ende tatsächlich kreuzungsfrei und sind wir nach endlich
vielen Schritten kreuzungsfrei?
Schauen wir mal.
Wir wissen eines auf jeden Fall.
In jedem Schritt wird die Gesamtlänge aller Kanten um einen positiven
Wert verringert.
Und das kann man sich schnell überlegen, wieso das so ist.
Nämlich, da gilt ja einfach die Dreiecksungleichung und die
Dreiecksungleichung besagt eben, dass, wenn wir das
auseinanderschneiden, also die alte und neue Regel, dann ist ganz klar
die jetzige Länge geringer geworden als zuvor.
Wir könnten also argumentieren, wenn wir richtig vorgehen, dass wir
mit jedem Auflösen einer Kreuzung die Gesamtlänge etwas verringern.
Das heißt, wir werden irgendwann mal auf ein Minimum kommen, weil wir
in jedem Schritt, wenn wir eine Kreuzung auflegen, die Gesamtlänge
unseres Polygons verringern.
Also werden wir irgendwann mal auf eine Minimallänge kommen, die wir
nicht unterscheiden können.
Also sieht es so aus, als ob wir terminieren.
Man muss jetzt noch nachweisen, dass zusätzlich auch tatsächlich das
Ergebnis selbst eben dann keine Kreuzungen mehr enthält.
Aber wir haben gesagt, wir lösen ja so lange Aufkreuzungen, bis die
Länge minimiert ist.
Also kann man sich einfach überlegen, vorstellen, wir nehmen
tatsächlich das Primitivverfahren, verbinden erstmal alle Punkte zu
einem Polygon, untersuchen dann anschließend, wo die Kreuzungen
existieren, lösen die Kreuzungen auf...
und wir wissen, dass dieses Vorgehen terminiert, weil wir irgendwann
die minimale Länge erreicht haben.
Wir verkürzen jedes Mal die Länge um einen Schritt.
Und zum Zweiten, dass wir tatsächlich dann auch zwingend am Ende alle
Kreuzungen beseitigt haben müssen.
So, also terminiert.
Es gibt keine Kreuzungen mehr.
Aber man könnte ja argumentieren, besonders elegant ist der
Algorithmus nicht.
Er fängt primitiv an und zwingt uns hinterher immer Kreuzungen
aufzulösen.
Ich gebe Ihnen noch ein weiteres Verfahren.
Übrigens, dass ich Ihnen hier einfach mal so ein paar Algorithmen nur
so anschaulich vorführe, heißt nur, gegeben ein Problem, es gibt
meistens mehrere Algorithmen, oder häufig mehrere Algorithmen, die das
Problem lösen.
Und man sollte nicht beim ersten gleich aufgeben, nur weil der Aufwand
zunächst mal groß erscheint, sondern sich überlegen, gibt es nicht
tatsächlich doch andere Lösungen, die dazu führen, dass man auch den
Aufwand verringern kann.
Entweder den Rechenaufwand oder den Speicheraufwand.
Und hier ist noch so eine Idee.
Wir ziehen um unseren Punkt, oder wir lassen so eine Kreisscheibe über
alle Punkte rotieren.
Also wir haben einen Kreis, und ziehen dann sozusagen eine Linie
drüber, und die lassen wir einfach rotieren.
Und jeden Punkt, den wir erreichen, verbinden wir einfach mit dem
vorhergehend erreichten Punkt.
Das sieht folgendermaßen aus, hier haben wir wieder unsere Punkte,
jetzt ziehen wir einen Kreis, hier haben wir natürlich einen
Mittelpunkt gezogen, hier ist der Mittelpunkt, und jetzt ziehen wir
einfach diese Kante über die Punkte, und dann sieht man deutlich, den
ersten Punkt, den wir erreichen werden, ist dieser hier, der zweite
Punkt, den wir erreichen werden, ist dieser hier, der dritte ist
dieser hier, der vierte hier, ist hier, und wir verbinden einfach
immer diese Punkte.
Also hier haben wir zum Beispiel angefangen, hier haben wir, wir sehen
erstmal die Punkte eins, zwei und drei verbunden, und hier sind wir
schon sehr weit, nämlich, wir haben fast ausgefüllt, und wir sehen
auch deutlich, was uns noch zu tun bleibt, ist das hier kreuzungsfrei.
Ohne, dass wir überhaupt einfach, dass wir die, wie zuvor, erstmal
überhaupt Kanten gezogen haben, und dann noch diesen Graph
analysieren, die Polygone analysieren müssen, um zu sehen, ist er
kreuzungsfrei, hier wird uns die Kreuzungsfreiheit ja geschenkt.
Also ganz einfaches Verfahren, um kreuzungsfrei zu arbeiten.
Auch da fragt man sich natürlich erstmal, ob das immer geht, oder gibt
es da irgendwelche typischen Situationen, bei denen es nicht geht.
Antwort, geht es immer oder nicht?
Nein.
Es gibt natürlich abartige Situationen, hier haben wir die Situation,
wir können immer sagen, zunächst mal liegt die neue Kante außerhalb
des bisherigen, weil sie außerhalb des überstrichenen Bereiches liegt,
aber jetzt kommt hier unser Problem, wenn der Radius 180 Grad
zurückgelegt hat, und keine Kante getroffen hat, dann fehlt uns so ein
Stück, was uns mal da raustreibt, und dann entsteht also hier in
dieser Situation zunächst mal erst das gleiche, und wenn wir jetzt
weitergehen, dann ziehen wir am Schluss eine Kante hier rauf, von
diesem Endpunkt, und der wird überschneitet, kommt am Schluss noch
diese dazu, aber wir haben eine Kreuzung drin, nämlich an dieser
Stelle.
Abhilfe.
Jetzt würden wir wieder Folgendes sagen, naja, wir haben ja gerade
vorhin gesehen, dass man einfach solche Kreuzungen entfernen kann,
indem wir dann die Einfachheit durch Kanten vertauschen, indem wir die
Kanten neu verbinden, die die Kreuzung ausmachen, das könnten wir
nicht hier auch machen, wir könnten also die Kante beseitigen.
Zweite Variante ist, also hier könnten wir erstens die Kreuzung
beseitigen, das wäre eine Möglichkeit, zweite Möglichkeit wäre,
immer unter 180 Grad bleiben.
Das wäre auch eine Lösung.
Na, wie bleibe ich jetzt unter 180 Grad?
Wie bleibe ich garantiert unter 180 Grad?
Eine primitive Regel ist die, wähle einfach den Radius der
Kreisscheibe so, dass er in der Mitte von drei Punkten liegt.
Dann treffe ich garantiert immer noch weniger als 180 Grad auf einen
Punkt.
Oder eine andere Möglichkeit, wähle einen Randpunkt.
Dann habe ich immer alles auf einer Seite, kann auch nicht schief
gehen.
Und jetzt nehmen wir wieder diesen Fall hier.
Zum Beispiel habe ich hier den roten Punkt, also meinen Radius, jetzt
so gewählt, dass er innerhalb dieser drei Punkte hier liegt.
Und damit ist garantiert, dass ich auf jeden Fall immer nach weniger
als 180 Grad auf irgendeinen Punkt stoße.
Und dann wissen wir ja, in dem Fall kommt ein kreuzungsfreies Polygon
zustande.
Zum Beispiel sehen wir es hier jetzt, wenn wir es jetzt drüber laufen
lassen, dann würde hier jetzt Folgendes entstehen.
Wir stoßen auf diesen hier, dann stoßen wir auf diesen hier, dann
stoßen wir auf den hier, dann stoßen wir auf den hier.
Hier eine andere Lösung, wir nehmen einen der Randpunkte.
Hatte ich gesagt, auch eine Möglichkeit.
Nehmen wir diesen hier als Randpunkt.
Wenn wir das als Randpunkt wählen und lassen wieder rüber laufen, dann
sehen wir, dass wenn der überhaupt über 180 Grad rüber streicht, das
ist hier tatsächlich der Fall, dann wird dort auf keinen Punkt
gestoßen.
Das heißt, es gibt auf jeden Fall der Winkel, in dem wir überhaupt
Punkte vorfinden, die zu verbinden sind, ist kleiner als 180 Grad.
Gut, dann können wir wieder sehen, wir nehmen zum Beispiel diesen
Punkt als Startpunkt.
Kommt dieser wieder zustande, dieser wieder zustande, dieser hier
zustande, kommt wieder das gleiche Polygon zustande.
Das ist beispielsweise, wenn wir nur Punkte vorgegeben haben und dann
eben beispielsweise einen Streckenzug durch alle durchlegen müssen,
derart, dass keine Kreuzungen zustande kommen.
Aber dann ist das ein einfaches Beispiel, man wird meistens noch
zusätzliche Bedingungen angeben, über die Form beispielsweise das
Polygon haben muss.
Jetzt können wir weiteres mit Polygonen tun, beispielsweise wäre auch
eine Möglichkeit, wir fordern, wir geben uns wieder eine Punktmenge
vor und wir wollen jetzt eine konvexe Hülle haben.
Und das mit der konvexen Hülle unserer Punktmenge meinen wir jetzt ein
Polygon, dass wir um diese Punkthülle herumziehen, derart, dass alle
Punkte im Innern liegen.
Und dann stellen wir noch eine Zusatzforderung, wir verlangen nämlich,
dass das kleinstmögliche Polygon gefunden wird.
Also, wir geben uns wieder mal so etwas vor, hier ist eine Punktmenge
und jetzt erhebt sich die Frage, wie kriegen wir das kleinste Polygon?
Da reicht es nicht aus, nur unsere vorherige Lösung, sondern jetzt
muss es kleinstmöglich sein.
Und insbesondere müssen wir auch gar nicht mehr alle Punkte verbinden,
wir müssen nur sicherstellen, dass alle Punkte im Innern liegen.
Man würde vermutlich tatsächlich sagen, dass das kleinstmögliche, das
kleinste Polygon, das wir ziehen können, bei dem alle Punkte im Innern
liegen.
Und die Frage ist wieder, wie erzeugt man so etwas systematisch?
So, eine Möglichkeit ist die folgende.
Wir bilden zunächst einmal, wir wählen drei beliebige Punkte aus und
das ist ein Startpolygon.
Und dann müssen wir jetzt diesem Startpolygon möglicherweise weitere
Kanten hinzufügen.
Das machen wir folgendermaßen, wir nehmen einen Punkt, der noch nicht
bearbeitet ist.
Schauen nach, liegt er innerhalb unseres Polygons, das wir bisher
erzeugt haben?
Braucht man nichts zu tun.
Ist unsere Bedingung erfüllt?
Liegt er außerhalb, dann müssen wir offenbar unser Polygon etwas
vergrößern.
Also versuchen wir mal hier.
Wir nehmen an, wir seien soweit schon gedient.
Das ist die bisherige Hülle, also wir sind schon drei Punkte, dann
haben wir vier gehabt, können nochmal zurückgehen.
Und jetzt aber liegt da hinten noch so ein Punkt.
Der muss mit einbezogen werden.
Und jetzt wäre ein Verfahren das folgende, wir fangen einfach an, da
irgendwie so tangential heranzugehen.
Das heißt, wir nehmen den Punkt hier.
Wir ziehen zwei Linien, die tangential das bisherige Polygon, also die
bisherige Hülle, verbinden.
Das sind dann die stützenden Kanten, also die Kanten, die unseren
Punkt stützen.
Und dann ziehen wir einfach diese als neue Kanten.
Und alle Punkte, die jetzt in das Innere fallen, die tragen nicht mehr
bei.
Das heißt, wir entfernen infolgend diese blauen Kanten dann.
Das wäre also eine Möglichkeit, weil wir sehen, dass ich eigentlich
immer nach außen gehe.
Ich fange mit einem kleinen Polygon an und dehne das dann so nach
außen.
Wenn neue Punkte hinzukommen, nennt man den also ein Stretching
-Algorithm oder Ausdehnungsalgorithmus.
Hier habe ich mal so ein Beispiel, das sind unsere ersten drei Punkte.
Wir haben ja schon geschickt gewählt, wir sehen nämlich schon, dass
zwei weitere Punkte im Inneren liegen.
Jetzt wählen wir, wie wir gesehen haben, erstmal diesen Punkt.
Müssen jetzt nach außen gehen, jetzt strecken wir, also ziehen wir
hier jetzt unsere stützenden Kanten.
Und dann werden diese stützenden Kanten voll ausgezogen und diese
innere Kante, die jetzt schwach markiert ist, die fällt weg.
Jetzt nehmen wir als nächstes offensichtlich diesen Punkt, machen
wieder genau das gleiche, strecken also jetzt unser Polygon da nach
links.
Dann haben wir noch diesen Punkt hier, strecken nochmal das Polygon
etwas, damit kriegen wir jetzt wieder neue Kanten und eine der alten
Kanten entfällt.
Und jetzt müssen wir noch diesen Punkt hier unterbringen und dehnen
das nochmal hier.
Das heißt, Sie sehen, wir laufen einfach rum und erhalten da so ein,
per Ausstrecken, per Strecken wird dann jeweils das Polygon notfalls
erweitert.
Kann ich auch wieder als Algorithmus angeben.
Und jetzt können wir noch ein bisschen auswählen, jetzt haben wir also
folgendes.
Ich betrachte, ich gebe also ein beliebiges Dreieck vor.
Jetzt nehme ich irgendeinen beliebigen Punkt und wenn dieser Punkt
nicht innerhalb der aktuellen Hülle ist, dann füge ich jetzt eine
Kante hinzu, zu dem bisherigen Hüllenpunkt mit dem kleinsten Winkel zu
P und dem Punkt mit dem größten Winkel zu P. Jetzt schauen wir mal an,
was das hier heißt.
Das ist eigentlich genau das, was ich vorhin schon mal vorgezeigt
hatte.
Wir haben also hier unsere X-Achse.
Das ist der Punkt, der uns hier interessiert.
Jetzt müssen wir also ansehen, welcher der Punkte der aktuellen Hülle
hat den kleinsten Winkel zu P und welcher den größten Winkel zu P. Da
ziehen wir uns jetzt erstmal so eine Parallele zur X-Achse.
Es gibt einen positiven Winkel, der wird also den Punkt mit dem
größten Winkel bestimmen.
Und es gibt einen negativen Winkel, möglicherweise an dieser Stelle
jedenfalls, der den kleinsten Winkel bestimmen wird.
So, jetzt sehen wir schon, wenn wir jetzt hier zu allen Punkten
jeweils den Winkel bestimmen, dann ist das der Punkt mit dem kleinsten
Winkel, mit dem größten negativen Winkel, und das ist der Punkt mit
dem größten positiven Winkel.
Und die beiden werden verbunden und alle Punkte, die jetzt
reinrutschen ins Innere, deren Kanten werden entfernt.
Also wird jetzt hier der zu diesem Punkt gezogen, kleinster, und hier
zum größten Wert.
Und nachdem wir das haben, wandelt sich das jetzt in die
entsprechenden Kanten und die inneren Punkte, die bisherigen blauen
Kanten, fallen weg.
Also wir berechnen einfach den, statt diesem Kantenziehen,
Tangentenziehen, berechnen wir einfach den kleinsten und größten
Winkel.
Da kann man also auch jetzt wieder den Aufwand ansehen und stellen
fest, ich muss alle Knoten betrachten und ich muss immer alle Winkel,
bei jedem Punkt muss ich erneut alle Winkel zu allen anderen Punkten
berechnen, also ist das irgendwo mit quadratischem Aufwand verbunden.
Könnt ihr auch anders machen.
Hier ist ein weiterer Algorithmus, der ähnelt von der Anschauung her
unserer Kreisscheibe.
Ich nehme einfach wieder so einen dehnbaren Faden in die Hand und
entwickle ihn einfach außenrum.
Jetzt wickeln wir den mal rum.
Wir fangen mit dem roten Punkt an.
An dem befestigen wir unseren Faden.
Und jetzt fangen wir an, mit dem Faden zu ziehen und ihn gleichzeitig
entgegen dem Uhrzeigersinn zu drehen.
Dann drehen wir also dahin.
Und dann ist das zunächst mal die erste Kante bis zu diesem Punkt hin.
Jetzt nehmen wir unseren Faden und versuchen wieder weiter zu ziehen
und zu drehen entgegen dem Uhrzeigersinn.
Dann ist natürlich offensichtlich, dass der nächste Punkt, der da ist.
Also ziehen wir den Faden da rum.
Und die Strecke bis zu diesem Punkt ist jetzt die zweite Kante.
So, jetzt können wir wieder ziehen.
Es ist offensichtlich, dass der nächste Punkt, den wir jetzt anstreben
werden, der da oben ist.
Also ziehen wir wieder.
Und erhalten jetzt hier die nächste Strecke.
Das kann man jetzt fortsetzen.
Dann kommt das da zustande.
Und so weiter.
Noch einen Schritt weiter.
So, jetzt können Sie sich ja vorstellen, jetzt ziehen wir nochmal
weiter, dann kommen wir hier hin.
Und dann ziehen wir nochmal weiter und kommen schließlich hier hin.
So, jetzt müssen wir uns, wenn wir jetzt programmieren würden, ein
Java -Programm schreiben würden, dann müssen wir jetzt den Faden halt
simulieren.
Dann können Sie ja meinetwegen ein Objekt faden.
Aber jetzt müssen wir halt das, was wir jetzt anschaulich gesehen
haben, irgendwie umrechnen oder umformulieren in etwas, was wir
algorithmisch behandeln können.
Da könnte zum Beispiel auch wieder der Winkel eine Rolle spielen.
Das heißt, wir drehen uns einmal im Kreis rum und reduzieren
systematisch den Winkel, bis wir auf den nächsten Punkt kommen.
Wäre eigentlich eine nette Übung, das Ganze mal zu überführen in einen
Algorithmus.
Und wie wir sehen, leider auch da die Idee, so schön sie ist, sie
bringt uns nicht vom quadratischen Aufwand weg.
So, hier sieht man schon, dass man irgendwie mit Winkeln rechnet.
Hier gibt es noch einen weiteren Suchalgorithmus, der sieht
folgendermaßen aus.
Ich ordne jetzt, der erste Trick besteht also darin, meine Punkte
entsprechend ihrer Winkel, und zwar, ich berechne als erstes die
Winkel der Verbindungen aller Punkte zu P1, also ich wähle irgendwie
einen äußeren Punkt, P1, und ich berechne dann den Winkel wiederum
dieser Punkte aller anderen Punkte gegenüber diesem Punkt P1, und zwar
bezüglich der X-Achse.
Und jetzt ordne ich diese Punkte, das heißt ich sortiere sie
entsprechend diesem Winkel.
Das ist auch ganz klar, weil ich einmal um 180 Grad mich drehen will,
also werde ich die einfach jetzt entsprechend der Größe und
Orientierung sortieren.
Und jetzt gehe ich los.
Ich nehme also einen Punkt nach dem anderen auf.
Ich muss nachschauen, wenn ich den letzten Punkt betrachte, den ich
bereits in meiner konvexen Hülle drin habe, und ich frage mich, also
jetzt ist der neue Punkt über einen Inwinkel kleiner als 180 Grad
erreichbar.
Wenn das der Fall ist, dann füge ich die Kante von PI-1 zu P hinzu.
Wenn das nicht der Fall ist, dann muss ich das PI-1 aus der Hülle
entfernen, und alle auch davor liegenden Punkte von denen, die über
den Innenwinkel größer als 180 Grad erreichbar sind.
Das ist also ein bisschen anders als das, was ich bisher hatte.
Da habe ich mir immer so gezogen an den Faden, und da bin ich nicht
aus Versehen mal in das Innere der Hülle reingeraten.
Aber jetzt, wenn wir hier rein ordnen, nach der Orientierung, da kann
es schon sein, dass wir auch an Punkte reingeraten, die eigentlich am
Ende ins Innere reingehören.
Und die müssen einfach zu einem Zeitpunkt, zu dem wir entdecken, dass
sie ins Innere gehören, und das ist genau diese Bedingung hier.
Wenn diese nicht erfüllt ist, dann fällt der Punkt in das Innere rein,
und dann müssen wir die vorigen Schritte rückgängig machen.
Gut, schauen wir uns das mal hier an.
Nehmen wir an, das war der Anfangspunkt PI-1.
Wir haben jetzt immer sortiert nach dem Winkel, mit dem wir uns
orientieren gegenüber der X-Achse.
Und da wir das der Äußerste sind, haben wir noch Winkel in der
Gegenrichtung, also über 90°.
Wir haben hier einen mit 90°.
Wir haben hier einen Innenwinkel, der auch irgendwie zunächst mal
weniger als 180° ist.
Wir gehen zu diesem Punkt über, ist auch wieder kleiner als 180°.
Wir gehen nochmal weiter, kleiner als 180°.
Und jetzt ist der nächste Punkt, den wir erreichen, ist dieser hier.
Ja, man kann es noch ganz schwach sehen, dass der tatsächlich ein
bisschen größer ist als der X-Winkel zu diesem Punkt.
Jetzt ist der Innenwinkel, den wir hier beschreiben, größer als 180°.
Das aber, haben wir gesagt, lassen wir nicht zu.
Also, sagen wir zunächst mal, dieser Punkt hier, der gehört ins Innere
rein.
Wir gehen einen Punkt zurück und müssen jetzt allerdings uns diesen
Innenwinkel ansehen.
Da hätten wir eigentlich hingehen sollen und stellen fest, der ist
auch größer als 180°.
Also kommt auch dieser Punkt nicht in Frage.
Wir gehen einen weiteren Punkt zurück und sagen, gut, wenn die anderen
im Innen liegen, dann hätte ich hier zur PI die Kante ziehen müssen.
Und die hat nun mal weniger als 180°, also wird diese Kante hier
gezogen und die beiden anderen Kanten und Punkte werden entfallen.
Die Kanten entfallen und die Punkte werden ins Innere verlagert.
Also fällt das weg und es fällt das weg.
So, das ist ein Algorithmus, den kann man im Grunde genommen durch
diese Vorsortierung und die Berechnung des Winkels etwas besser
formulieren als das Band, das ich vorher herumgezogen habe.
Aber ich lade Sie ein, sich mal zu überlegen, wie die Lösung mit dem
Band aussehen würde.
Ja, jetzt haben wir noch einen weiteren Vorteil.
Denn es stellt sich heraus, dass wir jeden Punkt nur genau einmal
anfassen und das O von N.
Nur, vorher müssen wir sortieren.
Und das N log N, also ist der Gesamtaufwand wieder N log N.
Und wir müssen einfach sagen, dass im Grunde genommen wir die meisten
Probleme, also sehr viele Probleme, die quadratisch sind, dadurch
lösen können, dass wir einfach vorsortieren und dann linear
abarbeiten.
Das heißt, dass wir bei vielen Problemen, die zunächst mal
quadratischen Aufwand haben, ansehen sollten, gibt es eine Ordnung?
Lässt sich eine lineare Ordnung angeben?
Wenn ja, dann sortieren wir vor und da braucht man nur noch einen
linearen Algorithmus, der dann anschließend die Elemente aus dieser
sortierten Reihenfolge herausgreift.
Also ein ganz typisches Problem, wie man von N² wenigstens zu N log N
kommt.
Ja, hier haben wir ein weiteres Problem.
Wir sind immer noch bei Punktmengen, denen wir irgendwie eine
geometrische Gestalt geben wollen, oder zumindest die wir bezüglich
irgendwelcher geometrischen Gestalten beurteilen wollen.
Eine, die enorm verbreitet ist, auf die werden Sie auch im
Hauptstudium sehr häufig stoßen, ist die sogenannte Ballung.
Man nimmt sogar irgendwie ein ganz anders geartetes Problem, aber wir
setzen es zu einer geometrischen Forderung.
Wir haben also hier eine Punktmenge und wir fragen uns, lässt sich
diese Punktmenge irgendwie einteilen oder gruppieren derart, dass wir
eine gewisse Homogenität erreichen, dass also was dicht beinahe
zusammenliegt, umschlossen wird von einem geometrischen Körper und der
Rest davon wird getrennt.
Also nehmen wir zum Beispiel das da an.
In wie viele homogene Punktmengen können wir diese Punktmenge
einteilen Ihrer Ansicht nach?
Was würden Sie sagen?
Wie viel?
Na, wie viel würden Sie denn daraus machen?
Wie viele Punktmengen?
Drei, hier ist ein Vorschlag, drei.
Andere Meinungen dazu?
Wie viele würden Sie machen?
Auch drei, ja.
Aber immerhin, wo würden Sie denn dann, wenn Sie drei sagen, diesen
Punkt hinschaffen?
Würden wir nach rechts schaffen, irgendwie mit den restlichen Punkten?
Ja, aber dessen Abstand ist doch eigentlich von dem links unten,
dieser Punktwolke, doch geringer als zum nächsten Punkt rechts.
Also wir brauchen ein Kriterium.
Es gibt das vor so Stellen, da ist man sich nicht so ganz sicher.
Also, das ist der naheliegende Vorschlag, aber wie gesagt, wenn ich
mir das ansehe hier, und das ist der nächste, dann gehört er doch
eigentlich mehr darüber.
Oder durch einfach so, durch visuelle Inspektionen hat man den
Eindruck, natürlicher wäre es aber anders.
Ha, das wäre auch eine Möglichkeit.
Und warum soll die schlechter sein?
Wer ist der Meinung, die Grüne ist schlechter als die Rote?
Ha, warum?
Aha, es wird argumentiert, die Grüne sähe sehr willkürlich aus.
Also verlangen Sie nach einem Kriterium.
Sie wollen also schon sagen können, dass wir nicht willkürlich
vorgehen, sondern dass wir ganz bestimmte Kriterien anlegen.
Also müssen wir uns überlegen, was sind denn die Kriterien?
Wonach ballen wir?
So, das ist also ein typisches Bild, was wir bei der Klassifikation
vorfinden.
Klassifikation kommt zum Beispiel bei der Sprachverarbeitung so häufig
vor.
Oder wenn wir in der Bildverarbeitung, Bilderkennung, überall kommen
Klassifikationsprobleme vor.
Also wir sprechen hier wieder von einer Problemklasse, die
ausgesprochen große praktische Bedeutung hat.
So, das erste worüber wir uns einigen müssen ist, dass wir scharf
klassifizieren.
Jeder Punkt gehört genau zu einer Klasse.
Gibt es auch was anderes?
Könnte man sich auch vorstellen, dass man Klassifikation treibt, bei
denen ein Punkt zu mehreren Klassen gehört?
Können wir sich auch vorstellen?
Oder wären Sie sehr unzufrieden, wenn ich Ihnen sage, dieser Punkt
gehört zwei Klassen an?
Also wenn wir es zulassen würden, also nehmen wir noch ein Bild, wo es
gar nicht unbedingt, die schlechten Lichtverhältnisse, Kanten,
unscharf und Sie müssen jetzt Punkte zuordnen, Kanten oder auch
Körpern, dann werden Sie es nicht immer schaffen, eine eindeutige
Zuordnung vorzunehmen.
Was wir dann gerne hätten, ist, dass wir Zugehörigkeitsgrade
entwickeln.
Dass wir sagen, die Zugehörigkeit dieses Punktes zu dieser Klasse ist
meinetwegen 0,8.
Was immer das heißen mag.
Dass wir gewichten die Zugehörigkeit.
Und das führt dann, das ist übrigens heute auch angesprochen worden
drauf, da kommt man zu sogenannten Fassimengen.
Also Mengen, die so etwas ausgefranst sind an den Rändern.
So, wir werden scharfe Klassifikation betreiben wollen.
Wenn wir scharfe Klassen haben, dann ist immer noch die Frage, ist das
eine gute Entscheidung der Klasse oder nicht und wir könnten dann
folgendes machen, wir könnten eine Art Heterogenitäts- oder
Homogenitätsindex einer Klasse bilden und sagen, wie gut passen denn
diese Punkte zusammen.
Da braucht man natürlich ein Maß.
Und der übliche Maß ist, dass wir einfach den Abstand zwischen den
Punkten ermitteln.
Und wir sagen, die Homogenität ist umso größer, je kleiner der
mittlere Abstand zwischen den Punkten ist.
Und wenn wir jetzt über alle Klassen das Ganze betrachten, dann kann
es schon Klassen geben, die sehr gut sind und gibt es andere Klassen,
die sind ziemlich schlecht, haben einen geringen Heterogenitätsindex,
dann können wir noch für die Klassifikation insgesamt einen Güterindex
angeben und das ist dann zum Beispiel die Summe über alle
Heterogenitätsindexe.
So, wie gehen wir denn jetzt vor?
Jetzt kann man sich überlegen, wir haben so eine Punktmenge, wie
könnte man denn die angehen?
Es gibt im Wesentlichen zwei Verfahren, die einen beginnen mit den
Punkten und enden bei den Klassen und die anderen beginnen mit einer
Klasse und enden bei den Punkten.
Die, die mit den Punkten beginnen, die schauen sich einfach mal die
Punkte an und sagen, welche Punkte könnten wir denn zunächst mal
zusammenlegen.
Und die, die mit der Klasse beginnen, packen alles in eine Klasse und
sagen, dann kann ich diese Klasse unterteilen, sodass ich die
Homogenität insgesamt verbessern kann.
Hier sehen wir also das erste Verfahren, das nennt sich Agglomerativ,
beginnt also beispielsweise hier zu sagen, die beiden Punkte scheinen
einen sehr geringen Abstand zu haben, die packen wir mal zusammen.
Und hier gibt es auch zwei Punkte, die haben einen recht geringen
Abstand, die packen wir mal zusammen.
So, bei dem Punkt, dieser Punkt hier, der liegt also außen, da gibt es
auch keinen anderen mehr.
Im nächsten Schritt können wir diesen Punkt mit diesem hier
zusammenpacken, also machen wir jetzt diesen Schritt hier.
Und hier schaue ich mir mal an, welcher Punkt ist weiter entfernt oder
näher dran, da könnte ich mal sagen, dieser hier.
Also füge ich das zusammen, dann bleibt noch ein Punkt übrig, das ist
dann dieser hier.
Und schließlich habe ich jetzt zwei Klassen bereits gebildet und die
füge ich auch wieder zusammen.
Wir sehen, was wir so haben, ist, dass wir im Wesentlichen immer
Klassen zusammenfügen zu größeren Klassen, wobei die Klassen entartet
sein können und einen einzelnen Punkt enthalten.
Hier ist es gerade umgekehrt, hier habe ich erstmal eine große Klasse.
Ich unterziehe jetzt erstmal diese dicke Linie hier durch und
unterteile das Ganze mal in zwei.
Links habe ich, soweit ich sehen kann, schon mal eine ordentliche
Homogenität, rechts ist das nicht der Fall.
Dann kann ich im nächsten Schritt feststellen, naja, hier kann ich
nochmal sinnvoll unterteilen, dann erhöhe ich wiederum die
Homogenität, weil ich jetzt für jede oder die Güte, weil ich für jede
einzelne Klasse eine bessere Homogenität erreiche und das Ganze setze
ich beispielsweise dann auf der rechten Seite auch noch fort.
So, und wir berechnen also jedes Mal mit jedem Schritt den Güteindex
und wählen immer eine, bei der der Güteindex nur noch gering
verbessert wird, weil wir hoffentlich vorher schon einen hohen
Güteindex erreicht haben.
So, nur haben wir leider das Problem erstmal verschoben.
Wir haben nämlich uns jetzt ein neues Problem, jetzt haben wir gesagt,
wir wollen den Güteindex hochtreiben und der basiert auf dem mittleren
Abstand.
Der mittlere Abstand ermittelt sich aus den Abständen der Punkte
untereinander, also müssen wir jetzt eine Abstandsberechnung
vornehmen.
Die Abstandsberechnung, die wird jetzt so durchgeführt, dass wir
beispielsweise feststellen müssen, wer ist denn der nächste Nachbar.
Und der nächste Nachbar von einem gegebenen Punkt aus ist derjenige,
der am nächsten bei einem gegebenen Punkt liegt.
Also ich habe einen Punkt P und frage, wer ist mein nächster Nachbar,
dann schaue ich mir die Umgebung an und suche den Punkt, der am
wenigsten weit entfernt ist.
Oder wenn ich zwei Punkte erstmal zusammenfassen will, wie wir das am
Anfang getan haben, dann suchen wir nach nächsten Paaren.
Das heißt, wir suchen immer die zwei Punkte einer Punktmenge, die den
geringsten Abstand haben.
Wir sehen zum Beispiel hier, dass wenn das unser Ausgangspunkt ist,
dann ist das der nächste Nachbar.
Der hat den geringsten Abstand, alle anderen sind weit entfernt.
Und wenn wir aber beginnen wollen, dann ist das nächste Paar dieses
hier.
Wir sehen schon, dass wir, wenn wir so ein agglomeratives Verfahren
haben, dass wir dann gerne erstmal mit dem nächsten Nachbarn arbeiten.
Wenn wir so ein divisives Verfahren haben, dann suchen wir häufig
erstmal von gegebenen Punkten aus nach dem nächsten Nachbarn.
So, wie kommen wir zum nächsten Paaren?
Einfaches Verfahren.
Wir berechnen einfach alle Distanzen aus und das Paar mit der
kleinsten Distanz, das hat es gemacht, das ist der nächste Nachbar.
Und wir können sofort überlegen, ich muss alle Kombinationen
überprüfen und das ist nichts anderes als quadratisches Verhalten.
So, das nächste ist sofort, sobald ich ja sehe, n² ist meine nächste
Überlegung, komme ich mit Teil und Herrsche, was mich immer auf einen
logarithmischen Aufwand bringt, komme ich da weiter.
Ob ich jetzt sortiere oder nicht, das wollen wir dahingestellt sein
lassen.
Also jedenfalls könnte ich versuchen, mit logarithmischem Aufwand zu
arbeiten.
Also wir müssen uns das Verfahren ansehen, wie ich zum nächsten
Nachbar, zum nächsten Paaren komme, wenn ich zunächst mal mit Teil und
Herrsche arbeite.
Die Zeit ist aber schon so weit fortgeschritten, dass ich das am
nächsten Montag noch vorführe.