Theorie Wieso muss es Informatikunterricht in einer Schule geben ?

Theorie

Wieso muss es Informatikunterricht in einer Schule geben ?

Informatik ist weit verbreitet

Wie viele andere Wissenschaften (Mathematik, Physik… ) ist die Informatik in viele Aspekte des alltäglichen Lebens eingebettet. Deswegen sollte man zumindest oberflächliche Kenntnisse in dem Gebiet gewinnen.

Die Komplexität der Informatik bewusst machen

Nachdem man die einfachen Grundprinzipien der Informatik erlernt hat und mehr Selbstvertrauen auf diesem Gebiet gewonnen hat, muss man sich näher mit ihr vertraut machen und sein Wissen vertiefen. So kann man erfahren, welche Voraussetzungen z.B. ein Informatikstudium mit sich bringt u. a.:

Bewusst machen, über die Komplexität der Informatik

Den Schülern muss klar werden:

Informatik ist nicht (nur) Word und Excel oder Internet. Die Informatik ist viel komplexer und komplizierter.

Einschränkung

Maschinen und Automaten

Was hilft uns das Verstehen des Automatenverhaltens ?

Besser im Alltag zu Recht zu kommen.

Mehr Selbstvertrauen im Umgang mit Automaten gewinnen.

Das Grundprinzip der Eingabe und Ausgabe zu verstehen.

Was hilft uns das Verstehen des Automatenverhaltens ?

Erlernen der spezifischen Denkweise der Informatiker (Programmierer):

Verschiedene Maschine werden aus einem, für den Schüler neuen

Gesichtspunkt besprochen; Die Schüler werden das Denken im

Großen und Kleinen kennenlernen

Voraussetzungen

Vorkenntnisse der Schüler:Die Schüler sollten Programmierkenntnisse haben, um später gewonnenes Wissen über die Automaten auch implementieren zu können.Weiteres Problem: Die Automatentheorie könnte für informatisch weniger Interessierte zu theoretisch und damit evtl. abschreckend wirken. Daher ist eine Einführung in die Automatentheorie zu Beginn des Kurses, also Anfang der Jgst. 11 mit dem Risiko behaftet, dass einige Schüler, die sich etwas anderes unter „Informatik“ vorgestellt haben, das Fach wieder abwählen.Geeignet wäre eine Einführung der Automatentheorie etwa in der Jgst. 12

Der Unterricht

Folgenden Themen werden besprochen:

Endliche Automaten;

Parallel und Reihenschaltung von Endlichen Automaten;

Mealy und Moore Akzeptoren;

Alphabet und Sprache;

Der Unterricht

Deterministische Endliche Automaten;

Nichtdeterministische Endliche Automaten;

Grammatiken und Sprachen (nicht unbedingt ausführlich).

Endliche Automaten-1. Teil

Begonnen wird mit einem Unterrichtsgespräch:

Die Schüler sollen hier zunächst ihre Vorstellung vom Begriff „Automaten“ darstellen und sagen, welche Automaten sie bereits aus dem täglichen Leben kennen oder zumindest glauben, zu kennen.

Endliche Automaten-1.Teil

Der Lehrer diskutiert mit den Schülern über die Funktionen sämtlicher einfacher Geräte.

-> Ziele:

- Der Lehrer verschafft sich einen ersten Eindruck von Leistungsstärke und Interesse des Kurses

Endliche Automaten-1.Teil

- Motivation, sich überhaupt mit Automaten auseinanderzusetzen. Das Interesse der Schüler lässt sich leichter gewinnen, wenn sie sehen, dass die Automatentheorie durchaus ein alltägliches Problem darstellt und dass ohne sie ein Leben in dieser Form nicht möglich wäre.

Endliche Automaten-1.Teil

Beispiele:

CD-Player, Colaautomat, Fahrkartenautomat, Ampel, etc.

Die von den Schülern genannten Automaten werden eventuell durch den Lehrer ergänzt.

Endliche Automaten- 1.Teil

Es folgt eine erste Einführung in die Automatentheorie:

Das Prinzip eines einfachen Automaten wird zunächst anhand eines Lichtschalters erklärt. Der Lichtschalter hat nur 2 Zustände: Ein/Aus.

Es werden Begriffe wie Zustand, Zustandsänderung, Eingabe, Ausgabe, etc. eingeführt.

Endliche Automaten-1.Teil

Ein Automat wird herausgegriffen und dessen Funktion und durchgeführte Prozesse werden von den Schülern erläutert (mit eigenen Worten).

(Haus-)Aufgabe an die Schüler: Beschreibe einen beliebigen Automaten aus dem Alltagsleben. Erläutere hierbei mögliche Eingaben, Prozesse und Resultate mit eigenen Worten.

Endliche Automaten-1.Teil

-> Ziel: Schüler sollen Prozesse erkennen lernen, vielleicht auch darauf kommen, dass nur bestimmte Ein- und Ausgaben möglich sind.

Beispiel: Ein Colaautomat akzeptiert nur bestimmte Geldmünzen und gibt (zumindest in der Regel) keinen Kaffee aus.

Endliche Automaten- 2.Teil

Dann folgt eine Besprechung der Ergebnisse im Unterrichtsgespräch.

Der Lehrer zeichnet den zu einem der beschriebenen Automaten gehörigen Graphen an die Tafel. Darin werden die Schüler eingebunden und aufgefordert, sich aktiv an der Graphenbildung zu beteiligen.

Endliche Automaten- 2.Teil

Es wird zunächst eine Definition von Endlichen (Deterministischen) Automaten gegeben. Die Begriffe „Sprache“ und „Alphabet“ werden erläutert.

Endliche Automaten- 2.Teil

A= (X,Y,Z,Ф,z0)X,Y,Z- Nicht leere MengenФ: X x ZY x Zz0 ZX- Menge der EingabezeichenY- Menge der AusgabezeichenZ- Menge der Zustände

Ф- Übergangsfunktion und z0- Startsymbol

Endliche Automaten- 2.Teil

(Haus-) Aufgabe an die Schüler: Zeichne selbst den Graphen des von dir beschriebenen Automaten !

Die Kenntnisse der Schüler über die Graphentheorie werden anhand von mehreren Aufgaben hierzu vertieft.

Endliche Automaten- 3.Teil

Die Parallel- und Reihenschaltung von Automaten werden demonstriert mit dem Ziel: Untersuchung eines Automaten, der eine Ampel vorstellt.

Endliche Automaten- 3.Teil

z1 z2 z3 z4t t t

t

z0- Startz1- Grünz2- Gelbz3- Rotz4- Rot/Gelbt= 3 s.

z0t

Endliche Automaten- 3.TeilParallelschaltung

z11,z12 z21,z22 z31,z32 z41,42t t t

t

z01,z02t

Endliche Automaten- 3.TeilReihenschaltung

z11,z12,z33,z34

z21,z22,z43,z44

z31,z32,z13,z14

z41,42,z23,z24

t t t

t

z01,z02,z03,z04

t

Akzeptoren

Mealy und Moore Akzeptoren werden definiert. Die Eigenschaften von beiden werden besprochen und die Unterschiede werden erklärt.

Die Äquivalenz der beiden Akzeptoren wird gezeigt, indem zu einem Mealy- Akzeptor ein Moore- Akzeptor gegeben wird Satz

Akzeptoren

Es wird versucht, die Unterschiede zwischen den beiden Typen zu demonstrieren- Sourcecode?

Beispiele:

Akzeptor für Zahlkonstanten, Akzeptor für Strings

Akzeptor für Zahlkonstanten

0 10…9

0…9

Endliche Automaten

Nach ausreichender Vertiefung der Kenntnisse folgt eine weiterführende Aufgabe: Die Schüler bekommen einen Graphen zu einem nichtdeterministischen Automaten

Den Schülern wird nicht vorher mitgeteilt, dass der Automat nicht determiniert.

Akzeptor für Strings

0 1 2 3g u t

g

u

t

Nichtdeterministischer endlicher Automat

Es folgt ein Unterrichtsgespräch, in dem der Lehrer zunächst abwartet, ob einer der Schüler selbstständig das Problem ankündigt und ansonsten nachfragt, ob jemand ein Problem erkannt hat.

Nichtdeterministischer endlicher Automat

Ziel: Die Schüler sollen selbstständig darauf kommen, dass ein nichtdeterministischer Automat keine sinnvolle Verwendung im Alltag bietet, da man unter Umständen kein Resultat bekommt.

Nichtdeterministischer endlicher Automat

Den Schülern wird zur Demonstration folgendes Szenario vorgelegt:Ein Schuldirektor versucht mittels eines nichtdeterministischen Automaten (wie eben vorgestellt), ein Suchprogramm zu erstellen, das von der Schule abgehende Emails auf Schimpfwörter überprüft. Der Lehrer legt ein entsprechendes Programm vor und die Schüler sollen nun versuchen, dieses Suchprogramm zu umgehen.

Nichtdeterministischer endlicher Automat

Eine weiterführende Aufgabe wird folgendermaßen gestellt:

Wie kann der Automat dahingehend verändert werden, dass das Programm nicht mehr so einfach zu umgehen ist?

Nächste Aufgabe: Das Suchprogramm

entsprechend verändern.

Akzeptor für Strings- Nichtdeterministisch

0 1 2 3g u t

Nichtdeterministischer endlicher Automat

Daraus resultiert die folgende Problemstellung:

Wie wird aus einem nichtdeterministischen ein deterministischer Automat?

Grammatiken und Sprachen

Nachdem der besprochene Teil der Automatentheorie abgeschlossen ist,

folgt ein kleiner Einblick in das Thema

Grammatiken und Sprachen.

Grammatiken und Sprachen

Zunächst wird eine Definition von Grammatik gegeben.

Die Grammatik G ist ein Tupel G= (N,X,S,R) N- Nichtterminale Symbole X- Terminale Symbole S- Startsymbol, SN V= X N, Vx=V*NV* RVxxV* X und N- Disjunkte Mengen R- endliche Menge von Regeln

Grammatiken und Sprachen

Am Ende der Unterrichtsreihe werden noch die einzelnen Typen von Grammatiken vorgestellt:

Eine Grammatik G=(N,X,S,R) mit V=NX heißt:

Grammatiken und Sprachen

- Regulär(Typ 3) falls RNx({}XXN),- Kontextfrei (Typ 2) falls RNxV*,- Kontextsensitiv (Typ 1) falls für alle Regeln uv in R gilt : |u|<=|v|,- Typ 0 sonst. Entsprechend heißt eine Sprache LX* vom

Typ i oder auch regulär, kontextfrei, kontextsensitiv wenn es eine Grammatik G vom Typ i mit L(G)=L gibt.

Grammatiken und Sprachen

Es folgen einige Beispiele für Grammatiken zu den entsprechenden Sprachen (s. Tafel)

Die Schüler erhalten evtl. eine Aufgabe hierzu, je nachdem, wie sie die Thematik verstanden haben.

Grammatiken vs. Automaten

Den Schülern wird vorgestellt, dass es Probleme gibt, die mit Automaten nicht eindeutig entschieden werden können, mit Grammatiken aber schon. Z.B. ein Klammerterm, bei dem überprüft werden soll, ob die Klammern richtig gesetzt wurden.

Grammatiken und Sprachen

Je nach Leistungsniveau und Interesse des Kurses soll hierauf näher eingegangen werden.