Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 45

Ein Algorithmus verarbeitet Daten, etwa Kontoführungsdaten oder geometrische Angaben. Ein Datentyp soll gleichartige Daten zusammenfassen und die nötigen Basisoperationen zur Verfügung stellen, wie beispielsweise eine Skalierung oder Rotation bei geometrischen Daten. Was ist nun die passende Abstraktion von derartigen Datentypen, wenn man sie mathematisch exakt definieren möchte?

Datentypen als Algebren

Eine passende mathematische Abstraktion für Datentypen sind Algebren. Eine Algebra ist eine Wertemenge plus Operationen auf diesen Werten. Ein typisches Beispiel für diese Konzept sind die natürlichen Zahlen N mit den Operationen + , −, ·, ÷ etc. Wir betrachten nun den Zusammenhang zwischen Datentypen und Algebren etwas genauer.

Sorten eines Datentyps Mehrsortige Algebren

Wertemengen eines Datentyps werden in der Informatik als Sorten bezeichnet. Die Operationen eines Datentyps entsprechen Funktionen und werden durch Algorithmen realisiert. In der Regel haben wir die Situation einer mehrsortigen Algebra vorliegen, also einer Algebra mit mehreren Sorten als Wertebereiche. Ein Beispiel für eine mehrsortige Algebra sind wiederum die natürlichen Zahlen plus die Wahrheitswerte mit den Operationen + , −, ·, ÷ auf den Zahlen, ¬, ∧, ∨, … auf den Wahrheitswerten und =, <, >, ≤, … als Verbindung zwischen den beiden Sorten.

Die Informatiksichtweise eines Datentyps basiert – im Gegensatz zum auf beliebigen Wertebereichen und Funktionen basierenden mathematischen Konzept der Algebra – auf interpretierbaren Werten mit ausführbaren Operationen – genauer gesagt durch Rechner interpretierbare Wertebereiche und durch Rechner ausführbare Operationen.

In den folgenden Abschnitten werden einige Beschreibungsmethoden für Algebren kurz skizziert, eine genauere Betrachtung erfolgt in Kapitel 11.