matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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
StartseiteMatheForenDiskrete MathematikBeweis von Funktionen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Diskrete Mathematik" - Beweis von Funktionen
Beweis von Funktionen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweis von Funktionen: Funktionsdefinitionen
Status: (Frage) beantwortet Status 
Datum: 16:37 Sa 16.04.2011
Autor: Max80

Aufgabe
Seien Funktionen [mm]f_1,f_2,f_3,f_4 : \IN \to \IR[/mm] definiert durch

[mm]f_1(n) := n^2 - n + 1[/mm]
<span class="math">[mm]f_2(n) := 2n^2 + 3n - 150[/mm]
[mm]f_3(n) := (n!)^2 + n![/mm]
[mm]f_4(n) := \summe_{i=1}^{n} 3i[/mm]

Zeigen Sie für alle Paare (i,j)[mm]\in[/mm]<span class="math">[mm]\left \{ 1,2,3,4 \right \}^2[/mm], ob <span class="math">[mm]f_i = O(f_i)[/mm] gilt oder nicht.</span>
</span>
</span>


Hallo zusammen!

Ich muss gestehen, dass mir für diese Aufgabe jeglicher Ansatz fehlt. Grund ist primär auch, dass ich gar nicht weiß, was das "[mm]O[/mm]" bedeuten soll. Also ich weiß gar nicht, was [mm]O(f_i)[/mm] bedeutet und was ich einsetzen und Beweisen soll.

Wär super, wenn jemand hier eine Idee hat...
Danke!!

Viele Grüße
Max

        
Bezug
Beweis von Funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:38 Sa 16.04.2011
Autor: meili

Hallo Max,

> Seien Funktionen [mm]f_1,f_2,f_3,f_4 : \IN \to \IR[/mm] definiert
> durch
>  
> [mm]f_1(n) := n^2 - n + 1[/mm]
>  <span class="math">[mm]f_2(n) := 2n^2 + 3n - 150[/mm]
>  
> [mm]f_3(n) := (n!)^2 + n![/mm]
>  [mm]f_4(n) := \summe_{i=1}^{n} 3i[/mm]
>  
> Zeigen Sie für alle Paare (i,j)[mm]\in[/mm]<span class="math">[mm]\left \{ 1,2,3,4 \right \}^2[/mm],
> ob <span class="math">[mm]f_i = O(f_i)[/mm] gilt oder nicht.</span>
>  </span>
>  </span>
>  
> Hallo zusammen!
>  
> Ich muss gestehen, dass mir für diese Aufgabe jeglicher
> Ansatz fehlt. Grund ist primär auch, dass ich gar nicht
> weiß, was das "[mm]O[/mm]" bedeuten soll. Also ich weiß gar nicht,
> was [mm]O(f_i)[/mm] bedeutet und was ich einsetzen und Beweisen
> soll.

Für [mm]\mathcal{O}(f_i)[/mm]  sieh mal bei []Landau-Symbole nach.

>  
> Wär super, wenn jemand hier eine Idee hat...
>  Danke!!
>  
> Viele Grüße
>  Max

Gruß
meili

Bezug
                
Bezug
Beweis von Funktionen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:05 Sa 16.04.2011
Autor: Max80


Hi!

Danke für die Antwort. Was bedeutet eigentlich [mm]\IN\to\IR[/mm] ? Wenn ich die Aufgabe richtig verstanden habe, soll ich also Beweisen, ob die Funktionen (von den Zahlen 1-4 eingesetzt) nur schwach schneller steigen als die jeweils andere. Was bedeutet das ^2 hinter der Klammer? Es gibt doch nur 4 Funktionen...

Ich versuche also mein Glück mit der ersten und der zweiten:

Sei n = 2:

[mm]f_1(2) = 4 - 2 + 1 = 3 [/mm]

[mm]f_2(2) = 2*(2*2) + 3*2 - 150 = 14-150 = -136[/mm]


Habe ich hiermit nicht schon widerlegt, dass für die ersten beiden das "schwache schneller wachsen" gilt?

Ich überlege, ob ich weiter mache, aber mir stellen sich jetzt schon zwei fundamentale Fragen: Was bedeutet eben dieses hoch 2 hinter den Zahlen 1,2,3,4 und wie kann man eigentlich etwas beweisen, wenn es stimmt. Selbst wenn ich eine niedrige Zahl und eine hohe Zahl einsetze, dann heißt es ja noch lange nicht, dass es auch für eine noch viel größere Zahl gilt. Kann man hier evtl. mit vollständiger Induktion etwas erreichen?? Ich befürchte nämlich, dass es darauf hinaus läuft...

Danke!!
Grüße
Max




Bezug
                        
Bezug
Beweis von Funktionen: Tipp
Status: (Antwort) fertig Status 
Datum: 19:03 Sa 16.04.2011
Autor: spongegar

Hallo,
also [mm] \IN \to \IR [/mm] bedeutet, dass du Funktionen betrachtest, die von den natürlichen Zahlen (Definitionsbereich) in die reellen Zahlen (Bildbereich) abbilden.

Das Quadrat hinter der Menge bedeutet, dass die Elemente daraus Paare (i,j) sind. (1,3) heißt z.B, dass du f1 und f3 vergleichst. Du musst also (1,2), (1,3), (1,4), (2,3) (2,4) und (3,4) betrachten.

Wie genau du Beweise in Bezug auf das Landau-Symbol führst, weiß ich leider  nicht. Wahrscheinlich wirst du Grenzwerte betrachten müssen. Jedenfalls genügt es nicht, Zahlenbeispiele auszuprobieren, du musst schon für alle n  beweisen. Mit Induktion könnte es vielleicht gehen.

Viel Erfolg!

Gruß,

spongegar

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]