WS 98/99 - Inhalt Algorithmen und Programmierung III

Java: Klasse, Paket. Modula: Definitions- und Implementierungs-Modul. Getrennte Übersetzung, Binden, Laden. Bibliotheksklassen/module. Kernbegriffe: Modulare Struktur, Schnittstelle, Geheimnisprinzip.

Beispiel Schlange. Abstraktes Datenobjekt, abstrakter Datentyp. Schnittstelle versus Klasse. Module als Objektverwalter. Modulbasierte versus klassenbasierte Programmierung. Datenabstraktion in Haskell.

Schnittstellentyp, alternative Implementierungen für eine Schnittstelle. Polymorphe Typsysteme. Vererbung als Erweiterung von Schnittstelle oder Implementierung, abstrakte Klassen. Typklassen in Haskell.

Spezifikation versus Implementierung, Verifikation. Informelle, formale und formalsprachliche Spezifikation. Spezifikation modellierend, algebraisch, mit Haskell.

Datenrepräsentation und zugehörige Algorithmen. Abstraktionsfunktion, abstrakte und konkrete Invariante. Korrektheit von Repräsentation und Algorithmen (Pre/Postconditions). Behandlung von Ausnahmen.

Verbunde, Felder, Listen; Keller, dynamische Speicherverwaltung, Entrekursivierung, Auswertung arithmetischer Ausdrücke; Schlangen; einschlägige Vererbungshierarchien. Manipulation von Zeichenketten.

Alternative Modelle für Bäume. Beispiele für Baumstrukturen. Repräsentation: Feld, Geflecht. Traversieren, Tiefendurchlauf vs. Breitendurchlauf; iteratives Traversieren.

Repräsentation: linear sortiert/unsortiert, Bitfeld, Streuspeicherung, Suchbäume (AVL, B, B*, ISAM), Heap. Prioritätsschlangen. Mengen von Folgen (trie). Relationen; Indexe.

Modellierung, Anwendungen. Operationen auf Graphen. Graphalgorithmen: einfaches Suchen, Traversieren; Algorithmen von Dijkstra, Warshall, Kruskal. Repräsentation: Geflechte, Adjazenzmatrix/listen.

Modellierung und Repräsentation. Schnittprobleme, Maßproblem.

Backtracking, Divide&Conquer, Greedy, Branch&Bound, Plane Sweep.

Statische vs. dynamische Speicherverwaltung, Keller und Halde. Haldenverwaltung, Fragmentierung, Kompaktifizierung. Explizite Speicherfreigabe vs. automatische Speicherbereinigung; Verweiszähler, Mark&Sweep.

Persistenz. Dateien: Modelle, Operationen, Repräsentation. Vorschau auf Datenbanken: Relationales Datenmodell, Schema-Architektur, Anfragen, Repräsentation. Objektorientierte Datenbanken.

Lehre