Praktische Grenzen der Berechenbarkeit

Zuordnungsquiz

Ordne den Funktionsnamen die zugehörigen Graphen und Terme zu!

	Exponentialfunktion	$a \cdot e^x$
	$a \cdot x$	Lineare Funktion
	Potenzfunktion	$a \cdot x^b$

Lineare Suche

Algorithmus lineare_suche
Eingabe: Ein Array a der Länge n und ein Objekt x
Ausgabe true, wenn es ein j, l <= j <= n gibt mit a[j] = x
j := 1
found := (a[j] = x)
while (not found and j<n){
       j:=j+1
       found:=(a[j]=x)
       return found
}

Türme von Hanoi

1. Spielt man dieses Spiel mit nur einer Scheibe, so ist die Anzahl der nötigen Züge trivialerweise Eins, da die eine vorhandene Scheibe lediglich vom linken auf den rechten Stab gesteckt werden muss.
Im Falle von zwei Scheiben ist fast ebenso einfach: Man steckt die kleine Scheibe auf den mittleren Stab, bewegt die große Scheibe auf den rechten Stab und setzt die kleine Scheibe obendrauf. Man benötigt also zwei Züge.

In dieser Animation siehst du die Lösung für den Fall, dass man mit 3 Scheiben spielt.

Wie viele Schritte werden benötigt, um den Turm mit 3 Scheiben von der linken auf die rechte Seite zu bringen?

	6
	7
	8

2. Wie viele Schritte werden benötigt, um den Turm mit 4 Scheiben von der linken auf die rechte Seite zu bringen?

	15
	16
	17

3. Angenommen $n$ ist die Anzahl der Scheiben, mit denen gespielt wird. Wie verhält sich die Anzahl der benötigten Züge in Abhängigkeit von $n$?

	linear
	quadratisch
	exponentiell

Punkte: 0 / 0

Aufgabe

$f(x)=2^x$

$g(x)=x^2$

$h(x) = x \cdot log_2 (x)$

$i(x) = 2\cdot x$

Ab welchem $x$ ist das exponentielle Wachstum schlechter als das Polynomielle?

[Lösung anzeigen][Lösung ausblenden]

$\begin{matrix} x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ f(x) & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512\\ g(x) & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & 81\\ h(x) & 0 & 2 & 4,75 & 8 & 11,61 & 15,51 & 19,65 & 24 & 28,53\\ i(x) & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 \end{matrix}$

Also ist $f(x)$ schlechter als $g(x)$ für $x>4$, $f(x)$ schlechter als $h(x)$ für $x>2$, $f(x)$ schlechter als $i(x)$ für $x>2$.

Aufgabe

Schachbrett Reiskörner

Aufgabe

Wie viele Knoten hat ein Spielbaum, bei dem jeder Halbzug (das heißt ein Zug von Spieler A oder B) 5 Zugmöglichkeiten hat und ein Spiel nach 60 Halbzügen beendet ist? Kann man diesen Spielbaum auf einer handelsüblichen Festplatte speichern, wenn pro Knoten 1 Byte Speicherplatz benötigt wird?

[Lösung anzeigen][Lösung ausblenden]

Für die Speicherung eines solchen Spielbaumes würde man ungefähr $8*10^{35}$ GB benötigen. Eine Studie von IDC hat für 2008 prognostiziert, dass der weltweit verfügbare Speicherplatz $2,25*10^{21}$ Bits beträgt. Es ist also nicht möglich einen solchen Spielbaum zu speichern.