Das Programm/Spiel "Akinator" funktioniert ähnlich wie ein simples Zahlenratespiel. Beispiel:
Spielleiter: Denke Dir eine Zahl zwischen 1 und 8! (also 1,2,3,4,5,6,7 oder 8)
Teilnehmer: OK! (T denkt sich in diesem Beispiel die Zahl 6)
Spielleiter: Ist die Zahl kleiner als 5?
Teilnehmer: Nein! (S weiß nun, dass nur noch 5,6,7,8 in Frage kommt)
Spielleiter: Ist die Zahl kleiner als 7?
Teilnehmer: Ja! (S weiß, dass nur noch 5,6 in Frage kommt)
Spielleiter: Ist die Zahl kleiner als 6?
Teilnehmer: Nein!
Spielleiter: Dann ist die gedachte Zahl die 6!
Wenn der Spielleiter aus 8 möglichen Zahlen die richtige erraten muss, so sind 3 Fragen erforderlich, um sicher das Ergebnis zu erraten. Bei 16 möglichen Zahlen sind 4 Fragen erforderlich.
Wertetabelle dazu:
Anzahl möglicher Zahlen: 8 16 32
Anzahl nötiger Fragen: 3 4 5
Dieser Wertetabelle liegt folgende Gesetzmäßigkeit zugrunde: Um von der Anzahl nötiger auf die Anzahl möglicher Zahlen zu schließen, rechnet man: Z(x) = 2x
Beispiel: Z(5) = 25 = 32
Um andersherum von der Anzahl möglicher Zahlen auf die Anzahl der nötigen Fragen zu schließen, benötigt man die Umkehrfunktion, also den Logarithmus zur Basis 2:
F(x) = log2(x)
Beispiel: F(32) = log2(32) = 5
Damit ergeben sich überraschende Ergebnisse: Ein Zahlenratespiel mit 1Mio möglichen Zahlen liefert das Ergebnis F(1Mio) = log2(1Mio) = ca. 19.93 = ca. 20. Man benötigt also nur 20 Fragen!
Wozu ist das wichtig?
Wenn man Daten sortiert vorliegen hat, wie z.B. alphabetisch sortierte Wörter in einem Deutsch-Englisch Wörterbuch, so kann man effizient darin suchen. Wenn man z.B. das Wort "Putzlappen" im Wörterbuch sucht, so kann man das Wörterbuch irgendwo in der Mitte aufschlagen, das dort zuerst vorkommende Wort prüfen, um dann zu entscheiden, in welchem Teil man weitersuchen muss. Idealerweise teilt man bei jedem Prüfvorgang die Menge der verbleibenden Seiten in zwei Teile, von denen man einen im nächsten Schritt ignorieren kann - eben genau mit der gleichen Idee, mit der der "Akinator" oder der Spielleiter beim Zahlenratespiel vorgeht.
Möchte man in einem Deutsch-Englisch Wörterbuch aber das englische Wort "juxtaposition" nachschlagen, so ist das eben NICHT effizient möglich: Man muss im schlimmsten Fall alle Einträge überprüfen (was natürlich niemand macht - dafür ist das Buch einfach nicht vorgesehen.)
Die Art und Weise, wie man in einem sortierten Datenbestand durch wiederholtes Aufteilen einen Datensatz findet, heißt "binäre Suche". Eine binäre Suche ist ein Algorithmus.
Laut Wikipedia ist ein Algorithmus "eine eindeutige Handlungsvorschrift zur Lösung eines Problems" (diese "Handlungsvorschrift" ist in der Informatik i.d.R. ein Programm). Es gibt viele Algorithmen. Beispielsweise ist auch Bubblesort ein Algorithmus: Man stellt einen unsortierten Datensatz bereit und Bubblesort macht daraus einen sortierten Datensatz.
In der Programmierung müssen wir ständig Algorithmen für bestimmte Probleme finden. Beispiele für weitere Probleme und die dafür passenden Algorithmen sind:
In der Informatik ist die erste Hürde oft, zu einem Problem einen Algorithmus zu finden. Aber ein gefundener Algorithmus kann auch "schlecht" sein: Er löst zwar das Problem, ist aber nicht effizient. Beispiel:
Problem: "Teilbarkeit durch 2". Ist eine gegebene natürliche Zahl X durch 2 teilbar?
Das Problem am ersten Algorithmus ist:
(muss noch ausformuliert werden)
Schlechte Algorithmen sind nicht nur ärgerlich, sondern letztlich auch ein Umweltproblem (Stichwort "green computing": Je weniger Rechenzeit ein Algorithmus benötigt, desto weniger CO2 wird produziert. Bei großen Rechenzentren fällt das ins Gewicht.)
Algorithmen lassen sich zwar gut in einer Programmiersprache wie Java formulieren, aber man möchte den Algorithmus zu Lehrzwecken auch solchen Leuten erklären können, die Java-Code nicht lesen können. Dafür verwendet man oft "Pseudocode". Das ist keine richtige Programmiersprache, sondern man beschreibt die Programmschritte (gemischt mit natürlicher Sprache und mathematischer Notation) so, dass man den Algorithmus problemlos in Java oder in einer anderen Programmiersprache formulieren kann.
Aufgabe 1)
Gegeben: Der "schlechte" Algorithmus zur Teilbarkeit durch 2:
Funktion teilbarDurchZwei( x ) {
rest = x
solange rest > 1
rest = rest - 2
wenn rest == 1:
return false
anderfalls
return true
}
Schreibe den Pseudocode in Java um und teste den Algorithmus anhand mehrerer Beispiele.
Aufgabe 2) Schreibe den Pseudocode für den oben skizzierten Primzahlalgorithmus
Aufgabe 2') Überlege, wie man den Algorithmus optimieren kann!
Aufgabe 3) Schreibe den Primzahlalgorithmus in Java
Aufgabe 4) Schreibe in Pseudocode einen Algorithmus, der aus einer Menge von Zahlen den Mittelwert herausfindet
Aufgabe 5) Schreibe in Pseudocode einen Algorithmus, der bei einer Menge von Zahlen entscheidet, ob Dubletten enthalten sind.