Einführung in die Informatik Teil XVII – Programmverifikation und logisch falsche Programme

 1. Die Aufgabe: Rechtecke mit Rand mit der Maus zeichnen

  2. Programmtest

      2.1  Untersuchung der Grenzfälle

  3. Programmverifikation und Struktogramme – ein Beispiel

  4. Programmverifikation allgemein

      4.1 Zum Begriff der Korrektheit

      4.2 Der Hoare-Kalkül

      4.3 Noch ein ausführliches Beispiel

      4.4  Programmverifikation in der Schule

      4.5 Aufgaben

Einführung in die Informatik Teil XVIII – Reguläre Sprachen

  1. Satzgliederungssprachen

  2. Die Backus-Naur-Form BNF

  3. Linksreguläre Sprachen

      3.1    Generative Grammatiken

      3.2    Analysierende Grammatiken

      3.3    Die Äquivalenz von erkennenden Automaten und linksregulären Grammatiken

      3.4    Beschränkungen regulärer Sprachen

  4. Aufgaben

  5. Projektvorschlag: Funktionsplotter

      5.1    Die Aufgabenstellung

      5.2    Die Sprache der rationalen Funktionsterme

      5.3    Eine Grammatik für rationale Funktionsterme

      5.4    Ein Parser für rationale Funktionsterme

      5.5    Ein Rechner für rationale Funktionsterme

      5.6    Ein Applet für den Funktionsplotter

      5.7    Aufgaben

Einführung in die Informatik Teil XIX – Kellerautomaten

  1. Kellerautomaten

      1.1    Die Definition von Kellerautomaten

      1.2    Beispiel: geschachtelte Klammern

      1.3    Die Simulation des Kellerautomaten mit SIMA

      1.4    Zur Bedeutung von Kellerautomaten für Programmiersprachen

  2. LOGO für Arme – Teil 2

      2.1    Änderungen an der Syntax

      2.2    Änderungen am Turtleparser

      2.3    Änderungen am Turtleinterpreter

      2.4    Aufgaben

Einführung in die Informatik Teil XX – Kontextfreie Sprachen

  1. Kontextfreie Sprachen

      1.1    Einordnung in den Unterricht

      1.2    Beispiel: Klammerstrukturen erzeugen

      1.3    Syntaxbäume

      1.4    Effiziente Syntaxanalyse

      1.5    Parsingtabellen

      1.6    Zur Äquivalenz von Kellerautomaten und kontextfreien Sprachen

      1.7    Aufgaben

  2. Projektvorschlag: Künstliche Pflanzen

      2.1    Lindenmeyer-Systeme

      2.2    Anforderungen an das System LISA

      2.3    Das Regelsystem

      2.4    Die Turtlegrafik

      2.5    Die Benutzeroberfläche

      2.6    Der Stapel

      2.7    Speichern und Laden in Textdateien

      2.8    Pflanzen zeichnen

      2.9    Beispiele

Einführung in die Informatik Teil XXI – Berechenbarkeits- und Entscheidbarkeitsprobleme

  1. Turingberechenbarkeit

      1.1    Berechenbarkeit

      1.2    Rekursive Berechenbarkeit

      1.3    Gekoppelte Turingmaschinen für rekursive Funktionen

               1.3.1     Gekoppelte Turingmaschinen

               1.3.2     Die Sprache GT für gekoppelte Turingmaschinen

               1.3.3     Gekoppelte Turingmaschinen für die elementaren Funktionen

               1.3.4     Rekursive Turingmaschinen

      1.4    Die universelle Turingmaschine

      1.5    Fleißige Biber und das Halteproblem

      1.6    Zur Unentscheidbarkeit des Halteproblems

      1.7    Aufgaben

  2. Projektvorschlag: GT – ein Simulator für gekoppelte Turingmaschinen

      2.1    Einordnung in den Unterricht

      2.2    GT – die Sprachdefinition

      2.3    Ein Scanner für GT

      2.5    Eine Grammatik für GT

      2.6    Ein Befehlslader für GT

      2.7    Ein GT-Interpreter

      2.8    Ein Arbeitsgang mit GT

      2.9    Aufgaben