Repds15:fragen-antworten

This is an old revision of the document!

Fragen und Antworten

Bitte setzt neue Fragen oben in das jeweilige Kapitel, damit die schon beantworten Fragen unten stehen. Bevor ihr eine Frage stellt, durchsucht bitte kurz diese Seite und die Hausaufgaben-Lösungsseite, damit es keine unnötige Arbeit gibt.

Vorlage:

Hier steht meine Frage…

Folgefrage: Hier steht noch eine Frage, weil mir die Antwort nicht gefällt oder ich noch weitere Fragen zum selben Thema habe.

Antwort: Hier steht meine Antwort.

Kantenbeziehungen

Hier haben wir ja die Bedingungen besprochen für Querkanten, Vorwärtskanten und Rückwärtskanten. In dem Fall A[u]>A[v] ist klar, dass der Knoten u vor dem Knoten v bei der Tiefensuche besucht wurde. Wie ist dann aber E[u]>E[v] zu verstehen?

Master-Theorem, 3 Fall:

Hier war die Nebenbedingung zu beachten: $a \cdot f(n/b) \leq \alpha \cdot f(n)$ und $0 < \alpha < 1$

Was sagt diese Ungleichung aus? Gibt es ein Beispiel für den Fall, daß man den dritten Fall des Master-Theorems nicht anwenden kann, weil die Ungleichung nicht erfüllt ist?

Antwort: $a \cdot f(n/b)$ ist der Aufwand, der für die $a$ rekursiven Aufrufe im nächsten Level des Rekursionsbaums anfällt. Angenommen die Nebenbedingung würde nicht gelten: $a \cdot f(n/b) > \alpha \cdot f(n)$. Dann ist es teurer, die $a$ rekursiven Aufrufe zu machen und entsprechend hält die Schranke $T(n) = \Theta(f(n))$ nicht mehr. Für das Theta brauchen wir dann auch $\alpha < 1$, damit die Summe der Laufzeiten aller rekursiven Aufrufe im ganzen Rekursionsbaum insgesamt die Form einer geometrischen Summe haben.

Beispiel: Wähle $a = b = 1$ und $f(n) = n$. Dann ist $f(n) = n = \Omega(n^\varepsilon)$ für jedes $0 < \varepsilon < 1$, aber $a \cdot f(n/b) = f(n) \leq \alpha \cdot f(n)$ gilt für kein $\alpha < 1$.

Logarithmen

Wie berechne ich

$\log_{2}(n^4 + 3x)$ - hier macht mir das 3x Probleme ;(
$\log_{10} (2/n^2)$ So scheint es nicht zu funktionieren: $\log_{10}(2/n^2) = \log_{10}(2)-2 \cdot \log_{10}(n) = ?$

Antwort:

$\log_{2}(n^4 + 3x)$: Wenn das $x$ eine Konstante ist bzw. für die Laufzeitanalyse nicht beachtet werden soll (also die Theta-Notation nur in Abhängigkeit von $n$ benutzt wird), dann erhalten wir $\log_2(n^4 + 3x) = \Theta(\log_2(n^4)) = \Theta(\log(n))$. Falls es ein Schreibfehler war: $\log_2(n^4 + 3n) \leq \log_2(n^4 + n^4) = \log_2(2n^4) = \log_2(2) + \log_2(n^4) = 1 + 4 \log_2(n)$, wobei wir annehmen, dass $n$ groß genug für die Ungleichung ist. Das dürfen wir, da wir nur an einer asymptotischen Betrachtung interessiert sind. Außerdem erhalten wir $\log_{2}(n^4 + 3n) \geq \log_2(n^4) = 4 \log_2(n)$ und somit insgesamt: $4 \log_2(n) \leq \log_2(n^4 + 3n) \leq 1 + 4 \log_2(n)$. Nach unten und oben ist es durch einen $\Theta(log_2(n))$-Term beschränkt.
$\log_{10}(2/n^2)$: Die Rechnung stimmt. Der Logarithmus darf auch negativ sein, denn die Exponentialfunktion erlaubt auch negative Exponenten. Für das Thema Laufzeitanalyse macht das jedoch keinen Sinn.