Autor |
Beitrag |
   
Spezi (Spezi)

Erfahrenes Mitglied Benutzername: Spezi
Nummer des Beitrags: 240 Registriert: 10-2001
| Veröffentlicht am Freitag, den 24. Oktober, 2003 - 18:48: |
|
Hallo, ich suche jemand, der mir bei meinen Aufgaben helfen kann, ich komme echt nicht mehr weiter! Aufgabe 1: Sei T ein endlicher Baum. Es sei nT die Anzahl der Knoten in T, hT die Höhe von T und bT die Anzahl der Blätter in T. Zeigen Sie: a) nT <= 2^(hT+1) - 1 b) Ist T vollständig, so ist nT=2^(hT+1) - 1 (was ist vollständig?, heißt das, dass jeder Knoten zwei Kinder hat, oder was??) c) bT <= 2^hT d) Ist T vollständig, so ist bT = 2^hT Ich musste noch nie etwas über Binärbäumen beweisen, und habe deshalb keine Ahnung, wie sowas geht! Aufgabe 2: a) kann ich selber :-) b) Zeigen Sie lg n! = Theta(n*lg n) lg heißt zur Basis 2 c) Beweisen oder widerlegen Sie (i) f(n) + g(n) = Theta(min(f(n), g(n))) (ii) f(n) = O(g(n)) => g(n) = Omega(f(n)) (iii) f(n) = O(g(n)) => 2^f(n) = O(2^g(n)) (ii) und (iii) finde ich einleuchtent, dass es so ist, aber wie ich das BEWEISEN soll, habe ich keine Ahnung! Aufgabe 3: Die Fibonacci-Zahlen sind durch folgende Rekurrenzen definiert F0 = 0 F1 = 1 Fi = F(i-1) + F(i-2), i>= 2 Sei ö=(1+sqrt(5))/2 und ö'=(1-sqrt(5))/2 (i) Zeigen Sie: Fi = (ö - ö')/sqrt(5) (ii) Zeigen Sie F(i+2) >= ö^i, i>= 0 (iii) Kann ich wieder selbst. Vielen Dank für jede Hilfe, jeden Tipp, ... Tamara |
   
Jair_ohmsford (Jair_ohmsford)

Erfahrenes Mitglied Benutzername: Jair_ohmsford
Nummer des Beitrags: 103 Registriert: 10-2003
| Veröffentlicht am Samstag, den 25. Oktober, 2003 - 00:34: |
|
Hallo Tamara, in Aufgabe 1 geht's doch um Binärbäume, d.h. jeder Knoten hat maximal 2 Kinder. Mit "Höhe" wird offenbar die Anzahl der Stufen über der ersten Stufe bezeichnet. "Blätter" sind wohl besondere Knoten (ohne Kinder). Die Anzahl der Knoten pro Stufe verdoppelt sich auf jeder Stufe höchstens. Dann ist doch die maximale Anzahl der Knoten 1 + 2 + 4 + ... = Sht i=02i= (2hT+1-1)/(2-1) (geometr. Reihe) =2hT+1-1 Damit ist dann Aufgabe a) und b) beantwortet. Evtl. musst du statt der Pünktchen eben die vollständige Induktion benutzen. Die maximale Anzahl der Blätter bildet eine geometrische Folge der Art 1,2,4,... Da gibt's dann zu jeder Höhe hT eben maximal 2hT Blätter - ebenfalls evtl. mit der vollständigen Induktion nachweisen. In Aufgabe 2 sagen mir leider Theta und Omega nichts - ich bin eben kein gelernter theoretischer Informatiker, eher ein Praktiker . Aber zur 3.Aufgabe weiß ich wieder etwas. Die habe ich mal als sehr unerfahrener Lehrer vor langer Zeit in einem Leistungskurs als Klausuraufgabe gestellt. (Jaja, ich schäme mich ja auch dafür... ). Also: Zunächst mal muss (i) richtig heißen F(i)=(öi-ö'i)/sqrt(5). Die Aussageform geht für 0 und 1 in wahre Aussagen über: F(0)=(1-1)/sqrt(5)=0 F(1)=((2*sqrt(5))/2)/sqrt(5)=1 Jetzt geht's weiter über vollständige Induktion: F(i+2)=F(i)+F(i+1) = (öi-ö'i)/sqrt(5)+(öi+1-ö'i+1)/sqrt(5) =(öi(1+ö))/sqrt(5) - (ö'i(1+ö'))/sqrt(5) Jetzt am besten von der anderen Seite aus weiter rechnen: F(i+2)= (öi+2-ö'i+2)/sqrt(5)= (öi*((1+2sqrt(5)+5)/2²))/sqrt(5)-(ö'i*((1-2sqrt(5)+5)/2²))/sqrt(5)= (öi*(3+sqrt(5))/2)/sqrt(5)-(ö'i*(3-sqrt(5))/2)/sqrt(5)= (öi(1+ö))/sqrt(5) - (ö'i(1+ö'))/sqrt(5) q.e.d. Ich denke, (ii) lässt sich ähnlich über vollst. Induktion zeigen. Ich bin allerdings jetzt müde und gehe ins Bett. Gute Nacht!
Mit freundlichen Grüßen Jair
|
   
Martin243 (Martin243)

Senior Mitglied Benutzername: Martin243
Nummer des Beitrags: 801 Registriert: 02-2001
| Veröffentlicht am Samstag, den 25. Oktober, 2003 - 11:58: |
|
Hi! zu Aufgabe 2: b) lg n! = lg (Pi=1ni) = lg 1 + lg 2 + ... + lg n = Q(lg n + lg n + ... + lg n) = Q(n*lg n) Übrigens sind alle logarithmischen Klassen äquivalent, da sie sich alle um einen konstanten Faktor unterscheiden. Die c) würde ich über die Definition von Q(f) machen. Ich rechne das mal auf Papier und melde mich wieder, wenn (falls!) ich es hinbekomme. Übrigens meine ich, (i) wäre falsch (Maximum statt Minimum). MfG Martin (Beitrag nachträglich am 25., Oktober. 2003 von Martin243 editiert) |
   
Spezi (Spezi)

Erfahrenes Mitglied Benutzername: Spezi
Nummer des Beitrags: 242 Registriert: 10-2001
| Veröffentlicht am Samstag, den 25. Oktober, 2003 - 18:39: |
|
Vielen Dank euch beiden!! Ich freue mich auf die Fortsetzung Tamara |
   
Spezi (Spezi)

Erfahrenes Mitglied Benutzername: Spezi
Nummer des Beitrags: 243 Registriert: 10-2001
| Veröffentlicht am Samstag, den 25. Oktober, 2003 - 20:24: |
|
Ich habe jetzt eure Lösungen nachvollzogen und verstanden. Danke. Die 3 (ii) habe ich auch geschafft, es ging sogar mit einem direkten Beweis. Tamara |
|