Definition Landau Symbole < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass folgende Definitionen für g : [mm] \IN \to \IR [/mm] äquvalent sind:
Omega(g) := [mm] \{ f : \IN \to \IR | \exists n_{0} \in \IN, c > 0: 0 \le c * g(n) \le f(n) \forall n \le n_{0} \}
[/mm]
Omega'(g) := [mm] \{f : \IN \to \IR | g \in O(f)\}
[/mm]
wobei O(f) := [mm] \{g :\IN \to \IR | \exists n_{0} \in \IN, c > 0: 0 \le g(n) \le c * f(n) \} [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Um zu zeigen, dass beide Definitionen äquivalent sind, muss ich die Gleichheit beider Mengen (Omega = Omega') zeigen.
Mein Ansatz sieht dann wie folgt aus:
z.z.: f [mm] \in [/mm] Omega(g) [mm] \gdw [/mm] f [mm] \inOmega'(g)
[/mm]
bew.: [mm] "\Rightarrow" [/mm] Sei f [mm] \in [/mm] Omega(g) beliebig
[mm] \gdw \exists n_{0} \in \IN, [/mm] c > 0: 0 [mm] \le [/mm] c * g(n) [mm] \le [/mm] f(n) [mm] \forall [/mm] n [mm] \le n_{0} [/mm]
[mm] \gdw \exists n_{0} \in \IN, [/mm] c > 0: 0 [mm] \le [/mm] g(n) [mm] \le [/mm] 1/c * f(n) [mm] \forall [/mm] n [mm] \le n_{0} [/mm]
[mm] \gdw [/mm] g [mm] \in \{ f : \IN \to \IR: \exists n_{0} \in \IN, c > 0, 0 \le g(n) < c* f(n)\}
[/mm]
[mm] \gdw [/mm] g [mm] \in [/mm] O(f), (nach Definition von O).
[mm] \Rightarrow [/mm] f [mm] \in [/mm] Omega'
[mm] \Leftarrow [/mm] Sei f [mm] \in [/mm] Omega'(g) beliebig
[mm] \gdw [/mm] g [mm] \in [/mm] O(f)
[mm] \gdw \exists n_{0}, [/mm] c > 0: 0 [mm] \le [/mm] g(n) [mm] \le [/mm] c * f(n)
[mm] \gdw \exists n_{0}, [/mm] c > 0: 0 [mm] \le [/mm] 1/c * g(n) [mm] \le [/mm] f(n)
[mm] \Rightarrow [/mm] f [mm] \in [/mm] Omega(g)
Leider bin ich mir bei Beweisen immer sehr unsicher und weiß nicht ob dieser Ansatz so stimmt. Über Antworten wäre ich dankbar.
Grüße Lukas
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Mo 02.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
