ADT 27.03.2006

Bachelor Algorithmen und Datenstrukturen
1

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.

2

ADT 27.03.2006
Aufgabe 6:
Meine Ergebnisse:
a)
A9: sorted(create) = true
A10: sorted(prepend1(x, prepend(y, l))) = true & sorted(prepend(y, l)) falls x < y
= false sonst

b)
A11: rotate(create) = create
A12: rotate(append(x, prepend(y, l))) = prepend(y, append(x, l))

kann mir das jemand bestätigen, oder verbessern?
Danke!

3
  • Wie löst du damit sorted(prepend(x, create)) auf?
  • Streng genommen steht in der Angabe auch, dass der Operator > definiert ist, nicht < (keine Ahnung wie streng das gesehen wurde).
  • true & foo() ist immer das gleiche wie foo(), „true &“ kannst du also weglassen
  • Wie löst du damit rotate(append(x, create)) auf?
  • append(x, prepend(y, l)) ist nach Axiom A2 das gleiche wie prepend(y, append(x, l)), dein A12:rotate ist also eher eine Identitätsfunktion (sie gibt genau das zurück, was ihr übergeben wurde).

Versuch mal dir beim Bearbeiten Notizen in einer anderen (eigenen) Darstellungsform zu machen, vielleicht kommst du dann besser zurecht. Beispiel, du hast hantiert mit:

[code] prepend(y, l) entspr.: y + Liste
append(x, prepend(y, l)) entspr.: (y + Liste) + x

append(x, l) entspr.: Liste + x
prepend(y, append(x, l)) entspr.: y + (Liste + x)[/code]
gesucht ist jedoch eine Umwandlung in diesem Stil:

    (Element + RestListe) -> (RestListe + Element)
4

A12 rotate(prepend(x, l) = append(x, l) Stimmt das so???

bei A10 habe ich allerdings keine Ahnung, wie schaut die Lösung aus?

5

Ich würde sagen: Ja.

Bei A10 würde ich sagen:
false falls x > head(l)
sorted(prepend(x,l)) =
sorted(l) sonst