Landau-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:07 Sa 26.02.2011 | | Autor: | Kato |
| Aufgabe 1 | Für eine Funktion [mm] g: \IN \rightarrow \IR^+[/mm] gilt
[mm] O(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: f(n) \leq cg(n)\} [/mm].
Analog wächst [mm]f[/mm] nicht langsamer als g, wenn [mm] f(n) \in \Omega(g(n)) [/mm] gilt mit
[mm] \Omega(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: f(n) \geq cg(n)\} [/mm].
1) Geben Sie eine möglichst einfache geschloßene Definition für die Menge [mm]\Theta(g)[/mm] an (d.h. mit möglichst wenigen Parametern, Quantoren etc. in der Definition), analog zur Definition der Mengen [mm]O(g) [/mm] und [mm]\Omega(g)[/mm]. |
| Aufgabe 2 | 2) a) Gilt für alle Funktionen [mm]f[/mm] und [mm]g[/mm], dass wenn [mm]f(n) \in \Theta(g)[/mm], dann auch [mm]g(n) \in \Theta(f)[/mm]?
b) Gibt es voneinander verschiedene Funktionen [mm]f(n) [/mm] und [mm]g(n)[/mm], so dass [mm]f(n) \in \Omega(g)[/mm] und [mm]g(n) \in \Omega(f)?[/mm] |
Hallo liebe Mathefreunde,
bei mir hat gerade die Vorlesung Datenstrukturen und Algorithmen angefangen und da die Landau-Notation dafür äußerst wichtig ist, möchte ich hier ganz sicher gehen.
Also für 1) habe ich mir folgende Definition überlegt:
[mm] \Theta(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c_1,c_2 \in \IR : f(n) = c_1g(n) + c_2\} [/mm].
Ich kann also g(n) mit Hilfe von [mm]c_1, c_2[/mm] auf f(n) abbilden.
Damit habe ich dann bei 2) a) folgenden Beweis geführt:
Sei F die Menge aller Funktionen
Beh.: [mm]\forall f,g \in F: f \in \Theta(g) \Rightarrow g \in \Theta(f) [/mm]
Ann.: [mm]f \in \Theta(g) [/mm] also [mm]\exists c_1,c_2 \in \IR: f(n) = c_1g(n) + c_2 [/mm]
Beweis: z.Z.: [mm]\exists c_3,c_4 \in \IR: g(n) = c_3f(n) + c_4 [/mm]
[mm]f(n) = c_1g(n) + c_2 \quad |-c_2 \, |:c_1(\not=0) [/mm]
[mm]g(n) = \frac{f(n)-c_2}{c_1} = \frac{f(n)}{c_1} - \frac{c_2}{c_1} [/mm], setze: [mm] c_3 = c_1^{-1} \, ; \, c_4 = -\frac{c_2}{c_1} [/mm].
Bei 2) b) habe ich folgende zwei Funktionen als Bsp. für die Richtigkeit der Aussage überlegt:
[mm] f(n) = n [/mm]
[mm] g(n) = \frac{n}{2} [/mm]
[mm] \Omega(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: f(n) \geq c*\frac{n}{2}\} [/mm]
[mm] \Omega(f(n)) := \{g: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: g(n) \geq c*n\} [/mm] Wähle: [mm] c = \frac{1}{3} \, \Rightarrow \,\frac{n}{2} > \frac{n}{3}[/mm].
Ich bin mir bewusst, dass dies mehrere lange Fragen sind. Doch ist dieses Thema eine wichtige Grundlage und deshalb hoffe ich auf euer Verständnis und eure Hilfe/Korrekturen.
Liebe Grüße
Kato
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:43 Sa 26.02.2011 | | Autor: | felixf |
Moin!
> Für eine Funktion [mm]g: \IN \rightarrow \IR^+[/mm] gilt
> [mm]O(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: f(n) \leq cg(n)\} [/mm].
>
> Analog wächst [mm]f[/mm] nicht langsamer als g, wenn [mm]f(n) \in \Omega(g(n))[/mm]
> gilt mit
> [mm]\Omega(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: f(n) \geq cg(n)\} [/mm].
>
> 1) Geben Sie eine möglichst einfache geschloßene
> Definition für die Menge [mm]\Theta(g)[/mm] an (d.h. mit möglichst
> wenigen Parametern, Quantoren etc. in der Definition),
Wie ist [mm] $\Theta$ [/mm] definiert? Als Schnitt von $O(g)$ und [mm] $\Omega(g)$?
[/mm]
> analog zur Definition der Mengen [mm]O(g)[/mm] und [mm]\Omega(g)[/mm].
Sind die obigen Definitionen die hier gemeinten?
> 2) a) Gilt für alle Funktionen [mm]f[/mm] und [mm]g[/mm], dass wenn [mm]f(n) \in \Theta(g)[/mm],
> dann auch [mm]g(n) \in \Theta(f)[/mm]?
>
> b) Gibt es voneinander verschiedene Funktionen [mm]f(n)[/mm] und
> [mm]g(n)[/mm], so dass [mm]f(n) \in \Omega(g)[/mm] und [mm]g(n) \in \Omega(f)?[/mm]
>
> Hallo liebe Mathefreunde,
>
> bei mir hat gerade die Vorlesung Datenstrukturen und
> Algorithmen angefangen und da die Landau-Notation dafür
> äußerst wichtig ist, möchte ich hier ganz sicher gehen.
>
>
> Also für 1) habe ich mir folgende Definition überlegt:
> [mm]\Theta(g(n)) := \{f: \IN \rightarrow \IR^+ : \exists c_1,c_2 \in \IR : f(n) = c_1g(n) + c_2\} [/mm].
> Ich kann also g(n) mit Hilfe von [mm]c_1, c_2[/mm] auf f(n)
> abbilden.
Das ist falsch, zum Beispiel gilt $1 + [mm] \frac{1}{n} [/mm] = [mm] \Theta(1)$, [/mm] jedoch gibt es zwischen $f(n) = 1 + [mm] \frac{1}{n}$ [/mm] und $g(n) = 1$ keine solche Relation.
> Damit habe ich dann bei 2) a) folgenden Beweis geführt:
>
> [...]
Das geht so nicht, da deine Beschreibung der Menge [mm] $\Theta(g(n))$ [/mm] falsch ist.
> Bei 2) b) habe ich folgende zwei Funktionen als Bsp. für
> die Richtigkeit der Aussage überlegt:
> [mm]f(n) = n[/mm]
> [mm]g(n) = \frac{n}{2}[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:19 So 27.02.2011 | | Autor: | Kato |
>Moin!
Hallo felixf,
vielen Dank erst Mal für deine Antwort.
>> Für eine Funktion $ g: [mm] \IN \rightarrow \IR^+ [/mm] $ gilt
>> $ O(g(n)) := [mm] \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: >\forall n \geq n_0: f(n) \leq cg(n)\} [/mm] $.
>>
>> Analog wächst $ f $ nicht langsamer als g, wenn $ f(n) [mm] \in \Omega(g(n)) [/mm] $
>> gilt mit
>> $ [mm] \Omega(g(n)) [/mm] := [mm] \{f: \IN \rightarrow \IR^+ : \exists c \in \IR^+, n_0 \in \IN: \forall n \geq n_0: f(n) \geq cg(n)\} [/mm] $.
>>
>> 1) Geben Sie eine möglichst einfache geschloßene
>> Definition für die Menge $ [mm] \Theta(g) [/mm] $ an (d.h. mit möglichst
>> wenigen Parametern, Quantoren etc. in der Definition),
>Wie ist $ [mm] \Theta [/mm] $ definiert? Als Schnitt von $ O(g) $ und $ [mm] \Omega(g) [/mm] $?
Eine Definition sollen wir selber finden, aber im wesentlich ist $ [mm] \Theta [/mm] $ ja der Schnitt von $ O(g) $ und $ [mm] \Omega(g) [/mm] $. Habe mir das mal auf Wikipedia angeschaut.
Die Definition über den Limes haben wir noch nicht in der Vorlesung besprochen. Also wird wohl erwartet, dass ich die Definition wohl so $ c_1g [mm] \leq [/mm] f [mm] \leq [/mm] c_2g $ hinschreiben soll.
>> analog zur Definition der Mengen $ O(g) $ und $ [mm] \Omega(g) [/mm] $.
>Sind die obigen Definitionen die hier gemeinten?
Ja, wir sollen eine eigene Def. von $ [mm] \Theta [/mm] $ finden, welche sich an die oben genannten von $ O(g) $ und $ [mm] \Omega(g) [/mm] $ anlehnt.
[...]
>Das ist falsch, zum Beispiel gilt $ 1 + [mm] \frac{1}{n} [/mm] = [mm] \Theta(1) [/mm] $, jedoch >gibt es zwischen $ f(n) = 1 + [mm] \frac{1}{n} [/mm] $ und $ g(n) = 1 $ keine solche >Relation.
Danke für diesen Hinweis. Ich werde sehen, was ich mit Hilfe der neuen $ [mm] \Theta [/mm] $ Definition herausfinden kann. Schreibe ich dann aber heute Abend. Ist schon ziemlich spät.
PS: Du wohnst ja auch in Zürich ^^.
Liebe Grüße
Kato
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:25 So 27.02.2011 | | Autor: | felixf |
Moin!
> >> 1) Geben Sie eine möglichst einfache geschloßene
> >> Definition für die Menge [mm]\Theta(g)[/mm] an (d.h. mit
> möglichst
> >> wenigen Parametern, Quantoren etc. in der Definition),
>
> >Wie ist [mm]\Theta[/mm] definiert? Als Schnitt von [mm]O(g)[/mm] und
> [mm]\Omega(g) [/mm]?
>
> Eine Definition sollen wir selber finden, aber im
> wesentlich ist [mm]\Theta[/mm] ja der Schnitt von [mm]O(g)[/mm] und [mm]\Omega(g) [/mm].
Nunja, ihr solltet schon eine Art Definition haben, oder zumindest einen Hinweis was [mm] $\Omega$ [/mm] sein soll.
> Habe mir das mal auf Wikipedia angeschaut.
> Die Definition über den Limes haben wir noch nicht in der
> Vorlesung besprochen. Also wird wohl erwartet, dass ich die
> Definition wohl so [mm]c_1g \leq f \leq c_2g[/mm] hinschreiben
> soll.
Genau.
> PS: Du wohnst ja auch in Zürich ^^.
Ja, tue ich. Und du offenbar auch?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:15 So 27.02.2011 | | Autor: | Kato |
Guten Abend,
so hier nun "meine" Definition (eigentlich ist sie ja von Wikipedia) und der auf ihr aufbauende Beweis. Langsam bekomme ich ein Gefühl für diese Notation.
[mm] \Theta(g(n)) := \{f:\IN \rightarrow \IR : \exists c_1,c_2 \in \IR^+ , n_0 \in \IN : \forall n \geq n_0 : c_1 * |g(n)| \leq |f(n)| \leq c_2 * |g(n)| \} [/mm]
Nun der Beweis 2) a)
Sei F die Menge aller Funktionen
Behauptung: [mm] \forall f, g \in F : f \in \Theta (g) \Rightarrow g \in \Theta (f) [/mm]
Annahme: [mm] f \in \Theta (g) \Rightarrow \exists c_1,c_2 \in \IR^+ , n_0 \in \IN : \forall n \geq n_0 : c_1 * |g(n)| \leq |f(n)| \leq c_2 * |g(n)| [/mm]
Beweis: z.Z.: [mm] \exists c_3,c_4 \in \IR^+ , n_0 \in \IN : \forall n \geq n_0 : c_3 * |f(n)| \leq |g(n)| \leq c_4 * |f(n)| [/mm]
1. Fall: [mm] \forall n \geq n_0 : |g(n)| > |f(n)| [/mm]
Aus der Annahme folgt:
[mm] c_1*|g(n)| \leq |f(n)| \quad | :c_1 [/mm]
[mm]|g(n)| \leq |f(n)|*\frac{1}{c_1} [/mm]
Setze: [mm] c_3 = 1 \, ; \, c_4 = \frac{1}{c_1} [/mm]
2. Fall: [mm] \forall n \geq n_0 : |g(n)| < |f(n)| [/mm]
Analog dem 1. Fall:
[mm] c_2*|g(n)| \geq |f(n)| \quad | :c_2 [/mm]
[mm]|g(n)| \geq |f(n)|*\frac{1}{c_2} [/mm]
Setze: [mm] c_3 = \frac{1}{c_2} \, ; \, c_4 = 1 [/mm]
3. Fall: [mm] \forall n \geq n_0 : |g(n)| = |f(n)| [/mm]
Setze: [mm] c_3 = c_1 \, ; \, c_4 = c_2 [/mm]
Ich bin mir 99%ig sicher, dass das richtig ist, deshalb wird es nicht nochmals als Frage gestellt.
Ja ich wohne auch in Zürich.
Liebe Grüße und danke für die Hilfe
Kato
|
|
|
|
