ADT

[system]

Ich check nix | Altklausur 24.02.2011 | Klausurkurs

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[bewi1992]

ADT
Hi,

ich und en Kumpel wir haben heute morgen versucht die Aufgaben von gestern aus dem Klausurkurs zu lernen bzw. zu verstehen. Aber bei ADT verstehen wir beide absolut nichts.

Ich bin jetzt nochmal meine Mitschriften aus dem Klausurkurs und aus der Vorlesung/Übung und die Folien durchgegangen, aber wie das ganze funktioniert leuchtet mir immer noch nicht ein.

Das einzige was mir klar ist ist die Aufgabe a) Aber die war auch echt lachhaft, musste man ja nur ablesen.

Aber schon bei der Aufgabe b fängt es an. Ich habe zwar die Mitschrift, aber ich weiß nicht wie man darauf kommt. Nachvollziehen geht zwar, aber wie komme ich da drauf?

"b) Ermitteln Sie die Normalform (Ergebnis“) des folgenden Ausdrucks. Zwischenschritte brauchen nicht angegeben zu werden.

getPublishDate(getPost(3,
publish(createPost(’Einsicht’, 02.05.2011, false), 0,
publish(createPost(’Klausur’, 24.02.2011, false), 1,
createFeed(’www2.cs.fau.de’))))) =

ich würd das so verstehen:

createFeed(’www2.cs.fau.de’)))))

Wird laut Signatur zu einem Feed.

publish(createPost(’Klausur’, 24.02.2011, false), 1,
createFeed(’www2.cs.fau.de’))))) =

wird zu:

publish(createPost(’Klausur’, 24.02.2011, false), 1,
*Feed*

und das wird zu folgendem weil (createPost(’Klausur’, 24.02.2011, false) zu Post wird:

publish(*Post* , 1,
*Feed*

und das wird ja laut Signatur zu Feed.

Analog würde das

publish(createPost(’Einsicht’, 02.05.2011, false), 0,
publish(createPost(’Klausur’, 24.02.2011, false), 1,
createFeed(’www2.cs.fau.de’))))) =

auch wieder zu Feed werden.

Also hätten wir das ganze konstrukt zu

getPublishDate(getPost(3,
*Feed*)) =

und

getPost(3,
*Feed*)) = 

wird laut Signatur zu Post.

Und dann hätte man doch

getPublishDate(*POST*)

und nicht NoPost…

Ich verstehs nich.

[Der_Ich]

---

in dieser speziellen aufgabe braucht es gesunden Menschenverstand oder man rechnet sich tot:

Da steht “Gib mir das Datum (getPublishDate) vom Post mit ID 3 (getPost)”

Da jedoch nie ein Post mit ID 3 erstellt wurde gibt es auch kein Datum → 1.1.1970

[bewi1992]

---

also meinst du einfach es ist in der Aufgabe nur Post mit ID 0 und 1 erstellt worden aber keiner mit der ID 3 ?

Dann hört sichs irgendwie simpel an

[Der_Ich]

---

@bewi1992

also meinst du einfach es ist in der Aufgabe nur Post mit ID 0 und 1 erstellt worden aber keiner mit der ID 3 ?

Dann hört sichs irgendwie simpel an

genauso ist es

[bewi1992]

---

hm okay,

trotzdem hab ich es irgendwie nicht so verstanden wie das ADT-System funktioniert.
Also c) und d) sind mir einigermaßen klar.

Beispielsweise:

f) markSeen soll die aktuelle Nachricht mit id1 als gelesen markieren. Ergänzen Sie das dazugehörige Axiom:

F8: markSeen(id1, publish(P, id2, F)) =

im Klausurenkurs hatten wir als Lösung :

publish(setSeen(P, true), id2, F) wenn id1==id2

publish(P, id2, marSeen(id1, F) falls id1 unglich id2

Allerdings ist uns unklar wie man darauf kommt.

Über markSeen, weiß ich nur:

markSeen: int x Feed → Feed
F7: markSeen(id1, createFeed(u)) = createFeed(u)

Ich versteh absolut nicht wie ich da auf die Lösung kommen soll.

[Das_F]

---

Da hilft leider auch nur gesunder Menschenverstand.

Man soll hier wohl offensichtlich einen Post mit einer bestimmten ID als gelesen markieren. Wenn man sich die Post-Signaturen anschaut fällt einem da setSeen auf. Was wohl genau das macht. Wenn die IDs also Übereinstimmen, will ich den Post markieren

setSeen(P,true)

und danach wieder in den Feed schieben

publish(..., id2, f)

ist der Post nicht der gewünscht, dann muss ich im restlichen Feed weitersuchen.

Im Kurs kam die Frage auf, wieso man nicht direkt markSeen auf den Post anwenden, also z.b.

publish(markSeen(P), id2, F)

macht, wenn id1 == id2. Das liegt daran, dass markSeen ein Axiom/eine Signatur auf dem Feed Datentyp ist, man ja aber am Post Datentyp etwas ändern möchte und somit dort die dazugehörigen Axiome verwenden darf.

[bewi1992]

---

Danke, auch wenn ich scheinbar keinen gesunden Menschenverstand besitze

[Das_F]

---

Wenn man die Lösung nicht einfach “sieht” hilft nur üben, üben, üben und das Thema solange durchdenken, bis es irgendwann klickt macht.

[heftig]

31.07.2008
Hello,

also ich hab hier ne alte Klausur vom 31.07.08 vor mir liegen und hab die mal “zum Spaß” gemacht

Irgendwie schnall ich das Thema nämlich auch nicht so wirklich.

"Eine Multimenge ist eine Menge, in der Elemente mehrfach vorkommen köonnen. Entsprechend
kann man eine Multimenge nicht nur fragen, ob sie ein Element enthäalt, sondern auch wie oft.
Gegeben sei folgende Signatur eines abstrakten Datentyps Multimenge M. Die Elemente der Multimenge
seien von einem beliebigen Typ T.

create:              --> M
add: T x M         --> M
contains: T x M   --> Nat
remove: T x M     --> M
removeAll: T x M  --> M

contains soll zurückliefern, wie oft ein Element eingefügt wurde. Es gilt daher z.B.

contains(x,add(x,add(x,create))) = 2

remove(x,m) entfernt nur ein Element x aus der Multimenge M, removeAll(x,m) jedoch alle Vorkommen
von x in M.

b) Geben Sie die Axiome zur Definition des Verhaltens von contains an:

Also ich bin mir da sehr unsicher (generell beim Axiome angeben).

Ich hab mir gedacht:

A1: contains (x, create) = 0
A2: contains (x, add(x, create) = 1

c) Geben Sie die Axiome zur Definition des Verhaltens von remove an:

A4: remove(x, add(x, create) = create
A5: remove (x, create) = ?

d) Geben Sie die Axiome zur Definition des Verhaltens von removeAll an:

A6: removeAll (x, create) =?
A7: removeAll( x, add(x, create) = ?

Also das sind so ungefähr meine Gedanken, aber ich weiß absolut nicht wie man richtig vorgehen muss.

Vielleicht hat ja Jemand den ein oder anderen Tipp oder ne Erklärung parat.

Viele Grüße,

sebbi

[ri31hoky]

---

Meine Lösung sähe wohl so aus

b) Geben Sie die Axiome zur Definition des Verhaltens von contains an:

A1: contains(x, create) = 0

A2: contains(x, add(y, M)) = 1 + contains (x, M) wenn x == y
contains(x,M) sonst

Erklärungsversuch:

Für die meisten Axiome (außer evtl. top() oder ähnliches) brauchst du einen Basisfall und (mindestens) einen Rekursionsfall.
Für das erste Axiom ist der Basisfall, dass ein leeres Multiset keine Elemente beinhalten kann. Deswegen ist contains von create 0.

Für das 2te Axiom betrachten wir jetzt ein Multiset, das NICHT create entspricht. Es ist also nicht leer sondern beinhaltet beliebig viele Elemente.
Dabei ist jedes Multiset ein Multiset, das mal um 1 kleiner war und in das mit add eine Zahl gelegt wurde.

Eigentlich denken wir uns jetzt also
contains(x, M1) wobei M1 ein Multiset ist.
Da wir hier aber nicht wissen, wie man rekursiv weitermachen kann, greifen wir auf das Wissen zurück, dass M1 ja mal add(y, M0) war (wobei M0 einfach ein 1 kleineres Multiset oder auch create sein kann)
Also ersetzten wir das M1 durch add(y, M0) (y ist hierbei eine beliebige Zahl)

Bleibt
contains(x, add(y, M0))

Jetzt wissen wir, dass wenn dieses x gleich dem y ist, müssen wir einen Zähler erhöhen und dann rekursiv weitermachen.
Ansonsten wollen wir nur schaun, ob das x im restlichen Multiset vorkommt.
→ obige Lösung

c) Geben Sie die Axiome zur Definition des Verhaltens von remove an:

A4: remove(x, create) = create

A5: remove(x, add(y, M)) = M wenn x == y
add(y, remove(x,M)) sonst

Bei remove funktioniert das ganze ähnlich:

Aus einem leeren Multiset können wir nichts removen → es bleibt create

Hier haben wir wieder den Fall, dass unser Multiset mal eins kleiner war und etwas geaddet wurde.
Wenn wir dieses hinzugefügte Element also einfach weglassen, dann entspricht das dem Löschvorgang (somit bleibt M, aber nur, wenn x tatsächlich y ist)
Da dieses weglassen von y ein Löschen verursacht, brauchen wir auch noch einen Fall, wo wir das Element NICHT löschen → Wir löschen es für den rekursiven remove Aufruf, fügen es aber durch add wieder hinzu)

d) Geben Sie die Axiome zur Definition des Verhaltens von removeAll an:

A6: removeAll(x, create) = create

A7: removeAll(x, add(y, M) = removeAll(x, M) wenn x == y
add(y, removeAll(x, M) sonst

[rupran]

---

@ri31hoky

c) Geben Sie die Axiome zur Definition des Verhaltens von remove an:

A4: remove(x, create) = create

A5: remove(x, add(y, M)) = M wenn x == y
add(y, remove(x,M)) sonst

Edit: Hier stand Mist, hab den Satz ueberlesen (siehe naechster Post). Sorry.

[ri31hoky]

---

Achtung: Multimenge →
A5: remove(x, add(y, M)) = remove(x, M), wenn x == y
add(y, remove(x,M)) sonst

Aufgabenstellung:

remove(x,m) entfernt nur ein Element x aus der Multimenge M, removeAll(x,m) jedoch alle Vorkommen von x in M.

[heftig]

---

Super vielen vielen Dank!
Tolle ausführliche erklärung.

Teil b) ist mir jetzt auch klar.

Aber beiteil c versteh ich nicht so ganz wieso man erst eins löscht und dann wieder eins mit add dazu macht.
der fall mit y=x ist mir klar…

Danke nochmal!

[heftig]

---

Oh jetzt hab ich die d) auch verstanden

…wunder gibt es immer wieder.

[ri31hoky]

---

Du kannst dir das folgendermaßen vorstellen.

Angenommen du hast einen Stapel mit 5 Bauklötzen.
Du willst den 3ten Bauklotz entfernen, kommst da aber nur von oben dran.

Du nimmst den 5ten Bauklotz und legst ihn irgenwo ab.
Dann nimmst du den 4ten Bauklotz und legst ihn irgendwo ab.
Jetzt nimmst du den 3ten Bauklotz und verbrennst ihn (gelöscht).

Dein Stapel hätte jetzt nurnoch die Höhe 2 obwohl du ja eigentlich nur ein Element löschen woltest.

Also musst du jetzt den 4ten Bauklotz wieder drauflegen.
Danach den 5ten.
Und genau das macht das add

[heftig]

---

Du bist genial!!!

Vielen dank.
So versteht es auch der letzte depp.
Du solltest nachhilfelehrer werden

[aya]

---

Kurz noch zu der selben Aufgabe, die a) lautet:

a) Welches sind die Konstruktoren der Multimenge?

Muss man nur Primär- oder auchHilfskonstruktoren angeben? Geht aus der Fragestellung ja nicht definitiv raus, also lieber auf nummer sicher und beide angeben?

[Mich]

---

@-aya-

Muss man nur Primär- oder auchHilfskonstruktoren angeben? Geht aus der Fragestellung ja nicht definitiv raus, also lieber auf nummer sicher und beide angeben?

Ich wuerde sage sind beides Konstruktoren, also wuerde ich beide, aber mit entsprechendem Verweis welcher Konstruktor sie sind, angeben. Somit erspart man sich potenziellen Punkte Verlust und endlos Diskussionen bei der Einsichtnahme.

[edisch]

---

Ich hab mich mal an einer Altklausur versucht (25.02.2010):

Meine Lösungsidee zu a)

A1: put(x, create) = M
A2: contains(x, put(Y,M))=True  falls x= y
                  contains(x,M)         sonst
A3: contains(x, create)= false

Meine Lösungsidee zu b)

Signatur:

COUNT: STRING x Multiset → INT

Axiome:

A1: count(create) = create
A2: count(x, put( y, M)) = 1+count(x,M)  falls x=y
                                     count (x, M)   sonst

Stimmt das so?

Danke schonmal