Algorithmen[1]#1

[CansaSCity]

als erste prüfst du auf O und dann auf Omega . Bsp zu O : hier stellst "befreist" du c vom rest, so dass du c auf einer seite hast. . Wenn jetzt n gegen undenlich läuft, strebt gegen 1 . D.h. du hast eine obere Schranke c => es liegt in O(n^b) . Genauso machst du es auch mit Omega

Dafür musst du aber noch nachweisen dass monoton steigend ist, sonst funktioniert dein Beweis nicht

[Thomas]

es reicht wenn man zeigt dass (n+a/n)^b gegen 1 geht und da is ja egal ob a negativ ist und wie groß a ist, zumindest bin ich der meinung dass, das reicht weils somit auf jeden fall ein c gibt dass größer bzw ein c' dass kleiner (n+a/n)^b ist
weil hier mal nach gegenbeispielen zu e) und f) gefragt wurde.
also bei e) hab ich f(n) = 2n und g(n) = n und bei der f) f(n) = 2^2n, falls ichs noch erklären soll, kann ichs gerne tun

[CansaSCity]

es reicht wenn man zeigt dass (n+a/n)^b gegen 1 geht und da is ja egal ob a negativ ist und wie groß a ist, zumindest bin ich der meinung dass, das reicht weils somit auf jeden fall ein c gibt dass größer bzw ein c' dass kleiner (n+a/n)^b ist
weil hier mal nach gegenbeispielen zu e) und f) gefragt wurde.
also bei e) hab ich f(n) = 2n und g(n) = n und bei der f) f(n) = 2^2n, falls ichs noch erklären soll, kann ichs gerne tun

Dann nimm zb 1/n her, dass konvergiert für n-> gegen 0, wird aber nicht von Null beschränkt, weil es für den Definitionsbereich von [0,) monoton fallend ist. Also gäbe es hier kein c, sodass c >= 1/n , für alle n.

[Cheffu]

es reicht wenn man zeigt dass (n+a/n)^b gegen 1 geht und da is ja egal ob a negativ ist und wie groß a ist, zumindest bin ich der meinung dass, das reicht weils somit auf jeden fall ein c gibt dass größer bzw ein c' dass kleiner (n+a/n)^b ist
weil hier mal nach gegenbeispielen zu e) und f) gefragt wurde.
also bei e) hab ich f(n) = 2n und g(n) = n und bei der f) f(n) = 2^2n, falls ichs noch erklären soll, kann ichs gerne tun

Dann nimm zb 1/n her, dass konvergiert für n-> gegen 0, wird aber nicht von Null beschränkt, weil es für den Definitionsbereich von [0,) monoton fallend ist. Also gäbe es hier kein c, sodass c >= 1/n , für alle n.

Hi,
wenn ich dich richtig verstehe willst du a = 1/n machen und das gegen 0 laufen lassen?
Wenn du das machen willst gibt das glaube ich nicht viel Sinn, denn a ist eine feste Zahl, also ist 1/n nicht möglich.

[Thomas]

es muss ja nicht von 0 beschränkt sein es reicht ja dass es von 1 beschränkt is, eine konvergente folge ist aba immer beschränkt und 0 ist auch eine schranke von 1/n nur halt ne untere schranke
in deinen fall wäre also 1 >= 1/n für alle n € N
aber ich glaub ich verstehe auf was du hinaus willst, da der grenzwert nicht immer die oebre schranke ist, falls die folge aba monoton fallend wäre, wäre einfach der startwert die obere grenze.
obs aba jetzt hunderprozentig stimmt weiß ich nicht

[Cheffu]

als erste prüfst du auf O und dann auf Omega . Bsp zu O : hier stellst "befreist" du c vom rest, so dass du c auf einer seite hast. . Wenn jetzt n gegen undenlich läuft, strebt gegen 1 . D.h. du hast eine obere Schranke c => es liegt in O(n^b) . Genauso machst du es auch mit Omega

Dafür musst du aber noch nachweisen dass monoton steigend ist, sonst funktioniert dein Beweis nicht

Ist es nicht so, dass monoton gegen 1 fällt und zwar (1+a)^b, zumindest wenn a positiv ist? Wenn es negativ ist gestaltet sich das wohl etwas schwerer. Man müsste also evtl sogar eine Fallunterscheidung machen.
Aber wenn man den Anfang vergisst, also ab einem bestimmten n0 gehts gegen 1 was eig reichen sollte, aber ich weis nicht ob das überhaupt der richtige weg ist

[colajunkie]

((n+a)/n)^b = (1+a/n)^b
und letzteres geht für n gegen unendlich immer gegen 1.
wenn a>0 von oben und wenn a<0 von unten...

€dit: gleich noch ne frage zur e):
in mathe hab ich mal gelernt:

2^x < 2^y <=> x<y
das sollte als beweis genügen oder?

[CansaSCity]

also beschränkte folgen sind immer konvergent, aber konvergente folgen sind nicht immer beschränkt.

1/n war nur ein Beispiel gewesen. Es gibt auf jeden Fall funktionen die konvergent aber nicht beschränkt sind. Um beschränktheit durch die konvergenz zu beweisen muss man zusätzlich zeigen, dass die Funktion monoton fallen/steigend ist. Ansonsten hilft nur abschätzen.

siehe HM I

[localhorst]

also beschränkte folgen sind immer konvergent, aber konvergente folgen sind nicht immer beschränkt.

Christen und Schmöger werden dich gemeinsam lynchen genau das Gegenteil ist der Fall.. (-1)^n

Um beschränktheit durch die konvergenz zu beweisen muss man zusätzlich zeigen, dass die Funktion monoton fallen/steigend ist. Ansonsten hilft nur abschätzen.

same.. nach /beschränkt/konvergent/g stimmt es.. siehe monotoniekriterium

Zum Thema:
Grenzwertbetrachtung ist doch hier ganz fehl am Platz, oder? Wir müssen ein c in Abhängigkeit von a und b entsprechend der Definition finden.. das funktioniert bei mir mit einer Fallunterscheidung zwischen a>=0 und a<0..

[Thomas]

man kann ja bei dem O-zeug auch ein sehr großes n0 wählen, und mit dem grenzwert zeigt man ja dass sich n^b und (n+a)^b eigentlich nicht mehr unterscheiden, da dass a dann unwichtig ist. zumindest hab ich den grenzwert deswegen gemacht. ob mans so machen kann ka