Differences

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

--- repds15:fragen-antworten [2015/10/04 17:53] – [Fragen und Antworten] 95.222.28.193
+++ 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**: Die innere Schleife endet in jedem Durchlauf der äußeren Schleife nach spätestens $O(\log(n))$ Schritten wegen ''j=j*2'', wenn man j=1 als Startwert annimmt. Somit haben wir insgesamt $O(n \log(n))$ als obere Abschätzung. Die untere $\Omega$-Abschätzung kriegen wir, wenn wir nur "großen" Anteile der Laufzeit analysieren. <del>Dafür gucken wir diesen leicht modifizierten Code an:</del>
-<code> #### So nicht!!! Falsch!!! Mein Fehler, Gruß, Mario #####
-for ( i=1; i<n/2; i++)
-  for ( j=n/2; j<n; j=j*2)
-</code>
-<del>Man kann sich überlegen, dass die äußere Schleife nun nur noch halb so oft läuft und die innere Schleife auch seltener. Dennoch erhalten wir $n/2 \cdot \log(n/2) = \Omega(n \log(n))$ als Laufzeit.
-Somit sind die obere und untere Schranke identisch und wir erhalten $\Theta(n \log(n))$ als Laufzeit.</del>
-**Achtung (Fehlerkorrektur)**: Mit dem modifizierten Code läuft die innere Schleife immer nur einmal. So kommt man nicht auf $n \log(n)$, sondern nur auf $n$ bzw. $n/2$. Besser man schreibt die Schleifen als Summenformel auf: $\sum_{i=1}^n \log(n-i) \approx \int_1^n \log(x) dx = \Theta(n \log(n))$
-**Folgefrage**:
-Ich habe das mal codiert und war über das Ergebnis T(n)= 2n verwundert.
-Für j=1 statt j=i stimmt jedoch $O(n \log n)$, was ich auch vermutet hatte.
-Vielleicht kann jemand den Code mal nachvollziehen.
-<code>
-void  f5 (int n)  // n = 1000000
-{
-	int i = n;
-	int j = 0;
-	int c = 0;
-	{
-		 for (  i = 1;   i < n; i++ )
-    	            for ( j = i;   j < n; j *= 2 )
-		     { cout <<  "c: " << ++c <<  "  i: " << i <<  "  j: " << j <<  endl; }
-	}
-}              //  Aufruf f5(1000000) ergibt:   c: 1999986  i: 999999  j: 999999
-</code>
-**"Antwort"**: Hmm, jetzt bin ich selbst verwundert. [[http://www.wolframalpha.com/input/?i=int+log_2%28x%29+dx|Wolframalpha]] bestätigt eigentlich die Analyse mit der Summenformel von oben. Hast du mal noch größere Werte ausprobiert?
-**"Re:Antwort"**:   f5(1000000000) ergibt:    c: 1999999977  i: 1000000000  j: 1999999998
-----
-**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.