Landau Notation / O-Notation

Neue Frage »

seppi79 Auf diesen Beitrag antworten »
Landau Notation / O-Notation
Meine Frage:
Hallo,

Ich habe einige Aufgaben zur Landau-Notation bearbeitet. Da ich mir jedoch nicht sicher bin, wäre es sehr nett wenn mal jemand drüber schauen würde.

Vielen Dank.

Meine Ideen:
Zu zeigen:

meine Bearbeitung:

für gilt
seppi79 Auf diesen Beitrag antworten »

Da ich leider Schwierigkeiten mit dem Formeleditor habe, habe ich es jetzt einfach abfotografiert.


http://i1381.photobucket.com/albums/ah221/niemandsmann/123_zpsu5oantzc.jpeg
 
 
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

wie habt ihr denn die O-Notation definiert?
Und was genau ist hier zu beweisen?
Denn
Zitat:
Zu zeigen:
würd ich als festes n interpretieren, dazu passt deine BEgündung nicht.

P.S. Du kannst (und solltest sinnvollerweise) Bilder hier auch direkt hochladen (Button unterhalb des Eingabefensters).
seppi79 Auf diesen Beitrag antworten »

Hallo, danke für deine Antwort.

Habe die Definition angehangen.
Captain Kirk Auf diesen Beitrag antworten »

O.k. dann passts.

Die c) funktioniert so nicht, g ist eine Abbildung keine natürliche Zahl.
Bei d) und e) sehe ich bei gutem Willen Beweisskizzen, beides kann ich aber nicht wirklich nachvollziehen. (evtl. liegt es auch daran, dass ich es falsch lese.)
seppi79 Auf diesen Beitrag antworten »

Danke für deine Rückmeldung. Ich denke nochmal drüber nach.
seppi79 Auf diesen Beitrag antworten »

zu der c) habe ich noch folgende Idee:

es ist gegeben, dass folgendes gilt:

ich will zeigen, dass gilt.

nun wähle ich k = c und N=1 und erhalte

Es wäre nett, wenn du mir nochmal eine Anregung geben könntest. Danke.
Captain Kirk Auf diesen Beitrag antworten »

Machen wir mal ein Beispiel, und zwar dass aus der a):

Dann gilt laut dir: für alle n>1.

Wobei mir grade kommt: Was ist hier eigentlich x?
seppi79 Auf diesen Beitrag antworten »

Danke für deine Antwort. X ist in der Aufgabe nicht definiert.

Dein Gegenbeispiel leuchtet mir ein. Ich tue mich schwer, einen Beweisansatz zu finden.

Was mir noch einfällt ist

Dann könnte man nutzen, dass ist, also .

Dann setze ich das ein.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
X ist in der Aufgabe nicht definiert.
Bitte gib doch mal die exakte Aufgabenstellung wieder.
Und Mathematik ist case-sensitive, Groß -und Kleinschreibung macht auch beivariablen/Konstanten etc. einen Unterschied.

Zitat:
Und was hat das mit der Fragestellung zu tun?

Ich zeig es dir hier einmal an diesem Beispiel:
Es ist , d.h. es gibt ein Konstante k und eine natürliche Zahl N mit .
Damit gilt für alle : .
seppi79 Auf diesen Beitrag antworten »

Danke für deine Hilfestellung. Kann es sein, dass dir in der 2. Zeile von unten ein Tippfehler unterlaufen ist und du am Ende n größer gleich N meinst? Ich überlege mal für die anderen Aufgaben.
Captain Kirk Auf diesen Beitrag antworten »

Ja, das war das falsche Ungleichungszeichen.

Die a) ist ungut formuliert. Ich ging gestern wohl davon aus, dass
gemeint ist, es kann aber (und ist wahrscheinlich sogar so) auch gemeint sein.
Man kann beides reininterpretieren.
seppi79 Auf diesen Beitrag antworten »

Danke für deine Hilfestellung.

zur f) habe ich nun folgendes. Laut Aufgabe gilt: und
.



zur e): gilt dasselbe wie für f.

Hier fehlt mir aber noch die Idee, wie ich das fasse, da ich wenn ich c=k wähle einschränke und das daher m.W. nicht darf.
Captain Kirk Auf diesen Beitrag antworten »

Die f) passt. Wobei du noch an das "genügend groß", das für alle n größer N denken musst.

Zur e): Natürlich kannst du nicht einfach c=k setzen, genausowenig wie du 2=4 setzen kannst. (das sind mögliche Werte für c und k)
Du suchst ein C mit .
Da sollte sich eines finden lassen.
seppi79 Auf diesen Beitrag antworten »

Danke nochmals für das Aufzeigen. So langsam wird es mir klarer. Nun müsste ich doch C = c+k wählen können, womit die Ungleichung ja erfüllt wäre, oder?
Captain Kirk Auf diesen Beitrag antworten »

Ja, das ist eine Möglichkeit.
seppi79 Auf diesen Beitrag antworten »

Ich habe mich noch einmal an einer Aufgabe versucht. Es wäre sehr hilfreich, wenn du mir hierzu nochmals Rückmeldung geben könntest. Vielen Dank im Voraus.

(Der Einfachheit halber hochgeladen, da der Formeleditor wesentlich mehr Zeit benötigt).
Captain Kirk Auf diesen Beitrag antworten »

Soweit ich es entziffern kann ist die Beweisidee richtig.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »