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.
Blatt 8 - Bonusaufgabe
Irgendwie is hier im Forum außer dem Wort der VL nix los… ich veruch es trotzdem mal… Hier ist, was ich mir bisher überlegt habe:
DAG/DSG-Semantik allgemein:
- Variablen sind Pointer auf Knoten
- die Zuweisung X:=Y kopiert einen Pointer
- Y:= cons A B fügt einen neuen Knoten oberhalb zweier bestehender ein und lässt Y dahin zeigen
- Y:= hd Z kopiert left-Pointer des Knotens Z in Y
- Y:= tl Z kopiert right-Pointer des Knotens Z in Y
Eine readonly/writeonly Semantik bezieht sich auf den Speicherbereich, also auf den Baum, auf dessen Wurzel readonly/writeonly-Variablen zeigen.
Kann man für readonly-Semantik nicht ganz banal den Pointer der Eingabevariable als fix deklarieren und und alle vom referenzierten Knoten erreichbaren Kinder vom Platzverbrauch abziehen?
Mir würden Hinweise zu den folgenden Fragen sehr weiterhelfen:
Denke ich hier irgendwo grundsätzlich falsch ?
Welchen Teil müsste ich anders oder genauer oder nur formaler betrachten ?
Seh ich auch so.
Das Problem ist ja eher das dann formal hinzuschreiben.
Im heiligen Buch auf Seite 265 steht die DAG semantik für GOTO. Sollen wir sowas jetzt für WHILE + ReadOnly Eingabe + WriteOnly Ausgabe ummünzen?
EDIT: Ne ich glaub das funktioniert nicht -_-
Die Daten sind in WHILE und GOTO die selben, das heißt im Prinzip erstmal Binärbäume mit (vereinfachend) nur dem einen Atom nil als Blatt. Deswegen kann man den DSG für WHILE genauso verwenden wie für GOTO, um den Speicher zu messen. Das Problem ist aber, dass man auf die Art natürlich immer mindestens die Eingabe und mindestens die Ausgabe als Platzbedarf bekommt. Die Frage ist also, wie man das beheben kann. Dazu gehört die Klärung der Fragen:
- Wie zählt man weder zu viel noch zu wenig? Antwort bei der TM: Ein- und Ausgabeband zählen nicht mir.
- Welche Befehle werden zugelassen / gesperrt? Antwort bei der TM: Schreiben auf Eingabeband und lesen vom Ausgabeband sind gesperrt.
Zu den gestellten Fragen:
Grundsätzlich falsch: Nein, die Richtung stimmt.
Formaler: Was genau heißt “als fix deklarieren”? Das könnte heißen, den Platzverbrauch der Eingabevariablen grundsätzlich nicht mitzuzählen, auch wenn er geändert wird. Oder es könnte heißen, dass man sich die Knoten merkt, die schon am Anfang da waren, und die, unabhängig von allen Variablenbelegungen, nie mitzählt. Je nachdem, was gemeint ist, muss man eventuell (oder vielleicht auch nicht) bestimmte Anweisungen auf bestimmten Variablen einschränken.
Danke für die Antwort.
Ich habe jetzt die Semantik so verändert, dass es 2 Variablen I und O gibt, die im Fall von I nicht beschrieben und im Fall von O nicht gelesen werden dürfen. (Grammatik von WHILE neu definiert)
Ein Store o ist definiert als o = (d,p), d = DSG, p = die Pointer auf den DSG wo die Variablen jeweils beginnen. Mein neues Platzmaß ist definiert als Anzahl aller Knoten die im DSG d erreicht werden können wenn man von allen möglichen “Startpunkten” aus p losläuft, mit Ausnahme von I und O.
Ist das im ersten Aufgabenteil so gedacht?
Und wie soll ich jetzt das alte Platzmaß mit dem neuen Vergleichen? Es ist ziemlich offensichtlich, dass neues Platzmaß = altes Platzmaß - Platz(I) - Platz(O).
Wie soll ich das jetzt formal ausdrücken?
Es gibt für den ersten Aufgabenteil (wesentlich) mehr als eine richtige Lösung.
Da müsste man dann auch noch sagen, was Platz(I) und was Platz(O) genau sind (zB welche Knoten des DSG).
Man darf in dieser Aufgabe die Dinge in Prosa erklären. Wichtig ist, dass alles präzise ist. Also zum Beispiel sollte geklärt werden, was es heißt, wenn eine Variable nicht „beschrieben“ bzw. „gelesen“ werden darf. An welcher Stelle von welchen Anweisungen darf man die betreffende Variable (nicht) verwenden?
Der zweite Teil, das Programm, ist trivial:
gefordert ist: n - 2 * [p] ≤ 1
Mein Programm:
[m]read X;
write X;[/m]
mit Platzverbrauch 0 und konstantem Zeitaufwand…
somit ist: n - 2 * [p] = n - 2 * n = -n ≤ 1
SCNR
Wenn man das neue Maß verwendet, bei dem Ein/Ausgabe ja nicht zählen, wovon ich ausgehe…
Zugegeben, gemeint war eigentlich |n - 2 * [p]| ≤ 1… das heißt, man soll halbieren. Da es jetzt allerdings für ein Update der Aufgabenstellung zu spät ist, gilt der Grundsatz: Macht die Aufgaben, die auf dem Blatt stehen. Allerdings sollte es in eurem Speichermodell zumindest möglich sein, mit konstantem Platz eine Zahl zu halbieren.