minimale laufzeit für paramet. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben seien Graphenalgorithmen mit den unten angegebenen Laufzeiten. Dabei ist n die Anzahl der Knoten, m die Anzahl der Kanten und k ein Parameter ,der von n und m abhängt und im jeweiligen Algorithmus bestimmt wird. Wie muss k jeweils gewählt werden, damit die Algorithmen asymptotisch minimale Laufzeit haben?
a) O [mm] (\bruch{n^3}{k} [/mm] + knm )
b) O (nk + [mm] \bruch{m}{k} [/mm] )
c) O [mm] (\bruch{m log(n)}{log(k)} [/mm] + [mm] \bruch{nk log(n)}{log(k)} [/mm] ) |
Hallo!
Also ich bin bei a und b folgendermaßen vorgegangen:
aufgabe a) :
Also ich habe [mm] \bruch{n^3}{k} [/mm] + knm nach k abgeleitet und erhalte [mm] \bruch{-n^3}{k^2} [/mm] + nm
wenn ich das ganze 0 setze, erhalte ich 2 mögliche lösungen für k:
k1 = [mm] \bruch{n}{\wurzel{m}} [/mm] und k2 = - [mm] \bruch{n}{\wurzel{m}} [/mm]
und dann habe ich meine erste ableitung noch einmal nach k abgeleitet und meine k1 und k2 dann eingesetzt.
2. ableitung nach k : [mm] \bruch{2n^3}{k^3}
[/mm]
wenn ich dann k1 und k2 einsetze, dann ist die 2. ableitung für k1 größer 0 => Minimum
und für k2 ist sie kleiner 0 => Maximum
=> mein k1 ist das gesuchte k
aufgabe b):
Also da habe ich das ganze wie bei aufgabe a gemacht, also erstmal nach k abgeleitet und erhalte:
n - [mm] \bruch{m}{k^2}
[/mm]
nun habe ich auch hier das ganze 0 gesetzt und erhalte als lösung für k:
[mm] k_{1/2} [/mm] = [mm] \pm \wurzel{m/n}
[/mm]
dann habe ich ebenfalls die 2. ableitung gebildet und erhalte:
[mm] \bruch{2m}{k^3}
[/mm]
wenn ih nun k1 bzw. k2 einsetze, ist die 2. ableitung für k1 größer 0 => minimum
für k2 ist sie kleiner 0 => Maximum
=> k1 ist das gesuchte k
(k1 ist die lösung mit dem +)
So, jetzt hatten wir zu dem ganzen aber keine Übung und auch keine beispiele, daher wollte ich fragen, ob das ganze so überhaupt richtig ist vom lösungsweg her und wenn ja, ob meine ergebnisse so in ordnung sind?
(wenn die vorgehensweise falsch ist, wie könnte ich das dann machen? )
Und zur Aufgabe c) habe ich leider noch nicht wirklich einen Ansatz. Eine Ableitung zu bilden, und dann nach k umzustellen, funktioniert ja hier leider nicht besonders gut (und das soll hier wohl auch anders gemacht werden, wenn ich den professor richtig verstanden habe).
Ich hatte mir zuerst überlegt, dass, wenn k n ist, sich dann ja das log n herauskürzen würde und ich hätte eine laufzeit von m + [mm] n^2 [/mm] (es sei denn n=1...)
Oder ich könnte das k sehr nah an 0 heranbringen, denn dann wird logk immer größer (und somit der bruch immer kleiner) und auch nk logn wird dann sehr klein.
Aber da k von m und n abhängt, weiß ich nicht genau, wie ich das richtig darstellen kann...
Könnte mir hier jemand weiterhelfen?
Vielen Dank im Voraus, die_conny
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Fr 16.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
