Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Abstrakte Datentypen - Einführung
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 145 Zeilen
- Abstrakte Datentype. Wir beginnen mit der Einführung des zentralen Begriffs für abstrakte Datentypen, nämlich der Abstraktion. Ein zentrales Paradigma bei
- der Entwicklung äh und Anwendung von allgemeinen Algorithmen und Datenstrukturen. Es geht hier darum, dass man ä den Kern von etwas äh
- extrahiert. ähm insbesondere indem man äh es hervorhebt durch äh Aufmerksamkeit, die sogenannte Aception oder durch das Festhalten von
- bestimmten Merkmalen, die dieses äh Ding, in unserem Fall den Algorithmus, die Datenstruktur besonders kennzeichnen. Auf der anderen Seite
- bedeutet es natürlich auch, dass gewisse Dinge vernachlässigt werden müssen, nämlich die Dinge, die eben nicht zum Kern gehören und vielleicht deswegen
- nicht so wichtig sind. Und die Herausforderung ist da natürlich jeweils diese Unterscheidung zu treffen. Was ist zentral? Was muss ich mit in die
- Abstraktion aufnehmen und was kann ich weglassen in einer abstrakten Darstellung? Und darauf baut dann direkt dieses
- Konzept, mit dem wir uns hier intensiv beschäftigen wollen, dem abstrakten Datentyp auf. Das heißt, wir definieren den Datentyp durch seine zentralen
- Eigenschaften. Ich mache das mal am Beispiel der Objektorientierung. Hier wissen wir, dass konkrete Beispiele der Strukturen als Instanzen oder Objekte
- repräsentiert werden. Und auf der anderen Seite haben wir die Klasse als Bauplan, die beschreibt, wie diese Instanzen oder Objekte aussehen. Auf der
- einen Seite, das wären die Objektvariablen oder auf der anderen Seite natürlich auch sich verhalten. Das wären dann die Methoden. Und ganz
- allgemein wollen wir jetzt also Datentypen beschreiben, indem wir ihre Eigenschaften angeben und zwar diese Eigenschaften, die dann jede mögliche
- Implementierung dieses Datentyps auch äh erfüllen soll. Auf der anderen Seite geben wir aber die konkrete Implementierung nicht an. Wie machen wir
- das? Wir beschreiben Wertemengen und dann Operationen auf diesen Wertemengen und zwar auf eine möglichst formale allgemeine Art und
- Weise. Und äh das bedeutet äh diese abstrakten Datentypen, die wir hier betrachten werden, setzen wir aus genau diesen beiden Bausteinen zusammen. Die
- Objektmengen sind entweder Wertebereiche und oder Wertemengen und auf der anderen Seite Operationen können auch als Funktionen oder Methoden ähm sich
- vorgestellt werden und die wiederum setzen sich zusammen aus einer Signatur. Das heißt, was stecken wir rein, was kommt raus, erstmal ganz allgemein und
- dann einer Semantik. Was sollen diese Operationen denn dann ganz konkret machen? Welche Wertemengen bilden Sie auf welche anderen Wertemengen ab und
- welche Eigenschaften hat beispielsweise die Eingabe und die Ausgabe? Um noch mal ganz klar zu sagen, das Ganze soll unabhängig sein von einer konkreten
- Programmiersprache, einer Implementierung. Ganz im Gegenteil, der gleiche abstrakte Datentyp soll sich dann mit unterschiedlichsten
- Programmiersprachen umsetzen lassen. Gucken wir uns das mal ein bisschen konkreter an. Ich habe hier mal
- drei Abstraktionsebenen festgelegt für einen abstrakten Datentyp und dann vielleicht auch konkrete Umsetzungen. Auf der höchsten Abstraktionsebene haben
- wir den abstrakten Datentyp, also das, was wir hier betrachten wollen als Beispiel Integer, also die Repräsentation einer Ganzzahl. Wenn wir
- etwas konkreter werden, dann sind wir auf der Ebene der Implementierung. Das könnte z.B. bedeuten, dass wir diesen Integer als eine 32 Bitzahl
- repräsentieren. Damit haben wir schon mal festgelegt, wie diese Zahl im Speicher abgelegt werden soll. Und in der dritten Ebene könnten wir hingehen
- und sagen, wir gucken uns jetzt eine ganz konkretes konkrete Instanz oder Objekt an. in diesem Fall hier nicht in im objektorientierten Sinne. Da sagen
- wir, wir haben jetzt eine Variable I von diesem Typ Integer und die hat vielleicht den Wert 5. Das ist dann natürlich Programmiersprachen abhängig,
- Plattformabhängig. Da haben wir diese Abstraktion des abstrakten Datentyps schon weit verlassen. Und wie wollen wir das jetzt
- machen? Ähm, wir gucken uns hier äh die Object Constraint Language, eine ähm Modellierungssprache, die Teil äh der UML, der Unified Modelling Language ist.
- Und äh wir werden uns nicht vollständig daran orientieren, aber die Konzepte, die ich hier in dieser Vorlesung verwende, die bauen schon auf dem, was
- in der OCL einmal vorgegeben war. Das handelt sich also hier um eine Sprache, die die Randbedingung ähm bei der Modellierung von Computerprogrammen
- allgemein formal festlegen kann. Wir interessieren uns hier für den Unterbereich der abstrakten Datentypen. Wir lehnen uns an, indem wir ähm dann
- Operationen definieren über zum einen Vorbedingungen, was erwarten wir, was reingesteckt wird in eine Operation und Nachbedingungen, was soll die Operation
- dann sicherstellen für das, was an Daten zurückgegeben wird. Wir gucken uns da eine Reihe von Bestandteilen an, die ich hier schon einmal vorher aufgeführt habe
- und die in den weiteren Folien schrittweise eingeführt werden. Wir haben also das Schlüsselwort Operation, wir haben den
- Kreuzoperator, wir haben diesen Pfeile für eine Abbildung, wir haben vor Nachbedingungen mit Free und Post, wir haben Eingabedaten mit In, wir haben
- Rückgabedaten mit Inout und dann eine Kombination für Variablen für Daten, die sowohl Teil der Eingabe sind als auch noch in der Ausgabe enthalten sind. Und
- dann haben wir hier die leere Menge, die wir dann brauchen, wenn wir Objekte generieren oder auch später wieder zerstören
- wollen. Fangen wir vorne an mit den Vorbedingungen. Sie kennen das vielleicht schon aus vorangegangenen Programmierveranstaltungen. Mit einer
- Vorbedingung formulieren wir Eigenschaften, die wir an die Eingabe erwarten. Und zwar muss die Eingabe vielleicht auf eine gewisse
- Art und Weise strukturiert sein oder gewisse Anforderungen erfüllen, dass überhaupt die Operation fehlerfrei anwendbar ist. Und wer immer jetzt einen
- solchen abstrakten Datentyp verwenden möchte, der muss sicherstellen, dass diese Eigenschaften erfüllt sind. Das kann man z.B. machen, indem man mit
- sogenannten Asse arbeitet. Das heißt also Bedingungen, die Teil des Codes sind, wo überprüft wird, ob eine Eigenschaft erfüllt ist, ja oder nein.
- Und dann im Fehlerfall entweder das Programm abgebrochen wird oder eine entsprechende Fehlermeldung zurückgegeben wird. Und auf der anderen
- Seite haben wir die Nachbedingungen, die wiederum gibt die Eigenschaften des Objektes nach Beendigung der Operation an. Das heißt, also wir müssen uns
- zunächst äh überlegen, was ist denn die Erwartung an das Ergebnis einer Operation? Wir spezifizieren das wieder möglichst formal in einer mathematischen
- Notation, sodass das Ganze sehr präzise ist und wenig oder gar kein Interpretations Spielraum mehr bietet. Und gleichzeitig haben wir damit eine
- Repräsentation, die sich natürlich leicht in ein Computerprogramm übersetzen lässt. Und damit wären wir auch schon bei den äh Details einer
- solchen äh Nachbedingung ähm bzw. allgemein der Operation, nämlich zunächst mal die Signatur, in der wir sagen, welche Eingabeparameter erwarten
- wir und welche Ausgabe Parameter erwarten wir. Und dazwischen verwenden wir diese Pfeilnotation, die sowas besagt wie aus den Eingaben wird die
- Ausgabe berechnet. Für beide müssen wir in irgendeiner Weise Wertebereich festlegen, also sowohl für die Eingabe als auch die Ausgabe. Das muss nicht
- notwendigerweise der gleiche Wertbereich sein und wir arbeiten hier auch teilweise schon mit Typen und gehen dabei implizit davon aus, dass etwa die
- aus der Programmierung bekannten Typen einfach hier auch bei abstrakten Datentypen wieder verwendet werden können mit Beispiel von Java,
- insbesondere natürlich die primitiven Datentypen. Wir machen das mal anhand eines Beispiels und das Beispiel soll die Divisionsoperation einer
- Gleitkommazahl oder allgemein von Gleitkommazahlen beschreiben. Wir beginnen also hier mit dem Schlüsselwort Operation oder Englisch Operation und
- geben in dem Fall das Symbol an, das für die Operation verwendet wird hier der geteiltoperator. Und dann haben wir hier im obersten Bereich die Signatur. Da
- beginnen wir damit zu sagen, welche Datentypen, welche Werte sind denn da überhaupt involviert. In dem Fall haben wir zwei Floatwerte, die wir benötigen.
- Dazu verwenden wir dann diesen Kreuzoperator, den X-Operator. Das wäre also die Zahl äh durch die wir teilen wollen und die Zahl, mit der wir teilen
- wollen. Und das Ergebnis ergibt sich dann wieder als eine Gleitkommazahl. Das heißt, dieses Float hier steht dann für das Ergebnis. Und wir erlauben in
- unserer Operation zusätzlich die Möglichkeit, dass ein Fehler auftritt. Und auch diesen Fehler wollen wir irgendwie repräsentieren. Der ist ja
- nicht Teil der Rückgabe, zumindest nicht in unserer Implementierung, sondern wir geben das als einen zusätzlichen Wert an, der in irgendeiner Weise aus der
- Operation herauskommen kann. Konkret sieht es dann so aus. Als Eingabe haben wir diese beiden Werte A und B und die werden abgebildet auf A B. Das ist also
- genau das, was der Divisionsoperator macht. In dem Fall, da wir Fehler arbeiten, einem möglichen Fehler, der zurückgegeben werden kann, äh erfahren
- wir keine Vorbedingung. Das heißt, jeder beliebige Floatwert ist sowohl für den ersten, für das erste als auch für das zweite Argument möglich. Wir haben aber
- eine Nachbedingung. Die Nachbedingung unterscheidet einmal für den gutartigen Fall, wo wir einfach die Divisionen durchbere durchführen können. Der
- Kootient aus A und B wird berechnet mit A ge b und wird zurückgegeben. Das wäre dieser Float Wert hier vorne. Nun kann es aber sein, dass der das zweite
- Argument, dass das B den Wert 0 hat. Sie wissen alle, durch null dürfen wir nicht teilen. Das heißt also, das Ergebnis ist an der Stelle nicht definiert. Wir
- können durch die eigentliche Rückgabe nicht den Fehler kommunizieren. Und dafür verwenden wir jetzt dieses diesen zweiten Wert, den Fehlerwert. Und dem
- weisen wir dann einen entsprechenden konkreten Wert zu irgendeinen Fehlercode, eine Fehlermeldung, vielleicht auch eine Exception, um zu
- kommunizieren, dass hier ein Fehler aufgetreten ist. Ja, als nächsten Punkt betrachten wir noch die Unterscheidung zwischen Werte
- und Referenzsemantik. Auch das haben Sie möglicherweise schon mal in Programmierveranstaltungen gehört. Hier bezieht sich das jetzt auf Parameter
- unserer Operation. Bei der Referenzsemantik haben wir nämlich die Möglichkeit, dass ähm eine Veränderung an einem Parameter auch nach ausführen
- der Operation noch vorhanden ist. Was bedeutet das? Wir gucken uns das wieder an einem kleinen Beispiel an. Wir haben hier eine Operation Einzahlen. Da
- stecken wir einen Betrag rein vom Typ Float. Und dann sehen Sie, wir haben ja einen zweiten Parameter. Dieser Parameter heißt Statuscode und der ist
- vom Typ int und den markieren wir jetzt nicht als Inabe wie der Betrag, sondern als Inout. Das heißt, der also sowohl bei der Eingabe als auch nach Beendigung
- der Operation noch zur Verfügung steht. Was können wir jetzt machen? Wir können mit dem Betrag arbeiten. Wir können z.B. irgendeinen Kontostand aktualisieren,
- basierend auf dem Wert von Betrag. Zusätzlich können wir jetzt einen Wert in die Variable Statuscode hereinschreiben, die dann noch äh der
- dann immer noch vorhanden ist. Die Variable ist vorhanden. Die Variable hat immer noch den Wert, den wir in der Operation vergeben haben, nachdem die
- Operation abgeschlossen ist. Also beispielsweise, wenn hier ein Betrag angegeben wird, der ungültig ist, vielleicht z.B., will, weil sie einen
- negativen Betrag ab eingeben, sie wollen etwas äh abheben, aber sie haben ihr Kredit mit überschritten, dann könnte man mit Hilfe des Statuscodes
- kommunizieren, dass diese diese Einzahlenoperation nicht erfolgreich war und das wäre eine alternative Möglichkeit, um einen Fehler zu
- kommunizieren. gehen immer wieder zurück zu unseren abstrakten Datentypen und da brauchen wir natürlich als Basis etwas, worauf wir arbeiten können, die
- sogenaren, sogenannten atomaren Datentypen, die Sie wie gesagt ja auch schon aus der Java Einführung kennen. Äh, ich habe hier mal als Beispiele
- Wahrheitswerte, ganze Zahlen, reelle Zahlen, Boole int und dann float oder Double. Und die sind natürlich auch mit elementaren Operationen bereit bereits
- ausgestandet ausgestattet. Bei Boolian sind es logische Operatoren wie End oder or. Arbeitz zahlen kann ich die Grundrechenarten anwenden, aber
- vielleicht auch den Absolutwert berechnen. Ich kann Vergleiche machen mit kleiner Größeroperation und bei reellen Zahlen gibt's dann zusätzlich
- vielleicht noch die trigonometrischen Operationen Sinus, Tangens und so weiter. Das heißt also, wir sind hier schon ausgestattet mit einem Grundsatz
- an Dingen, mit dem wir arbeiten können. Wenn wir jetzt aber diese atomaren Datentypen verlassen und eher in eine objektorientierte Repräsentation gehen,
- dann brauchen wir noch zusätzliche Möglichkeiten, denn Objekte können bekannterweise erzeugt werden. Das kennen wir zumindest aus der Javawelt
- mit dem New Operator. Objekte können aber auch zerstört werden. In Java müssen wir uns da nicht drum kümmern. Das macht der Garbage Collector für uns.
- In anderen Programmiersprachen, wie beispielsweise C++, müssen wir uns selber um das Speichermanagement kümmern und insofern auch manuell den Destruktor
- für ein Objekt aufrufen, wenn ich es nicht mehr benötige. Beide Fälle wollen wir in den abstrakten Datentypen mit abbilden. Das heißt, also wir haben hier
- die Operation Ctor für Konstruktor. Da starten wir mit diesem leere Mengesymbol. Das heißt also mit dem aus dem Nichts erzeugen wir ein Objekt vom
- Typ mein Typ. Und genauso bei der Delete der Zerstörungsoperation dem Destruktor, da bekommen wir ein Objekt und durch die Zerstörung wird es zu nichts. Diese
- beiden Ergänzungen brauchen wir also dann, wenn wir mit ähm mit objektorientierten Konzepten arbeiten wollen. Und mit diesem Grundsatz
- ausgestattet können wir jetzt tatsächlich auch auf Objekten arbeiten. Das heißt, also wir haben Objektmenge und wir können für
- ein Objekt dann eine beliebige Menge an Operationen definieren. Das wären dann in einer Java basierten Implementierung später, worauf voraussichtlich die
- Methoden. Auch das gucken wir uns wieder an dem Beispiel an. Ich nehme jetzt noch mal den Datentyp Inter inte Integer, also hier die Rapperklasse ähm und nicht
- den primitiven Datentyp. Und ähm dieser Datentyp, der braucht verschiedene Objektmengen. Also irgendwo arbeitet er mit einem oder mehreren intwerten und
- zwischendrin auch mit irgendwelchen Booliwerten. Ja, sie sehen hier schon Bull ist die allgemeingültigere Form. In Java wäre das dann der Boolientyp in
- anderen Programmiersprachen heißt ähm der Typ für Wahrheitswerte vielleicht anders. Üblicherweise verwendet man im Allgemeinen dafür die Bezeichnung Bull.
- Und jetzt gucken wir uns als Beispiel mal den Plusator an. In Wirklichkeit gibt's für Intager natürlich viele verschiedene Operationen. Was haben wir
- da? Wir bekommen zwei Int-Werte wieder mit dieser Kreuznotation und das Ergebnis wird berechnet und liefert wieder einen Intwert. Konkret sieht das
- so aus, dass diese beiden Werte, die wir hier mit A und B bezeichnen, abgebildet werden auf a + B. Jetzt können wir uns überlegen, gibt's dafür Vorbedingung,
- gibt es Nachbedingung, die würden wir hier formulieren und dann natürlich weitergehen mit all den anderen Operationen, die unser Datentyp Integer
- bereitstellt. Vielleicht noch einmal zu diesem Kreuzoperator. Das ist das sogenannte kartesische Produkt zweier Zahlen. Das bedeutet einfach nur, dass
- wir die Wertemenge aufblähen. Wenn wir einen Datentyp haben, dann hat er zunächst mal eine eigene Wertemenge. Und wenn wir den dann
- kombinieren mit einem zweiten Wert, mit dem kartesischen Produkt, dann steigt diese Wertemenge natürlich, ne? Wenn wir als Beispiel nehmen, wir haben hier die
- ganzen Zahlen, vielleicht erstmal nur die positiven Zahlen von eins bis größte darstellbare Zahl, dann hätten wir für die Kombination 1 mit 1, 1 mit 2, 1 mit
- 3, 2 mit 1, 2 mit 2, 2 mit 3 und so weiter. Sie sehen schon, da wird es sehr schnell eine sehr große Menge und die repräsentiert man hier durch dieses
- diesen Kreuzoperator bzw. das kathesische Produkt. Ein weiteres Beispiel, jetzt etwas komplexer als Datentyp, den wir
- beschreiben wollen, betrachten wir jetzt die Polynome noch mal als Erinnerung, das ist sowas wie ai mal x hoch i, also vielleicht
- a0 mal x hoch 0, also mal 1 + a1* x + a2* x² und so weiter bis zu einem höchsten Exponenten, der hier als n gekennzeichnet ist. Und auch hier wollen
- wir uns wieder eine beispielhafte Operation rausgreifen. Wir nehmen mal die Addition. Also zwei Polynome lassen sich addieren, bekommen wir das erste
- Polynom hier als P, das zweite als Q. Und das Ergebnis soll die Summe der beiden Polynome sein. Hier habe ich jetzt die Vorbedingung formuliert, dass
- der Grad gleich groß sein muss. Streng genommen kann man auch anders Polynome äh addieren, aber für unsere Operation hier ist das mal die angenommene ähm
- Vorbedingung. Und wenn dieser Grad der beiden Polynome gleich groß ist, dann können wir die Nachbedingung, die Postbedingung beschreiben, indem wir
- sagen, wir haben zwei Polynome, die haben jeweils eine Laufvariable von i = 0 bis groß n, wobei n eben dieser maximale Grad bei der Polynome ist. Und
- dann können wir die Summe beschreiben, indem wir wieder diese Summenformel verwenden und dann jeweils die be die Vorfaktoren AI und bi aufdieren und
- damit ein Ergebnispolynom bekommen. Also das als ein Beispiel für ein etwas komplexere Struktur, ein Objekt, das wir hier im als abstrakten Datentyp
- beschreiben. Ja, und ähm dann noch ein drittes Beispiel für so eine traditionelle Klasse. haben Sie bestimmt schon mal ein Beispiel gesehen, in der
- Sie eine Hochschule mit Studierenden repräsentieren und hier wollen wir uns mal die Konstruktionsoperation angucken, der
- Konstruktor, wenn man so will. Hier sagen wir, wir starten wieder aus dem Nichts. Wir haben aktuell noch äh kein Objekt. Wir brauchen eine Hochschule als
- Basis, ja, weil da vielleicht die Informationen verwaltet werden, was hier nicht explizit gesagt wurde. Es geht hier tatsächlich darum, einen
- studierenden Objekt zu erzeugen und wir erwarten als Eingabe zwei Zeichenketten, die hier verwendet werden sollen als Vorname und Nachname. Also aus
- Hochschule, Vorname und Nachname generieren wir ein studierenden Objekt. Als Vorbedingung sagen wir jetzt erstmal diese diese ganzen Argumente, die dort
- reinkommen, jeweils nicht Nall sein dürfen, sonst können wir damit nicht arbeiten. Und die Nachbedingung ist äh ein studierenden Objekt und das ist
- wieder ein zusammengesetzter Datentyp, da sehen Sie schon. Dieses studierenden Objekt hat nachher verschiedene Felder, Vorname, Nachname und Matrikelnummer.
- Für die Vor und Nachnahme erwarten wir, dass die Werte verwendet werden, die hier als Eingabe für die Operation vorgesehen waren. Bei der Matrikelnummer
- ähm da erwarten wir, dass überhaupt erstmal eine generiert wurde und dass die noch eindeutig ist. Das muss dann die Operation, die Implementierung
- sicherstellen, dass wir da eine passende Matrikelnummer erzeugen. Ja, kommen wir ähm zum Abschluss dieses Abschnitts über
- abstrakte Datentypen und gucken uns noch mal die Eigenschaften ein äh an. Insbesondere diese sechs Bausteine zeichnen abstrakte Datentypen aus. Die
- Universalität, die besagt, dass wir vollständig unabhängig sind von einer Programmiersprache, die Implementierung also später noch flexibel gestalten
- können. Wir erwarten, dass die Beschreibung formal mathematisch präzise ist, sodass sie sich einfach übersetzen lässt später in eine konkrete
- Implementierung. Gleichzeitig ähm muss die Beschreibung so einfach wie möglich sein. Also als anschauliche Beschreibung, wenn Sie zwei
- Möglichkeiten haben, einen abstrakten Datentyp vollständig zu beschreiben und die eine Beschreibung ist einfacher als die andere, dann ist diese eine die
- bessere. Sie kennen vielleicht schon das Kissprinzip Keep keep it simple stupid, das nichts anderes besagt als das Einfachheit das Ziel ist. Wir haben dann
- zwei ähm Eigenschaften, die miteinander eng verzahnt sind, die Kapselung und die Geschütztheit. Das heißt also die interne Form, das was Implementierung
- und Repräsentation ist, die soll weggekapselt sein, für die Anwender nicht sichtbar. Daraus resultiert dieses Geheimnisprinzip, dass ich also im
- Inneren die Informationen verstecke, die nicht für die Schnittstelle nach außen notwendig sind. Wenn ich das umsetze, dann resultiert häufig daraus die
- Geschütztheit, nämlich, dass interne Datenstrukturen nicht von außen angegriffen werden können, außer eben über die festgelegte Schnittstelle, die
- ähm für genau diese Aufgabe auch vorgesehen ist. Und dann kommen wir noch zu einem Konzept, was sehr sehr wichtig ist für die
- erfolgreiche Generierung von komplexen umfangreichen Anwendungen, nämlich die Modularität. Wir müssen in der Lage sein, dann diese kleinen abstrakten
- Datentypen als Bausteine zu verwenden, die sich kombinieren lassen und daraus lassen sich dann komplexere, größere Anwendungsäh Kontexte zusammenbauen und
- sie darin integrieren. M.