Einstellungen

Anmelden

Hilfe

Zur Ordnungswirkung fundamentaler Ideen der Informatik am Beispiel der theoretischen Schulinformatik

Beispiel 2: Mustererkennung

Eckart Modrow

Max-Planck-Gymnasium
Theaterplatz 10
37073 Göttingen
emodrow@astro.physik.uni-goettingen.de

Das folgende Beispiel soll zeigen, wie schon in der Mittelstufe quasi nebenbei Begriffe eingeführt werden, die in der theoretischen Informatik eine Rolle spielen. Beachten wir das Vertikalkriterium, dann müssen fundamentale Ideen auf jedem Niveau vermittelt werden können - also auch schon ganz zu Anfang des Informatikunterrichts.

Geplant wird eine Unterrichtseinheit für eine Klasse, die schon etwas mit einer Java-Entwicklungsumgebung vertraut ist - in diesem Fall mit dem JBuilder von Borland. Um den üblichen Einwänden entgegen zu wirken, die ein Programmentwicklungssystem wie dieses für zu komplex für den Anfangsunterricht halten, möchte ich gleich darauf hinweisen, dass z. B. die Erstellung von Präsentationen (z. B. mit MS-Powerpoint oder OpenOffice) mehr oder weniger Standard in dieser Altersstufe ist - und deren Oberfläche ist ähnlich komplex wie z. B. die JBuilder-IDE. Wenn also nur der Einsatz einfacher Software-Werkeuge möglich wäre, dann gelte das "Einfachheits-Argument" für alle - und für Präsentationssysteme gilt es offensichtlich nicht, denn die werden sehr erfolgreich benutzt. Ebenso ist das Argument, dass "theoretische" Inhalte der Oberstufe oder sogar nur der Universität vorbehalten sein müssten, offensichtlich nicht stichhaltig. Einerseits widerspricht es dem Vertikalkriterium, anderseits bedeutet ein propädeutisches Vorgehen natürlich nicht, dass die Themen erschöpfend behandelt werden. Weiterhin gibt es genügend Beispiele (z.B. Didaktik nach P. Hubwieser) und Werkzeuge (z.B. die "Turing-Kara" der ETH Zürich), die für diese Altersstufe vorgesehen sind.

In der Mittelstufe hat der Informatikunterricht ähnlich wie in den Naturwissenschaften u. a. die Aufgabe, Erfahrungen zu ordnen und ggf. zu verschaffen, anhand derer eine informatische Begriffsbildung erfolgen kann, die weitgehend der Vermittlung fundamentaler Ideen entspricht. Die entwickelten Begriffe sind in einem geeigneten Kontext einzuführen und anzuwenden, sodass im weiterführenden Unterricht auf sie aufgebaut werden kann. Unter dieser Voraussetzung stehen dann z. B. in der Sekundarstufe II genügend Erfahrungen und Unterrichtszeit zur Verfügung, um z. B. theoretische Inhalte angemessen vertieft zu unterrichten. Wenn es also möglich ist, dann sollten schon sehr früh Begriffe wie z. B. Zustand, Zustandswechsel, Automat, ... benutzt werden - auch wenn es nicht unbedingt nötig ist. Solange es nicht stört, kann damit weiterführender Unterricht effizient vorbereitet werden.

In diesem Fall sollen die folgenden Begriffe eingeführt bzw. benutzt werden

Automat (Eine Maschine zur Mustererkennung, die nach vorgegebenen Regeln funktionieren)

Zustand (beschreibt die momentane "Befindlichkeit" eines Automaten)
Algorithmus (beschreibt hier die Arbeitsweise des Automaten z. B. in Abhängigkeit von dessen Zustand)
Ereignis (löst Zustandswechsel und Methodenaufrufe aus, die (Teil-)Algorithmen implementieren)

Gesucht ist ein kleines System, das eine typische Funktionalität von Textverarbeitungs- und Mailsystemen rekonstruiert: Textbausteine können durch spezielle Zeichenfolgen "abgekürzt" werden. Erkennt das System diese Zeichenfolgen, dann ersetzt es diese durch den "Langtext". In diesem Fall wollen wir uns auf die Zeichenfolge "Mit freundlichen Grüßen"

beschränken, die durch "MfG" abgekürzt wird.

In einer ersten Phase soll gemeinsam das Problem analysiert und die zu lösenden Teilprobleme ermittelt werden. Danach kann im Wechsel in Gruppen und im Unterrichtsgespräch gearbeitet werden.
(verplant wurden Doppelstunden)

Stunde	Inhalt	Kommentar
1	Einführung, Planung, Zustandsdiagramm	Problem besprechen, Zustandsbegriff herausarbeiten, Zustandsdiagramm entwickeln
2-3	Appletoberfläche planen, Überführungsfunktion schreiben, Programm testen und verbessern	Designer benutzen, Eigenschaften setzen, Überführungsfunktion als Mehrfachauswahl, einfache Zeichenfolgen eingeben und Zustand ausgeben lassen
4-5	"Mustererkenner" im Struktogramm planen, Teilaufgaben festlegen, "Mustererkenner" fertig machen	erforderliche Daten festlegen, Abläufe anhand von Beispielen ermitteln, Struktogramm zeichnen und testen, Applet so ändern, dass es als Mustererkenner arbeitet

Es sollen die Begriffe des Zustands des Automaten sowie der Ereignisse, die Aktionen auslösen, deutlich herausgearbeitet werden.

zur 1. Doppelstunde:

Problem besprechen, anhand von einfachen Beispielen Zustandsabhängigkeit herausarbeiten.

Automatenmodell benutzen, Zustandsdiagramm entwickeln:

Zuerst den einfachen Durchgang festlegen. Wichtig sind die Zeichen {M,f,G}.

Danach die fehlenden Kanten mit {M,f,G} ergänzen.

Wählen wir das Zeichen "x" als Stellvertreter für alle anderen Zeichen, dann können wir das Diagramm vervollständigen.

Der Automat hat die Zeichenfolge "MfG" erkannt, wenn er in den Zustand "3" überführt worden ist.

zur 2./3. Doppelstunde:

Appletoberfläche planen: In ein Textfeld werden Zeichen eingegeben. Diese werden auf Knopfdruck "geprüft" und der aktuelle Zustand wird ausgegeben. Der Einfachheit halber versetzt ein Reset-Knopf das System in den Anfangszustand.

Im Designer wird die Oberfläche erzeugt. Eigenschaften (Namen, Aufschriften, ...) werden gesetzt. Das System erzeugt das Rumpfprogramm und die Ereignisbehandlungsmethoden automatisch. Diese werden mit Code gefüllt.

Am einfachsten ist der Reset-Knopf zu behandeln:

void bReset_actionPerformed(ActionEvent e)

{
zustand = 0;

lZustand.setText(""+zustand);

Etwas komplizierter ist es mit dem Prüfen. Wir holen uns den Eingabetext, prüfen, ob überhaupt etwas vorhanden ist und überprüfen dann das erste Zeichen

void bPruefe_actionPerformed(ActionEvent e)

    {
      String eingabe = tfEingabe.getText();
      if(eingabe.length()>0) //zur Sicherheit
      {
        char c = eingabe.charAt(0);
        pruefe(c);
        lZustand.setText("" + zustand);
      }
    }

Und wie prüft man nun die eingegebenen Zeichen? In einer Mehrfachauswahl bestimmt man je nach aktuellem Zustand aus dem geprüften Zeichen den Folgezustand.

private void pruefe(char zeichen)

    {
      switch(zustand)
      {
        case 0: {if(zeichen=='M') zustand = 1; break;}
        case 1:
        {
          if(zeichen=='M') zustand = 1;
          else if(zeichen=='f') zustand = 2;
               else zustand = 0;
          break;
        }
        case 2:
        {
          if(zeichen=='M') zustand = 1;
          else if(zeichen=='G') zustand = 3;
               else zustand = 0;
          break;
        }
        case 3:
        {
          if(zeichen=='M') zustand = 1;
          else zustand = 0;
          break;
        }
      }
    }

Das funktioniert sogar!

<Die Java-Klassen in Form eines zip-Files können hier heruntergeladen werden.>

zur 4. /5. Doppelstunde:

Jetzt soll ein richtiger "Brief durchmustert werden. Dafür ersetzen wir das Textfeld durch eine TextArea-Komponente und benutzen einen Suchen-Knopf, der die Mustererkennung durchführt.

Der Suchvorgang lässt sich leicht im Struktogramm beschreiben:

Und dann auch als Java-Quelltext:

void bSuchen_actionPerformed(ActionEvent e)

    {
      String zeile = taText.getText();
      String neu="";
      char c;
      zustand = 0;
      for(int i=0;i<zeile.length();i++)
      {
        c = zeile.charAt(i);
        pruefe(c);
        if(zustand==3)
          neu = neu.substring(0,neu.length()-2) + "Mit freundlichen Grü?en";
        else
          neu = neu + c;
      }
      taText.setText(neu);
    }

<Die Java-Klassen in Form eines zip-Files können hier heruntergeladen werden.>

Erweiterungen/Differenzierungsmöglichkeiten:

Andere Begriffe suchen und ersetzen

Zwei Begriffe gleichzeitig suchen und ersetzen

Nach dieser Unterrichtsphase sollen die Schülerinnen und Schüler mindestens Kenntnisse zu folgenden Themen besitzen:

Klasse, Objekt, Eigenschaft

Ereignis, Ereignisbehandlung, Methodenaufruf

elementare Datentypen: Zahl, Zeichen, Zeichenkette
Wertzuweisung, Sequenz, Alternative, Iteration
Variable, Variablenname, Variablenwert

Benutzer: gast • Besitzer: schwill • Zuletzt geändert am: