Algorithmen und Datenstrukturen at Hochschule Weserbergland

• Eine Datenstruktur ist eine bestimmte Art, Daten zu verwalten und miteinander zu verknüpfen, um in geeigneter Weise auf diese zugreifen und diese manipulieren zu können 

- Die Mechanismen der erlaubten Operationen (Einfügen, Löschen, Ändern) sind Teil der Struktur! 

• Einfache Beispiele 

- Listen 

- Arrays

Computer werden zwar immer schneller und Speicher immer größer und billiger, aber 

• Geschwindigkeit und Speicher werden immer begrenzt sein 

• Die Problemstellungen werden immer komplexer 

• Die Datenmengen werden immer umfangreicher 

Daher muss auch heute mit den Ressourcen Zeit und Speicher geschickt umgegangen werden.

• Das wichtigste Maß für die Geschwindigkeit von Algorithmen nennt man ihre Zeitkomplexität 

   - Dabei geht es nicht um exakte Aussagen, sondern nur um Größenordnungen. Man gibt an, wie sich die Laufzeit eines Algorithmus ändert, wenn sich das Datenvolumen ändert 

• Platzbedarf 

   - Ebenso wie der Zeitbedarf lässt sich der Platzbedarf eines Algorithmus messen. Dieses Maß nennt man die Speicherplatzkomplexität eines Algorithmus.

Mit Hilfe der O-Notation kann eine Abschätzung des Zeitverhaltens von Algorithmen abgegeben werden. Dabei werden bei Die Laufzeitfunktionen (z.B. 17 n² + 155 n + 3.157 ) vereinfacht durch:

• Vereinheitlichen durch Bilden oberer Schranke
• Weglassen von Summanden niedriger Ordnung
• Ignorieren von Konstanten

für das obige Beispiel also O(n²).

• Synonym: Sequenz, Liste 

• Eigenschaften 

   - Besitzt eine Länge, die durch die Anzahl Elemente in der Folge bestimmt ist 

   - Elemente der Folge haben den gleichen Grundtyp 

   - Elemente der Folge haben eine Ordnung 

- Vorgänger, Nachfolger 

- Duplikate erlaubt

•  Grundlage zur Implementierung •
•  Einfach oder doppelt verkettete Liste 
• • Array

• Stack: Stapel 

   • Fixierung auf „oberstes“ Element 

   • Nur dieses sichtbar 

   • Nur dieses entnehmbar 

   • Einfügen eines neuen Elementes durch „darauf legen“ 

➢ LIFO – Struktur (last-in-first-out). 

   - Anwendungsfall: z.B. invertieren von Listen

• Queue: (Warte-)Schlange 

   • Entnahme von Elementen nur an einem Ende („vorne“) 

   • Anhängen von Elementen nur am anderen Ende („hinten“) 

   ➢ FIFO – Struktur (first-in-first-out).

   - Anwendungsfall: z.B. Druckerwarteschlange

• Sequenzieller Durchlauf aller Listenelemente, beginnend mit dem ersten 

• Wird auch lineare Suche bezeichnet 

• Anzahl der Suchdurchläufe (die Liste habe die Länge n): 

• im besten Fall: 1 

• im schlechtesten Fall: n 

• durchschnittlich bei erfolgreicher Suche: n/2 

• bei erfolgloser Suche: n

• Schritte 

1. Wähle den mittleren Eintrag und prüfe, ob gesuchter Wert in der ersten oder der zweiten Hälfte der Folge ist 

2. Fahre analog 1. mit der Hälfte fort, in der sich der Eintrag befindet 

(Ende, wenn entweder der Eintrag gefunden oder wenn der Suchbereich keine Elemente mehr enthält) 

Aufwand = Anzahl der benötigten Schleifendurchläufe bis Element gefunden.

• Aufwand (n sei wiederum die Länge der Liste) 

• Im besten Fall: 1 

• Im schlechtesten Fall: log2 n 

➢ Finden des Elements erst „ganz am Schluss“ bzw. Element nicht in Liste 

• Nach dem ersten Teilen der Folge bleiben noch n/2 Elemente, nach dem zweiten Schritt noch n/4, nachdem dritten noch n/8 usw. 

• Allgemein: im i-ten Durchlauf sind maximal n/(2i) Elemente zu durchsuchen 

• Entsprechend werden log2 n Schritte benötigt 

• Im durchschnittlichen Fall: 0,5 * log2 n

• Menge von Knoten, die untereinander „verzeigert“ sind 

• Ohne explizite Position • Jeder Knoten besitzt Verweis auf Nachfolgerknoten sowie das zu speichernde Element 

• Listenkopf: spezieller Knoten head ohne Inhalt, nur Zeiger

• Listenende: null-Zeiger.

1. Einfügeposition suchen 

2. Neuen Knoten anlegen 

3. Zeiger vom neuen Knoten auf Knoten an Einfügeposition 

4. Zeiger vom Vorgänger auf neuen Knoten

Rekursive Rückführung eines zu lösenden Problems auf ein identisches Problem mit kleinerer Eingabemenge 

• Zerlege Problem P in Teilprobleme P1 ... Pn 

• Finde Lösungen L1 ... Ln der Teilprobleme 

• Setze Lösung L von P als Kombination aus L1 ... Ln zusammen

• Spezifikation 

− Eingabespezifikation: Eingabegrößen 

− Ausgabespezifikation: Ausgabegröße 

• Durchführbarkeit 

− Endliche Beschreibung: Verfahren muss vollständig beschrieben sein 

− Effektivität: jeder Schritt muss effektiv ausführbar sein 

− Determiniertheit: bei jeder Ausführung für gleiche Eingabewerte auch immer die selben Ausgabewerte 

• Korrektheit 

− Partielle Korrektheit: jedes berechnete Ergebnis genügt der Ausgabespezifikation, sofern die Eingaben der Spezifikation entsprachen (ggf. keine Problemlösung) 

− Terminierung: Halt nach endlich vielen Schritten mit einem Ergebnis, sofern die Eingaben der Spezifikation entsprachen 

=> Wenn beide Bedingungen erfüllt, dann liegt „totale Korrektheit“ vor.