Empfehlung zur Umsetzung

Vertiefungsgebiet funktionale Programmierung

Funktionale Programmiersprachen lassen etwas von der Eleganz, Klarheit und Präzision der Mathematik in die Welt der Programmierung einfließen. Im Mittelpunkt steht das mathematische Konzept von Funktionen und Rekursion. Innovative Konzepte, wie Musteranpassung, algebraische Datentypen, Funktionen höherer Ordnung und Polymorphie, machen funktionale Programme elegant und flexibel; sie eignen sich deshalb besonders gut zur Spezifikation.

Die funktionale Programmierung beschäftigt sich nicht mit der Abbildung eines Problems auf den sequentiellen Ablauf eines Programms. Vielmehr steht die Problemlösung (der Algorithmus) im Mittelpunkt (deklarative Programmierung). Dies führt zu einem Programmierstil, der sich grundlegend vom imperativen Programmieren unterscheidet. Die Implementierungen sind in fast allen Fällen kurz und übersichtlich.

Durch die Verwendung einer funktionalen Programmiersprache lassen sich viele zentrale Inhalte des Informatik-Unterrichts an der Schule sehr zielgerichtet thematisieren. Gleichzeitig erfordern diese Sprachen eine bedachte und wohlüberlegte Arbeitsweise, die zur Herausbildung eines sauberen Programmierstils beitragen kann. In Lerngruppen mit heterogenen Vorkenntnissen hat sich die frühzeitige Einführung einer "neuen" Programmiersprache als förderlich erwiesen.

Im Grundkurs bietet sich das Wahlgebiet bei der Einführung der Rekursion an. Hier kann man an den funktionalen Leitgedanken des Mathematikunterrichts anknüpfen und den Funktionsbegriff zur Beschreibung von Algorithmen erweitern. Die Kenntnis von Rekursion und Listen ist bei der späteren imperativen Behandlung hilfreich.

Im Leistungskurs können funktionale Sprachen frühzeitig eingeführt und dann unterrichtsbegleitend zur Spezifikation eingesetzt werden. Insbesondere für die Wahlgebiete Theoretische Informatik und Kryptologie bieten sich hier interessante Aspekte an, die bei einem späteren Studium nützlich sind (Programmiersprachen, reguläre Ausdrücke, Compiler, Algebraische Spezifikation, Techniken zur Entwicklung korrekter Software usw.).

WorkShop Funktionale Programmierung am Informatiktag 2019

Annette Machmer hat freundlicherweise ihr Material zur Verfügung gestellt

Funktionale Programmierung
Vorschläge für Schwerpunktvorhaben: Grundlegende Sprachelemente funktionaler Sprachen Auswertung durch Reduktion Wiederholung durch Rekursion Listen und Bäume als rekursive Datenstrukturen Polymorphie und Funktionskomposition Vergleich von funktionalen / imperativen Paradigmen
Fachinhalte	Kompetenzen	Vernetzungen
Funktionen als Programme
Arbeitsumgebung funktionaler Sprachen (Interpreter) Definition und Anwendung einfacher Funktionen Typkonzept funktionaler Sprachen Typableitung einer Funktion, Signaturen	Vertraut werden mit den Grundlagen des funktionalen Sprachparadigmas Lösungen für einfache Probleme entwerfen und prüfen Den Typ einfacher Funktionen ableiten und manuelle Auswertung vornehmen können	Aufgreifen des Funktionsbegriffs aus der Mathematik Funktionen mit mehreren Variablen als Bausteine z.B. zur Formelberechnung (CAS) Funktionale Zusammenänge in anderen Unterrichtsfächern
manuelle Auswertung durch Reduktion von Funktionstermen Funktionen mit mehreren Variablen Fallunterscheidungen; Musteranpassung lokale Definitionen (aus Gründen der Effizienz und der besseren Übersicht)	Typische Besonderheiten der funktionalen Programmierung erfassen und beurteilen	Klare Trennung zwischen (beweisbar korrekten) Berechnungen und Interaktionen, die ggf. Seiteneffekte aufweisen könnten
Rekursion
rekursive Funktionen und deren Auswertung endrekursive Funktionen und Iteration Akkumulatoren Beispiele für rekursive Algorithmen (Türme von Hanoi, Quicksort, Euklid, Linienalgorithmus,...)	Rekursive Algorithmen entwickeln und prüfen Die Rekursion als Möglichkeit für Wiederholungsanweisungen anwenden können Rekursive und iterative Problemlösungen untersuchen und bewerten, auch unter dem Gesichtspunkt der Effizienz	Vertiefung des grundlegenden Begriffes der Rekursion in der Mathematik (Wurzelberechnung, Folgen, Induktion), Chaostheorie Rekursion und vollständige Induktion (Mathematik) Rekursionen als wesentlicher Bestandteil einiger Entwurfsstrategien (z.B. Teile und Herrsche) große Bedeutung in der theoretischen Informatik (Compilerbau) Vertiefung der Komplexitätstheorie
Rekursive Datenstrukturen
Die Liste als rekursive, polymorphe Datenstruktur Arbeiten mit Listenfunktionen (traversieren, suchen, sortieren, einfügen, ...) Spezifikation von Stack, Queue Binärbäume als algebraische Datentypen mit Zugriffsfunktionen mögliche Erweiterungen: Operatorbäume zur Termberechnung, Huffman-Baum zur Datenkomprimierung, Vielwegbäume (Filesystem)	Typische Datenstrukturen handhaben Datenstrukturen entwickeln und auswählen Die Beziehung zwischen Algorithmus und Datenstruktur analysieren Abstraktion und Modularisierung beurteilen	Verwendung der Datenstrukturen z.B. im Betriebssystem und in Anwendungsprogrammen Modularisierung und Abstraktion bei der Softwareentwicklung Polymorphie in imperativen Programmiersprachen
Funktionen höherer Ordnung
Funktionen, die Funktionen als Parameter verarbeiten (map, filter, fold, ...) Funktionskomposition	Den Funktionsbegriff vertiefen Modularisierung durch Komposition von Funktionen beherrschen	Operatoren in der Mathematik, z.B. Differential- und Integraloperatoren Verkettung von Funktionen in der Mathematik
Vertiefung und Projektarbeit
Mögliche Vertiefungen:... Backtracking Faltungsfunktionen Korrektheit von Programmen Interaktion durch Monaden Mögliche Projektthemen: Rekursions-grafiken (z.B. mit Turtlegrafik) Kryptologie Huffman-Kodierung Simulation von Automaten	Grundlagen des Softwareentwurfs reflektieren Korrektheit informatischer Problemlösungen beurteilen	Funktionale Sprachen als Spezifikationssprache Korrektheitsüberlegungen beruhen auf dem Prinzip der vollständigen Induktion. (Mathematik)