WS 97/98 - Inhalt Algorithmen und Programmierung III

Modula: Definitions- und Implementierungs-Modul, getennte Übersetzung, Binden; lokale Module . Beispiel Schlange, Beispiel Bibliotheksmodule. Begriffe: Schnittstelle, Geheimnisprinzip.

Beispiel Schlange. Abstraktes Datenobjekt, abstrakter Datentyp. Schnittstelle, Spezifikation, Implementierung. Module als Objektverwalter. Klassen, Prototypen versus Klassen. Generizität. Modulbasierte versus klassenbasierte Programmierung. Datenabstraktion in Miranda.

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

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

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

Laufzeit- versus Speicherkomplexität, Wiederholung O-Notation (ALP II). Beispiel lineare Repräsentationen von Mengen.

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, Tiefensuche vs. Breitensuche; 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. Datenbanken: Relationales Datenmodell, Schema-Architektur, Anfragen, Repräsentation. Objektorientierte Datenbanken.

Lehre