Praktische Grenzen der Berechenbarkeit

Motivation

Bei der Entwicklung eines effizienten Algorithmus spielt die Komplexitätstheorie eine große Rolle. Sie dient der Bewertung von Programmen und ermöglicht den Vergleich verschiedener Algorithmen bezüglich ihrer Laufzeit oder ihrem Speicherbedarf. Hierzu führt man, in Anlehnung an die Mathematik, Funktionsklassen ein, um die Algorithmen zu klassifizieren.

Ein Algorithmus heißt effizient, wenn er ein Problem mit möglichst geringem Ressourcenverbrauch (Zeit oder Speicher) löst.

Funktionsgraphen

Wie gut kennst du noch die Funktionsgraphen und Funktionsnamen? Ordne den Funktionsgraphen die zugehörigen Funktionsnamen und Funktionsterme zu!

	Exponentialfunktion	$f(x)=e^x$
	$f(x)=x$	Lineare Funktion
	Potenzfunktion	$f(x)=x^2$

Lineare Suche

Der unten stehende Algorithmus durchsucht ein gegebenes Array a nach einem Objekt x.

Algorithmus lineare_suche
Eingabe: Ein Array a der Länge n und ein zu suchendes Objekt x
Ausgabe true, wenn es ein j, 1 <= 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
}

Der Algorithmus geht die Elemente des Arrays der Reihe nach durch. Dabei vergleicht er jedes Element mit dem Objekt x. Das Programm endet, sobald x gefunden oder das Ende des Arrays erreicht worden ist.

Zur Analyse der Laufzeit des Algorithmus zählt man die elementaren Rechenoperationen. Hierzu zählen:

• Vergleiche wie "<", ">", "=", "and", "not",...
• Wertzuweisungen wie ":="
• Rechenoperationen wie "+", "-", "*", "/",...

Die Zahl der benötigten Rechenoperationen hängt offensichtlich von der Größe des Array und ob bzw. an welcher Stelle im Array das Objekt x vorkommt. Im besten Fall (englisch "best case") benötigt man also sechs elementare Rechenoperationen. Dies ist der Fall wenn das gesuchte Objekt im ersten Arrayfeld ist. Hier wird die while-Schleife nicht durchlaufen.

Im schlechtesten Fall wird die while-Schleife (n-1)-mal durchlaufen. Dies ist der Fall, wenn das gesuchte Objekt x überhaupt nicht im Array vorhanden ist. Dann benötigt man $3+(n-1)\cdot 7 = 7\cdot n - 4$ elementare Rechenoperationen.

Interessant ist auch der durchschnittliche Fall (englisch "average case"). Hier wird die durchschnittliche Laufzeit über alle Möglichkeiten unter Berücksichtung der Wahrscheinlichkeit für die Eingabe a gemittelt. Man benötigt im Durchschnitt $3+4\cdot(n-1)= 4\cdot n - 1$ Rechenschritte.

Mit $T(n)$ wird die Anzahl der elementaren Rechenoperationen in Abhängigkeit von der Länge des Arrays bezeichnet.

Zusammenfassend erhalten wir:

• $T_{best}(n)= 6$
• $T_{average}(n)=4\cdot n - 1$
• $T_{worst}(n)= 7\cdot n - 4$

Türme von Hanoi

Das Spiel Türme von Hanoi besteht aus drei Stäben A,B und C, auf die verschieden große, gelochte Scheiben gesteckt werden können. Ziel des Spieles ist es, denn Stapel von Stab A auf Stab C zu verschieben. Dabei darf immer nur eine Scheibe auf eine anderen Stab gesteckt werden, wobei auf dem Zielstab keine kleinere Scheibe sein darf. Die Scheiben sind auf jedem Stab also der Größe nach geordnet.

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

Zusatzinformation: [Anzeigen][Verstecken]

Die Originalversion der Türme von Hanoi wurde von buddhistischen Mönchen ausgedacht. Dabei gab es ebenfalls 3 Stäbe, aber 64 Scheiben. Die Mönche prophezeiten das Ende der Welt, falls diese Aufgabe gelöst werde. Für die Lösung benötigt man mehr als $1,8\cdot 10^{19}$ Scheibenbewegungen. Würde ein Mensch für eine Scheibenbewegung 1 Sekunde benötigen, würde das Lösen der Aufgabe 584.942.417.355 Jahre dauern, ohne auch nur geschlafen zu haben.

Wachstum von Funktionen

Gegeben sind die untenstehenden Funktionen. Ab welchem ganzzahligen $x$ ist das exponentielle Wachstum von $f(x)$ schlechter als das polynomielle der Funktionen $g,\,h,\,i$?

• $f(x)=2^x$
• $g(x)=x^2$
• $h(x) = x \cdot \log_2 (x)$
• $i(x) = 2\cdot x$

(Hinweis: Stelle zur Bestimmung eine Wertetabelle auf oder löse die Aufgabe graphisch!)

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

Tabelle als Lückentext zum Ausfüllen

[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$.

Spielstellungen beim Schach

In den Nachrichten liest man von Zeit zu Zeit einen Artikel über Schach-Matches zwischen Schachgroßmeistern wie "Garri Kasparow" und Supercomputern wie "Deep Blue". Doch warum braucht man dazu Supercomputer? Und warum gewinnt der Computer nicht immer? Die Antwort auf diese Frage kannst du dir vielleicht schon nach dieser Aufgabe selbst beantworten!

Ein Computerschachprogramm baut sich für jede Spielsituation einen Spielbaum auf und analysiert mit diesem, welcher Zug den größten Erfolg bringt. Um die Größe eines solchen Spielbaums geht es in dieser Aufgabe:

• Wie viele Knoten hat ein Schachspielbaum, bei dem jeder Halbzug (d.h. schwarz oder weiß ist am Zug) 5 Zugmöglichkeiten hat und ein Spiel im Durchschnitt nach 60 Halbzügen beendet ist?
• Kann man diesen Spielbaum auf einer handelsüblichen Festplatte speichern, wenn pro Knoten des Spielbaums 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\cdot 10^{35}$ GB benötigen. Eine Studie von IDC hat für 2007 prognostiziert, dass der weltweit verfügbare Speicherplatz $2,8\cdot 10^{11}$ GB beträgt. Es ist also nicht möglich einen solchen Spielbaum zu speichern.