Theta Notation < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 19:41 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
ps: Ja ich weiß dummer student kriegt mal wieder den letzten beknackten schritt nicht hin -.-
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:49 Do 17.10.2013 | | Autor: | Diophant |
Hallo DieNase,
auch wenn matux zugeschlagen hat: dies ist ein Doppelpost zu diesem Thread. Bitte setlle dort eine weitere Frage, die signalisiert, dass du noch an einer Lösung interessiert bist.
Gerne werden wir auch, wenn du es selbst versäumt hast, dabei behilflich sein, für Fragen angemessene Laufzeiten einzustellen. Frage dazu einfach irgendeinen anwesenden Moderator.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:54 Do 17.10.2013 | | Autor: | DieNase |
Da sich keiner aus dem Informatik bereich gemeldet hat. Dachte ich mir vlt. kann mir ein Mathematiker helfen. Es eilt auch nicht wenn ich wüsste wie würd ich die Deadline auch nach oben setzen. Ich finde die funktion bloß leider nicht. Es handelt sich um eine Übung die ich nächste woche donnerstag abgeben muss. Ich arbeite nur vor.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:56 Do 17.10.2013 | | Autor: | Diophant |
Hallo,
stelle bitte im alten Thread eine neue Frage, damit dieser wieder in der Liste der aktuellen Fragen auftaucht. Bei Erstellen einer Frage kannst du die Laufzeit einstellen. Wenn das nicht klappt, wie gesagt: daran soll es nicht scheitern.
Das mit den Doppelpostings steht ja auch alles in den Forenregeln. 
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:24 Do 17.10.2013 | | Autor: | DieNase |
Also kannst du das ding hier dann löschen? Habs wieder ins Informatik forum gestellt ^^ Und danke für die Antwort.
|
|
|
| |
|
Ich habe am ursprünglichen Thread jetzt eine Antwort
angefügt !
LG , Al-Chw.
|
|
|
|
