Einführung in die Informatik - Exam

Aufgabe 1)

Gegeben sei eine einfache Programmiersprache namens SimpleLang. In dieser Sprache sind Additions- und Multiplikationsoperationen sowie die Verwendung von Variablen möglich. Ein gültiges Programm in SimpleLang könnte zum Beispiel folgendes sein: a = 3 b = 4 c = a + b * 2. Für diese Aufgabenstellung betrachten wir sowohl die Syntax als auch die Semantik von SimpleLang.

a)

Definiere die Grammatikregeln (kontextfreie Grammatik) für SimpleLang, welche die Syntax der beschriebenen Sprache vollständig abdeckt. Stelle sicher, dass Deine Grammatik die Zuweisungen, Additionen und Multiplikationen korrekt beschreibt.

Lösung:

Um die Grammatikregeln für die Programmiersprache SimpleLang zu definieren, können wir eine kontextfreie Grammatik (CFG) verwenden. Diese Grammatik wird die Syntax für Zuweisungen, Additionen und Multiplikationen beschreiben.

Die kontextfreie Grammatik für SimpleLang könnte wie folgt aussehen:

• Programm:
• Program ::= StatementList
• Aussagenliste:
• StatementList ::= Statement ';' StatementList
• StatementList ::= Statement
• Aussage:
• Statement ::= Assignment
• Zuweisung:
• Assignment ::= Variable '=' Expression
• Ausdruck:
• Expression ::= Term
• Expression ::= Expression '+' Term
• Term:
• Term ::= Factor
• Term ::= Term '*' Factor
• Faktor:
• Factor ::= Variable
• Factor ::= Number
• Factor ::= '(' Expression ')'
• Variable und Zahl:
• Variable ::= [a-zA-Z][a-zA-Z0-9]* (Eine Variable beginnt mit einem Buchstaben und kann Buchstaben und Ziffern enthalten)
• Number ::= [0-9]+ (Eine Zahl ist eine Folge von einer oder mehreren Ziffern)

Diese Grammatik beschreibt die grundlegende Syntax von SimpleLang vollständig:

• Ein Programm besteht aus einer Liste von Aussagen.
• Eine Aussagenliste kann aus mehreren Aussagen bestehen, die durch Semikolons getrennt sind.
• Eine Aussage ist eine Zuweisung.
• Eine Zuweisung besteht aus einer Variablen, einem Gleichheitszeichen und einem Ausdruck.
• Ein Ausdruck kann ein Term oder eine Addition von Termen sein.
• Ein Term kann ein Faktor oder eine Multiplikation von Faktoren sein.
• Ein Faktor kann eine Variable, eine Zahl oder ein geklammerter Ausdruck sein.

Mit dieser Grammatik wird sichergestellt, dass Zuweisungen, Additionen und Multiplikationen korrekt beschrieben werden.

b)

Erstelle den Syntaxbaum (Parse Tree) für das SimpleLang-Programm c = a + b * 2 unter Verwendung der in Sub-Aufgabe 1 definierten Grammatik. Achte darauf, die Hierarchie der Operationen korrekt darzustellen.

Lösung:

Um den Syntaxbaum (Parse Tree) für die SimpleLang-Anweisung c = a + b * 2 zu erstellen, müssen wir die in der vorherigen Aufgabe definierte Grammatik verwenden. Wichtig ist, die Hierarchie der Operationen korrekt darzustellen, also sicherzustellen, dass die Multiplikation vor der Addition ausgeführt wird.

• Grammatikübersicht:
• Program ::= StatementList
• StatementList ::= Statement ';' StatementList | Statement
• Statement ::= Assignment
• Assignment ::= Variable '=' Expression
• Expression ::= Term | Expression '+' Term
• Term ::= Factor | Term '*' Factor
• Factor ::= Variable | Number | '(' Expression ')'
• Variable ::= [a-zA-Z][a-zA-Z0-9]*
• Number ::= [0-9]+

Nun erstellen wir den Syntaxbaum für c = a + b * 2:

• Syntaxbaum: Assignment | -------------------------------- Variable     '='   Expression |    |   |       --------------------    c            Expression       '+' &bsp; Term / Expression '*' Term | | Factor  Factor Term Factor & | & &bsp; &bsp; &bsp; | &bsp; &bsp; &bsp;&bsp;&bsp;&bsp; &bsp; a&es &bsp; &bsp;&bsp; &bsp; | &bsp; | &bsp; &bsp; &bsp; &bsp; | |
• Eine Zuweisung besteht aus einer Variablen, einem Gleichheitszeichen und einem Ausdruck.
• Ein Ausdruck kann ein Term oder eine Addition von Termen sein.
• Ein Term kann ein Faktor oder eine Multiplikation von Faktoren sein.
• Ein Faktor kann eine Variable, eine Zahl oder ein geklammerter Ausdruck sein.

Und das ist der vollständige Syntaxbaum für die Anweisung c = a + b * 2, wobei die Multiplikation korrekt über der Addition priorisiert wird.

c)

Beschreibe die semantische Bedeutung (Operational Semantics) der Addition- und Multiplikationsoperationen in SimpleLang. Stelle sicher, dass die Beschreibung nachvollziehbar macht, wie die Operationen Schritt für Schritt ausgewertet werden.

Lösung:

Um die semantische Bedeutung (Operational Semantics) der Additions- und Multiplikationsoperationen in SimpleLang zu beschreiben, müssen wir erklären, wie diese Operationen schrittweise ausgewertet werden. Dabei betrachten wir, wie die Werte der Variablen und Zahlen in diesen Operationen manipuliert und berechnet werden.

• Multiplikation (*):
• Die Multiplikation nimmt zwei Operanden (Zahlen oder Variablen, die auf Zahlen verweisen) und berechnet deren Produkt.
• Die Evaluierung erfolgt von links nach rechts. Bei verschachtelten Termen wird zuerst der innere Term ausgewertet.
• Steps:

1. Erhalte den Wert des linken Operanden.
2. Erhalte den Wert des rechten Operanden.
3. Multipliziere die beiden erhaltenen Werte.
4. Das Resultat ist der Wert der Multiplikationsoperation.

Beispiel: b * 2 mit b = 4 1. Erhalte den Wert von b (4). 2. Der rechte Operand ist 2. 3. Multipliziere 4 und 2: 4 * 2 = 8 4. Ergebnis ist 8.

Addition (+):

• Die Addition nimmt zwei Operanden (Zahlen oder Variablen, die auf Zahlen verweisen) und berechnet deren Summe.
• Die Evaluierung erfolgt auch hier von links nach rechts. Bei verschachtelten Termen wird ebenfalls zuerst der innere Term ausgewertet.
• Steps:

1. Erhalte den Wert des linken Operanden.
2. Erhalte den Wert des rechten Operanden.
3. Addiere die beiden erhaltenen Werte.
4. Das Resultat ist der Wert der Additionsoperation.

Beispiel: a + (b * 2) mit a = 5 und b = 3 1. Erhalte den Wert von a (5). 2. Evaluierung des rechten Operanden: a. Erhalte den Wert von b (3). b. Multipliziere 3 mit 2: 3 * 2 = 6 3. Addiere den Wert des linken Operanden (5) mit dem Ergebnis des rechten Operanden (6): 5 + 6 = 11 4. Ergebnis ist 11.

Zusammengefasst bedeutet dies:

• Multiplikationen werden zuerst ausgewertet, bevor Additionen durchgeführt werden.
• Die Werte von Variablen werden vor den Operationen aufgelöst.
• Die Operationen werden von links nach rechts durchgeführt, wobei verschachtelte Ausdrücke den inneren Ausdruck zuerst auswerten.

Dieses Vorgehen stellt sicher, dass die semantische Bedeutung der Operationen in SimpleLang klar definiert und nachvollziehbar ist.

d)

Gegeben sei das SimpleLang-Programm: x = 5 y = x * 2 + 3 z = y * x - 4. Führe eine semantische Analyse des Programms durch und berechne die endgültigen Werte von x, y und z. Zeige dabei alle Zwischenschritte und Überlegungen.

Lösung:

Um die semantische Analyse des SimpleLang-Programms x = 5 y = x * 2 + 3 z = y * x - 4 durchzuführen und die endgültigen Werte von x, y und z zu berechnen, gehen wir Schritt für Schritt vor:

• Schritt 1: x = 5
• Dies ist eine einfache Zuweisung. Der Variable x wird der Wert 5 zugewiesen.

Ergebnis nach Schritt 1:

• x = 5
• y = undefiniert
• z = undefiniert
• Schritt 2: y = x * 2 + 3
• Zuerst wird der Ausdruck auf der rechten Seite der Zuweisung ausgewertet.
• Da die Multiplikation eine höhere Priorität als die Addition hat, wird x * 2 zuerst berechnet.
• Ersetze x durch seinen Wert (5): 5 * 2
• Berechne das Ergebnis der Multiplikation: 5 * 2 = 10
• Addiere 3 zu diesem Ergebnis: 10 + 3 = 13

Ergebnis nach Schritt 2:

• x = 5
• y = 13
• z = undefiniert
• Schritt 3: z = y * x - 4
• Zuerst wird der Ausdruck auf der rechten Seite der Zuweisung ausgewertet.
• Da die Multiplikation eine höhere Priorität als die Subtraktion hat, wird y * x zuerst berechnet.
• Ersetze y durch seinen Wert (13) und x durch seinen Wert (5): 13 * 5
• Berechne das Ergebnis der Multiplikation: 13 * 5 = 65
• Subtrahiere 4 von diesem Ergebnis: 65 - 4 = 61

Ergebnis nach Schritt 3:

• x = 5
• y = 13
• z = 61

Damit haben wir die endgültigen Werte der Variablen x, y und z:

• x = 5
• y = 13
• z = 61

Aufgabe 2)

Du bist ein Softwareentwickler bei einem Unternehmen und wirst gebeten, eine Anwendung zu schreiben, die die tägliche Produktion einer Fabrik analysiert. Die Fabrik produziert verschiedene Arten von Produkten und Du musst den Produktionsprozess optimieren. Dazu sollst Du die Schleifen- und Bedingungskontrollstrukturen in Deinem Programm verwenden.

a)

Verwende eine \texttt{for}-Schleife, um die Anzahl der produzierten Produkte über eine Woche (7 Tage) zu summieren. Nimm an, dass Du folgende Produktionswerte in einer Liste hast: \texttt{[120, 150, 130, 170, 160, 145, 180]}. Berechne die Gesamtproduktion der Woche und gib das Ergebnis aus.

Lösung:

Um die Gesamtproduktion einer Woche zu berechnen, können wir eine for-Schleife verwenden, die durch die Liste der Produktionswerte iteriert und die Werte summiert. Hier ist ein Beispiel in Python:

• Definiere die Liste der Produktionswerte: produktionswerte = [120, 150, 130, 170, 160, 145, 180]
• Initialisiere eine Variable, um die Gesamtproduktion zu speichern: gesamtproduktion = 0
• Verwende eine for-Schleife, um durch die Liste zu iterieren und die Produktionswerte zu summieren:

produktionswerte = [120, 150, 130, 170, 160, 145, 180] gesamtproduktion = 0  for wert in produktionswerte: gesamtproduktion += wert  print("Gesamtproduktion der Woche:", gesamtproduktion)

Das Programm läuft wie folgt:

• Initialisiert gesamtproduktion mit 0.
• Iteriert durch jedes Element in der Liste produktionswerte und addiert es zur Variable gesamtproduktion.
• Am Ende der Schleife enthält gesamtproduktion die Summe aller Produktionswerte.
• Die Ausgabe zeigt die Gesamtproduktion der Woche an.

Das Ergebnis wäre:

Gesamtproduktion der Woche: 1055

b)

Schreibe eine \texttt{while}-Schleife, die die Produktion an einem Tag simuliert und so lange läuft, bis mindestens 200 Produkte hergestellt wurden. Nimm an, dass jedes Schleifenintervall 10 Produkte produziert. Gib die Anzahl der Intervalle aus, die benötigt wurden, um die Produktionsschwelle zu erreichen.

Lösung:

Um die Produktion mit einer while-Schleife zu simulieren, die so lange läuft, bis mindestens 200 Produkte hergestellt wurden, kannst Du den folgenden Ansatz verwenden:

• Initialisiere eine Variable, um die Anzahl der produzierten Produkte zu speichern: gesamtproduktion = 0
• Initialisiere eine weitere Variable, um die Anzahl der Schleifenintervalle zu speichern: intervalle = 0
• Verwende eine while-Schleife, die läuft, bis die gesamtproduktion mindestens 200 erreicht:

gesamtproduktion = 0 intervalle = 0  while gesamtproduktion < 200: gesamtproduktion += 10 intervalle += 1  print("Anzahl der Intervalle, die benötigt wurden: ", intervalle)

Das Programm läuft wie folgt:

• Initialisiert gesamtproduktion mit 0.
• Initialisiert intervalle mit 0.
• Die while-Schleife addiert in jedem Schleifendurchlauf 10 Produkte zur gesamtproduktion und incrementiert die intervalle-Variable.
• Sobald die gesamtproduktion mindestens 200 erreicht, beendet sich die Schleife.
• Die Ausgabe zeigt die Anzahl der Intervalle an, die benötigt wurden, um die Produktionsschwelle zu erreichen.

Das Ergebnis wäre in diesem Fall:

Anzahl der Intervalle, die benötigt wurden: 20

c)

Verwende eine \texttt{if-else}-Struktur, um zu entscheiden, welche Art von Bonus die Fabrikarbeiter basierend auf der Tagesproduktion erhalten. Für eine Tagesproduktion von weniger als 150 Produkten gibt es keinen Bonus. Bei einer Produktion zwischen 150 und 170 Produkten gibt es einen kleinen Bonus, und bei einer Produktion von mehr als 170 Produkten gibt es einen großen Bonus. Implementiere diese Logik und gib den entsprechenden Bonus als String aus.

Lösung:

Um zu entscheiden, welchen Bonus die Fabrikarbeiter basierend auf der Tagesproduktion erhalten, kannst Du eine if-else-Struktur verwenden. Hier ist ein Beispiel in Python:

• Initialisiere die Tagesproduktionsvariable: tagesproduktion = 160 (dieser Wert kann je nach Tagesproduktion variieren).
• Verwende die if-else-Struktur, um den Bonus basierend auf der Produktionsmenge zu bestimmen:

tagesproduktion = 160  if tagesproduktion < 150: bonus = "Kein Bonus" elif 150 <= tagesproduktion <= 170: bonus = "Kleiner Bonus" else: bonus = "Großer Bonus"  print("Der Bonus für die Arbeiter ist:", bonus)

Das Programm läuft wie folgt:

• Initialisiere die Variable tagesproduktion mit dem aktuellen Produktionswert.
• Überprüfe mit der if-else-Struktur die Bedingung:
• Wenn die Tagesproduktion weniger als 150 Produkte beträgt, setze bonus auf "Kein Bonus".
• Wenn die Tagesproduktion zwischen 150 und 170 Produkten liegt (inklusive), setze bonus auf "Kleiner Bonus".
• Wenn die Tagesproduktion mehr als 170 Produkte beträgt, setze bonus auf "Großer Bonus".
• Die Ausgabe zeigt den entsprechenden Bonus für die Arbeiter an.

Nehmen wir an, die Tagesproduktion ist 160. Dann wäre die Ausgabe:

Der Bonus für die Arbeiter ist: Kleiner Bonus

d)

Erstelle ein \texttt{switch}-Statement, das entsprechend dem Tag der Woche die Ankündigungen für ein entsprechendes Ereignis ausgibt. Die Woche beginnt bei `1` (Montag) und endet bei `7` (Sonntag). Die Ereignisse sind: \texttt{1: 'Team Meeting', 3: 'Wartungsarbeiten', 5: 'Produktauswertung', 7: 'Abschlussbesprechung'}. Für alle anderen Tage gibt es keine besonderen Ereignisse. Implementiere das \texttt{switch}-Statement und gib die korrekte Ankündigung oder 'Keine besonderen Ereignisse' für den jeweiligen Tag aus.

Lösung:

In Python gibt es kein eingebautes switch-Statement wie in einigen anderen Programmiersprachen (z.B. C oder Java). Stattdessen können wir diese Logik mit if-elif-else-Strukturen oder mit Hilfe eines Dictionaries simulieren. Hier ist ein Beispiel, wie Du das mit einem Dictionary tun kannst:

• Definiere ein Dictionary, das die Wochentage mit den entsprechenden Ereignissen verknüpft:

ereignisse = { 1: 'Team Meeting', 3: 'Wartungsarbeiten', 5: 'Produktauswertung', 7: 'Abschlussbesprechung' }

• Definiere eine Funktion, die die Ankündigung basierend auf dem Tag der Woche ausgibt:

def ankuendigung_fuer_tag(tag): return ereignisse.get(tag, 'Keine besonderen Ereignisse')

• Erhalte den aktuellen Wochentag als Eingabe und gebe die entsprechende Ankündigung aus:

tag = 3  print("Ankündigung für Tag " + str(tag) + ":", ankuendigung_fuer_tag(tag))

Das Programm läuft wie folgt:

• Das Dictionary ereignisse verknüpft die Tage mit den entsprechenden Ereignissen.
• Die Funktion ankuendigung_fuer_tag verwendet die get-Methode des Dictionaries, um das Ereignis für den gegebenen Tag zu finden. Wenn der Tag nicht im Dictionary vorhanden ist, wird der Standardwert 'Keine besonderen Ereignisse' zurückgegeben.
• Der Tag der Woche wird als Input genommen und die entsprechende Ankündigung wird ausgegeben.

Wenn zum Beispiel der aktuelle Tag tag = 3 ist, dann wäre die Ausgabe:

Ankündigung für Tag 3: Wartungsarbeiten

Wenn der aktuelle Tag kein besonderer Tag ist (z. B. tag = 4), dann wäre die Ausgabe:

Ankündigung für Tag 4: Keine besonderen Ereignisse

Aufgabe 3)

Angenommen, Du hast eine unsortierte Liste von Ganzzahlen mit 1000 Elementen, die zufällig im Bereich von 1 bis 10.000 verteilt sind. Diese Liste möchtest Du verwenden, um die Effizienz verschiedener Such- und Sortieralgorithmen zu analysieren und zu vergleichen.

b)

Implementiere den Algorithmus der binären Suche in Python. Sortiere zuvor die Liste mit dem Merge Sort Algorithmus. Bestimme die durchschnittliche Laufzeitkomplexität für das Finden eines Elements nach der Sortierung. Erkläre die Iterationen und Berechnungen, die notwendig sind, um ein Element mit der binären Suche zu finden. Nutze dazu die Big-O-Notation.

Lösung:

Implementierung des binären Suchalgorithmus und Merge Sort in Python:

• Merge Sort Algorithmus

def merge_sort(liste):    if len(liste) <= 1:        return liste    mid = len(liste) // 2    links = merge_sort(liste[:mid])    rechts = merge_sort(liste[mid:])    return merge(links, rechts)def merge(links, rechts):    result = []    i = j = 0    while i < len(links) and j < len(rechts):        if links[i] < rechts[j]:            result.append(links[i])            i += 1        else:            result.append(rechts[j])            j += 1    result.extend(links[i:])    result.extend(rechts[j:])    return result

• Binäre Suche Algorithmus

def binaere_suche(liste, ziel):    links, rechts = 0, len(liste) - 1    while links <= rechts:        mitte = (links + rechts) // 2        if liste[mitte] == ziel:            return mitte        elif liste[mitte] < ziel:            links = mitte + 1        else:            rechts = mitte - 1    return -1

• Erklärung der Laufzeitkomplexität:

• Merge Sort: Merge Sort hat eine durchschnittliche und worst-case Laufzeitkomplexität von O(n log n). Der Algorithmus teilt die Liste kontinuierlich in zwei Hälften (was log n Aufruften entspricht), bis jede Unterliste nur ein Element enthält, und führt dann O(n) Kombinationen durch, um die sortierte Liste zu erzeugen.
• Binäre Suche: Nach der Sortierung können wir die binäre Suche verwenden, um ein Element effizient zu finden. Im schlimmsten Fall ist die Laufzeitkomplexität O(log n), weil der Suchraum mit jeder Iteration halbiert wird.

• Durchlauf des binären Suchalgorithmus:

• Die binäre Suche funktioniert, indem die mittlere Position der Liste überprüft wird. Wenn das Ziel-Element kleiner als das mittlere Element ist, wird die linke Sub-Liste durchsucht. Wenn es größer ist, wird die rechte Sub-Liste durchsucht. Dieser Prozess wiederholt sich, bis das Ziel-Element gefunden wird oder alle Elemente überprüft wurden.
• Da der Suchraum mit jeder Iteration halbiert wird, beträgt die maximale Anzahl der Iterationen log(n), wobei n die Anzahl der Elemente in der Liste ist.

• Gesamte Laufzeitkomplexität:

• Die Gesamtlaufzeitkomplexität für das Finden eines Elements nach der Sortierung ist die Summe der Laufzeitkomplexität von Merge Sort und der binären Suche:
• Gesamt: O(n log n) + O(log n) = O(n log n)

c)

Vergleiche die Effizienz von Bubble Sort und Merge Sort für das Sortieren der gegebenen Liste. Implementiere beide Algorithmen in Python und messe die Zeit, die sie zum Sortieren der Liste benötigen. Analysiere die Zeit- und Speicherkomplexität der beiden Algorithmen und erkläre, weshalb einer der beiden effizienter ist. Stelle Deine Ergebnisse in tabellarischer Form dar und erläutere sie ausführlich. Nutze dazu die Big-O-Notation zur Darstellung der Komplexität.

Lösung:

Implementierung von Bubble Sort und Merge Sort in Python:

• Bubble Sort Algorithmus

import timedef bubble_sort(liste):    n = len(liste)    for i in range(n):        for j in range(0, n-i-1):            if liste[j] > liste[j+1]:                liste[j], liste[j+1] = liste[j+1], liste[j]# Beispiel-Listeunsorted_list = [random.randint(1, 10000) for _ in range(1000)]# Zeitmessung für Bubble Sortstart_time = time.time()bubble_sort(unsorted_list.copy())bubble_sort_time = time.time() - start_time

• Merge Sort Algorithmus

def merge_sort(liste):    if len(liste) <= 1:        return liste    mid = len(liste) // 2    links = merge_sort(liste[:mid])    rechts = merge_sort(liste[mid:])    return merge(links, rechts)def merge(links, rechts):    result = []    i = j = 0    while i < len(links) and j < len(rechts):        if links[i] < rechts[j]:            result.append(links[i])            i += 1        else:            result.append(rechts[j])            j += 1    result.extend(links[i:])    result.extend(rechts[j:])    return result# Zeitmessung für Merge Sortstart_time = time.time()sorted_list = merge_sort(unsorted_list.copy())merge_sort_time = time.time() - start_time

• Messergebnisse in tabellarischer Form:

Algorithmus	Zeit (Sekunden)
Bubble Sort	{bubble_sort_time:.6f}
Merge Sort	{merge_sort_time:.6f}

• Analyse der Zeit- und Speicherkomplexität:

• Bubble Sort:
• Zeitkomplexität: O(n^2)
• Im schlimmsten und durchschnittlichen Fall benötigt Bubble Sort O(n^2) Vergleiche und Vertauschungen, weil jedes Element mehrfach verglichen wird.
• Speicherkomplexität: O(1)
• Bubble Sort benötigt keine zusätzliche Speicherkapazität außer dem Platz für die Liste selbst.

• Merge Sort:
• Zeitkomplexität: O(n log n)
• Merge Sort teilt die Liste rekursiv in zwei Hälften, sortiert jede Hälfte und kombiniert sie wieder. Dies führt zu einer logarithmischen Anzahl von Teilungen und einer linearen Anzahl von Kombinationen.
• Speicherkomplexität: O(n)
• Merge Sort benötigt zusätzlichen Speicherplatz für die Hilfslisten während des Merge-Prozesses.

• Schlussfolgerung:
• Merge Sort ist effizienter als Bubble Sort für große Listen. Dies liegt daran, dass die Zeitkomplexität von O(n log n) wesentlich besser skaliert als die quadratische Komplexität von Bubble Sort.
• Allerdings erfordert Merge Sort zusätzlichen Speicherplatz, während Bubble Sort in-place arbeitet.

Aufgabe 4)

Komplexitätsanalyse: Gegeben ist ein Algorithmus, der eine sortierte Liste durchsucht und einen bestimmten Wert sucht. Der Algorithmus verwendet die binäre Suche. Dabei wird die Liste in zwei Hälften geteilt und jeweils die Hälfte durchsucht, die den gesuchten Wert enthalten könnte. Der Algorithmus endet, wenn der Wert gefunden wurde oder die Liste vollständig durchsucht wurde.

b)

Berechne den Speicherbedarf des gegebenen Algorithmus. Gehe dabei auf die Anzahl der notwendigen Variablen und zusätzlichen Speicherstrukturen ein, die für die Durchführung der binären Suche benötigt werden.

Lösung:

Berechnung des Speicherbedarfs des gegebenen AlgorithmusUm den Speicherbedarf des binären Suchalgorithmus zu berechnen, gehen wir wie folgt vor:

• Beschreibung des Algorithmus:Die binäre Suche durchsucht eine sortierte Liste, indem sie die Liste in zwei Hälften teilt und die Hälfte durchsucht, die den gesuchten Wert enthalten könnte. Dieser Vorgang wiederholt sich rekursiv oder iterativ, bis der gesuchte Wert gefunden wird oder die Liste vollständig durchsucht ist.
• Speicherbedarf für Variablen:Der Algorithmus benötigt einige Variablen:
  • Index- und Grenzvariablen: Variablen wie left, right und mid werden verwendet, um die aktuellen Indizes und Grenzen der Liste zu speichern. Diese Variablen sind primitive Datentypen (typischerweise Integer) und haben daher einen festen und konstanten Speicherbedarf.
  • Zielwert: Eine Variable wird benötigt, um den zu suchenden Wert zu speichern. Auch dies ist eine primitive Variable und benötigt konstanten Speicher.
• Speicherbedarf für rekursive Implementierung:Falls der Algorithmus rekursiv implementiert ist, benötigt jeder rekursive Aufruf Speicher auf dem Call-Stack. Jeder Aufruf braucht Speicher für die Variablen und die Rücksprungadresse. Da die Tiefe der Rekursion im schlimmsten Fall logarithmisch zur Eingabengröße n ist, ergibt sich ein zusätzlicher Speicherbedarf von \(O(\log n)\).
• Speicherbedarf für iterative Implementierung:Falls der Algorithmus iterativ implementiert ist, benötigt er keinen zusätzlichen Speicher für den Call-Stack, und der Speicherbedarf bleibt auf konstantem Niveau bezogen auf die benötigten Variablen.

Zusammenfassend:

• Der Speicherbedarf der binären Suche kann im iterativen Fall konstant beschrieben werden, also \(O(1)\), da lediglich eine feste Anzahl von Variablen genutzt wird.
• Im Fall einer rekursiven Implementierung liegt der Speicherbedarf bei \(O(\log n)\), da jeder rekursive Aufruf Speicher auf dem Call-Stack benötigt.

c)

Vergleiche die Worst-Case-Laufzeitkomplexität der binären Suche mit der Worst-Case-Laufzeitkomplexität einer linearen Suche. Erkläre anhand eines Beispiels, wann die binäre Suche signifikant effizienter ist als die lineare Suche.

Lösung:

Vergleich der Worst-Case-Laufzeitkomplexität der binären Suche mit der linearen SucheUm die Effizienz der binären Suche im Vergleich zur linearen Suche zu verstehen, betrachten wir die Worst-Case-Laufzeitkomplexität beider Algorithmen:

• Lineare Suche:Bei der linearen Suche wird jeder einzelne Eintrag in der unsortierten Liste nacheinander geprüft, bis der gesuchte Wert gefunden wird oder das Ende der Liste erreicht ist. Dies bedeutet, dass im schlimmsten Fall alle n Elemente der Liste durchsucht werden müssen.Die Worst-Case-Laufzeitkomplexität der linearen Suche ist daher\[O(n)\]
• Binäre Suche:Die binäre Suche wird auf eine sortierte Liste angewendet. Sie halbiert die Suchmenge in jedem Schritt und konzentriert sich auf die Hälfte, die den gesuchten Wert enthalten könnte. Dieser Vorgang wird so lange wiederholt, bis der gesuchte Wert gefunden wird oder die Menge auf eine Größe von 1 reduziert wird.Wie bereits hergeleitet, ist die Worst-Case-Laufzeitkomplexität der binären Suche\[O(\log n)\]

Beispiel und Effizienzvergleich:Betrachten wir ein Beispiel mit einer Liste der Länge n = 1.000.000:

• Lineare Suche: Im schlimmsten Fall muss die lineare Suche alle 1.000.000 Elemente durchsuchen. Dies bedeutet, dass bis zu 1.000.000 Vergleiche notwendig sind.
• Binäre Suche: Im schlimmsten Fall halbiert die binäre Suche die Liste wiederholt, bis die Größe auf 1 reduziert ist. Dies erfordert:\[\log_2(1.000.000)\approx 19,93\]Das bedeutet, dass die binäre Suche maximal etwa 20 Vergleiche benötigt, um den Wert in einer Liste mit 1.000.000 Elementen zu finden.

Fazit:Die binäre Suche ist signifikant effizienter als die lineare Suche, insbesondere bei großen Datensätzen. Während die lineare Suche bis zu n Vergleiche benötigt, benötigt die binäre Suche nur log_2(n) Vergleiche, was bei großen Werten von n einen enormen Unterschied in der Laufzeit bedeutet. Beispielsweise ist 20 im Vergleich zu 1.000.000 eine drastische Reduktion der Anzahl der Operationen.

d)

Erläutere den Begriff der amortisierten Analyse und gib ein konkretes Beispiel, bei dem die amortisierte Analyse zur Bestimmung der Laufzeit eines Algorithmus verwendet wird. Wie unterscheidet sich diese Analyse von der Worst-Case-Analyse?

Lösung:

Amortisierte AnalyseDie amortisierte Analyse ist eine Technik zur Bestimmung der durchschnittlichen Laufzeit eines Algorithmus über eine Sequenz von Operationen. Im Gegensatz zur Worst-Case-Analyse, die die maximale Laufzeit einer einzelnen Operation betrachtet, zielt die amortisierte Analyse darauf ab, die durchschnittlichen Kosten einer Operation zu berechnen, indem sie die Gesamtkosten einer Sequenz von Operationen durch die Anzahl der Operationen teilt. Dies ergibt oft eine realistischere Darstellung der erwarteten Leistung über viele Operationen hinweg.Konkretes Beispiel: Dynamisches ArrayEin häufiges Beispiel, das mit amortisierter Analyse analysiert wird, ist die Erweiterung eines dynamischen Arrays (wie etwa ein ArrayList in Java oder eine vector in C++). Die folgenden Schritte erläutern die entsprechenden Schritte:

1. Initiale Einfügen: Angenommen, wir haben ein dynamisches Array mit initialer Kapazität 1. Das Einfügen des ersten Elements ist eine konstante Zeitoperation \(O(1)\).
2. Erweiterung: Wenn das Array voll ist und ein weiteres Element eingefügt werden soll, muss das Array verdoppelt werden. Dies führt zu zusätzlichen Kosten von \(O(n)\)-Zeit für das Kopieren der vorhandenen Elemente in das neue Array.
3. Einfügen neuer Elemente: Nach der Verdopplung ist wieder genügend Platz für die nächsten Einfügungen, die nun erneut in konstanter Zeit \(O(1)\) erfolgen können, bis das Array erneut gefüllt ist.

Amortisierte Kostenberechnung:Um die amortisierten Kosten zu berechnen, betrachten wir die gesamte Sequenz von Elementeinfügungen:

• Die ersten Einfügungen sind kostengünstig: das Einfügen eines einzelnen Elements ohne Verdopplung kostet \(O(1)\).
• Beim Verdoppeln, wenn das Array voll ist, müssen alle Elemente kopiert werden, was \(O(n)\) kostet.

Nehmen wir nun an, wir fügen \(n\) Elemente in das Array ein. Während der gesamten Sequenz gibt es \(\log_2(n)\) Verdopplungen (weil das Array um den Faktor 2 wächst). Betrachten wir die Gesamtkosten aller Operationen:\[\text{Gesamtkosten} = \sum_{i=0}^{\log_2(n)} O(2^i)\]Die Kosten für die Verdopplungen summieren sich zu:\[O(1) + O(2) + O(4) + ... + O(n)\] was letztlich \(O(n)\) ergibt. Da wir \(n\) Operationen betrachten, sind die amortisierten Kosten pro Operation:\[\frac{O(n)}{n} = O(1)\]Vergleich zur Worst-Case-Analyse:

• Worst-Case-Analyse: Diese Analyse betrachtet die Kosten der teuersten einzelnen Operation. Beim dynamischen Array könnte dies eine Kapazitätsverdopplung sein, die \(O(n)\) kostet.
• Amortisierte Analyse: Diese Analyse betrachtet die durchschnittlichen Kosten pro Operation über eine Sequenz von Operationen. Auch wenn eine einzelne Operation teuer sein kann, sind die durchschnittlichen Kosten pro Operation \(O(1)\), da viele günstige Operationen die gelegentlichen teuren Operationen ausgleichen.