Direkt zur Hauptnavigation springen Direkt zum Inhalt springen Jump to sub navigation

Empfehlung zur Umsetzung des Vertiefungsgebietes "Theoretische Informatik"

Empfehlung zur Umsetzung des Vertiefungsgebietes "Theoretische Informatik"

Handreichungen zum Informatikunterricht SEK 2 

Vertiefungsgebiet Theoretische Informatik

Theoretische Informatik gehört zu den Kernthemen der Schulinformatik. Sie legt ein zeitbeständiges theoretisches Fundament zum Informatikunterricht und hat eine allgemeinbildende Wirkung (z. B. Erfassung prinzipieller Grenzen der Informationstechnik). Bei ihrer Behandlung in der Schule sollen die theoretischen Probleme aus Anwendungsproblemen heraus entstehen. Eine davon abgehobene Betrachtungsweise ist nicht intendiert. Damit wird z. B. ein Einstieg in die Problematik mit Hilfe von Automatenmodellen nahe gelegt. Ein anderer motivierender Einstieg kann über das Busy-Beaver-Problem und damit über Turing-Maschinen erfolgen. Angesichts der theoretischen Aspekte ergeben sich Querverbindungen zur Mathematik, die besonders im Leistungskurs Informatik oder Mathematik (z.B. Markow-Ketten) genutzt werden können.

Ergänzung

Es werden drei Themen vorgeschlagen, die sich leicht vernetzen lassen:

Wahlgebiet Theoretische Informatik

Vorschläge für Schwerpunktvorhaben:
  • Beschreibung von Systemen durch endliche Automaten
  • Turing-Maschinen
  • Typen und Grammatiken formaler Sprachen
FachinhalteKompetenzenVernetzungen
Endliche Automaten
  • Simulation von realen Automaten durch endliche Automaten (Transduktoren)
  • erkennende Automaten (Akzeptoren)
  • Zustandsgraphen, Zustandstabellen,
  • Simulation von Automaten durch eine geeignete Programmiersprache
  • Mit formalen Beschreibungsmethoden (Automat, Grammatik) umgehen können
  • Überblick über Einsatzbereiche realer Automaten gewinnen
  • Verstehen der Arbeitsweise von Automaten aus dem Alltag
  • Modellieren realer Automaten durch geeignete Darstellungs-formen (Tabellen, Zustandsgraphen, Programme...)
  • Erkennen, welche Probleme mit Automaten lösbar sind und welche nicht.
  • Automaten spielen im Alltag eine wichtige Rolle
  • Automatentheorie ist wichtig u.a. für Texterkennung und im Compilerbau
  • Zustandsgraphen werden in vielen Gebieten für die Beschreibung von Zustandsänderungen und die Klassifizierung von Zustandsmengen verwendet
  • Unterschied zwischen Determinismus und nichtdeterministischen Methoden
  • Weitere Vernetzungsmöglichkeiten:
    • formale Sprachen
    • Turing-Maschine
    • Registermaschine
    • andere Rechenmodelle
Formale Sprachen und Grammatiken
  • Syntax und Grammatiken natürlicher und formaler Sprachen
  • Begriffe: Terminalsymbol, Nichtterminalsymbol, Startsymbol, Produktionsregel, Wort, Satz
  • Synthese und Analyse
  • Syntaxdiagramme
  • Modellierung einfacher Sprachen
  • Parser für formale Sprachen
  • kontextfreie Sprachen
  • Backus-Naur-Formalismus (BNF)
  • Zusammenhang zwischen regulären Sprachen und endlichen Automaten, Kellerautomat
  • Compiler, Interpreter
  • Unterscheidung zwischen Syntax und Semantik
  • Beschreibung einfacher Grammatiken in geeigneter Form
  • Konstruieren formaler Sprachen
  • Verstehen der Funktionsweise eines Parsers
  • Gewinnen von Überblick über die grundsätzliche Arbeitsweise von Compilern und Interpretern
  • Ggf. Anknüpfung an das Thema "Endliche Automaten"
  • Anknüpfung an den Sprachunterricht (Linguistik)
  • Anwendung von Sprachen in unterschiedlichem Umfeld: Gerätekommunikation (Protokolle), Maschinensprache, Programmiersprachen,
  • mathematische Formelsprache, natürliche Sprachen
  • philosophische Aspekte:
      Roboter / Mensch;
      Maschine / Mensch
Turingmaschinen
  • Architektur und Arbeitsweise einer Turingmaschine
  • Turing-Programme (Algorithmen)
  • Beispiele wie a:=a+1;
  • Multiplikation a*b (a,b aus N),
  • Kopieren eines Wortes
  • Busy Beaver
  • Turing-Maschine mit Darstellungsformen: Turing-Befehle z.B. als 5-er Tupel (aktueller Zustand, gelesenes zeichen, Richtung der Bandbewegung, neu erreichter Zustand), Zustandsgraphen
  • Vergleich: Turing-Maschine mit endlichem Automat/mit Computer
  • Präzissierung des Algorithmenbegriffs, Berechenbarkeit Halteproblem
  • Verstehen der Grundlagen von Informatiksystemen
  • Spezielle Informatiksysteme (Modell-Turing-Maschine) anwenden können
  • Gestaltung von Informatiksystemen
  • Prinzipielle Grenzen von Informatiksystemen erfahren
  • Im www finden sich Demonstrationsprogramme. Es ist auch möglich, selbst im Unterricht Modelle zu erstellen, die beispielsweise in anderen Kursen nutzbar sind.
  • Das Busy-Beaver-Problem hat im WWW große Aufmerksamkeit gefunden. Es führt schnell auf Fragen der Berechenbarkeit und auf das Halteproblem.
  • Zustandsgraphen werden in vielen Bereichen zur Beschreibung von Zustandsveränderungen benutzt, u.a. in der Mathematik bei Markow-Ketten
  • Vernetzung von Turing-Maschine mit Automaten und Computern
  • Aufgreifen des Funktionsbegriffs aus der Informatik/Mathematik
mögliche Vertiefungen
  
  • Einige Themen können auch in vertiefter Form als Projektarbeit durchgeführt werden.

Redaktionell verantwortlich: Frank Oppermann