Diskrete Mathematik???

22.04.2005, 16:33	Oma Hoppenstedt	Auf diesen Beitrag antworten »
Diskrete Mathematik??? Hallihallo! Ich studiere doch nur Mathe für Sek 1 und muss jetzt sowas wissen!!! http://www.math.uni-frankfurt.de/~zahri/blatt1.pdf Bitte, wäre dankbar für Tipps!!! Verstehe gerade nur Bahnhof und weiss auch nicht wofür ich den Kram später brauchen kann. Liebe Grüße
23.04.2005, 02:37	carsten	Auf diesen Beitrag antworten »
Ein paar genauere Angaben, was du alles kannst/verstanden hast und wo es genau haengt waeren sehr nett Weisst du denn wie man so einen Schaltkreis konstruiert/wie er funktioniert? Die Groessenordnung der Funktionen duerften doch mit deren Definitionen nicht zuuu schwer sein. Einfach mal die Definition hinschreiben und die Funktionen einsetzen. Gruesse Carsten
23.04.2005, 18:46	lene	Auf diesen Beitrag antworten »
hi carsten! was meinst du denn mit den definitionen der angegebenen funktionen? kannst du an der a) bitte mal zeigen, wie man da heran gehen kann?! dankeschön! viele grüße marlene
23.04.2005, 20:22	Tobias	Auf diesen Beitrag antworten »
$\begin{eqnarray} f \in O(g) \iff \exists c > 0 \; \exists n_0 \in \mathbb{N}: \; f(n) \leq c\cdot g(n) \; \forall n \geq n_0 \end{eqnarray}$ Für $\begin{eqnarray} f_1 \end{eqnarray}$ sieht man, dass für große $\begin{eqnarray} n \end{eqnarray}$ der Term $\begin{eqnarray} n - \log(n^3) \end{eqnarray}$ schnell größer wird als 1. Als ist für große n nur folgender Term zu betrachten: $\begin{eqnarray} f_1(n) = \frac{n^2}{n-\log(n^3)} \end{eqnarray}$ Es kommt hier nicht auf die genaue Grenze an sondern wir wählen z.B. n >= 16. Jetzt schätzen wir $\begin{eqnarray} n-\log(n^3) \end{eqnarray}$ nach unten ab. Da der Term im Nenner steht, bedeutet dies für $\begin{eqnarray} f_1 \end{eqnarray}$ , dass bei kleinerem Nenner der Gesamtterm größer wird. (Und wir wollen ihn schließlich nach oben abschätzen). $\begin{eqnarray} n - \log(n^3) = n - 3\log(n) \geq n - \frac{n}{2} = \frac{n}{2} \end{eqnarray}$ Damit ergibt sich die Abschätzung: $\begin{eqnarray} f_1(n) = \frac{n^2}{n-\log(n^3)} \leq \frac{n^2}{\frac{n}{2}} = 2n \end{eqnarray}$ Damit ist $\begin{eqnarray} f_1 \in O(n) \end{eqnarray}$ wenn wir z.B. $\begin{eqnarray} c := 2 \end{eqnarray}$ und $\begin{eqnarray} n_0 := 16 \end{eqnarray*}$ setzen.
24.04.2005, 23:28	lene	Auf diesen Beitrag antworten »
Hey Tobias! Es ist jetzt echt schon super spät und du siehst ja, Mathe beschäftigt uns immer noch. DANKE schon mal für die AUFGABE, haben es aber noch immer nicht ganz gerafft! Kannst du uns nicht noch ein bisschen mehr und öfter mal weiter helfen? Damit wir irgendwann auch mal so schlaue Birnen werden?! Das wäre wirklich supi! Viele Grüße lene
25.04.2005, 01:10	Tobias	Auf diesen Beitrag antworten »
Nochmal zum O-Kalkül: Eine Funktion g ist im Sinne des O-Kalküls obere Schranke von f (geschrieben $\begin{eqnarray} f \in O(g) \end{eqnarray}$ ), wenn ab einer bestimmten Eingabegröße $\begin{eqnarray} n_0 \end{eqnarray}$ ein Vielfaches $\begin{eqnarray} c\cdot g(n) \end{eqnarray}$ immer größer ist als $\begin{eqnarray} f(n) \end{eqnarray}$ . Um also formal zu beweisen, dass $\begin{eqnarray} f \in O(g) \end{eqnarray}$ , musst du ein c und ein n_0 angeben, die dieses Kriterium erfüllt. Später weicht man dann von der formalen Situation ab um es übersichtlicher und schneller zu entscheiden. Dabei setzt man dann einfach die Existenzen der Konstanten voraus. Im Allgemeinen kategorisiert man Funktionen, indem man sie so knapp wie möglich (aber so großzügig wie nötig) nach oben abschätzt. Weiteres Beispiel: $\begin{eqnarray} \log(1) + \ldots + \log(n) \end{eqnarray}$ Wir wissen, dass log streng monoton steigend ist. Das heitß, dass die Logarithmusfunktion für größere Eingaben auch größere Funktionswerte liefert. Wir schätzen jetzt einfach die n vielen Summanden alle nach log(n) ab: $\begin{eqnarray} \log(1) + \ldots + \log(n) \leq \log(n) + \log(n) + \ldots + \log(n) = n \cdot \log(n) \end{eqnarray}$ Dann sagen wir also: $\begin{eqnarray} f_2 \in O(n\log(n)) \end{eqnarray}$ Für $\begin{eqnarray} f_4 \end{eqnarray}$ bietet es sich an, die abbrechende Reihe durch die nichtabbrechende Reihe abzuschätzen. Alle Summanden der Reihe sind positiv, das bedeutet, dass die Reihe also maximal größer wird: $\begin{eqnarray} f_4(n) = \sum_{k=2}^{n}\frac{k}{2^k} \leq \sum_{k=2}^{\infty}\frac{k}{2^k} \end{eqnarray}$ Und diese unendliche Reihe konvergiert. Damit ist $\begin{eqnarray} f_4 \in O(1) \end{eqnarray}$
Anzeige

25.04.2005, 19:17	Oma Hoppenstedt	Auf diesen Beitrag antworten »
Hallihallo! Vielen Dank für Eure Bemühnungen, jetzt werden wir mal versuchen, damit zurecht zu kommen! Werde zur Not morgen wieder nerven! Liebe Grüße

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »