Praktische Grenzen der Berechenbarkeit: Unterschied zwischen den Versionen

Aus DMUW-Wiki
Wechseln zu: Navigation, Suche
K (→‎Lineare Suche)
(kat Lernpfad Berechenbarkeit)
 
(66 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
−
== Motivation ==
+
{{Lernpfad-M|<big>'''Praktische Grenzen der Berechenbarkeit'''</big>
−
 
+
__NOTOC__
−
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.
+
''Teil 2 der Lernpfadgruppe: Grenzen der Berechenbarkeit.''
−
 
+
−
Ein Algorithmus heißt '''effizient''', wenn er ein Problem mit möglichst geringem Ressourcenverbrauch (Zeit oder Speicher) löst.
+
  
 +
*'''Zeitbedarf: ca. 6 Unterrichtsstunden'''
 +
*'''Material: Laufzettel'''
 +
*'''Behandelte Themen: '''Wachstum von Funktionen, Suchverfahren, <math>\mathcal{O}</math>-Notation, Sortierverfahren, Türme von Hanoi, exponentielles Wachstum.'''
 +
}}
 
== Funktionsgraphen ==
 
== Funktionsgraphen ==
 +
{{Aufgabe-Mathe|
 +
Wie gut kennst du noch die Funktionsgraphen und Funktionsnamen?
 +
 +
Ordne den Funktionsgraphen die zugehörigen Funktionsnamen '''und''' Funktionsterme zu!
 +
}}
  
 
<div class="zuordnungs-quiz">
 
<div class="zuordnungs-quiz">
−
Wie gut kennst du noch die Funktionsgraphen und Funktionsnamen?
 
−
Ordne den Funktionsgraphen die zugehörigen Funktionsnamen und Funktionsterme zu!
 
 
{|  
 
{|  
 
| [[Bild:Häufglöckner_Graph2.jpg|Was bin ich?|150px]] ||  Exponentialfunktion || <math>f(x)=e^x</math>
 
| [[Bild:Häufglöckner_Graph2.jpg|Was bin ich?|150px]] ||  Exponentialfunktion || <math>f(x)=e^x</math>
Zeile 19: Zeile 24:
 
</div>
 
</div>
  
−
<br />
+
== Wachstum von Funktionen ==
−
<br />
+
{{Aufgabe-Mathe|
 +
Gegeben sind die untenstehenden Funktionen. Ab welchem ganzzahligen <math>x</math> ist die Exponentialfunktion <math>f(x)</math> größer als die Funktionen <math>g,\,h,\,i</math>?
 +
* <math>f\left(x\right)=2^x</math>  
 +
* <math>g\left(x\right)=x^2</math>
 +
* <math>h(x) = x \cdot \log_2 (x)</math>
 +
* <math>i(x) = 2\cdot x</math>
 +
'''Stelle zur Bestimmung eine Wertetabelle auf oder löse die Aufgabe graphisch, notiere deine Ergebnisse auf dem Laufzettel und überprüfe anschließend dein Ergebnis durch Ausfüllen des Lückentextes.'''
 +
 
 +
<quiz display="simple">
 +
{
 +
| type="{}" }
 +
 
 +
Die Funktion <math>f(x)=2^x</math> ist für <math>x\geq</math> { 5 } größer als <math>g\left(x\right)=x^2</math>.
 +
 
 +
{
 +
|type="{}" }
 +
Die Funktion <math>f(x)=2^x</math> ist für <math>x\geq</math> { 2 } größer als <math>h(x) = x \cdot \log_2 (x)</math>.
 +
 
 +
{
 +
|type="{}" }
 +
Die Funktion <math>f(x)=2^x</math> ist für <math>x\geq</math> { 2 } größer als  <math>i(x) = 2\cdot x</math>.
 +
</quiz>
 +
}}
 +
 
 +
<!--
 +
{| {{Prettytable}}
 +
|- style="background-color:#8DB6CD"
 +
! x !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9
 +
|-
 +
| <math>f(x)=2^x</math> || '''2''' || '''4''' || '''8''' || '''16''' || '''32''' || '''64''' || '''128''' || '''256'''  || '''512'''
 +
|-
 +
| <math>g(x)=x^2</math> || '''1''' || '''4''' || '''9''' || '''16''' || '''25''' || '''36''' || '''49''' || '''64''' || '''81'''
 +
|-
 +
| <math>h(x)=x\cdot \log_2(x)</math> || '''0''' || '''2''' || '''4,75''' || '''8''' || '''11,61''' || '''15,51''' || '''19,65''' || '''24''' || '''28,53'''
 +
|-
 +
| <math>i(x)=2\cdot x</math> || '''2''' || '''4''' || '''6''' || '''8''' || '''10''' || '''12''' || '''14''' || '''16''' || '''18'''
 +
|}
 +
-->
 +
 
 +
{{Lösung versteckt|
 +
Die Tabelle sieht dann folgendermaßen aus:
 +
<center>
 +
[[Bild:Haeufgloeckner_WertetabelleFunktionen.png]]
 +
</center>
 +
Die zugehörigen Graphen sind in diesem Bild dargestellt:
 +
<center>
 +
[[Bild:Haeufgloeckner_Funktionsgraphen.gif]]
 +
</center>
 +
}}
  
 
== Lineare Suche ==
 
== Lineare Suche ==
Zeile 39: Zeile 92:
 
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.
 
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.
  
−
{{Merke|Zur Analyse der Laufzeit des Algorithmus zählt man die elementaren Rechenoperationen. Hierzu zählen:
+
'''Notiere den Merksatz auf deinem Laufzettel.'''
 +
{{Merke|Zur Analyse der Laufzeit eines Algorithmus zählt man die elementaren Rechenoperationen. Hierzu zählen:
 
* Vergleiche wie "<", ">", "&#61;", "and", "not",...
 
* Vergleiche wie "<", ">", "&#61;", "and", "not",...
 
* Wertzuweisungen wie ":&#61;"  
 
* Wertzuweisungen wie ":&#61;"  
Zeile 47: Zeile 101:
 
}}
 
}}
  
−
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.  
+
Die Zahl der benötigten Rechenoperationen hängt offensichtlich von der Größe des Arrays ab und davon, 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 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 "wiederhole-solange"-Schleife (auch 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.
 
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.
Zeile 56: Zeile 110:
 
Mit <math>T(n)</math> wird die Anzahl der elementaren Rechenoperationen in Abhängigkeit von der Länge des Arrays bezeichnet.
 
Mit <math>T(n)</math> wird die Anzahl der elementaren Rechenoperationen in Abhängigkeit von der Länge des Arrays bezeichnet.
 
Zusammenfassend erhalten wir:
 
Zusammenfassend erhalten wir:
−
* <math>T_{best}(n)= 6</math>
+
* <math>T_{best}\left(n\right)= 6</math>
−
* <math>T_{average}(n)=4\cdot n - 1</math>
+
* <math>T_{average}\left(n\right)=4\cdot n - 1</math>
−
* <math>T_{worst}(n)= 7\cdot n - 4</math>
+
* <math>T_{worst}\left(n\right)= 7\cdot n - 4</math>
  
−
== <math>\mathcal{O}</math>-Notation ==
+
'''Notiere auf deinem Laufzettel, welche Fälle man bei der Laufzeitanalyse untersucht.'''
 +
 
 +
== O-Notation ==
 +
 
 +
Im vorangegangenen Abschnitt haben wir uns mit der Anzahl der Rechenoperationen in Abhängigkeit von der Eingabegröße beschäftigt. Um die unterschiedlichen Algorithmen unterschiedlichen "Schwierigkeitsklassen" zuordnen zu können, wird die sogenannte '''<math>\mathcal{O}</math>-Notation eingeführt.
 +
 
 +
'''Notiere die Definition auf deinem Laufzettel.'''
 +
{{Definition|
 +
Sind <math>f</math> und <math>g</math> zwei Funktionen. Dann ist <math>f</math> von Ordnung <math>g</math>, wenn es eine Konstante <math>C>0</math> gibt, so dass <math> f(n)\leq C\cdot g(n)</math> für alle <math>n\in\mathbb{N}</math> ab einer gewissen Größe.
 +
 
 +
Mit <math>\mathcal{O}(g)</math> bezeichnet man alle Funktionen der Ordnung <math>g</math>
 +
}}
 +
 
 +
Die wichtigsten Ordnungsklassen sind:
 +
 
 +
* konstante Ordnung <math>\mathcal{O}(1)</math>
 +
* logarithmische Ordnung <math>\mathcal{O}(\log n)</math>
 +
* lineare Ordnung <math>\mathcal{O}(n)</math>
 +
* n-log-n Ordnung <math>\mathcal{O}(n\cdot \log n)</math>
 +
* quadratische Ordnung <math>\mathcal{O}(n^2)</math>
 +
* polynomielle Ordnung <math>\mathcal{O}(n^k)</math> mit <math>k\in\mathbb{N}</math> fest
 +
* exponentielle Ordnung <math>\mathcal{O}(d^n)</math> mit <math>d>1</math>
 +
 
 +
Je weiter man die Liste nach unten geht, um so schwieriger ist die Funktion zu berechnen.
 +
 
 +
'''Notiere die Ordnungsklassen auf deinem Laufzettel.'''
  
 
== Bubble Sort ==
 
== Bubble Sort ==
  
 
Sortierverfahren spielen in der Praxis eine wichtige Rolle. Bubble-Sort ist eines der einfacheren Sortierverfahren. Der Name kommt daher, dass große Elemente wie Luftblasen nach oben steigen. In diesem Video kann man die Funktionsweise anschaulich sehen.
 
Sortierverfahren spielen in der Praxis eine wichtige Rolle. Bubble-Sort ist eines der einfacheren Sortierverfahren. Der Name kommt daher, dass große Elemente wie Luftblasen nach oben steigen. In diesem Video kann man die Funktionsweise anschaulich sehen.
−
 
+
<center>
 
:{{#ev:youtube|MtcrEhrt_K0|300}}
 
:{{#ev:youtube|MtcrEhrt_K0|300}}
 +
</center>
  
 
  Algorithmus BubbleSort
 
  Algorithmus BubbleSort
Zeile 85: Zeile 165:
  
 
Zur Laufzeit:
 
Zur Laufzeit:
−
Im schlechtesten Fall ist das Array absteigende sortiert. Dann steigt das erste Element von Feld 1 zu Feld n auf. Das zweite Element steigt dann von Feld 1 bis Feld n-1 auf und so weiter bis das Array aufsteigend sortiert ist. Es werden dann also für das erste Element n-1 Vertauschungen , für das zweite Element n-2 Vertauschungen, für das dritte Element n-3 Vertauschunge usw. durchgeführt. Beim letzten Element muss dann keine Vertauschung mehr durchgeführt werden. Insgesamt sind das dann <math>\frac{n\cdot (n-1)}{2}</math> Vertauschungen. BubbleSort hat dann eine Laufzeit von <math>\mathcal{O}(n^2)</math>.
+
Im schlechtesten Fall ist das Array absteigend sortiert. Dann steigt das erste Element von Feld 1 zu Feld n auf. Das zweite Element steigt dann von Feld 1 bis Feld n-1 auf und so weiter bis das Array aufsteigend sortiert ist. Es werden dann also für das erste Element n-1 Vertauschungen , für das zweite Element n-2 Vertauschungen, für das dritte Element n-3 Vertauschunge usw. durchgeführt. Beim letzten Element muss dann keine Vertauschung mehr durchgeführt werden. Insgesamt sind das dann <math>\frac{n\cdot (n-1)}{2}</math> Vertauschungen. Bubble Sort hat dann eine Laufzeit von <math>\mathcal{O}(n^2)</math>.
  
−
Im besten Fall ist das Array bereits aufsteigend sortiert. Dann wird das Array genau einmal durchlaufen und dabei feststellen, dass das Array bereits sortiert ist. BubbleSort hat dann eine Laufzeit von <math>\mathcal{O}(n)</math>.
+
Im besten Fall ist das Array bereits aufsteigend sortiert. Dann wird das Array für jedes Element genau einmal durchlaufen und der Algorithmus wird dabei feststellen, dass das Array bereits sortiert ist. Die Bedingung A[i]>A[i+1] ist also immer wahr. Dadurch müssen keine Vertauschungen von Elementen durchgeführt werden. Bubble Sort hat dann eine Laufzeit von <math>\mathcal{O}(n)</math>, da jedes Element einmal betrachtet werden muss.
  
−
Unter diesem [http://siebn.de/anisort/anisort Link] werden die Sortierverfahren BubbleSort, Quicksort, Heapsort, InsertionSort, Mergesort und SelectionSort visualisiert.
+
Unter diesem [http://siebn.de/anisort/anisort Link] werden die Sortierverfahren Bubble Sort, Quick Sort, Heap Sort, Insertion Sort, Merge Sort und Selection Sort visualisiert.
  
 
Alle diese Sortierverfahren haben eine worst-case-Laufzeit zwischen <math>\mathcal{O}(n\cdot\log(n))</math> und <math>\mathcal{O}(n^2)</math>.
 
Alle diese Sortierverfahren haben eine worst-case-Laufzeit zwischen <math>\mathcal{O}(n\cdot\log(n))</math> und <math>\mathcal{O}(n^2)</math>.
 +
 +
{{Aufgabe-Mathe|
 +
Beantworte die Multiple-Choice Fragen!
 +
 +
'''Notiere deine Antwort auf dem Laufzettel bevor du auf "Korrektur" klickst.'''
 +
 +
<quiz display="simple">
 +
{Welche Ordnung hat das Programm "methode1"?
 +
 +
//Programm methode1
 +
public static int methode1 (int n) {
 +
  int i,j,k;
 +
  int a = 0;
 +
  int b = 1;
 +
  for (i = 0; i < n; i++) {
 +
    for (j = 0; j < n; j++){
 +
      for (k = 0; k < n; k++){
 +
        a = a + b;
 +
      &#125;
 +
    &#125;
 +
  return a;
 +
&#125;
 +
}
 +
+ <math>\mathcal{O}(n)</math>
 +
- <math>\mathcal{O}(n^2)</math>
 +
- <math>\mathcal{O}(n^3)</math>
 +
 +
{Welche Ordnung hat das Programm "methode2"?
 +
 +
// Programm methode2
 +
public static int methode2 (int n) {
 +
  int i,j,x,y;
 +
  x = 0; y = 0;
 +
  for (i = 1; i < n; i++) {
 +
    for (k = i; k < n; k++) {
 +
      x = x + 1;
 +
    &#125;
 +
    for (k = 1; k < i; k++) {
 +
      y = y + 1;
 +
    &#125;
 +
  &#125;
 +
  return x+y;
 +
&#125;
 +
}
 +
 +
- <math>\mathcal{O}(n)</math>
 +
+  <math>\mathcal{O}(n^2)</math>
 +
-  <math>\mathcal{O}(n^3)</math>
 +
 +
</quiz>
 +
}}
  
 
== Türme von Hanoi ==
 
== 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.
+
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, den 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.
  
 +
{{Aufgabe-Mathe|
 
<quiz display="simple">
 
<quiz display="simple">
 
{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.<br />
 
{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.<br />
−
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.<br />
+
Im Falle von zwei Scheiben ist es 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 drei Züge.<br />
  
 
In dieser Animation siehst du die Lösung für den Fall, dass man mit 3 Scheiben spielt.
 
In dieser Animation siehst du die Lösung für den Fall, dass man mit 3 Scheiben spielt.
Zeile 118: Zeile 250:
 
+ exponentiell
 
+ exponentiell
 
</quiz>
 
</quiz>
 +
'''Beantworte die Fragen auf dem Laufzettel.'''
 +
}}
  
 
'''Zusatzinformation:''' {{versteckt|
 
'''Zusatzinformation:''' {{versteckt|
−
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 <math>1,8\cdot 10^{19}</math> 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.
+
Eine optimale Zugfolge benötigt bei <math>n</math> Scheiben <math>2^n-1</math> Züge.
 +
 
 +
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 nach der obigen Formel mehr als <math>1,8\cdot 10^{19}</math> 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. Selbst wenn man die Geschwindigkeit, mit der man die Scheiben bewegt, um einen konstanten Faktor erhöht, kann man wieder ein anderes <math>n</math> finden, so dass man das Problem nicht mehr in akzeptabler Zeit lösen kann.
 
}}
 
}}
  
−
== Wachstum von Funktionen ==
 
  
−
Gegeben sind die untenstehenden Funktionen. Ab welchem ganzzahligen <math>x</math> ist das exponentielle Wachstum von <math>f(x)</math> schlechter als das polynomielle der Funktionen <math>g,\,h,\,i</math>?
 
−
* <math>f(x)=2^x</math>
 
−
* <math>g(x)=x^2</math>
 
−
* <math>h(x) = x \cdot \log_2 (x)</math>
 
−
* <math>i(x) = 2\cdot x</math>
 
−
(Hinweis: Stelle zur Bestimmung eine Wertetabelle auf oder löse die Aufgabe graphisch!)
 
−
 
−
<div class="lueckentext-quiz">
 
−
 
−
{| {{Prettytable}}
 
−
|- style="background-color:#8DB6CD"
 
−
! x !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9
 
−
|-
 
−
| <math>f(x)=2^x</math> || '''2''' || '''4''' || '''8''' || '''16''' || '''32''' || '''64''' || '''128''' || '''256'''  || '''512'''
 
−
|-
 
−
| <math>g(x)=x^2</math> || '''1''' || '''4''' || '''9''' || '''16''' || '''25''' || '''36''' || '''49''' || '''64''' || '''81'''
 
−
|-
 
−
| <math>h(x)=x\cdot \log_2(x)</math> || '''0''' || '''2''' || '''4,75''' || '''8''' || '''11,61''' || '''15,51''' || '''19,65''' || '''24''' || '''28,53'''
 
−
|-
 
−
| <math>i(x)=2\cdot x</math> || '''2''' || '''4''' || '''6''' || '''8''' || '''10''' || '''12''' || '''14''' || '''16''' || '''18'''
 
−
|}
 
−
</div>
 
−
 
−
 
−
'''Tabelle als Lückentext zum Ausfüllen'''
 
−
 
−
{{Lösung versteckt|
 
−
<math>\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}</math>
 
−
 
−
[[Bild:Haeufgloeckner_Funktionsgraphen.gif]]
 
−
 
−
Also ist <math>f(x)</math> schlechter als  <math>g(x)</math> für <math>x>4</math>,
 
−
<math>f(x)</math> schlechter als  <math>h(x)</math> für <math>x>2</math>,
 
−
<math>f(x)</math> schlechter als  <math>i(x)</math> für <math>x>2</math>.
 
−
 
−
}}
 
  
 
== Reiskörner auf einem Schachbrett ==
 
== Reiskörner auf einem Schachbrett ==
  
−
Im alten Persien gab es einen klugen Hofdiener, der seinem König ein Schachbrett schenkte. Als Dank dafür durfte sich der Hofdiener etwas wünschen. Er sagte: "Ich wünsche mit nichts weiter, als dass das Schachbrett mit Reis gefüllt wird und zwar so, dass auf dem ersten Feld ein Reiskorn liegt, auf jedes weitere die doppelte Anzahl an Reiskörnern., also 1 Korn auf dem ersten Feld, 2 Körner auf dem zweiten, 4 Körner auf dem dritten, 8 Körner auf dem vierten und so weiter."
+
Im alten Persien gab es einen klugen Hofdiener, der seinem König ein Schachbrett schenkte. Als Dank dafür durfte sich der Hofdiener etwas wünschen. Er sagte: "Ich wünsche mit nichts weiter, als dass das Schachbrett mit Reis gefüllt wird und zwar so, dass auf dem ersten Feld ein Reiskorn liegt, auf jedem weiteren die doppelte Anzahl an Reiskörnern des vorherigen Feldes, also 1 Korn auf dem ersten Feld, 2 Körner auf dem zweiten, 4 Körner auf dem dritten, 8 Körner auf dem vierten und so weiter."
  
−
Der König war überrascht und sagte: "Es ehrt dich, dass du einen so bescheidenen Wunsch hast. Er soll die auf der Stelle erfüllt werden."
+
Der König war überrascht und sagte: "Es ehrt dich, dass du einen so bescheidenen Wunsch hast. Er soll dir auf der Stelle erfüllt werden."
  
 
Der Hofdiener lächelte und verneigte sich tief vor seinem König.
 
Der Hofdiener lächelte und verneigte sich tief vor seinem König.
  
 +
{{Aufgabe-Mathe|
 
Warum lächelte der Hofdiener, nachdem ihm der Wunsch gewährt worden war?
 
Warum lächelte der Hofdiener, nachdem ihm der Wunsch gewährt worden war?
 +
 +
'''Beantworte diese Frage auf deinen Laufzettel.'''
  
 
{{versteckt|
 
{{versteckt|
 
Der Hofdiener war von nun an der reichste Mann im ganzen Land. Denn summiert man die Anzahl der Reiskörner auf (allein auf dem n-ten Feld sind <math>2^{n-1}</math> Reiskörner zu finden), erhält man die gigantische Zahl 18.446.744.073.709.552.000 (18,4 Trillionen) Reiskörner. Geht man davon aus, dass ein Reiskorn im Durchschnitt 0,03g wiegt, ergibt sich eine Masse von 553.402.322.000 Tonnen, was in etwa der heutige Weltjahresproduktion an Reis entspricht.
 
Der Hofdiener war von nun an der reichste Mann im ganzen Land. Denn summiert man die Anzahl der Reiskörner auf (allein auf dem n-ten Feld sind <math>2^{n-1}</math> Reiskörner zu finden), erhält man die gigantische Zahl 18.446.744.073.709.552.000 (18,4 Trillionen) Reiskörner. Geht man davon aus, dass ein Reiskorn im Durchschnitt 0,03g wiegt, ergibt sich eine Masse von 553.402.322.000 Tonnen, was in etwa der heutige Weltjahresproduktion an Reis entspricht.
 +
}}
 
}}
 
}}
  
Zeile 187: Zeile 284:
 
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:
 
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?  
+
{{Aufgabe-Mathe|
−
* Kann man diesen Spielbaum auf einer handelsüblichen Festplatte speichern, wenn pro Knoten des Spielbaums 1 Byte Speicherplatz benötigt wird?
+
* 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? '''Notiere die Antwort auf deinem Laufzettel.'''
 +
* Kann man diesen Spielbaum auf einer handelsüblichen Festplatte speichern, wenn pro Knoten des Spielbaums 1 Byte Speicherplatz benötigt wird? '''Begründe deine Antwort auf deinem Laufzettel.'''
 +
(Hinweis: In der ersten Ebene des Spielbaums ist 1 Knoten, in der zweiten Ebene sind es 5 Knoten, in der dritten sind es 25 Knoten,...)
  
 
[[Bild:Häufglöckner_Spielbaum.png|400px]]
 
[[Bild:Häufglöckner_Spielbaum.png|400px]]
  
 
{{Lösung versteckt|
 
{{Lösung versteckt|
−
Für die Speicherung eines  solchen Spielbaumes würde man ungefähr <math>8\cdot 10^{35}</math> GB benötigen. Eine [http://www.emc.com/collateral/analyst-reports/diverse-exploding-digital-universe.pdf Studie von IDC] hat für 2007 prognostiziert, dass der weltweit verfügbare Speicherplatz <math>2,8\cdot 10^{11}</math> GB beträgt. Es ist also nicht möglich einen solchen Spielbaum zu speichern.
+
Ein solchen Schachspielbaum hat in der ersten Ebene <math>5^0=1</math> Knoten, in der zweiten Ebene <math>5^1=5</math> Knoten, in der dritten Ebene <math>5^2=25</math> Knoten,..., in der sechzigsten Ebene <math>5^{59}\approx 1,73\cdot 10^{41}</math> Knoten. Summiert man diese noch alle auf, erhält man ca. <math>2,17\cdot 10^{41}</math> Knoten.
−
}}
+
  
 +
Für die Speicherung eines  solchen Spielbaumes würde man ungefähr <math>2,02\cdot 10^{32}</math> GB benötigen. Eine [http://www.emc.com/collateral/analyst-reports/diverse-exploding-digital-universe.pdf Studie von IDC] hat für 2007 prognostiziert, dass der weltweit verfügbare Speicherplatz <math>2,8\cdot 10^{11}</math> GB beträgt. Es ist also nicht möglich einen solchen Spielbaum zu speichern, selbst wenn man doppelt oder viermal so viel Speicherplatz zur Verfügung hätte.
 +
}}
 +
}}
  
  
−
== Travelling Salesman Problem ==
+
[[Kategorie:Lernpfad Berechenbarkeit]]

Aktuelle Version vom 5. Dezember 2011, 00:48 Uhr

Mathematik-digital Pfeil-3d.png
Lernpfad

Praktische Grenzen der Berechenbarkeit

Teil 2 der Lernpfadgruppe: Grenzen der Berechenbarkeit.

  • Zeitbedarf: ca. 6 Unterrichtsstunden
  • Material: Laufzettel
  • Behandelte Themen: Wachstum von Funktionen, Suchverfahren, \mathcal{O}-Notation, Sortierverfahren, Türme von Hanoi, exponentielles Wachstum.

Funktionsgraphen

  Aufgabe   Stift.gif

Wie gut kennst du noch die Funktionsgraphen und Funktionsnamen?

Ordne den Funktionsgraphen die zugehörigen Funktionsnamen und Funktionsterme zu!

Was bin ich? Exponentialfunktion f(x)=e^x
Was bin ich? f(x)=x Lineare Funktion
Was bin ich? Potenzfunktion f(x)=x^2

Wachstum von Funktionen

  Aufgabe   Stift.gif

Gegeben sind die untenstehenden Funktionen. Ab welchem ganzzahligen x ist die Exponentialfunktion f(x) größer als die Funktionen g,\,h,\,i?

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

Stelle zur Bestimmung eine Wertetabelle auf oder löse die Aufgabe graphisch, notiere deine Ergebnisse auf dem Laufzettel und überprüfe anschließend dein Ergebnis durch Ausfüllen des Lückentextes.

1.

Die Funktion f(x)=2^x ist für x\geq größer als g\left(x\right)=x^2.

2.

Die Funktion f(x)=2^x ist für x\geq größer als h(x) = x \cdot \log_2 (x).

3.

Die Funktion f(x)=2^x ist für x\geq größer als i(x) = 2\cdot x.

Punkte: 0 / 0



Die Tabelle sieht dann folgendermaßen aus:

Haeufgloeckner WertetabelleFunktionen.png

Die zugehörigen Graphen sind in diesem Bild dargestellt:

Haeufgloeckner Funktionsgraphen.gif


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
  gefunden := (a[j] = x)
  wiederhole
    j := j + 1
    gefunden := (a[j] = x)
  solange j =< n
  return gefunden

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.

Notiere den Merksatz auf deinem Laufzettel.

Nuvola apps kig.png   Merke

Zur Analyse der Laufzeit eines 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 Arrays ab und davon, 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 "wiederhole-solange"-Schleife (auch 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}\left(n\right)= 6
  • T_{average}\left(n\right)=4\cdot n - 1
  • T_{worst}\left(n\right)= 7\cdot n - 4

Notiere auf deinem Laufzettel, welche Fälle man bei der Laufzeitanalyse untersucht.

O-Notation

Im vorangegangenen Abschnitt haben wir uns mit der Anzahl der Rechenoperationen in Abhängigkeit von der Eingabegröße beschäftigt. Um die unterschiedlichen Algorithmen unterschiedlichen "Schwierigkeitsklassen" zuordnen zu können, wird die sogenannte \mathcal{O}-Notation eingeführt.

Notiere die Definition auf deinem Laufzettel.

Definition

Sind f und g zwei Funktionen. Dann ist f von Ordnung g, wenn es eine Konstante C>0 gibt, so dass f(n)\leq C\cdot g(n) für alle n\in\mathbb{N} ab einer gewissen Größe.

Mit \mathcal{O}(g) bezeichnet man alle Funktionen der Ordnung g


Die wichtigsten Ordnungsklassen sind:

  • konstante Ordnung \mathcal{O}(1)
  • logarithmische Ordnung \mathcal{O}(\log n)
  • lineare Ordnung \mathcal{O}(n)
  • n-log-n Ordnung \mathcal{O}(n\cdot \log n)
  • quadratische Ordnung \mathcal{O}(n^2)
  • polynomielle Ordnung \mathcal{O}(n^k) mit k\in\mathbb{N} fest
  • exponentielle Ordnung \mathcal{O}(d^n) mit d>1

Je weiter man die Liste nach unten geht, um so schwieriger ist die Funktion zu berechnen.

Notiere die Ordnungsklassen auf deinem Laufzettel.

Bubble Sort

Sortierverfahren spielen in der Praxis eine wichtige Rolle. Bubble-Sort ist eines der einfacheren Sortierverfahren. Der Name kommt daher, dass große Elemente wie Luftblasen nach oben steigen. In diesem Video kann man die Funktionsweise anschaulich sehen. 

Algorithmus BubbleSort
Eingabe: ein Array der Länge n
Ausgabe: ein aufsteigend sortiertes Array
 wiederhole
   vertauscht := falsch
   für jedes i von 1 bis n - 1 wiederhole 
     falls A[ i ] > A[ i + 1 ] dann
       vertausche( A[ i ], A[ i + 1 ] )
       vertauscht := wahr
     ende falls
   ende für
   n := n - 1
 solange vertauscht und n >= 1

Die äußerste Schleife durchläuft die zu sortierenden Daten, bis keine Vertauschungen mehr nötig sind. In dieser Schleife wird das Feld jeweils einmal durchlaufen und es werden zwei benachbarte Daten vertauscht, wenn sie in falscher Reihenfolge stehen.

Zur Laufzeit: Im schlechtesten Fall ist das Array absteigend sortiert. Dann steigt das erste Element von Feld 1 zu Feld n auf. Das zweite Element steigt dann von Feld 1 bis Feld n-1 auf und so weiter bis das Array aufsteigend sortiert ist. Es werden dann also für das erste Element n-1 Vertauschungen , für das zweite Element n-2 Vertauschungen, für das dritte Element n-3 Vertauschunge usw. durchgeführt. Beim letzten Element muss dann keine Vertauschung mehr durchgeführt werden. Insgesamt sind das dann \frac{n\cdot (n-1)}{2} Vertauschungen. Bubble Sort hat dann eine Laufzeit von \mathcal{O}(n^2).

Im besten Fall ist das Array bereits aufsteigend sortiert. Dann wird das Array für jedes Element genau einmal durchlaufen und der Algorithmus wird dabei feststellen, dass das Array bereits sortiert ist. Die Bedingung A[i]>A[i+1] ist also immer wahr. Dadurch müssen keine Vertauschungen von Elementen durchgeführt werden. Bubble Sort hat dann eine Laufzeit von \mathcal{O}(n), da jedes Element einmal betrachtet werden muss.

Unter diesem Link werden die Sortierverfahren Bubble Sort, Quick Sort, Heap Sort, Insertion Sort, Merge Sort und Selection Sort visualisiert.

Alle diese Sortierverfahren haben eine worst-case-Laufzeit zwischen \mathcal{O}(n\cdot\log(n)) und \mathcal{O}(n^2).

  Aufgabe   Stift.gif

Beantworte die Multiple-Choice Fragen!

Notiere deine Antwort auf dem Laufzettel bevor du auf "Korrektur" klickst.

1. Welche Ordnung hat das Programm "methode1"? 

//Programm methode1
public static int methode1 (int n) {
  int i,j,k;
  int a = 0;
  int b = 1;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++){
      for (k = 0; k < n; k++){
        a = a + b;
      }
    }
  return a;
}
\mathcal{O}(n)
\mathcal{O}(n^2)
\mathcal{O}(n^3)

2. Welche Ordnung hat das Programm "methode2"? 

// Programm methode2
public static int methode2 (int n) {
  int i,j,x,y;
  x = 0; y = 0;
  for (i = 1; i < n; i++) {
    for (k = i; k < n; k++) {
      x = x + 1;
    }
    for (k = 1; k < i; k++) {
      y = y + 1;
    }
 }
  return x+y;
}
\mathcal{O}(n)
\mathcal{O}(n^2)
\mathcal{O}(n^3)

Punkte: 0 / 0


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, den 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.

  Aufgabe   Stift.gif

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 es 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 drei 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

Beantworte die Fragen auf dem Laufzettel.

Zusatzinformation:

Eine optimale Zugfolge benötigt bei n Scheiben 2^n-1 Züge.

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 nach der obigen Formel 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. Selbst wenn man die Geschwindigkeit, mit der man die Scheiben bewegt, um einen konstanten Faktor erhöht, kann man wieder ein anderes n finden, so dass man das Problem nicht mehr in akzeptabler Zeit lösen kann.


Reiskörner auf einem Schachbrett

Im alten Persien gab es einen klugen Hofdiener, der seinem König ein Schachbrett schenkte. Als Dank dafür durfte sich der Hofdiener etwas wünschen. Er sagte: "Ich wünsche mit nichts weiter, als dass das Schachbrett mit Reis gefüllt wird und zwar so, dass auf dem ersten Feld ein Reiskorn liegt, auf jedem weiteren die doppelte Anzahl an Reiskörnern des vorherigen Feldes, also 1 Korn auf dem ersten Feld, 2 Körner auf dem zweiten, 4 Körner auf dem dritten, 8 Körner auf dem vierten und so weiter."

Der König war überrascht und sagte: "Es ehrt dich, dass du einen so bescheidenen Wunsch hast. Er soll dir auf der Stelle erfüllt werden."

Der Hofdiener lächelte und verneigte sich tief vor seinem König.

  Aufgabe   Stift.gif

Warum lächelte der Hofdiener, nachdem ihm der Wunsch gewährt worden war?

Beantworte diese Frage auf deinen Laufzettel.

Der Hofdiener war von nun an der reichste Mann im ganzen Land. Denn summiert man die Anzahl der Reiskörner auf (allein auf dem n-ten Feld sind 2^{n-1} Reiskörner zu finden), erhält man die gigantische Zahl 18.446.744.073.709.552.000 (18,4 Trillionen) Reiskörner. Geht man davon aus, dass ein Reiskorn im Durchschnitt 0,03g wiegt, ergibt sich eine Masse von 553.402.322.000 Tonnen, was in etwa der heutige Weltjahresproduktion an Reis entspricht.

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:

  Aufgabe   Stift.gif
  • 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? Notiere die Antwort auf deinem Laufzettel.
  • Kann man diesen Spielbaum auf einer handelsüblichen Festplatte speichern, wenn pro Knoten des Spielbaums 1 Byte Speicherplatz benötigt wird? Begründe deine Antwort auf deinem Laufzettel.

(Hinweis: In der ersten Ebene des Spielbaums ist 1 Knoten, in der zweiten Ebene sind es 5 Knoten, in der dritten sind es 25 Knoten,...)

Häufglöckner Spielbaum.png

Ein solchen Schachspielbaum hat in der ersten Ebene 5^0=1 Knoten, in der zweiten Ebene 5^1=5 Knoten, in der dritten Ebene 5^2=25 Knoten,..., in der sechzigsten Ebene 5^{59}\approx 1,73\cdot 10^{41} Knoten. Summiert man diese noch alle auf, erhält man ca. 2,17\cdot 10^{41} Knoten.

Für die Speicherung eines solchen Spielbaumes würde man ungefähr 2,02\cdot 10^{32} 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, selbst wenn man doppelt oder viermal so viel Speicherplatz zur Verfügung hätte.


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