Beweis von Funktionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:37 Sa 16.04.2011 | | Autor: | Max80 |
| Aufgabe | Seien Funktionen [mm]f_1,f_2,f_3,f_4 : \IN \to \IR[/mm] definiert durch
[mm]f_1(n) := n^2 - n + 1[/mm]
<span class="math">[mm]f_2(n) := 2n^2 + 3n - 150[/mm]
[mm]f_3(n) := (n!)^2 + n![/mm]
[mm]f_4(n) := \summe_{i=1}^{n} 3i[/mm]
Zeigen Sie für alle Paare (i,j)[mm]\in[/mm]<span class="math">[mm]\left \{ 1,2,3,4 \right \}^2[/mm], ob <span class="math">[mm]f_i = O(f_i)[/mm] gilt oder nicht.</span>
</span>
</span> |
Hallo zusammen!
Ich muss gestehen, dass mir für diese Aufgabe jeglicher Ansatz fehlt. Grund ist primär auch, dass ich gar nicht weiß, was das "[mm]O[/mm]" bedeuten soll. Also ich weiß gar nicht, was [mm]O(f_i)[/mm] bedeutet und was ich einsetzen und Beweisen soll.
Wär super, wenn jemand hier eine Idee hat...
Danke!!
Viele Grüße
Max
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:38 Sa 16.04.2011 | | Autor: | meili |
Hallo Max,
> Seien Funktionen [mm]f_1,f_2,f_3,f_4 : \IN \to \IR[/mm] definiert
> durch
>
> [mm]f_1(n) := n^2 - n + 1[/mm]
> <span class="math">[mm]f_2(n) := 2n^2 + 3n - 150[/mm]
>
> [mm]f_3(n) := (n!)^2 + n![/mm]
> [mm]f_4(n) := \summe_{i=1}^{n} 3i[/mm]
>
> Zeigen Sie für alle Paare (i,j)[mm]\in[/mm]<span class="math">[mm]\left \{ 1,2,3,4 \right \}^2[/mm],
> ob <span class="math">[mm]f_i = O(f_i)[/mm] gilt oder nicht.</span>
> </span>
> </span>
>
> Hallo zusammen!
>
> Ich muss gestehen, dass mir für diese Aufgabe jeglicher
> Ansatz fehlt. Grund ist primär auch, dass ich gar nicht
> weiß, was das "[mm]O[/mm]" bedeuten soll. Also ich weiß gar nicht,
> was [mm]O(f_i)[/mm] bedeutet und was ich einsetzen und Beweisen
> soll.
Für [mm]\mathcal{O}(f_i)[/mm] sieh mal bei ![[]](/images/popup.gif) Landau-Symbole nach.
>
> Wär super, wenn jemand hier eine Idee hat...
> Danke!!
>
> Viele Grüße
> Max
Gruß
meili
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:05 Sa 16.04.2011 | | Autor: | Max80 |
Hi!
Danke für die Antwort. Was bedeutet eigentlich [mm]\IN\to\IR[/mm] ? Wenn ich die Aufgabe richtig verstanden habe, soll ich also Beweisen, ob die Funktionen (von den Zahlen 1-4 eingesetzt) nur schwach schneller steigen als die jeweils andere. Was bedeutet das ^2 hinter der Klammer? Es gibt doch nur 4 Funktionen...
Ich versuche also mein Glück mit der ersten und der zweiten:
Sei n = 2:
[mm]f_1(2) = 4 - 2 + 1 = 3
[/mm]
[mm]f_2(2) = 2*(2*2) + 3*2 - 150 = 14-150 = -136[/mm]
Habe ich hiermit nicht schon widerlegt, dass für die ersten beiden das "schwache schneller wachsen" gilt?
Ich überlege, ob ich weiter mache, aber mir stellen sich jetzt schon zwei fundamentale Fragen: Was bedeutet eben dieses hoch 2 hinter den Zahlen 1,2,3,4 und wie kann man eigentlich etwas beweisen, wenn es stimmt. Selbst wenn ich eine niedrige Zahl und eine hohe Zahl einsetze, dann heißt es ja noch lange nicht, dass es auch für eine noch viel größere Zahl gilt. Kann man hier evtl. mit vollständiger Induktion etwas erreichen?? Ich befürchte nämlich, dass es darauf hinaus läuft...
Danke!!
Grüße
Max
|
|
|
| |
|
Hallo,
also [mm] \IN \to \IR [/mm] bedeutet, dass du Funktionen betrachtest, die von den natürlichen Zahlen (Definitionsbereich) in die reellen Zahlen (Bildbereich) abbilden.
Das Quadrat hinter der Menge bedeutet, dass die Elemente daraus Paare (i,j) sind. (1,3) heißt z.B, dass du f1 und f3 vergleichst. Du musst also (1,2), (1,3), (1,4), (2,3) (2,4) und (3,4) betrachten.
Wie genau du Beweise in Bezug auf das Landau-Symbol führst, weiß ich leider nicht. Wahrscheinlich wirst du Grenzwerte betrachten müssen. Jedenfalls genügt es nicht, Zahlenbeispiele auszuprobieren, du musst schon für alle n beweisen. Mit Induktion könnte es vielleicht gehen.
Viel Erfolg!
Gruß,
spongegar
|
|
|
|
