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.
Klausur 17.9.07
Wollte mal Fragen, ob das so stimmt:
Aufgabe 3:
d) würde ich sagen eine Streutabelle (die als Kollisionsbehebung Listen verwendet) oder? Weil dort kann man gut nach Kantengewichten ordnen. In einer Halde steht zwar dann immer die minimale Kante in der Wurzel aber bei Prim weiß man ja nicht, ob man diese als nächstes dazunehmen darf oder nicht(würde sich meines erachtens eher bei Kruskal anbieten) oder sind die zu untersuchenden Kanten nur die die man als nächstes anschat weil dann wäre es eine Minhalde bei Prim…
e) genau n Knoten
genau n-1 Kanten
mindestens einen minimalen Spannbaum
Aufgabe 4:
b) bester Fall: 1 (das gesuchte Element steht in der Wurzel)
schlechtester Fall: n (zur Liste entartet)
(mittlerer Fall müsste dann logn sein denk ich)
c) 6,4,8,2,5,7,1
d) inorder(gibt sortierte Liste), preorder, postorder
Die 4 hab ich auch so.
bei 3d) müsste aber Halde heißen. und bei 3e) sinds doch mindestens n-1 Kanten. da steht ja nix von minimalem Spannbaum
ne weil ein Spannbaum hat doch keine Zyklen…
Hast recht 
Wissensfragen 1i)
Laut Klausurenwiki ist die Aussagen O(2^logn) = O(log2^n) falsch. Ich danchte aber dass sie wegen 2^logn = n^log2 ∈ O(n) und log2^n =n*log2 ∈ O(n) wahr ist. Kann mir bitte jemand sagen wo mein Denkfehler ist??
Dankeschonmal
mm ich hab da gesagt, dass es falsch ist aber das war einfach eher intuitiv kann ich nicht so recht begründen-.- dafür versteh ich aber nicht wieso bei der 1i) die 1. falsch ist und die 2.richtig… weil wurzel n ist doch immer größer als log n demnach müsste wurzel n doch in O(log n) liegen oder?
Ich kenne mich mit Mathematik nicht so gut aus aber Wolframalpha sagt n^log(2) == 2^log(n) = true demnach ist also per Definition auch O(n^log(2)) == O(2^log(n)) = true sein.
EDIT: Oops, die Frage ist ja eine ganz andere… habe noch mal versucht nach zu lesen, allerdings kann ich dir auch nicht wirklich weiterhelfen als zu sagen:
Hier kommt es drauf an wie das = zu verstehen ist denn:
O(log(2^n)) = O(log2(2^n)) =O(n)
und
O(2^log(n)) in O(n)
demnach ist
O(2^log(n)) in O(log(2^n))
Wenn nun das = ein einfaches „ist in“ ist dann ist es korrekt, falls = was anderes bedeutet dann ist es u.U. falsch.
Mathematisch pingelig sind O(term) Mengen, die Gleichheit von O(a) und O(b) ist also definiert als
O(a) ⊂ O(b) ∧ O(b) ⊂ O(a)
Das tut aber in dem Fall nichts zur Sache, Gleichheit gilt natürlich trivial für a=b, bzw. generell für lim_{n->Infinity} (a/b) = c (c ∈ R)
Edit:MalteM hat natürlich Recht, Zeichensatzfail meinerseits.
Falsch. Es muss O(a) ⊂ O(b) ∧ O(b) ⊂ O(a) heißen. :-p
OK. Demnach ist also [m]O(2^log(n)) ≠ O(log(2^n))[/m] weil zwar
[m]O(2^log(n)) ∈O(log(2^n))=O(n)[/m] ist aber [m]O(log(2^n))=O(n) ∉O(2^log(n)) [/m]
[ot]
Uns hat man damals™ gesagt das die Verwendung des = und des ∈ das selbe bedeute … offensichtlich und logischerweise war das falsch.
[/ot]
Also abgesehen von den verwendeten Zeichen, für die man übrigens (@MalteM) korrekterweise ⊆ für die Definition von Gleichheit verwenden sollte, dachte ich es geht um die Frage ob O(n^log(2)) = O(2^log(n)) und das ist wie schon festgestellt trivial richtig.
O(log(2^n)) kann gar nicht gleich sein mit O(2^log(n)), da gilt:
log(2^n) = n*log(2) ∊ Θ(n) ⊂ O(n)
2^log(n) = n^(log 2) ∊ Θ(n^(log 2)) ⊂ ω(n)
und trivial:
O(n) ∩ ω(n) = ∅
[ot]
Malte korrigier mich wenn ich Blödsinn laber
[/ot]
Zu dem “=” = “∈” muss man sagen das diverse Informatiker das gerne so verwenden, es bleibt trotzdem Blödsinn…
Wissensfragen 1b)
Die Frage lautet:
Für jede topologische Sortierung eines Baumes lässt sich eine Traversierung in Breitensuchreihenfolge angeben, die die Knoten in dieser Reihenfolge besucht.
Ich hätte jetzt gesagt, dass ist falsch weil ich die Tiefensichreihenfolge brauche. Ws sagt ihr dazu?
[quote=bulsa]korrekterweise ⊆ für die Definition von Gleichheit verwenden sollte[/quote]Da hast du bedingt Recht: man sollte ⊆ verwenden, wenn man mit ⊂ die echte Teilmenge meint. Mach ich normalerweise auch so, hab aber in letzter Zeit öfter auch ⊂ gesehen von Leuten, die für die echte Teilmenge ⊊ schreiben. Außerdem ist ⊆ nicht auf meiner Tastatur drauf, genauso wie ≤ fehlt :(…
Edit: gerade festgestellt, dass das Layout das bietet, ich aber keinen Hardware-Num-Block hab auf dem Notebook. Ich komme also per Fn+ScrollLock (entspricht NumLock), Shift+Mod3+j (entspricht Shift+Mod3+KP_1) dran. Das muss ich mal ändern.
[quote]
O(log(2^n)) kann gar nicht gleich sein mit O(2^log(n)), da gilt:
log(2^n) = n*log(2) ∊ Θ(n) ⊂ O(n)
2^log(n) = n^(log 2) ∊ Θ(n^(log 2)) ⊂ ω(n)
und trivial:
O(n) ∩ ω(n) = ∅
[/quote]Das gilt natürlich nur für Basen >2 beim Logarithmus. Für den binären Logarithmus stimmts also nicht.
Hiermit geschehen. Sooo schlimm war’s aber gar nicht.
+1
Wozu hast du denn dann ein super nerdiges Layout? 
Ich hab den mal als dekadischen oder natürlichen angenommen, für andere Basen ist die Schreibweise meines Wissens nicht üblich (ld dagegen schon).
Danke.
s. mein edit im letzten Post. Wie gesagt, ich werds noch ändern, brauche eigentlich so Zeichen wie ⚥ oder № eher selten, kann die also ersetzen…
Cormen verwendet lg tatsächlich nicht für den dekadischen, sondern den dualen Logarithmus, ist mir gestern aufgefallen.