Lösungshinweise Übung 3

Benutzeravatar
~usz
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 18. Okt 2007 10:46

Lösungshinweise Übung 3

Beitrag von ~usz » 23. Jun 2011 20:15

Hallo,

drei Fragen zu den Lösungshinweisen:

Müsste bei Aufgabe 1c) die unterste Anomalie in der Tabelle (givenReferences, 35-...-51) nicht eine ur-Anomalie sein? Ihr habt den Pfad dort als du-Anomalie klassifiziert. Es gibt aber im gesamten Graphen kein d(givenReferences), also kann das irgendwie nicht richtig sein?

Zeile 60 im Code "children.next();" wird im Graph mit d(children) markiert (siehe auch Datenflussgraph in der Augabenstellung). Die Frage ist hier, warum es sich um eine Zuweisung handelt? Man könnte das so verstehen dass der "Wert" von children verändert wird, weil die Operation next() den Zustand der Variable ändert. Das ist aber auch streng genommen nicht garantiert, da man nie wissen kann, ob eine Operation den Zustand eine Objektes verändert oder nicht. Bei next() hilft man sich wohl über die Benamung, aber was wäre bei foo.bar() ?
Dann nehmt ihr an der Stelle noch verwirrenderweise Bezug auf einen Hinweis in der Aufgabenstellung: Dort steht aber nur, dass next() eine berechnende Operation (c) ist. Stünde dort "zustandsverändernde Operation" wäre es klarer, aber so? Wir hatten das damals auch in der Abgabe unserer Übung bemerkt, und der Tutor hat auch geschrieben das es richtig ist, aber den angegebenen Grund können wir leider nicht entziffern ;)

1f) Warum geht der Rückwärtsslice über 46, 45, 43? Dafür müsste es eine Datenflusskante von 45 nach 46 geben. Es gibt diese Kante aber nicht im Graphen (was auch korrekt ist). Unserer Meinung nach müsste der Slice 46, 43, 38, 36, 35 sein.

Benutzeravatar
saller
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 12. Okt 2007 15:14
Wohnort: Darmstadt
Kontaktdaten:

Re: Lösungshinweise Übung 3

Beitrag von saller » 23. Jun 2011 22:18

Hi,
Müsste bei Aufgabe 1c) die unterste Anomalie in der Tabelle (givenReferences, 35-...-51) nicht eine ur-Anomalie sein? Ihr habt den Pfad dort als du-Anomalie klassifiziert. Es gibt aber im gesamten Graphen kein d(givenReferences), also kann das irgendwie nicht richtig sein?
Danke für den Hinweis - hier hast Du einen Fehler gefunden - das ist tatsächlich eine ur-Anomalie.
Zeile 60 im Code "children.next();" wird im Graph mit d(children) markiert (siehe auch Datenflussgraph in der Augabenstellung). Die Frage ist hier, warum es sich um eine Zuweisung handelt? Man könnte das so verstehen dass der "Wert" von children verändert wird, weil die Operation next() den Zustand der Variable ändert. Das ist aber auch streng genommen nicht garantiert, da man nie wissen kann, ob eine Operation den Zustand eine Objektes verändert oder nicht. Bei next() hilft man sich wohl über die Benamung, aber was wäre bei foo.bar() ?
Dann nehmt ihr an der Stelle noch verwirrenderweise Bezug auf einen Hinweis in der Aufgabenstellung: Dort steht aber nur, dass next() eine berechnende Operation (c) ist. Stünde dort "zustandsverändernde Operation" wäre es klarer, aber so? Wir hatten das damals auch in der Abgabe unserer Übung bemerkt, und der Tutor hat auch geschrieben das es richtig ist, aber den angegebenen Grund können wir leider nicht entziffern ;)
Da hast Du vollkommen recht - man könnte es als eine Zustandsverändernde Operation sehen (damit wäre es ein d(children)) oder man behandelt Methoden eines Objektes als Black-Box und verwendet einen einfachen c-Operator. Beides ist in diesem Falle korrekt, da beide Argumentationen zulässig sind. Ich habe den Hinweis in dem Lösungsvorschlag entsprechend angepasst, damit dies hoffentlich klarer wird.
1f) Warum geht der Rückwärtsslice über 46, 45, 43? Dafür müsste es eine Datenflusskante von 45 nach 46 geben. Es gibt diese Kante aber nicht im Graphen (was auch korrekt ist). Unserer Meinung nach müsste der Slice 46, 43, 38, 36, 35 sein.
Der Rückwärtsslice über den Knoten 45 wird nur klar, wenn man den Datenflussgraphen mit den Kontrollflussverzweigungen angereichert hat. Die Bedingung in 45 beeinflusst auch den Wert des Knotens 46 und halt auch 48. Ein Datenfluss besteht nicht, das sit korrekt, aber der Wert der Bedingung beinflusst auch den Ausgangsknoten 48. Damit gehört 45 in den Rückwärtsslice und es müssen auch alle Knoten aufgenommen werden, die wiederum 45 beeinflussen.
Kurz: Bei einem Rückwärsslice muss ein vollständiger Abhängigkeitsgraph vorliegen und es müssen nicht nur die Datenfluss sondern auch die Abhängigkeitskanten betrachtet werden.

Gruß
Karsten

Benutzeravatar
~usz
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 18. Okt 2007 10:46

Re: Lösungshinweise Übung 3

Beitrag von ~usz » 24. Jun 2011 14:30

saller hat geschrieben: Der Rückwärtsslice über den Knoten 45 wird nur klar, wenn man den Datenflussgraphen mit den Kontrollflussverzweigungen angereichert hat. Die Bedingung in 45 beeinflusst auch den Wert des Knotens 46 und halt auch 48. Ein Datenfluss besteht nicht, das sit korrekt, aber der Wert der Bedingung beinflusst auch den Ausgangsknoten 48. Damit gehört 45 in den Rückwärtsslice und es müssen auch alle Knoten aufgenommen werden, die wiederum 45 beeinflussen.
Kurz: Bei einem Rückwärsslice muss ein vollständiger Abhängigkeitsgraph vorliegen und es müssen nicht nur die Datenfluss sondern auch die Abhängigkeitskanten betrachtet werden.
Ja, du hast recht, danke :)

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Lösungshinweise Übung 3

Beitrag von s!mon » 17. Jul 2011 16:11

Habe auch noch eine Frage zu der Übung. Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?

Bei der Operation refCount++ lese ich doch den alten Wert von refCount und weise das dann als neuen Wert refCount zu. Ich habe also die Reihenfolge c(refCount), d(refCount). Warum gibt es dann eine Kante im Graphen dafür? Imo dürfte nur bei einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen.

Need help :P

edit: außerdem frage ich mich noch wieso bei dem Kontrollflussgraphen im Knoten 64-66 ein u(v,e, children) vorkommt. Das undefined erfolgt doch schon bei Knoten 62?!

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Lösungshinweise Übung 3

Beitrag von oren78 » 17. Jul 2011 22:17

s!mon hat geschrieben:Habe auch noch eine Frage zu der Übung. Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?

Bei der Operation refCount++ lese ich doch den alten Wert von refCount und weise das dann als neuen Wert refCount zu. Ich habe also die Reihenfolge c(refCount), d(refCount). Warum gibt es dann eine Kante im Graphen dafür? Imo dürfte nur bei einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen.
In der Tat etwas seltsam, im Skript, Seite: 201 steht ja unter Punkt 3. folgendes:
3. für alle Anweisungen \(n\) auf Pfad \(p\) (ohne \(n_1\)) gilt nicht \(d(v)\) für \(n\):
\(n\) ändert also nicht den bei \(n_1\) festgelegten Wert von \(v\)
Meiner Meinung nach dürfen weder bei \(46, 58\) noch bei \(60\) die Knoten eine Kante zu sich selbst besitzen,
da innerhalb des selben Knotens der Wert der jeweiligen Variable \(v\) mittels \(d(v)\) geändert wird!

Im Prinzip widerspricht sich hier also die Definition 3. mit der Musterlösung insofern das ja gesagt wird:
ohne \(n_1\) wobei \(n_1\) der einzige knoten ist !!!
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Mojito Mix
DON'T PANIC
Beiträge: 42
Registriert: 10. Okt 2007 18:28

Re: Lösungshinweise Übung 3

Beitrag von Mojito Mix » 19. Jul 2011 12:07

Hallo,
hab auch noch eine Frage zu dieser Übung...Bei der Tabelle zu den Anomalien (Aufgabenteil c) wird für die Variabel e eine dd-Anomalie angegeben. Laut dem Graph kann es aber durch den Knoten 62 keine dd-Anomalie geben? In jeder Iteration der while-Schleife wird laut dem Graph die Variable auf undefined gesetzt. Damit eine dd-Anomalie vorhanden ist, darf laut Skript bis zur nächsten Definitionsstelle die Variable nicht benutzt (u|r|d) werden?
Ist der Knoten 62 überhaupt notwendig oder kann man die Variable e bereits im Knoten 45, also im Schleifenkopf, auf undefined setzen?

Benutzeravatar
saller
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 12. Okt 2007 15:14
Wohnort: Darmstadt
Kontaktdaten:

Re: Lösungshinweise Übung 3

Beitrag von saller » 19. Jul 2011 17:32

Hi,
Laut dem Graph kann es aber durch den Knoten 62 keine dd-Anomalie geben?
NEIN - da hast du einen Fehler aufgespürt. Laut Script darf auf dem Pfad einer dd-Anomalie kein lesender oder natürlich auch 'undefinierender' zugriff erfolgen. Damit fliegt diese Anomalie raus...
Ist der Knoten 62 überhaupt notwendig oder kann man die Variable e bereits im Knoten 45, also im Schleifenkopf, auf undefined setzen?
Das geht leider nicht, da man sonst mit dem Kontrollfluss durcheinander kommt und man würde beim ersten Schleifendurchlauf automatisch ein undefine von einem noch nicht existierenden Attribut machen. Es muss also explizit am Ende der Schleife / Kontrollblockes ausgeführt werden.

Gruß
Karsten

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Lösungshinweise Übung 3

Beitrag von s!mon » 19. Jul 2011 18:11

- Aber beim Funktionskopf macht man das doch genauso (um beispielsweise ur Anomalien zu bestimmen von Variablen die nie definiert wurden). Also da wird doch auch u(var) angegeben obwohl das Attribut noch gar nicht existieren kann?!

Wollte auch nur noch mal darauf hinweisen, dass ich auch noch eine Frage gestellt habe (weil ich befürchte, dass du sie überlesen hast, weil du die Frage ganz unten beantwortet hast :)):

- Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?
Bei der Operation refCount++ lese ich doch den alten Wert von refCount und weise das dann als neuen Wert refCount zu. Ich habe also die Reihenfolge c(refCount), d(refCount). Warum gibt es dann eine Kante im Graphen dafür? Imo dürfte nur bei einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen.

- Außerdem frage ich mich noch wieso bei dem Kontrollflussgraphen im Knoten 64-66 ein u(v,e, children) vorkommt. Das undefined erfolgt doch schon bei Knoten 62?!

Need help :P

Benutzeravatar
saller
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 12. Okt 2007 15:14
Wohnort: Darmstadt
Kontaktdaten:

Re: Lösungshinweise Übung 3

Beitrag von saller » 19. Jul 2011 19:05

Ups - Sorry - da hab ich wohl was überlesen - gut also zu Deinen Fragen:
- Aber beim Funktionskopf macht man das doch genauso (um beispielsweise ur Anomalien zu bestimmen von Variablen die nie definiert wurden). Also da wird doch auch u(var) angegeben obwohl das Attribut noch gar nicht existieren kann?!
Das ist ein Sonderfall, der so eigentlich nicht definiert ist. Normalerweise liegt ja auch der komplette Quellcode vor und nicht nur Teile daraus.
In der Übung hatte ich gesagt, dass es als korrekt angesehen wird (im Hinblick auf die Korrektur). Wichtig war mir vor Allem, dass erkannt wird, das eine UR-Annomalie vorliegt. Wo man das U gesetzt hat (Methodenbeginn oder vor direkt dem R) war dabei irrelevant.
In der Klausur würde dieser Spezialfall - ein Attribut wird niemals direkt undefined - nicht auftreten, da wir ihn "offiziell" nicht behandelt haben. Sprich man hätte immer ein undefine wie "String s;".
Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?
Beim nächsten Schleifendurchlauf liest du aber von dieser Definitionsstelle, daher liest es soz. von sich selbst. Ich habe jetzt allerdings gesehen, dass refCount ja in der Schleife definiert wird. Daher ist diese Kante tatsächlich falsch. Daten fließen somit nur von 51 und 54 nach 58. Wäre diese "starke" Definition allerdings nicht gegeben (z.B. die Initialisierung in Zeile 51 würde in 39 vorgenommen werden), wäre der rekursive Datenfluss allerdings korrekt. Bei sowas muss man immer Aufpassen.
einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen
Das ist Korrekt - hier hast du einen direkten Datenfluss. Es ist aber - wie oben erwähnt - nicht der einzige Fall.
Außerdem frage ich mich noch wieso bei dem Kontrollflussgraphen im Knoten 64-66 ein u(v,e, children) vorkommt. Das undefined erfolgt doch schon bei Knoten 62?!
Verfluchtes Copy&Paste - für solche Arbeiten sollte man das ausschalten können. Du hast hiermit Recht - ein doppeltes undefine der Attribute v,e,children macht natürlich keinen Sinn.

Danke für die Hinweise und viele Grüße
Karsten

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Lösungshinweise Übung 3

Beitrag von s!mon » 20. Jul 2011 16:15

saller hat geschrieben:Beim nächsten Schleifendurchlauf liest du aber von dieser Definitionsstelle, daher liest es soz. von sich selbst. Ich habe jetzt allerdings gesehen, dass refCount ja in der Schleife definiert wird. Daher ist diese Kante tatsächlich falsch. Daten fließen somit nur von 51 und 54 nach 58. Wäre diese "starke" Definition allerdings nicht gegeben (z.B. die Initialisierung in Zeile 51 würde in 39 vorgenommen werden), wäre der rekursive Datenfluss allerdings korrekt. Bei sowas muss man immer Aufpassen.
Ja die Definition aus 51 war das, was mich gestört hatte. Alles klar, vielen Dank.

nogood
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 5. Jul 2007 12:47

Re: Lösungshinweise Übung 3

Beitrag von nogood » 21. Jul 2011 00:20

Hi,

mir ist jetzt auch noch eine kleine Kleinigkeit an der Lösung 3 aufgefallen ^^.

Für die Variablen dag und givenRefernces wird im ersten Knoten des Kontrollflussgraphen ein u(dag,givenReferences) angegeben,
ein explizites d|u(dag|givenReferences) findet nicht statt.
Das Selbe gilt für die Variable visitor, die müsste dann doch auch noch mit u(visitor) in den ersten Knoten aufgenommen werden?

Mir ist auch nicht ganz klar was alles jetzt abschließend noch auf undefined gesetzt werden muss. Alles was nicht schon undefined ist? Oder evtl auch alles was irgendwann mal verwendet wurde obwohl es noch nie definiert worden ist wie visitor, dag und givenReferences?
Aus dem Lösungsvorschlag geht der erste Fall hervor, aber wäre schön da sicher zu sein.

Hoffe mich kann da jemand aufklären :)

Ich habe auch noch ein Verständnisproblem mit dem ++Refcount Beispiel:
saller hat geschrieben:
einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen
Das ist Korrekt - hier hast du einen direkten Datenfluss. Es ist aber - wie oben erwähnt - nicht der einzige Fall.
Wenn ich die Diskussion richtig verstanden habe seit ihr der Meinung, dass für den Fall ++refcount für den entsprechenden Knoten eine rekursive Schleife angelegt werden müsste? Wenn nicht dann ignoriert den Rest einfach ;)

Es ist doch so dass ++refcount bzw. refcount++ lediglich etwas syntaktischen Zucker darstellen um eine verkürzte Schreibweise für zwei Zuweisungsanwendungsfälle bereitzustellen:
Sodass

Code: Alles auswählen

int d = refcount++;
=>
int d = refcount;
int refcount = refcount +1;
und

Code: Alles auswählen

int d = ++refcount;
=>
int d = refcount +1 ;
refcount = refcount + 1;
bzw. 
refcount = refcount + 1;
int d = refcount;
In beiden Fällen muss aber zuerst ein c(refcount) vor einem d(refcount) ausgeführt werden, sodass lediglich im Fall einer Zuweisung an eine weitere Variable eine rekursive Schleife entstehen würde?

Benutzeravatar
saller
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 12. Okt 2007 15:14
Wohnort: Darmstadt
Kontaktdaten:

Re: Lösungshinweise Übung 3

Beitrag von saller » 21. Jul 2011 14:33

Hi,
Das Selbe gilt für die Variable visitor, die müsste dann doch auch noch mit u(visitor) in den ersten Knoten aufgenommen werden?
Hmm - war vielleicht etwas schlecht gewählt ohne den direkten Hintergrund der Übungsdiskussion. In der Pbung wurde darüber diskutiert, dass man ja nicht wissen kann, ob diese Variablen gegeben sind (z.B. als globale Attribute) definiert sind oder auch nicht initialisiert wurden. In unserer Übung betrachten wir ja immer nur einen Codeausschnitt. Der Konsistenz halber sollte hier also auch u(visitor) stehen.
Wenn ich die Diskussion richtig verstanden habe seit ihr der Meinung, dass für den Fall ++refcount für den entsprechenden Knoten eine rekursive Schleife angelegt werden müsste? Wenn nicht dann ignoriert den Rest einfach ;)
Also nur um das kurz klar zu stellen: Eine rekursive Schleife wird hier Prinzip nicht angelegt, sondern der Selbstverweis deutet auf einen Datenfluss zu sich selbst hin. Sprich ich definiere und lese diese Definition irgendwann evtl. später.
++refcount bzw. refcount++ lediglich etwas syntaktischen Zucker darstellen
:) Hehe - japp da hast Du recht. Es wird immer ein c und dann erst ein d von refCount gemacht. Manchmal sollte man Feierabend machen, wenn es Zeit dafür ist ;)
Aber um meine Ehre zu Verteigien - das Beispiel könnte entsprechend erweitert werden:
Bei

Code: Alles auswählen

System.out.println(++refCount); 
Hätten wir immer einen Selbstverweis auf sich: c(refCount), d(RefCount), c(refCount)
Im Gegensatz zu:

Code: Alles auswählen

System.out.println(refCount++); 
Hier wird erst refCount ausgegeben, bevor es neu definiert wird: c(refCount), (c(refCount) da bin ich mir jetzt nicht sicher ob notwendig), d(refCount).

Gruß
Karsten

nogood
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 5. Jul 2007 12:47

Re: Lösungshinweise Übung 3

Beitrag von nogood » 21. Jul 2011 20:39

Danke für die Klarstellung :)

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Lösungshinweise Übung 3

Beitrag von s!mon » 21. Jul 2011 21:33

Eigentlich wollte ich mit dem Ausdruck nur darauf hinweisen, dass die Reihenfolge von Auswertung und Zuweisung wichtig ist und man nicht immer gleich eine rekursive Kante einführen darf. Dass das mit ++refCount (alleinstehend) gar nicht funktioniert ist mir jetzt aber nicht aufgefallen, danke :oops:

Benutzeravatar
Omen
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 6. Nov 2004 21:04

Re: Lösungshinweise Übung 3

Beitrag von Omen » 31. Jan 2012 11:28

Ich habe eine Frage zur "Erweiterung zu einem Abhängigkeitsgraphen" Hinweise zum 3. Aufgabenblatt Seite 27:
Müsste es nicht einen Erweiterungspfad vom Knoten "n10" zum Knoten "n37" geben? Ist das nicht vergleichbar mit n20---->n33?

Antworten

Zurück zu „Archiv“