www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algorithmen und Datenstrukturen" - Limeskriterien + eine Aufgabe
Limeskriterien + eine Aufgabe < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Limeskriterien + eine Aufgabe: Aufgabe und generelle Frage
Status: (Frage) beantwortet Status 
Datum: 18:11 Mo 29.08.2005
Autor: DerMathematiker

Hi alle zusammen,

wir haben in der Vorlesung die Limeskriterien aufgeschrieben.

Ein Kriterium ist z. Bsp.

[mm] \limes_{n\rightarrow\infty} \frac{f(n)}{g(n)} [/mm] = c < [mm] \infty \Rightarrow [/mm] f [mm] \in [/mm] O(g)

Bedeutet c < [mm] \infty [/mm] soviel, dass am Schluss im Zähler kein von n abhängiger Term stehen darf? Ich würde sagen ja, aber ich weiß es nicht genau. War gerade eben beim durchgehen etwas verwirrt.

Zudem habe ich noch eine Frage, wie man beweisen kann, dass [mm] e^{\sqrt{n}} \in [/mm] O(n!).

Weil mit n! kann ich nicht wirklich rechnen, ich weiß, dass

n! = n (n-1) ....

Aber sonst auch nichts, d.h. wenn ich mit der puren Definition nicht weiterkomme, habe ich ein Problem. Wie könnte man diesen Beweis führen? Bzw. was sollte man zu der Fakultät noch wissen?

MfG Andi

        
Bezug
Limeskriterien + eine Aufgabe: Konvergenz
Status: (Antwort) fertig Status 
Datum: 18:50 Mo 29.08.2005
Autor: Loddar

Hallo Andi!


> Bedeutet c < [mm]\infty[/mm] soviel, dass am Schluss im Zähler kein
> von n abhängiger Term stehen darf?

Der Ausdruck $c \ < \ [mm] \infty$ [/mm] besagt, dass der betrachtete Ausdruck (hier: [mm] $\frac{f(n)}{g(n)}$ [/mm] ) auch konvergent ist. Das heißt, es existiert ein konkreter Wert für den Grenzwert $c_$.


Der Ausdruck [mm] $\limes_{n\rightarrow \infty} [/mm] ... \ = \ c \ [mm] \red{=} [/mm] \ [mm] \pm \infty$ [/mm] beschreibt dann die Divergenz des betrachteten Ausdruckes.


Gruß
Loddar


Bezug
                
Bezug
Limeskriterien + eine Aufgabe: Frage
Status: (Frage) beantwortet Status 
Datum: 19:02 Mo 29.08.2005
Autor: DerMathematiker

Also bedeutet das, wenn c < [mm] \infty, [/mm] dann dürfte eigentlich kein n im Term vorkommen, sondern nur Konstanten? Weil ansonsten lässt es sich ja nicht konkret berechnen.

Ist das richtig so?


MfG Andi

Bezug
                        
Bezug
Limeskriterien + eine Aufgabe: auch mit n's ....
Status: (Antwort) fertig Status 
Datum: 19:15 Mo 29.08.2005
Autor: Loddar

Hallo Andi!


> Also bedeutet das, wenn c < [mm]\infty,[/mm] dann dürfte eigentlich
> kein n im Term vorkommen, sondern nur Konstanten? Weil
> ansonsten lässt es sich ja nicht konkret berechnen.

[notok] Das stimmt so nicht ...

Ich gebe Dir mal ein Beispiel:

[mm] $\limes_{n\rightarrow\infty}\bruch{6n^2+4}{3n^2-7} [/mm] \ = \ [mm] \bruch{6}{3} [/mm] \ = \ 2 \ =: \ c \ < \ [mm] \infty$ [/mm]

Hier haben wir ja sowohl in Nenner als auch im Zähler jeweils $n_$ auftreten, aber dennoch existiert hier ein Grenzwert $c_$ mit $c \ < \ [mm] \infty$ [/mm] .


Nun etwas klarer?

Gruß
Loddar


Bezug
                                
Bezug
Limeskriterien + eine Aufgabe: Danke + Zusammenfassung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:46 Mo 29.08.2005
Autor: DerMathematiker

Hi,

ok, jetzt hab ich's endlich gepeilt, wenn man L'Hopital anwenden würde, dann wäre es ja noch klarer, da sich ja dann das n wegkürzt und dann genau diese 2 stehen bleibt.

Das ganze geht aber gegen unendlich, wenn z.Bsp. [mm] \frac{n^3}{n^2} [/mm] da steht, oder? Weil, dann kann man ja 2x l'Hopital anwenden und man erhält n und das geht ja trivialerweise gegen unendlich.

Also ich hoffe, dass meine folgende Aussagen nun stimmt:

c < [mm] \infty [/mm] gilt dann, wenn entweder ein konstanter Term da steht oder wenn es gegen einen reellen Wert konvergiert, d.h. wenn man z. Bsp. durch l'Hopital die n's beseitigen kann. Ich hoffe, das ist jetzt so ungefähr richtig. Falls es falsch ist, könntest du ein Beispiel machen, wo etwas gegen unendlich konvergiert?

Meiner Meinung ist das immer dann der Fall, wenn [mm] \frac{n^x}{n^y} [/mm] mit x>y gilt.

MfG Andi

PS: Sorry, ich bin in Analysis ein absoluter Versager *gg*, ich denke das hat man gemerkt.

Bezug
                                        
Bezug
Limeskriterien + eine Aufgabe: So stimmt's ...
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:41 Mo 29.08.2005
Autor: Loddar

Hallo Andreas!


Diese Zusammenfassung von Dir kann man so stehen lassen [ok] (vom Nachsatz natürlich mal abgesehen ;-) ...)


Gruß
Loddar


Bezug
        
Bezug
Limeskriterien + eine Aufgabe: Antwort zur 2ten Teilfrage
Status: (Antwort) fertig Status 
Datum: 21:08 Do 01.09.2005
Autor: Karl_Pech

Hallo Andi,


Kommen wir mal zu deiner 2ten Teilfrage:


> Zudem habe ich noch eine Frage, wie man beweisen kann, dass
> [mm]e^{\sqrt{n}} \in \mathcal{O}\left(n!\right)[/mm].
>  
> Weil mit $n!$ kann ich nicht wirklich rechnen, ich weiß, dass
>
> $n! := n [mm] *\left(n-1\right)* \ldots*1$ [/mm] und $0! := 1$
>  
> Aber sonst auch nichts, d.h. wenn ich mit der puren
> Definition nicht weiterkomme, habe ich ein Problem. Wie
> könnte man diesen Beweis führen? Bzw. was sollte man zu der
> Fakultät noch wissen?


Du könntest mal nach der Stirlingschen Näherungsformel schauen.
Allerdings wäre es übertrieben diese Formel hier zu benutzen. Die Definition, die Du oben angegeben hast, liefert dir nämlich schon eine gute Abschätzung für $n!$:


[m] \begin{array}{ccccccccccccccc} {n^n} & = & n & * & n & * & \ldots & * & n & {} & {} & * & \ldots & * & n \\ {n!} & = & n & * & {\left( {n - 1} \right)} & * & \ldots & * & {\frac{n}{2}} & {} & {} & * & \ldots & * & 1 \\ {\left(\frac{n}{2}\right)^{\frac{n}{2}}} & = & {\frac{n}{2}} & * & {\frac{n}{2}} & * & \ldots & * & {\frac{n}{2}} & * & 1 & * & \ldots & * & 1 \end{array} [/m]


Die Faktoren der dritten Gleichung sind jeweils kleiner oder gleich den Faktoren von $n!$. Das Umgekehrte gilt für die Faktoren von [mm] $n^n$. [/mm] Damit gilt insgesamt:


[mm] $\left(\bruch{n}{2}\right)^{\bruch{n}{2}} \le [/mm] n! [mm] \le n^n$ [/mm]


Könnten wir also zeigen, daß [mm] $e^{\sqrt{n}} \le \left(\bruch{n}{2}\right)^{\bruch{n}{2}}$ [/mm] ist, so hätten wir auch deine Aussage bewiesen, also versuchen wir es mal:


[m]e^{\sqrt n } \leqslant \left( {\frac{n} {2}} \right)^{\frac{n} {2}} \Rightarrow \ln \left( {e^{\sqrt n } } \right) \leqslant \ln \left( {\left( {\frac{n} {2}} \right)^{\frac{n} {2}} } \right) \Rightarrow \sqrt n \leqslant \frac{n} {2}\ln \left( {\frac{n} {2}} \right) \Rightarrow 2 \leqslant \sqrt n \ln \left( {\frac{n} {2}} \right)[/m]


Ich denke, damit wäre es gezeigt.



Grüße
Karl





Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de