Signatur eines Abstrakten Datentyps

[BlackSalad]

Hallo,

ich verstehe den Abstrakten Datentyp nicht ganz.

Wir haben in der Vorlesung folgendes Beispiel gehabt:

"In diesem Beispiel soll ein ADT Number entwickelt
werden, welcher ganze Zahlen zusammen mit den
zugehörigen Rechenoperationen darauf darstellt. Bei der
Definition Ihrer Axiome dürfen Sie keine „klassischen“
Operationen auf ganzen Zahlen verwenden, also auch
keine Operationen wie n + m oder n ≤ m für n, m ∈ Z –
stattdessen müssen Sie diese auf die in Number
definierten (vorgegebenen oder von Ihnen entwickelten)
Operationen zurückführen. Der Datentyp Boolean mit
den Konstruktoren true bzw. false steht Ihnen zur
Verfügung."

Als lösung:

"

create: Z → Number
inc: Number → Number
dec: Number → Number
isZero: Number → Boolean
isLessThanZero: Number → Boolean "


Nur wie kommt man da blos drauf?

Ich verstehe noch nicht mal die Fragestellung richtig. Könnte mir jemand erklären was damit gemeint ist?

Wäre wirklich sehr nett


LG

 

[SlaterB]

Java Java Java, wo ist da Java? das ist hier doch keine Besprechung von beliebigen Uni-Vorlesungen,
verschoben

 

[The_S]

ich verstehe den Abstrakten Datentyp nicht ganz.

Kein Wunder, die sind ja auch schrecklich. Hab schon ewig kein ADT mehr gesehen. Immer nur Algebras.

"In diesem Beispiel soll ein ADT Number entwickelt
werden, welcher ganze Zahlen zusammen mit den
zugehörigen Rechenoperationen darauf darstellt. Bei der
Definition Ihrer Axiome dürfen Sie keine „klassischen“
Operationen auf ganzen Zahlen verwenden, also auch
keine Operationen wie n + m oder n ≤ m für n, m ∈ Z –
stattdessen müssen Sie diese auf die in Number
definierten (vorgegebenen oder von Ihnen entwickelten)
Operationen zurückführen. Der Datentyp Boolean mit
den Konstruktoren true bzw. false steht Ihnen zur
Verfügung."

Als lösung:

create: Z → Number
inc: Number → Number
dec: Number → Number
isZero: Number → Boolean
isLessThanZero: Number → Boolean

Das ist die Lösung? Kann ich mir nicht vorstellen. Das sind nur die Operatoren. Da fehlen noch die Axiome (die ja auch explizit in der Aufgabe erwähnt wurden). Aber egal ... Um die benötigten Operationen als ADT definieren zu können, benötigst du auch erst einmal das Wissen darüber, was dein ADT überhaupt können soll. Es geht bspw. nirgends hervor, dass er auf 0 oder kleiner 0 überprüft werden kann.

Ich verstehe noch nicht mal die Fragestellung richtig. Könnte mir jemand erklären was damit gemeint ist?

Die Fragestellung ist, dass du einen abstrakten Datentyp spezifizieren sollst, der bestimmte (hier nicht angegebene ) Operationen bereitstellen soll. Dazu gehören bspw. die Addition, die Subtraktion, ... Diese musst du in der Notation für ein ADT angeben. Was musst du sonst noch wissen?

 

[parabool]

verstehe ich so das Du aus den gegebenen Operationen:

create: Z → Number
inc: Number → Number
dec: Number → Number
isZero: Number → Boolean
isLessThanZero: Number → Boolean

die Operationen zu den ganzen Zahlen erzeugen sollst;
also Addition = m*inkrementieren
Substration = m* dekrementieren
Multipl. ergibt sich wiederum aus der def. Addition
Div. aus Subtraktion

Gruss

 

[BlackSalad]

Naja, ich kann mit dem ADT leider verdammt wenig anfangen. Zum Beispiel verstehe ich nicht wie sie auf

create: Z → Number
inc: Number → Number
dec: Number → Number
isZero: Number → Boolean
isLessThanZero: Number → Boolean


kommen.

was bedeutet inc, dec usw,?

Naja eigentlich soll ich es irgednwann schaffen die aus vorgegebenem Java Code zu erkennen und ihre Signatur und Axiome angeben zu können.

Seh ich es richtig, dass die Signatur immer die möglichen Operationen angeben soll und die Axiome die Kombination aus den Operationen?

 

[parabool]

Naja, inc bedeutet inkrementieren d.h. schrittweise erhöhung um einen Betrag (hier wohl um 1),
dasselbe bei dec nur eben abziehen.

stattdessen müssen Sie diese auf die in Number
definierten (vorgegebenen oder von Ihnen entwickelten)
Operationen zurückführen.

Vorgegeben ist unter anderem inc: Number → Number

Daraus kann man dann die Addition entwickeln also
also n+m wäre m * die vorgegebene Operation inc ausführen also: m mal (n um den den Betrag 1 erhöhen).

Aus der nun entwickelten Addition lässt sich dann die Multiplikation ableiten...

 

[BlackSalad]

okay, ich habs jetzt verstanden glaub ich.


Aber wie find ich in nem gegebenen Code was für ne Art abstrakter datentyp vorliegt?

Also ob Binärbaum oder Liste oder schlange ?

 

[The_S]

Naja, ich kann mit dem ADT leider verdammt wenig anfangen. Zum Beispiel verstehe ich nicht wie sie auf

create: Z → Number
inc: Number → Number
dec: Number → Number
isZero: Number → Boolean
isLessThanZero: Number → Boolean


kommen.

was bedeutet inc, dec usw,?

Naja eigentlich soll ich es irgednwann schaffen die aus vorgegebenem Java Code zu erkennen und ihre Signatur und Axiome angeben zu können.

Seh ich es richtig, dass die Signatur immer die möglichen Operationen angeben soll und die Axiome die Kombination aus den Operationen?

inc = inkrement = erhöhen, dec = dekrement = verringern. Das sind die Namen deiner Funktionen. Was kann mit dem Datentyp angestellt werden? Er kann erstellt (create), erhöht (inc), verringert (dec), auf Null überprüft (isZero) und auf kleiner Null (isLessThenZero) überprüft werden. Genau genommen gibt es nur Funktionen, deren Namen diese Funktionalitäten suggerieren. Was diese Funktionen dann wirklich machen, wird durch die Axiome definiert (die hier nicht aufgezählt sind).

Aber wie find ich in nem gegebenen Code was für ne Art abstrakter datentyp vorliegt?

Also ob Binärbaum oder Liste oder schlange ?

Normalerweise sollten die anständig benannt sein ;-) . Aber Anhand der Operationen kann man eine Vorauswahl treffen. Bspw. macht es wenig Sinn, einer Zahl die Operation "insert" zur Verfügung zu stellen. Auf der anderen Seite macht es auch keinen Sinn einer Liste die Operation "inc" zur Verfügung zu stellen. Genauere Auskunft geben dann noch die Axiome, da diese genauer angeben, was in welcher Operation geschieht.

 

[DerGroßeNargus]

Naja du sollst doch die Operationen add, sub, mul, isLessThan, isGreaterThan, equals und div erstellen mittels Axiome.

Signaturen dafür, wenn man dazu immer 2 Numbers nimmt:
add: Number x Number -> Number
sub: Number x Number -> Number
mul: Number x Number -> Number
div: Number x Number -> Number
isLessThan: Number x Number -> boolean
isGreaterThan: Number x Number -> boolean

Jetzt muss man für diese Signaturen die passenden Axiome finden, dass die Operationen formal ausgeführt werden können. Das ist nicht gerade trivial und eigentlich eine ziemliche Unverschämtheit, diese Axiome zu finden da das eigentlich nur Mathe/Logiklastig ist und dem Verständnis von ADTs und Axiomen nicht weiterhilft. Ein trivialeres Beispiel hätte auch geholfen...

für add wäre das z.B. (keine Garantie auf Richtigkeit):

add(A,B) = create(A) wenn isZero(B) = true;
add(A,B) = create(B) wenn isZero(A) = true;
add(A,B) =
{ 1. Fall: add(inc(A), dec(B)) wenn isZero(B) =false;
2. Fall: add(dec(A), inc(B)) wenn isLessThanZero(A) && isLessThanZero(B) = true; }

 

[BlackSalad]

Achso okay. Ich hab jetzt zwar lange gebraucht aber es ist mir glaube ich etwas klarer.


Und wie finde ich sowas jetzt in einem Code:

Zum Beispiel hatten wir in der Übungsstunde:

public class Foggy{
	final static int ERROR = 0xffffff;
	int a1[];
	int a2;
	public Foggy(){
		a1 = new int[2];
		a2 = -1;
	
	}
	
	public void f1(int v){
		a2++;
		if (a2>=a1.length) f5();
		a1[a2] = v;
	}
	
	public int f2(){
		if (a2>=0 && a2<a1.length) return a1[a2];
		return ERROR;
	}
	
	public void f3(){
		if (a2>=0)
			a2--;
	}
	
	public boolean f4(){
		if (a2<0) return true;
		return false;
	}
	
	private void f5(){
		int l1 = a1.length * 2;
		int[] l2 = new int[l1];
		for (int i=0; i<a1.length; i++){
			l2[i] = a1[i];
		}
		a1 = l2;
	}
	
	public int f6(){
		return a2+1;
	}
	
	public boolean f7(int v){
		for (int i=0; i<=a2; i++)
			if (a1[i]==v) return true;
		return false;
	}
	
	
	public void f8(Foggy l1){
		for (int i=0; i<=l1.a2; i++){
			int v = l1.a1[i];
			if (!f7(v))
				f1(v);
		}
	}
}

Aber wie finde ich darin jetzt die Signatur?

 

[The_S]

Die Signaturen sind deine Methodensignaturen. Ganz einfach . Ggf. noch mit "this" als zusätzliches Objekt.