Not logged in. · Lost password · Register

Page:  1  2  next 
???
Member since Oct 2011
445 posts
Subject: 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
This post was edited on 2012-02-20, 13:45 by ???.
ellewoods
Member since Nov 2011
45 posts
Quote by ??? on 2012-02-20, 13:33:
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
???
Member since Oct 2011
445 posts
ne weil ein Spannbaum hat doch keine Zyklen...
This post was edited on 2012-02-21, 16:51 by ???.
ellewoods
Member since Nov 2011
45 posts
Hast recht ;)
ellewoods
Member since Nov 2011
45 posts
Subject: 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
???
Member since Oct 2011
445 posts
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?
Mich
Member since Dec 2008
337 posts
In reply to post #5
Quote by ellewoods:
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

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.
This post was edited on 2012-02-22, 10:15 by Mich.
bulsa
Member since May 2011
568 posts
Quote by Mich:
Quote by ellewoods:
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

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.
This post was edited 2 times, last on 2012-02-22, 14:10 by bulsa.
MalteM
Member since May 2011
1470 posts
Quote by bulsa:
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)

Falsch. Es muss O(a) ⊂ O(b) ∧ O(b) ⊂ O(a) heißen.  :-p
Mich
Member since Dec 2008
337 posts
In reply to post #8
Quote by bulsa:
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)

OK. Demnach ist also O(2^log(n)) ≠ O(log(2^n)) weil zwar
O(2^log(n)) ∈O(log(2^n))=O(n) ist aber O(log(2^n))=O(n) ∉O(2^log(n))

Off Topic:
Uns hat man damals™ gesagt das die Verwendung des = und des ∈ das selbe bedeute ... offensichtlich und logischerweise war das falsch.
This post was edited on 2012-02-22, 12:22 by Mich.
bulsa
Member since May 2011
568 posts
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) = ∅

Off Topic:
Malte korrigier mich wenn ich Blödsinn laber ;)

Zu dem "=" = "∈" muss man sagen das diverse Informatiker das gerne so verwenden, es bleibt trotzdem Blödsinn...
ellewoods
Member since Nov 2011
45 posts
Subject: 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?
MalteM
Member since May 2011
1470 posts
In reply to post #11
Quote by bulsa:
korrekterweise ⊆ für die Definition von Gleichheit verwenden sollte
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.
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) = ∅
Das gilt natürlich nur für Basen >2 beim Logarithmus. Für den binären Logarithmus stimmts also nicht.
Off Topic:
Malte korrigier mich wenn ich Blödsinn laber ;)
Hiermit geschehen. Sooo schlimm war’s aber gar nicht.
Zu dem "=" = "∈" muss man sagen das diverse Informatiker das gerne so verwenden, es bleibt trotzdem Blödsinn...
+1
This post was edited on 2012-02-22, 15:14 by MalteM.
bulsa
Member since May 2011
568 posts
Quote by MalteM:
Quote by bulsa:
korrekterweise ⊆ für die Definition von Gleichheit verwenden sollte
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 :(…
Wozu hast du denn dann ein super nerdiges Layout? ;)
Quote by MalteM:
Das gilt natürlich nur für Basen >2 beim Logarithmus. Für den binären Logarithmus stimmts also nicht.
Ich hab den mal als dekadischen oder natürlichen angenommen, für andere Basen ist die Schreibweise meines Wissens nicht üblich ;) (ld dagegen schon).
Quote by MalteM:
Hiermit geschehen. Sooo schlimm war’s aber gar nicht.
Danke.
MalteM
Member since May 2011
1470 posts
Quote by bulsa:
Wozu hast du denn dann ein super nerdiges Layout? ;)

s. mein edit im letzten Post. Wie gesagt, ich werds noch ändern, brauche eigentlich so Zeichen wie ⚥ oder № eher selten, kann die also ersetzen…
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:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen