Qualifikationsziele: Die Studentinnen und Studenten können objektorientierte Software entwickeln: sie beherrschen den Umgang mit Datenabstraktion, Vererbung und polymorphen Typsystemen und sind in der Lage, abstrakte Datentypen zu spezi- fizieren und zu implementieren, Korrektheitsbeweise für die Implementierungen abstrakter Datentypen durchzufüh- ren und unter Einbeziehung von Effizienzanalysen eine Entscheidung über die jeweils zu wählende Datenrepräsen- tation 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.

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 Implemen- tierung 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.