Differences

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

--- repds15:fragen-antworten [2015/10/01 19:18] – mario
+++ 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.
-----
-**Expansion**
-<WRAP round help>
-Wenn wir nach der Expansion der Rekursionsgleichung beim kleinen Gauß landen, wissen wir ja dass die Laufzeit $n^2$ beträgt. Wie lautet die Laufzeit aber, wenn wir $i^k$ oder $a^i$ anstatt nur dem i haben? Bzw was könnte hier in der Klausur noch relevant sein?
-In der ersten Klausur war das Ergebnis dieser Aufgabe die geometrische Reihe mit Laufzeit $2^n$
-</WRAP>
-Soll $i$ die Laufvariable der Summe sein? i=0,...,n? Falls ja:
-**Antwort**: Bei $a^i$ hat man eine geometrische Summe. Statt $\sum_{i=1}^n i^k$ könnt ihr auch einfach das Integral $\int_{1}^n x^k dx$ ausrechnen.
-Ansonsten hilft für Abschätzung oft [[http://www.lkozma.net/inequalities_cheat_sheet/ineq.pdf|dieses nette PDF mit "useful inequalities"]].
-----
-**Asymptotisches Wachstum**
-<WRAP round help>
-Welche Funktion wächst schneller, $n!$ oder $n^{log_2n}$ ?
-</WRAP>
-**Antwort**:
-<code>
-from math import factorial, log2
-for i in range(1, 10000):
-    a = factorial(i)
-    b = i**log2(i)
-    print(b/a)    # Das geht gegen 0. Was heißt das?
-</code>
-----
-**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?
-</WRAP>
-**Antwort**: Nein, A[u]>A[v] bedeutet, dass u später besucht wurde. Grafisch kannst du dir das so vorstellen, als würdest du mit deinem Ariadne-Faden um den Tiefensuchebaum herumlaufen und die Schritte zählen. Wenn du links von einem Knoten u bist, trägst du die Schrittzahl in A[u] ein, wenn du rechts neben dem Knoten u bist, trägst du E[u] ein. Siehe [[https://en.wikipedia.org/wiki/Tree_traversal]]
-----
-**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.