Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Binärbaume, Algorithmen und Fibonacci

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Mathematik für Informatiker » Binärbaume, Algorithmen und Fibonacci « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 240
Registriert: 10-2001
Veröffentlicht am Freitag, den 24. Oktober, 2003 - 18:48:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Jair_ohmsford (Jair_ohmsford)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Jair_ohmsford

Nummer des Beitrags: 103
Registriert: 10-2003
Veröffentlicht am Samstag, den 25. Oktober, 2003 - 00:34:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Martin243 (Martin243)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Martin243

Nummer des Beitrags: 801
Registriert: 02-2001
Veröffentlicht am Samstag, den 25. Oktober, 2003 - 11:58:   Beitrag drucken

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)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 242
Registriert: 10-2001
Veröffentlicht am Samstag, den 25. Oktober, 2003 - 18:39:   Beitrag drucken

Vielen Dank euch beiden!!

Ich freue mich auf die Fortsetzung :-)

Tamara
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Spezi (Spezi)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Erfahrenes Mitglied
Benutzername: Spezi

Nummer des Beitrags: 243
Registriert: 10-2001
Veröffentlicht am Samstag, den 25. Oktober, 2003 - 20:24:   Beitrag drucken

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

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page