michael.eichberg@dhbw.de, Raum 149B
1.2
Die Folien sind teilweise inspiriert von oder basierend auf Lehrmaterial von Prof. Dr. Ritterbusch, Prof. Dr. Baumgart oder Prof. Dr. Albers.
Analyse des Aufwands zur Berechnung von Ergebnissen ist wichtig ...
im Design,
in der Auswahl
und der Verwendung von Algorithmen.
Für relevante Algorithmen und Eingangsdaten können Vorhersagen getroffen werden:
Um Zusammenhänge sind zwischen Eingangsdaten und Aufwand zu finden.
Aufwand kann Rechenzeit, Speicherbedarf oder auch Komponentennutzung sein.
Der Rechenaufwand ist häufig zentral und wird hier betrachtet, die Verfahren sind aber auch für weitere Ressourcen anwendbar.
Die Vorhersagen erfolgen über asymptotische Schätzungen
mit Hilfe der Infinitesimalrechnung,
durch Kategorisierung im Sinne des Wachstumsverhaltens,
damit ist oft keine exakte Vorhersage möglich.
Unterschiedliche Systeme sind unterschiedlich schnell, relativ dazu wird es interessant.
Im Folgenden geht es um:
die Beschreibung des asymptotischen Wachstumsverhaltens
die Analyse von iterativen Algorithmen
die Analyse von rekursiv teilenden Algorithmen
Die Infinitesimalrechnung bezeichnet die Differenzial- und Integralrechnung. Es wird mit unendlich kleinen Größen gerechnet.
Der folgende Abschnitt behandelt die dynamische Programmierung, um ein Problem effizient zu lösen. Er zeigt gleichzeitig wie die Wahl des Algorithmus und der Implementierung die Laufzeit dramatisch beeinflussen kann.
Berechnung der Fibonacci-Zahlen
Implementieren Sie eine rekursive Funktion, die die \(n\)-te Fibonacci-Zahl berechnet!
Bis zu welchem \(n\) können Sie die Fibonacci-Zahlen in vernünftiger Zeit berechnen (d. h. < 10 Sekunden) ?
Lösen eines Problems durch Lösen mehrerer kleinerer Teilprobleme, aus denen sich die Lösung für das Ausgangsproblem zusammensetzt.
Mehrfachberechnungen von Lösungen
Speichern einmal berechneter Lösungen (in einer Tabelle) für spätere Zugriffe.
Definition
\(F(0) = 0\)
\(F(1) = 1\).
\(F(n) = F(n-1) + F(n-2)\)
\(F(n)\) als stehende Formel:
Aufrufbaum
Rekursive Beschreibung des Problems P
Bestimmung einer Menge \(T\), die alle Teilprobleme von \(P\) enthält, auf die bei der Lösung von \(P\) – auch in tieferen Rekursionsstufen – zurückgegriffen wird.
Bestimmung einer Reihenfolge \(T_0 , \ldots, T_k\) der Probleme in \(T\), so dass bei der Lösung von \(T_i\) nur auf Probleme \(T_j\) mit \(j < i\) zurückgegriffen wird.
Sukzessive Berechnung und Speicherung von Lösungen für \(T_0 ,...,T_k\).
Rekursive Definition der Fibonacci-Zahlen nach gegebener Gleichung.
\(T = { f(0),..., f(n-1)}\)
\(T_i = f(i), i = 0,...,n – 1\)
Berechnung von \(fib(i)\) benötigt von den früheren Problemen nur die zwei letzten Teillösungen \(fib(i – 1)\) und \(fib(i – 2)\) für \(i \geq 2\).
Lösung mit linearer Laufzeit und konstantem Speicherbedarf
1procedure fib (n : integer) : integer2f_n_m2 := 0; f_n_m1 :=13for k := 2 to n do4f_n := f_n_m1 + f_n_m25f_n_m2 := f_n_m16f_n_m1 := f_n7if n ≤ 1 then return n8else return f_n
Lösung mit Memoisierung (Memoization)
Berechne jeden Wert genau einmal, speichere ihn in einem Array F[0...n]:
1procedure fib (n : integer) : integer2F[0] := 0; F[1] := 1;3for i := 2 to n do4F[i] := ∞ // Initialisierung5return lookupfib(n)67procedure lookupfib (n : integer) : integer8if F[n] = ∞ then9F[n] := lookupfib(n-1) + lookupfib(n-2)10return F[n]
Fibonacci-Zahl effizient berechnen
Implementieren Sie den Pseudocode der ersten Lösung zur Berechnung der Fibonacci-Zahlen.
Bis zur welcher Fibonacci-Zahl können Sie die Berechnung nun durchführen?
Im Allgemeinen werden Laufzeiten oder Aufwände in Abhängigkeit von einer Eingangsgröße als Folge beschrieben:
Folgenglieder
Beispiel: (\(a_n\)) : \(a_1 = 2, a_2 = 3, a_3 = 7, a_4 = 11, ...\)
Rekursive Definition
Beispiel: (\(c_n\)) : \(c_1 = 1, c_2 = 1, c_{n+2} = c_n + c_{n+1}\) für \(n \in \mathbb(N)\)
Explizite Definition
Beispiel: (\(b_n\)) : \(b_n = n^2\) für \(n \in~\mathbb{N}\)
Eine rekursive Definition ist eine Definition, die sich auf sich selbst bezieht. Häufiger schwieriger zu analysieren. Die explizite Definition ist eine direkte Zuweisung und meist die beste Wahl.
Die explizite Definition von Laufzeiten ist zur Auswertung vorzuziehen.
Die rekursive Definition tritt oft bei rekursiven Verfahren auf, und sollte dann in eine explizite Definition umgerechnet werden.
Berechnung der Anzahl der Schritte zum Lösen der Türme von Hanoi.
Türme von Hanoi mit 3 Scheiben.
Die Türme von Hanoi (ChatGPT)
Die Türme von Hanoi sind ein klassisches mathematisches Puzzle. Es besteht aus drei Stäben und einer bestimmten Anzahl von unterschiedlich großen Scheiben, die anfangs alle in absteigender Reihenfolge auf einem Stab gestapelt sind – der größte unten und der kleinste oben.
Das Ziel des Spiels ist es, alle Scheiben auf einen anderen Stab zu bewegen, wobei folgende Regeln gelten:
Es darf immer nur eine Scheibe auf einmal bewegt werden.
Eine größere Scheibe darf nie auf einer kleineren liegen.
Alle Scheiben müssen auf den dritten Stab bewegt werden, indem sie über den mittleren Stab verschoben werden.
Für die Lösung sind für jeden Ring \(n\) die folgenden \(a_n\) Schritte erforderlich:
Alle \(n-1\) kleineren Ringe über Ring \(n\) müssen mit \(a_{n-1}\) Schritten auf den Hilfsstab.
Der Ring \(n\) kommt auf den Zielstab mit einem Schritt.
Alle \(n-1\) Ringe vom Hilfsstab müssen mit \(a_{n-1}\) Schritten auf den Zielstab.
Bei nur einem Ring ist \(a_1 = 1\) und sonst \(a_n = a_{n-1} + 1+ a_{n-1} = 2a_{n-1} + 1\).
Also: \(a_1 = 1\), \(a_2 = 2·1+ 1= 3\), \(a_3 = 2·3+ 1= 7\), \(a_4 = 2·7+ 1= 15\), ...
Damit liegt nahe, dass der Aufwand (\(1,3,7,15,...\)) dem Zusammenhang \(a_n = 2^n-1\) entspricht.
Beweis durch vollständige Induktion
Induktionsanfang \(n = 1\): \(a_1 = 2^n -1 = 2^1-1 = 1\)
Induktionsvoraussetzung: \(a_{n-1} = 2^{n-1}-1\) und \(a_{n} = 2a_{n-1} + 1\)
Induktionsschritt (\(n-1 \rightarrow n\)):
\(a_{n} = 2·(2^{n-1}-1)+1\)
\(\quad\, = 2^{n}-2+1\)
\(\quad\, = 2^{n}-1\)
Damit ist die Vermutung bestätigt.
Betrachten wir die Folge (\(a_n\)) mit \(a_n = {(-1)^n \over n} + 2\), \(n \in \mathbb{N}\):
Entwicklung der Folge:
Die Folge konvergiert zu 2, da für ein gegebenes \(\varepsilon > 0\) ein \(N\) existiert so dass \(|a_n-a|<\varepsilon \):
wenn \(n > {1 \over \varepsilon }\) ist.
D. h. \(a_n \rightarrow 2\) oder \(lim_{n\rightarrow \infty } a_n = 2\)
Die Folge \(a_n = {n^2 + 1 \over n^3}\) konvergiert gegen 0, da:
Die Folge konvergiert gegen 0, da der Zähler gegen 0 strebt (\(\lim_{{n \to \infty}} {( 1/n)} = 0\) und \(\lim_{{n \to \infty}} {( 1/n^3)} = 0\)) und der Nenner konstant ist.
Die allgemeine Vorgehensweise ist es, die größte Potenz im Zähler und Nenner zu finden und dann diese auszuklammern. Im zweiten Schritt kürzen wir dann. In diesem Fall ist es \(n^3\).
D. h. das Ziel ist es den Ausdruck so umzuformen, dass der Grenzwert direkt abgelesen werden kann. Dies ist inbesondere dann der Fall, wenn \(n\) nur noch im Nenner oder Zähler steht.
Wir möchten \(f(x) = \frac{\ln(x)}{x^{2/3}}\) für \(x \to \infty\) untersuchen.
Das vereinfacht sich zu:
Die Regel von L'Hôpital ermöglicht es Grenzwerte von Ausdrücken des Typs \(\frac{0}{0}\) oder \(\frac{\infty}{\infty}\) zu berechnen. In diesem Fall nehmen wir die Ableitungen des Zählers und des Nenners.
Die Regel besagt:
Falls \(\lim_{x \to a} \frac{f(x)}{g(x)}\) den unbestimmten Ausdruck \(\frac{0}{0}\) oder \(\frac{\infty}{\infty}\) ergibt, dann gilt:
sofern der Grenzwert auf der rechten Seite existiert oder unendlich ist.
Erste Folge - zum Aufwärmen
Zeigen Sie, dass die Folge \(a_n = {n^2 \over n^2 + 1}\) konvergiert und bestimmen Sie den Grenzwert.
Zweite Folge
Bestimmen Sie den Grenzwert der Folge, wenn er denn existiert: \(b_n = {1 - n + n^2 \over n(n+1)}\).
Folge mit Wurzel
Bestimmen Sie den Grenzwert \(\lim_{n\rightarrow \infty } \sqrt{n^2 + n} - n\).
Hier könnte die dritte binomische Formel (\((a-b)(a + b) = a^2 -b^2\)) hilfreich sein.
Um eine Potenz aus einer Wurzel zu bekommen, hilft ggf. das Wurzelgesetz \(\sqrt{a} \cdot \sqrt{b} = \sqrt{a \cdot b}\).
Beispiel: \(\sqrt{x^4 + x^2} = \sqrt{x^4 (1 + 1/x ^2)} = \sqrt{x^4} \cdot \sqrt{(1 + 1/x ^2)} = x^2 \cdot \sqrt{(1 + 1/x ^2)}\).
Folge mit mehreren Termen
Berechnen Sie den Grenzwert Folge \(b_n = {n^2 -1 \over n + 3 } - {n^2 + 1 \over n - 1}\) falls er existiert.
Zwei Wurzeln
Bestimmen Sie den Grenzwert \(\lim_{n\rightarrow \infty } \sqrt{n^2 + 1} - \sqrt{n^2 + 4n}\).
Es gilt der folgende Zusammenhang für die Mengen \(\mathcal{O}(g)\)[1], \(\Omega (g)\) und \(\Theta (g)\):
Wenn eine Funktion \(f\) in der Menge \(O(g)\) (d. h. \(f \in O(g)\)) ist, dann wächst die Funktion \(g\) mindestens genauso schnell wie die Funktion \(f\). Wächst \(g(n)\) asymptotisch schneller, dann ist \(f(n)/g(n)\) für \(n \to \infty\) in diesem Falle 0; wachsen beide gleich schnell, dann ist es eine Konstante \(c\).
Die Verwendung der O-Notation zur Beschreibung der Komplexität von Algorithmen wurde von Donald E. Knuth eingeführt.
Insbesondere für die obere Abschätzung \(O(g)\) gibt es eine alternative Schreibweise:
D. h. ab einem Wert \(n_0\) liegt die Funktion \(f\) unter dem \(c_0\)-fachen der Funktion \(g\).
Beispiel: \(f(n) = 4n + 7 \in O(n)\)
\(4n + 7 \leq c_0· n \Leftrightarrow n· (4- c_0) \leq -7\)
Wähle (exemplarisch): \(c_0 = 5\) und \(n_0 = 7\) sowie \(g(n) = n\).
Häufige Vergleichsfunktionen sind zum Beispiel Monome wie \(n^k\) für \(k \in \mathbb{N}_0\).
Asymptotische Laufzeitabschätzungen können zu Missverständnissen führen:
Asymptotische Abschätzungen werden nur für steigende Problemgrößen genauer, für kleine Problemstellungen liegt oft eine ganz andere Situation vor.
Asymptotisch nach oben abschätzende Aussagen mit \(O(g)\)-Notation können die tatsächliche Laufzeit beliebig hoch überschätzen, auch wenn möglichst scharfe Abschätzungen erwünscht sein sollten, gibt es diese teilweise nicht in beliebiger Genauigkeit, oder sind nicht praktikabel.
Nur Abschätzungen von gleicher Ordnung \(\Theta (g)\) können direkt verglichen werden, oder wenn zusätzlich zu \(O(g)\) auch \(\Omega (h)\) Abschätzungen vorliegen.
Gegenseitige asymptotische Abschätzung I
Bestimmen Sie welche Funktionen sich gegenseitig asymptotisch abschätzen:
\(f_1(x) = \sqrt[3]{x},\; f_2(x) = e^{-1+ln\, x} , f_3(x) = {x \over ln(x) + 1}\).
D. h. berechnen Sie:
Denken Sie daran, dass die erste Ableitung von \(f(x) = ln(x)\) die Funktion \(f'(x)= {1 \over x}\) ist.
Gegenseitige asymptotische Abschätzung II
Vergleichen Sie: \(f_1(x) = e^{2ln(x)+1}\) und \(f_2(x) = {x^3+1 \over x}\).
Gegenseitige asymptotische Abschätzung III
Vergleichen Sie: \(f_1(x) = 2^{1+2x}\) und \(f_2(x) = 4^x + 2^x\).
Algorithmen sind Verfahren, die gegebene Ausprägungen von Problemen in endlich vielen Schritten lösen können.
Dabei muss jeder Schritt
ausführbar und
reproduzierbar sein.
Es gibt aber oft viele Methoden die Probleme zu lösen:
Daher ist es wichtig, Eigenschaften von Algorithmen zu analysieren!
Insbesondere z.B.
Zeitaufwand und
Speicherbedarf
in Abhängigkeit von der Problemgröße.
Problemumfang (Problemgröße) n
Konkrete Beispiele für Problemgrößen:
Konkreter Wert von \(n\): \(f (n)\)
Stellenanzahl des Eingabewertes (der Eingabewerte) → \(f (z_1z_2 . . . z_n) (z_i \in { 0, . . . , 9 })\)
Anzahl der Eingabewerte: \(f(x_1, x_2, . . . , x_n)\)
Tatsächlicher Zeitaufwand hängt vom ausführenden Rechnersystem ab.
Beeindruckende Entwicklung der Rechentechnik.
Größere Probleme können gelöst werden.
Langsamere Algorithmen bleiben langsamer auch auf schnellen Systemen.
Eine möglichst sinnvolle Annahme eines Rechnersystems gesucht:
Von-Neumann System
mit einer Recheneinheit
genaue Geschwindigkeit nicht relevant.
Die Komplexität eines Problems zu bestimmen ist oft ausgesprochen schwierig, da man hierfür den besten Algorithmus kennen muss. Es stellt sich dann weiterhin die Frage wie man beweist, dass der beste Algorithmus vorliegt.
Bei vielen Komplexitätsanalysen steht die Zeitkomplexität im Vordergrund.
Die Zeitkomplexität misst nicht konkrete Ausführungszeiten (z. B. 1456 ms), da die Ausführungszeit von sehr vielen Randbedingungen abhängig ist, die direkt nichts mit dem Algorithmus zu tun haben, z. B.:
Prozessortyp und Taktfrequenz
Größe des Hauptspeichers
Zugriffszeiten der Peripheriegeräte
Betriebssystem → wird z. B. ein virtueller Speicher unterstützt
Compiler- oder Interpreter-Version
Systemlast zum Zeitpunkt der Ausführung
Klasse |
Eigenschaft |
|---|---|
\(O(1)\) |
Die Rechenzeit ist unabhängig von der Problemgröße |
\(O(\log n)\) |
Die Rechenzeit wächst logarithmisch mit der Problemgröße |
\(O(n)\) |
Die Rechenzeit wächst linear mit der Problemgröße |
\(O(n \cdot \log n)\) |
Die Rechenzeit wächst linear logarithmisch mit der Problemgröße |
\(O(n^2)\) |
Die Rechenzeit wächst quadratisch mit der Problemgröße |
\(O(n^3)\) |
Die Rechenzeit wächst kubisch mit der Problemgröße |
\(O(2^n)\) |
Die Rechenzeit wächst exponentiell (hier zur Basis 2) mit der Problemgröße |
\(O(n!)\) |
Die Rechenzeit wächst entsprechend der Fakultätsfunktion mit der Problemgröße |
\(O(1)\)
Liegt typischerweise dann vor, wenn das Programm nur einmal linear durchlaufen wird.
Es liegt keine Abhängigkeit von der Problemgröße vor, d. h. beispielsweise keine Schleifen in Abhängigkeit von \(n\).
Beispiel:
Die Position eines Datensatzes auf einem Datenträger kann mit konstanten Aufwand berechnet werden.
\(O(\log n)\)
Beispiel:
Binäre Suche; d. h. in einem sortierten Array mit \(n\) Zahlen eine Zahl suchen.
\(O(n)\)
Beispiel:
Invertieren eines Bildes oder sequentielle Suche in einem unsortierten Array.
\(O(n \cdot \log n)\)
Beispiel:
Bessere Sortierverfahren wie z. B. Quicksort.
\(O(n^2)\)
Häufig bei zwei ineinander geschachtelten Schleifen.
Beispiel:
Einfache Sortierverfahren wie z. B. Bubble-Sort oder die Matrixaddition.
\(O(n^3)\)
Häufig bei drei ineinander geschachtelten Schleifen.
Beispiel:
Die (naive) Matrixmultiplikation:
\(M(m, t)\) ist eine Matrix mit m Zeilen und t Spalten.
\(C(m, t) = A(m, n)· B(n, t)\) mit
\(c_{i,j} = \sum_{k = 1}^n a_{i,k}· b_{k,j}\qquad i = 1, . . . , m \qquad j = 1, . . . , t\)
\(O(2^n)\)
Typischerweise der Fall, wenn für eine Menge mit \(n\) Elementen alle Teilmengen berechnet und verarbeitet werden müssen.
Beispiel:
Rucksackproblem (Knapsack Problem)
Ein Rucksack besitzt eine maximale Tragfähigkeit und \(n\) Gegenstände unterschiedlichen Gewichts und Wertes liegen vor, deren Gesamtgewicht über der Tragfähigkeit des Rucksacks liegt. Ziel ist es jetzt eine Teilmenge von Gegenständen zu finden, so dass der Rucksack optimal in Hinblick auf den Gesamtwert gefüllt wird.
\(O(n!)\)
Typischerweise der Fall, wenn für eine Menge von \(n\) Elementen alle Permutationen dieser Elemente zu berechnen und zu verarbeiten sind.
Beispiel:
Problem des Handlungsreisenden (Traveling Salesman Problem (TSP))
Gegeben sind \(n\) Städte, die alle durch Straßen direkt miteinander verbunden sind und für jede Direktverbindung ist deren Länge bekannt.
Gesucht ist die kürzeste Rundreise, bei der jede Stadt genau einmal besucht wird.
Sei die Problemgröße \(n = 128\):
Klasse |
Laufzeit |
|---|---|
\(O(\log_2\, n)\) |
\(1,75\,ns\) |
\(O(n)\) |
\(32\,ns\) |
\(O(n \cdot \log_2\, n)\) |
\(224\,ns\) |
\(O(n^2)\) |
\(4,096\,µs\) |
\(O(n^3)\) |
\(524,288\,µs\) |
\(O(2^n)\) |
\(2,70 \cdot 10^{21}\,a\) |
\(O(3^n)\) |
\(9,35 \cdot 10^{43}\,a\) |
\(O(n!)\) |
\(3,06 \cdot 10^{198}\,a\) |
Dies zeigt, dass Algorithmen mit einer Komplexität von \(O(n^3)\) oder höher für große bzw. nicht-triviale Problemgrößen nicht praktikabel sind.
Operation |
Anzahl der Rechenschritte |
|---|---|
elementare Arithmetik: + ,- , * , /, <, <=, etc. |
1 |
elementare logische Operationen: &&, ||, !, etc. |
1 |
Ein- und Ausgabe |
1 |
Wertzuweisung |
1 |
|
1 |
Kontrollstrukturen |
Anzahl der Rechenschritte |
|---|---|
Methodenaufruf |
1 + Komplexität der Methode |
Fallunterscheidung |
Komplexität des logischen Ausdrucks + Maximum der Komplexität der Rechenschritte der Zweige |
Schleife |
Annahme: \(m\) Durchläufe: Komplexität der Initialisierung + \(m\) mal die Komplexität des Schleifenkörpers + Komplexität aller Schleifenfortschaltungen |
def ist_primzahl(n):
prim = True # Wertzuweisung: 1
i = 2 # Wertzuweisung: 1
if n < 2: # Vergleich: 1
prim = False # Wertzuweisung: 1
else: # Durchläufe: n-2 * (
while prim and i < n: # Vergleiche, und: 3
if n % i == 0: # modulo, Vergleich: 2
prim = False # Wertzuweisung: 1
i += 1 # Inkrement: 1
# )
# letzte Bedingungsprüfung 3
return prim # Befehl: 1Im schlechtesten Fall, d. h. \(i \geq 2\) und es gilt \(i==n\) nach der while-Schleife, werden \(7 + (n- 2)· 7 = 7· n- 7\) Rechenschritte benötigt. Die Anzahl der Rechenschritte hängt somit linear vom Eingabewert \(n\) ab.
Beachte, dass in keinem Falle alle Instruktionen ausgeführt werden.
Insertion-Sort
Vergleichbar zum Ziehen von Karten: die neue Karte wird an der richtigen Stelle eingeschoben.
def insertion_sort(A):
for i in range(1, len(A)):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = keyAlgorithmus: Insertion-Sort(A, n) [Pseudocode] |
Zeit |
Anzahl |
|
|---|---|---|---|
1: |
for i = 2...n do |
c1 |
\(n\) |
2: |
key = A[i] |
c2 |
\(n-1\) |
3: |
j = i - 1 |
c3 |
\(n-1\) |
4: |
while j > 0 and A[j] > key do |
c4 |
\(\sum_{i=2}^n t_i\) |
5: |
A[j + 1] = A[j] |
c5 |
\(\sum_{i=2}^n (t_i-1)\) |
6: |
j = j - 1 |
c6 |
\(\sum_{i=2}^n (t_i-1)\) |
7: |
A[j + 1] = key |
c7 |
\(n-1\) |
\(c_x\) sind die konstanten Kosten für die jeweilige Operation. Wir abstrahieren diese als \(c = max(c_1,...c_7)\).
\(t_i\) ist die Anzahl der Schritte, die für das Einsortieren der \(i\)-ten Karte benötigt wird. Dies hängt davon ab, wie die Liste vorliegt.
Abschätzung der Laufzeit \(T(n)\) nach oben:
Jetzt können drei Fälle unterschieden werden:
die Liste ist bereits sortiert, d. h. \(t_i = 1\)
die Liste ist umgekehrt sortiert, d. h. \(t_i = i\)
die Liste ist zufällig sortiert, d. h. \(t_i = {i+1 \over 2}\)
Im schlimmsten Fall, d. h. die Liste ist umgekehrt sortiert, ergibt sich:
und nach Anwendung der Summenformel für die natürlichen Zahlen:
Im besten Fall, d. h. die Liste ist bereits sortiert, ergibt sich:
Hinweise
in Zeile 1 ist die Anzahl \(n\), da \(n-1\) mal hochgezählt wird und dann noch ein Test erfolgt, der fehlschlägt und die Schleife beendet.
In Hinblick auf den Zeitaufwand gilt:
Der Insertion-Sort-Algorithmus hat eine quadratische Komplexität, d. h. die Laufzeit wächst quadratisch mit der Problemgröße. Er hat die Komplexität \(O(n^2)\).
Bestimmung der asymptotischen Laufzeit eines Algorithmus
Die Funktion \(p(n)\) hat die Laufzeit \(T_p(n) = c_p \cdot n^2\) und \(q(n)\) die Laufzeit \(T_q(n) = c_q \cdot \log(n)\).
1Algorithmus COMPUTE(n)2p(n);3for j = 1...n do4for k = 1...j do5q(n);6end7end
Bestimmen Sie die asymptotische Laufzeit des Algorithmus in Abhängigkeit von \(n\) durch zeilenweise Analyse.
„Naive“ Power Funktion
Bestimmen Sie die algorithmische asymptotische Komplexität des folgenden Algorithmus durch Analyse jeder einzelnen Zeile. Jede Zeile kann für sich mit konstantem Zeitaufwand abgeschätzt werden. Die Eingabe ist eine nicht-negative Ganzzahl \(n\) mit \(k\) Bits. Bestimmen Sie die Laufzeitkomplexität für den schlimmstmöglichen Fall in Abhängigkeit von \(k\)!
(Beispiel: die Zahl \(n = 7_d\) benötigt drei Bits \(n= 111_b\), die Zahl \(4_d\) benötigt zwar auch drei Bits \(100_b\) aber dennoch weniger Rechenschritte.).
1Algorithmus Power(x,n)2r = 13for i = 1...n do4r = r * x5return r
Effizientere Power Funktion
Bestimmen Sie die algo. asymptotische Komplexität des folgenden Algorithmus durch Analyse jeder einzelnen Zeile. Jede Zeile kann für sich mit konstantem Zeitaufwand abgeschätzt werden. Bestimmen Sie die Laufzeitkomplexität mit Indikator \(t_i\) für gesetzte Bits in \(n\) für den schlimmstmöglichen Fall - in Abhängigkeit von \(k\) für eine nicht-negative Ganzzahl \(n\) mit \(k\) Bits.
(D. h. \(t_i = 1\), wenn der i-te Bit von \(n\) gesetzt ist, sonst ist \(t_i = 0\); sei \(n = 5_d = 101_b\) dann ist \(t_1 = 1, t_2 = 0, t_3 = 1\)).
1Algorithmus BinPower(x,n)2r = 13while n > 0 do4if n mod 2 == 1 then5r = r * x6n = (n-1)/27else8n = n/29x = x * x10return r
1gW = [ (1, 1), (3, 4), (5, 8), (2, 3) ] # [(Gewicht, Wert)...]23def bestWertRekursiv(n):4best = 05for i in range(len(gW)):6(gewt,wert) = gW[i]7if n >= gewt:8test = wert + bestWertRekursiv(n - gewt)9if test > best:10best = test11return best1213print(bestWertRekursiv(5)) # max. Traglast ist hier zu Beginn n = 5
Für Komplexität nehmen wir jetzt die häufigste Aktion her; hier die Additionen.
Bei der Rekursion ergibt sich (\(m\) = Anzahl der verschiedenen Objekte):
Im schlimmsten Fall sind alle \(g_i = 1\) (d. h. die Gewichte).
Pro Aufruf \(m\) weitere Aufrufe.
(D. h. auf erster Ebene haben wir \(m\) Additionen, auf der zweiten Ebene \(m^2\) Additionen, usw.)
Erklärungen
Grobe Idee: Wir gehen in der Methode bestWertRekursiv über alle Elemente und probieren aus ob wir diese einmal in den Rucksack packen können, d. h. die (verbleibende) Traglast ausreicht. Falls ja, dann führen wir einen rekursiven Aufruf durch bei dem wir die Traglast entsprechende reduziert haben.
Details: Für jedes Element entscheiden wir, ob es noch in den Rucksack passt (Zeile 7). Falls ja, dann wird der Wert des Elements addiert und die Traglast um das Gewicht des Elements reduziert (Zeile 8: n - gewt). Anschließend wird rekursiv der bester Wert für den kleineren Rucksacks berechnet.
Grundsätzliche Idee der iterativen Lösung
Gehe über alle Objekte. Berechne in jedem Schleifendurchlauf i bei Hinzunahme von Teil i das jeweils das beste Ergebnis für alle Kapazitäten j bis inklusive n.
Beispiel
Verfügbare Objekte (\((Gewicht,Wert)\)): \(A = \{(1,1),(3,4),(5,8),(2,3)\}\). Sei die maximale Traglast \(n = 7\):
i\j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|---|---|---|---|---|---|---|---|---|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
0 |
1 |
2 |
4 |
5 |
6 |
8 |
9 |
2 |
0 |
1 |
2 |
4 |
5 |
8 |
9 |
10 |
3 |
0 |
1 |
3 |
4 |
6 |
8 |
9 |
11 |
Implementierung
1gW = [ (1, 1), (3, 4), (5, 8), (2, 3) ] # (Gewicht, Wert)23def bestWertIterativ(n):4best = [0] * (n + 1) # best[i] = bester Wert für Traglast i5for i in range(len(gW)):6(gewt, wert) = gW[i]7for j in range(gewt, n + 1):8test = best[j - gewt] + wert9if test > best[j]:10best[j] = test1112return best[n]1314print(bestWertIterativ(5)) # max. Traglast ist hier zu Beginn n = 5
Komplexitätsanalyse
Bei den Iterationen ergibt sich:
Zwei Schleifen über \(m\) und \(n\):
Erklärungen
Grobe Idee: Wir gehen in der Methode bestWertIterativ über alle Objekte (Zeile 5). In der inneren Schleife (Zeile 7) iterieren wir über die Traglasten, die das Objekt – ggf. auch mehrfach – aufnehmen könnten (range(gewt, n + 1)). Für jede dieser Traglasten prüfen wir ob es vorteilhaft ist das Objekt in den Rucksack zu packen. Falls ja, dann wird der aktuell beste Wert für die Traglast aktualisiert.
D. h. wir legen zum Beispiel ein Objekt mit dem Gewicht 2 bei einer verbleibenden Traglast von 5 ggf. (implizit) dadurch mehrfach in den Rucksack, dass wir bereits den besten Wert für die kleineren Traglasten kennen.
Die iterative Variante ist wegen der vermiedenen Berechnung gleicher Werte – aufgrund der Verwendung von dynamischer Programmierung – praktisch immer schneller. Dies könnte bei Rekursion ggf. mit Caching erreicht werden.
Wieso ist das Rucksackproblem dann aber als NP-vollständig klassifiziert?
Die Analyse erfolgte nicht über die Wortlänge (als Eingabegröße); d. h. \(n\) (Kapazität bzw. Tragkraft) entspricht nicht der Wortlänge. Ein Binärwort \(n\) mit \(k\) Zeichen (Bits) hat bis zu \(2^k-1\) Werte.
Die Wortlänge eines Problems bezeichnet hier die Anzahl der Bits, die benötigt werden, um die Eingabe eines Problems darzustellen. Sie ist ein Maß dafür, wie groß oder komplex die Darstellung der Eingabedaten ist.
Die iterative Variante mit dynamischer Programmierung hat eine Laufzeit von \(O(m\cdot n)\) wobei \(n\) hier die Kapazität in Gewichtseinheiten ist, nicht die Wortlänge. Wenn \(n\) exponentiell groß ist, wird der Algorithmus ineffizient, da die Eingabegröße \(\lceil log_2 N\rceil \) viel kleiner ist als \(N\) selbst. (D. h. wenn die Kapazität 10 ist, dann brauchen wir 4 Bits, um die Kapazität darzustellen, wenn die Kapazität jedoch 1000 (100 mal größer) ist, dann brauchen wir 10 Bits (d. h. nur 2,5 mal so viele Bits.)
Standardverfahren zur Analyse rekursiver Algorithmen:
Anwendung der Verfahren zur Analyse iterativer Algorithmen um die Rekurrenzgleichung zu bestimmen.
Eine Anzahl von Werten ausrechnen und auf sinnvollen Zusammenhang schließen.
Beweis des Zusammenhangs mit vollständiger Induktion.
Dieses Verfahren haben wir bei den Türmen von Hanoi angewandt.
Rekurrenzgleichungen sind Gleichungen, die eine Folge \(a_n\) durch ihre vorherigen Elemente definieren. Sie beschreiben die Entwicklung eines Wertes \(a_n\) in Abhängigkeit von vorhergehenden Werten.
Teilende Verfahren, bzw. Divide-and-Conquer-Algorithmen, sind typischerweise sehr effizient.
Wird beispielsweise das Problem immer halbiert, ist also \(a_{2n} = a_n + 1\) und ist \(a_1 = 1\), dann würde für die Folgenglieder gelten \(a_1 = 1, a_2 = 2, a_4 = 3, a_8 = 4, a_{16} = 5, ...\).
Verallgemeinert: \(a_n = \log_2(n) +1\).
Herleitung:
\(a_1 = \log_2(1) + 1 = 0 + 1\)
\(a_{2n} = a_n + 1 = \log_2(n) + 1 + 1 = \log_2(n) + \log_2(2) + 1 = \log_2(2n) + 1\)
Ein Beispiel ist die binäre Suche nach einem Namen im Telefonbuch oder nach einer zu erratenden Zahl.
Bei der Herleitung wurde (wieder) vollständige Induktion angewandt und die Logarithmusgesetze genutzt: \(\log(a) + \log(b) = \log(a \cdot b)\) sowie \(\log_bb= 1\).
In vielen Fällen geben rekursiv teilende Algorithmen Grund zur Hoffnung, dass die Laufzeit einen relevanten logarithmischen Anteil hat.
Häufig können die Rekurrenz-Gleichungen rekursiv teilender Algorithmen in folgende Form gebracht werden:
Sei:
\(a\): die Anzahl der rekursiven Aufrufe,
\({n \over b}\): die Größe jedes rekursiven Unterproblems wobei \(b\) die Anzahl der Teile ist in die das Problem geteilt wird,
\(f(n)\): der Aufwand während der Ausführung (z. B. der Aufwand für das Teilen der Eingabedaten und das Zusammenführen der Teillösungen).
In diesem Fall können drei Fälle unterschieden identifiziert werden:
Ist der Aufwand \(f(n)\) vernachlässigbar gegenüber dem Aufwand der weiteren Aufrufe, so ist ein rein durch die Rekursion bestimmtes Verhalten zu erwarten.
Entspricht der Aufwand \(f (n)\) genau dem Aufwand der weiteren Aufrufe, so vervielfältigt sich der Aufwand gegenüber dem 1. Fall, bleibt aber in der gleichen Größenordnung.
Ist der Aufwand \(f (n)\) größer als der Aufwand der verbleibenden Aufrufe, so wird der Aufwand asymptotisch von \(f (n)\) dominiert.
Beispiel für den 1. Fall
Bei \(a = 1\) und \(b= 2\) — wie bei der binären Suche — ist somit logarithmisches Verhalten zu erwarten. Wird hingegen ein \(b= 2\) halbiertes Feld \(a = 4\) viermal aufgerufen, so ist ein quadratisches Verhalten zu erwarten.
Das Master-Theorem ist ein Werkzeug zur Analyse der Zeitkomplexität von rekursiven Algorithmen, die mit Hilfe von Rekurrenzgleichungen der Form \(T(n) = a \cdot T\left({n \over b}\right) + f(n)\) beschrieben werden können.
Anwendungsgebiet sind insbesondere Teile-und-Herrsche Algorithmen.
Das Master-Theorem hat drei Fälle, die auf dem Vergleich zwischen \(f(n)\) und \(n^{\log_b a}\) basieren und die asymptotische Komplexität von \(T(n)\) bestimmen. Wobei \(n^{\log_b a}\) die Laufzeit für die Rekursion selbst beschreibt:
Seien \(a >0\) und \(b >1\) Konstanten und \(f : \mathbb{N} \rightarrow \mathbb{N}\):
Wenn \(f(n) \in O(n^{\log_b a - \epsilon})\) für ein \(\epsilon > 0\) gilt – d. h. wenn \(f(n)\) langsamer wächst als \(n^{\log_b a}\) – dann dominiert die Rekursion, und es gilt: \(T(n) \in \Theta(n^{\log_b a})\).
Wenn \(f(n) \in \Theta(n^{\log_b a} \cdot (\log n)^k)\) für ein \(k \geq 0\) gilt – d. h. wenn \(f(n)\) und \(n^{\log_b a} \cdot (\log n)^k\) gleich schnell wachsen – dann tragen beide Teile zur Gesamtkomplexität bei, und es gilt: \(T(n) \in \Theta(n^{\log_b a} \cdot (\log n)^{k+1})\).
Wenn \(f(n) \in \Omega(n^{\log_b a + \epsilon})\) für ein \(\epsilon > 0\) gilt und weiterhin gilt \(af(n/b) \leq c f(n)\) für eine Konstante \(c < 1\) und ein hinreichend großes \(n\) – d. h. wenn also \(f(n)\) schneller wächst als \(n^{\log_b a}\) – dann dominiert \(f(n)\) die Komplexität, und es gilt: \(T(n) \in \Theta(f(n))\).
Viele Sortieralgorithmen sind zum Beispiel Teile-und-Herrsche Algorithmen.
Im Mastertheorem erfolgt der Vergleich ggf. mit \(n^{(\log_ba)-\epsilon}\) und nicht mit \(n^{\log_b (a-\epsilon)}\).
\(T (n) = 2T (n/2) + n \log_2 n\)
\(a = 2\), \(b = 2\) und \(n^{\log_2 2} = n\)
Es liegt Fall 2 vor, da \(f(n) = n \cdot (\log_2n)^{k=1} \in \Theta(n^{\log_b a} \cdot (\log n))\).
Die Laufzeit beträgt somit \(T(n) = \Theta(n \cdot (\log_2 n)^2)\).
Der Wechsel der Basis des Logarithmus ist möglich, da sich die Basis nur um einen konstanten Faktor unterscheidet:
\(\log_\textcolor{blue}{a} \textcolor{red}{x} = \frac{ 1 }{ \log_b \textcolor{blue}{a}} \cdot \log_b \textcolor{red}{x}\)
\(T (n) = 9T (n/3) + 2n\)
\(a = 9\), \(b = 3\) und \(n^{\log_3 9} = n^2\)
Es liegt Fall 1 vor, da \(f(n) = 2n \in O(n^{\log_3 9 - \epsilon})\).
Die Laufzeit beträgt somit \(T(n) = \Theta(n^2)\).
\(T (n) = 2T (n/3) + n\)
\(a = 2\), \(b = 3\) und \(n^{\log_3 2}\), \(log_32 \approx 0,63 < 1\)
Es liegt Fall 3 vor, da \(f(n) = n \in \Omega(n^{\log_3 2 + \epsilon})\) und
\(af(n/b) = 2n/3 \leq c \cdot n\) für \(1 > c \geq 2/3\).
Die Laufzeit beträgt somit \(T(n) = \Theta(n)\).
Das Master-Theorem hilft also, die asymptotische Komplexität von Algorithmen schnell zu bestimmen, ohne dass eine detaillierte Analyse der Rekurrenz erforderlich ist.
f(n) ist konstant
Gegeben sei: \(T (n) = 2T (n/4) + 1\)
Bestimmen Sie die Laufzeit des Algorithmus mit Hilfe des Master-Theorems.
f(n) ist die Quadratwurzel
Gegeben sei: \(T (n) = 3T (n/9) + \sqrt{n}\)
Bestimmen Sie die Laufzeit des Algorithmus mit Hilfe des Master-Theorems.
a=1 und f(n) sind konstant
Gegeben sei: \(T (n) = T (n/2) + 1\)
Bestimmen Sie die Laufzeit des Algorithmus mit Hilfe des Master-Theorems.
Anwendung des Master-Theorems auf Mergesort
Der Mergesort-Algorithmus ist ein rekursiver Algorithmus, der ein Array in zwei Hälften teilt, die Hälften sortiert – wenn sie nicht trivial sind – und dann die sortierten Hälften zusammenführt. Das Zusammenführen der Hälften hat einen Aufwand von \(n\) und das Teilen des Arrays hat einen konstanten Aufwand.
Bestimmen Sie die Rekurrenzgleichung für den Mergesort-Algorithmus.
Bestimmen Sie die Laufzeit des Mergesort-Algorithmus mit Hilfe des Master-Theorems.
Neben der dynamischen Programmierung ist das Backtrack-Prinzip ein weiteres grundlegendes Verfahren zur Lösung von Problemen.
Backtracking ist ein Verfahren, das in vielen Algorithmen zur Anwendung kommt. Insbesondere, wenn kein effizienterer Algorithmus bekannt ist, als alle möglichen Lösungen auszuprobieren.
Backtracking ist eine systematische Methode, um alle möglichen Lösungen eines Problems zu finden. Es ist eine Art von rekursivem Durchsuchen, bei dem Teillösungen zu Gesamtlösungen erweitert werden.
Backtracking erlaubt ggf. Heuristiken, um die Suche zu beschleunigen.
Weder die Komplexitätsklasse noch die Korrektheit ändert sich dadurch.
Viele NP-harte Probleme werden mit Backtracking gelöst.[2]
Backtracking führt eine erschöpfende Suche durch, um eine Lösung zu finden. Kann aber auch direkt genutzt werden, um ggf. alle Lösungen zu finden.
Backtracking ist in Prolog inherent vorhanden, da Prolog auf dem Prinzip des Backtrackings basiert, weswegen Prolog für die Lösung solcher Probleme gut geeignet ist.
1// i: Spalte; j: Zeile2procedure findeStellung(i : integer)3j := 04repeat5{ wähle nächste Zeile j }6if Dame an Position i / j bedroht7keine bisher platzierte Dame then8{ platziere Dame in Feld i / j }9if i = 4 then10{ Lösung gefunden }11{ Ausgabe der Lösung }12else13findeStellung(i + 1) // rek. Aufruf14{ entferne Dame aus Spalte i und Zeile j } // zurücksetzen des Zustands15until { alle Zeilen j getestet }
Wesentliche Elemente:
Die Lösung ist endlich.
Die Lösung wird iterativ aufgebaut. Es ist jederzeit möglich zu testen, ob die bisherige Lösung noch gültig ist (Zeile 6, 7).
Ist eine Lösung nicht mehr möglich, wird die Teillösung auch nicht weiter verfolgt.
Wurde eine Lösung gefunden, wird sie ausgegeben (Zeile 10, 11).
Die Methode wird rekursiv aufgerufen, um die Lösung zu vervollständigen (Zeile 13).
Voraussetzungen für Backtracking
Die Lösung ist als Vektor a[1], a[2], ... endlicher Länge darstellbar.
Jedes Element a[i] hat eine endliche Anzahl von möglichen Werten A[i].
D. h. die Menge der möglichen Werte pro a[i] kann unterschiedlich sein.
Es gibt einen effizienten Test, ob eine Teillösung a[1], a[2], ..., a[k] zu einer gültigen Lösung führen kann.
Verfahren
Wähle eine Teillösung a[1].
Ist eine Teillösung basierend auf a[1], a[2], ..., a[k-1] noch keine Gesamtlösung, dann erweitere sie mit dem nächsten nicht ausgeschlossenen Wert a[k] aus A[k] zur neuen Teillösung a[1], a[2], ..., a[k].
Falls noch nicht alle Elemente von A[K], die zu keiner inkonsistenten Lösungen führen, ausgeschöpft sind, dann gehe zurück (backtrack) und wähle a[k] neu. Ggf. gehe zu a[k-1] usw. zurück.
Es wird hier nicht gefordert, dass alle Element den gleichen Wertebereich haben. Es ist auch möglich, dass die Werte unterschiedlich sind.
Auswerten logischer Ausdrücke mittels Backtracking
Bestimmen Sie für folgenden Ausdruck c - mittels Backtracking - Wahrheitswerte für die Variablen, damit der Ausdruck als Ganzes wahr wird:
c = (A ∨ ¬B) ∧ (¬A ∨ B) ∧ (¬A ∨ ¬C) ∧ (C ∨ D) ∧ (¬C ∨ ¬D)
Füllen Sie dazu die folgende Tabelle aus, um alle Lösungen zu finden. In der letzten Spalte geben Sie an, ob die Zeile eine Teillösung darstellt, eine Inkonsistenz gefunden wurde, oder eine Gesamtlösung identifiziert wurde. Die Evaluation wie vieler vollständiger Belegungen wurde eingespart, wenn die Lösung gefunden wurde?
A |
B |
C |
D |
nicht inkonsistent (T), keine Lösung (K), vollständige Lösung (L) |
|
|---|---|---|---|---|---|
1 |
w |
T |
|||
... |
... |
... |
... |
... |
... |
16 |
... |
... |
... |
... |
... |
Das Erfüllbarkeitsproblem
Entwickeln Sie ein Programm – in einer Programmiersprache Ihrer Wahl – dass in der Lage ist eine Formel in konjunktiver Normalform (KNF) auf Erfüllbarkeit zu prüfen. Prüfen Sie Ihr Programm anhand der vorhergehenden Aufgabe.
1from abc import abstractmethod234class Expr:56@abstractmethod7def is_solution(self, binding: dict["Var", bool]) -> bool | None:8"""True or False if this expression definitively9evaluates to the respective truth value with the10given binding or None otherwise.1112Returning a truth value does not necessarily13require all variables to be bound to a definite14value.1516For example, None will be returned, if the17truth value cannot be determined with the given18binding. E. g., if this expression represents a19variable for which the binding has no value, None20is returned.2122An expression such as "A ⋀ B" would return True23if A and B are both True in the24binding and False if at least one of them is bound25to False, and None otherwise.26"""27raise NotImplementedError282930class And(Expr):31def __init__(self, *exprs: Expr):32self.exprs = exprs3334def is_solution(self, binding):35r = True36for expr in self.exprs:37e = expr.is_solution(binding)38if e is None:39r = None40elif not e:41return False42return r4344def __str__(self):45return " ⋀ ".join(str(expr) for expr in self.exprs)4647def __repr__(self):48return "And(" + ", ".join(str(expr) for expr in self.exprs) + ")"495051class Or(Expr):52def __init__(self, *exprs: Expr):53self.exprs = exprs5455def is_solution(self, binding):56r = False57for expr in self.exprs:58e = expr.is_solution(binding)59if e is None:60r = None61elif e:62return True63return r6465def __str__(self):66return " ⋁ ".join(str(expr) for expr in self.exprs)6768def __repr__(self):69return "Or(" + ", ".join(repr(expr) for expr in self.exprs) + ")"707172class Not(Expr):73def __init__(self, expr: Expr):74self.expr = expr7576def is_solution(self, binding):77e = self.expr.is_solution(binding)78if e is None:79return None80else:81return not e8283def __str__(self):84return f"¬{self.expr}"8586def __repr__(self):87return "Not(" + repr(self.expr) + ")"888990class Var(Expr):91def __init__(self, name: str):92self.name = name9394def is_solution(self, binding):95"""True or False if bound.96None if unbound (default).97"""98if self not in binding:99return None100else:101return binding[self]102103def __str__(self):104return self.name105106def __repr__(self):107return 'Var("' + self.name + '")'108109110A = Var("a")111B = Var("b")112C = Var("c")113D = Var("d")114vars = [A, B, C, D]115""" The variables are now indexed to enable iterating over116them in the solve function. """117118expr = And(119Or(A, B),120Or(Not(A), B),121Or(Not(A), Not(C)),122Or(C, D),123Or(Not(C), Not(D)),124)125print("Finding solutions for: " + expr.__str__())126127solution: dict[Var, bool] = {}128""" Stores the current solution by mapping the name of a129variable to its current truth value (True or False)."""130131132def solve(expr, vars):133var = vars[0]
Gruppenzuteilung
Finden Sie eine sehr gute Aufteilung von Personen (Studierenden) auf eine feste Anzahl an Gruppen, basierend auf den Präferenzen der Personen. Nutzen Sie dazu Backtracking.
Im Template ist eine initiale Aufgabenstellung hinterlegt, die es zu lösen gilt: Verteilung von 16 Studierenden auf 4 Gruppen inkl. Bewertungsmatrix (jeder Studierende hat jeden anderen mit Werten von 1 bis 10 bewertet).