Grundlagenmodul - Exam

Aufgabe 1)

Stell Dir vor, Du entwickelst eine Software zum Verwalten von Studenteninformationen an der Universität Erlangen-Nürnberg. Die Software soll grundlegende Informationen eines Studenten enthalten und folgende Abfragen ermöglichen:

• Die Eingabe der Studenteninformationen (Name, Matrikelnummer, Studiengang)
• Das Finden eines Studenten anhand der Matrikelnummer
• Das Aktualisieren der Studiengangsinformation eines Studenten

Verwende eine Programmiersprache Deiner Wahl, aber achte darauf, die Syntaxregeln und Konzepte zu berücksichtigen, die in den Vorlesungsunterlagen erwähnt wurden.

a)

Subexercise 1: Schreibe eine Funktion eingabeStudent(), die die Informationen eines Studenten von der Konsole einliest. Die Funktion soll einen Datentyp, z.B. ein Dictionary oder eine Struktur, verwenden, um die Studenteninformationen zu speichern. Erläutere den Code und beschreibe, wie die lexikalische Analyse und die Syntaxanalyse in dem von Dir verwendeten Code greifen.

def eingabeStudent():    name = input('Name eingeben: ')    matrikelnummer = input('Matrikelnummer eingeben: ')    studiengang = input('Studiengang eingeben: ')    student = {        'Name': name,        'Matrikelnummer': matrikelnummer,        'Studiengang': studiengang    }    return student

Lösung:

Um die gestellte Aufgabe zu lösen, erstellen wir eine Funktion namens eingabeStudent(), die die Studenteninformationen von der Konsole einliest und in einem Dictionary speichert. Dies ist eine einfache und effiziente Möglichkeit, die Informationen strukturiert zu speichern.

Hier ist der Code, mit einer detaillierten Erläuterung:

def eingabeStudent():    name = input('Name eingeben: ')    matrikelnummer = input('Matrikelnummer eingeben: ')    studiengang = input('Studiengang eingeben: ')    student = {        'Name': name,        'Matrikelnummer': matrikelnummer,        'Studiengang': studiengang    }    return student

Erläuterung des Codes:

• def eingabeStudent(): Diese Zeile definiert die Funktion eingabeStudent().
• name = input('Name eingeben: '): Hier wird der Benutzer aufgefordert, den Namen des Studenten einzugeben. Der eingegebene Wert wird in der Variable name gespeichert.
• matrikelnummer = input('Matrikelnummer eingeben: '): In dieser Zeile wird die Matrikelnummer des Studenten abgefragt und in der Variable matrikelnummer gespeichert.
• studiengang = input('Studiengang eingeben: '): Hier wird der Benutzer aufgefordert, den Studiengang einzugeben. Der Wert wird in der Variable studiengang gespeichert.
• student = { 'Name': name, 'Matrikelnummer': matrikelnummer, 'Studiengang': studiengang}: Ein Dictionary wird erstellt, das drei Schlüssel enthält: 'Name', 'Matrikelnummer' und 'Studiengang'. Den jeweiligen Schlüsseln werden die zuvor eingegebenen Werte zugewiesen.
• return student: Die Funktion gibt das Dictionary student zurück, das die Informationen des Studenten enthält.

Lexikalische Analyse und Syntaxanalyse:

• Lexikalische Analyse: In dieser Phase wird der Code in Token zerlegt. Ein Token ist die kleinste Einheit des Codes und kann aus Bezeichnern (z. B. Variablennamen), Schlüsselwörtern (z. B. def), Operatoren (z. B. =), und Literalen (z. B. 'Name eingeben: ') bestehen.
• Syntaxanalyse: In dieser Phase wird überprüft, ob die Folge der Token den grammatikalischen Regeln (Syntax) der Programmiersprache entspricht. Zum Beispiel überprüft der Parser, ob der Funktionsaufruf korrekt ist und ob die Anweisungen innerhalb der Funktion den Regeln von Python folgen.

Durch die Kombination dieser beiden Analyseschritte wird sichergestellt, dass der Code sowohl lexikalisch korrekt (gültige Token) als auch syntaktisch korrekt (richtige Reihenfolge und Struktur der Token) ist.

b)

Subexercise 2: Implementiere eine weitere Funktion aktualisiereStudiengang(student, neuerStudiengang), die den Studiengang eines existierenden Studentendatensatzes ändert. Verfasse zusätzlich eine Kontrolle, die die gültige Dateneingabe (Typprüfung) der Matrikelnummer sicherstellt. Beschreibe die Funktionalität und erläutere, wie Kontrollstrukturen und Typprüfungen verwendet werden.

def aktualisiereStudiengang(student, neuerStudiengang):    if not isinstance(student['Matrikelnummer'], str):        raise ValueError('Ungültige Matrikelnummer')    student['Studiengang'] = neuerStudiengang    return student

Lösung:

Um die gestellte Aufgabe zu lösen, erstellen wir eine Funktion namens aktualisiereStudiengang(student, neuerStudiengang), die den Studiengang eines existierenden Studentendatensatzes ändert. Zusätzlich fügen wir eine Typprüfung hinzu, um sicherzustellen, dass die Matrikelnummer ein gültiger String ist.

Hier ist der vollständige Code, gefolgt von einer detaillierten Erläuterung:

def aktualisiereStudiengang(student, neuerStudiengang):    if not isinstance(student['Matrikelnummer'], str):        raise ValueError('Ungültige Matrikelnummer')    student['Studiengang'] = neuerStudiengang    return student

Erläuterung des Codes:

• def aktualisiereStudiengang(student, neuerStudiengang): Diese Zeile definiert die Funktion aktualisiereStudiengang().
• if not isinstance(student['Matrikelnummer'], str): Hier verwenden wir die Funktion isinstance(), um zu überprüfen, ob die Matrikelnummer des Studenten ein String ist. Falls nicht, wird eine ValueError Ausnahme ausgelöst.
• raise ValueError('Ungültige Matrikelnummer'): Wenn die Matrikelnummer kein String ist, wird diese Ausnahme ausgelöst und eine entsprechende Fehlermeldung ausgegeben.
• student['Studiengang'] = neuerStudiengang: Der Studiengang des Studenten wird auf den neuen Studiengang aktualisiert.
• return student: Die Funktion gibt das aktualisierte Dictionary student zurück.

Funktionalität:

• Die Funktion aktualisiereStudiengang() nimmt zwei Argumente: das Dictionary student, das die Informationen des Studenten enthält, und den neuen Studiengang neuerStudiengang.
• Die Funktion überprüft, ob die Matrikelnummer des Studenten ein String ist. Dies wird durch die Funktion isinstance() realisiert.
• Wenn die Matrikelnummer kein String ist, wird eine ValueError Ausnahme ausgelöst.
• Ist die Matrikelnummer ein String, wird der Studiengang des Studenten auf den neuen Studiengang aktualisiert.
• Zum Schluss gibt die Funktion das aktualisierte Dictionary student zurück.

Verwendung von Kontrollstrukturen und Typprüfungen:

• Kontrollstrukturen: Die if-Anweisung wird verwendet, um die Typprüfung der Matrikelnummer zu kontrollieren. Falls die Bedingung if not isinstance(student['Matrikelnummer'], str) wahr ist, wird eine Ausnahme ausgelöst. Andernfalls wird der Code fortgesetzt und der Studiengang wird aktualisiert.
• Typprüfungen: Die Funktion isinstance() wird verwendet, um zu überprüfen, ob ein Objekt zu dem angegebenen Datentyp gehört. In diesem Fall überprüfen wir, ob die Matrikelnummer ein String ist. Diese Typprüfung stellt sicher, dass die Daten konsistent und korrekt sind, bevor eine Aktualisierung durchgeführt wird.

Aufgabe 2)

Du arbeitest an einem Projekt zur Simulation einer Verkehrssignalsteuerung. Du wirst Schleifen und Bedingungen nutzen, um die Signale für Autos und Fußgänger zu steuern. Das Verkehrssignal folgt einem einfachen Ablauf:

• Wenn die Ampel für Autos grün ist, ist die Ampel für Fußgänger rot und bleibt für 60 Sekunden in diesem Zustand.
• Wenn die Ampel für Autos gelb wird, bleibt sie für 5 Sekunden in diesem Zustand, während die Ampel für Fußgänger weiterhin rot bleibt.
• Wenn die Ampel für Autos rot ist, wechselt die Fußgängerampel auf grün und bleibt für 30 Sekunden grün.
• Danach wird die Fußgängerampel wieder rot und der Zyklus beginnt von neuem.

b)

Beschreibe die Bedeutung einer do-while-Schleife in einer solchen Simulation und erläutere, warum sie gegenüber einer normalen while-Schleife bevorzugt werden könnte. Implementiere die Simulation erneut unter Verwendung einer do-while-Schleife.

Lösung:

Bedeutung und Vorteile einer do-while-Schleife

In einer Verkehrssignalsteuerung-Simulation kannst Du eine do-while-Schleife nutzen, um sicherzustellen, dass ein bestimmter Codeblock mindestens einmal ausgeführt wird, bevor eine Bedingung geprüft wird. Das ist besonders sinnvoll, wenn Du sicherstellen möchtest, dass der Ablauf der Ampelsteuerung mindestens einmal vollständig durchläuft.

Vorteile gegenüber einer normalen while-Schleife:

• Eine do-while-Schleife garantiert, dass der Codeblock mindestens einmal ausgeführt wird, unabhängig davon, ob die Bedingung am Anfang wahr ist oder nicht.
• Das ist besonders nützlich in Szenarien wie einer Ampelsteuerung, wo Du sicherstellen möchtest, dass der gesamte Zyklus mindestens einmal durchläuft, bevor eine Bedingung erneut überprüft wird.

Implementierung der Simulation mit einer do-while-Schleife

let autosAmpel = 'gruen';let fussgaengerAmpel = 'rot';let zeit = 0;do {  if (autosAmpel === 'gruen') {    // Ampel für Autos ist grün für 60 Sekunden    zeit = 60;    fussgaengerAmpel = 'rot';    console.log(`Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel} für ${zeit} Sekunden`);    autosAmpel = 'gelb';  }   else if (autosAmpel === 'gelb') {    // Ampel für Autos ist gelb für 5 Sekunden    zeit = 5;    console.log(`Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel} für ${zeit} Sekunden`);    autosAmpel = 'rot';  }  else if (autosAmpel === 'rot') {    // Ampel für Autos ist rot, Fußgängerampel wird grün für 30 Sekunden    fussgaengerAmpel = 'gruen';    zeit = 30;    console.log(`Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel} für ${zeit} Sekunden`);    fussgaengerAmpel = 'rot';    autosAmpel = 'gruen'; // Zyklus beginnt von Neuem  }} while (true);

c)

Stelle dir vor, das System muss erweitert werden, um eine Priorität für Notfallfahrzeuge zu berücksichtigen. Die Ampel sollte auf grün schalten, wenn ein Notfallfahrzeug erkannt wird. Implementiere eine zusätzliche Bedingung für diese Anforderung in die bestehende Simulation. Verwende eine boolean-Variable notfall, die auf true gesetzt wird, wenn ein Notfallfahrzeug eintrifft.

Lösung:

Erweiterung der Ampelsteuerung für Notfallfahrzeuge

Um die Simulation so zu erweitern, dass sie eine Priorität für Notfallfahrzeuge berücksichtigt, kannst Du eine zusätzliche Bedingung einfügen. Wenn die Variable notfall auf true gesetzt wird, sollte die Ampel für Autos sofort auf grün schalten. Hier ist, wie Du dies in den bestehenden Code integrieren kannst:

Modifizierte Implementierung der Simulation

let autosAmpel = 'gruen';let fussgaengerAmpel = 'rot';let zeit = 0;let notfall = false;do {  if (notfall === true) {    // Wenn ein Notfallfahrzeug erkannt wird, wird die Autos-Ampel sofort grün    autosAmpel = 'gruen';    fussgaengerAmpel = 'rot';    zeit = 0;    console.log(`Notfall! Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel}`);    // Hier kannst Du notfall wieder auf false setzen, nachdem die Ampel grün geworden ist    notfall = false;  } else {    if (autosAmpel === 'gruen') {      // Ampel für Autos ist grün für 60 Sekunden      zeit = 60;      fussgaengerAmpel = 'rot';      console.log(`Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel} für ${zeit} Sekunden`);      autosAmpel = 'gelb';    }     else if (autosAmpel === 'gelb') {      // Ampel für Autos ist gelb für 5 Sekunden      zeit = 5;      console.log(`Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel} für ${zeit} Sekunden`);      autosAmpel = 'rot';    }    else if (autosAmpel === 'rot') {      // Ampel für Autos ist rot, Fußgängerampel wird grün für 30 Sekunden      fussgaengerAmpel = 'gruen';      zeit = 30;      console.log(`Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel} für ${zeit} Sekunden`);      fussgaengerAmpel = 'rot';      autosAmpel = 'gruen'; // Zyklus beginnt von Neuem    }  }} while (true);

In diesem modifizierten Code wird die Bedingung für Notfälle zuerst überprüft. Wenn ein Notfallfahrzeug erkannt wird (notfall ist true), schaltet die Autos-Ampel sofort auf grün und die Fußgängerampel auf rot. Der Wert von notfall wird dann wieder auf false gesetzt, damit das System in den normalen Zyklus zurückkehren kann, sobald der Notfall vorbei ist.

d)

Füge eine for-Schleife hinzu, die die Simulation für einen Zeitraum von 24 Stunden durchläuft. Nutze dabei eine Schrittweite von einer Sekunde, um die tatsächliche Zeit zu simulieren (d.h., insgesamt 86400 Iterationen). Berücksichtige dabei die verschiedenen Signalzeiten und die Notfallbedingung.

Lösung:

Erweiterung der Simulation zur Laufzeit von 24 Stunden

Um die Simulation für einen Zeitraum von 24 Stunden mit einer Schrittweite von einer Sekunde durchzuführen, können wir eine for-Schleife mit 86400 Iterationen hinzufügen. Dabei berücksichtigen wir die verschiedenen Signalzeiten und die Notfallbedingung. Hier ist die vollständige Implementierung:

Implementierung der Verkehrssignalsteuerung

let autosAmpel = 'gruen';let fussgaengerAmpel = 'rot';let notfall = false;function signalwechsel(zeit, ampelFarbe, fussgaengerFarbe, notfall) {  for (let sekunde = 0; sekunde < zeit; sekunde++) {    if (notfall === true) {      // Wenn ein Notfallfahrzeug erkannt wird, wird die Autos-Ampel sofort grün      autosAmpel = 'gruen';      fussgaengerAmpel = 'rot';      console.log(`Notfall! Autos: ${autosAmpel}, Fußgänger: ${fussgaengerAmpel}`);      // notfall wieder auf false setzen, nachdem die Ampel grün geworden ist      notfall = false;    } else {      console.log(`Sekunde ${sekunde}: Autos: ${ampelFarbe}, Fußgänger: ${fussgaengerFarbe}`);    }  }}for (let i = 0; i < 86400; i++) {  if (autosAmpel === 'gruen') {    signalwechsel(60, 'gruen', 'rot', notfall);    autosAmpel = 'gelb';  } else if (autosAmpel === 'gelb') {    signalwechsel(5, 'gelb', 'rot', notfall);    autosAmpel = 'rot';  } else if (autosAmpel === 'rot') {    signalwechsel(30, 'rot', 'gruen', notfall);    autosAmpel = 'gruen'; // Zyklus beginnt von Neuem  }}

In dieser Implementierung wird die Funktion signalwechsel genutzt, um die Signalwechsel und die Notfallbedingung für eine gegebene Zeit zu simulieren. Die Hauptschleife (for-Schleife) läuft 86400 Iterationen, die jeweils eine Sekunde simulieren und entsprechend den Ampelstatus aktualisieren.

Innerhalb der signalwechsel-Funktion wird die Notfallbedingung überprüft und entsprechend gehandelt, wenn ein Notfallfahrzeug erkannt wird.

Aufgabe 3)

Gegeben sei eine Liste von ganzen Zahlen: L = [34, 7, 23, 32, 5, 62]. Diese Liste soll mit Hilfe von Sortier- und Suchalgorithmen bearbeitet werden.

a)

Verwende den Merge Sort Algorithmus, um die Liste L zu sortieren. Zeige alle Zwischenschritte auf, die beim Sortieren der Liste auftreten. Erläutere die Zeitkomplexität und den Speicherbedarf des Merge Sort Algorithmus.

  def merge_sort(arr):      if len(arr) > 1:          mid = len(arr) // 2          L = arr[:mid]          R = arr[mid:]          merge_sort(L)          merge_sort(R)          i = j = k = 0          while i < len(L) and j < len(R):              if L[i] < R[j]:                  arr[k] = L[i]                  i += 1              else:                  arr[k] = R[j]                  j += 1              k += 1          while i < len(L):              arr[k] = L[i]              i += 1              k += 1          while j < len(R):              arr[k] = R[j]              j += 1              k += 1  return arr

Lösung:

Um die Liste L = [34, 7, 23, 32, 5, 62] unter Verwendung des Merge Sort Algorithmus zu sortieren, werden wir Schritt für Schritt alle Zwischenschritte aufzeigen. Hier ist der Merge Sort Algorithmus und seine Anwendung auf die gegebene Liste:

  def merge_sort(arr):      if len(arr) > 1:          mid = len(arr) // 2          L = arr[:mid]          R = arr[mid:]          merge_sort(L)          merge_sort(R)          i = j = k = 0          while i < len(L) and j < len(R):              if L[i] < R[j]:                  arr[k] = L[i]                  i += 1              else:                  arr[k] = R[j]                  j += 1              k += 1          while i < len(L):              arr[k] = L[i]              i += 1              k += 1          while j < len(R):              arr[k] = R[j]              j += 1              k += 1  return arr

Jetzt werden wir die einzelnen Schritte des Merge Sort Algorithmus durchgehen:

• Schritt 1: Teile die Liste [34, 7, 23, 32, 5, 62] in zwei Hälften: L1 = [34, 7, 23] und L2 = [32, 5, 62].
• Schritt 2: Teile L1 weiter in L11 = [34] und L12 = [7, 23]. Teile L2 weiter in L21 = [32] und L22 = [5, 62].
• Schritt 3: Teile L12 in L121 = [7] und L122 = [23]. Teile L22 in L221 = [5] und L222 = [62].
• Schritt 4: Führe die Listen L121 und L122 zusammen zu [7, 23]. Führe die Listen L221 und L222 zusammen zu [5, 62].
• Schritt 5: Führe [34] und [7, 23] zusammen zu [7, 23, 34]. Führe [32] und [5, 62] zusammen zu [5, 32, 62].
• Schritt 6: Führe abschließend [7, 23, 34] und [5, 32, 62] zusammen zu [5, 7, 23, 32, 34, 62].

Die sortierte Liste lautet somit: [5, 7, 23, 32, 34, 62].

Zeitkomplexität: Die Zeitkomplexität des Merge Sort Algorithmus beträgt im schlimmsten Fall O(n log n), da die Liste wiederholt in zwei Hälften geteilt wird (was log n Schritte erfordert) und dann wieder zusammengesetzt wird (was n Schritte erfordert).

Speicherbedarf: Der Speicherbedarf des Merge Sort Algorithmus ist O(n), da zusätzlicher Speicher für die Zwischenlisten während des Teilens und Zusammenfügens der Listen verwendet wird.

b)

Nachdem die Liste L sortiert wurde, soll die Zahl 32 mit dem Binary Search Algorithmus gesucht werden. Zeige alle Zwischenschritte auf, die beim Suchen gemacht werden. Erläutere die Zeitkomplexität des Binary Search Algorithmus.

  def binary_search(arr, x):      low = 0      high = len(arr) - 1      mid = 0      while low <= high:          mid = (high + low) // 2          if arr[mid] < x:              low = mid + 1          elif arr[mid] > x:              high = mid - 1          else:              return mid      return -1

Lösung:

Nachdem die Liste L = [34, 7, 23, 32, 5, 62] sortiert wurde, haben wir die sortierte Liste sorted_L = [5, 7, 23, 32, 34, 62]. Jetzt werden wir die Zahl 32 mit dem Binary Search Algorithmus suchen. Der Algorithmus wird wie folgt implementiert und wir zeigen die Zwischenschritte auf:

  def binary_search(arr, x):      low = 0      high = len(arr) - 1      mid = 0      while low <= high:          mid = (high + low) // 2          if arr[mid] < x:              low = mid + 1          elif arr[mid] > x:              high = mid - 1          else:              return mid      return -1

Wir wenden den Binary Search Algorithmus auf die sortierte Liste sorted_L = [5, 7, 23, 32, 34, 62] an, um die Zahl 32 zu finden:

• Schritt 1: Anfangswerte: low = 0, high = 5 (Index der letzten Stelle in der Liste). Berechne mid = (0 + 5) // 2 = 2. Der Wert an Index 2 ist 23. Da 23 < 32, setzen wir low = mid + 1 = 3.
• Schritt 2: Neue Werte: low = 3, high = 5. Berechne mid = (3 + 5) // 2 = 4. Der Wert an Index 4 ist 34. Da 34 > 32, setzen wir high = mid - 1 = 3.
• Schritt 3: Neue Werte: low = 3, high = 3. Berechne mid = (3 + 3) // 2 = 3. Der Wert an Index 3 ist 32. Da 32 == 32, haben wir die gesuchte Zahl gefunden und der Algorithmus gibt den Index 3 zurück.

Die gesuchte Zahl 32 befindet sich an Index 3 in der sortierten Liste.

Zeitkomplexität: Die Zeitkomplexität des Binary Search Algorithmus beträgt O(log n), da die Liste in jedem Schritt halbiert wird, was eine logarithmische Anzahl von Schritten in Bezug auf die Größe der Liste erfordert.

Aufgabe 4)

Dein Chef hat Dich gebeten, ein Programm zu analysieren, das die Laufzeiten von verschiedenen Sortieralgorithmen vergleicht. Zwei der Algorithmen, die analysiert werden sollen, sind der Bubble-Sort und der Merge-Sort. Beide Sortieralgorithmen sollen auf eine Liste mit n Zahlen angewendet werden. Du musst die Laufzeiten dieser Algorithmen in der Big-O-Notation darstellen. Die Analyse soll sowohl den Average-Case als auch den Worst-Case für beide Algorithmen umfassen, und Du sollst auch eine kurze Begründung für Deine Ergebnisse liefern.

a)

Berechne und notiere die Big-O-Notation für die Average-Case und Worst-Case Laufzeit von Bubble-Sort. Erkläre kurz, warum die jeweilige Laufzeit so berechnet wird.

Lösung:

Um die Big-O-Notation für die Average-Case und Worst-Case Laufzeiten von Bubble-Sort zu berechnen, lass uns zunächst erklären, wie der Bubble-Sort Algorithmus funktioniert.

• Bubble-Sort Algorithmus: Der Bubble-Sort Algorithmus vergleicht wiederholt benachbarte Elemente einer Liste und vertauscht sie, falls sie in der falschen Reihenfolge sind. Dieser Prozess wird so lange wiederholt, bis die Liste vollständig sortiert ist.

Schauen wir uns die Laufzeiten im Detail an:

• Average-Case Laufzeit: Die Average-Case Laufzeit für Bubble-Sort ist \(O(n^2)\). Dies liegt daran, dass im Durchschnitt jedes Element mit jedem anderen Element verglichen werden muss. Der Algorithmus enthält zwei verschachtelte Schleifen: die äußere Schleife läuft \(n\) Mal, und die innere Schleife läuft im Durchschnitt auch \(n\) Mal. Daher beträgt die Gesamtlaufzeit im Durchschnitt \(n \times n = n^2\).
• Worst-Case Laufzeit: Die Worst-Case Laufzeit für Bubble-Sort ist ebenfalls \(O(n^2)\). Im schlimmsten Fall ist die Liste in umgekehrter Reihenfolge sortiert. In diesem Fall müsste jedes Element bei jedem Durchgang bis ans Ende der Liste verschoben werden. Auch hier laufen die beiden Schleifen jeweils \(n\) Mal, was zu einer Laufzeit von \(n \times n = n^2\) führt.

Zusammenfassend:

• Average-Case Laufzeit: \(O(n^2)\)
• Worst-Case Laufzeit: \(O(n^2)\)

Die quadratische Laufzeit ergibt sich daraus, dass der Bubble-Sort Algorithmus in beiden Fällen die Liste systematisch durchläuft und dabei jedes Element mit allen anderen Elementen vergleicht und gegebenenfalls vertauscht.

b)

Berechne und notiere die Big-O-Notation für die Average-Case und Worst-Case Laufzeit von Merge-Sort. Erkläre kurz, warum die jeweilige Laufzeit so berechnet wird.

Lösung:

Um die Big-O-Notation für die Average-Case und Worst-Case Laufzeiten von Merge-Sort zu berechnen, lass uns kurz erklären, wie der Merge-Sort Algorithmus funktioniert.

• Merge-Sort Algorithmus: Merge-Sort ist ein rekursiver Divide-and-Conquer-Algorithmus, der eine Liste in kleinere Teillisten aufteilt, diese sortiert und anschließend wieder zusammensetzt. Der Algorithmus besteht hauptsächlich aus zwei Phasen: der Teilphase, in der die Liste kontinuierlich in kleinere Hälften zerlegt wird, und der Merge-Phase, in der die sortierten Teillisten wieder zusammengemischt werden.

Schauen wir uns die Laufzeiten im Detail an:

• Average-Case Laufzeit: Die Average-Case Laufzeit für Merge-Sort ist \(O(n \log n)\). Der Grund hierfür ist, dass der Algorithmus die Liste in etwa \(\log n\) Schritte unterteilt (da die Liste immer wieder halbiert wird), und in jedem Schritt werden die Elemente der Liste insgesamt \(n\) Mal verglichen und zusammengeführt. Dies führt zu einer Laufzeit von \(n \log n\).
• Worst-Case Laufzeit: Die Worst-Case Laufzeit für Merge-Sort ist ebenfalls \(O(n \log n)\). In jedem Fall wird die Liste unabhängig von ihrer ursprünglichen Reihenfolge immer gleichmäßig geteilt und dann wieder zusammengeführt. Dies bedeutet, dass die Anzahl der Operationen immer proportional zu \(n \log n\) ist.

Zusammenfassend:

• Average-Case Laufzeit: \(O(n \log n)\)
• Worst-Case Laufzeit: \(O(n \log n)\)

Die logarithmische Laufzeit ergibt sich daraus, dass der Merge-Sort Algorithmus die Liste systematisch in kleinere Teile zerlegt und anschließend effizient kombiniert, was sowohl im Durchschnitt als auch im schlimmsten Fall zu einer optimalen Laufzeit führt.