Praktische Grenzen der Berechenbarkeit
Inhaltsverzeichnis |
Zuordnungsquiz
Ordne den Funktionsnamen die zugehörigen Graphen und Terme zu!
Exponentialfunktion | ||
Lineare Funktion | ||
Potenzfunktion |
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 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 Rechenschritte.
Mit wird die Anzahl der elementaren Rechenoperationen in Abhängigkeit von der Länge des Arrays bezeichnet.
Zusammenfassend erhalten wir:
Türme von Hanoi
Die Originalversion 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 Scheibenbewegungen. Würde ein Mensch für eine Scheibenbewegung 1 Sekunde benötigen, würde das Lösen der Aufgabe 584942417355 Jahre dauern, ohne auch nur geschlafen zu haben.,
Wachstum von Funktionen
Gegeben sind die Funktionen und . Ab welchem ganzzahligen ist das exponentielle Wachstum von schlechter als das polynomielle der Funktionen ? (Stelle zur Bestimmung eine Wertetabelle auf!)
Also ist schlechter als für , schlechter als für , schlechter als für .
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?
Für die Speicherung eines solchen Spielbaumes würde man ungefähr GB benötigen. Eine Studie von IDC hat für 2008 prognostiziert, dass der weltweit verfügbare Speicherplatz Bits beträgt. Es ist also nicht möglich einen solchen Spielbaum zu speichern.