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.
aufgaben vergleichen
ich habe mich mit der aufgabe 1 der klausur vom 19.9.2005 eben beschäftigt und hatte ein problem mit der aufgabenstellung die da lautet:
ORY JFK BRU DUS ZRH MEX ORD NRT
fügen sie die codes (lexikographische ordnung) in der gegebenen reihenfolge in einen avl-baum ein!
juhu!
die gegebene reihenfolge ist jedoch nicht in lexikographischer ordnung, man soll sie aber trotzdem so hinkriegen! macht für mich zu dieser traurigen stunde keinen sinn!
ich habe die codes von links nach rechts mit 1,2,3,…,8 gekennzeichnet und die gegebene reihenfolge in einen avl-baum eingegeben:
4
2 6
1 3 5 7
8
also dann nach meiner intepretation:
DUS
JFK MEX
ORY BRU ZRH ORD
NRT
wie wäre es denn richtig gewesen? 
Glaube die aufgabenstellung zeigt nur die einfügereihenfolge. die lexikographische ordnung wird erst beim einfügen in den baum erzeugt. Habe einfach unter die Kürzel die Zahl geschrieben, also BRU = 1, DUS = 2, MEX = 3, usw. und dann in den avl-baum eingefügt.
Nein ich glaube nicht, dass das so richtig ist.
thomas_ hat schon recht mit seiner Vermutung.
bronx: Ist JFK wirklich kleiner als DUS?
Ich habe es so:
JFK
BRU MEX
DUS ORY ZRK
ORD NRTMeiner sieht auch so aus, zumindest der letzte…
hehejo deins ist falsch, so wie es da aussieht müsste NRT größer als ZRK sein (vielleicht ist es dir ja nur verrutscht ^^)
Also meiner sieht so aus (bin mir aber auch nicht sicher):
1 JFK
2 BRU ORD
3 DUS MEX ORY
4 NRT ZRH
Um die Verwirrung komplett zu machen:
Es heisst doch: “Gegeben ist eine geordnete Liste”
D. h. Die Codes sind bereits vorsortiert und zwar Lexikographisch.
Das wiederum würde ja dann bedeuten, dass ORY am gewichtigsten wäre, dann kommt JFK usw.
Also habe ich ORY = 8, JFK = 7, BRU = 6… angegeben und komme zu der Lsg:
DUS
MEX JFK
ORP ZRH BRU ORY
NRT
Ich komme auf den gleichen Baum wie Jan.
Mal noch eine Frage zu den Rotationsrichtungen (die soll man ja in der folgenden Teilaufgabe angeben). Auf unseren Folien wird da nicht unterschieden, von daher denk ich ist es auch nicht so wichtig. Trotzdem: Es ist schon so, dass die Rotation z.B. nach dem Einfügen von BRU eine Rechtsrotation wäre? Oder folgt das wieder irgendeiner wirren Mathematiker-Logik (also, nichts gegen Mathematiker ;-)), und das ganze wird genau andersherum bezeichnet, als jeder “normale” Mensch instinktiv annehmen würde…
@an-d: Dann differiert aber deren Definition von “lexikographisch” ziemlich von der Allgemeinen…
Rotation nach dem Einfügen von BRU? oO
Wie hast du das denn geschafft?
Ich musste ein einziges mal rotieren (beim Einfügen von NRT).
Nachdem ich keine Ahnung habe, was eine rechts- und was eine linksseitige Rotation ist, hätte ich bei der b) dann halt mathematisch korrekt auf die gestellte Frage geantwortet, dass es sich dabei um “eine doppelte Rotation nach links oder rechts” handelt 
Du müsstest auch mehr als einmal vertauscht haben, sonst hättest du JFK nicht als Wurzel, das landet ja beim Einfügen erstmal im linken Teilbaum.
Bei mir sah das halt so aus:
ORY JFK
JFK -> BRU ORY
BRUkann mir jmd die ordnung erklären? ich dachte bei dem begriff so an “telefonbuch-ordnung”?!
Oh stimmt ja, den Schritt hatte ich ganz übersehen ^^
adl: falls du die lexikographische Ordnung meinst, da ist einfach eine alphabetisch aufsteigende Sortierung (wie in einem Telefonbuch) gemeint.
Mal eine Schleifeninvariantenaufgabe:
double heron(double a) {
double x, y, h;
x = a; y = 1;
while (x > y) {
x = (x+y)/2;
y = a/x;
}
return x;
}
“Es lässt sich zeigen, dass bei Terminierung der while-Schleife x = y gilt.
a) Bestimmen Sie eine Vorbedingung, eine Nachbedingung und die Invariante der while-Schleife!”
Was würdet ihr als Invariante nehmen?
x*y=a
Plausibel…
1)a=xy gilt vor eintritt in die schleife
da x=a und y=1 a=x1 ->a=x
2)I ist eine invariante denn
wp(x=(x+y)/2,y=a/x ;I)=wp(x=x+y/2 ; wp(y=a/x,I) )
wp( y= a/x , I)=wp( y= a/x , a=xy)= (a=xa/x) → a=a–> true
–>wp(x=(x+y)/2 ,true) = true
haut das so hin?
- bei Terminierung gilt (I∧nicht-b)→Q
das ergibt sich hier wohl automatisch ,dass das identisch ist…?
bzw. das sieht man einfach.
4)die Schleife terminiert da y=a/x und x im lauf der Schleife kleiner wird,
und somit irgendwann nicht mehr x>y gilt…
korrekt so`?
Nö eigentlich nicht ^^
Bei wp(x=(x+y)/2; y=a/x; , I) muss I rauskommen ansonsten ist es keine Invariante -_-
Aber “true” wäre beispielsweise eine super Invariante. Bringt nur nicht viel 
Außerdem dachte ich, wir müssen keine Invarianten „erraten“ können:
Quelle: http://fsi.informatik.uni-erlangen.de/forumtest/thread/3091,1#4997
Naja ausgeschlosse hat er nur das, aber wenn man mal die Invariante hat, ist es ja echt einfach die nachzuweisen. Is ja nur einsetzen.
Ach ja und die Invariante von oben kann wirklich nicht stimmen (aus den bereits genannten Gründen).
Ich hab leider auch keine bessere Lösung im Moment…
wo im skript finde ich die substantivanalyse…???
Folie 1-15