E

v01-Einfuehrung-print1x1

Datenstrukturen

  • Datenstruktur: Methode zur Speicherung und Anordnung von Daten, die eine strukturelle Organisation und den Zugriff auf Datenelemente ermöglicht.

  • Ziel: Die Hauptziele einer Datenstruktur sind die schnelle Auffindbarkeit, Modifizierbarkeit und Effizienz der Datenmanipulation.

  • Abstrakter Datentyp: Definiert die logische Struktur der Daten und die möglichen Operationen, die darauf durchgeführt werden können, unabhängig von der spezifischen Implementierung.

Implementierung

  • Realisierung der Funktionalität: Bezieht sich auf die konkrete Umsetzung der Datenstruktur in einer Programmiersprache. Es umfasst die Optimierung von Zeit- und Speicherkomplexität, um die Effizienz zu maximieren.

Fragestellungen

  • Wie sind die Daten gespeichert?: Die Speicherung kann verschiedene Formate annehmen, z.B. Arrays, verkettete Listen oder Bäume.

  • Wie werden die Operationen realisiert?: Berücksichtigt die Implementierung von grundlegenden Operationen wie Einfügen, Löschen und Suchen von Elementen.

Algorithmen

  • Algorithmus: Eine präzise Verfahrensvorschrift, die eine Sequenz von Anweisungen beschreibt, um eine bestimmte Ausgabe aus gegebenen Eingaben zu erzeugen.

  • Definition: Die Anweisungen müssen klar und exakt sein, um eine bestimmte Problemklasse zu lösen und die Ausgaben zu optimieren.

Fragestellungen

  • Wie kann man die Effizienz von Algorithmen bewerten und vergleichen?: Es geht um Zeit- und Raumkomplexität sowie um die Analyse der besten, schlechtesten und durchschnittlichen Fälle.

  • Wie implementiert man grundlegende Datenstrukturen und Algorithmen?: Umfasst die Anwendung von Programmiersprachen und Programmiertechniken zur Realisierung der theoretischen Konzepte in praktische Anwendungen.

  • Wie entwirft man Datenstrukturen und Algorithmen?: Berücksichtigt die Analyse des Problems, die Wahl der passenden Datenstruktur und den Entwurf effizienter Algorithmen.

  • Wie beweist man die Korrektheit und Effizienz der Algorithmen?: Methoden wie vollständige Induktion oder die Verwendung von Schleifeninvarianten zur formalen Überprüfung der Funktionsfähigkeit.

Beispiel: Sortierproblem

  • Definition:

    • Eingabe: Eine Folge von n Zahlen (a1, a2, ..., an).

    • Ausgabe: Eine Permutation (a'1, a'2, ..., a'n), sodass (a'1 ≤ a'2 ≤ ... ≤ a'n).

    • Konkretes Beispiel: Eingabe: (31, 41, 59, 26, 41, 58) => Ausgabe: (26, 31, 41, 41, 58, 59).

Sortierproblem - Vorgehensweise

  • Vorgehen: Zwei Hände verwenden; eine bleibt leer, während die andere die Karten aufnimmt und sortiert. Die Karten in der rechten Hand sind immer sortiert.

  • Invariante: Zu jedem Zeitpunkt während des Sortierprozesses sind die Elemente in der rechten Hand korrekt sortiert.

  • Geeignete Datenstruktur: Array.

Sortieralgorithmus: InsertionSort

  • Pseudocode:

    func InsertionSort(A[])
    Feld A[1..1] ist bereits sortiert.
    Durchlauf:
    Für (i ← 2) bis zur Länge von A:
    A[i] in A[1..i−1] einfügen.
    Rückgabe: A.

Offene Fragen nach der Algorithmusfindung

  • Ist der Algorithmus korrekt?: Prüfung der Logik und der Ergebnisse des Algorithmus.

  • Welche Laufzeit hat er?: Analyse der Zeitkomplexität in verschiedenen Szenarien.

  • Wie viel Speicherplatz benötigt er?: Betrachtung der Speicherkomplexität im Hinblick auf die benötigten Ressourcen zur Ausführung des Algorithmus.

Korrektheit

  • Prinzip: Nutzung der Schleifeninvarianz zur Sicherstellung der Korrektheit des Algorithmus.

  • Beweis: Durch vollständige Induktion, die Schritte umfasst: Initialisierung, Aufrechterhaltung und Terminierung der Schleifeninvarianz.

Sortieren durch Einfügen

  • Korrektheit: Nach Abschluss sollte die Funktion bestätigen, dass die Elemente im Feld aufsteigend sortiert sind.

Laufzeit

  • Worst Case: T(n) = O(n^2) bei ungünstigsten Eingabefällen.

  • Best Case: T(n) = O(n) bei bereits sortierten Daten.

  • Average Case: T(n) = O(n^2) bei zufälligen Eingaben.

Speichereinsatz

  • Speicheranforderung: O(n), da In-situ-Umsortierung innerhalb des Eingabefeldes erfolgt, ohne zusätzlichen Speicher zu beanspruchen.

Alternativen zum Sortieren

  • Idee: Teilt den Stapel in zwei Hälften, sortiert diese und verbindet sie anschließend.

  • Ansatz: Divide and Conquer (Teile und herrsche), das Problem in kleinere Instanzen zerlegt und rekursive Lösungen verwendet.

  • Sortieren durch Mischen: MergeSort.

Pseudocode für MergeSort

  • Rekursive Aufteilung und Sortierung der Teilfelder.

Korrektheit von MergeSort

  • Induktionsbeweis: Bestätigung der Funktionsfähigkeit für Felder unterschiedlicher Längen durch Annahme für kürzere Felder.

Laufzeit von MergeSort

  • T(n) = O(n log n), was es effizient hinsichtlich der Zeitkomplexität macht.

Vergleich MergeSort vs. InsertionSort

  • Überlegungen zu den Vor- und Nachteilen der beiden Methoden in Bezug auf Effizienz und Anwendungsbereich.

Literatur

  • Gumm, Sommer: Einführung in die Informatik, 2013.

  • Herold, Lurz, Wohlrab, Hopf: Grundlagen der Informatik, 2017.

  • Sedgewick, Wayne: Algorithmen, 2014.

  • Cormen, Leiserson, Rivest, Stein: Algorithmen, 2013.

  • Knuth: The Art of Computer Programming, 2011.