Gruppe: 31 Grundlagen wissenschaftlichen Arbeitens Algorithmen und Datenstrukturen Iris Studeny

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