Definitionen der Algebra, Ordnungsrelationen und Verbände

Eine Algebra ist eine Struktur der Form
wobei M eine Menge von Objekten (Zahlen, Buchstaben, Programmteile) und O eine Menge von Operationen, die auf M definiert sind.

Eine Algebra
bei der jede Anwendung einer Operation aus O wieder ein Element der Grundmenge M liefert, heißt universale oder universelle Algebra.

Wenn zwischen x und y eine gewisse Verbindung besteht, wird das x steht in Relation zu y genannt. Beschrieben wird das durch xRy.

Klassifikation von Datentypen

Daten sind alle Arten von Zeichenketten für die Mitteilungen bzw. Speicherung von Informationen, die von einem Computer verarbeitet werden können.

Ein Datentyp T ist eine spezielle Algebra <W,O>, bestehend aus einer endlichen Menge (Wertemenge, Trägermenge) von Werten (Daten) und auf diesen zulässigen Operationen.

Diese Algebra muss nicht universell sein, d.h., es ist durchaus möglich, aus Elementen von W mithilfe von Operationen aus O neue Elemente, die zuvor nicht in W vorhanden waren, zu konstuieren. Ist der Datentyp im obrigen Sinne eine universelle Algebra, so spricht man auch von einem universellen Datentyp, andernfalls von einem mehrsortigen Datentyp. Ein Beispiel für einen einfachen, auch Basisdatentyp genannt, sind etwa die ganzen Zahlen, versehen mit den Rechenarten Addition oder Multiplikation. Komplexe Datentypen sind beispielsweise Stapel oder Array.

Die Beschreibung eines Datentyps besteht aus zwei Teilen.

• Dem syntaktischen Teil, auch Signatur genannt, in dem vor allem die Bezeichnung festgelegt werden.
• Dem semantischen Teil, in dem die Definition der Trägermengen und der Operatoren vorgenommen werden.

Als Beispiel für die Definition eines abstrakten Datentypen "Stapel".



Bei komplexen Datentypen kann man natürlich verschiedene Implementierungen eines Datentyps wählen, die jedoch alle - das ist Bedingung - der gleichen algebraischen Spezifikation genügen. Nun würde es wenig Sinn machen,  für jede mögliche Implementierung einen eigenen Datentypen zu definieren. Vielmehr sollte es so sein, das zwei Typen nur dann zu unterschieden sind, wenn sie bei indentischen Input unterschiedlichen Output erzeugen.

Zwei Datentypen heißen äquivalent, wenn sie die gleichen Signaturen haben und das gleiche äußere Verhalten aufweisen. Eine bezüglich dieser Äquivalenzrelation gebildete Aquivalenzklasse nennt man einen abstrakten Datentypen (ADT). Zwei Datentypen sind äquivalent (und damit Repräsentanten des gleichen ADT), wenn der Benutzer keinen Unterschied zwischen ihnen feststellen kann.

Die Beschreibung eines ADT kann durch eine sehr "abgespeckte" Spezifikation erfolgen, was im Allgemeinen die Übersichtlichkeit eines Programmes erhöht. So kann man z.B. zuerst spezifizieren, was der Datentyp leisten soll und darauf das weitere Programm aufbauen. Die Implementierung kann sich das problemlos von Version zu Version ändern, ohne das man die Teile des Programms, die auf die Datenstruktur zugreifen, modifizieren muss. Im Allgemeinen muss - eben weil es ein abstrakter Datentyp ist - auf die interne Arbeitsweise der Operationen keine Interesse liegen.

Die Realisierung der Objektmengen eines ADTs mittels einer Programmiersprache nennt man Datenstruktur. Diese Realisierung kann beispielsweise mittels einer Kollektion von Variablen verschiedener Datentypen erfolgen.

Die erste Fundamentale Klassifikation besteht darin, zwischen linearen und nichtlinearen Datentypen zu unterscheiden.

Lineare Datenstrukturen sind solche, bei denen die einzelnen Elemente streng geordnet sind. Man also stehts sofort sagen kann, welches Element das "nächste" ist. Ein Vertreter dieser Art von Datenstruktur ist ein Array.

Nicht lineare Datenstrukturen sind solche, bei denen es eben keine, eine nicht strenge Ordnung existiert. Ein Vertreter sind Bäume oder Graphen.

Lineare Datentypen unterteilen sich noch einmal in verschiedene Untertypen. Folgend eine schematische Darstellung.

• Lineare
  Die Elemente sind streng nacheinander geordnet.
  
• Statische
  Ihre Größe und damit der belegte Speicherplatz steht bereits zu Beginn fest.
  
• Basis
  Zeichnen sich durch ihre Unteilbarkeit (Atomar) aus. Sie sind meist fest im Betriebssystem verankert.
  Beispiele: Boolean, Integer, Float, Character
  
• Aggregierte
  Zusammenfassung von statischen Datentypen. Wird auch strukturierter Datentyp genannt. Hier wird noch einmal nach verschiedenen Varianten unterschieden, die sich in der Art der Zusammenfassung unterscheiden. Zusammenfassungen gleichen Typs Array und Set/Enum oder Zusammenfassung unterschiedlichen Types Record/Structure. [Feld (Array), Verbund (Record, Structure), Menge (Set, Enum)]
• Dynamische
  Ihre Größe steht zu Beginn noch nicht fest. Die einzelnen Elemente können frei über dem Computerspeicher verteilt sein. Die Beziehung zueinander werden durch Zeiger (Pointer) hergestellt. Die physikalische Position hat keinen Zusammenhang zu der logischen Position innerhalb. Dennoch sind Vertreter dieser Gattung logisch lineare Datentypen. Zu ihnen gehören vorallem die verkettete Liste, Stack (Last-In-First-Out) und Queue (First-In-First-Out).
• Nichtlineare
  Die Elemente müssen nicht streng geordnet sein. Die Elemente können logisch quasi "nebeneinander", auf gleicher Ebene existieren. Sie haben nicht nur einen Nachfolger, sondern können mehrere haben.
  
• Bäume
  Hat mehrere - allerdings stehts nur endlich viele - Nachfolger. Ein Element zeichnet sich dadurch aus, dass es keine Vorgänger hat und wird Wurzel des Baumer genannt. Die Elemente eines Baumes werden Knoten genannt. Knoten die keinen Nachfolger haben, werden Blätter genannt. Die Verbindungen zwischen Knoten, z.B. Vater(knoten) und Sohn(knoten) werden Kante genannt. Der Abstand, also die Schritte von Knoten A bis Konten Z wird Pfad genannt. Die Länge des Pfades von der Wurzel zu einem Knoten nennt man auch das Niveau oder die Tiefe des Knotens.
  
• Geordnetet Baum
  Ordnet man die Knoten innerhalb eines Niveaus so an, dass man von zwei beliebigen Knoten sofort sagen kann welcher "vor" dem anderen (Vater-Sohn-Beziehung) kommt, so spricht man von streng geordneten Bäumen.
• Vollständiger Baum
  Ein Baum heißt vollständig, wenn er auf jedem Niveau die größtmögliche Knotenzahl hat und wenn alle seine Blätter dieselbe Tiefe haben.
  
• Binäre Bäume
  Binärbaum ist ein geordneter Baum der Ordnung 2. D.h. ein Baum ist ein Binärbaum, wenn jeder seiner Knoten keinen, einen oder zwei Nachfolger hat.Häufig finden binäre Bäume bei Such- und Sortieralgorithmen nach der "Divide and conquer"-Technik Anwendung.
  
     
• Graphen
  Ist eine weitere Verallgemeinerung des Baumes mit dem Unterschied, dass es keinen Wurzelknoten meht gibt und Kanten zwischen beliebigen Knoten vorhanden sein können. Zudem können wir von gerichteten und ungerichteten Graphen sprechen. Bei einem gerichteten Graphen ist jede Kanta zwischen zwei Knoten zusätzlich mit einer Richtung (Pfeil) versehen. Dadurch das wir, wie gerade beschrieben, quasi von Knoten zu Knnoten "gehen" können stellt sich die Frage, ob ein solcher durchlaufender Weg zum Ausgangspunkt zurückführen kann. Ja, wenn dies passiert spricht man von einem zyklischen Graphen.
  
  
  

Adjazenzmatrizen

Eine Adjazenzmatrix ist ein effizientes Mittel zur Abspeicherung eines Graphen. Es transformiert eine grafische durch Knoten und Pfeile visualierte Figur zu einer Matrix die Nullen und Einsen enthält. Und das geht so: Wir nummerieren die Knoten des zu behandelnden Graphen G durch und nennen sie V1,...,Vn. Nun definieren wir eine Menge von n² Zahlen durch die folgende Vorschrift: Gibt es in G eine Kante (Pfeil) von Vi nach Vj' setzen wir Cij =1, gibt es keine solche Kante, setzten wir Cij =0.

Beispiel: Steht in der zweiten Zeile, erste Spalte, eine Eins, da es einen Pfeil von V2 nach V1 gibt, wohingegen das Matrixelement C34 null ist, da es eben von V3 nach V4 keine (direkte) Verbindung gibt.