Aktivität 12 – endliche Automaten

Schatzsuche – endliche Automaten

Computerprogramme müssen oft eine Folge von Symbolen, wie Buchstaben oder Wörter, in einem Dokument oder sogar den Text eines anderen Computerprogramms verarbeiten. ComputerwissenschaftlerInnen benutzen dafür oft einen endlichen Automaten. Ein endlicher Automat (EA) folgt einer Reihe von Anweisungen, um zu sehen, ob der Computer das Wort oder die Zeichenfolge von Symbolen erkennt. Wir werden mit etwas arbeiten, das einem EA entspricht - Schatzkarten!

-  Mathematik: Logik und Argumentation entwickeln - Wörter und Symbole verwenden, um Modelle zu beschreiben und umzusetzen - Sozialwissenschaft -  Englisch

-  Einfache Kartenlesung

-  Muster erkennen

-  Logik

-  Befehle ausführen

-  9+

Worum geht es in dieser Aktivität?

Endliche Automaten werden in der Informatik verwendet, um einem Computer bei der Verarbeitung einer Folge von Zeichen oder Ereignissen zu helfen.

Ein einfaches Beispiel ist, wenn du eine Telefonnummer wählst und eine Nachricht erhältst, die sagt „Drücken Sie 1 für diese ... Drücken Sie 2 für das ... Drücken Sie 3, um mit einer Serviceperson zu sprechen.“ Die Tastendrücke sind Eingaben für einen endlichen Automaten am anderen Ende des Telefons. Der Dialog kann ziemlich einfach oder sehr komplex sein. Manchmal wird man im Kreis herumgeführt, weil es im endlichen Automaten eine seltsame Schleife gibt. Wenn dies auftritt, ist dies ein Fehler im Design des Systems - und es kann für den Anrufer extrem frustrierend sein!

Ein anderes Beispiel ist, wenn du Geld von einem Bankautomaten erhältst. Das Programm im Computer der Maschine führt dich durch eine Abfolge von Ereignissen. Innerhalb des Programms werden alle möglichen Sequenzen als endlicher Automat gespeichert. Jede Taste, die du drückst, bringt den Automaten in einen anderen Zustand. In einigen Ländern haben Computer verschiedene Anweisungen wie „100€ Bargeld herausgeben“ oder „einen Beleg drucken“ oder „die Geldkarte auswerfen“.

Einige Computerprogramme befassen sich tatsächlich mit deutschen Sätzen, die Karten, wie die auf Seite 130, verwenden. Sie können sowohl Sätze selbst erzeugen, als auch Sätze verarbeiten, die der Benutzer eingibt. In den 1960er Jahren schrieb ein Informatiker ein berühmtes Programm namens „Eliza“ (nach Eliza Doolittle), das Gespräche mit Menschen führte. Das Programm gab vor, Psychotherapeut zu sein und brachte führende Ausdrücke wie „Erzähl mir von deiner Familie“ und „Mach weiter“ hervor. Obwohl es nichts „verstand“ war es ausreichend plausibel - und seine menschlichen Benutzer waren ausreichend leichtgläubig, sodass einige Leute wirklich glaubten, sie würden mit einem menschlichen Psychotherapeuten sprechen.

Obwohl Computer die natürliche Sprache nicht wirklich gut verstehen, können sie künstliche Sprachen leicht verarbeiten. Eine wichtige Art der künstlichen Sprache ist die Programmiersprache. Computer benutzen Automaten mit endlichen Zuständen, um Programme einzulesen und in Form elementarer Computeranweisungen zu übersetzen, die dann direkt vom Computer „ausgeführt“ werden können.

Übungen und Materialien

Materialien

-  Einen Satz Inselkarten (die Anweisungen müssen vor denen verborgen bleiben, die versuchen, die Karte zu zeichnen!)   - Kopiere die Kopiervorlage: Inselkarten (ab Seite 125) und schneide sie aus. Falte entlang der gepunkteten Linie und klebe jede Karte so, dass auf der Vorderseite der Karte der Name der Insel und auf der Rückseite die Anweisungen stehen.

-  Arbeitsblatt: Finde deinen Weg zu den Reichtümern auf der Schatzinsel

-  Stift oder Bleistift

-  Arbeitsblatt: Schatzinseln

-  Arbeitsblatt: Das mysteriöse Münzspiel