4. Komplexitätstheorie (2) - rekursive Funktionen

Komplexitätstheorie (2) - rekursive Funktionen

  • K

    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.

    0
  • S

    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:N→Ng, f : \mathbb{N} \rightarrow \mathbb{N} definiert als
    g(n)=10ng(n) = 10n
    f(n)=f(n−1)+10f(n) = f(n-1) + 10 wobei f(0) = 0.

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

    ⇒f(n)=O(g(n))⋁g(n)=O(f(n))\Rightarrow f(n) = O(g(n)) \bigvee g(n) = O(f(n))

    ⇒∃n_0,n_1∈N, c,d∈R∀n≥n_0 f(n)≤cg(n)⋁∀n≥n_1 g(n)≤df(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=1c = d = 1 und n_0=n_1=0n\_0 = n\_1 = 0, dann ist zu zeigen dass
    f(n)=g(n)=10nf(n) = g(n) = 10n

    Beweis:

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

    Nun ist zu zeigen, dass aus f(n)=g(n)f(n) = g(n) auch f(n+1)=g(n+1)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)⇔f(n)+10=g(n)+10f(n+1)=g(n+1) \Leftrightarrow f(n) + 10 = g(n) + 10. Und diese Gleichung gilt bei der Voraussetzung f(n)=g(n)f(n)=g(n).
    Damit gilt ∀ng(n)=f(n)\forall n \quad g(n)=f(n).

    0
  • K

    sauber aufgeschrieben

    Nee!

    0
  • S

    knivil schrieb:

    sauber aufgeschrieben

    Nee!

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

    0
  • S

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

    0
  • J

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

    0
  • S

    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)f(n) = g(n).

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

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

    Es kann die Gleichung f(n+1)=g(n+1)f(n+1) = g(n+1) folglich durch
    f(n)+10=g(n)+10f(n) + 10 = g(n) + 10
    ersetzt werden. Subtrahiert man nun 10, ergibt sich
    f(n)=g(n)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)⇒f(2)=g(2)⇒...f(n)=g(n)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)f(n) = g(n).

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

    0
  • J

    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. 😉

    0
  • S

    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),wobeif(0)=1f(n) = 2f(n-1), wobei f(0) = 1
    Das Gegenstück ist, soweit ich sehe,
    g(n)=2ng(n) = 2^n

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

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

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

    Natürlich noch mit dem ganzen Tohuwabohu.

    0
  • J

    ja genau. viel mehr brauchts auch gar nicht.

    0
  • S

    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(n2)+10f(n) = f(\frac{n}{2}) + 10
    Der ist noch einfach (10log2(n)10 log_2(n)), aber wie würde ich hier die Induktion vollbringen? Einsetzen von n+1 ergibt:

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

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

    0
  • J

    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.

    0
  • K

    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.

    0
  • J

    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.

    0
Anmelden zum Antworten