Differences

This shows you the differences between two versions of the page.

--- repds15:fragen-antworten [2015/09/27 13:15] – 78.50.221.146
+++ repds15:fragen-antworten [Unknown date] (current) – removed - external edit (Unknown date) 127.0.0.1
@@ Line 1: / Line 1: @@
-====== 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 [[repds15:hausaufgaben_loes|Hausaufgaben-Lösungsseite]], damit es keine unnötige Arbeit gibt.
-**Vorlage:**
-<WRAP round help>
-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.
-</WRAP>
-**Antwort**: Hier steht meine Antwort.
-----
-**Kantenbeziehungen**
-<WRAP round help>
-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:**
-<WRAP round help>
-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?
-</WRAP>
-**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 ====
-<WRAP round help>
-  - 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) = ?$
-</WRAP>
-**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.