Computerorientierte Mathematik

Übersicht

• Hintergrund
• Wettbewerb
• Hilfsmittel

Hintergrund

In der Übung am 25.02.2001 wurde behauptet, dass Menschen nicht in der Lage sind, eine zufällige Folge von Nullen und Einsen zu erzeugen.
Um diese Behauptung zu untermauern wurde folgendes Experiment vorgeschlagen:

Mehrere Studenten der CoMa tippen jeweils eine Folge von 1000 Nullen und Einsen hintereinander ein und versuchen dabei, so zufällig wie möglich zu sein.
Vor dem Eintippen der nächsten Zahl erhält ein Algorithmus jeweils die bis dahin eingegebene Zahlenfolge und "errät" die nächste Zahl.

Vermutung: Mit einfachen Algorithmen können durchschnittlich 70% der Zahlen richtig vorhergesagt werden.

Bemerkung: Bei tatsächlich zufälligen Zahlenfolgen kann jeder Algorithmus durchschnittlich nur 50% der Zahlen vorhersagen.

Wettbewerb

Wir wollen den oben beschriebenen Versuch in Form eines kleinen Wettbewerbs durchführen, um die Erkenntnis zu gewinnen gibt, wie durschaubar Menschen sein können.
Damit das Experiment auch richtig fair abläuft, gibt es bei dem Wettbewerb zwei Kategorien:

1. Wer entwickelt den besten Algorithmus zum Vorhersagen von Zahlen?

   Jeder von Euch kann einen Algorithmus in Java schreiben, der zu einer gegebenen 0/1-Folge die nächste Zahl vorhersagt. Dazu müßt ihr nur eine Klasse PredictVornameNachname schreiben, die das unten beschriebene Interface Predictor implementiert.

   Jeder Teilnehmer schickt bitte bis spätestens 14.02.2001 10.00 Uhr seiner Algorithmus in Form einer compilierfähigen Java-Datei (Name: PredictVornameNachname.java) an Andreas. Sollte Euer Algorithmus Hilfklassen benötigen, so implementiert diese bitte als private innere Klassen.

   Jeder Algorithmus wird auf allen dann eingetippten 0/1-Folgen getestet. Der Algorithmus mit der höchsten Trefferquote, berechnet auf allen teilnehmenden Folgen, gewinnt den Wettbewerb.

   Bitte habt Verständnis, dass wir aus Fairness-Gründen keinerlei Betreuung, weder per Email noch während der betreuten Rechnerzeiten, zu dieser Aufgabe bieten können.

2. Wer kann die "zufälligste" 0/1-Folge eintippen?

   Jeder von Euch kann eine 0/1-Folge eintippen, von der er denkt, sie sei sehr zufällig. Diese Folge wird dann mit allen am Wettbewerb teilnehmenden Algorithmen getestet. Die 0/1-Folge, die gemittelt über alle Algorithmen die geringste Trefferquote verursacht hat, gewinnt den Wettbewerb.

   Damit es bei diesem Wettbewerb wirklich fair zu geht, werden wir hier keine per Email eingesendeten 0/1-Folgen zulassen. Stattdessen könnt ihr am 14.02. (evtl. auch früher) bei Andreas Eure Folge direkt am Rechner eingeben. Eingabe Schluß ist dabei jedenfalls am 14.02. um 17.00 Uhr.

Herr Möhring hat für den besten Algorithmus einen Buchpreis gestiftet. Allerdings wollen wir den Preis nicht allein für den Algorithmus mit der höchsten Trefferquote vergeben, sondern in erster Linie für den besten Algorithmus, der unsere Programmierrichtlinien einhält und so effizient wie möglich programmiert ist.

Hilfsmittel

Alles, was ihr eigentlich braucht, ist das interface Predictor, das wie folgt aussieht:

/** A predictor can predict the next number of a 0/1-sequence */
public interface Predictor {
    /** Predicts the next number.
	An array of arbitrary length is given, of wich the first numbers are used.
	So the first numbers are 0 or 1. All later positions of the array are undefined.
	@param numbers An array of already known numbers.
	@param digits The number of used positions of the array. 
	@returns 0 or 1.
    */
    public int predictNext(int[] numbers, int digits);

    /** A short description.*/
    public String toString();
}
    

Eure Hauptaufgabe besteht darin, die Methode predictNext zu implementieren, die die eigentliche Rate-Methode ist. Diese Methode erhält zwei Parameter:

• int[] numbers: In diesem Array stehen die jeweils bisher bekannten Zahlen der Zahlenfolge.
  Achtung! Dieses Array ist zu lang und nicht bis zum letzten Element mit sinnvollen Zahlen gefüllt, sondern nur die ersten Stellen entsprechen der Folge.
• int digits: Dieser Parameter gibt die Zahl der sinnvollen Einträge des Arrays an. Die bisherige Zahlenfolge besteht also nur aus den Werten numbers[0] bis numbers[digits-1]. Die übrigen Stellen von numbers enthalten keine sinnvollen Werte (sollten eigentlich mit 0 initialisiert sein).

Außerdem müßt ihr in der Methode toString einen kurzen (max. 8 Zeichen) String zurückgeben, der Euren Algorithmus eindeutig identifiziert, z.B. Anfangsbuchstabe des Vornamens + erste 7 Buchstaben des Nachnamens.

Eure Predictor-Klasse darf darüber hinaus weitere Methoden haben, die allerdings private sein sollten.
Falls ihr einen Konstruktor benötigt, so darf dieser keine Parameter erwarten.

Nun wollt ihr ja sicherlich Euren Algorithmus testen. Dazu findet ihr hier (Unix/Linux: .tar.gz, Win: .zip) eine kleine Anwendung, in die ihr nur noch Euren Algorthimus einbauen müßt. Dazu fügt ihr ihn einfach in der Methode startPrediction() bei folgenden Zeilen ein:

	/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	   Add your own algorithm here
	   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
	Predictor[] predictors = new Predictor[5];
	predictors[0] = new Predict0();
	predictors[1] = new Predict1();
	predictors[2] = new PredictAlter();
	predictors[3] = new PredictRandom();
	predictors[4] = new PredictOpposite();
    

Damit ihr auch genug 0/1-Folgen zum testen habt, gibt es das Vezeichnis sequences, in dem ihr verschiedene mehr oder weniger zufällige Folgen findet (Referenzmenge):

• human: Diese Folgen sind wirklich von verschiedenen Leuten eingegeben!
• binary: Hier sind die binären Zahlen verschiedener Länge versteckt. Insbesondere bei den ersten Folgen sollte eine Trefferquote von über 95% erreichbar sein!
• monoton und repeat: auch diese Folgen sind alles andere als zufällig!
• rand und random: Diese Folgen wurden mit guten (Pseudo-)Zufallszahlengeneratoren erzeugt. Hier sind nur durchschnittliche Trefferquoten von 50% zu erwarten.

• Predict0 rät immer 0,
• Predict1 rät immer 1,
• PredictAlter rät immer abwechselnd 0 und 1,
• PredictRandom rät zufällig,
• PredictOpposite rät immer das Gegenteil der letzten Zahl.

So, nun aber viel Spaß und viel Erfolg beim Zahlen-Raten!