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.
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.
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.
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.
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.
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).
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.
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.
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.
Prinzip: Nutzung der Schleifeninvarianz zur Sicherstellung der Korrektheit des Algorithmus.
Beweis: Durch vollständige Induktion, die Schritte umfasst: Initialisierung, Aufrechterhaltung und Terminierung der Schleifeninvarianz.
Korrektheit: Nach Abschluss sollte die Funktion bestätigen, dass die Elemente im Feld aufsteigend sortiert sind.
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.
Speicheranforderung: O(n), da In-situ-Umsortierung innerhalb des Eingabefeldes erfolgt, ohne zusätzlichen Speicher zu beanspruchen.
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.
Rekursive Aufteilung und Sortierung der Teilfelder.
Induktionsbeweis: Bestätigung der Funktionsfähigkeit für Felder unterschiedlicher Längen durch Annahme für kürzere Felder.
T(n) = O(n log n), was es effizient hinsichtlich der Zeitkomplexität macht.
Überlegungen zu den Vor- und Nachteilen der beiden Methoden in Bezug auf Effizienz und Anwendungsbereich.
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.