MatheFrage

10 Beiträge17.10.2007Archiviert
movco17.10.2007 · Beitrag #15119
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
Beweisen oder widerlegen sie

ln(n!) = O(Thetanotation)(nln(n))

Hoffe jemand hat schnell eine Lösung LG! Mir fehlt ein kleiner Hinweis!


LG
Shader17.10.2007 · Beitrag #15121
Avatar
Mitglied seit: 19.06.2006
Forenbeiträge: 432
Besuche: 4083
? Mathe LK oder was...?
movco17.10.2007 · Beitrag #15122
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
LK???

Vorlesungsübung/Aufgabe Datenstrukturen und Algorithmen!
Shader17.10.2007 · Beitrag #15123
Avatar
Mitglied seit: 19.06.2006
Forenbeiträge: 432
Besuche: 4083
LK = Leistungskurs
movco17.10.2007 · Beitrag #15124
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
Uni Vorlesung! Einfach nur Notationslehre quasi! Die woche halt! Und da die Aufgabe! Habe aber ka wie ich das lösen soll! Die anderen habe ich ja gelöst aber da komm ich mit dem n! nicht zammen
janheisterkamp17.10.2007 · Beitrag #15126
Mitglied seit: 01.04.2006
Forenbeiträge: 490
Besuche: 1305
Es geht doch bei n! um ein Faktorial [sagt man auf deutsch auch so?] von einem nicht negativen ganzheitlichen Wert, siehe auch http://en.wikipedia.org/wiki/Factorial, dann haben wir die Big O Notation, also Obergrenze aus Theta n

Wenn n= 2 ist dann ist behält n! den gleichen Wert

Also log 2 = O (Theta 2) * 2*(log2)

Ich muss dabei darauf hinweisen, das ich schon seit 1000 Jahren aus der Schule bin, immer einer der miesesten Matheschueler war und die einzige exzellente Matheklausur in meinem Leben, Trigonometrie, unter dem Einfluss einer sauberen Dosis LSDs geschrieben habe- trotzdem glaube ich nicht völlig falsch zu liegen...

Wenn Theta(n) = 2 ist, dann folgt Theta(2) < 2n log(2)
Vllt hilft Dir folgender Link weiter:
http://mathforum.org/library/drmath/view/51527.html

saludos
Jan


[ Bearbeitet Mi, 17. Okt 2007, 18:48 ]
movco17.10.2007 · Beitrag #15127
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
Das ist schon korrekt!

dann ist für Onotation und für Deltanotation bewiesen, dass es für n=2 gilt! Aber ich benötige leider einen allgemeinen Beweis bzw. eine einzelne Widerlegung! Widerlegen muss ich nicht, denn laut Maple ist es korrekt! Dh. ich muss doch 2 Grenzen finden. dh zB. 1/2 und 1.

c1 = 1/2, c2 = 1

dh. c1 * g(n) <= f(n) <= c2 * g(n)

gut sage ich nun 1/2 * nln(n) <= ln(n!) .... (Beta-notation)
muss ich weiter rechnen. Aber da komme ich mit dem Beweis nicht weiter.

Bei ln(n!) <= nln(n) .... (O-noation)

Da kann ich mit dem Limes arbeiten und dieser geht gegen 0. Dh. damit gilt das 0 < Unendlich ist und die O-noatiton bewiesen ist. Aber bei Beta-notation geht der Limes leider gegen Unendlich und so kann man das nicht beweisen. Da hänge ich halt gerade!

LG
info-man17.10.2007 · Beitrag #15128
Mitglied seit: 04.04.2007
Forenbeiträge: 33
Besuche: 446
ln(n!) ist ja ln(n) + ln(n-1) + ln(n-2) + ... + ln(1). verallgemeinert ist das dann für O: O(ln(n)) + O(ln(n-1)) + ... + O(ln(1)). -> höchstens so schnell wie n * O(ln(n)) also O(nln(n))
jetzt musst du noch zeigen, dass es mindestens so schnell wächst:
Da sollte es am leichtesten laufen, wenn du die Formel
lim inf n->unendl |ln(n!)|/|nln(n)| = |ln(n!-n)|/n und das ist immer > 0
janheisterkamp17.10.2007 · Beitrag #15130
Mitglied seit: 01.04.2006
Forenbeiträge: 490
Besuche: 1305
immer...!:D
movco17.10.2007 · Beitrag #15133
Avatar
Mitglied seit: 08.10.2007
Forenbeiträge: 264
Besuche: 1383
ja da ist ja nicht das problem sondern umgekehrt wie soll ich umgekehrt beweisen das was du meinst so beweist man die o notation |ln(n!)|/|nln(n)| mit Limes noch aber umgekehrt funkt es mit Limes nicht!