Klausuraufgaben Maerz 2005

system · 14. September 2006 um 12:16

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.

phil · 14. September 2006 um 12:16

Klausuraufgaben Maerz 2005
1 c)

(let* ((var 1)
               (fn (lambda (var) (* var 2)))
               (var (+ var 2)))
  (+ var (begin (set! var fn) (var (var 4)))))

=> 19

Das seh ich nicht so.
Ich wuerde sage die Loesung ist undefiniert.
Weil nicht vorgeschrieben ist, dass der scheme Interpreter die Argumente der Reiche nach von links nach rechts auswertet kann es sein das zuerst var auf fn gesetzt wird und dann erst das erste var vor dem plus ausgewertet wird.Folgendes

(+ fn (fn (fn 4)))

ergibt dann einen “The first argument to integer add is not the correct type” Fehler.

phil · 14. September 2006 um 14:57

3 c)
Gegeben:

(define (f3 a)
  (cond ((null? a) '())
             ((symbol? a) (symbol-?string a))
             (else (cons (f3 (car a)) (f3 (cdr a))))))

Gesucht: Prozedur- und Prozesstyp sowie Komplexit"at von f3 in der Variablen a

L"osungsvorschlag:
f3 und der von f3 erzeugte Prozess sind baumrekursiv (zweimaliger paralleler rekursiverAufruf). f3 ist exponentiell komplex (O(2^n)) in a bez. Zeit- und Speicherplatzbedarf(Baumrekursion).

Auch hier stimm ich nicht unbedingt mit der Loesung ueberein.
Wenn nach der Komplexitaet in a gefragt ist, ist normalerweise nach der Komplexitaet bzgl. der Laenge von a gefragt.

Wenn ich f3 beispielsweise mit einem Baum mit 8 Blaettern aufrufe

(f3 '(((a . b ) . (c . d)) . ((e . f) . (g . h))))

Habe ich:
1 Aufruf mit 8 Blaettern
2 Aufrufe mit 4 Blaettern
4 Aufrufe mit 2 Blaettern
8 Aufrufe mit 1 Blatt

= 2 * 8 Aufrufe - 1

Also ist so wie ich das sehe f3 in O(n) in a bezueglich der Laenge von a.

Wenn allerding nach Komplexitaet von f3 bezueglich der Verschachtelungstiefe von a gefragt waere stimmt O(2^n).

andy · 14. September 2006 um 20:53

Hast du vollkommen Recht.

Jo, es sieht mir sogar so aus als wären sie da immer ein bisschen schlampig bei solchen Aufgaben. Es ist natürlich baumrekursiv auf dem cons-(Binär)-Baum, aber dessen Knotenzahl ist ja linear zur Länge des flachgeklopften Baums, der „Länge“ von a. Im wesentlichen läuft hier ja auch einfach ein map auf diesen flachgeklopften Baum ab.
Übrigens vllt ganz nett: es besteht tatsächlich ne direkte Isomorphie zum map: ordnet mal die cons-Paare um, dann kriegt ihr ne ganz normale Liste (die allerdings nicht auf nil endet).

Ich würde jetzt einfach mal vorschlagen das man sich sein n halt immer konkret definiert und sich nicht verführen lässt Eigenschaften des Rekursionsschemas auf falsche bzw ungeeignete Eingabegrösse zu beziehen. Den Musterlösern ist wohl intuitiv geglückt die Grösse zu wählen auf die man sich bei der Bearbeitung beziehen sollte.

phil · 14. September 2006 um 21:32

Warum willst du denn die schoene Baumstrukur zerstoeren?

Mann kann aus f3 ganz leicht ein binear-tree-map bauen, dass sich wie map verhaellt jedoch auf binaere baume angewendet werden kann

(define (binear-tree-map fn a)
  (cond ((null? a) '())
	((symbol? a) (fn a))
	(else (cons (binear-tree-map fn (car a)) (binear-tree-map fn (cdr a))))))

oder noch schoener ein tree-map das auf beliebig verschachtelte listen angewendet werden kann

(define (tree-map fn a)
  (cond ((null? a) '())
	((symbol? a) (fn a))
	(else (map (lambda (l)(tree-map fn l))a))))

wunderschoen. tree-map ruft map auf und map ruft tree-map auf

andy · 14. September 2006 um 21:47

Hmm? Ich wollte nur auf die Isomorphie hindeuten.

Übrigens sind deine beiden Implementierungen Sonderfälle von cons-fold und noch nicht so ganz generisch wie die Namen vermuten lassen. :>

(define (cons-fold f b p)
  (cond ((pair? p) (f (cons-fold f b (car p)) (cons-fold f b (cdr p))))
            (else b)))

Vllt mal Kürzel erklären: f=Funktion die cons „ersetzt“ b=Basisfall-Wert p=vermeintl. Paar

BTW: es existieren für alle rekursiv definierten Datenstrukturen (genauer: „isorecursive types“) solche generischen Morphismen (das sind mal grob gesprochen „strukturerhaltende Abbildungen“, wobei die Struktur nicht auf einen Typ beschränkt sein muss). Gibt auch ne reichhaltige Theorie dahinter, die einem in funktionalen (will fast sagen: kategoriellen; damn, das artet schon wieder zu ner Freakshow meinerseits aus ^^) Kontexten immer wieder begegnet. Vllt noch ganz nett zu erwähnen: Listen stellen sowas wie den Prototyp rekursiv definierter Typen dar; viele dieser Morphismen wurden erst auf Listen praktiziert und wurden dann verallgemeinert.