Not logged in. · Lost password · Register

phil
Member since May 2006
34 posts
Subject: 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.
This post was edited 2 times, last on 2006-09-14, 17:27 by phil.
phil
Member since May 2006
34 posts
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
your local λ-dealer
Member since Oct 2005
248 posts
In reply to post #1
Quote by phil:
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.
Hast du vollkommen Recht.

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).
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. ;P
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 2 times, last on 2006-09-15, 00:26 by andy.
phil
Member since May 2006
34 posts
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
your local λ-dealer
Member since Oct 2005
248 posts
Quote by phil:
Warum willst du denn die schoene Baumstrukur zerstoeren?  ;-)
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.
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 5 times, last on 2006-09-15, 02:17 by andy.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen