binäre suchbäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sei B ein binärer Suchbaum, der die Elemente 1..n enthält.
Gegeben ist $A(n) = [mm] \summe_{k=1}^{n} [/mm] ( A(k-1)*A(n-k) )$, $A(0)=1$
A(n) gibt an wie viele verschiedene binäre Suchbäume sich aus den Elementen 1..n bilden lassen.
Finden Sie:
a) Eine (rekursive) Funktion, die einem Paar natürlicher Zahlen (h,n) die Anzahl der binären Suchbäume mit Höhe h und n Elementen zuordnet.
b) darauf basierend eine Funktion für die durchschnittliche Höhe.
c) Lösen Sie die obigen Rekursionen auf. |
So, wer nach dieser Aufgabenstellung mein Problem noch nicht sehen kann, bitte schön:
Zu aller erst muss wohl gesagt werden, dass die Funktion A(n) nicht in der Aufgabenstellung selbst gegeben wurde.
Sie wurde in einer anderen Aufgabe ausgerechnet und der Tutor hat ein paar Andeutungen gemacht dass sie bei dieser Aufgabe vielleicht von Nutzen wäre, weswegen ich sie mal mit aufgeführt habe.
Weiterhin ist zu sagen, dass die gesamte Aufgabe (Teil a) bis c)) gerade mal 10 Punkte wert ist, was in dem betreffenden Fach eigendlich einem Arbeitsaufwand von 2 Minuten bis hin zu 2 Stunden - keinesfalls mehr - entspricht.
Leider scheitere ich mit meinen Kommilitonen bereits an Teil a).
Nach ca. 4 Stunden haben wir folgende Funktion $f$ gefunden, die hoffentlich das gewünschte tut:
$f(h,n) = 0$ für $n<h$ oder $n> [mm] 2^h-1$
[/mm]
Im ersten Fall gibt es einfach nicht genug Elemente um einen Baum der Höhe h zu erhalten, im zweiten Fall sind es zu viele Elemente.
Dann als Rekursionsanfang:
$f(0,0) = f(1,1) = 1$
Und daraufhin folgende Gleichung:
$f(h,n) = [mm] \summe_{k=1}^{n} [/mm] (( f(h-1,k-1)*g(h-1,n-k) ) + ( g(h-1,k-1)*f(h-1,n-k) ) - ( f(h-1,k-1)*f(h-1,n-k) ) )$
Wobei:
$g(h,n) = [mm] \summe_{k=0}^{h} [/mm] f(k,n)$
g gibt an wie viel Bäume es mit einer Höhe von h oder kleiner gibt. (siehe unten)
Einmal zur Erklärung:
Wir wählen einen beliebigen Knoten als Wurzel (wird dadurch geregelt, dass wir eine Summe haben). Dann betrachten wir alle Möglichkeiten aus den Elementen, die kleiner als unsere Wurzel sind (und somit im linken Teilbaum liegen) einen Baum der Höhe h-1 zu basteln. Diese müssen natürlich multipliziert werden mit allen Möglichkeiten im rechten Unterbaum irgendwas zu basteln, dessen Höhe kleiner oder gleich h-1 ist (das ist insgesamt der erste Summand).
Darauf addieren wir dann das gleiche mit dem rechten Unterbaum der Höhe h-1 und dem linken irgendwo kleiner-gleich h-1.
Zu guter letzt müssen wir noch alle Kombinationen abziehen, wo beide Teilbäume eine Höhe von h-1 haben, da wir diese doppelt gezählt haben.
Allerdings glaube ich nicht, dass das so richtig ist, aus verschiedenen Gründen:
1. Das ist keine Funktion, die man mal so eben in einer Viertelstunde aus dem Ärmel schüttelt.
2. Die Funktion hat so viele Rekursionsstufen, dass die Berechnung eines einzelnen Wertes (zB f(10,10)) schonmal gut und gern eine Minute oder länger dauert. - der Tutor meinte aber "plottet dann mal kurz alles für $h [mm] \le [/mm] 20$ oder so.
3. Der Professor hat in der letzten Vorlesung gesagt "ich weiß, sie werden das Auflösen von Rekursionsgleichungen wahrscheinlich nicht im Laufe ihres Studiums lernen, aber keine Sorge, das was ich hier mache ist keine Zauberrei; selbst wenn es so aussieht". Daraufhin hat er eine Rekursionsgleichung aufgelöst, die gegen diese hier ein absoluter Witz an Trivialität war. - Und dann in der Hausaufgabe sowas; eher unglaubwürdig...
Also Fazit: Ich glaube nicht wirklich an diese Funktion; aber ich habe nichts besseres anzubieten.
Leider habe ich auch keinerlei Vergleichswerte um die Funktion zu testen oder so, weswegen ich mir nichtmal auf diesem Wege Gewissheit verschaffen kann.
Also, ich hoffe ich war einfach nur zu blöd die einfache Version zu entdecken und habe mir viel zu viel Mühe gemacht.
Sieht jemand von euch einen leichteren Weg das Problem zu lösen, eine Lösung, die für eine Zweitsemester-Informatik-Vorlesung, in der es um Datenstrukturen und nur in dritter Linie um Mathe geht, "angemessener" ist?
Danke schonmal für eure Mühen. ;)
MfG
Schadowmaster
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:32 Sa 14.05.2011 | | Autor: | felixf |
Moin!
> Sei B ein binärer Suchbaum, der die Elemente 1..n
> enthält.
Was hat $B$ mit dem Rest der Aufgabe zu tun?
> Gegeben ist [mm]A(n) = \summe_{k=1}^{n} ( A(k-1)*A(n-k) )[/mm],
> [mm]A(0)=1[/mm]
> A(n) gibt an wie viele verschiedene binäre Suchbäume
> sich aus den Elementen 1..n bilden lassen.
Hast du mal versucht, diese Formel nachzuvollziehen?
Also. Erstmal ist $A(n)$ nicht nur die Anzahl der Suchbaeume mit den Eintraegen $1, [mm] \dots, [/mm] n$, sondern auch die Anzahl der Suchbaeume mit $n$ verschiedenen, fest gewaehlten Eintraegen [mm] $k_1 [/mm] < [mm] \cdots [/mm] < [mm] k_n$.
[/mm]
Um eine Formel fuer $A(n)$ zu finden, geht man wie folgt vor: man hat $n$ Moeglichkeiten, die Wurzel des Suchbaumes zu waehlen. Sei $A(n, k)$ die Anzahl der binaeren Suchbaeume mit Wurzel $k$. Dann ist $A(n) = [mm] \sum_{k=1}^n [/mm] A(n, k)$. Nun besteht so ein Suchbaum mit Eintraegen $1, [mm] \dots, [/mm] n$ und Wurzel $k$ im Wesentlichen aus zwei Teilbaeumen: einmal der linke Teilbaum mit den Eintraegen $1, [mm] \dots, [/mm] k - 1$ (das sind $k - 1$ Eintraege), und der rechte Teilbaum mit den Eintraegen $k + 1, [mm] \dots, [/mm] n$ (das sind $n - (k + 1) + 1 = n - k$ Eintraege). Die Anzahl der moeglichen linken Teilbaeume ist also $A(k - 1)$, und die Anzahl der moeglichen rechten Teilbaeume ist $A(n - k)$. Da man linken und rechten Teilbaum voellig unabhaengig voneinander waehlen kann, ist $A(n, k) = A(k - 1) [mm] \cdot [/mm] A(n - k)$, und man erhaelt die Formel aus der Aufgabenstellung.
> Zu aller erst muss wohl gesagt werden, dass die Funktion
> A(n) nicht in der Aufgabenstellung selbst gegeben wurde.
> Sie wurde in einer anderen Aufgabe ausgerechnet und der
> Tutor hat ein paar Andeutungen gemacht dass sie bei dieser
> Aufgabe vielleicht von Nutzen wäre, weswegen ich sie mal
> mit aufgeführt habe.
Ah, ok. Entweder kanntest du die Erklaerung dann schon, und falls nicht weisst du jetzt ein wenig mehr, was fuer Aufgabenteil a) sehr hilfreich sein kann.
> Finden Sie:
> a) Eine (rekursive) Funktion, die einem Paar natürlicher
> Zahlen (h,n) die Anzahl der binären Suchbäume mit Höhe h
> und n Elementen zuordnet.
> b) darauf basierend eine Funktion für die
> durchschnittliche Höhe.
> c) Lösen Sie die obigen Rekursionen auf.
>
> Weiterhin ist zu sagen, dass die gesamte Aufgabe (Teil a)
> bis c)) gerade mal 10 Punkte wert ist, was in dem
> betreffenden Fach eigendlich einem Arbeitsaufwand von 2
> Minuten bis hin zu 2 Stunden - keinesfalls mehr -
> entspricht.
Nun, manchmal ueberschaetzen Aufgabensteller den Aufwand, und manchmal gibt es schwierige Knobelaufgaben mit wenig Punkten, damit auch Studenten die bei sowas keine Chance haben genuegend Punkte bekommen. Was hier der Fall ist kann ich nicht sagen 
> Leider scheitere ich mit meinen Kommilitonen bereits an
> Teil a).
> Nach ca. 4 Stunden haben wir folgende Funktion [mm]f[/mm] gefunden,
> die hoffentlich das gewünschte tut:
> [mm]f(h,n) = 0[/mm] für [mm]n 2^h-1[/mm]
> Im ersten Fall gibt es
> einfach nicht genug Elemente um einen Baum der Höhe h zu
> erhalten, im zweiten Fall sind es zu viele Elemente.
> Dann als Rekursionsanfang:
> [mm]f(0,0) = f(1,1) = 1[/mm]
Der leere Baum hat also Hoehe 0, und der Baum mit einem Element (der Wurzel) hat Hoehe 1?
> Und daraufhin folgende Gleichung:
>
> [mm]f(h,n) = \summe_{k=1}^{n} (( f(h-1,k-1)*g(h-1,n-k) ) + ( g(h-1,k-1)*f(h-1,n-k) ) - ( f(h-1,k-1)*f(h-1,n-k) ) )[/mm]
>
> Wobei:
> [mm]g(h,n) = \summe_{k=0}^{h} f(k,n)[/mm]
Das kannst du noch vereinfachen. Beachte dazu, dass [mm] $\sum_{k=1}^n [/mm] A(k - 1, n - k) = [mm] \sum_{k=1}^n [/mm] A(n - k, k - 1)$ ist (es wird einmal ueber $(k - 1, n - k) = (0, n - 1), (1, n - 2), [mm] \dots, [/mm] (n - 1, 0)$ summiert, das andere mal ueber $(n - k, k - 1) = (n - 1, 0), (n - 2, 1), [mm] \dots, [/mm] (0, n - 1)$ summiert). Wenn du jetzt $A(x, y) := f(h - 1, x) g(h - 1, y)$ einsetzt, siehst du dass $f(h, n) = [mm] \sum_{k=1}^n \left( 2 f(h - 1, k - 1) g(h - 1, n - k) - f(h - 1, k - 1) f(h - 1, n - k) \right) [/mm] = [mm] \sum_{k=1}^n \left( 2 f(h - 1, k - 1) \sum_{j=0}^{h-1} f(j, n - k) - f(h - 1, k - 1) f(h - 1, n - k) \right)$ [/mm] ist. Dies ist auch gleich [mm] $\sum_{k=1}^n [/mm] f(h - 1, k - 1) [mm] \left( 2 \sum_{j=0}^{h-2} f(j, n - k) + f(h - 1, n - k) \right)$.
[/mm]
> g gibt an wie viel
> Bäume es mit einer Höhe von h oder kleiner gibt. (siehe
> unten)
>
> Einmal zur Erklärung:
> Wir wählen einen beliebigen Knoten als Wurzel (wird
> dadurch geregelt, dass wir eine Summe haben). Dann
> betrachten wir alle Möglichkeiten aus den Elementen, die
> kleiner als unsere Wurzel sind (und somit im linken
> Teilbaum liegen) einen Baum der Höhe h-1 zu basteln. Diese
> müssen natürlich multipliziert werden mit allen
> Möglichkeiten im rechten Unterbaum irgendwas zu basteln,
> dessen Höhe kleiner oder gleich h-1 ist (das ist insgesamt
> der erste Summand).
> Darauf addieren wir dann das gleiche mit dem rechten
> Unterbaum der Höhe h-1 und dem linken irgendwo
> kleiner-gleich h-1.
> Zu guter letzt müssen wir noch alle Kombinationen
> abziehen, wo beide Teilbäume eine Höhe von h-1 haben, da
> wir diese doppelt gezählt haben.
![[ok]](/images/smileys/ok.gif "[ok]")
> Allerdings glaube ich nicht, dass das so richtig ist, aus
> verschiedenen Gründen:
Doch doch, das stimmt schon.
> 1. Das ist keine Funktion, die man mal so eben in einer
> Viertelstunde aus dem Ärmel schüttelt.
> 2. Die Funktion hat so viele Rekursionsstufen, dass die
> Berechnung eines einzelnen Wertes (zB f(10,10)) schonmal
> gut und gern eine Minute oder länger dauert. - der Tutor
> meinte aber "plottet dann mal kurz alles für [mm]h \le 20[/mm] oder
> so.
Nun, das haengt davon ab wie du die Funktion berechnest. Wenn du alle bereits berechneten Funktionswerte in einer $10 [mm] \times [/mm] 10$ Matrix speicherst (fuer $f(10, 10)$ jetzt), dann benoetigst du hoechstens [mm] $O(10^4)$ [/mm] Operationen um $f(10, 10)$ auszurechnen. Das geht in ein paar Millisekunden.
Ich hab gerade testweise ein Programm geschrieben, dass $f(n, h)$ fuer alle $(n, h)$ mit $0 [mm] \le [/mm] n, h [mm] \le [/mm] 100$ ausrechnet. Es braucht dazu ~0.25 Sekunden. (Fuer $0 [mm] \le [/mm] n, h [mm] \le [/mm] 200$ braucht es ca. 3 Sekunden.)
> 3. Der Professor hat in der letzten Vorlesung gesagt "ich
> weiß, sie werden das Auflösen von Rekursionsgleichungen
> wahrscheinlich nicht im Laufe ihres Studiums lernen, aber
> keine Sorge, das was ich hier mache ist keine Zauberrei;
> selbst wenn es so aussieht". Daraufhin hat er eine
> Rekursionsgleichung aufgelöst, die gegen diese hier ein
> absoluter Witz an Trivialität war. - Und dann in der
> Hausaufgabe sowas; eher unglaubwürdig...
Nun, Rekursionen aufloesen ist auch alles andere als einfach.
Die Rekursion $A(n)$ laesst sich uebrigens aufloesen, das Ergebnis sind die ![[]](/images/popup.gif) Catalan-Zahlen. Ebenso laesst sich eine Formel fuer $f(n, n)$ angeben, naemlich $f(n, n) = [mm] 2^{n-1}$ [/mm] fuer $n > 0$.
Fuer die Funktion $h(n) := f(n + 1, n + 2)$ bekommt man diese Folge, und somit ist $h(n) = (2n+1) [mm] 2^n$. [/mm] Fuer $g(n) := f(n, n + 3)$ bekommt man diese Formel, also $g(n) = [mm] (n^2 [/mm] - 6) [mm] 2^{n-2}$.
[/mm]
Die Funktion $f$ selber findet sich uebrigens in dieser Folge. Dort ist nur eine rekursive Formel beschrieben, eine Formel ist offenbar nicht bekannt.
Deswegen bezweifle ich stark, dass man die Rekursion in a) wirklich aufloesen kann. Wenn es doch geht, so waer ich (und vermutlich viele andere) sehr interessiert an einer Loesung :)
Die Frage ist allerdings, welche Rekursion in c) gemeint ist. Eventuell ist die Rekursion fuer $A(n)$ gemeint?
> Also Fazit: Ich glaube nicht wirklich an diese Funktion;
> aber ich habe nichts besseres anzubieten.
> Leider habe ich auch keinerlei Vergleichswerte um die
> Funktion zu testen oder so, weswegen ich mir nichtmal auf
> diesem Wege Gewissheit verschaffen kann.
Ohne Gewaehr die Funktionswerte $f(h, n)$ fuer $0 [mm] \le [/mm] h, n [mm] \le [/mm] 20$:
| 1: | n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12 n=13 n=14 n=15 n=16 n=17 n=18 n=19 n=20
| | 2: | h=0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
| | 3: | h=1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
| | 4: | h=2 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
| | 5: | h=3 0 0 0 4 6 6 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0
| | 6: | h=4 0 0 0 0 8 20 40 68 94 114 116 94 60 28 8 1 0 0 0 0 0
| | 7: | h=5 0 0 0 0 0 16 56 152 376 844 1744 3340 5976 10040 15856 23460 32398 41658 49700 54746 55308
| | 8: | h=6 0 0 0 0 0 0 32 144 480 1440 4056 10856 27672 67616 159184 362280 798616 1707996 3549264 7173268 14106912
| | 9: | h=7 0 0 0 0 0 0 0 64 352 1376 4736 15248 47104 140640 407360 1148560 3162016 8519936 22509880 58398904 148944824
| | 10: | h=8 0 0 0 0 0 0 0 0 128 832 3712 14272 50784 172640 568832 1828832 5757088 17787296 54043904 161750576 477548320
| | 11: | h=9 0 0 0 0 0 0 0 0 0 256 1920 9600 40576 156864 575104 2036416 7034624 23837888 79490560 261375872 848747360
| | 12: | h=10 0 0 0 0 0 0 0 0 0 0 512 4352 24064 110592 459648 1797504 6753920 24680192 88356224 311302912 1082465792
| | 13: | h=11 0 0 0 0 0 0 0 0 0 0 0 1024 9728 58880 291840 1294592 5362176 21221888 81360896 304774656 1121787392
| | 14: | h=12 0 0 0 0 0 0 0 0 0 0 0 0 2048 21504 141312 750592 3534336 15428096 64001024 256124416 998363136
| | 15: | h=13 0 0 0 0 0 0 0 0 0 0 0 0 0 4096 47104 333824 1890304 9407488 43114496 186805248 777627648
| | 16: | h=14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8192 102400 778240 4677632 24516608 117606400 530757632
| | 17: | h=15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16384 221184 1794048 11403264 62754816 314294272
| | 18: | h=16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32768 475136 4096000 27443200 158162944
| | 19: | h=17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 65536 1015808 9273344 65306624
| | 20: | h=18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 131072 2162688 20840448
| | 21: | h=19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 262144 4587520
| | 22: | h=20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 524288 |
(Das ist jetzt leider sehr unleserlich geworden :-( )
> Also, ich hoffe ich war einfach nur zu blöd die einfache
> Version zu entdecken und habe mir viel zu viel Mühe
> gemacht.
Ich glaube, du hoffst vergeblich.
LG Felix
|
|
|
| |
|
Zu aller erst mal vielen Dank für deine Mühe.
Die Erklärung zu der A(n) hättest du dir sparen können (sorry, hätte ich vielleicht dazuschreiben müssen).
Die habe ich eigendlich so weit verstanden; ich hab nur nicht wirklich gesehen wie/wo ich sie benutzen könnte.
Zu der Symetriebetrachtung von f:
Ich hab mir auch überlegt das so zu machen, das dann aber recht schnell wieder verworfen da man hier eine Fallunterscheidung braucht ob n gerade ist oder nicht.
Ist n ungerade so hast du das "mittlere" Element nur einmal, du musst diesen Fall also gesondert betrachten.
Ich hoffe ich hab richtig verstanden was du da erklären wolltest; das war zumindest mein Problem weswegen ich es nicht mithilfe von Symetriebetrachtungen vereinfacht habe.
Vor allem bin ich dir aber dankbar für den Link und die Tabelle; denn jetzt habe ich endlich ein paar Werte mit denen ich testen kann ob meine Funktion richtig ist.
Die Musterlösung für diese Aufgabe werde ich wahrscheinlich mitte bis Ende nächster Woche erhalten; ich kann sie dir dann gern per PN schicken (auch wenn ich denke dass in einer Info-Zweitsemester-Vorlesung mit nem Haufen Leuten die wirklich kaum bis garkein Mathe können nicht so eine Funktion aufgelöst wird. xD)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:44 So 15.05.2011 | | Autor: | felixf |
Moin,
> Zu aller erst mal vielen Dank für deine Mühe.
> Die Erklärung zu der A(n) hättest du dir sparen können
> (sorry, hätte ich vielleicht dazuschreiben müssen).
hab ich mir auch gedacht als ich ueber den Rest deiner Frage laenger nachgedacht habe. Allerdings war es auch ganz praktisch fuer mich selber, um besser in das Thema hereinzukommen :)
> Die habe ich eigendlich so weit verstanden; ich hab nur
> nicht wirklich gesehen wie/wo ich sie benutzen könnte.
> Zu der Symetriebetrachtung von f:
> Ich hab mir auch überlegt das so zu machen, das dann aber
> recht schnell wieder verworfen da man hier eine
> Fallunterscheidung braucht ob n gerade ist oder nicht.
Inwiefern?
> Ist n ungerade so hast du das "mittlere" Element nur
> einmal, du musst diesen Fall also gesondert betrachten.
Welches mittlere Element? Und wieso nur einmal?
> Ich hoffe ich hab richtig verstanden was du da erklären
> wolltest; das war zumindest mein Problem weswegen ich es
> nicht mithilfe von Symetriebetrachtungen vereinfacht habe.
>
> Vor allem bin ich dir aber dankbar für den Link und die
> Tabelle; denn jetzt habe ich endlich ein paar Werte mit
> denen ich testen kann ob meine Funktion richtig ist.
> Die Musterlösung für diese Aufgabe werde ich
> wahrscheinlich mitte bis Ende nächster Woche erhalten; ich
> kann sie dir dann gern per PN schicken (auch wenn ich denke
> dass in einer Info-Zweitsemester-Vorlesung mit nem Haufen
> Leuten die wirklich kaum bis garkein Mathe können nicht so
> eine Funktion aufgelöst wird. xD)
Ich wuerd mich sehr freuen, wenn du mir die Musterloesung schicken koenntest :) Ich bin wirklich sehr gespannt was da als Loesung erwartet wird...
LG Felix
|
|
|
|
