Informatik-Box

Lernpfad:Lerntheke Marsrover/31: Unterschied zwischen den Versionen

Lernpfad:Lerntheke Marsrover/31 (Quelltext anzeigen)

Version vom 10. November 2020, 00:15 Uhr

8.755 Bytes hinzugefügt ,  00:15, 10. Nov. 2020
keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Markierungen: Mobile Bearbeitung Mobile Web-Bearbeitung
Keine Bearbeitungszusammenfassung
 
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Karte}}
{{Karte}}


Simulation einer Turing-Maschinen (Busy Beaver?)
{{Kasten|
Eine [[wikipedia:Turingmaschine|Turingmaschine]] ist eine (theoretische) Maschine, die von dem britischen Mathematiker [[wikipedia:Alan Turing|Alan Turing]] erdacht wurde. Sie besteht aus einem unendlichen Band und einem Lese-/Schreibkopf, der über dieses Band läuft.
 
[[Datei:Turingmaschine.svg|center|300px]]
 
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 <code>0</code> dar, ein Feld mit einer Marke eine <code>1</code>.
* Pro Aufruf der <code>act()</code>-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 <code>"karte31_fleissige_rover"</code> laden, um die Ausgangssituation zu erhalten.
 
{{Aufgabe:Start|Icon=Greenfoot Rover.png}}
Implementiere die Methoden <code>links()</code> und <code>rechts()</code>, die den Rover ein Feld nach links / rechts bewegen. Der Rover schaut zu Beginn und nach Ablauf nach oben. 
{{Aufgabe:End}}
{{Lösung:Start}}
<syntaxhighlight lang="java">
    public void links() {
        drehe("links");
        fahre();
        drehe("rechts");
    }
   
    public void rechts() {
        drehe("rechts");
        fahre();
        drehe("links");
    }
</syntaxhighlight>
{{Lösung:End}}
 
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 <code>0</code> könnte das zum Beispiel so aussehen:
<syntaxhighlight lang="java">
    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
        }
    }
</syntaxhighlight>
 
{{Aufgabe:Start|Icon=Greenfoot Rover.png}}
# Ergänze in ''Zeile 9'' hinter <code>private Display anzeige;</code> diesen Code: <code>private int zustand = 0;</code>
# Ergänze innerhalb der Klasse <code>Rover</code> die Methode <code>public int zustand0()</code> von oben.
# Implementiere die <code>act()</code>-Methode wie folgt:
<syntaxhighlight lang="java">
    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
        }
    }
</syntaxhighlight>
# Probiere den Turing-Rover aus und prüfe, was diese "Turingmaschine" macht.
{{Aufgabe:End}}
{{Lösung:Start}}
Der obere Teil der Klasse Rover muss wie folgt aussehen:
<syntaxhighlight lang="java">
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 ...
   
}
</syntaxhighlight>
 
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.
{{Lösung:End}}
 
{{Aufgabe:Start|Icon=Greenfoot Rover.png}}
# 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.
{{Aufgabe:End}}
{{Lösung:Start|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.
{{Lösung:End}}
{{Lösung:Start|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:End}}
{{Lösung:Start|Lösung für zwei Zustände}}
<syntaxhighlight lang="java">
    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;
        }
    }
</syntaxhighlight>
{{Lösung:End}}
{{Lösung:Start|Lösung für drei Zustände}}
<syntaxhighlight lang="java">
    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;
        }
    }
</syntaxhighlight>
{{Lösung:End}}
 
{{Inhalt/Lerntheke}}
{{Inhalt/Lerntheke}}
Jneug
8.581

Bearbeitungen

Abgerufen von „http://ngb.schule/wiki/Spezial:Mobiler_Unterschied/6647...7421“