Differences

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

--- repds15:fragen-antworten [2015/10/04 15:52] – 94.219.213.151
+++ 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.
-----
-**Laufzeit**
-<WRAP round help>
-Wie schätze ich die Laufzeit ab?
-<code>
-i = n
-j = c = 0
-for ( i=1; i<n; i++)
-  for ( j=i; j<n; j=j*2)
-     print c
-</code>
-</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>
-Darf man beide Seiten logarithmieren und dann vergleichen?
-**Antwort**: Das kann man machen, aber dann muss man aufpassen, dass man keine falschen Schlüsse zieht. Beispielsweise ist  $2^{n/2} = o(2^n)$ . Wenn man beide Seiten logarithmiert kommt man auf  $n/2$  und  $n$  und diese beiden Terme wachsen bekanntlich gleich schnell. Daraus kann man jedoch nicht auf das Wachstum von  $2^{n/2}$  und  $2^n$  schließen.
-In der Aufgabe sieht das wie folgt aus:
-  *  $\log(n!) = \sum_{i=1}^n \log(i) \approx \int_1^n \log(x) dx = \Theta(n \log(n))$
-  *  $\log(n^{\log(n)}) = \log(n) \cdot \log(n) = (\log(n))^2$
-Daraus kann man also wirklich schließen, dass  $n!$  schneller wächst.
-----
-**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.