Beweis der Summenregel O-Kalkü < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:46 Mi 08.06.2011 | | Autor: | BlackSalad |
Hey, ich verstehe leider irgendwie den Beweis der Summenregel vom o-Kalkül nicht so ganz. Also ich verstehe schon, was die Summenregel ist udn wie sie funktioniert und wie man sie benutzt, aber ich verstehe nicht was der Beweis genau aussagt und wie man sonen beweis aufstellt.
Ich wäre froh, wenn mir Jemand diesen beweis in möglichst einfachen Worten erläutern könnte.. (vielleicht auch für Leute die nicht so mathebegabt sind ;) )
Richtung ⊆:
□
Sei 𝑡(𝑛) ∈ 𝑂(𝑓(𝑛)+𝑔(𝑛)).
□
Dann gibt es ein 𝑐∈ℝ+ und ein 𝑛0∈ℕ, so dass für alle 𝑛>𝑛0 gilt:
𝑡(𝑛) ≤ 𝑐 · (𝑓(𝑛)+𝑔(𝑛))≤2 · 𝑐 · max (𝑓(𝑛),𝑔(𝑛))
□
Mit 𝑐′=2 · 𝑐 gilt für alle 𝑛>𝑛0 damit
𝑡(𝑛) ≤ 𝑐′ · max (𝑓(𝑛),𝑔(𝑛))
□
Also ist 𝑡(𝑛) ∈ 𝑂(max (𝑓(𝑛),𝑔(𝑛))).
Richtung ⊇:
□
Sei 𝑡(𝑛) ∈ 𝑂(max (𝑓(𝑛),𝑔(𝑛))).
□
Dann gibt es ein 𝑐∈ℝ+ und ein 𝑛0∈ℕ, so dass für alle 𝑛>𝑛0 gilt
𝑡(𝑛) ≤ 𝑐 · max (𝑓(𝑛),𝑔(𝑛)) ≤ 𝑐 · (𝑓(𝑛)+𝑔(𝑛))
□Also ist 𝑡(𝑛) ∈ 𝑂(𝑓(𝑛)+𝑔(𝑛)).
Wär euch echt dankbar. Sonst verstehe ich das glaube ich nie!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:41 Do 09.06.2011 | | Autor: | meili |
Hallo,
> Hey, ich verstehe leider irgendwie den Beweis der
> Summenregel vom o-Kalkül nicht so ganz. Also ich verstehe
> schon, was die Summenregel ist udn wie sie funktioniert und
> wie man sie benutzt, aber ich verstehe nicht was der Beweis
> genau aussagt und wie man sonen beweis aufstellt.
>
> Ich wäre froh, wenn mir Jemand diesen beweis in möglichst
> einfachen Worten erläutern könnte.. (vielleicht auch für
> Leute die nicht so mathebegabt sind ;) )
>
>
> Richtung ⊆:
> □
> Sei 𝑡(𝑛) ∈ 𝑂(𝑓(𝑛)+𝑔(𝑛)).
> □
> Dann gibt es ein 𝑐∈ℝ+ und ein 𝑛0∈ℕ, so dass
> für alle 𝑛>𝑛0 gilt:
> 𝑡(𝑛) ≤ 𝑐 · (𝑓(𝑛)+𝑔(𝑛))≤2 · 𝑐
> · max (𝑓(𝑛),𝑔(𝑛))
> □
> Mit 𝑐′=2 · 𝑐 gilt für alle 𝑛>𝑛0 damit
> 𝑡(𝑛) ≤ 𝑐′ · max (𝑓(𝑛),𝑔(𝑛))
> □
> Also ist 𝑡(𝑛) ∈ 𝑂(max
> (𝑓(𝑛),𝑔(𝑛))).
>
> Richtung ⊇:
> □
> Sei 𝑡(𝑛) ∈ 𝑂(max (𝑓(𝑛),𝑔(𝑛))).
> □
> Dann gibt es ein 𝑐∈ℝ+ und ein 𝑛0∈ℕ, so dass
> für alle 𝑛>𝑛0 gilt
> 𝑡(𝑛) ≤ 𝑐 · max (𝑓(𝑛),𝑔(𝑛)) ≤
> 𝑐 · (𝑓(𝑛)+𝑔(𝑛))
> □Also ist 𝑡(𝑛) ∈ 𝑂(𝑓(𝑛)+𝑔(𝑛)).
Leider ist der Beweis so nicht lesbar! Deshalb auch nicht erklärbar.
Oder ist die Anzeige nur bei mir so?
>
>
> Wär euch echt dankbar. Sonst verstehe ich das glaube ich
> nie!
Gruß
meili
|
|
|
| |
|
Könnt ihr es jetzt lesen?
Richtung [mm] \subseteq [/mm] :
Sei t(n) [mm] \in [/mm] = O(f(n)+g(n)).
Dann gibt es ein O [mm] \in [/mm] R+ und ein [mm] n_0 \in \IN, [/mm] so dass
für alle n > [mm] n_0 [/mm] gilt:
t(n) [mm] \le [/mm] c * (f(n)+g(n)) [mm] \le [/mm] 2 * c
* max (f(n),g(n))
Mit c'=2*c gilt für alle n > n'_0 damit
t(n) [mm] \le [/mm] c' * max (f(n),g(n))
Also ist t(n) [mm] \in [/mm] O(max
(f(n),g(n))).
Richtung [mm] \supseteq [/mm] :
Sei t(n) [mm] \in [/mm] O(max (f(n),g(n))).
Dann gibt es ein c [mm] \in [/mm] R+ und ein [mm] n_0 \in \IN, [/mm] so dass
für alle n > [mm] n_0 [/mm] gilt
t(n) [mm] \le [/mm] c * max (f(n),g(n)) [mm] \le [/mm]
c * (f(n)+g(n))
Also ist t(n) [mm] \in [/mm] O(f(n)+g(n)).
|
|
|
| |
|
Hallo BlackSalad,
was genau ist dir denn unklar?
Um eine Mengengleichheit [mm]A=B[/mm] zu zeigen, zeigt man beide Teilmengenbeziehungen [mm]A\subset B[/mm] und [mm]A\supset B[/mm]
Das wird von der Mengenebene auf Elementebene heruntergebrochen, man zeigt: [mm]x\in A \ \Rightarrow \ x\in B[/mm] und [mm]x\in B \ \Rightarrow \ x\in A[/mm]
Offenbar soll hier gezeigt werden: [mm]\mathcal{O}(f(n)+g(n))=\mathcal{O}(\max\{f(n),g(n)\})[/mm]
Hierzu zeigt mal:
1) [mm] $t(n)\in\mathcal{O}(f(n)+g(n)) [/mm] \ [mm] \Rightarrow [/mm] \ [mm] t(n)\in\mathcal{O}(\max\{f(n),g(n)\})$ [/mm] und
2) [mm] $t(n)\in\mathcal{O}(\max\{f(n),g(n)\}) [/mm] \ [mm] \Rightarrow [/mm] \ [mm] t(n)\in\mathcal{O}(f(n)+g(n))$
[/mm]
In 1), also [mm]\subset[/mm] ist das erste [mm]\le[/mm] einfach die Definition von [mm]t(n)\in\mathcal O(f(n)+g(n))[/mm]
Für die zweite Abschätzung überlegt man sich, dass sowohl [mm]f[/mm] als auch [mm]g[/mm] [mm]\le[/mm] [mm]\max\{f(n),g(n)\}[/mm] sind.
Ist dir das klar?
Dann kannst du sowohl [mm]f[/mm] als auch [mm]g[/mm] durch das Maximum abschätzen und erhältst [mm]...\le c\cdot{}(\max\{f(n),g(n)\}+\max\{f(n),g(n)\})=2\cdot{}c\cdot{}\max\{f(n),g(n)\}[/mm]
Man erhält schließlich [mm]t(n)\in\mathcal{O}(\max\{f(n),g(n)\})[/mm]
Bei der anderen Richtung 2) [mm] $\supset$ [/mm] ganz ähnlich:
Das erste [mm]\le[/mm] ist wieder die Definition von [mm]t(n)\in\mathcal{O}(\max\{f(n),g(n)\})[/mm]
Kannst du nun die zweite Abschätung erklären?
Wieso ist [mm]\max\{f(n),g(n)\}\le f(n)+g(n)[/mm] ?
Gruß
schachuzipus
|
|
|
| |
|
okay, soweit ist es mir jetzt klar.
Aber wie muss ich jetzt vorgehen um
f(n)*g(n) Element groß Theta (s(n) * r(n)).
zu beweisen?
wie gehe ich da vor oder wo setze ich vorallem an?
|
|
|
| |
|
Hallo nochmal,
> okay, soweit ist es mir jetzt klar.
>
> Aber wie muss ich jetzt vorgehen um
>
> f(n)*g(n) Element groß Theta (s(n) * r(n)).
>
> zu beweisen?
Wieso so kryptisch und wortkarg.
Man kann dir besser helfen, wenn du die Aufgabe mitsamt allen Voraussetzungen im Originalwortlaut postest!
Und die griechischen Buchstaben kannst du so machen:
\Omega für [mm]\Omega[/mm]
\omega für [mm]\omega[/mm]
\Theta für [mm]\Theta[/mm]
\theta für [mm]\theta[/mm]
usw.
>
>
> wie gehe ich da vor oder wo setze ich vorallem an?
>
>
>
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:04 So 12.06.2011 | | Autor: | BlackSalad |
Naja, vermutlich so Wort karg weil ich nicht viel davon verstehe und mich das alles ziemlich verwirrt.
Gegeben sei f : N -> R+ und g : N -> R+. Es gilt f(n) [mm] \in \Theta [/mm] (s(n)), g(n) [mm] \in \Theta(r(n)).
[/mm]
Beweisen Sie f(n) * g(n) [mm] \in \Theta(s(n) [/mm] · r(n)).
Also was Theta ist hab ich soweit verstanden. Aber ich weiß trotzdem nicht wie ich so einen Beweis führen muss.
|
|
|
| |
|
Hallo nochmal,
> okay, soweit ist es mir jetzt klar.
>
> Aber wie muss ich jetzt vorgehen um
>
> f(n)*g(n) Element groß Theta (s(n) * r(n)).
>
> zu beweisen?
>
>
> wie gehe ich da vor oder wo setze ich vorallem an?
Schreibe dir die Definitionen, also die Ungleichungen für
1) [mm] $f(n)\in\Theta(s(n))$ [/mm] und
2) [mm] $g(n)\in\Theta(r(n))$ [/mm] hin, dann wird es doch ziemlich schnell klar ...
Gruß
schachuzipus
|
|
|
| |
|
leider finde ich nur wenig über das groß Theta.
Wie ist es denn genau definiert?
Das ist das erste mal wo ich einen Beweis tun soll.
|
|
|
| |
|
Hallo nochmal,
> leider finde ich nur wenig über das groß Theta.
???
Hast du kein Internet??
www.google.de --> "Landausymbole" ---> ersten link zu wikipedia anklicken.
Da steht alles - findest du in 10 Sekunden.
Also etwas mehr Eigenantrieb ...
>
> Wie ist es denn genau definiert?
Schaue auf Wikipedia nach - wahlweise in (fast) jedem Informatik I - Skript ...
>
> Das ist das erste mal wo ich einen Beweis tun soll.
Ja, dann leg los, schlag' die Definition nach und schreibe die entsprechenden Ungleichungen hin ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:05 Do 09.06.2011 | | Autor: | leduart |
Hallo
auch für mich ist dein post unlesbar, anscheinend hast du irgendwelche tastaturkürzel benutzt, die wohl kein browser lesen kann. sieh dir deinen post an und schreib das neu mit dem editor (unter dem Eingabefenster)
Gruss leduart
|
|
|
|
