Rekurrenzen

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.

Rekurrenzen
Hi,

was glaubt ihr? Müssen wir so Rekurrenzen erraten können? Ich finde das deutlich schwieriger als ne Schleifeninvariante rauszukriegen.

Hat sich das überhaupt jemand angeschaut? Mich wundert nur, dass es darüber noch keine Diskussionen gab :wink:

Edit:

bzw. lernt jemand diesen Hauptsatz auswendig?


was ist denn eine rekurrenz doch gleich wieder :smiley: ?


also ich hoffe sehr, dass das nicht drankommt… Was ich allerdings noch vermisse, ist eine klare herangehensweise für Schleifeninvarianten, weil du das grade erwähnst. Wie machst du das?


(1) Invariante herausfinden → kommt net dran
(2) Gilt SIV am Anfang?
(3) Bleibt die Invariante erhalten? => Mit dem wp-Kalkül drauf losgehen: wp(Schleifenrumpf,Invariante) <=> Invariante ?

A ja, und die Schleife sollte terminieren. Weiß nicht, ob man das auch zeigen muss…


ach jetzt. rekurrenzen beim teile-und-herrsche, bzw. bei der rekursion. ja ähm, fällt wohl nicht sehr ins gewicht denk ich …aber sieht meiner meinung auch nicht so schwer aus. Man rechnet hald für ein paar Werte n das T(n) aus, und muss hald dann irgendein Schema darin erkennen, und das dann per Induktion beweisen, oder seh ich das falsch ?


Ich glaube, das geht viel einfacher. Man braucht nur den Hauptsatz über Rekurrenzen und diese tolle Formel:

[m]T(n) = a * T(n / b) + f(n)[/m]

[m]b[/m] ist die Anzahl der Teilprobleme, in die das Problem rekursiv geteilt wird (meistens 2).
[m]a[/m] ist die Anzahl der Teilprobleme, die behandelt werden. Meistens werden alle Teilprobleme behandelt, also [m]a = b[/m] (Gegenbeispiel: Suchbaum).
[m]f(n)[/m] ist der Aufwand für die Zusammenführung der Teilergebnisse.

Beispiel Skyline-Problem:
Die Skyline wird in zwei Hälften zerlegt ([m]b = 2[/m]) und alle beide Hälften werden rekursiv berechnet ([m]a = 2[/m]). Dann werden die beiden Teilergebnisse wieder zusammengeführt ([m]f(n) = n[/m]).
[m]T(n) = 2 * T(n / 2) + n[/m]


Ja daher mein Zusatz: Lern jemand diesen Hauptsatz? Ich find die Formeln jetzt nicht gerade intuitiv. Ich glaub, das wird eine gezielte Lücke bei mir :smiley:


hmm das is direkt intressant nur irgendwie kann ich mir net vorstellen dass der da ne Aufgabe dran bringt … was willer denn da scho fragen…


Naja er kann halt irgend ne Rekurrenz herleiten lassen, so wie in der Übung oder auf den Folien. Aber geh etz mal davon aus, dass er das nicht tun wird. Genauso wenig wird er Induktionsbeweise verlangen… Davon geh ich für mich etz mal aus. Wenn es doch anders ist, lass ich die Aufgabe halt weg :wink:


Also ich hab mir den Hauptsatz schon gemerkt, ist gar nicht so schwierig wenn man mal ein paar Übungen dazu gemacht hat. Könnt mir schon vorstellen das irgendso eine Frage kommt wie: finden sie eine asymptotische Schranke für T(n) = 4T(n/2) + n^3 oder so. Ich rechne jedenfalls mal mit allen und denk das es reicht den Hauptsatz einigermaßen zu können.


Aber ich hoffe doch, dass wir nicht diese 3 Fäll mit den ε und den Logarithmen auswendig können müssen. Das würde mich irgendwie stressen, mir die noch reinzuprügeln.

@immoartl:
Terminierung der Schleife musst du für Beweis der totalen Korrektheit des Algorithmus bringen (für partielle Korrektheit ist es nicht nötig).


@peda.
bei deinem beispiel greift der dritte fall, oder?
was hast du denn für ein ε?