Lernpfad:Lerntheke Marsrover/31

Fleißige Rover

Eine Turingmaschine ist eine (theoretische) Maschine, die von dem britischen Mathematiker Alan Turing erdacht wurde. Sie besteht aus einem unendlichen Band und einem Lese-/Schreibkopf, der über dieses Band läuft.

Der Kopf kann einzelne Zeichen, die auf dem Band stehen, lesen und/oder neue Zeichen auf das Band schreiben. Außerdem kann sich der Kopf immer um ein Feld nach link oder rechts über das Band bewegen.

Eine Turingmaschine wird programmiert, indem verschiedene Zustände definiert werden, in der sie sich befinden kann und wie sie sich dann verhalten soll (welches Zeichen schreiben/wie bewegen).

Ein Fleißiger Biber ist eine besondere Art von Turingmaschine, die nur Einsen und Nullen liest und schreibt und so programmiert ist, dass sie mit einer festen Anzahl Zuständen möglichst viele Einsen auf das Band schreibt.

Der Rover kann eine Turingsmaschine simulieren, aber natürlich nicht mit unendlich viel Speicherplatz. Das Band kann maximal 15 Zeichen breit sein.

Wir legen folgende Bedingungen für die Rover-Turingmaschine fest:

Der Rover ist der Lese-/Schreibkopf und steht mit Blickrichtung nach oben.
Der Rover kann sich nur ein Feld nach links oder rechts bewegen.
Ein leeres Feld stellt eine 0 dar, ein Feld mit einer Marke eine 1.
Pro Aufruf der act()-Methode kann der Rover das aktuelle Feld auf eine Marke prüfen, die Marke entfernen oder eine setzen und sich ein Feld bewegen. Mehr nicht.

Das Rolle des Bandes unserer Rover-Turingmaschine übernimmt eine Zeile in der Roverwelt. Du kannst die Karte "karte31_fleissige_rover" laden, um die Ausgangssituation zu erhalten.

Arbeitsauftrag

Implementiere die Methoden links() und rechts(), die den Rover ein Feld nach links / rechts bewegen. Der Rover schaut zu Beginn und nach Ablauf nach oben.

Lösung

    public void links() {
        drehe("links");
        fahre();
        drehe("rechts");
    }
    
    public void rechts() {
        drehe("rechts");
        fahre();
        drehe("links");
    }

Damit der Rover sich auch wie der Schreib-/Lesekopf der Turingsmaschine verhalten kann, muss er sich einen Zustand merken können und basierend auf diesem Zustand entscheiden können, wie er weiterarbeitet. Ein Zustand kann einfach durch eine Zahl repräsentiert werden. Wir starten immer in Zustand 0.

In jedem Zustand muss der Rover entschieden was er macht. Diese Entschiedung hängt davon ab, ob auf dem Feld eine Marke liegt, oder nicht. Zur besseren Ünersicht (siehe Strukturierte Zerlegung) schreibst du für jeden Zustand eine eigene Methode, die die passende Aktion ausführt und den neuen Zustand als Zahl zurückgibt.

Für Zustand 0 könnte das zum Beispiel so aussehen:

    public int zustand0() {
        if( markeVorhanden() ) {// es wurde "1" gelesen
            entferneMarke();        // schreibe eine "0"
            links();                // bewege den Kopf nach links
            return 0;               // bleibe in Zustand 0
        } else {                // Es wurde "0" gelesen
            setzeMarke();           // schreibe eine "1"
            rechts();               // bewege den Kopf nach links
            return 1;               // wechsele in Zustand 1
        }
    }

Arbeitsauftrag

Ergänze in Zeile 9 hinter private Display anzeige; diesen Code: private int zustand = 0;
Ergänze innerhalb der Klasse Rover die Methode public int zustand0() von oben.
Implementiere die act()-Methode wie folgt:

    public void act() {
        switch( zustand ) {
            case 0:                     // Wenn in Zustand 0
                zustand = zustand0();   // führe die Methode "zustand0" aus
                break;                  // und beende die act()-Methode
        }
    }

Probiere den Turing-Rover aus und prüfe, was diese "Turingmaschine" macht.

Lösung

Der obere Teil der Klasse Rover muss wie folgt aussehen:

public class Rover extends Actor {

    private Display anzeige;

    private int zustand = 0;
    
    /**
     * Act-Methode des Rovers. Programmiere hier deinen Algorithmus und starte
     * ihn mit dem "Act"-Button in Greenfoot.
     */
    public void act() {
        switch( zustand ) {
            case 0:                     // Wenn in Zustand 0
                zustand = zustand0();   // führe die Methode "zustand0" aus
                break;                  // und beende die act()-Methode
        }
    }
    
    public int zustand0() {
        if( markeVorhanden() ) {// es wurde "1" gelesen
            entferneMarke();        // schreibe eine "0"
            links();                // bewege den Kopf nach links
            return 0;               // bleibe in Zustand 0
        } else {                // Es wurde "0" gelesen
            setzeMarke();           // schreibe eine "1"
            rechts();               // bewege den Kopf nach links
            return 1;               // wechsele in Zustand 1
        }
    }
    
    public void links() {
        drehe("links");
        fahre();
        drehe("rechts");
    }
    
    public void rechts() {
        drehe("rechts");
        fahre();
        drehe("links");
    }
    
    // Rest der Klasse Rover folgt hier ...
    
}

Die Turingmaschine schreibt eine "1" (eine Marke) auf das Band und macht dann nichts mehr (terminiert). Da die Maschine nur einen Zustand hat, handelt es sich um einen "Fleißigen Biber" (bzw. "Fleißigen Rover"), der die maximale Anzahl "1" auf das Band schreibt, die mit genau einem Zustand möglich ist.

Arbeitsauftrag

Implementiere einen "Fleißigen Rover" mit zwei Zuständen.
Implementiere einen "Fleißigen Rover" mit drei Zuständen.

Probiere selber, eine möglichst gute lösung zu finden. Wenn du eine Lösung hast, kannst du dein Ergebnis mit der maximalen Anzahl vergleichen, die unten in der Lösung steht.

Hinweis zum Biber mit drei Zuständen

Der "Fleißige Biber" mit drei Zuständen kann maximal 21 "1" auf das Band schreiben. Da unser Band nur 15 Felder hat, wirst du auch bei optimaler Lösung nicht alle "1" schreiben können.

Maximale Anzahl "1" bei fester Anzahl an Zuständen

Ein Zustand: 1-mal "1"
Zwei Zustände: 6-mal "1"
Drei Zustände: 21-mal "1"
Vier Zustände: 107-mal "1"

Lösung für zwei Zustände

    private int zustand = 0;

    public void act() {
        switch( zustand ) {
            case 0:
                zustand = zustand0();
                break;
            case 1:
                zustand = zustand1();
                break;
        }
    }
    
    public int zustand0() {
        if( markeVorhanden() ) {
            links();
            return 1;
        } else {
            setzeMarke();
            rechts();
            return 1;
        }
    }
    
    public int zustand1() {
        if( markeVorhanden() ) {
            rechts();
            return 2;
        } else {
            setzeMarke();
            links();
            return 0;
        }
    }

Lösung für drei Zustände

    private int zustand = 0;

    public void act() {
        switch( zustand ) {
            case 0:
                zustand = zustand0();
                break;
            case 1:
                zustand = zustand1();
                break;
            case 2:
                zustand = zustand2();
                break;
        }
    }
    
    public int zustand0() {
        if( markeVorhanden() ) {
            rechts();
            return 3;
        } else {
            setzeMarke();
            rechts();
            return 1;
        }
    }
    
    public int zustand1() {
        if( markeVorhanden() ) {
            rechts();
            return 1;
        } else {
            rechts();
            return 2;
        }
    }
    
    public int zustand2() {
        if( markeVorhanden() ) {
            links();
            return 0;
        } else {
            setzeMarke();
            links();
            return 2;
        }
    }

Lernpfad:Lerntheke Marsrover/31

Navigationsmenü

Suche