Gruppe: 3 1
Grundlagen wissenschaftlichen Arbeitens
Algorithmen und Datenstrukturen
Iris Studeny
Gruppe: 3 2
Algorithmen und Datenstrukturen
• Vorstellung• Sichtweisen: Benutzer – Programmierer• Mögliche Datenstrukturen und ihre Vielfalt –
Schlitzkarten• Einfache Datenstrukturen und
Zugriffsalgorithmen• Rechenmodelle und Komplexität• Datenstrukturtypen• Zusammenspiel von Algorithmus und
Datenstruktur
Gruppe: 3 3
Benutzer kontra Programmierer
• Zwei unterschiedliche Sichtweisen:– Benutzer: Daten und Operationen– Programmierer: Datenstrukturen und
Algorithmen
Gruppe: 3 4
Mögliche Datenstrukturen und ihre Vielfalt
• Bsp. Schlitzkarten
Gruppe: 3 5
Mögliche Datenstrukturen und ihre Vielfalt
• Lösungsansätze für Kreuzworträtsel– Backtrack-Algorithmus– Expertensystem
Gruppe: 3 6
Einfache Datenstrukturen und Zugriffsalgorithmen
• Stapel:– Datentyp und Implementierung– Der Stapel als Hochseil für
Algorithmenakrobatik
• Warteschlange
• Wörterbuch
Gruppe: 3 7
Rechenmodelle und Komplexität
• Speicher mit Direktzugriff
• Probleminstanzen, Problemklassen und Asymptotik
• Schranken:– Untere Schranken– Obere Schranken
• Problemreduktion
Gruppe: 3 8
Datenstrukturtypen
• Implizite Datenstrukturen, Adressberechnung
• Die Vorrangschlange, als Heap implementiert
• Hashing
• Verkettete Listen
Gruppe: 3 9
Zusammenspiel von Algorithmus und Datenstruktur
• Heapsort: Datenstruktur führt zum Algorithmus
• Plane-sweep, Warteschlange, Wörterbuch
Gruppe: 3 10
Warteschlange
Gruppe: 3 11
Warteschlange
Gruppe: 3 12
Wörterbuch
• Wachstum ist abhängig von– Struktur des Wertebereiches der Einträge– Anzahl der erlaubten Abfragen– Statisches oder dynamisches Wörerbuch
• Grundlegende Operationen:– data is_member(key k)– insert(data d, key k)– data delete(key k)
Gruppe: 3 13
Heapsort
k1
k2
k7
k8
k3
k6k5k4
Gruppe: 3 14
Heapsort
8
6
2
1
7
543
Gruppe: 3 15
Vielen Dank für Ihre Aufmerksamkeit