Master Theorem < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:44 Mi 16.01.2013 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | | $T(n) = \sqrt{2} T\left(\frac{n}{2}\right) + log(n)$ |
Generell gilt: a=\sqrt{2}, b=2 und $f(n) = log_2(n)$
1. Fall:
$f(n) \in O\left(n^{log_b(a)-\epsilon}\right)$
$n^2 \in O\left(n^{log_2(\sqrt{2})-\epsilon}\right)$ mit $\epsilon=\frac12$ das ist wie gefordert >0
Nun Grenzwertbildung wie in Wikipedia für die obere Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=log_2(n)$ und $g(n):=1$.
$\Rightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{log_2(n)}{1} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \underbrace{\limsup_{n \to \infty} \left(\left| log_2(n) \right|\right)}_{\to \infty} < \infty$
Widerspruch! Unendlich ist nicht echt kleiner als Unendlich! Also trifft erster Fall nicht zu.
2. Fall:
$f(n) \in \Theta\left(n^{log_b(a)}\right)$
$n^2 \in \Theta\left(n^{log_2(\sqrt{2})}\right)$
Nun Grenzwertbildung wie in Wikipedia für die exakte Scharfe Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=log_2(n)$ und $g(n):=\sqrt{n}$.
$\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{log_2(n)}{\sqrt{n}}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{log_2(n)}{\sqrt{n}} \right|\right) < \infty$
$\overbrace{\Leftrightarrow}^{l'H} 0 \leq \liminf_{n \to \infty} \left(\left| \frac{2}{n^{\frac32}\cdot ln(2)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{2}{n^{\frac32}\cdot ln(2)}} \right|\right) < \infty$
Der Fall ist richtig da beide limes gegen 0 gehen!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:32 Mi 16.01.2013 | | Autor: | Helbig |
Hallo bandchef,
> [mm]T(n) = \sqrt{n} T(\frac{n}{2} + log(n)[/mm]
> Generell gilt:
> [mm]a=\sqrt{2},[/mm] b=2 und [mm]f(n) = log_2(n)[/mm]
>
Dies ist wohl ein Tippfehler: Wir untersuchen $T(n) = [mm] \sqrt{2} T\left({n \over 2 }\right)+ \log n\,.$
[/mm]
> 1. Fall:
> [mm]f(n) \in O\left(n^{log_b(a)-\epsilon}\right)[/mm]
> [mm]n^2 \in O\left(n^{log_2(\sqrt{2})-\epsilon}\right)[/mm] mit
> [mm]\epsilon=\frac12[/mm] das ist wie gefordert >0
Wo kommt das [mm] $n^2$ [/mm] her?
Es ist doch [mm] $\log_2\sqrt [/mm] 2 = {1 [mm] \over 2}\,.$
[/mm]
Im ersten Fall müssen wir demnach ein [mm] $\epsilon [/mm] > 0$ finden, für das
[mm] $\log [/mm] n [mm] \in O(n^{1/2-\epsilon})$
[/mm]
gilt.
Aus Ana1 wissen wir, daß diese Bedingung z. B. für [mm] $\epsilon [/mm] = 1/4$ erfüllt ist.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:14 Do 17.01.2013 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Generell gilt: a=\sqrt{2}, b=2 und $f(n) = log_2(n)$ (Ich gehe übrigens bei log(n) von log_2(n) aus$
1. Fall:
$f(n) \in O\left(n^{log_b(a)-\epsilon}\right)$
$log(n) \in O\left(n^{log_2(\sqrt{2})-\epsilon}\right)$ mit $\epsilon=\frac12$ das ist wie gefordert >0
$log(n) \in O\left(n^{\frac12-\epsilon}\right)$
Wie finde ich hier nun raus welche \epsilon passen könnte? Ich meine, es könnte ja irgendein \epsilon geben dass in der Potenz dem log(n) gleichkommt, oder? Du schreibst, dass $log(n) = n^{\frac14}$ sein soll. Irgendwie stimmt das bei mir nicht, denn: $log_2(4) = 2$ aber 2^{\frac14} = 1,414$... Deswegen nun dennoch diese Grenzwertbildung:
Nun Grenzwertbildung wie in Wikipedia für die obere Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=log_2(n)$ und $g(n):=1$.
$\Rightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{log_2(n)}{1} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \underbrace{\limsup_{n \to \infty} \left(\left| log_2(n) \right|\right)}_{\to \infty} < \infty$
Widerspruch! Unendlich ist nicht echt kleiner als Unendlich! Also trifft erster Fall nicht zu.
2. Fall:
$f(n) \in \Theta\left(n^{log_b(a)}\right)$
$log(n) \in \Theta\left(n^{log_2(\sqrt{2})}\right)$
Nun Grenzwertbildung wie in Wikipedia für die exakte Scharfe Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=log_2(n)$ und $g(n):=\sqrt{n}$.
$\Rightarrow 0 > \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty$
$\Leftrightarrow 0 > \liminf_{n \to \infty} \left(\left| \frac{log_2(n)}{\sqrt{n}}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{log_2(n)}{\sqrt{n}} \right|\right) < \infty$
$\overbrace{\Leftrightarrow}^{l'H} 0 > \liminf_{n \to \infty} \left(\left| \frac{2}{n^{\frac32}\cdot ln(2)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{2}{n^{\frac32}\cdot ln(2)}} \right|\right) < \infty$
Der Fall ist richtig da beide limes gegen 0 gehen! Habe ich hier nun den 2. Fall richtig angewendet? Übrigens gleiche Frage wie in Aufgabe 1. Warum zwei verschiedene limes über ein und dasselbe Argument? Da kann doch nix anderes rauskommen, oder? Oder muss man diese zwei verschiedenen Limes in Gedanken anders ausführen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:16 Do 17.01.2013 | | Autor: | Helbig |
> Generell gilt: [mm]a=\sqrt{2},[/mm] b=2 und $f(n) = [mm]log_2(n)$[/mm] (Ich
> gehe übrigens bei log(n) von [mm]log_2(n)[/mm] aus$
>
> 1. Fall:
> [mm]f(n) \in O\left(n^{log_b(a)-\epsilon}\right)[/mm]
> [mm]log(n) \in O\left(n^{log_2(\sqrt{2})-\epsilon}\right)[/mm] mit
> [mm]\epsilon=\frac12[/mm] das ist wie gefordert >0
> [mm]log(n) \in O\left(n^{\frac12-\epsilon}\right)[/mm]
>
> Wie finde ich hier nun raus welche [mm]\epsilon[/mm] passen könnte?
Jedes [mm] $\epsilon$ [/mm] mit [mm] $0<\epsilon [/mm] < 1/2$ paßt hier, denn für solche [mm] $\epsilon$ [/mm] ist [mm] $\log [/mm] n [mm] \in O\left(n^{1/2-\epsilon}\right)\,.$ [/mm] Der Einfachheit halber habe ich [mm] $\epsilon [/mm] = 1/4$ gewählt. Damit ist die Bedingung für Fall 1 erfüllt, und wir sind fertig! Du verwechselst offensichtlich "für jedes [mm] $\epsilon [/mm] > 0$ " und "für ein [mm] $\epsilon [/mm] > 0$ ".
> Ich meine, es könnte ja irgendein [mm]\epsilon[/mm] geben dass in
> der Potenz dem log(n) gleichkommt, oder? Du schreibst, dass
> $log(n) = [mm]n^{\frac14}$[/mm] sein soll.
Nein, das schreibe ich nicht! Siehe oben!
> Irgendwie stimmt das bei
> mir nicht, denn: [mm]$log_2(4)[/mm] = 2$ aber [mm]2^{\frac14}[/mm] =
> 1,414$... Deswegen nun dennoch diese Grenzwertbildung:
>
> Nun Grenzwertbildung wie in Wikipedia für die obere
> Schranke angegeben. Ich definiere für die Grenzwertbildung
> [mm]f(n):=log_2(n)[/mm] und [mm]g(n):=1[/mm].
>
> [mm]\Rightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty[/mm]
> [mm]\Leftrightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{log_2(n)}{1} \right|\right) < \infty[/mm]
> [mm]\Leftrightarrow 0 \leq \underbrace{\limsup_{n \to \infty} \left(\left| log_2(n) \right|\right)}_{\to \infty} < \infty[/mm]
> Widerspruch! Unendlich ist nicht echt kleiner als
> Unendlich! Also trifft erster Fall nicht zu.
Falsch! Es gibt ein [mm] $\epsilon$, [/mm] so daß die Bedingung von Fall 1 erfüllt ist, nämlich [mm] $\epsilon [/mm] = [mm] 1/4\,.$ [/mm] Und das genügt!
>
>
> 2. Fall:
> [mm]f(n) \in \Theta\left(n^{log_b(a)}\right)[/mm]
> [mm]log(n) \in \Theta\left(n^{log_2(\sqrt{2})}\right)[/mm]
>
> Nun Grenzwertbildung wie in Wikipedia für die exakte
> Scharfe Schranke angegeben. Ich definiere für die
> Grenzwertbildung [mm]f(n):=log_2(n)[/mm] und [mm]g(n):=\sqrt{n}[/mm].
>
> [mm]\Rightarrow 0 > \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty[/mm]
> [mm]\Leftrightarrow 0 > \liminf_{n \to \infty} \left(\left| \frac{log_2(n)}{\sqrt{n}}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{log_2(n)}{\sqrt{n}} \right|\right) < \infty[/mm]
> [mm]\overbrace{\Leftrightarrow}^{l'H} 0 > \liminf_{n \to \infty} \left(\left| \frac{2}{n^{\frac32}\cdot ln(2)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{2}{n^{\frac32}\cdot ln(2)}} \right|\right) < \infty[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Was soll jetzt das bedeuten??? Ich kann da beim besten Willen nichts richtiges herauslesen.
>
> Der Fall ist richtig da beide limes gegen 0 gehen!
Der Limes ist hier gleich 0, also ist $\log n \notin \Theta\left(n^{\log_2(\sqrt 2)\right)\,.$ Schau Dir nochmal die Definition für die Menge $\Theta(g(n))$ an!
Fall 2 paßt hier jedenfalls nicht!
> Habe ich
> hier nun den 2. Fall richtig angewendet? Übrigens gleiche
> Frage wie in Aufgabe 1. Warum zwei verschiedene limes über
> ein und dasselbe Argument? Da kann doch nix anderes
> rauskommen, oder? Oder muss man diese zwei verschiedenen
> Limes in Gedanken anders ausführen?
Wir drehen uns hier im Kreis. Ich hatte die Frage schon mal beantwortet.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:16 Fr 18.01.2013 | | Autor: | bandchef |
Ich habe Fall 2 nur noch angefangen, weil ich eben nicht gedacht habe, dass ich schon bei Fall 1aufhören kann.
Warum ich das gemeint hab liegt daran weil ich das (auch jetzt) noch nicht verstanden hab:
> Jedes [mm] $\epsilon$ [/mm] mit [mm] $0<\epsilon [/mm] < 1/2$ paßt hier, denn für solche [mm] $\epsilon$ [/mm] ist [mm] $\log [/mm] n [mm] \in O\left(n^{1/2-\epsilon}\right)\,.$
[/mm]
Mit dieser Aussage wäre ja mit [mm] $0<\epsilon [/mm] < 1/2$ immer [mm] $\log [/mm] n [mm] \in O\left(n^{1/2-\epsilon}\right)\,.$.
[/mm]
Natürlich hast du Recht, denn es sollte ja mit [mm] $\epsilon [/mm] = [mm] \frac14$ [/mm] gelten:
[mm] $\Rightarrow [/mm] 0 [mm] \leq \limsup_{n \to \infty} \left( \left| \frac{log(n)}{n^{\frac14}} \right| \right) [/mm] < [mm] \infty$
[/mm]
[mm] $\overbrace{\Leftrightarrow}^{\text{l'H}} [/mm] 0 [mm] \leq \limsup_{n \to \infty} \left( \left| \frac{\frac{1}{n\cdot ln(2)}}{\frac14\cdot n^{-\frac34}} \right| \right) [/mm] = [mm] \limsup_{n \to \infty} \left( \left| \underbrace{\frac{1}{n\cdot ln(2)}}_{=0} \cdot \underbrace{\frac{4}{n^{-\frac34}}}_{=0} \right| \right) [/mm] < [mm] \infty$
[/mm]
So kann man wohl zeigen, dass Fall 1 wirklich stimmt, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:29 Fr 18.01.2013 | | Autor: | Helbig |
> Ich habe Fall 2 nur noch angefangen, weil ich eben nicht
> gedacht habe, dass ich schon bei Fall 1aufhören kann.
>
> Warum ich das gemeint hab liegt daran weil ich das (auch
> jetzt) noch nicht verstanden hab:
> > Jedes [mm]\epsilon[/mm] mit [mm]0<\epsilon < 1/2[/mm] paßt hier, denn für
> solche [mm]\epsilon[/mm] ist [mm]\log n \in O\left(n^{1/2-\epsilon}\right)\,.[/mm]
>
> Mit dieser Aussage wäre ja mit [mm]0<\epsilon < 1/2[/mm] immer [mm]\log n \in O\left(n^{1/2-\epsilon}\right)\,.[/mm].
Genau!
>
> Natürlich hast du Recht, denn es sollte ja mit [mm]\epsilon = \frac14[/mm]
> gelten:
>
> [mm]\Rightarrow 0 \leq \limsup_{n \to \infty} \left( \left| \frac{log(n)}{n^{\frac14}} \right| \right) < \infty[/mm]
>
> [mm]\overbrace{\Leftrightarrow}^{\text{l'H}} 0 \leq \limsup_{n \to \infty} \left( \left| \frac{\frac{1}{n\cdot ln(2)}}{\frac14\cdot n^{-\frac34}} \right| \right) = \limsup_{n \to \infty} \left( \left| \underbrace{\frac{1}{n\cdot ln(2)}}_{=0} \cdot \underbrace{\frac{4}{n^{-\frac34}}}_{=0} \right| \right) < \infty[/mm]
>
> So kann man wohl zeigen, dass Fall 1 wirklich stimmt, oder?
Ich denke mal, Du kannst einfach aus Ana1 übernehmen, daß [mm] $\limsup {\log n \over n^{1/4}}= \lim {\log n \over n^{1/4}} [/mm] = 0$ ist, unabhängig von der Basis des Logarithmus. Wenn Du das mit L'Hospital zeigen willst, beachte $0 < [mm] \log_a [/mm] n = [mm] \ln [/mm] n * [mm] \log_a [/mm] e$ für jedes [mm] $a>1\;.$
[/mm]
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:07 Fr 18.01.2013 | | Autor: | bandchef |
Ja, ich denke schon, dass ich sowas mit l'Hospital zeigen würde, weil nur so könnte ich mir in der Klausur wirklich sicher sein. Aber ich verstehe $ 0 < [mm] \log_a [/mm] n = [mm] \ln [/mm] n [mm] \cdot{} \log_a [/mm] e $ nicht so ganz.
Ist das einfach eine Umrechnung damit man den "richtigen Logarithmus" (nicht Logarithmus naturalis!) anders darstellen kann?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:50 Fr 18.01.2013 | | Autor: | Helbig |
> Ja, ich denke schon, dass ich sowas mit l'Hospital zeigen
> würde, weil nur so könnte ich mir in der Klausur wirklich
> sicher sein. Aber ich verstehe [mm]0 < \log_a n = \ln n \cdot{} \log_a e[/mm]
> nicht so ganz.
>
> Ist das einfach eine Umrechnung damit man den "richtigen
> Logarithmus" (nicht Logarithmus naturalis!) anders
> darstellen kann?
Ja! Wenn Du L'Hospital anwenden willst, mußt Du [mm] $\log_a [/mm] n$ ableiten, Du kennst aber nur die Ableitung von [mm] $\ln [/mm] n = [mm] \log_e n\,.$ [/mm]
Aber Du kannst in Deinen Herleitungen auch einfach [mm] $\log_2 [/mm] n$ durch [mm] $\ln [/mm] n$ ersetzen, da sich diese Funktionen nur um einen konstanten Faktor unterscheiden, der keinen Einfluß auf das Grenzwertverhalten hat.
Ist das eigentlich eine Analysis- oder eine Informatikvorlesung? Wenn es hier um Informatik geht, kannst Du getrost die Ergebnisse aus der Analysis verwenden, ohne sie etwa mit L'Hospital jedesmal herzuleiten. Benutze einfach [mm] $\lim {\log n \over n^\alpha} [/mm] = 0$ wenn [mm] $\alpha [/mm] > 0$ und $= [mm] \infty$, [/mm] wenn [mm] $\alpha \le 0\,.$ [/mm] Und wenn Du willst, kannst Du dies ja ein für allemal herleiten. Achtung: Für [mm] $\alpha \le [/mm] 0$ ist dies keine Anwendung von L'Hospital!
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:06 Fr 18.01.2013 | | Autor: | bandchef |
> Ja! Wenn Du L'Hospital anwenden willst, mußt Du [mm] $\log_a [/mm] n$ ableiten, Du kennst aber nur die Ableitung von [mm] $\ln [/mm] n = [mm] \log_e n\,.$
[/mm]
Hm, in meiner Formelsammlung steht aber für [mm] $(log_a(x))' [/mm] = [mm] \frac{1}{x \cdot ln(b)}...
[/mm]
Geht das nicht?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:17 Fr 18.01.2013 | | Autor: | Helbig |
> > Ja! Wenn Du L'Hospital anwenden willst, mußt Du [mm]\log_a n[/mm]
> ableiten, Du kennst aber nur die Ableitung von [mm]\ln n = \log_e n\,.[/mm]
>
> Hm, in meiner Formelsammlung steht aber für [mm]$(log_a(x))'[/mm] =
> [mm]\frac{1}{x \cdot ln(b)}...[/mm]
>
> Geht das nicht?
Du kannst bei Deinen Lösungen nicht alles verwenden, was in irgendeiner Formelsammlung steht und erwarten, daß der Leser, in diesem Fall ich, diese Formeln auswendig weiß!
Gruß,
Wolfgang
|
|
|
|
