O-Kalkül Beweisführung < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:20 Di 11.11.2003 | | Autor: | Gloomer |
Hallo :)
Ich knabber da an nem Beweis.....
und zwar: geg. f,g (monoton steigende Fkt) : N -> R+
O(f(n)) = O(g(n)) <=> f(n) Є O(g(n)) Λ g(n) Є O(f(n))
und
O(f(n)) "echte Teilmenge" O(g(n)) <=> f(n) Є O(g(n)) Λ g(n) "nicht Element" O(f(n))
schönen dank im voraus :D in der literatur die ich fand, wurde das immer obda als gegeben gesehen, das half mir natürlich nicht weiter ;)
thx
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:18 Di 11.11.2003 | | Autor: | Stefan |
Hallo Gloomer,
was bedeutet denn [mm]g(n) \in {\cal O}(f(n))[/mm]? Es bedeutet:
Es gibt eine Konstante [mm]K>0[/mm] und ein [mm]n_0 \in \mathbb{N}[/mm], so dass für alle [mm]n \in \mathbb{N}[/mm] mit [mm]n \ge n_0[/mm] folgendes gilt:
[mm] g(n) \le K \cdot f(n).[/mm]
Wir zeigen nun zunächst:
[mm] g(n) \in {\cal O}(f(n)) \Leftrightarrow {\cal O}(g(n)) \subset {\cal O}(f(n)).[/mm]
"[mm]\Leftarrow[/mm]": Trivial wegen [mm]g(n) \in {\cal O}(g(n))[/mm].
"[mm]\Rightarrow[/mm]": Aus [mm]g(n) \in {\cal O}(f(n))[/mm] folgt: Es gibt eine Konstante [mm]K>0[/mm] und ein [mm]n_0 \in \mathbb{N}[/mm], so dass für alle [mm]n \in \mathbb{N}[/mm] mit [mm]n \ge n_0[/mm] folgendes gilt:
[mm] g(n) \le K \cdot f(n).[/mm]
Nun sei [mm]h(n) \in {\cal O}(g(n))[/mm] beliebig gewählt, d.h. es gebe eine Konstante [mm]L>0[/mm] und ein [mm]n_1 \in \mathbb{N}[/mm], so dass für alle [mm]n \in \mathbb{N}[/mm] mit [mm]n \ge n_1[/mm] folgendes gilt:
[mm] h(n) \le L \cdot g(n).[/mm]
Dann gilt für alle [mm]n \in \mathbb{N}[/mm] mit [mm]n\ge n_2:=\max\{n_0,n_1\}[/mm] und [mm]M:=K\cdot L[/mm] die Ungleichung
[mm] h(n) \le L \cdot g(n) \le L\cdot K \cdot f(n) = M \cdot f(n),[/mm]
also: [mm]h(n) \in {\cal O}(f(n))[/mm].
Vertauscht man nun die Rollen von [mm]f(n)[/mm] und [mm]g(n)[/mm], so folgt deine erste Aussage.
Die zweite Aussage folgt nun so:
Aus den obigen Erklärungen folgt:
[mm]{\cal O}(f(n)) \subset {\cal O}(g(n)) \Leftrightarrow f(n) \in {\cal O}(g(n))[/mm].
Zu zeigen bleibt also:
[mm]{\cal O}(g(n)) \not\subset {\cal O}(f(n)) \Leftrightarrow g(n) \notin {\cal O}(f(n))[/mm].
Dies ist aber die obige Äquivalenz (beide Seiten verneint) und damit ebenfalls wahr.
Alles Gute
Stefan
Nachricht bearbeitet (Di 11.11.03 21:19)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:25 Mi 12.11.2003 | | Autor: | Gloomer |
suuuupa danke :D
wie immer, es ist einfach, wenn man erstma den passenden ansatz findet! manchmal seh ich die passende formel vor lauter symbolen net ;)
aber mal nen tip für die seite hier: die möglichkeit ne druckbare version anzuzeigen müsste her, und die e-mail benachrichtigung ist auch etwas umständlich gelöst, mit dem text, welcher unformatiert angezeigt wird....
mal sehn ob ich in zukunft hier auch wem helfen kann :D
man sieht sich
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:03 Mi 12.11.2003 | | Autor: | Marc |
Hallo Gloomer,
> wie immer, es ist einfach, wenn man erstma den passenden ansatz
> findet! manchmal seh ich die passende formel vor lauter
> symbolen net ;)
Das bringt aber dann die Übung mit sich -- und sicher auch ein paar vorgerechnete Aufgaben 
> aber mal nen tip für die seite hier: die möglichkeit ne
> druckbare version anzuzeigen müsste her, und die e-mail
Druckbare Version der Seite ist bereits auf der TODO-Liste, allerdings ziemlich weit unten...
> benachrichtigung ist auch etwas umständlich gelöst, mit dem
> text, welcher unformatiert angezeigt wird....
Das klingt, als hättest du eine bessere Idee für die Formatierung? Nur raus' damit!
Allerdings soll die Benachrichtigung auch wirklich nur eine Benachrichtigung sein -- der Inhalt des Artikels sollte nur eine Zugabe sein, da sich die Artikel nach der Benachrichtigung häufig bereits geändert haben.
Einzige Möglichkeit einer schöneren Formatierung ist (soweit ich es sehe), eine HTML-Seite mit integrierten Bildern zu verschicken, aber da werden wir sicher von mehreren Usern gesteinigt, und ich müßte mich auch selbst steinigen
> mal sehn ob ich in zukunft hier auch wem helfen kann :D
Das wäre sehr nett, so soll der MatheRaum ja auch funktionieren. (Betrachte es aber bitte nicht als Verpflichtung...)
> man sieht sich
Gruß,
Marc.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:56 Mo 17.11.2003 | | Autor: | Gloomer |
huhu...
also die mail benachrichtigung sollte den text gar nicht enthalten, sondern sollte wirklich nur ne art memo sein.... ist in andern boards auch so üblich und hat sich bewährt....
hier mal der vollständigkeit halber die lösungen wie sie mein prof meinte:
[Dateianhang nicht öffentlich]
[Dateianhang nicht öffentlich]
kann das leider nicht anders hier einbinden..... bin nen bisserl faul das nu zu tippen :D
so long......
Dateianhänge:
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
Anhang Nr. 3 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:47 Mo 17.11.2003 | | Autor: | Stefan |
Hallo Gloomer,
> huhu...
> also die mail benachrichtigung sollte den text gar nicht
> enthalten, sondern sollte wirklich nur ne art memo sein.... ist
> in andern boards auch so üblich und hat sich bewährt....
Das sehe ich anders. Ich will schon vorher wissen, ob es sich lohnt ins Forum zu gehen. Gerade das stört mich an anderen Foren. "Sie haben eine Benachrichtigung" zwingt mich immer nachzuschauen. Hier kann ich sofort sehen, ob mich die Benachrichtigung potentiell interessiert. Wir werden es (zumindestens, wenn es nach mir geht, aber ich habe nur eine von vier Stimmen) so lassen wie bisher.
Die Lösung des Profs entspricht ja genau meiner Lösung, nur mit anderen Worten. Von daher: Alles bestens. 
Alles Gute
Stefan
|
|
|
|
