Grundlagen: algorithmen und Datenstrukturen - Exam.pdf

Aufgabe 1)

Innerhalb dieser Aufgabe betrachten wir Greedy-Algorithmen, die in jedem Schritt die lokal beste Wahl treffen, um ein global optimales Ergebnis zu erreichen. Obwohl solche Algorithmen effizient sind, ist die globale Optimalität oft nicht gesichert. Anwendungen umfassen Prim's Algorithmus, Dijkstra und Kruskal, welche zur Lösung von verschiedenen Problemen verwendet werden können.

a)

(a) Erläutere das Prinzip der Greedy-Algorithmen und beschreibe eine Situation in der Praxis, in der ein Greedy-Algorithmus eine optimale Lösung findet. Begründe, warum die lokale Entscheidung in dieser Situation zu einer global optimalen Lösung führt.

Lösung:

Prinzip der Greedy-Algorithmen:

• Greedy-Algorithmen sind eine Klasse von Algorithmen, die ihr Problem durch eine Reihe von Schritten lösen, bei denen in jedem Schritt diejenige Wahl getroffen wird, die in diesem Moment am besten erscheint.
• In jedem Schritt wird die lokal beste Entscheidung getroffen ohne Rücksicht auf zukünftige Konsequenzen.
• Diese Herangehensweise kann in vielen Fällen zu einem schnellen und effizienten Lösungsweg führen.
• Jedoch garantiert sie nicht immer eine globale optimale Lösung, da die durchweg lokalen Entscheidungsfindungen nicht unbedingt zu einer global besten Lösung führen müssen.

• Eine bekannte Anwendung, bei der ein Greedy-Algorithmus eine optimale Lösung findet, ist Prim's Algorithmus zur Berechnung des minimalen Spannbaums (MST) in einem Graphen.
• Prim's Algorithmus arbeitet, indem er von einem Startknoten aus einen Baum aufbaut, bei dem in jedem Schritt die Kante mit dem geringsten Gewicht gewählt wird, die einen neuen Knoten zum Baum hinzufügt.
• Grund: Warum die lokale Entscheidung in diesem Fall zur global optimalen Lösung führt:

• Das Prinzip hinter Prim's Algorithmus ist, dass jede lokal optimale Entscheidung (Wahl der Kante mit dem geringsten Gewicht) auch eine global optimale Entscheidung ist, da:
• Durch die Wahl der Knoten (und der zugehörigen Kanten) wird entweder ein Zyklus vermieden oder die kürzeste Kante gewählt. Die Wahl einer anderen Kante mit höherem Gewicht würde den Gesamtbaum nur unnötig schwerer machen.
• Dieses Vorgehen garantiert, dass der am Ende resultierende Baum der minimale Spannbaum ist, da niemals unnötig schwere Kanten eingefügt werden.

b)

(b) Gegeben sei ein ungerichteter Graph G = (V, E) mit positiven Kantengewichten. Beschreibe detailliert, wie Prim's Algorithmus funktioniert, um den minimalen Spannbaum zu finden. Implementiere den Algorithmus in Python.

def prim(graph):    # Deine Implementierung hier    pass

Lösung:

Prim's Algorithmus zum Finden des minimalen Spannbaums:

• Prim's Algorithmus beginnt bei einem beliebigen Startknoten des Graphen.
• Er hält eine Menge von Knoten, die bereits im minimalen Spannbaum enthalten sind, und eine Menge von Kanten, die diesen Knoten verbinden.
• In jedem Schritt wird die Kante mit dem geringsten Gewicht ausgewählt, die genau einen neuen Knoten zu dem bereits konstruierten Teil des Baums hinzufügt.
• Der Prozess wiederholt sich, bis alle Knoten im Baum enthalten sind.

Hier ist eine detaillierte Implementierung von Prim's Algorithmus in Python:

import heapq  # Für die Priority Queue (Heap-Datenstruktur) verwendetdef prim(graph):  min_heap = []   start_node = list(graph.keys())[0]   for dest, weight in graph[start_node].items():    heapq.heappush(min_heap, (weight, start_node, dest))   visited = set([start_node])    mst = []  total_weight = 0  while min_heap:      weight, frm, to = heapq.heappop(min_heap)      if to not in visited:        visited.add(to)        mst.append((frm, to, weight))        total_weight += weight        for next_dest, next_weight in graph[to].items():          if next_dest not in visited:           heapq.heappush(min_heap, (next_weight, to, next_dest))   return mst, total_weight 

• graph: Ein Dictionary, das den Graphen darstellt. Die Schlüssel sind Knoten, und die Werte sind Dictionaries, die die Nachbarn und die entsprechenden Kantengewichte repräsentieren.
• min_heap: Eine Priority Queue (Heap), die verwendet wird, um die Kanten nach ihrem Gewicht zu sortieren.
• visited: Eine Menge, die alle besuchten Knoten verfolgt, um Zyklen zu vermeiden.
• mst: Eine Liste, die die Kanten des minimalen Spannbaums speichert.
• total_weight: Die Gesamtsumme der Kantengewichte im minimalen Spannbaums.

c)

(c) Analysiere die Laufzeit von Dijkstra's Algorithmus. Welchen Einfluss hat die Wahl der Datenstrukturen auf die Komplexität des Algorithmus? Vergleiche die Komplexität bei Verwendung von binären Heaps und Fibonacci Heaps.

Lösung:

Laufzeitanalyse von Dijkstra's Algorithmus:

• Dijkstra's Algorithmus wird verwendet, um die kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem Graphen mit nicht-negativen Kantengewichten zu finden.
• Die Laufzeit von Dijkstra's Algorithmus hängt stark von den verwendeten Datenstrukturen zur Verwaltung der Prioritätswarteschlange ab. Zwei gängige Datenstrukturen sind binäre Heaps und Fibonacci Heaps.

Verwendung von Binären Heaps:

• Binäre Heaps sind eine häufig verwendete Datenstruktur für die Prioritätswarteschlange in Dijkstra's Algorithmus.
• Die Operationen Einfügen und Extrahieren des minimalen Elements haben eine Laufzeit von \(\text{O}(\text{log} \, V)\), wobei \(V\) die Anzahl der Knoten im Graphen ist.
• Die Laufzeit für die Decrease-Key-Operation (Verringern des Schlüssels eines Elements) beträgt ebenfalls \(\text{O}(\text{log} \, V)\).
• Da jede Hinzufügung und Entfernung eines Knotens im binären Heap eine \(\text{log} \, V\)-Operation kostet und jede Kante im schlimmsten Fall zu einer Decrease-Key-Operation führt, ergibt sich die Gesamtlaufzeit:

• \[ \text{O}(V \, \text{log} \, V + E \, \text{log} \, V) \]
• Dies vereinfacht sich zu \(\text{O}(E \, \text{log} \, V)\), da \(E\) die Anzahl der Kanten ist und \(E \, \text{log} \, V\) immer größer oder gleich \(V \, \text{log} \, V\) ist.

Verwendung von Fibonacci Heaps:

• Fibonacci Heaps sind eine effizientere Datenstruktur für die Prioritätswarteschlange in bestimmten Aspekten.
• Die Operationen Einfügen und Extrahieren des minimalen Elements haben eine Laufzeit von \(\text{O}(\text{log} \, V)\), aber Decrease-Key ist amortisiert nur \(\text{O}(1)\).
• Die Gesamtlaufzeit ergibt sich daher zu:

• \[ \text{O}(V \, \text{log} \, V + E) \]
• Diese Verbesserung resultiert daraus, dass die Decrease-Key-Operationen nur \(\text{O}(1)\) kosten und es im Graphen \(E\) Kanten gibt.

Zusammenfassung:

• Die Wahl der Datenstruktur hat großen Einfluss auf die Laufzeit von Dijkstra's Algorithmus.
• Für Binäre Heaps beträgt die Komplexität \(\text{O}(E \, \text{log} \, V)\).
• Für Fibonacci Heaps beträgt die Komplexität \(\text{O}(V \, \text{log} \, V + E)\), was in der Praxis effizienter sein kann, insbesondere für dichte Graphen.

d)

(d) Für den Graphen G = (V, E) mit den Knoten V = {1, 2, 3, 4, 5} und den Kanten E = {(1,2,2), (1,3,3), (2,3,1), (2,4,4), (3,4,2), (4,5,3)} in der Form (u, v, w) wobei u und v die Knoten und w das Kantengewicht ist, wende Kruskal's Algorithmus an, um den minimalen Spannbaum zu finden. Berechne die Gesamtkosten des resultierenden Spannbaums und zeichne den minimalen Spannbaum grafisch.

• Sortiere die Kanten
• Setze die Kanten in den Spannbaum ein, ohne Zyklen zu erzeugen
• Gib die endgültigen Kosten und die Kanten des minimalen Spannbaums an

Lösung:

Anwendung von Kruskal's Algorithmus:

• Kruskal's Algorithmus findet den minimalen Spannbaum, indem er die Kanten des Graphen sortiert und sie der Reihe nach hinzufügt, solange sie keine Zyklen erzeugen.

Für den gegebenen Graphen:

• Knoten: \( V = \{1, 2, 3, 4, 5\} \)
• Kanten: \( E = \{(1, 2, 2), (1, 3, 3), (2, 3, 1), (2, 4, 4), (3, 4, 2), (4, 5, 3)\} \) in der Form \( (u, v, w) \).

1. Sortiere die Kanten nach ihrem Gewicht:

• (2, 3, 1)
• (1, 2, 2)
• (3, 4, 2)
• (1, 3, 3)
• (4, 5, 3)
• (2, 4, 4)

2. Füge die Kanten in den Spannbaum ein, ohne Zyklen zu erzeugen:

1. Füge Kante (2, 3, 1) hinzu. Gesamtgewicht: 1
2. Füge Kante (1, 2, 2) hinzu. Gesamtgewicht: 3
3. Füge Kante (3, 4, 2) hinzu. Gesamtgewicht: 5
4. Füge Kante (1, 3, 3) hinzu. Nicht erlaubt (würde Zyklus erzeugen)
5. Füge Kante (4, 5, 3) hinzu. Gesamtgewicht: 8
6. Füge Kante (2, 4, 4) hinzu. Nicht erlaubt (würde Zyklus erzeugen)

Endgültige Kosten und Kanten des minimalen Spannbaums:

• Gesamtkosten: 8
• Kanten des minimalen Spannbaums:
• (2, 3, 1)
• (1, 2, 2)
• (3, 4, 2)
• (4, 5, 3)

Grafische Darstellung:

Zu einer Zeichnung wie unten dargestellt:

1 -- 2 -- 3    \           \ |   3              |       4 -- 5  

Aufgabe 2)

Betrachte das klassische Rucksackproblem (Knapsack-Problem), bei dem Du eine Menge von Gegenständen mit jeweils einem Gewicht und einem Wert gegeben hast und einen Rucksack mit einer maximalen Gewichtskapazität hast. Ziel ist es, den maximal möglichen Wert zu ermitteln, den Du in den Rucksack packen kannst, ohne die Kapazität zu überschreiten.

a)

a) Formuliere das Rucksackproblem als ein dynamisches Programmierungsproblem. Definiere die rekursive Formel unter Berücksichtigung von Memoisierung. Schreibe die Pseudocode-Implementierung der rekursiven Top-Down-Lösung mit Memoisierung.

Lösung:

Das Rucksackproblem kann als dynamisches Programmierungsproblem formuliert werden. Hierbei wird das Problem mit Hilfe einer rekursiven Formel gelöst, die die Entscheidungen hinsichtlich der Aufnahme oder Nichtaufnahme eines Gegenstandes berücksichtigt. Memoisierung hilft dabei, bereits berechnete Werte zu speichern und so die Berechnungszeit zu verringern.

Rekursive Formel:

Sei dp[i][w] der maximale Wert, den wir mit den ersten i Gegenständen und einer maximalen Gewichtskapazität w erreichen können. Die rekursive Formel lautet dann:

• Wenn i = 0 oder w = 0, dann ist dp[i][w] = 0.
• Wenn das Gewicht des i-ten Gegenstandes (weight[i-1]) größer ist als w, dann ist dp[i][w] = dp[i-1][w] (der Gegenstand passt nicht in den Rucksack).
• Andernfalls ist dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w-weight[i-1]]) (wir entscheiden uns, ob wir den Gegenstand aufnehmen oder nicht).

Pseudocode-Implementierung der rekursiven Top-Down-Lösung mit Memoisierung:

def knapsack(values, weights, W):    # Anzahl der Gegenstände    n = len(values)        # Memoisierungs-Tabelle    memo = [[-1 for _ in range(W + 1)] for _ in range(n + 1)]    def dp(i, w):        # Basisfall        if i == 0 or w == 0:            return 0                # Wert wurde schon berechnet        if memo[i][w] != -1:            return memo[i][w]        # Gewicht des aktuellen Gegenstandes        weight = weights[i-1]        value = values[i-1]        # Wenn der Gegenstand nicht mit einbezogen wird        if weight > w:            memo[i][w] = dp(i-1, w)        else:            # Maximales Wert auswählen            memo[i][w] = max(dp(i-1, w), value + dp(i-1, w - weight))        return memo[i][w]    return dp(n, W)# Beispielaufruf:values = [60, 100, 120]weights = [10, 20, 30]W = 50print(knapsack(values, weights, W))  # Ausgabe: 220

In diesem Pseudocode umfasst die Rekursivfunktion dp(i, w) die oben beschriebene rekursive Formel und verwendet eine Memoisierungstabelle memo zur Speicherung der Zwischenergebnisse.

b)

b) Erstelle eine Tabelle zur Lösung des Rucksackproblems mit der Bottom-Up-Methode und erkläre den Tabellenausfüllprozess. Zeige Schritt für Schritt, wie die Tabelle für eine gegebene Menge von Gegenständen und einer bestimmten Rucksackkapazität ausgefüllt wird.

Lösung:

Die Bottom-Up-Methode zur Lösung des Rucksackproblems ist ein dynamisches Programmierungsansatz, bei dem wir eine Tabelle verwenden, um die Zwischenlösungen zu speichern und schrittweise das Endergebnis zu ermitteln.

Erklärung des Tabellenausfüllprozesses:

Wir erstellen eine Tabelle dp mit den Dimensionen (n + 1) x (W + 1), wobei n die Anzahl der Gegenstände und W die maximale Gewichtskapazität des Rucksacks ist. Das Zellenelement dp[i][w] repräsentiert den maximalen Wert, der mit den ersten i Gegenständen und einer maximalen Gewichtskapazität w erreicht werden kann.

Die Schritte zum Ausfüllen der Tabelle sind:

• Initialisiere dp[i][0] für alle i mit 0, da der maximale Wert bei einer Gewichtskapazität von 0 immer 0 ist.
• Initialisiere dp[0][w] für alle w mit 0, da der maximale Wert mit 0 Gegenständen immer 0 ist.
• Für jedes i von 1 bis n und jedes w von 1 bis W:
• Wenn das Gewicht des i-ten Gegenstandes (weights[i-1]) größer ist als w, dann ist dp[i][w] = dp[i-1][w].
• Andernfalls ist dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]]).

Hier ist ein Beispiel, um den Tabellenausfüllprozess Schritt für Schritt zu veranschaulichen:

Angenommen, wir haben drei Gegenstände mit folgenden Werten und Gewichten:

• Werte: [60, 100, 120]
• Gewichte: [10, 20, 30]
• Maximale Rucksackkapazität W: 50

Schritt-für-Schritt-Ausfüllen der Tabelle:

values = [60, 100, 120]weights = [10, 20, 30]W = 50n = len(values)dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]for i in range(1, n + 1):    for w in range(1, W + 1):        if weights[i-1] > w:            dp[i][w] = dp[i-1][w]        else:            dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])

Schauen wir uns an, wie die Tabelle iterativ gefüllt wird:

Initiale Tabelle:dp = [    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 0]]Schritt 1 - Andocken des ersten Gegenstandes:Für i=1, w=1 bis 50:dp = [    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 60, 60, ..., 60],    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 0]]Schritt 2 - Andocken des zweiten Gegenstandes:Für i=2, w=1 bis 50:dp = [    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 60, 60, ..., 60],    [0, 0, 0, 0, 0, ..., 100, 100, ..., 160, 160, ..., 160],    [0, 0, 0, 0, 0, ..., 0]]Schritt 3 - Andocken des dritten Gegenstandes:Für i=3, w=1 bis 50:dp = [    [0, 0, 0, 0, 0, ..., 0],    [0, 0, 0, 0, 0, ..., 60, 60, ..., 60],    [0, 0, 0, 0, 0, ..., 100, 100, ..., 160, 160, ..., 160],    [0, 0, 0, 0, 0, ..., 100, 120, ..., 180, 220, ..., 220, 220]]

Das Endergebnis befindet sich in dp[3][50], was 220 ist.

Dieser Prozess zeigt, wie die Tabelle systematisch gefüllt wird, um den maximalen erreichbaren Wert zu bestimmen.

c)

c) Analysiere die Zeit- und Platzkomplexität der Top-Down- und Bottom-Up-Ansätze für das Rucksackproblem. Diskutiere, warum dynamische Programmierung effizienter als naive Ansätze ist.

Lösung:

Die Analyse der Zeit- und Platzkomplexität der Top-Down- und Bottom-Up-Ansätze für das Rucksackproblem zeigt, warum dynamische Programmierung (DP) effizienter als naive Ansätze ist.

Top-Down-Ansatz (mit Memoisierung):

• Zeitkomplexität: Jeder Zustand dp[i][w] wird höchstens einmal berechnet und dann aus dem Memoisierungsarray abgerufen. Da es n \times W verschiedene Zustände gibt, beträgt die Zeitkomplexität O(nW).
• Platzkomplexität: Für die Speicherung der Memoisierungs-Tabelle memo benötigen wir (n+1) \times (W+1) Einträge. Daher ist die Platzkomplexität O(nW).

Bottom-Up-Ansatz:

• Zeitkomplexität: In einer Schleife durchlaufen wir alle n Gegenstände und für jeden dieser Gegenstände alle möglichen Gewichtskapazitäten von 0 bis W. Daher beträgt die Zeitkomplexität ebenfalls O(nW).
• Platzkomplexität: Auch beim Bottom-Up-Ansatz speichern wir die Werte in einer Tabelle mit (n+1) \times (W+1) Einträgen, sodass die Platzkomplexität O(nW) beträgt.

Vergleich mit naiven Ansätzen:

• Der naive Ansatz zur Lösung des Rucksackproblems ist eine Brute-Force-Methode, bei der alle möglichen Kombinationen der Gegenstände berücksichtigt werden, um den maximalen Wert zu finden, der in den Rucksack passt. Für n Gegenstände gibt es 2^n mögliche Kombinationen. Daher beträgt die Zeitkomplexität des naiven Ansatzes O(2^n), was für große Werte von n unpraktikabel ist.
• Dynamische Programmierung reduziert die exponentielle Zeitkomplexität des naiven Ansatzes auf eine polynomiale Zeitkomplexität von O(nW). Dies wird durch die Speicherung und Wiederverwendung von Zwischenlösungen erreicht, wodurch unnötige, doppelte Berechnungen vermieden werden.

Warum dynamische Programmierung effizienter ist:

• Durch die Tabellierung (Tabulation) oder Memoisierung vermeidet DP das mehrfache Berechnen derselben Zwischenwerte, was im naiven Ansatz vorkommt.
• DP nutzt rekursive Beziehungen zwischen den Teilproblemen, um effizienter zu Lösungen zu kommen, während naive Ansätze oftmals jede mögliche Kombination prüfen müssen, was zu erheblich mehr Berechnungen führt.
• Die polynomiale Zeitkomplexität von O(nW) ist viel handhabbarer für große Problemgrößen im Vergleich zu der exponentiellen Zeitkomplexität O(2^n) des naiven Ansatzes.
• Effizienzgewinne durch DP erlauben es, komplexere Probleme in akzeptabler Zeit zu lösen, was in vielen praxisrelevanten Anwendungen entscheidend ist.

Fazit: Die Top-Down- und Bottom-Up-Ansätze der dynamischen Programmierung sind beide signifikant effizienter als naive Ansätze in Bezug auf Zeit- und Platzkomplexität, was sie zu bevorzugten Methoden für die Lösung des Rucksackproblems macht.

d)

d) Implementiere einen Algorithmus (in Python oder einer anderen Programmiersprache Deiner Wahl) zur Lösung des Rucksackproblems mit der Bottom-Up-Methode. Verwende die definierte Formel aus Teil b) und zeige den vollständigen Code.

Lösung:

Um das Rucksackproblem mit der Bottom-Up-Methode zu lösen, können wir einen dynamischen Programmierungsansatz verwenden, wie in Teil b) besprochen. Hier ist eine Implementierung des Algorithmus in Python:

def knapsack_bottom_up(values, weights, W):    # Anzahl der Gegenstände    n = len(values)        # Erstellen der dp-Tabelle     dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]        # Füllen der dp-Tabelle    for i in range(1, n + 1):        for w in range(1, W + 1):            if weights[i-1] <= w:                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])            else:                dp[i][w] = dp[i-1][w]        # Der gesuchte Wert befindet sich in dp[n][W]    return dp[n][W]# Beispielaufruf:values = [60, 100, 120]weights = [10, 20, 30]W = 50print(knapsack_bottom_up(values, weights, W))    # Ausgabe: 220

Erklärung des Codes:

• Initialisierung: Wir initialisieren eine Tabelle dp mit der Größe (n + 1) x (W + 1), wobei alle Einträge auf 0 gesetzt sind. Hierbei steht n für die Anzahl der Gegenstände und W für die maximale Gewichtskapazität des Rucksacks.
• Füllen der Tabelle: Wir durchlaufen alle Gegenstände (Index i) und alle möglichen Gewichtsklassen (Index w). Wenn das Gewicht des aktuellen Gegenstandes kleiner oder gleich w ist, berechnen wir den maximalen Wert unter der Annahme, dass der Gegenstand entweder aufgenommen oder nicht aufgenommen wird.
• Ergebnis: Der höchstmögliche Wert, der in den Rucksack gepackt werden kann, wird in dp[n][W] gespeichert und schließlich zurückgegeben.

Dieser Algorithmus implementiert die Bottom-Up-Methode effizient und löst das klassische Rucksackproblem in polynomialer Zeit.

Aufgabe 3)

Gegeben sei ein ungerichteter Graph G mit den Knoten V und Kanten E. Der Graph wird verwendet, um eine Netzwerkstruktur zu modellieren. Der Graph ist wie folgt dargestellt: Der Knoten V besteht aus den Punkten (A, B, C, D, E) und die Kanten E bestehen aus den Verbindungen [(A, B), (A, C), (B, D), (C, D), (D, E)]. Verwenden Sie diesen Graphen, um die folgenden Aufgaben zu lösen.

a)

Erstelle eine Adjazenzmatrix für den gegebenen Graphen G. Welches sind die Eintragswerte in der Adjazenzmatrix und welche Bedeutung haben sie?

Lösung:

Um eine Adjazenzmatrix für den gegebenen ungerichteten Graphen G zu erstellen, befolge die folgenden Schritte:

• Knotenliste: Zunächst sortiere die Knoten in einer festen Reihenfolge. In diesem Fall verwenden wir die Reihenfolge (A, B, C, D, E).
• Matrix erstellen: Erstelle eine nxn Matrix (n ist die Anzahl der Knoten), wobei die Einträge 0 oder 1 sind, je nachdem ob eine Kante zwischen den Knoten existiert oder nicht.

Der Graph G hat die folgenden Kanten: [(A, B), (A, C), (B, D), (C, D), (D, E)].

Die Adjazenzmatrix sieht wie folgt aus:

Eintragswerte in der Adjazenzmatrix:

• Ein Eintrag 1 an der Position (i, j) bedeutet, dass eine Kante zwischen den Knoten i und j existiert.
• Ein Eintrag 0 an der Position (i, j) bedeutet, dass keine Kante zwischen den Knoten i und j existiert.

Bedeutung der Eintragswerte:

• Die Einträge in der Adjazenzmatrix geben an, wie die Knoten des Graphen miteinander verbunden sind.
• Eine symmetrische Matrix bedeutet, dass der Graph ungerichtet ist, was bestätigt, dass die Verbindung von Knoten A nach B die gleiche ist wie von B nach A.
• Die Diagonaleinträge sind immer 0, da es keine Schleifen (selbstverbindende Kanten) in diesem Graphen gibt.

b)

Implementiere den DFS-Algorithmus in Python, um alle Knoten des Graphen zu durchlaufen, beginnend bei Knoten A. Gib die Reihenfolge der besuchten Knoten an.

Lösung:

Um den DFS-Algorithmus (Depth-First Search) in Python zu implementieren und alle Knoten des gegebenen Graphen zu durchlaufen, beginne beim Knoten A und befolge die folgenden Schritte:

• Erstelle eine Datenstruktur zur Darstellung des Graphen. Hier verwenden wir ein Adjazenzlisten-Format.
• Erstelle eine Funktion für den DFS-Algorithmus.
• Rufe die Funktion auf und gib die Reihenfolge der besuchten Knoten aus.

Hier ist der Python-Code zur Lösung der Aufgabe:

def dfs(graph, start, visited=None):    if visited is None:        visited = set()        visited.add(start)    print(start, end=' ')        for neighbor in graph[start]:        if neighbor not in visited:            dfs(graph, neighbor, visited)        return visited# Graph in Adjazenzlisten-Darstellunggraph = {    'A': ['B', 'C'],    'B': ['A', 'D'],    'C': ['A', 'D'],    'D': ['B', 'C', 'E'],    'E': ['D']}# DFS-Aufruf und Ausgabe der besuchten Reihenfolgeprint('DFS-Reihenfolge der besuchten Knoten:')dfs(graph, 'A')

Reihenfolge der besuchten Knoten:

Wenn Du diesen Code ausführst, erhältst Du die folgende Ausgabe (die Reihenfolge der besuchten Knoten):

DFS-Reihenfolge der besuchten Knoten:A B D C E

Aufgabe 4)

Hash-TabellenDatenstruktur zur schnellen Suche, Einfügen und Löschen von Elementen mithilfe einer Hash-Funktion.

• Hash-Funktion: Transformiert Schlüssel in einen Index des Arrays.
• Kollisionsbehandlung: Notwendig, da verschiedene Schlüssel denselben Index erzeugen können. Methoden: Verkettung und offene Adressierung.
• Verkettung (chaining): Kollidierende Elemente werden in einer Liste an einem Array-Index gespeichert.
• Offene Adressierung (open addressing): Sucht nach alternativen Positionen im Array.
• Laufzeitkomplexität: Durchschnittlich O(1) für Suche, Einfügen und Löschen; Im schlechtesten Fall O(n).

a)

Beschreibe die Funktionsweise einer Hash-Tabelle und erkläre, wie die Hash-Funktion zur Speicherung und zum Abruf von Daten beiträgt. Was ist die Bedeutung der Kollisionsbehandlung in diesem Kontext?

Lösung:

Funktionsweise einer Hash-Tabelle:

Eine Hash-Tabelle ist eine Datenstruktur, die entwickelt wurde, um schnelle Einfügungen, Löschungen und Suchvorgänge zu ermöglichen. Das Herzstück einer Hash-Tabelle ist die Hash-Funktion, die einen gegebenen Schlüssel in einen spezifischen Index umwandelt.

• Hash-Funktion: Diese Funktion nimmt einen Schlüssel und transformiert ihn in einen Array-Index. Dabei wird ein mathematischer Algorithmus verwendet, der auf den Eingabedaten basiert und diese in eine numerische Form umwandelt, die als Index im Array dient.
• Speicherung: Der Schlüssel wird durch die Hash-Funktion verarbeitet und in einer bestimmten Speicherzelle (Array-Index) abgelegt. Der abgelagerte Index bietet eine schnelle Möglichkeit zum Abrufen.
• Abruf: Bei einer Suchanfrage wird der Schlüssel erneut durch die Hash-Funktion geleitet, um den Index zu ermitteln, an dem die entsprechenden Daten gespeichert sind. Dies ermöglicht eine sehr schnelle Datenlokalisierung, oft in \textit{O(1)} Zeit.
• Kollisionsbehandlung: Da verschiedene Schlüssel denselben Array-Index erzeugen können, sind Mechanismen zur Kollisionsbehandlung notwendig.

Bedeutung der Kollisionsbehandlung:

Kollisionsbehandlung ist von wesentlicher Bedeutung, um sicherzustellen, dass die Hash-Tabelle effektiv arbeiten kann und keine Daten verloren gehen oder überschrieben werden. Zwei gebräuchliche Methoden zur Behandlung von Kollisionen sind:

• Verkettung (chaining): Wenn eine Kollision auftritt, werden alle kollidierenden Elemente in einer verketteten Liste am entsprechenden Array-Index gespeichert. Dies bedeutet, dass jedes Array-Element auf eine Liste zeigt, die alle Schlüssel enthält, die von der Hash-Funktion auf denselben Index abgebildet wurden.
• Offene Adressierung (open addressing): Bei dieser Methode wird im Falle einer Kollision nach einer alternativen Position im Array gesucht, um das kollidierende Element zu speichern. Verschiedene Strategien wie lineares Sondieren, quadratisches Sondieren oder doppelte Hashing-Verfahren können angewendet werden, um einen neuen, nicht kollidierenden Index zu finden.

Die Wahl der richtigen Kollisionsbehandlungsmethode ist entscheidend für die Leistung der Hash-Tabelle. Obwohl die durchschnittliche Zeitkomplexität für Suchoperationen, Einfügungen und Löschungen \textit{O(1)} ist, kann die Leistung im schlimmsten Fall auf \textit{O(n)} anwachsen, wenn viele Kollisionen auftreten und nicht effektiv behandelt werden.

b)

Angenommen, Du verwendest Verkettung zur Kollisionsbehandlung. Skizziere die Schritte, die zum Suchen eines Elements in einer Hash-Tabelle unter Verwendung dieser Methode erforderlich sind. Vergleiche die durchschnittliche und die schlechteste Laufzeitkomplexität dieses Verfahrens.

Lösung:

Schritte zum Suchen eines Elements in einer Hash-Tabelle unter Verwendung von Verkettung:

1. Schritt 1: Berechne den Index des Schlüssels durch Anwendung der Hash-Funktion auf den Suchschlüssel. Sei key der zu suchende Schlüssel und hash_function die verwendete Hash-Funktion. Der Index ist dann index = hash_function(key).
2. Schritt 2: Gehe zum Array-Index, der durch die Hash-Funktion ermittelt wurde.
3. Schritt 3: Durchsuche die verknüpfte Liste, die an diesem Array-Index gespeichert ist. Dies wird mit einer einfachen linearen Suche durchgeführt, indem man jedes Element der Liste mit dem Suchschlüssel vergleicht.
4. Schritt 4: Falls ein Element gefunden wird, das dem Suchschlüssel entspricht, gib dieses Element zurück.
5. Schritt 5: Falls die Liste durchsucht ist und kein passendes Element gefunden wurde, gib einen entsprechenden Hinweis zurück, dass das Element nicht in der Hash-Tabelle vorhanden ist (z. B. null oder not found).

Ein konkretes Beispiel in Pseudocode:

function search(HashTable, key):     index = hash_function(key)     current_list = HashTable[index]     for element in current_list:         if element.key == key:             return element     return null

Vergleich der durchschnittlichen und der schlechtesten Laufzeitkomplexität:

• Durchschnittliche Laufzeitkomplexität: Im Durchschnitt hat die Suche eine Laufzeit von O(1). Dies liegt daran, dass bei einer gut implementierten Hash-Funktion die Elemente gleichmäßig über die Array-Indizes verteilt werden, was zu kürzeren Listen führt.
• Schlechteste Laufzeitkomplexität: Im schlechtesten Fall kann die Suche eine Laufzeit von O(n) haben. Dieser Fall tritt ein, wenn alle Schlüssel auf denselben Array-Index abgebildet werden, was bedeutet, dass eine lange verknüpfte Liste durchsucht werden muss. Dies kann bei einer schlechten Hash-Funktion oder bei einer hohen Anzahl von Kollisionen vorkommen.

c)

Erläutere die Methode der offenen Adressierung zur Kollisionsbehandlung in Hash-Tabellen. Beschreibe dabei insbesondere die Vorgehensweise bei \textit{linearer Sondierung} (linear probing). Führe die Vor- und Nachteile gegenüber der Verkettung auf.

Lösung:

Offene Adressierung zur Kollisionsbehandlung in Hash-Tabellen:

Bei der offenen Adressierung wird ein kollidierendes Element nicht in einer Liste an einem bestimmten Array-Index gespeichert, sondern es wird nach einem alternativen Index im Array gesucht. Dies wird durch eine Probe- oder Suchstrategie bestimmt, und es gibt verschiedene Techniken, um diese alternativen Positionen zu bestimmen. Eine dieser Techniken ist die lineare Sondierung (linear probing).

Lineare Sondierung (linear probing):

Die lineare Sondierung ist eine Methode, bei der im Falle einer Kollision sequentiell nach dem nächsten freien Platz im Array gesucht wird. Das bedeutet, dass wenn der ursprüngliche Index durch die Hash-Funktion besetzt ist, der nächste zu überprüfende Index der nächste in Folge ist (d.h. der Index wird um 1 erhöht).

• Einfügen:1. Berechne den ursprünglichen Index des Schlüssels durch die Hash-Funktion: index = hash_function(key).
• 2. Falls dieser Index besetzt ist, prüfe sequentiell die nächsten Indizes im Array: index + 1, index + 2, usw., bis ein freier Platz gefunden wird.
• 3. Füge das Element am ersten freien Index ein.

• Suchen:1. Berechne den ursprünglichen Index des Schlüssels: index = hash_function(key).
• 2. Falls das Element am berechneten Index nicht der gesuchte Schlüssel ist, prüfe sequentiell die nächsten Indizes: index + 1, index + 2, usw., bis das gesuchte Element gefunden oder eine leere Zelle erreicht wird (was bedeutet, dass das Element nicht in der Tabelle ist).

• Löschen:1. Berechne den ursprünglichen Index des Schlüssels: index = hash_function(key).
• 2. Falls das Element am berechneten Index gefunden wird, markiere diesen Index als gelöscht (oft durch ein spezielles Markierungsbit).
• 3. Prüfe nachfolgende Indizes, um sicherzustellen, dass die Suche später korrekt fortgesetzt werden kann. Verschiebe eventuell verbliebene Elemente.

Ein einfaches Beispiel in Pseudocode für das Einfügen mit linearer Sondierung:

function insert(HashTable, key, value):     index = hash_function(key)     while HashTable[index] is not empty:         index = (index + 1) % len(HashTable)     HashTable[index] = (key, value)

Vor- und Nachteile der linearen Sondierung gegenüber der Verkettung:

• Vorteile:
  • Keine zusätzlichen Datenstrukturen: Es werden keine zusätzlichen Listen oder Speicherplatz benötigt, da alle Elemente direkt im Array gespeichert werden.
  • Einfachere Speicherverwaltung: Alle Einträge befinden sich innerhalb des Arrays und es gibt keinen externen Speicherbedarf.
• Nachteile:
  • Primäres Clustering: Bei linearer Sondierung können Cluster von belegten Indizes entstehen, was die Suchzeit erhöhen kann. Elemente neigen dazu, in Gruppen zu clustern, was die Leistung degradiert.
  • Verschlechterung der Leistung bei hoher Auslastung: Bei hoher Auslastung des Arrays kann die Zeit für das Einfügen und Suchen deutlich ansteigen.
  • Schwierigkeiten bei der Löschung: Die korrekte Handhabung von Löschungen erfordert zusätzliche Maßnahmen, um die Integrität der Hash-Tabelle zu gewährleisten.

d)

Eine Hash-Tabelle hat eine Größe von 7, und die Hash-Funktion lautet h(x) = x % 7. Füge die Schlüssel 10, 20, 15, 7 und 14 ein. Zeichne die resultierende Hash-Tabelle, wenn Du lineare Sondierung zur Kollisionsbehandlung verwendest. Berechne die Belastung der Hash-Tabelle nach den Einfügungen.

Lösung:

Einfügen der Schlüssel 10, 20, 15, 7 und 14 in eine Hash-Tabelle der Größe 7 unter Verwendung von linearer Sondierung:

Gegebene Hash-Funktion: h(x) = x % 7

Starten wir mit einer leeren Hash-Tabelle:

| Index  | Value ||--------|-------|| 0      |       || 1      |       || 2      |       || 3      |       || 4      |       || 5      |       || 6      |       |

Einfügeoperationen:

• Schlüssel 10:Index = 10 % 7 = 3Resultierende Hash-Tabelle:

| Index  | Value ||--------|-------|| 0      |       || 1      |       || 2      |       || 3      | 10    || 4      |       || 5      |       || 6      |       |

• Schlüssel 20:Index = 20 % 7 = 6Resultierende Hash-Tabelle:

| Index  | Value ||--------|-------|| 0      |       || 1      |       || 2      |       || 3      | 10    || 4      |       || 5      |       || 6      | 20    |

• Schlüssel 15:Index = 15 % 7 = 1Resultierende Hash-Tabelle:

| Index  | Value ||--------|-------|| 0      |       || 1      | 15    || 2      |       || 3      | 10    || 4      |       || 5      |       || 6      | 20    |

• Schlüssel 7:Index = 7 % 7 = 0Resultierende Hash-Tabelle:

| Index  | Value ||--------|-------|| 0      | 7     || 1      | 15    || 2      |       || 3      | 10    || 4      |       || 5      |       || 6      | 20    |

• Schlüssel 14:Index = 14 % 7 = 0Index 0 ist besetzt, daher lineare Sondierung:Nächster Index = 1 (besetzt)Nächster Index = 2 (frei)Resultierende Hash-Tabelle:

| Index  | Value ||--------|-------|| 0      | 7     || 1      | 15    || 2      | 14    || 3      | 10    || 4      |       || 5      |       || 6      | 20    |

Berechnung der Belastung der Hash-Tabelle:

Die Belastung wird als Verhältnis der Anzahl der gespeicherten Elemente zur Gesamtgröße der Hash-Tabelle berechnet.

• Anzahl der gespeicherten Elemente: 5 (10, 20, 15, 7, 14)
• Größe der Hash-Tabelle: 7

Die Belastung ist daher:

\[\text{Belastung} = \frac{\text{Anzahl der gespeicherten Elemente}}{\text{Größe der Hash-Tabelle}} = \frac{5}{7} \approx 0.714\]

Die Hash-Tabelle ist also zu etwa 71.4% ausgelastet.