Datenstrukturen und Datenabstraktion mit Anwendung

Organisationseinheit
Freie Universität Berlin/Mathematik und Informatik/Institut für Informatik

Bereich

Vertiefungsbereich
Wahlbereich - Teil A

Zugangsvoraussetzungen

Keine

Qualifikationsziele

Die Studentinnen und Studenten können objektorientierte Software entwickeln: Sie beherrschen den Umgang mit Datenabstraktion, Vererbung und polymorphen Typsystemen. Sie sind in der Lage,

abstrakte Datentypen zu spezifizieren und zu implementieren,
Korrektheitsbeweise für die Implementierungen abstrakter Datentypen durchzuführen und
unter Einbeziehung von Effizienzanalysen eine Entscheidung über die jeweils zu wählende Datenrepräsentation zu treffen.

Sie kennen die wichtigsten abstrakten Datentypen und ihre gängigen Implementierungen sowie die entsprechenden Schnittstellen und Klassen aus den Bibliotheken der verwendeten Programmiersprache. Sie können eine typische Anwendung selbstständig bearbeiten.

Inhalte

Ausgangspunkt ist das Geheimnisprinzip und seine Bedeutung für die Strukturierung von Programmen und die Konstruktion von Datenobjekten mittels Modulen und Klassen. Eine zentrale Rolle bei der Modellierung von Daten spielt der Begriff der Datenabstraktion, verbunden mit der Unterscheidung zwischen Spezifikation und Implementierung abstrakter Datenobjekte und Datentypen. Folgen, Mengen, Relationen, Bäume, Graphen und geometrische Objekte werden als abstrakte Typen eingeführt. Anschließend werden effizient manipulierbare Repräsentationen dieser Typen betrachtet und die zugehörigen Algorithmen auf ihre Komplexität hin untersucht. In der objektorientierten Programmierung spielen neben der Datenabstraktion Vererbung und Polymorphie eine wesentliche Rolle. Abstrakte Datentypen werden daher häufig unter Verwendung von Vererbungsmechanismen spezifiziert und implementiert. Für typische Problemlösungen lassen sich Entwurfsmuster angeben; die Behandlung der Muster Iterator, Kompositum, Abstrakte Fabrik bietet sich an. Technische Aspekte der Datenspeicherung im Arbeitsspeicher (Keller und Halde) und im Hintergrundspeicher (Dateien, persistente Objekte) werden behandelt. Programmiert wird sowohl in objektorientierten als auch in funktionalen Sprachen.

Lehr- und Lernformen

Aktive Teilnahme

Vorlesung
4 SWS
Teilnahme empfohlen

Schriftliche Bearbeitung der Übungsblätter, zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung, Bearbeitung einer anwendungsorientierten Aufgabe einschließlich einer lauffähigen Implementierung

Übung
2 SWS
verpflichtete Teilnahme

Schriftliche Bearbeitung der Übungsblätter, zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung, Bearbeitung einer anwendungsorientierten Aufgabe einschließlich einer lauffähigen Implementierung

Aufwand

Präsenzzeit Vorlesung	60 Stunden
Vor- und Nachbereitung Vorlesung	60 Stunden
Präsenzzeit Übung	30 Stunden
Vor- und Nachbereitung Übung	60 Stunden
Bearbeitung Anwendung	60 Stunden
Prüfungsvorbereitung und Prüfung	30 Stunden

Modulprüfung
Klausur (120 Minuten)

Differenzierte Bewertung
differenzierte Bewertung

Modulsprache
Deutsch

Arbeitsaufwand (Stunden)
300

Leistungspunkte (LP)
10

Dauer des Moduls
Ein Semester

Häufigkeit des Angebots
Jedes Wintersemester

Verwendbarkeit

Bachelorstudiengang Mathematik