ADT

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.

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.

Danke, auch wenn ich scheinbar keinen gesunden Menschenverstand besitze

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

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

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

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

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

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

Aufgabenstellung:

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

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!

Oh jetzt hab ich die d) auch verstanden

…wunder gibt es immer wieder.

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

Du bist genial!!!

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

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?

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.

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

und hier noch die Teilaufgaben c) und d)

c) Erweitern Sie Signatur und Axiomensystem des ADT MultiSet so, dass alle Vorkommen
eines (evtl. auch mehrmals!) eingef¨ugten Strings mittels der Operation purge entfernt
werden:
• Signatur :

PURGE: STRING x Multiset → Multiset

• Axiome:

A1: purge(x,create) = create
A2: purge (x, add (y, M)) = prurge(x, M) falls x=y
add(y,purge(x,M))

stimmt das so?

d) Nennen Sie die Prim¨arkonstruktoren des ADT MultiSet:

primärkonstruktoren müssten dann für meine begriffe add und create sein.

Schaut ganz gut aus, allerdings ein paar kleine Fehler

Du verwendest die Methode add, die gibt es aber nicht (hier heißt sie put)

b)

müsste heißen

A1: count(x, create) = 0

Es muss ein String und ein Multiset reingehen und ein Int rauskommen
Ansonsten schaut das gut aus

Ich hab jetzt mal versucht die Antworten zu Aufgabe 5 ADT WS 2010/2011 in diesem Thread + eigene Lösungsvermutunge im Prüfungswiki einzutragen (https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bachelor/aud/loesungws10).

Leider war ich nicht im Vorbereitungskurs und habe daher noch Probleme mit den Antworten zu d) und e). Wer kann mir helfen?

Danke

Ja ups, weiß auch nicht wa sich da geschafft hab mit dem put und add.

@laCucaracha: wo liegt denn dein Problem bei d) un e) ?

Bei d und e bin ich mir bei folgendem unsicher:

Bei d) kann ich ja höchstens auf getUrl(F) vereinfachen, aber reicht das schon aus?
Bei e) würde ich gemäss Axiom F5 auf den ersten Blick sagen F, aber muss man da nicht auch wieder eine Fallunterscheidung machen? Habe F5 auch ehrlicherweise nicht ganz verstanden. Der Feed wird immer zurückgegeben das sagt doch nichts darüber aus ob der Post wiederrufen wurde oder nicht?