www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Navigation
 Startseite...
 Suchen
 Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - O-Kalkül Beweisführung
O-Kalkül Beweisführung < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

O-Kalkül Beweisführung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
O-Kalkül Beweisführung: Antwort
Status: (Antwort) fertig Status 
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)

Bezug
                
Bezug
O-Kalkül Beweisführung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
O-Kalkül Beweisführung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.


Bezug
                                
Bezug
O-Kalkül Beweisführung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]
Bezug
                                        
Bezug
O-Kalkül Beweisführung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]