Logarithmus - Versionsgeschichte

Css: /* Binary Search */

2018-07-26T13:33:59Z

‎Binary Search

Css: /* Binary Search */

2018-07-26T13:28:56Z

‎Binary Search

Css am 26. Juli 2018 um 13:10 Uhr

2018-07-26T13:10:27Z

Css: /* Logarithmus */

2018-07-25T13:28:39Z

‎Logarithmus

Css: /* Logarithmus */

2018-07-25T13:27:43Z

‎Logarithmus

Css: /* Logarithmus */

2018-07-25T13:25:41Z

‎Logarithmus

Css: /* Logarithmus */

2018-07-25T13:22:00Z

‎Logarithmus

Css: /* Logarithmus */

2018-07-25T13:15:10Z

‎Logarithmus

Css am 25. Juli 2018 um 12:45 Uhr

2018-07-25T12:45:48Z

Css: /* Ausblick: Komplexe Exponenten */

2018-07-25T12:45:00Z

‎Ausblick: Komplexe Exponenten

← Nächstältere Version		Version vom 26. Juli 2018, 13:33 Uhr
Zeile 95:		Zeile 95:

	Mit jedem Schritt halbiert sich die Anzahl der Elemente die übrig sind. Das heißt, wenn wir am Anfang $n$ Elemente haben, haben wir nach $k$ schritten rund $(\frac{1}{2})^k\cdot n$ Elemente übrig. Das heißt, wir sind ungefähr fertig, wenn $(\frac{1}{2})^k\cdot n \approx 1$, also $n \approx 2^k$, also $k \approx \log_2 n$.		Mit jedem Schritt halbiert sich die Anzahl der Elemente die übrig sind. Das heißt, wenn wir am Anfang $n$ Elemente haben, haben wir nach $k$ schritten rund $(\frac{1}{2})^k\cdot n$ Elemente übrig. Das heißt, wir sind ungefähr fertig, wenn $(\frac{1}{2})^k\cdot n \approx 1$, also $n \approx 2^k$, also $k \approx \log_2 n$.
		+
		+	Eine ähnliche Strategie kann man zum Beispiel verwenden, um Wörterbücher zu durchsuchen.

← Nächstältere Version		Version vom 26. Juli 2018, 13:28 Uhr
Zeile 65:		Zeile 65:

	== Binary Search ==		== Binary Search ==
		+
		+	In vielen Problemen in der Informatik tritt der Logarithmus natürlich auf. Ein Beispiel stellt ''Binärsuche'' dar. Man stelle sich vor, man hätte eine sortierte Liste von Zahlen:
		+
		+	22 23 39 45 47 55 58 59 61 67 69
		+
		+	Angenommen wir wollen feststellen, ob eine bestimmte Zahl, zum Beispiel 48, darin vorkommt. Die naive Methode wäre, einfach alle Elemente durchzugehen, und mit der Zahl zu vergleichen. Dazu müssten wir im schlimmsten Fall so viele Zahlen vergleichen, wie Elemente in der Liste sind. Da wir wissen, dass die Liste sortiert ist, geht es aber schneller:
		+
		+	Wir schauen uns zunächst nur das mittlere Element an, und vergleichen es. Ist es gleich unserer Zahl, sind wir fertig. Ist es kleiner als unsere Zahl, so wissen wir, dass die Zahl höchstens rechts von uns stehen kann, ist es größer, dann links.
		+
		+	> 48
		+	↓
		+	22 23 39 45 47 55 58 59 61 67 69
		+
		+	Damit können wir alle Elemente die rechts oder links von der Zahl stehen ignorieren, effektiv stehen wir also vor dem selben Problem, aber jetzt mit einer Liste die nur rund halb so lang ist, deren Mitte wir wieder anschauen können, und immer so weiter:
		+
		+	< 48
		+	↓
		+	22 23 39 45 47
		+
		+	< 48
		+	↓
		+	39 45 47
		+
		+	< 48
		+	↓
		+	47
		+
		+	Am Ende bleibt nur noch ein Element übrig. Wenn das nicht gleich dem gesuchten Element ist wissen wir, dass es nicht vorkommt.
		+
		+	Mit jedem Schritt halbiert sich die Anzahl der Elemente die übrig sind. Das heißt, wenn wir am Anfang $n$ Elemente haben, haben wir nach $k$ schritten rund $(\frac{1}{2})^k\cdot n$ Elemente übrig. Das heißt, wir sind ungefähr fertig, wenn $(\frac{1}{2})^k\cdot n \approx 1$, also $n \approx 2^k$, also $k \approx \log_2 n$.

← Nächstältere Version		Version vom 26. Juli 2018, 13:10 Uhr
Zeile 63:		Zeile 63:

	Um nun von $e^{i\varphi}$ zu beliebigem $a^{i\varphi}$ zu kommen, können wir wiederum den Logarithmus verwenden: $a^{i\varphi} = (e^{\log_e a})^{i\varphi} = e^{i\varphi\log_e a}$. Und für komplexe Exponenten dann $a^{x+iy} = a^x\cdot a^{iy}$.		Um nun von $e^{i\varphi}$ zu beliebigem $a^{i\varphi}$ zu kommen, können wir wiederum den Logarithmus verwenden: $a^{i\varphi} = (e^{\log_e a})^{i\varphi} = e^{i\varphi\log_e a}$. Und für komplexe Exponenten dann $a^{x+iy} = a^x\cdot a^{iy}$.
		+
		+	== Binary Search ==

@@ Zeile 35: / Zeile 35: @@
 Logarithmen sind also proportional zueinander. Deshalb haben die meisten Taschenrechner keine zweistellige Logarithmusfunktion, sondern nur $\ln = \log_e$, den '''natürlichen Logarithmus''', zur Basis $e$, der Euler'schen Zahl, die rund $2,718281828$ ist. Die genaue Bedeutung der Zahl $e$ ist für den Kurs nicht wichtig. Oft schreibt man auch einfach nur $\log x$, je nach dem meint man damit den natürlichen Logarithmus, manchmal auch den Logarithmus zur Basis 10. Wir verwenden Logarithmen im Kurs hauptsächlich zur Beschreibung von Komplexitätsklassen, bei denen es auf lineare Faktoren nicht ankommt. Wenn wir im Kurs $\log x$ schreiben, ist die Basis entsprechend nicht relevant.
-$\lfloor\log_{10} a\rfloor$ gibt an, wie viele Dezimalstellen $a$ vor dem Komma hat. Analog gibt $\lfloor\log_2 a\rfloor$ an, wie viele Binärstellen $a$ hat.
+$\lceil\log_{10} a\rceil$ gibt an, wie viele Dezimalstellen $a$ vor dem Komma hat. Analog gibt $\lceil\log_2 a\rceil$ an, wie viele Binärstellen $a$ hat.
 == Ausblick: Komplexe Exponenten ==

← Nächstältere Version		Version vom 25. Juli 2018, 13:27 Uhr
Zeile 34:		Zeile 34:

	Logarithmen sind also proportional zueinander. Deshalb haben die meisten Taschenrechner keine zweistellige Logarithmusfunktion, sondern nur $\ln = \log_e$, den '''natürlichen Logarithmus''', zur Basis $e$, der Euler'schen Zahl, die rund $2,718281828$ ist. Die genaue Bedeutung der Zahl $e$ ist für den Kurs nicht wichtig. Oft schreibt man auch einfach nur $\log x$, je nach dem meint man damit den natürlichen Logarithmus, manchmal auch den Logarithmus zur Basis 10. Wir verwenden Logarithmen im Kurs hauptsächlich zur Beschreibung von Komplexitätsklassen, bei denen es auf lineare Faktoren nicht ankommt. Wenn wir im Kurs $\log x$ schreiben, ist die Basis entsprechend nicht relevant.		Logarithmen sind also proportional zueinander. Deshalb haben die meisten Taschenrechner keine zweistellige Logarithmusfunktion, sondern nur $\ln = \log_e$, den '''natürlichen Logarithmus''', zur Basis $e$, der Euler'schen Zahl, die rund $2,718281828$ ist. Die genaue Bedeutung der Zahl $e$ ist für den Kurs nicht wichtig. Oft schreibt man auch einfach nur $\log x$, je nach dem meint man damit den natürlichen Logarithmus, manchmal auch den Logarithmus zur Basis 10. Wir verwenden Logarithmen im Kurs hauptsächlich zur Beschreibung von Komplexitätsklassen, bei denen es auf lineare Faktoren nicht ankommt. Wenn wir im Kurs $\log x$ schreiben, ist die Basis entsprechend nicht relevant.
		+
		+	$\lfloor\log_{10} a\rfloor$ gibt an, wie viele Dezimalstellen $a$ vor dem Komma hat. Analog gibt $\lfloor\log_2 a\rfloor$ an, wie viele Binärstellen $a$ hat.

	== Ausblick: Komplexe Exponenten ==		== Ausblick: Komplexe Exponenten ==

← Nächstältere Version		Version vom 25. Juli 2018, 13:25 Uhr
Zeile 32:		Zeile 32:

	Weiterhin ist $\log_b x = \frac{\log_a x}{\log_a b}$. Denn ist $b^y=x$, und $a^z=b$, so ist $(a^z)^y=a^{zy}=x$, also $\log_a x=zy = \log_a b \cdot \log_b x$.		Weiterhin ist $\log_b x = \frac{\log_a x}{\log_a b}$. Denn ist $b^y=x$, und $a^z=b$, so ist $(a^z)^y=a^{zy}=x$, also $\log_a x=zy = \log_a b \cdot \log_b x$.
		+
		+	Logarithmen sind also proportional zueinander. Deshalb haben die meisten Taschenrechner keine zweistellige Logarithmusfunktion, sondern nur $\ln = \log_e$, den '''natürlichen Logarithmus''', zur Basis $e$, der Euler'schen Zahl, die rund $2,718281828$ ist. Die genaue Bedeutung der Zahl $e$ ist für den Kurs nicht wichtig. Oft schreibt man auch einfach nur $\log x$, je nach dem meint man damit den natürlichen Logarithmus, manchmal auch den Logarithmus zur Basis 10. Wir verwenden Logarithmen im Kurs hauptsächlich zur Beschreibung von Komplexitätsklassen, bei denen es auf lineare Faktoren nicht ankommt. Wenn wir im Kurs $\log x$ schreiben, ist die Basis entsprechend nicht relevant.

	== Ausblick: Komplexe Exponenten ==		== Ausblick: Komplexe Exponenten ==

← Nächstältere Version		Version vom 25. Juli 2018, 13:22 Uhr
Zeile 26:		Zeile 26:

	Gegeben sei die Gleichung $a^b=c$. Haben wir $a$ und $b$ gegeben, können wir $c$ leicht ausrechnen. Haben wir umgekehrt $b$ und $c$ gegeben, ist $a=c^{\frac{1}{b}}$ ebenfalls leicht auszurechnen. Was wir noch nicht können, ist, auszurechnen, was $b$ sein muss, wenn wir $a$ und $c$ gegeben haben. Dieses $b$ nennt man den '''Logarithmus''' zur Basis $a$ von $c$, und schreibt $\log_a c$.		Gegeben sei die Gleichung $a^b=c$. Haben wir $a$ und $b$ gegeben, können wir $c$ leicht ausrechnen. Haben wir umgekehrt $b$ und $c$ gegeben, ist $a=c^{\frac{1}{b}}$ ebenfalls leicht auszurechnen. Was wir noch nicht können, ist, auszurechnen, was $b$ sein muss, wenn wir $a$ und $c$ gegeben haben. Dieses $b$ nennt man den '''Logarithmus''' zur Basis $a$ von $c$, und schreibt $\log_a c$.
		+
		+	Logarithmen haben einige schöne Eigenschaften.
		+
		+	Zunächst ist $\log_a (b\cdot c) = \log_a b + \log_a c$. Das sieht man leicht, indem man sich überlegt, dass wenn $a^x=b$ und $a^y=c$ ist, dann $a^{x+y}=a^x\cdot a^y = b\cdot c$. Auf diesem Prinzip basieren Rechenschieber.
		+
		+	Weiterhin ist $\log_b x = \frac{\log_a x}{\log_a b}$. Denn ist $b^y=x$, und $a^z=b$, so ist $(a^z)^y=a^{zy}=x$, also $\log_a x=zy = \log_a b \cdot \log_b x$.

	== Ausblick: Komplexe Exponenten ==		== Ausblick: Komplexe Exponenten ==

← Nächstältere Version		Version vom 25. Juli 2018, 13:15 Uhr
Zeile 25:		Zeile 25:
	== Logarithmus ==		== Logarithmus ==

		+	Gegeben sei die Gleichung $a^b=c$. Haben wir $a$ und $b$ gegeben, können wir $c$ leicht ausrechnen. Haben wir umgekehrt $b$ und $c$ gegeben, ist $a=c^{\frac{1}{b}}$ ebenfalls leicht auszurechnen. Was wir noch nicht können, ist, auszurechnen, was $b$ sein muss, wenn wir $a$ und $c$ gegeben haben. Dieses $b$ nennt man den '''Logarithmus''' zur Basis $a$ von $c$, und schreibt $\log_a c$.

	== Ausblick: Komplexe Exponenten ==		== Ausblick: Komplexe Exponenten ==

@@ Zeile 22: / Zeile 22: @@
 Wir können auf diese Weise beliebig genaue Näherungen von $a^r$ berechnen.
 == Ausblick: Komplexe Exponenten ==
@@ Zeile 49: / Zeile 52: @@
 Um nun von $e^{i\varphi}$ zu beliebigem $a^{i\varphi}$ zu kommen, können wir wiederum den Logarithmus verwenden: $a^{i\varphi} = (e^{\log_e a})^{i\varphi} = e^{i\varphi\log_e a}$. Und für komplexe Exponenten dann $a^{x+iy} = a^x\cdot a^{iy}$.

@@ Zeile 46: / Zeile 46: @@
 \end{align}$
-Insbesondere ist also $e^{i\pi} + 1 = 0$.
+Insbesondere ist also $e^{i\pi} + 1 = 0$ (bekannte Formel).
 == Logarithmus ==