uni/algodat/report123/p1-fragestellungen.md

P1 Fragestellungen

findMax

Für die Problematik konnen wir nicht die Annahme treffen, das Array sei sortiert, daher bietet sich nur eine naive Suche an. Bei dieser naiven Suche wird das Array iteriert und laufend ein neues Maximum gesetzt, sofern ein neues gefunden wird. Erwartungsgemäß, durch die strikte $\Theta(n)$ Implementierung, wird auch genau n mal abgefragt. Das setzen eines neuen Maximums ist eine $O(1)$ Operation und wird auch nicht immer durchgeführt.

Bis auf einige schwer zu begründende Artefakte bei kleinen Eingabegrößen, lässt sich in Fig.1 ein klarer Trend erkennen, welcher den Erwartungen entspricht.

closestPair

Bei dieser Problemstellung werden alle möglichen Paare, die sich bilden lassen aus einer Liste mit n Punkten, geprüft. Somit lässt sich bei einer naiven Implementierung eine Komplexität von $\Theta(n^2)$ erwarten. Ein dichtes Paar zeichnet sich durch seine geringe euklidische Distanz aus, also wird für jedes Paar eine entsprechende euklidische Distanz gebildet. Diese Operation ist, obwohl Wurzelziehen eine teure Operation sein soll, immer noch $O(1)$.

Eine naive Implementierung besteht aus zwei verschachtelten Schleifen, welche über die Indizes des Eingabearrays iterieren und jeweils Paare bilden, wobei gleiche Indizes übersprungen werden. Aber es fällt schnell auf, dass schon gebildete Paare öfter gebildet werden. Bei einer Punktemenge ${ 1, 2, 3 }$ beispielsweise, werden $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$ gebildet. Dies kann leicht verhindert werden, da die äußere Schleife alle Elemente der Reihenfolge abarbeitet. Ist nämlich z.B. Punkt 1 bereits abgearbeitet, wird dieser in Zukunft einfach nicht mehr berücksichtigt. Dadurch ergeben sich nur noch die Paare $(1, 2), (1, 3), (2, 3)$. Die Anzahl an Vergleichen lässt sich nun generalisieren auf $n^2 * (n-1)^2 * (n-2)^2 * ... * 1$.

Wie erwartet lässt sich eine nahezu quadratische Laufzeit observieren. Dies ist beispielsweise in Fig.2 dadurch zu erkennen, dass eine Verdoppelung der Eingabegröße (z.B. 7.5k -> 15k) auf eine nahezu Vervierfachung der Laufzeit (~300 -> ~1050) hinausführt.

hasSubsetSum

Für dieses Problem müssen Teilmengen und deren Summe gebildet werden, um zu Evaluieren, ob eine gesuchte Summe durch eine Teilmenge gebildet werden kann. Da bei einer naiven Implementierung alle Teilmengen gebildet werden müssen, kann das Problem auf das finden der Potenzmenge abgestimmt werden. Somit lässt sich eine worst-case Performance von $O(2^n)$ erwarten.

Zu aller erst wurde eine naive rekursive Implementierung versucht, welche mit allen abzutastenden Elementen eine Summe bildet und den abzutastenden Bereich des Eingabearrays reduziert, um mit subsequenten rekursiven Aufrufen das Problem zu lösen. Diese Implementierung hatte leider einen zu massiven Overhead und hat somit unrealistisch lange Wartezeiten aufbeschworen.

Als nächstes wurde eine naive iterative Implementierung versucht, in welcher alle Permutationen der Potenzmenge abgespeichert und laufend aufsummiert werden. Diese Implementierung litt (in Retrospekt offensichtlicherweise) unter massivem Speicheraufwand ($\Theta(2^n)$).

Als nächstes ist eine elegante dynamische Implementierung versucht worden. Das bilden einer Potenzmenge lässt sich leicht erklären, als Problem in welchem einmal ein Element dazu genommen wird, und einmal dasselbe Element nicht dazu genommen wird. Eine naheliegende Lösung ist, zwei rekursive Aufrufe zu verwenden, wobei eine Zwischensumme und ein eingeschränkter Bereich, nämlich exklusive dem ersten Element der zu betrachtenden Elemente, weitergegeben wird. Eine Zwischensumme bildet sich dann mit Berücksichtigung des ersten Elementes, und die andere ohne, wie aus der verbalen Beschreibung für das Potenzmengenproblem.

Eine interessante und sehr naheliegende Optimierung ist es, alle rekursiven Zweige, in denen Zwischensumme die gesuchte Summe überschreitet, zu terminieren. Die Komplexität bleibt zwar exponentiell, mit einem $O(2^n)$, aber verhält sich wesentlich performanter, als die erste, komplett naive Implementierung. Dieser Trend lässt sich auch in Fig.3 deutlich erkennen.

In Fig.3 werden Zahlenmengen gegeben, für welche sich die gesuchte Summe nicht zusammenstellen lässt. Das trägt zur Konsequenz, das nicht im Verlauf eine passende Zwischensumme gefunden werden kann um den Algorithmus zu terminieren, sondern jeder Zweig ausgeschöpft werden muss, bis sich sagen lässt, es gibt keine passende Zwischensumme. Im worst-case ist die gesuchte Summer größer als alle aufstellbaren Summen, sodass alle Teilmengen probiert werden müssen und die erwartete worst-case Komplexität für $O(2^n)$ eintritt. Interessant ist wie sich Problemmengen verhalten, in denen die gesuchte Summe schon gefunden werden kann. Wie bereits angedeutet, existiert eine passende Zwischensumme, ist es umgangssprachlich nur eine Frage der Zeit diese zu finden. Es besteht immer noch ein worst-case, in dem die gesuchte Summe der letzten Zwischensumme, die gebildet wird, entspricht. Die Auswirkung daher ist, dass wenn passende Zwischensummen existieren, der Algorithmus nur etwas früher terminieren wird als im Fall von Fig.3. Die eigentliche Laufzeitkomplexität bleibt bei einem $O(2^n)$. Die Gegenüberstellung aus Fig.4 unterstützt diese Observierung, wo bei gleicher Problemgröße entweder eine idente Laufzeit, oder eine geringere Laufzeit wenn passende Zwischensummen existieren entsteht.

abschließende Worte

Die Vorlesung scheint nicht gelogen zu haben, Komplexitätsanalyse erweist sich bei diesen Problemstellungen als äußerst intuitiv und beschreibt elegant die Laufzeiten, welche sich in der Praxis observieren lassen.