Übung 6 - 6.3

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 6 - 6.3

Beitrag von Prof. Karsten Weihe »

sven.lohrmann hat geschrieben:Welche Basis ist eigentlich gemeint, wenn beim Logarithmus keine explizit angegeben ist?
Wie schon mehrfach gesagt und auch im Wiki geschrieben, ist die Basis des Logarithmus bei O-Notation irrelevant. Wenn Sie sich unbedingt eine Basis \(b\) vorstellen wollen, können Sie sich jede beliebige Zahl \(b>1\) hernehmen. Bei der Berechnung der Ableitung bietet es sich natürlich an, die Eulersche Zahl zur Basis zu machen.

KW

sven.lohrmann
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 26. Apr 2012 12:16

Re: Übung 6 - 6.3

Beitrag von sven.lohrmann »

Das sehe ich anders. Zum einen ist es für 6.3 relevant, um die Ableitung zu bilden (Ja ich weiß hier ist es irrelevant welche Basis gewählt wird, aber man muss es dennoch mathematisch korrekt aufschreiben). Zum anderen macht es doch einen unterschied welche Basis gegeben ist, wenn man bspw. \(log n^{2}\) mit \(e^{log log n^{2}}\) vergleicht. Ist die Basis < e wächst \(log n^{2}\) langsamer. Ist die Basis > e wächst \(log n^{2}\) schneller als \(e^{log log n^{2}}\) ...

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 6 - 6.3

Beitrag von Prof. Karsten Weihe »

sven.lohrmann hat geschrieben:Das sehe ich anders. Zum einen ist es für 6.3 relevant, um die Ableitung zu bilden (Ja ich weiß hier ist es irrelevant welche Basis gewählt wird, aber man muss es dennoch mathematisch korrekt aufschreiben).
Dazu hatte ich ja geschrieben, dass Sie bspw. die Eulersche Zahl hernehmen können.

sven.lohrmann hat geschrieben: Zum anderen macht es doch einen unterschied welche Basis gegeben ist, wenn man bspw. \(log n^{2}\) mit \(e^{log log n^{2}}\) vergleicht.
Edit: Ich sehe keinen Unterschied, der bei asymptotischen Betrachtungen relevant wäre.

KW

sven.lohrmann
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 26. Apr 2012 12:16

Re: Übung 6 - 6.3

Beitrag von sven.lohrmann »

Prof. Karsten Weihe hat geschrieben:Der Titel des Threads und somit meine Antwort bezieht sich auf 6.3...
Soll ich dafür dann jetzt einen anderen Thread aufmachen oder bekomme ich hier noch ein Antwort dazu?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 6 - 6.3

Beitrag von Prof. Karsten Weihe »

sven.lohrmann hat geschrieben: Soll ich dafür dann jetzt einen anderen Thread aufmachen oder bekomme ich hier noch ein Antwort dazu?
Siehe Edit meines letzten Postings.

KW

sven.lohrmann
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 26. Apr 2012 12:16

Re: Übung 6 - 6.3

Beitrag von sven.lohrmann »

Hm... \(e^{log log n^{2}}\) kann man ja schreiben als \((log n)^{2*log e}\) wenn man das jetzt mit \((log n)^{2}\) vergleicht macht es schon einen Unterschied was die Basis ist und ob der Exponent somit > oder < 1 ist, denn je nachdem wächst die eine oder die andere Funktion schneller. Der Quotient beider Funktionen ist ja zudem, wie ich das sehe, keine Konstante, wie es bspw. in Regel 10 im Wiki der Fall ist, wodurch ja erst die Basis irrelevant wird.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 6 - 6.3

Beitrag von Prof. Karsten Weihe »

Mein Ansatz ist Folgender. Sei \(b\) die Basis des äußeren Logarithmus in \(e^{\log_b\log n^2}\). Durch Einführung eines konstanten Vorfaktors im Exponenten kann ich Basis \(b\) durch Basis \(e\) ersetzen. Und dann habe ich die Logarithmengesetze angewandt, um diesen Ausdruck möglichst nah an den Ausdruck \(\log n^2\) zu bringen.

KW

sven.lohrmann
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 26. Apr 2012 12:16

Re: Übung 6 - 6.3

Beitrag von sven.lohrmann »

Ah ich glaube jetzt steig ich dahinter, danke :)

jan789
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2012 21:38

Re: Übung 6 - 6.3

Beitrag von jan789 »

Ich hänge momentan an derselben Funktion.
Mein momentaner Stand ist: \((\log n^2)^{(1/\ln a)}\). a ist die Basis, die bleibt, wenn ich den natürlichen Logarithmus benutzen möchte. Nun ist die Einordnung der Funktion aber immer noch von a abhängig...
Kann mir hier eventuell jmd. auf die Sprünge helfen?

Danke & Gruß
Jan :)

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: Übung 6 - 6.3

Beitrag von derJan2 »

Ist vielleicht eine blöde Frage, aber ich bin mir inzwischen unsicher, wie der Ausdruck in der Aufgabenstellung 6.3 gemeint ist:
1. (log)^k (n), d.h. für k=2 log(log(n)) oder
2. (log (n))^k, d.h. für k=2 (log(n))^2 ?
Gruß, derJan2

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Übung 6 - 6.3

Beitrag von JannikV »

letzteres

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: Übung 6 - 6.3

Beitrag von derJan2 »

vielen Dank!

gugugs
Neuling
Neuling
Beiträge: 2
Registriert: 28. Mai 2012 16:48

Re: Übung 6 - 6.3

Beitrag von gugugs »

in der Aufgabenstellung steht
"Hinweis: L'Hopitalsche Regel aus der Vorlesung und vollstandige Induktion uber k."
Das mit der L'Hopitalsche Regel verstehe ich ja, aber was ist mit vollstandiger Induktion uber k gemeint? Das verstehe ich überhaupt nicht?
In der Vorlesung wurde eine Induktion über Bucketsort(war es glaube ich?) durchgeführt, aber nicht allgemein über so einen formalen Ausdruck.
Kann mir jemand hier vielleicht eine Hilfestellung geben?

Danke

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Übung 6 - 6.3

Beitrag von JannikV »

Aufgabe ist ja zu zeigen, dass die Aussage für jedes \(k \in \mathbb{N}\) gilt. Nun gibt es aber unendlich viele natürliche Zahlen und es für jede einzeln zu beweisen könnte ein Weilchen dauern. ^^
In solchen Fällen nutzt man für seinen Beweis die sog. vollständige Induktion (hier über die natürlichen Zahlen).

Das Prinzip ist dabei folgendes:
Induktionsanfang: Wir zeigen per Hand dass die Aussage für ein möglichst kleines k gilt.
Induktionsvorraussetzung: Angenommen für ein \(k \in \mathbb{N}\) gilt die Aussage so-und-so.... (hier gibts nichts zu tun, da steht immer nur dieser Satz)
Induktionsschritt: Wir schreiben den Term mal hin, aber statt k schreiben wir k+1. Der Trick ist dann zu zeigen, dass wenn die Aussage für k gilt, sie auch für k+1 gilt. Dazu formt man so lange um bis man k+1 irgendwie in "irgendwas mit k" und "irgendwas mit 1" trennen kann. Dass es für k gilt wurde angenommen und dass es mit dem Rest wo die 1 dabei ist immer noch gilt musst du dann zeigen.

So ist dann gezeigt, dass es für jede natürliche Zahl gilt.
Oh je, ich frage mich ob das verständlich war. Ziemlich kompliziert zu erklären.

Ich mache dir mal ein kleines Beispiel, das wir neulich in Mathe hatten:

Zu zeigen: Für alle \(a \in \mathbb{N}\) gilt \(ln(x^a) = a*ln(x)\)
Induktionsanfang: Für a = 1 gilt \(ln(x^1) = ln(x) = 1 * ln(x)\)
Induktionsvorraussetung: Für ein \(a \in \mathbb{N}\) gelte \(ln(x^a) = a*ln(x)\).
Induktionsschritt: Nach Umformungsregeln gilt \(ln(x^{a+1}) = ln(x^a * x) = ln(x^a) + ln(x)\) und das ist nach Induktionsvorraussetzung \(a * ln(x) + ln(x) = (a+1) * ln(x)\).
q.e.d.

Und bei der Hausaufgabe fängst du halt an es für k = 1 zu zeigen, nimmst dann an es gilt für ein k und zeigst dass es auch für k+1 gilt wenn es bereits für k gilt.

Hoffe es hilft.

VG

gugugs
Neuling
Neuling
Beiträge: 2
Registriert: 28. Mai 2012 16:48

Re: Übung 6 - 6.3

Beitrag von gugugs »

vielen dank

Antworten

Zurück zu „Archiv“