Komplexitätstheorie (2) - rekursive Funktionen

[Sone]

Gut, die nächste Frage:

Für eine rekursiv definierte Funktion f soll eine nicht-rekursive Funktion gefunden werden (die ich im weiteren Verlauf einfach mal g nenne), für die
$f = \theta (g)$
gillt.
Das wiederum heißt
$f = O(g)$ und $g = O(f)$
Was wiederum heißt, dass für genügend große n folgendes gilt:
$f(n) \le c g(n)$
$g(n) \le d f(n)$
Wobei c, d einfach irgendwelche Konstanten sind. Es muss sie aber geben.

Das wäre auch alles kein Problem, nur wie immer soll ich das beweisen - und wie geht das, wenn doch die Funktion rekursiv definiert ist? Wie bspw. hier:
$f(n) = f(n - 1) + 10$
Wie kann ich hier auch nur eine Ungleichung o.ä. aufstellen?

Ich komme schon darauf, dass es zu
$f(n) = 10n$
wird, welches wiederum auf
$f(n) = n$
reduziert werden kann (da der Koeffizient egal ist, schließlich ist bei der O-Notation eine beliebiger Koeffizient gefragt, der kann dann auch einfach angepasst werden).

Aber wie stelle ich da irgendeine Gleichung auf? Wie muss so ein Beweis für rekursive Funktionen aussehen?

Tut mir Leid, wenn ich mich doof stelle - aber ich habe noch nie vorher "Beweise" machen müssen. Ich habe nie ein Studium begonnen.

Vielen Dank im Voraus!

P.S.: Es ist übrigens gegeben, dass alle Funktionen von ℕ nach ℕ abbilden.

[Jester]

Sone schrieb:

$f(n) = c g(n)$
$g(n) = d f(n)$
Wobei c, d einfach irgendwelche Konstanten sind.
[/latex]

Nicht = sondern <= und auch erst ab einem bestimmten n_0!

Um zu zeigen, dass f(n) = 10 n gilt kannst du zum beispiel vollständige induktion verwenden.

[Sone]

Jaja, da habe ich mich natürlich verschrieben. Editiert.

Jester schrieb:

Um zu zeigen, dass f(n) = 10 n gilt kannst du zum beispiel vollständige induktion verwenden.

Eureka!

[Sone]

Ist das hier bereits ein richtiger Beweis:

Behauptung:
Wenn $g(n) = 10n$ und $f(n) = f(n-1) + 10$ wobei $f(0) = 0$, dann gilt $\forall n \ge 0 , f(n) = g(n)$

Beweis:
$g(n+1) = 10(n+1) = 10n + 10 = g(n) + 10$
$\Rightarrow g(n) = g(n-1) + 10$
■

?

[knivil]

Nein, es fehlt Vorraussetzung, Induktionsbehauptung, Induktionsanfang und Induktionsschritt ... so heissen die! Auch machst jetzt aus der expliziten Gleichung die impliziete, normalerweise ist das umgekehrt.

Weil heute mein Mathe-Tag anscheinend ist

Voraussetzung: g(n) = 10n und f(n) = f(n-1) + 10, n aus N (hier fehlt f(0))
Induktionsbehauptung: f(k) = g(k)
Induktionsanfang: Ja bitte wo ist der Anfang denn? ich tippe mal auf f(0) = g(0) = 0 (denn fuer f(0) = 3 ist obige Behauptung falsch)
Induktionsschritt:
f(k+1)
= f(k) + 10 | Definition von f aus der Voraussetzung
= g(k) + 10 | Induktionsbehauptung
= 10k + 10
= 10(k+1)
= g(k+1) | Definition von g aus der Vorraussetzung

Also aus f(k) = g(k) folgt f(k+1) = g(k+1). Das hat aber alles keinen Wert, wenn es keinen Induktionsanfang gibt.

Antwortsatz: Da Anfang gilt und ... bla bla ... alle folgenden durch Induktionsschritt, gilt fuer alle n >= 0 f(n) = g(n) = 10n

PS: Auch beim Programmieren mit rekursiven Funktionen gibt es den Basisfall fuer den Rekursionsabbruch. Folgendes in C ist auch sinnlos:

int f(int n)
{
    return f(n-1) + 10;
}

Tut mir Leid, wenn ich mich doof stelle - aber ich habe noch nie vorher "Beweise" machen müssen. Ich habe nie ein Studium begonnen.

Direkter Beweis, Widerspruchsbeweis und Induktionsbeweis sollten Schulstoff sein.

Gut, die nächste Frage:

Ja welche Frage denn. Du hast nur beschrieben, was du machst, aber nicht, welches Problem eigentlich geloest werden soll. Deswegen ist dieser Beitrag auch nur ins Blaue geraten.

[Sone]

knivil schrieb:

Nein, es fehlt Vorraussetzung, Induktionsbehauptung, Induktionsanfang und Induktionsschritt ... so heissen die!

Gut! Jetzt weiss ich es.

Ich schaue mir den Rest an, wenn ich wieder zu Hause bin... vielen Dank schon mal fuers aufschreiben.

PS: Auch beim Programmieren mit rekursiven Funktionen gibt es den Basisfall fuer den Rekursionsabbruch. Folgendes in C ist auch sinnlos:

int f(int n)
{
    return f(n-1) + 10;
}

Denkst du das Weiss ich nicht!?

Direkter Beweis, Widerspruchsbeweis und Induktionsbeweis sollten Schulstoff sein.

Ich habe in der Schule lediglich den direkten Beweis - eine simple Herleitung- gelernt.

Gut, die nächste Frage:

Ja welche Frage denn. Du hast nur beschrieben, was du machst, aber nicht, welches Problem eigentlich geloest werden soll. Deswegen ist dieser Beitrag auch nur ins Blaue geraten.

Welches Problem? Das war eine Aufgabe, ganz direkt wie sie im OP steht. Da gibt es keinen hoeheren Sachverhalt.

[knivil]

Welches Problem? Das war eine Aufgabe, ganz direkt wie sie im OP steht. Da gibt es keinen hoeheren Sachverhalt.

Dann solltest du die O-Notation noch irgendwie verwurschteln.

PS: Ich finde Fettdruck gleicht dem SCHREIEN.

[Sone]

Gut, ich höre auf zu Schreien.

Dann solltest du die O-Notation noch irgendwie verwurschteln.

Ganz einfach, ich setze die Konstante gleich 1. Fertig. Dann steht da "größer-gleich", wobei natürlich auch nur letzteres erfüllt sein kann. Also eine einfache Gleichung.

Gut, klar, mein Versuch glich wohl eher quod est dubitandum.

Hier mal deiner sauber aufgeschrieben:
___________________________________________________________________________________________________________________________________

Es seien $g, f : \mathbb{N} \rightarrow \mathbb{N}$ definiert als
$g(n) = 10n$
$f(n) = f(n-1) + 10$ wobei f(0) = 0.

Behauptung:
$f(n) = \theta (g(n))$

$\Rightarrow f(n) = O(g(n)) \bigvee g(n) = O(f(n))$

$\Rightarrow \exists n\_0, n\_1 \in \mathbb{N}, \ c, d \in \mathbb{R} \quad \forall n \ge n\_0 \ f(n) \le c g(n) \bigvee \forall n \ge n\_1 \ g(n) \le d f(n)$

Wir setzen $c = d = 1$ und $n\_0 = n\_1 = 0$, dann ist zu zeigen dass
$f(n) = g(n) = 10n$

Beweis:

Für n=0 gilt $f(0) = 0$, $g(0) = 10 * 0 = 0$

Nun ist zu zeigen, dass aus $f(n) = g(n)$ auch $f(n+1) = g(n+1)$ folgt.
Wenn man n+1 einsetzt, erhält man
f(n+1) = f(n) + 10
g(n+1) = 10(n+1) = 10n + 10 = g(n) + 10

Das heißt, $f(n+1)=g(n+1) \Leftrightarrow f(n) + 10 = g(n) + 10$. Und diese Gleichung gilt bei der Voraussetzung $f(n)=g(n)$.
Damit gilt $\forall n \quad g(n)=f(n)$.

[knivil]

sauber aufgeschrieben

Nee!

[Sone]

knivil schrieb:

sauber aufgeschrieben

Nee!

Ja wie denn nu? Wie muss ein Beweis denn aussehen? Dein Post oben hatte ja auch nur eine Beweisskizze!

[Sone]

Gut, ich habe es editiert und den unteren Teil, den "Beweis" selbst, zu einem (hoffentlich richtigem) vollständigen Induktionsbeweis gemacht.

[Jester]

Mach mal die Struktur richtig mit Induktionsanfang, Induktionsvoraussetzung und Induktionsschritt. Dein Aufschrieb ist mindestens schlampig.

[Sone]

Jester schrieb:

Dein Aufschrieb ist mindestens schlampig.

Mach mal die Struktur richtig mit Induktionsanfang, Induktionsvoraussetzung und Induktionsschritt.

Ich dachte, das soll man in Beweisen nicht explizit hinschreiben...

Induktionsvoraussetzung:
$f(n) = g(n)$.

Induktionsanfang:
Für n = 0 gilt
$f(0) = 0$ (per Definition)
$g(0) = 10*0 = 0$
$\Rightarrow f(0) = g(0)$

Induktionsschritt:
$f(n+1) = f(n) + 10$
$g(n+1) = 10(n+1) = 10n + 10 = g(n) + 10$

Es kann die Gleichung $f(n+1) = g(n+1)$ folglich durch
$f(n) + 10 = g(n) + 10$
ersetzt werden. Subtrahiert man nun 10, ergibt sich
$f(n) = g(n)$
Was wiederum die Induktionsvoraussetzung ist.

Antwortsatz: Da f(0) = g(0) gilt, ist die Induktionsvoraussetzung für n=0 erfüllt. Damit gilt $f(1) = g(1) \Rightarrow f(2) = g(2) \Rightarrow ... f(n) = g(n)$ für beliebige n.
Daher gilt für alle n, $f(n) = g(n)$.

(Dass $n \in \mathbb{N}$ wird dadurch impliziert, dass f und g von ℕ nach ℕ abbilden).

[Jester]

Schon etwas besser, jetzt noch ein bisschen sortieren. Der Induktionsanfang kommt ganz nach vorne. Die Induktionsvoraussetzung gehört vor den Induktionsschritt -- dort wird sie schließlich auch benutzt.

Jetzt solltest Du noch den Induktionsschritt aufräumen, das geht bei dir grad ziemlich durcheinander. Du nimmst irgendwelche Gleichungen formst die scheinbar wahllos um kommst am Schluß irgendwie da an wo Du hin willst.

Zu zeigen: f(n+1) = g(n+1)

f(n+1) =(Def.) f(n) + 10 =(nach IV) g(n) + 10 =(Def.) 10n+10 = 10*(n+1) =(Def.) g(n+1)

Siehst Du wie gezielt die vorhandenen Informationen eingesetzt werden um genau die Aussage zu zeigen, die bewiesen werden soll.

Für die ersten ca. 100 Induktionsbeweise solltest Du die Struktur sauber ausarbeiten. Danach darfst Du dann irgendwann schlampiger werden.

[Sone]

f(n+1) =(Def.) f(n) + 10 =(nach IV) g(n) + 10 =(Def.) 10n+10 = 10*(n+1) =(Def.) g(n+1)

Ah, ich sehe, was du getan hast.
(Def.) f(n) + 10 =(nach IV) g(n) + 10
gilt natürlich direkt, wenn f(n) = g(n). Mein Induktionsschritt macht ja prinzipiell dasselbe.

Gut, ich habe hier noch ein paar Funktionen, bei denen ich das gleich mal machen werde - beispielsweise:
$f(n) = 2f(n-1), wobei f(0) = 1$
Das Gegenstück ist, soweit ich sehe,
$g(n) = 2^n$

Wieder Induktionsanfang:
$f(0) = 1$ (per Definition)
$g(0) = 2^0 = 1$
$\Rightarrow f(0) = g(0)$

Induktionsvoraussetzung:
$f(n) = g(n)$

Induktionsschritt:
$f(n+1) = 2f(n) = 2g(n) = 2 * 2^n = 2^{n+1} = g(n+1)$
Daher $f(n+1)=g(n+1)$.

Natürlich noch mit dem ganzen Tohuwabohu.

[Jester]

ja genau. viel mehr brauchts auch gar nicht.

[Sone]

Jester schrieb:

ja genau. viel mehr brauchts auch gar nicht.

Hier nicht, nein...
Aber ich habe hier eine Reihe von Funktionen, die nicht linear rekursiv implementiert sind, sondern exponentiell rekursiv (kann man das so sagen?):

$f(n) = f(\frac{n}{2}) + 10$
Der ist noch einfach ($10 log_2(n)$), aber wie würde ich hier die Induktion vollbringen? Einsetzen von n+1 ergibt:

$f(n+1) = f(\frac{n+1}{2}) + 10$
Beim Einsetzen bei g sieht es nicht rosiger aus.

Einsetzen von $2n$ ginge natürlich, bringt mir aber nichts, weil es nicht alle n berücksichtigt.

[Jester]

du bist auch nicht drauf angewiesen eine geschlossene darstellung von f zu finden. Du willst schließlich nur eine Aussage im O-Kalkül machen. Du mußt also nur eine Abschätzung induktiv beweisen, das kann deutlich einfacher sein.

[knivil]

Ich dachte, das soll man in Beweisen nicht explizit hinschreiben...

Wer sagt das? Ein Beweis ist etwas formales. Hat ein Zeitungsartikel eine Ueberschrift?

eine Beweisskizze!

Nein, es war der komplette Beweis. Mir faellt grad auf, wenn f(n) = g(n) ist, dann ist trivialerweise f(n) = O(f(n)).

Natürlich noch mit dem ganzen Tohuwabohu.

Bis auf Antwortsatz fehlt nix. Btw. bei mir war es ueblich, Funktionsparameter im Induktionsbehauptung/-schritt anders zu benennen. Da du ja erstmal nur zeigst, das aus f(k) = g(k) nur f(k+1) = g(k+1) folgt, das ist schon verschieden von f(n) = g(n) fuer alle n aus N.

aber wie würde ich hier die Induktion vollbringen?

n einfach 2^k setzen. Induktion bedeutet nicht immer von n nach n+1, hier muss von n nach 2n gegangen werden, da f nur Argumente aus N entgegennimmt.

IA: *hoffentlich bei 1 startend* f(1) = 0; g(1) = 10 log 1 = 0; => f(1) = g(1)
IB: f(2^k) = ... = g(2^k)
IS: f(2^(k+1)) = f(2^k) + 10 = g(2^k) + 10 = 10 log 2^k + 10 = 10k + 10 = 10(k+1) = 10 (k+1) log 2 = 10 log 2^(k+1) = g(k+1)

Nun, jetzt gilt es streng genommen nicht mehr fuer alle n aus N. Macht aber nix, da f: N -> N abbildet und gar keine anderen Werte eigentlich zulaessig sind. Ausserdem kann gegebenes n durch die naechste Zweierpotenz nach oben bzw. unten abgeschaetzt werden.

[Jester]

Das abschätzen des parameters nützt aber nur was, wenn du schon weißt dass f monoton ist. Hier fehlen imo zu viele infos als dass man irgendwas anderes als 2er-Potenzen sinnvoll einsetzen kann.