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 [2015/10/04 18:20] – mario
@@ Line 13: / Line 13: @@
 ----
-**Kantenbeziehungen**
+**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
+**"Re:Re:Antwort"**: Und die Initialisierung von i und j zu Beginn der Funktion sowie die fehlenden Klammer der i-Schleife machen wirklich nichts aus? Ich bin gerade mittelmäßig verwirrt, wieso die experimentellen Ergebnisse meine Summenformel-Analyse nicht zu bestätigen scheinen... :( Wie kann denn j im Code oben am Ende eine ungerade Zahl sein?
+----
+**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:**