Praktische Grenzen der Berechenbarkeit: Unterschied zwischen den Versionen

Aus DMUW-Wiki
Wechseln zu: Navigation, Suche
(→‎Lineare Suche)
(→‎Lineare Suche)
Zeile 37: Zeile 37:
 
* Rechenoperationen 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 <math>3+(n-1)\cdot 7 = 7\cdot n - 4</math> elementare Rechenoperationen
+
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 <math>3+(n-1)\cdot 7 = 7\cdot n - 4</math> 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 <math>3+4\cdot(n-1)= 4\cdot n - 1</math> Rechenschritte.
 
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 <math>3+4\cdot(n-1)= 4\cdot n - 1</math> Rechenschritte.
 +
 +
Mit <math>T(n)</math> wird die Anzahl der elementaren Rechenoperationen in Abhängigkeit von der Länge des Arrays bezeichnet.
 +
 +
Zusammenfassend erhalten wir:
 +
* <math>T_{best}(n)= 6</math>
 +
* <math>T_{averade}(n)=4\cdot n - 1</math>
 +
* <math>T_{worst}(n)= 7\cdot n - 4</math>
  
 
== Türme von Hanoi ==
 
== Türme von Hanoi ==

Version vom 19. September 2009, 10:12 Uhr

Inhaltsverzeichnis

Zuordnungsquiz

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

Was bin ich? Exponentialfunktion a \cdot e^x
Was bin ich? a \cdot x Lineare Funktion
Was bin ich? Potenzfunktion a \cdot x^b




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_{averade}(n)=4\cdot n - 1
  • T_{worst}(n)= 7\cdot n - 4

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.

Häufglöckner Hanoi3.gif

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?

Häufglöckner Hanoi4.gif
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?

\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?

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.

Von „http://dmuw.zum.de/index.php?title=Lernpfade/Berechenbarkeit/Praktische_Grenzen_der_Berechenbarkeit&oldid=5725“