Aufgabe 1)

Gegeben sei der folgende Algorithmus, welcher das Maximum in einer Liste von ganzen Zahlen findet:

'def finde_maximum(liste):    max_wert = liste[0]    for wert in liste:        if wert > max_wert:            max_wert = wert    return max_wert'

Basierend auf dieser Definition und nach den Eigenschaften von Algorithmen, beantworte die folgenden Fragen:

a)

a) Eigenschaften des Algorithmus: Identifiziere und erkläre anhand des gegebenen Algorithmus alle fünf definierten Eigenschaften von Algorithmen (Determinismus, Endlichkeit, Eingaben, Ausgaben, Effektivität). Gehe darauf ein, wie der gegebene Algorithmus jede dieser Eigenschaften erfüllt.

Lösung:

• Determinismus: Ein Algorithmus ist deterministisch, wenn bei gleichen Eingabedaten stets die gleichen Ausgaben erzeugt werden. Der gegebene Algorithmus ist deterministisch, da er bei jeder Ausführung mit der gleichen Liste von ganzen Zahlen immer das gleiche Maximum zurückgibt.
• Endlichkeit: Ein Algorithmus muss in einer endlichen Anzahl von Schritten abgeschlossen sein. Der gegebene Algorithmus erfüllt diese Eigenschaft, da die Schleife über die Liste nach einer endlichen Anzahl von Schritten (anhand der Listenlänge) abgeschlossen wird.
• Eingaben: Algorithmen benötigen Eingaben, um zu funktionieren. Der gegebene Algorithmus akzeptiert eine Liste von ganzen Zahlen als Eingabe.
• Ausgaben: Algorithmen müssen eine Ausgabe erzeugen. Der gegebene Algorithmus gibt den größten Wert in der Liste, also das Maximum, zurück.
• Effektivität: Jeder Schritt eines Algorithmus muss effektiv und eindeutig definierbar sein. Im gegebenen Algorithmus sind alle Schritte klar definiert: Initialisierung des Maximalelements, Iteration über die Liste, Vergleich und Aktualisierung des Maximums sowie Rückgabe des Endergebnisses.

b)

b) Korrektheit und Laufzeit: Beweise die Korrektheit des Algorithmus und berechne die Laufzeitkomplexität in Abhängigkeit von der Anzahl der Elemente in der Eingabeliste n. Begründe Deine Ausführungen mathematisch und detailliert. Stelle sicher, dass du sowohl die Schleifeninvariante als auch eine asymptotische Laufzeitanalyse (Big-O-Notation) verwendest.

Lösung:

• Korrektheit des Algorithmus: Um die Korrektheit des Algorithmus zu beweisen, verwenden wir die Schleifeninvariante. Eine Schleifeninvariante ist eine Aussage, die vor und nach jeder Iteration der Schleife wahr ist.
  • Schleifeninvariante: Vor jeder Iteration der Schleife gilt: max_wert ist der größte Wert aller bisher geprüften Elemente der Liste.
  • Initialisierung: Vor Beginn der Schleife wird max_wert auf das erste Element der Liste gesetzt (liste[0]). Zu diesem Zeitpunkt ist max_wert korrekt, da es der größte Wert der bisher geprüften (in diesem Fall nur ein Element) ist.
  • Erhaltung: Während jeder Iteration der Schleife wird der aktuelle Wert (wert) mit max_wert verglichen. Wenn wert größer ist als max_wert, wird max_wert aktualisiert. Dadurch bleibt die Invariante erhalten (d.h., max_wert bleibt immer das größte bisher geprüfte Element).
  • Terminierung: Wenn die Schleife endet, wurde jedes Element der Liste einmal überprüft. Laut der Schleifeninvariante ist max_wert am Ende das größte Element der gesamten Liste.
• Laufzeitkomplexität: Um die Laufzeitkomplexität zu analysieren, betrachten wir die Anzahl der Operationen, die der Algorithmus in Abhängigkeit von der Länge der Eingabeliste n benötigt.
  • Initialisierung: Die Zuweisung von max_wert = liste[0] ist eine O(1)-Operation.
  • Schleife: Die Schleife läuft über alle n Elemente der Liste. In jeder Iteration wird eine Vergleichsoperation (if wert > max_wert) und möglicherweise eine Zuweisungsoperation (max_wert = wert) durchgeführt. Beide Operationen sind O(1). Die Schleife wird n Mal ausgeführt, daher ist die Zeitkomplexität der Schleife O(n).
  • Rückgabewert: Die Rückgabeoperation (return max_wert) ist ebenfalls eine O(1)-Operation.
  Durch die Betrachtung aller Operationen ergibt sich die Gesamtzeitkomplexität des Algorithmus als O(n). Da hauptsächlich die Schleife dominiert, lautet die asymptotische Laufzeit des Algorithmus O(n).

Aufgabe 2)

Betrachten die folgenden grundlegenden algorithmischen Strategien zur Lösung komplexer Probleme: Divide and Conquer, Greedy, und Dynamic Programming. Eine genaue Kenntnis dieser Strategien ermöglicht es, verschiedene Problemtypen effizient zu lösen. Beantworten die folgenden Teilaufgaben basierend auf diesen Konzepten.

a)

(a) Entwickeln einen Divide-and-Conquer-Algorithmus für das Finden des Maximums in einem Array von n Elementen. Beschreiben den Algorithmus und analysieren seine Zeitkomplexität.

Lösung:

Divide-and-Conquer-Algorithmus zum Finden des Maximums in einem Array

Ein Divide-and-Conquer-Algorithmus kann verwendet werden, um das Maximum in einem Array von n Elementen effizient zu finden. Der grundlegende Ansatz dieser Methode besteht darin, das Problem in kleinere Teilprobleme zu zerlegen, diese rekursiv zu lösen und anschließend die Ergebnisse zu kombinieren.

Algorithmusbeschreibung

1. Teilen: Teile das Array in zwei Hälften auf.

2. Erobern: Bestimme rekursiv das Maximum in jeder Hälfte.

3. Kombinieren: Das Maximum des gesamten Arrays ist das Maximum der beiden Teilmaxima.

Hier ist der Pseudocode des Algorithmus:

function findMaximum(arr, left, right) {  if left == right {    // Basisfall: ein einziges Element    return arr[left];  }  // Mitte des Arrays berechnen  mid = left + (right - left) / 2;  // Rekursiv das Maximum in der linken und rechten Hälfte suchen  maxLeft = findMaximum(arr, left, mid);  maxRight = findMaximum(arr, mid + 1, right);  // Das größere der beiden Teilmaxima zurückgeben  return max(maxLeft, maxRight);}

Analyse der Zeitkomplexität

Die Zeitkomplexität des Divide-and-Conquer-Algorithmus kann wie folgt analysiert werden:

• Im Teilen-Schritt wird das Array in zwei Hälften aufgeteilt, was eine konstante Zeit O(1) benötigt.
• Der Erobern-Schritt beinhaltet das rekursive Finden des Maximums in beiden Hälften, wobei jedes Teilarray eine Größe von n/2 hat.
• Der Kombinieren-Schritt vergleicht die beiden Teilmaxima, was ebenfalls in konstanter Zeit O(1) erfolgt.

Die Rekurrenzrelation für diesen Algorithmus ist:

T(n) = 2T(n/2) + O(1)

Diese Relation kann mit dem Master-Theorem gelöst werden:

a = 2, b = 2, f(n) = O(1)

Da f(n) = O(n^{log_b a}) mit log_b a = log_2 2 = 1 übereinstimmt, fällt der Fall 2 des Master-Theorems an:

T(n) = O(n^log_b a) = O(n^1) = O(n)

Daher ist die Zeitkomplexität des Divide-and-Conquer-Algorithmus zum Finden des Maximums in einem Array O(n).

b)

(b) Gib ein Beispiel eines Problemes, welches durch einen Greedy-Algorithmus gelöst werden kann. Beschreiben den Algorithmus in Pseudocode und erklären, warum die Greedy-Strategie in diesem Fall zu einer optimalen Lösung führt. Nutze dabei insbesondere die Eigenschaften von Greedy-Strategien.

Lösung:

Beispiel eines Problems, das mit einem Greedy-Algorithmus gelöst werden kann

Ein klassisches Beispiel, das mit einem Greedy-Algorithmus gelöst werden kann, ist das Aktivitätenauswahlproblem (Activity Selection Problem). In diesem Problem geht es darum, eine maximale Menge an nicht überlappenden Aktivitäten aus einer gegebenen Menge zu wählen. Jede Aktivität hat eine Startzeit und eine Endzeit.

Algorithmusbeschreibung

Der Greedy-Algorithmus für das Aktivitätenauswahlproblem wählt Aktivitäten basierend auf der frühesten Endzeit zuerst. Der Grundgedanke ist, dass die frühzeitige Auswahl der am frühesten endenden Aktivität den größten Spielraum für die verbleibenden Aktivitäten lässt.

1. Sortiere die Aktivitäten basierend auf ihrer Endzeit.

2. Wähle die erste Aktivität (diejenige mit der frühesten Endzeit).

3. Für jede folgende Aktivität in der sortierten Liste:

   • Wenn die Startzeit der aktuellen Aktivität größer oder gleich der Endzeit der zuletzt ausgewählten Aktivität ist, wähle diese Aktivität aus.

Hier ist der Pseudocode für den Greedy-Algorithmus:

function activitySelection(activities) {  // Sortiere die Aktivitäten nach ihrer Endzeit aufsteigend  sort(activities, activity.endTime);  // Initialisiere die Liste der ausgewählten Aktivitäten  selectedActivities = [];  // Wähle die erste Aktivität aus  selectedActivities.append(activities[0]);  lastActivity = activities[0];  // Gehe durch die sortierten Aktivitäten  for i from 1 to length(activities) - 1 {    if activities[i].startTime >= lastActivity.endTime {      selectedActivities.append(activities[i]);      lastActivity = activities[i];    }  }  return selectedActivities;}

Warum führt die Greedy-Strategie zu einer optimalen Lösung?

Der Greedy-Algorithmus führt in diesem Fall zu einer optimalen Lösung aufgrund der folgenden Eigenschaften:

• Greedy-Choice-Eigenschaft: Zu jedem Zeitpunkt wird die Aktivität gewählt, die die früheste Endzeit hat und kompatibel mit den bisher ausgewählten Aktivitäten ist. Diese Wahl stellt sicher, dass möglichst viele Aktivitäten ausgewählt werden können.
• Optimale Teilstruktur: Wenn eine Teilmenge von Aktivitäten optimal ist, dann ist diese Teilmenge auch Teil der optimalen Lösung des gesamten Problems. Diese Eigenschaft ermöglicht es, das Problem rekursiv durch Greedy-Entscheidungen zu lösen.

Da die Aktivitäten nach der frühesten Endzeit sortiert und ausgewählt werden, wird sichergestellt, dass jede gewählte Aktivität maximal Platz für kommende Aktivitäten lässt. Dies führt zu einer maximalen Anzahl nicht überlappender Aktivitäten, was eine optimale Lösung für das Aktivitätenauswahlproblem darstellt.

c)

(c) Implementieren einen Dynamic-Programming-Algorithmus zur Berechnung des n-ten Fibonacci-Zahl. Der Algorithmus sollte sowohl eine Memoisierungs- als auch eine Bottom-Up-Ansatz enthalten. Analysieren ihre Zeit- und Speicherkomplexität. Nutzen den folgenden Python-Code als Basis für ihre Implementierung:

def fibonacci(n):    # Ihre Implementation hier    pass

Lösung:

Berechnung der n-ten Fibonacci-Zahl mit Dynamic Programming

Um die n-te Fibonacci-Zahl zu berechnen, können wir Dynamic Programming auf zwei Arten nutzen: Memoisierung (Top-Down-Ansatz) und Bottom-Up-Ansatz. Beide Ansätze reduzieren die Zeitkomplexität im Vergleich zu einer naiven rekursiven Lösung.

Memoisierung (Top-Down-Ansatz)

Beim Top-Down-Ansatz merken wir uns die bereits berechneten Ergebnisse, um doppelte Berechnungen zu vermeiden. Hier ist der Python-Code:

def fibonacci_memo(n, memo={}):    # Basisfälle    if n <= 1:        return n    # Wenn bereits berechnet, Wert aus dem Memo zurückgeben    if n in memo:        return memo[n]    # Rekursiv berechnen und speichern    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)    return memo[n]

Analyse der Zeit- und Speicherkomplexität (Memoisierung)

• Zeitkomplexität: O(n), da jede Fibonacci-Zahl genau einmal berechnet und gespeichert wird.
• Speicherkomplexität: O(n), für die Speicherung der Ergebnisse im Memo.

Bottom-Up-Ansatz

Beim Bottom-Up-Ansatz bauen wir die Lösung von den Basisfällen auf und speichern die Zwischenwerte in einem Array. Hier ist der Python-Code:

def fibonacci_bottom_up(n):    if n <= 1:        return n    # Array zur Speicherung der Fibonacci-Zahlen    fib = [0] * (n + 1)    fib[1] = 1    for i in range(2, n + 1):        fib[i] = fib[i - 1] + fib[i - 2]    return fib[n]

Analyse der Zeit- und Speicherkomplexität (Bottom-Up)

• Zeitkomplexität: O(n), da wir in einer Schleife von 2 bis n iterieren und jede Iteration eine konstante Zeit benötigt.
• Speicherkomplexität: O(n), für das Array zur Speicherung der Zwischenwerte.

Optimierter Bottom-Up-Ansatz

Wir können den Speicherbedarf weiter reduzieren, indem wir nur die letzten beiden berechneten Fibonacci-Zahlen speichern. Hier ist der Python-Code:

def fibonacci_optimized(n):    if n <= 1:        return n    a, b = 0, 1    for _ in range(2, n + 1):        a, b = b, a + b    return b

Analyse der Zeit- und Speicherkomplexität (Optimierter Bottom-Up)

• Zeitkomplexität: O(n), aus denselben Gründen wie zuvor.
• Speicherkomplexität: O(1), da wir nur eine konstante Menge an zusätzlichem Speicher für a und b benötigen.

Die obigen Implementierungen zeigen, wie Dynamic Programming verwendet werden kann, um die n-te Fibonacci-Zahl effizient zu berechnen, und sie verdeutlichen die Unterscheidung zwischen Memoisierung (Top-Down) und dem Bottom-Up-Ansatz.

d)

(d) Ein gegebenes Problem lässt sich sowohl mit Divide-and-Conquer als auch mit Dynamic Programming lösen. Beschreiben, wie man dieses Problem mit jeder der beiden Methoden lösen würde, und vergleichen die beiden Ansätze hinsichtlich Laufzeit und Speicherverbrauch. Gib ein konkretes Beispiel zur Veranschaulichung.

Lösung:

Lösung eines Problems mit Divide-and-Conquer und Dynamic Programming

Ein klassisches Beispiel, das sowohl mit Divide-and-Conquer als auch mit Dynamic Programming gelöst werden kann, ist das Problem der Berechnung der größten gemeinsamen Teilfolge (LCS, Longest Common Subsequence) zweier Zeichenfolgen.

Divide-and-Conquer-Ansatz zur Berechnung der LCS

Der Divide-and-Conquer-Ansatz zerlegt das Problem in kleinere Teilprobleme, die rekursiv gelöst werden. Hier ist der Pseudocode:

def lcs_divide_and_conquer(X, Y, m, n):    if m == 0 or n == 0:        return 0    elif X[m-1] == Y[n-1]:        return 1 + lcs_divide_and_conquer(X, Y, m-1, n-1)    else:        return max(lcs_divide_and_conquer(X, Y, m, n-1),                   lcs_divide_and_conquer(X, Y, m-1, n))

Analyse der Zeit- und Speicherkomplexität:

• Zeitkomplexität: O(2^n), da jede rekursive Aufteilung zwei weitere Aufteilungen erzeugt.
• Speicherkomplexität: O(n), da der maximale Rekursionstiefenstack n Aufrufe tief ist.

Dynamic-Programming-Ansatz zur Berechnung der LCS

Der Dynamic-Programming-Ansatz verwendet eine Tabelle zur Speicherung der Zwischenlösungen, um redundante Berechnungen zu vermeiden. Hier ist der Pseudocode:

def lcs_dynamic_programming(X, Y):    m = len(X)    n = len(Y)    # Initialisiere eine (m+1)x(n+1) Tabelle    L = [[0] * (n + 1) for i in range(m + 1)]    for i in range(m + 1):        for j in range(n + 1):            if i == 0 or j == 0:                L[i][j] = 0            elif X[i-1] == Y[j-1]:                L[i][j] = L[i-1][j-1] + 1            else:                L[i][j] = max(L[i-1][j], L[i][j-1])    return L[m][n]

Analyse der Zeit- und Speicherkomplexität:

• Zeitkomplexität: O(m * n), da jede Zelle der Tabelle einmal berechnet wird.
• Speicherkomplexität: O(m * n) für die Speicherung der Tabelle.

Vergleich der beiden Ansätze

Im Vergleich der beiden Ansätze für die Berechnung der LCS zeigt sich:

• Der Divide-and-Conquer-Ansatz ist aufgrund seiner exponentiellen Zeitkomplexität ineffizient für große Eingaben. Er hat eine Zeitkomplexität von O(2^n) und eine Speicherkomplexität von O(n) aufgrund der maximalen Rekursionstiefe.
• Der Dynamic-Programming-Ansatz ist wesentlich effizienter mit einer Zeitkomplexität von O(m * n), da jede Teillösung nur einmal berechnet wird. Allerdings hat er eine höhere Speicherkomplexität von O(m * n), da eine Tabelle mit m*n Einträgen verwendet wird.

Konkretes Beispiel zur Veranschaulichung

Betrachten wir die beiden Zeichenfolgen X = 'ABCBDAB' und Y = 'BDCAB'. Die größte gemeinsame Teilfolge dieser Zeichenfolgen ist 'BDAB' mit einer Länge von 4.

Beim Divide-and-Conquer-Ansatz würden zahlreiche redundante Berechnungen gemacht, was zu einer langsamen Berechnung führt.

Beim Dynamic-Programming-Ansatz hingegen wird eine Tabelle verwendet, in der Teillösungen gespeichert sind, sodass jede Teillösung nur einmal berechnet wird. Dies führt zu einer wesentlich schnelleren Berechnung.

In den meisten praktischen Anwendungen ist der Dynamic-Programming-Ansatz daher die bevorzugte Methode zur Lösung solcher Probleme.

Aufgabe 3)

Effizienzanalyse eines gegebenen Algorithmus

Gegeben sei der folgende Algorithmus:

def sample_algorithm(n):     total = 0     for i in range(n):         j = 1         while j < n:             j *= 2             total += 1     return total  

Analysiere die Effizienz dieses Algorithmus hinsichtlich Laufzeit und Speicherplatz. Verwende die Konzepte der Big-O Notation, amortisierten Analyse und Rekurrenzen.

b)

Amortisierte Analyse: Diskutiere, ob die amortisierte Analyse auf den gegebenen Algorithmus anwendbar ist. Falls ja, führe eine amortisierte Analyse für die Laufzeit des Algorithmus durch. Falls nein, erkläre warum nicht.

Lösung:

Effizienzanalyse eines gegebenen Algorithmus

Gegeben sei der folgende Algorithmus:

def sample_algorithm(n):     total = 0     for i in range(n):         j = 1         while j < n:             j *= 2             total += 1     return total  

Analysiere die Effizienz dieses Algorithmus hinsichtlich Laufzeit und Speicherplatz. Verwende die Konzepte der Big-O Notation, amortisierten Analyse und Rekurrenzen.

Amortisierte Analyse:

Diskutiere, ob die amortisierte Analyse auf den gegebenen Algorithmus anwendbar ist. Falls ja, führe eine amortisierte Analyse für die Laufzeit des Algorithmus durch. Falls nein, erkläre warum nicht.

Antwort:

Bei der amortisierten Analyse betrachten wir die durchschnittlichen Kosten einer Operation über eine Reihe von Operationen hinweg. Diese Technik wird häufig für Algorithmen und Datenstrukturen verwendet, bei denen einige Operationen teurer als andere sein können, die teureren Operationen jedoch selten auftreten.

In diesem Algorithmus jedoch sind die Kosten jeder Iteration sowohl der äußeren for-Schleife als auch der inneren while-Schleife sehr genau vordefiniert und homogen:

• Die äußere Schleife läuft genau n Mal.
• Die innere Schleife läuft innerhalb jeder Iteration der äußeren Schleife logarithmisch zur Basis 2 in Bezug auf n (\(\text{log}_2(n)\)).

Dies bedeutet, dass jede Iteration innerhalb der Schleifen in ziemlich konsistenter Weise abläuft. Es gibt keine seltenen, teureren Operationen, die auf andere Iterationen „umgelegt“ werden müssten, um die Durchschnittskosten zu berechnen. Stattdessen bleibt die Laufzeit des Algorithmus in jeder Iteration gleich. Daher kann die amortisierte Analyse auf diesen Algorithmus nicht sinnvoll angewendet werden.

Zusammengefasst lässt sich sagen, dass die amortisierte Analyse nicht anwendbar ist, weil:

• Alle Operationen im Algorithmus eine konsistente, vorhersehbare Laufzeit haben.
• Es gibt keine seltenen, teureren Operationen, die eine Verschiebung der Kosten über eine Sequenz von Operationen erfordern würden.

Deshalb bleibt die einfachste und genaueste Methode zur Analyse dieses Algorithmus die direkte Berechnung der Zeitkomplexität, die, wie zuvor gezeigt, \(\text{O}(n \text{log} n)\) beträgt.

c)

Rekurrenzen: Der gegebene Algorithmus enthält eine Schleife innerhalb einer anderen Schleife. Stelle eine geeignete Rekurrenzgleichung für die äußere Schleife auf und löse sie mit dem Master-Theorem.

Lösung:

Effizienzanalyse eines gegebenen Algorithmus

Gegeben sei der folgende Algorithmus:

def sample_algorithm(n):     total = 0     for i in range(n):         j = 1         while j < n:             j *= 2             total += 1     return total  

Analysiere die Effizienz dieses Algorithmus hinsichtlich Laufzeit und Speicherplatz. Verwende die Konzepte der Big-O Notation, amortisierten Analyse und Rekurrenzen.

Rekurrenzen:

Der gegebene Algorithmus enthält eine Schleife innerhalb einer anderen Schleife. Stelle eine geeignete Rekurrenzgleichung für die äußere Schleife auf und löse sie mit dem Master-Theorem.

Antwort:

Um die Effizienz des Algorithmus anhand von Rekurrenzen zu analysieren, konzentrieren wir uns auf die Laufzeit der Schleifen.

• Äußere Schleife (for-Schleife):Die äußere Schleife läuft genau n Mal.
• Innere Schleife (while-Schleife):Die while-Schleife beginnt mit j = 1 und verdoppelt j in jedem Schritt, bis j >= n ist. Daher läuft die while-Schleife logarithmisch zur Basis 2 in Bezug auf n, also \(\text{log}_2(n)\).

Die Zeitkomplexität der inneren while-Schleife ist also \(\text{T}_{\text{inne}}(n) = \text{log}_2(n)\).

Da die äußere Schleife n Mal läuft, ergibt sich für die gesamte Laufzeit des Algorithmus:

\(T(n) = n \cdot \text{T}_{\text{inne}}(n) = n \cdot \text{log}_2(n)\)

Diese Gleichung deckt sich mit unserer vorherigen Analyse zur Zeitkomplexität.

Da dies keine klassische rekursive Gleichung der Form \(T(n) = aT(n/b) + f(n)\) ist, ist das Master-Theorem hier nicht direkt anwendbar. Wir können es jedoch für allgemeinere Zwecke diskutieren:

• Das Master-Theorem wird typischerweise bei rekursiven Algorithmen wie dem Mergesort verwendet, um die Komplexität zu lösen. Ein Beispiel für eine solche rekursive Gleichung wäre: \(T(n) = 2T(n/2) + O(n)\).
• In unserem Fall ist der Algorithmus jedoch nicht rekursiv, sondern iterativ. Daher betrachten wir direkt die geschlossene Form der Laufzeit.

Zusammenfassend ergibt sich, dass eine geeignete Rekurrenzgleichung für die äußere Schleife die einfache Multiplikation der Iterationen der beiden Schleifen ist, was zu:

\(T(n) = n \cdot \text{log}_2(n)\)

führt. Das Master-Theorem ist hier nicht anwendbar, da es sich nicht um eine rekursive Gleichung handelt.

d)

Speicherplatzkomplexität: Analysiere die Speicherplatzkomplexität des gegebenen Algorithmus. Ist sie signifikant? Begründe deine Antwort und berechne die Speicherplatzkomplexität in Big-O Notation.

Lösung:

Effizienzanalyse eines gegebenen Algorithmus

Gegeben sei der folgende Algorithmus:

def sample_algorithm(n):     total = 0     for i in range(n):         j = 1         while j < n:             j *= 2             total += 1     return total  

Analysiere die Effizienz dieses Algorithmus hinsichtlich Laufzeit und Speicherplatz. Verwende die Konzepte der Big-O Notation, amortisierten Analyse und Rekurrenzen.

Speicherplatzkomplexität:

Analysiere die Speicherplatzkomplexität des gegebenen Algorithmus. Ist sie signifikant? Begründe Deine Antwort und berechne die Speicherplatzkomplexität in Big-O Notation.

Antwort:

Die Speicherplatzkomplexität eines Algorithmus misst den zusätzlichen Speicherbedarf in Abhängigkeit von der Eingabegröße. Hier betrachten wir die verwendeten Variablen genauer:

• Variable „total“: Diese Variable wird einmal initialisiert und durchläuft mehrere Updates. Der Speicherbedarf bleibt konstant, unabhängig von der Eingabegröße n.
• Variable „i“ (in der äußeren Schleife): „i“ wird als Schleifenvariablen von 0 bis n-1 verwendet. Der Speicherbedarf für „i“ bleibt ebenfalls konstant.
• Variable „j“ (in der inneren Schleife): „j“ wird innerhalb jeder Iteration der äußeren Schleife initialisiert und verwendet. Der Speicherbedarf für „j“ bleibt konstant, da es für die Verdopplung von 1 bis n verwendet wird.

Es gibt keine Arrays oder andere dynamische Datenstrukturen, deren Größe sich mit der Eingabegröße n ändert. Alle gespeicherten Daten haben eine konstante Größe.

Zusammengefasst lässt sich sagen, dass der gegebene Algorithmus nur einen konstanten Speicherbedarf (\(\text{O}(1)\)) hat. Die Variablen haben keine Abhängigkeit von der Eingabegröße n, daher bleibt die Speicherplatzkomplexität konstant.

Die Speicherplatzkomplexität in Big-O Notation lautet daher:

\(\text{O}(1)\)

Zusammenfassung:

• Die Speicherplatzkomplexität des gegebenen Algorithmus ist nicht signifikant.
• Alle benutzten Variablen haben eine konstante Speicherplatzverwendung.
• Daher beträgt die Speicherplatzkomplexität \(\text{O}(1)\).

Aufgabe 4)

Verwaltung von Datensammlungen in der Informatik

Arrays, Listen und Bäume sind grundlegend für die effiziente Verarbeitung und Verwaltung von Daten. Dabei haben Arrays eine feste Größe und ermöglichen schnellen, indexbasierten Zugriff. Listen bieten eine dynamische Größe und flexibles Einfügen und Löschen von Elementen. Bäume, insbesondere binäre Bäume, AVL-Bäume und B-Bäume, stellen hierarchische Strukturen dar und sind besonders effizient für Suchoperationen.

a)

(a) Gegeben sei ein unsortiertes Array A mit den Elementen [42, 23, 16, 15, 8, 4]. Implementiere einen Algorithmus in Python, der alle Elemente von A in einer Linked List speichert und die Elemente in der Reihenfolge des Arrays durchläuft. Gib den Python Code an.

Lösung:

• Verwaltung von Datensammlungen in der Informatik

Arrays, Listen und Bäume sind grundlegend für die effiziente Verarbeitung und Verwaltung von Daten. Dabei haben Arrays eine feste Größe und ermöglichen schnellen, indexbasierten Zugriff. Listen bieten eine dynamische Größe und flexibles Einfügen und Löschen von Elementen. Bäume, insbesondere binäre Bäume, AVL-Bäume und B-Bäume, stellen hierarchische Strukturen dar und sind besonders effizient für Suchoperationen.

• (a) Gegeben sei ein unsortiertes Array A mit den Elementen [42, 23, 16, 15, 8, 4]. Implementiere einen Algorithmus in Python, der alle Elemente von A in einer Linked List speichert und die Elemente in der Reihenfolge des Arrays durchläuft. Gib den Python Code an.

Hier ist der Python-Code, um die Elemente eines Arrays in eine verkettete Liste zu speichern und die Elemente in der Reihenfolge des Arrays durchzulaufen:

class Node:    def __init__(self, data):        self.data = data        self.next = Noneclass LinkedList:    def __init__(self):        self.head = None    def append(self, new_data):        new_node = Node(new_data)        if self.head is None:            self.head = new_node            return        last = self.head        while last.next:            last = last.next        last.next = new_node    def print_list(self):        temp = self.head        while temp:            print(temp.data)            temp = temp.next# Gegebenes unsortiertes Array AA = [42, 23, 16, 15, 8, 4]# Erstellen einer Linked List und Hinzufügen der Array-Elementellist = LinkedList()for element in A:    llist.append(element)# Ausgeben der verketteten Listellist.print_list()

• In diesem Code definieren wir eine Node-Klasse, um die Elemente der verketteten Liste zu speichern, und eine LinkedList-Klasse, die Methoden zum Anhängen von Elementen und zum Durchlaufen (und Drucken) der Liste enthält.
• Dann erstellen wir eine Instanz der LinkedList-Klasse, fügen die Elemente des Arrays A in die verkettete Liste ein und durchlaufen schließlich die Liste, um die Elemente gemäß der Reihenfolge im Array auszugeben.

b)

(b) Erläutere, wie AVL-Bäume die Höhenbalance aufrecht erhalten. Gibt ein Beispiel für eine Sequenz von Einfügungen, die zu einer Rotation führen würde. Zeichne den Baum vor und nach der Rotation und beschreibe die Rotationsoperationen.

Lösung:

• Verwaltung von Datensammlungen in der Informatik

Arrays, Listen und Bäume sind grundlegend für die effiziente Verarbeitung und Verwaltung von Daten. Dabei haben Arrays eine feste Größe und ermöglichen schnellen, indexbasierten Zugriff. Listen bieten eine dynamische Größe und flexibles Einfügen und Löschen von Elementen. Bäume, insbesondere binäre Bäume, AVL-Bäume und B-Bäume, stellen hierarchische Strukturen dar und sind besonders effizient für Suchoperationen.

• (b) Erläutere, wie AVL-Bäume die Höhenbalance aufrecht erhalten. Gib ein Beispiel für eine Sequenz von Einfügungen, die zu einer Rotation führen würde. Zeichne den Baum vor und nach der Rotation und beschreibe die Rotationsoperationen.

Erklärung der Höhenbalance bei AVL-Bäumen

AVL-Bäume sind selbstbalancierende binäre Suchbäume. Nach jeder Einfügung oder Löschung eines Knotens überprüfen sie die Höhenbalance des Baums. Die Höhe eines Knotens im Baum ist die Anzahl der Kanten vom Knoten bis zu seinem am weitesten entfernten Blatt. Die Balance eines Knotens wird durch die Differenz der Höhen seines linken und rechten Teilbaums bestimmt. Ein AVL-Baum bleibt balanciert, wenn die Balance aller Knoten zwischen -1 und +1 bleibt. Um dies sicherzustellen, verwenden AVL-Bäume Rotationen, um den Baum nach Einfügungen oder Löschungen neu zu balancieren.

Rotationsoperationen

Es gibt vier mögliche Rotationen, die Anwendungen finden können:

• Rechtsrotation (Right Rotation, RR): Wenn die Balance eines Knotens +2 ist und die Balance seines linken Kindes >= 0.
• Linksrotation (Left Rotation, LL): Wenn die Balance eines Knotens -2 ist und die Balance seines rechten Kindes <= 0.
• Links-Rechtsrotation (Left Right Rotation, LR): Wenn die Balance eines Knotens +2 ist und die Balance seines linken Kindes < 0 (d.h. eine Linksrotation gefolgt von einer Rechtsrotation).
• Rechts-Linksrotation (Right Left Rotation, RL): Wenn die Balance eines Knotens -2 ist und die Balance seines rechten Kindes > 0 (d.h. eine Rechtsrotation gefolgt von einer Linksrotation).

Beispiel für Rotationen

Betrachten wir nun ein Beispiel für eine Sequenz von Einfügungen, die zu einer Rechts-Links-Rotation (RL) führen:

1. Füge 30 ein
2. Füge 20 ein
3. Füge 40 ein
4. Füge 35 ein

Nachdem wir 35 eingefügt haben, sieht der Baum wie folgt aus:

       30      /      20   40          /        35

Beachten wir nun, dass der Knoten 30 eine Balance von -2 hat (dies ist nicht erlaubt). Um dies zu korrigieren, machen wir eine Rechtsrotation um den Knoten 40 und danach eine Linksrotation um den Knoten 30. Der Baum sieht danach so aus:

      35     /     30    40  /20

Der Baum ist jetzt erneut balanciert, da die Balance jedes Knotens im Bereich von -1 bis +1 liegt.