Theta Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:40 Di 15.10.2013 | | Autor: | DieNase |
| Aufgabe | | Beweisen oder widerlegen Sie, dass [mm] \summe_{i=1}^{n} log_{2} [/mm] i = [mm] \odot(n [/mm] * [mm] log_{2} [/mm] n) |
forweg ich hab leider kein beseres zeichen für Theta gefunden...
Also wenn ich die Summe schätze sage ich jeder summant ist kleiner oder gleich [mm] log_{2} [/mm] n und es gibt n summanten. Daher kann ich sagen das [mm] n*log_{2} [/mm] n eine obere schranke ist. Jetzt muss ich noch beweisen das es auch eine untereschranke ist. Wobei das ganze ja so definiert ist das f(n) >= c * g(n) sein. Ich dachte mir das es nicht stimmt und das n * [mm] log_{2} [/mm] n definitif keine untere Schranke ist. Also hab ich folgendes gemacht ich habe c <= f(n) / g(n) für n = 3 gerechnet und da kam 0.545 heraus. Anschließend hab ich es für n = 4 gerechnet da kam dann 0.575 heraus. Und für 5 sogar 0,595 für c....
Also muss ich wohl auf dem Holzweg sein. Es gibt also ein c. Mein Problem ist jetzt folgendes. Ich muss das ganze jetzt beweisen bzw. zeigen das es eine Untere schranke ist. Ich weiß bloß nicht wie. Drum wollte ich hier mal fragen ob mir jemand helfen kann und mir ein tipp / idee geben kann.
mfg
Christoph
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Do 17.10.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:22 Do 17.10.2013 | | Autor: | DieNase |
| Aufgabe | | Beweisen oder widerlegen Sie, dass [mm] \summe_{i=1}^{n} log_{2} [/mm] i = [mm] \odot(n [/mm] * [mm] log_{2} [/mm] n) |
Da ich nicht davon ausgehe das ein Mathematiker weiß was die Theta Notation ist möchte ich zuerst die Definition posten:
Hab leider kein theta gefunden!
f(n) = Theta(g(n)) [mm] \gdw [/mm] Es existiert ein [mm] c_{1}, c_{2} \in \IR; n_{0} \in \IN; [/mm] : f(n) [mm] \ge [/mm] c2 * g(n), f(n) [mm] \le [/mm] c1 * g(n) für alle n [mm] \ge n_{0}
[/mm]
Also ich muss zeigen das es ein c1, c2 gibt, dann wäre es eine exakte schranke die abschätzung nach oben war ganz einfach n * log(n) ist auf jedenfall größer als die summe von log(n). die summe bis n von log(i) ist aufjedenfall kleiner als n * log(n). Das klar.
Das problem ist ich dachte mir das n* log(n) nicht eine untereschranke ist. Danach hab ich folgende dinge probiert:
c2 [mm] \le [/mm] f(n) / g(n). Meine Vermutung war jetzt das n*log(n) mit größer werdendem n schneller wächst. (Ja meine annahme war dumm natürlich andersrum)
Gut ich bin dann schnell drauf gekommen als ich ein beweis durch beispiel probiert hab und gedacht hab ich nehme n = 3 und dann n = 4. Ich weiß also das der wert der raus kommt bei größer werdendem n immer kleiner wird. Insofern wäre c2 für [mm] n_{0} [/mm] = 3 das c2 damit n * log(n) die untere schranke wäre.
Soviel dazu. Jetzt mein Problem. Wie in aller welt kann ich das beweisen???
Wäre ein Induktions beweis leicht möglich mit dem ansatz g(n) >= f(n) Basis wäre 3.
Oder gibts hier ein leichteren weg den ich net sehe?
Wie könnte ich durch widerspruch es zeigen. Dann müsste ich die annahme treffen das es kein c2 gibt. Doch wie dann weiter wie müsste ich meine Formel ansetzen?
mfg
Christoph
|
|
|
| |
|
Die Antwort habe ich schon angefügt, aber halt als
bloße "Mitteilung" .
|
|
|
| |
|
> Beweisen oder widerlegen Sie, dass [mm] $\summe_{i=1}^{n} log_{2}i\ [/mm] =\ [mm] \odot (log_{2}*n)$
[/mm]
> Da ich nicht davon ausgehe das ein Mathematiker weiß was
> die Theta Notation ist möchte ich zuerst die Definition
> posten:
>
> Hab leider kein theta gefunden!
>
> f(n) = Theta(g(n)) [mm]\gdw[/mm] Es existiert ein [mm]c_{1}, c_{2} \in \IR; n_{0} \in \IN;[/mm]
> : f(n) [mm]\ge[/mm] c2 * g(n), f(n) [mm]\le[/mm] c1 * g(n) für alle n [mm]\ge n_{0}[/mm]
So nebenbei:
Was diese Notation (richtig notiert mit einem großen " [mm] $\mathcal{O}$ [/mm] "
oder einem kleinen " o " ) bedeutet, wissen Mathematiker
sehr wohl, denn es ist eine mathematische Notation !
Es gibt sehr wohl manche Teilgebiete der Informatik,
die eigentlich Unterabteilungen mathematischer Gebiete
sind.
http://de.wikipedia.org/wiki/Landau-Symbole
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:15 Fr 18.10.2013 | | Autor: | DieNase |
Also ich hab jetzt alles ausgerechnet, Aber wie gesagt das eine problem bleibt. Ich muss zeigen das die differenz zwischen der Summe und n*log(n) immer kleiner wird. Und nicht größer wird mit wachsendem n.
Denn es gibt ein c so das c * g(n) <= f(n) ist.
Ich dachte mir zuerst das könne nicht sein ist aber leider so. Insofern steh ich vor einem Problem das ich so net lösen kann. die stirlingformel haben wir noch nie verwendet und werden das auch net (laut skriptum) insofern denke ich muss man das Beispiel auch anders lösen können.
Wenn die differenz zwischen f(n) und g(n) immer kleiner wird müsste doch eine lim f(n)/ g(n) Betrachtung gegen unendlich gegen 1 gehen. Oder irre ich mich da jetzt? Wäre dies ein Aussreichender Beweis oder müsste ich noch mehr machen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:59 Fr 18.10.2013 | | Autor: | felixf |
Moin!
> Also ich hab jetzt alles ausgerechnet, Aber wie gesagt das
> eine problem bleibt. Ich muss zeigen das die differenz
> zwischen der Summe und n*log(n) immer kleiner wird. Und
> nicht größer wird mit wachsendem n.
Nein, das musst du eben nicht. Du musst den Quotienten der beiden betrachten und nicht deren Differenz.
> Denn es gibt ein c so das c * g(n) <= f(n) ist.
>
> Ich dachte mir zuerst das könne nicht sein ist aber leider
> so.
Wieso leider? :)
> Insofern steh ich vor einem Problem das ich so net
> lösen kann. die stirlingformel haben wir noch nie
> verwendet und werden das auch net (laut skriptum) insofern
> denke ich muss man das Beispiel auch anders lösen können.
Klar. Es gibt immer viele Moeglichkeiten.
> Wenn die differenz zwischen f(n) und g(n) immer kleiner
> wird müsste doch eine lim f(n)/ g(n) Betrachtung gegen
> unendlich gegen 1 gehen. Oder irre ich mich da jetzt?
Ja. Das ist hier aber nicht der Fall.
Du musst einfach zeigen, dass $f(n) / g(n)$ weder beliebig gross noch beliebig klein werden kann.
> Wäre
> dies ein Aussreichender Beweis oder müsste ich noch mehr
> machen?
Du hast nichts bewiesen, du hast nur die eine Behauptung umformuliert in eine andere Aussage, die du nicht bewiesen hast.
Versuch es doch ueber den Integral-Ansatz. Du kannst [mm] $\sum_{i=1}^n \log_2 [/mm] i$ durch zwei Integral nach oben und unten abschaetzen, und du kannst diese beiden Integrale explizit ausrechnen. Sie haben beide den Wert $n [mm] \log_2 [/mm] n$ plus/minus etwas "kleines".
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:59 So 20.10.2013 | | Autor: | DieNase |
Mich würde interessieren was du mit integral abschätzen meinst!
Soll das heißen ich soll ein integral von z.b. n/2 - n machen [mm] log_{2}(i) [/mm] und einmal integral 1 - n/2?
und soll ich dann n*logn ins verhältnis setzen ????? So ganz ist mir dein Ansatz nich geläufig wie das geht was du von mir vorderst zum Beweis :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Mi 23.10.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](/images/popup.gif){kind=small}
Landau-Symbole