Differences

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

--- repds15:fragen-antworten [2015/09/27 07:28] – [Fragen und Antworten] 95.222.28.156
+++ 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.
-----
-**Master-Theorem, 3 Fall:**
-<WRAP round help>
-Hier war die Nebenbedingung zu beachten: $a * f(n/b) \leq \alpha * f(n)$
-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**: Hier steht meine Antwort.
-----
-==== 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.