Diskussion:Abstrakter Datentyp

(Ohne Überschrift)

Offenbar hat der Verfasser dieses Artikels keine Informatik
studiert. Leider fehlt mir die Zeit und Muße diesen Artikel
umzuschreiben, dennoch möchte ich ein paar Bemerkungen dazu
machen:

Ein Abstrakter Datentyp (ADT) ist im wesentlichen durch
eine formale Beschreibung seiner Schnittstelle zur Umwelt
charakterisiert. Ein ADT ist in keinster Weise ein
- wie der Artikel sagt - spezieller Datentyp. Ein ADT ist
nur eine besondere Weise einen Datentyp zu definieren bzw.
anzugeben.

Die Defninition des ADT hält sich dabei an folgendes Muster:

  1. Typ/Wertebereich (welche Werte nimmt der ADT an bzw. mit welchen Datentypen geht er um)
  2. Methoden - die Syntax wie mit dem Datentyp gearbeitet wird
  3. Axiome - die die Semantik des Datentypen definieren

Beispiel: Stack:

1. Type:

  Stack (das definieren wir hier)
  Element (ebenfalls ein ADT den wir hier aber nicht definieren wollen, damit arbeitet unserer Stack)

2. Operationen (Syntax):

  StackInit: "nichts" -> Stack
  StackEmpty: Stack -> Boolean
  Push: Element x Stack -> Stack
  Pop: Stack -> Element x Stack

3. Axiome (Semantik):

  x: Element
  s: Stack
  Pop(Push(x,s)) = (x,s)
  Push(Pop(s)) = s, für StackEmpty(s) = FALSE
  StackEmpty(StackInit) = TRUE
  StackEmpty(Push(x,s)) = FALSE

Das ist ein ADT. Eine Datenstuktur bzw. Datentyp die über die auf ihm erlaubten Operationen - getrennt von jedweiger Implementierung - definiert ist.

Ein anders Beispiel: Boolean:

1. Wertebereich:

  {TRUE, FALSE}

2. Operationen:

  not Boolean -> Boolean
  and Boolean x Boolean -> Boolean
  or Boolean x Boolean -> Boolean

3. Axiome

  not TRUE = FALSE
  not FALSE = TRUE
  x and TRUE = x
  x and FALSE = FALSE
  x or TRUE = TRUE
  x or FALSE = x

Wenn man lustig ist kann man nun behaupten, das alle Terme die man über not, and und or bilden kann wieder die Form TRUE oder FALSE annehmen.

Beweis mittels struktureller Induktion über den Aufbau der Terme:

Induktionsanfang:

  TRUE, FALSE

Induktionsvorraussetzung:

  Die Terme x, y sind als TRUE oder FALSE darstellbar.

Induktionsschritt:

  not x: not TRUE = FALSE, not FALSE = TRUE
  x and y: t and TRUE = t, t and FALSE = FALSE
  x or y: t or TRUE = TRUE, t or FALSE = t

Also hätten wir die Behauptung mit Hilfe der oben definierten Axiome des ADT bewiesen.

Was bringen ADT's?

Nun sie dienen wie im Artikel beschreiben der Abstaktion.
Man kann auf diese Weise einen Datentyp beschreiben ohne
sich um die Details der Implementierung zu kümmern.

Dies hat den Vorteil das man bei dem Entwurf von Software
Systemen beispielsweise die Struktur vor der Implementierung
entwerfen kann. Der Code wird so Modularer und gekapselter.
Er kann so leichter gewartet werden, da er abgesehen von der
Signatur (= Summe der Methoden mit ihren Parametern) unabhängig
vom Rest des Softwaresystems implementiert werden kann.

Wer nach ADT in einer Suchmaschiene sucht findet schnell zahlreiche besser geschreibene Artikel als diesen hier. Und weitaus akuratere als den Artikel zu dem diese Diskussion gehört.

---

Leider ist diese vom Prinzip richtige Beschreibung einer allgemeinen Definition abstrakter Datentypen nur anonym geschrieben, so dass man nicht direkt mit dem Verfasser in Kontakt treten kann. Zur Historie dieses Artikels: Er wurde aus Datentyp ausgelagert und beschäftigt sich bisher fast ausschließlich mit der Begriffsbestimmung Abstrakter Datentyp im Umfeld konkreter Programmiersprachen. Er ist damit allerhöchsten unvollständig, nicht jedoch falsch. Die allgemeinere Beschreibung findet sich wie gesagt im Artikel Datentyp. btw: Einer der Verfasser hat Informatik studiert. --Friese 21:54, 13. Jun 2005 (CEST)

---

Ich hab mir das Chaos um die Datentypen heute morgen mal angeschaut ... Ich denke es wäre erst mal sinnvoll eine allgemeine Diskussion zu führen, wie die Aufteilung vorzunehmen ist ... Dafür habe ich mal unter Diskussion:Datentyp eine Diskussion angelegt und meine Ideen aufgeschrieben ... Grüße, --Jkrieger 11:07, 30. Jun 2005 (CEST)

Überarbeitet

Ich habe es nun stark überarbeitet - der auf der Diskussion verwendete ADT findet nicht mein Geschmack, weil mit pop gleich zwei Sachen gemacht wird, Stack kürzen und Element abgreifen. Ich bevorzüge top and pop. Ich habe es also so überarbeitet :-) und Queue als Gegenüberstellung auch noch aufgenommen.

Gerade Informatik-Studenten kriegen in der Vorlesung nicht immer alles mit, deswegen ist der Chaos bei den Informatik-Fragen durchaus recht hoch, weil etwas wesentliches fehlt oder etwas falsch aufgefasst wurde (hier waren auch einige Dinger einfach so nicht richtig). Aber so lernt man :-) --WiseWoman 01:00, 9. Okt 2005 (CEST) Habe sogar Informatik studiert und bin nun Hochschullehrerin...

Hmm, was meinst mit "Gerade Informatik-Studenten"? Passen andere Studenten besser auf? -- Gruss sparti 09:10, 9. Okt 2005 (CEST)

:-) Na ja, die sitzen janz locker mit ihren Laptops in der Vorlesung, angeblich um mitzuschreiben. Und schwupp-di-wupp sind sie dabei, E-Mails zu schreiben oder /. zu checken... wenn sie zu laut lachen an unangepasster Stelle frage ich sie, ob sie vielleicht mal zusammenfassen wollen, was wir gerade gemacht haben... --WiseWoman 09:50, 9. Okt 2005 (CEST)

So,so, die schreiben Emails. Wenn sie fuer Wikipedia schreiben wuerden, dann waere es ja noch zu verzeihen :-) -- Gruss sparti 21:30, 9. Okt 2005 (CEST)

Wer kann mir das erläutern?

Ich finde im Artikel folgende Passage: Wenn man die Definition eines ADTs mathematisch betrachtet, handelt es sich um die Spezifikation einer Termalgebra durch Signatur, Konstruktor und Axiome. und würde sie gern verstehen. --Peu 12:24, 25. Jun 2006 (CEST)

"mathematisch betrachtet"

Der Satz Wenn man die Definition eines ADTs mathematisch betrachtet, handelt es sich um die Spezifikation einer Termalgebra durch Signatur, Konstruktor und Axiome. Daraus ergibt sich die erste Art der Spezifikation, die mathematisch-axiomatische. beruht auf einer Einfügung von Benutzer:Robert.hartmann2 [1], und es ist auch sein einziger Beitrag. Diskutiert wurde mit ihm allem Anschein nach darüber weder hier noch auf seiner Benutzer-Diskussions-Seite.

Weder hier (s. voriger Diskussionsbeitrag) noch auf der Diskussionsseite der Benutzerin WiseWoman, die die entsprechenden Passage[2] aus dem ursprünglichen

== Mathematisch ==
Spezifikation einer Termalgebra durch Signatur, Konstruktor und Axiome.

herausformuliert und sogar noch erklärende(?) Links hinzugefügt hat, bekomme ich erklärt, was es mit dieser Aussage auf sich hat.

Kann es sein, dass wir es mit leerem Gerede zu tun haben? --Peu 15:36, 2. Jul 2006 (CEST)

Nein, das ist genau richtig, es ist ein Termalgebra. Ich setze einen Link ... ah, ich sehe, existiert nur bei WP:EN. Also müssen wir da ran, Termalgebra zu definieren. --WiseWoman 21:38, 3. Jul 2006 (CEST)

Nein! Termalgebra, gut und schön, aber was - um Gottes Willen - hat das mit Konstruktoren zu tun??? --Peu 22:41, 3. Jul 2006 (CEST)

Ein Konstruktor ist eine besondere Art von Operation, die als Rückgabetyp den Typ selber zurückliefert. Der Signatur umfasst alle Operationen. Oft haben ADTs nullary-Construktoren (ohne Parameter), aber manchmal gibt es auch Parameter. Das ist doch alles ganz klar, worin besteht genau der Konfusion? Verstehe ich nicht. --WiseWoman 23:22, 3. Jul 2006 (CEST)

Ich war mir eigentlich bis eben sicher, bei Konstruktoren würde die Abstraktion aufhören. Diesem Umstand verdanken doch Mittel wie class factories, clone-Methoden etc. ihre Existenz - sollte ich umlernen? Konstruktoren im herkömmlichen Sinne haben aus meiner Sicht nichts mit Abstrakten Datentypen zu tun. --Peu 19:06, 4. Jul 2006 (CEST)

Doch, man braucht ein Generator für ein Typ, auch im abstrakten, um einige mathematischen Beweise zu machen. Die heisst oft create: --> MyADT, that is, it creates something of thype MyADT, so that you have a base case for some constructions. Es geht hier nicht um die Tätigkeiten, die im Konstruktoren ablaufen, sondern nur um die SIGNATUREN, das ist das, was wichtig ist für die ADT. Man rechnet algebraisch mit den Operatoren, und kann durch die Stelligkeiten und Typen überprüfen, ob die Terme wohlgeformt sind. Wirklich. Habe ich schon mal gemacht, vor Jahren, als ich noch in theoretischen Informatik promovierte :) --WiseWoman 20:48, 4. Jul 2006 (CEST)

Dann schließe ich, dass Konstruktor im Sinne von C++ oder Java hier nicht gemeint ist. Gut, dann sollte es auch anders dargestellt werden, jedenfalls nicht mit dem irreführenden Link. Wie ich es verstehe, ist ein Konstruktionsmechanismus gemeint, der verwendet werden kann, aber den "Aufrufer" nicht an eine konkrete Implementierung bindet, sondern sich darauf beschränkt, etwas zu liefern, das als der beabsichtigte ADT fungiert. --Peu 23:08, 4. Jul 2006 (CEST)

Jetzt verstehe ich das eigentliche Problem - der Link unter Konstruktor. Können wir das einfach in "Erzeuger" umbenennen? Ich erinnere mich schwach daran, das schon öfters gehört zu haben. Literatur ist aber nicht zur Hand. Sonst entferne den Link um Konstruktor, das ist in der Tat verwirrend. --WiseWoman 16:38, 8. Jul 2006 (CEST)

Genau, danke! ich ändere es gleich --Peu 13:02, 20. Jul 2006 (CEST)

Tut mir leid, wenn ich hier wiedersprechen muss, aber Konstruktoren werden wirklich nicht benötigt. Entscheidend sind nur Signatur und Axiome. Oft legt man die Axiome so an, das ein Termersetzungssystem eine kanonische Normalform erzeugt. Will man z.B. das freie Monoid, also den Datentyp der Listen haben, dann kann man z.B. spezifizieren:

 ADT List(X) with
 Signature
    nil : List(X)
    cons: X * List(X) -> List(X)
    append: List(X) * List(X) -> List(X)
 Axioms
    append(nil,X) = X
    append(cons(X,Y),Z) = cons(X,append(Y,Z))

Damit lässt sich dann jeder Grundterm (also jeder Term ohne Variablen) über der Signatur durch Anwendung der Axiome in einen Term umschreiben, der nur noch die Funktionen nil und cons enthält. Die damit noch verbliebenen Funktionen nennt man dann einfach Konstruktoren. Sie sind aber nicht konstituierend für den Begriff des ADTs. Man hätte genau so gut definieren können:

 ADT List(X) with
   X subset List(X)
 Signature
   nil: List(X)
   append: List(X) * List(X) -> List(X)
 Axioms
   append(nil,X) = X
   append(X,nil) = X
   append(append(X,Y),Z) = append(X,append(Y,Z))

was gerade die Axiome des freien Monoids sind und hätte dann denselben Datentyp. Wer will, kann dem dann noch 'cons' hinzufügen mit:

 Signature
   cons: X * List(X) -> List(X)
 Axioms
   cons(X,Y) = append(X,Y)

Die Bezeichnung Konstruktor bedeutet insofern nur, dass die Axiome so gewählt sind, dass Funktionen, die keine Konstruktoren sind, bei der Normalisierung vollständig aufgelöst werden können. In diesem Sinne tragen die Funktionen, die keine Konstruktoren sind, dann nicht zur gewählten Repräsentation des Datentyps bei. Das ist aber nur eine Hilfsvorstellung, bei der man versucht, die Daten sozusagen noch stofflich an einer Normalform festzumachen und die die Wahl einer kanonischen Normalform unterstützt. Mathematisch betrachtet ist der Datentyp aber bereits durch die Signatur und die Axiome über die Quotiententermalgebra eindeutig definiert, egal, ob ein bestimmtes Termersetzungssystem clever genug ist, mit ihnen eine Normalform hinzubekommen oder nicht. Welche Präsentation man wählt, soll ja gerade abstrakt bleiben. Erst dann, wenn man die Spezikation tatsächlichen "rennen" will, kommt das Leistungsvermögen des Termersetzungssystem ins Spiel, was dann ggfls. tatsächlich noch allerlei Unterstützung braucht, um herauszufinden, ob man die Axiome besser von links nach rechts anwendet oder umgekehrt und wann und wo welches. Dann ist man aber auch schon beim Übergang von der Spezifikation in die Implementierung.

Zur Beleg und um dies mit den Erzeugern auseinander zu kriegen, hier eine Defintion aus [3]:

Definition: In an ADT, the collection of operations whose range is a certain sort S are called the generators of S. We sometimes identify a minimal subset of the generators called constructors with the property that every ground term of sort S is equivalent to some ground term involving only the constructors of sort S. That is, every object of type S is produced by some combination of the constructor operations.

Konstruktoren sind, wenn man solche benennen will, also Operationen. Erzeuger hingegen sind Werte.

Der Begriff der erzeugenden Menge tritt allerdings durchaus im Zusammenhang mit ADTs auf. Der Parameter X in List(X) in obigem Beispiel sind ein Platzhalter für die Grundmenge, über die die Liste frei erzeugt wird. Also z.B. List(Nat) wenn es eine Liste mit natürlichen Zahlen werden soll. Die Operationen der Zahlen spielen dabei keine Rolle, sondern nur die Grundmenge, also in diesem Beispiel die Zahlen, die dann die Erzeuger der Liste der Zahlen sind. -- Cobalt pen (Diskussion) 16:27, 10. Dez. 2015 (CET)

Toter Weblink

Bei mehreren automatisierten Botläufen wurde der folgende Weblink als nicht verfügbar erkannt. Bitte überprüfe, ob der Link tatsächlich unerreichbar ist, und korrigiere oder entferne ihn in diesem Fall!

• http://www.zib.de/Visual/people/mueller/Course/Tutorial/
  • In Abstrakter Datentyp on 2007-05-31 11:22:17, 404 Not Found
  • In Abstrakter Datentyp on 2007-06-11 15:15:08, 404 Not Found

--KuhloBot 17:15, 11. Jun. 2007 (CEST)

Java-Code

Der Java-Code ist eine statische Methode...in der Praxis ja total unbrauchbar. Ich krieg' immer Krisen wenn ich derlei statischen Code sehe. Das macht man besser in C, dafür brauchts nun wirklich kein Java. Lernt doch korrektes objektorientiertes Programmieren in Java! --178.197.228.1 00:07, 27. Jun. 2013 (CEST)

Ich frage mich, was du mit "statische Methode" meinst. Das Schlüsselwort static steht jedenfalls weder jetzt im Code, noch stand es im Juni 2013 im Code, laut Versionsgeschichte.

Das Problem, das ich mit dem Java-Code sehe, sind die Überschriften "Informelle Methode". Was in der Welt ist denn damit gemeint? Das wesentliche Merkmal der Methoden, das sich mir erschließt, ist, dass sie abstrakt sind (wie bei Interfaces normal). --dealerofsalvation 19:48, 30. Mai 2015 (CEST)