O und Omega Notation < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:12 Do 29.04.2010 | | Autor: | matheja |
| Aufgabe | Hallo Leute,
ich brauch hilfe wie ich folgende Behauptungen beweisen kann.
a) [mm] 4n^{5} [/mm] − [mm] 3n^{2} [/mm] − 5n + 1 ist [mm] O(n^{5})
[/mm]
[mm] b)4n^{5} [/mm] − [mm] 3n^{2} [/mm] − 5n + [mm] 1=n^{5} [/mm] +3 [mm] *(n^{5} [/mm] − [mm] n^{2}) [/mm] − 5n + 1 ist [mm] \Omega(n^{5})
[/mm]
c)Ist P(n) = [mm] a_k [/mm] * [mm] n^{k} [/mm] + [mm] a_{k−1} [/mm] * [mm] n_{k−1} [/mm] + ... + [mm] a_2 [/mm] * [mm] n^{2} [/mm] + [mm] a_1 [/mm] * n + [mm] a_0 [/mm] ein Polynom vom Grad k,
dann gilt: P(n) ist [mm] O(n^{k}) [/mm] und log P(n) ist O(log n) |
Ich hab mich im netz zu diesem Thema umgeschaut wie man so was beweisen kann ,doch leider bin ich nicht viel schlauer wie vorher
beste grüße vom matheja
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:28 Do 29.04.2010 | | Autor: | iMod109 |
Hallo matheja,
zum Aufgabenteil a):
Die GroßO-Notation gibt eine obere Schranke an, damit man die Laufzeit von Algorithmen besser abschätzen kann. Dazu ein Beispiel:
f(n) [mm] \in [/mm] O(g(n)), wenn gilt f(n) [mm] \le [/mm] c*g(n) , ab einem bestimmten Wert [mm] n_{0}.
[/mm]
Die Strategie für den Beweis lautet wie folgt: Finde passende Werte c und [mm] n_{0}, [/mm] so dass [mm] 4n^{5}-3n^{2}-5n+1 \le c*n^{5} [/mm] für alle n > [mm] n_{0} [/mm] Dabei hilft dir sicherlich eine Wertetabelle. Wenn du diese beiden Werte gefunden hast, hast du auch bewiesen, dass diese Funktion in O(n) liegt.
Aufgabenteil b) ist fast identisch nur dass du mir die untere Grenze finden sollst. Also wieder c und [mm] n_{0} [/mm] finden, so dass [mm] 4n^{5}-3n^{2}-5n+1 \ge c*n^{5}. [/mm] Aufpassen umgedrehtes Relationszeichen.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:37 Di 04.05.2010 | | Autor: | matheja |
| Aufgabe | Moin,
so ich hab nun die Aufgaben bearbeitet und poste meine Ergebnisse.
Ich mir nicht ganz sicher ob diese richtig sind |
a) [mm] 4n^{5}-3n^{2}-5n+1 \le c\cdot{}n^{5} [/mm]
Vollständige Induktion:
IA: wähle [mm] n_0=1 [/mm] und c=4
=> [mm] 4*1^{5}-3*1^{2}-5*1+1 \le 4*1^{5} [/mm]
=> -3 [mm] \le [/mm] 4
IV: [mm] T_1(n) \le [/mm] * [mm] n^{5}
[/mm]
IS:n->n+1 und c=4
[mm] =>4(n+1)^{5}-3(n+1)^{2}-5(n+1)+1 \le 4*(n+1)^{5} [/mm] | [mm] -4(n+1)^{5}
[/mm]
=> [mm] 3(n+1)^{2}-5(n+1)+1 \le [/mm] 0 qed
b) Auch vollständige Induktion:
Zu zeigen: [mm] 4n^{5}-3n^{2}-5n+1=n^{5}+3(n^{5}-n{2})-5n+1 \ge [/mm] c*n^
Wenn man den rechten Term umformt erhält man
[mm] 4n^{5}-3n^{2}-5n+1=4n^{5}-3n^{2}-5n+1
[/mm]
Also nehme ich an dass [mm] 4n^{5}-3n^{2}-5n+1 \ge c*n^{5}
[/mm]
IA: Wähle n=2 und c=3
[mm] =>107>3*2^{5}=96
[/mm]
IV: [mm] T_2 [/mm] (n) [mm] \ge [/mm] c* [mm] n^{5}
[/mm]
IS:n->n+1 und c=3
[mm] 4(n+1)^{5}-3(n+1)^{2}-5(n+1)+1 \le 3*(n+1)^{5} [/mm] | [mm] :(n+1)^5 [/mm] |-3 <=>
[mm] 1-\bruch{3}{(n+1)^3}-\bruch{5}{(n+1)^4}-\bruch{1}{(n+1)^5} \ge [/mm] 0
[mm] \limes_{n\rightarrow\infty} \bruch{3}{(n+1)^3} [/mm] ->0
[mm] \limes_{n\rightarrow\infty} bruch{5}{(n+1)^4}->0
[/mm]
[mm] \limes_{n\rightarrow\infty} bruch{1}{(n+1)^5}->0
[/mm]
somit wär die aussage bewiesen oder ?
Was mich hier verwirrt das die aussage für n=1 und c=4 nicht gilt
muss sie aber nicht für alle c und n gelten oder hab ich da was falsch verstanden?
c)
Zu Zeigen
1) [mm] P(n)=O(n^{k})
[/mm]
2) log P(n)= O(log n)
zu 1)
Laut definition der O-notation gilt:
P(n) [mm] \le a_k *n^{k}+...+a_1*n+a_0 [/mm] | [mm] n^{k} [/mm] ausklammern
[mm] \le (a_k +\bruch{a_{k-1}}{n}+...+\bruch{a_0}{n^{k}})*n^{k}
[/mm]
[mm] \le (a_k +a_{k-1}+...+a_0)*n^{k}
[/mm]
wähle [mm] c=(a_k +a_{k-1}+...+a_0) [/mm] und [mm] n_0=1 [/mm] => P(n) [mm] \le c*n^{k} [/mm] qed
2) log P(n) => O(log n)
Bin genau wie bei 1) vorgegangen
es gilt zusätlich dass, der Logarithmus eines Produktes gleich der summer der faktoren entspricht (siehe: wiki Logarithmusgesetze)
=>
log [mm] P(n)\le [/mm] log [mm] (a_k *n^{k})+...+log(a_1*n)+log(a_0 [/mm] ) | [mm] n^{k} [/mm] und log ausklammern
[mm] \le ((a_k )+\bruch{a_{k-1}}{log(n)}+...+\bruch{a_0}{log(n^{k})})*log (n^{k})
[/mm]
[mm] \le (a_k +a_{k-1}+...+a_0)*log (n^{k})
[/mm]
.
.
.
ab hier weiß ich nicht mehr weiter :(
rauskommen sollte das hier:
=> P(n) [mm] \le [/mm] c*log n
=> 0 (log n)
Danke für alle die helfen
beste grüße
matheja
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Do 06.05.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 13:37 Mo 03.05.2010 | | Autor: | matheja |
| Aufgabe | Moin,
Danke Imod :)
Ich hab die a und b nun so lösen können wie du es mir gesagt.ich hab zusätlich die vollständige Induktion angwendet.
|
Nur für c) brauch ich nochmals hilfe, wie würdet ihr an diese Aufgabe gehen
beste grüße
matheja
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:29 Mo 03.05.2010 | | Autor: | iMod109 |
Wenn du ein Polynom vom Grad k hast, bedeutet dass der höchste Exponent k ist. Also für ein Polynom vom Grad 3: [mm] P(x)=a_{0}*x^{3}+a_{1}*x^{2}+a_{2}*x+a_{4}, [/mm] wobei [mm] a_{0-4} [/mm] konstante Koefizienten sind.
Für die Abschätzung von oberen oder unteren Schranken genügt es bei einem Polynom den höchsten Exponenten zu beachten, da die niedrigeren Ausdrücke für große Werte nicht ins Gewicht fallen:
Beispiel: [mm] P(x)=x^{2}+4*x
[/mm]
Wenn man hier x = 100 wählt, ist das Ergebnis 10400. [mm] x^{2} [/mm] alleine wäre schon 10000. Den Unterschied, den das 4*x macht, ist also sehr gering und wird für größere Werte x fast unbedeutend. (im Zweifelsfall einfach mal ausprobieren)
Bei der Aufgabe c musst du nun zeigen, dass Polynome vom Grad k die Obere Schranke [mm] n^{k} [/mm] haben. Ich würde in diesem Fall in einem kurzen Text begründen, warum die Exponenten kleiner k kaum ins Gewicht fallen, so dass es wieder wie in Aufgabe a) und b) Werte c und [mm] n_{0} [/mm] gibt, so dass [mm] c*n^{k} \ge [/mm] P(n), ab einem Wert [mm] n_{0}.
[/mm]
Für die zweite Hälfte müsste dir jemand anderes helfen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Mi 05.05.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
