Landau-Beweise

08.04.2016, 21:08

Musican

Landau-Beweise

Meine Frage:
Wieder einmal Hallo!
Ich weiß nicht, ob hier Platz für informatikübergreifende Mathematik-Anwedungen Platz ist. Es geht um Komplexitätstheorie.
Es seien vier Funktionen gegeben:

$\begin{eqnarray*} f_{1}(n) = n² , f_{2}(n) = n² + 1000n , f_{3}(n) = m^{log n} , f_{4} (n) = n^{log m} \end{eqnarray*}$
Sei zusätzlich m > 1 konstant.
"Zeigen Sie nun unter Verwendung der LandauDefinition : $\begin{eqnarray*} f_{2} \in \mathbb O (f_{1} ) und f_{3} \in \mathbb O(f_{4} \end{eqnarray*}$

Meine Ideen:

Naja die Definition besagt ja (ich sehe dort auch parallelen zur Epsilon-Umgebung bei Folgenkonvergenz) dass die Funktion g(n) in der Laufzeit O(f(n)) liegt, wenn :

$\begin{eqnarray*} \exists c \geq 0 \in \mathbb R : \exists n_{0} \in \mathbb N \forall n \geq n_{0} : g(n) \leq c * f(n) \end{eqnarray*}$

ich habe einfach mal für den ersten Beweis $\begin{eqnarray*} f_{2} \leq c * f_{1} \end{eqnarray*}$ gesetzt. Wenn ich nun ein c UND ein n_0 finde, sodass die Ungleichung gilt, müsste doch direkt gezeigt sein, dass f1(n) in f2(n) liegt oder? In dem Fall würde die Ungleichung bei n = 1 und c = 2000 stimmen. Ich habe bewusst einen großzügigen Wert genommen.

Bei der zweiten ist es etwas kniffliger. Ich muss halt erstmal wissen, ob mein erster Ansatz stimmt. Oder, ob es doch eines vollständigeren Beweises bedarf. Falls ja, würde mich interessieren, ob jemand von euch eine Idee hat, oder sich vllt sogar damit auskennt.

Liebe Grüße

Der Musiker smile

08.04.2016, 21:37

tatmas

Auf diesen Beitrag antworten »

Hallo,

Landau-Symbolik ist ein Standardthema der Analysis, kommt meistens in Analyss I drin. Das ist ganz normale Mathematik.

Zitat:

In dem Fall würde die Ungleichung bei n = 1 und c = 2000 stimmen

So wie es dasteht ist es nur eine Behauptung und noch kein Beweis. Warum stimmt denn diese Aussage, das wäre ein Beweis?
Übrigens ist die Behauptung falsch.
$\begin{eqnarray*} f_1(n) > 2000\cdot f_2(n) \end{eqnarray*}$ für jede natürliche Zahl n.

08.04.2016, 22:22

Musican

Auf diesen Beitrag antworten »

Gut zu wissen, bei uns spielte in Angewandter Mathematik die Landau Symbolik irgendwie gar nicht rein.

Da hast du total Recht! War ich wohl voll durcheinander.
Gut, also muss ich es doch für alle n >= diesem n_0 zeigen.
Ich sehe nur weiß Gott nicht, wie das funktionieren soll. Laut Aufgabentext soll ich die Wahrheit dieser Aussagen zeigen. Mein Menschenverstand sagt mir auch, dass 1000n im Unendlichen keine Rolle für ein exponentielles n² spielen, was die asymptotische Laufzeit betrifft.

Wenn ich durch n² teile erhalte ich $\begin{eqnarray*} n² + 1000n \leq cn² = 1 + \frac{1000}{n} \leq c \end{eqnarray*}$

wird dann nicht bei einem c = 2 und ab einem n >= 1000=n_0 die Aussage war?

08.04.2016, 22:31

tatmas

Auf diesen Beitrag antworten »

Zitat:

. Mein Menschenverstand sagt mir auch, dass 1000n im Unendlichen keine Rolle für ein exponentielles n² spielen, was die asymptotische Laufzeit betrifft.

Bitte verwende saubere Defintionen (die du hier ja bereits aufgeschrieben hast.) nicht irgendwelche halbgare Veranschaulichungen. Die landau-Symbole sind gerade dafür da dieses "spielt im Unendlichen keine Rolle" eine saubere und korrekte mathematische Basis zu geben.

Zitat:

Wenn ich durch n² teile erhalte ich $\begin{eqnarray*} n² + 1000n \leq cn² = 1 + \frac{1000}{n} \leq c \end{eqnarray*}$

Was teilst du durch n²?
Wieso soll plötzlich cn²=1+1000/n gelten?

Ansonsten kann man hier aber mit dem neuen c und n arbeiten.

08.04.2016, 22:37

Musican

Auf diesen Beitrag antworten »

Naja ich dachte ich versuchs damit $\begin{eqnarray*} n² + 1000n \leq c* n² \end{eqnarray*}$ per Definition zu setzen. Dann habe ich auf beiden Seiten durch n² geteilt und gemerkt, dass oben aufgeführte funktion $\begin{eqnarray*} 1 + \frac{1000}{n} \leq c \end{eqnarray*}$ entsteht.
Ich dachte jetzt, dass ich daran vielleicht besser mein n_0 und mein c abschätzen könnte.
Oder darf ich die Ungleichung etwa nicht umformen, und damit weiterarbeiten? verwirrt

08.04.2016, 22:44

tatmas

Auf diesen Beitrag antworten »

Zitat:

per Definition zu setzen

Du setzt, allerdings nicht per Defintion.
Man kann kann nicht per Defintion setzen, etwas gilt per Defintion. Das ist hier allerdings nicht der Fall.

Zitat:

Dann habe ich auf beiden Seiten durch n²

Das ist eine Termumformung, die darfst du machen. Die notiert man aber mit Äquivalenzpfeilen.
= steht bei einer Gleichungskette.

Zitat:

oben aufgeführte funktion

Das ist eine Ungleichung, keine Funktion.

Was du machst ist schon richtig, du kannst es nur nicht gut kommunizieren weil du die falsche Fachbegriffe oder Fachbegriffe falsch berwendest.

08.04.2016, 22:58

Musican

Auf diesen Beitrag antworten »

Okay, danke für das Feedback, aber ehrlich gesagt ist mir das schon alles klar, nach 5 semestern Informatik ^^
Ich hab es gerad nur blöderweise vernachlässigt, da ich eh nur an der Richtigkeit meiner Vorgehensweise interessiert war, aber mein Fehler. Mir liegen halt Beweistechniken an sich nicht so. Aber gut, dass dus sagst, ich werde mehr drauf achten.

Meinst du denn es ist generell sinnvoll so vorzugehen, um zu zeigen, dass eine gewisse Funktion g(n) in O (f(n)) liegt?
Oder gibt es noch geschicktere Vorgehensweisen für ggf. komplexere Funktionen g(n) und f(n)?

08.04.2016, 23:04

tatmas

Auf diesen Beitrag antworten »

Zitat:

Meinst du denn es ist generell sinnvoll so vorzugehen,

Ja. Und wie oft mag es für bestimmte Konstellationen einfacheres Vorgehen geben oder auch nicht.

Neue Frage »

Antworten »

Landau-Beweise

Verwandte Themen