Sachanalyse

Sachanalyse

Theorie
Die Sachanalyse dient der Auseinandersetzung mit dem fachlichen Inhalt, der dem Unterricht zu Grunde liegt. Das übergeordnete Themengebiet wird beleuchtet und es werden Verknüpfungen zu anderen Bereichen der Informatik hergestellt. Der Inhalt beschränkt sich deshalb nicht allein auf das Thema der Stunde. (vgl. Standop et al., 2015, S. 131)

Fachdidaktische Überlegungen sollten nicht mit in die Sachanalyse einfließen. Weiterhin sollte verzichtet werden auf eine detaillierte Beschreibung von Einzelheiten eines Themas (z. B. die Syntax einer for-Schleife beschreiben).

Für herangehende Lehrkräfte ist es wichtig, das behandelte Thema sehr gut zu beherrschen. Das Wissen der Lehrkraft sollte über die für den Unterricht notwendigen Konzepte hinausgehen; beispielsweise für den Fall, dass Schüler*innen weiterführende Fragen stellen. Zudem muss sich ein Überblick über das gesamte Themengebiet verschafft werden, um die einzelnen Aspekte auch verknüpfen zu können. Dies ist relevant, wenn die Lehrkraft den Zusammenhang einzelner Themen für die Schüler*innen darlegen muss. Für die Schüler*innen ist es oft besonders wichtig, diesen Zusammenhang zu erkennen und zu verstehen, wenn es sich um abstrakte Themen handelt und eine eigenständige Strukturierung des Inhalts nicht von den Schüler*innen erwartet werden kann. (vgl. Klüver et al., 2012, S.12 ff.)

Beim Verfassen der Sachanalyse sollte mindestens auf folgende Aspekte eingegangen werden:

Struktur des Inhalts, Gliederung des Themengebiets und sachlogische Reihenfolge
Facetten, die das Thema aufweist
Zusammenhänge des Themas mit anderen Bereichen innerhalb der Informatik und außerhalb (Interdisziplinarität)
Bedeutung des Themengebiets innerhalb des Faches, Beurteilung der Relevanz (sehr bzw. wenig relevant)
Beurteilung der Komplexität des Themas und Benennung von Schwierigkeiten

Beispiel
Eine Sachanalyse zum Thema Berechenbarkeit:

Eine Funktion f : M → ℕ wird berechenbar genannt, wenn es einen Algorithmus (bzw. ein Programm) gibt, der für jeden Eingabewert m ∈ M, für den f(m) definiert ist, nach endlich vielen Schritten anhält und das Ergebnis f(m) liefert. In den Fällen, in denen f(m) nicht definiert ist, soll der Algorithmus nicht terminieren. Ob eine Funktion berechenbar ist, hängt also zunächst einmal vom gewählten Berechnungsmodell ab.

Der erste, der sich mit dem Thema Berechenbarkeit beschäftigte, war der Mathematiker Alan Turing. Er beschrieb berechenbare Funktionen als diejenigen Funktionen, die von einer Turing-Maschine berechnet werden können. Es gibt jedoch noch andere Konzepte, wie etwa LOOP-Programme oder WHILE-Programme, um Berechenbarkeit zu definieren. Es ist jedoch gezeigt worden, dass all diese Konzepte zueinander äquivalent sind. Nach der Churchschen These ist diese Definition der Berechenbarkeit ausreichend.

Tatsächlich ist bisher kein Berechnungsmodell bekannt, welches mächtiger ist als das Modell der Turing-Maschinen. Die Turing-Maschine wurde somit zur Grundlage der Theorie der Berechenbarkeit. Ohne Weiteres lassen sich sofort berechenbare Funktionen aufzählen.

So ist zum Beispiel die Funktion f : ℕ → ℕ, n → n + 1 berechenbar, genauso wie die überall undefinierte Funktion. Weitere einfache Beispiele sind leicht zu finden.

Nun liegt es nahe zu vermuten, dass jede Funktion, die man präzise definieren kann, auch berechenbar ist. Überraschenderweise ist dies nicht der Fall, es gibt tatsächlich nichtberechenbare Funktionen:

Ein abstraktes Argument zeigt, dass die Menge an Programmen abzählbar ist, wohingegen es überabzählbar viele Funktionen gibt. Somit muss es Funktionen geben, die nicht berechenbar sind. Dadurch ist bereits bewiesen, dass algorithmisch arbeitende Computer nicht jedes Problem lösen können. Erwähnt werden sollte dabei, dass diese Erkenntnis aus einer Zeit stammt, in der es noch keine Computer gab.

Der Begriff der Entscheidbarkeit ist eng mit dem Begriff der Berechenbarkeit verbunden. Wir nennen eine Teilmenge M einer abzählbaren Menge entscheidbar, wenn ihre charakteristische Funktion ?M : M → {0,1} berechenbar ist.

Wir nennen ein Problem entscheidbar, wenn es einen Algorithmus gibt, der in endlich vielen Schritten klärt, ob es für das gegebene Problem eine Lösung gibt oder nicht.

Zwei Unterthemenkomplexe der Berechenbarkeitstheorie sind dabei von besonderem Interesse:

Zunächst gehen wir noch einmal auf die Frage nach den Grenzen der Berechenbarkeit ein. Wie bereits erwähnt wissen wir, dass es Funktionen gibt, die nicht berechenbar sind. Noch ist aber nicht klar, ob diese Funktionen nicht nur von theoretischem Interesse sind. Ein wichtiges Resultat der theoretischen Informatik zeigt aber, dass es relevante Probleme gibt, deren charakteristischen Funktionen nicht berechenbar sind:

Alan Turing bewies, dass das Halteproblem nicht entscheidbar ist.

Auch das Postsche Korrespondenzproblem (PKP) ist nicht entscheidbar. Ein Problemfall des PKP ist eine endliche Menge an Wortpaaren über einem endlichen Alphabet. Eine Lösung zu einem Problemfall ist eine nichtleere, endliche Folge von Nummern für Wortpaare, so dass die ersten Komponenten der Wortpaare zusammengesetzt das gleiche Wort ergeben wie die zweiten Komponenten der Wortpaare.

Die Eigenschaft von Problemfällen, eine Lösung zu besitzen, ist unentscheidbar.

Nun gibt es verschiedene Möglichkeiten, weitere Probleme als unentscheidbar zu klassifizieren. Besonders hervorzuheben ist hier die Methode der Reduktion, welche von Andreas Schwill als fundamentale Idee der Informatik im Bereich der Algorithmisierung genannt wird.

Die Idee der Reduktionsmethode ist es, für ein gegebenes Problem ein bereits bekanntes Problem zu finden, welches mindestens so schwer, höchstens so schwer oder im wesentlichen gleich schwer ist, um nun durch die Kenntnis der (Un)Entscheidbarkeit des bekannten Problems auf die (Un)Entscheidbarkeit des gegebenen Problems zu schließen.

Tatsächlich kann man für viele andere Probleme zeigen, dass sie nicht entscheidbar sind, indem man sie auf das Halteproblem zurückführt:

Ist g eine Funktion, deren Berechenbarkeit die Berechenbarkeit einer Funktion f impliziert und bereits bekannt ist, dass f nicht berechenbar ist, so kann auch g nicht berechenbar sein. Mittels dieses Verfahrens lässt sich zeigen, dass aus der Unentscheidbarkeit des Halteproblems folgt, dass auch das PKP nicht entscheidbar ist. Hieraus wiederum lässt sich ableiten, dass das Schnittproblem kontextfreier Grammatiken nicht entscheidbar ist.

Der zweite wichtige Themenkomplex beschäftigt sich mit der Untersuchung der Klasse der berechenbaren Funktionen. Ein wichtiges Resultat aus diesem Bereich der Berechenbarkeitstheorie ist der Satz von Rice.

Dieser besagt, dass grundsätzlich alle Fragestellungen, die das funktionale Verhalten von Algorithmen betreffen, unentscheidbar sind. Wollen wir zum Beispiel die Menge aller berechenbaren Funktionen bestimmen, die für jede Eingabe mindestens 30 Sekunden laufen, so lässt sich diese Menge nicht mittels eines Programms bestimmen.

Testaufgaben
Mit welchen der folgenden Fragen beschäftigt sich die Sachanalyse genauer?

Welche fachlichen Vertiefungen sind zu bedenken?
Worin liegt die Bedeutung des Themas für die Zukunft der S*S?
Welche Facetten weist das Thema auf?
Gibt es Verbindungen zu anderen Fachwissenschaften?
Welche Bedeutung hat das Thema innerhalb des Faches?
Welche fachlichen Schwerpunkte können in dieser Lerngruppe gesetzt werden?
Überprüfen
Ziehen Sie die Wörter in die richtigen Felder!

Wesentlich ist beim Verfassen der Sachanalyse, dass und des Themas herausgearbeitet werden. Es sollten möglichst viele zu anderen innerhalb und außerhalb der Informatik aufgezeigt werden.
Weiterhin sollte die Bedeutung des Themas für , nicht aber für , herausgearbeitet werden. Zuletzt sollte auch des Themas beurteilt werden.
Überprüfen

Übungsaufgabe
Aufgabe:

Verfassen Sie den Entwurf einer Sachanalyse. Sie können Ihre Ideen in Stichpunkten notieren, sollten aber voll ausformulierte Sätze schreiben.
Die Sachanalyse soll ebenfalls wie die Bedingungsanalyse zum Thema Schleifen verfasst werden.

Auf der folgenden Folie finden Sie einen ausformulierten Lösungsvorschlag, dieser ist jedoch nur eine mögliche Lösung und dient lediglich zur Orientierung.

Lösungsvorschlag
In allen Disziplinen der Informatik ist das Konzept der Iteration von enormer Bedeutung. Die stetige Wiederholung eines Vorgangs ist ein aus dem Alltag entlehntes Vorgehen. Es ist also nicht verwunderlich, dass Iteration sowohl in der Programmierung als auch in der theoretischen Informatik die Grundlage für viele komplexere Konzepte bildet.

Iteration lässt sich innerhalb der Programmierung in den Bereich der Kontrollstrukturen einordnen. Neben Verzweigungen, wie der Bedingten Anweisung (if-Anweisung), sind Schleifen ein häufig verwendetes Werkzeug, um den Ablauf eines Programms zu steuern. Grundsätzlich lassen sich Schleifen in drei Schleifentypen unterteilen, welche sich in ihrem Aufbau unterscheiden:

Erstens: Kopf- und Fußgesteuerte Schleifen wiederholen einen Anweisungsblock solange eine Bedingung erfüllt ist (while-, do-while-Schleife) oder bis eine Bedingung erfüllt ist (repeat-until-Schleife). Kopfgesteuerte Schleifen prüfen die Bedingung vor der Ausführung des Anweisungsblocks, Fußgesteuerte Schleifen nach der Ausführung. Die Bedingung muss im Anweisungsblock verändert werden, damit keine Endlosschleife auftritt.
Zweitens: Zählschleifen (for-Schleifen) arbeiten wie Schleifen des Typs 1, die Änderung der Bedingung wird jedoch im Kopf der Schleife vorgenommen. Meist werden Zählschleifen dafür verwendet, eine feste Anzahl an Wiederholungen auszuführen, die Bedingung kann jedoch auch im Anweisungsblock verändert werden. Anwendungen finden sich also hauptsächlich im Durchlaufen von Arrays oder Listen.
Drittens: Mengenschleifen können als Zählschleifen aufgefasst werden, wobei die Anzahl an Wiederholungen der Anzahl an Elementen einer Eingabemenge entspricht.
Offensichtlich ist die Verwendung von Schleifen zur wiederholten Ausführung desselben Programmcodes. Darüber hinaus ermöglichen Schleifen eine variable Anzahl an Wiederholungen, wenn z.B. vor der Ausführung des Programms noch nicht klar ist, wie oft etwas wiederholt werden soll. Sie erlauben also eine Steuerung des Programmablaufs parallel zur Laufzeit. Ein einfaches Beispiel dafür ist die Programmierung eines „Menüs”, bei welchem der Nutzer die Wahl zwischen verschiedenen Auswahlmöglichkeiten hat und immer wieder zurück in das Menü gelangt, bis er das Programm beendet.

Simple strukturierte Datentypen wie Felder (Arrays) oder Zeichenketten (Strings) werden im Regelfall durch Schleifen angesteuert. Aber auch komplexere Datenstrukturen wie Listen können mit Schleifen einfach verwendet werden. Dementsprechend benötigen alle Programme, die in einer Art Daten in Arrays oder Listen abspeichern, Schleifen, um die einzelnen Elemente anzusteuern.

Vorangegangen ist eine Unterscheidung der Schleifen in 3 Typen. Jedoch lässt sich beispielsweise eine for-Schleife immer auch als while-Schleifen umsetzen. Beide Typen bieten Vorteile auf Grund ihres Aufbaus und werden dementsprechend für unterschiedliche Anwendungen genutzt.

Während die while-Schleife auf Grund ihres hohen Alltagsbezugs sehr intuitiv genutzt werden kann, ist die for-Schleife einfacher zu programmieren, da weniger Überlegung in die Schleifenbedingung investiert werden muss. Bei der Verwendung von while-Schleifen besteht zudem immer die Gefahr einer Endlosschleife. Es ist bei der Programmierung also immer abzuwägen, welcher Schleifentyp für ein gegebenes Problem nun am sinnvollsten ist.

Weiterhin ist die Betrachtung von Schleifen für die Laufzeitanalyse von Bedeutung, damit die Anzahl an Elementaroperationen ermittelt werden kann.

Neben der Anwendung in der Programmierung spielen Schleifen auch in der theoretischen Informatik eine bedeutende Rolle. Im Rahmen der Berechenbarkeitstheorie definiert man Klassen von Funktionen, die durch eine möglichst geringen Anzahl an Grundfunktionen beschrieben wird. LOOP-Programme sind ein Beispiel für eine solche Klasse von Funktionen:

Ein LOOP-Programm wird aus Befehlen eines definierten Befehlssatzes aufgebaut, dieser besteht aus Wertezuweisungen, der Addition und Subtraktion von 1 sowie der namensgebenden Anweisung LOOP (Die LOOP-Schleife wird sooft durchlaufen, wie der Inhalt der Schleifenvariable vor dem ersten Durchlauf angibt. Der Variablenwert kann im Anweisungsblock verändert werden, dies hat jedoch keinen Einfluss auf die Anzahl an Wiederholungen). Mit Hilfe dieser Grundfunktionen können neue Funktionen der LOOP-Klasse definiert werden. Lässt sich ein Problem mit einem LOOP-Programm lösen, bezeichnet man es als LOOP-berechenbar. Mit diesem vergleichsweise geringen Befehlssatz können bereits viele Funktionen umgesetzt werden, beispielsweise die arithmetischem Grundrechenarten, das Potenzieren, Logarithmieren oder eine bedingte Anweisung (if-Anweisung).

Auf Grund ihrer Definition sind alle LOOP-Programme totale Funktionen, sprich sie terminieren für jede Eingabe. WHILE-Programme hingegen bilden eine Klasse von Funktionen, die nicht zwangsweise total sind. Sie erweitern den Befehlssatz der LOOP-Programme um die WHILE-Schleife. Im Gegensatz zur LOOP-Schleife kann die Schleifenvariable nun im Anweisungsblock verändert werden. Mit Hilfe der WHILE-Schleife lassen sich mehr Funktionen realisieren. Die Menge der WHILE-Programme ist also echt größer als die Menge der LOOP-Programme. Weiterhin lässt sich beweisen, dass alle WHILE-berechenbaren Funktionen auch durch eine Turingmaschine realisiert werden können und andersherum.

Neben LOOP-Programmen lässt sich die Klasse der primitiv-rekursiven Funktionen definieren, welche aus drei Grundfunktionen besteht. Mit Hilfe des Induktions-Rekursionsschemas lassen sich aus diesen Grundfunktionen, wie auch bei LOOP-Programmen, weitere Funktionen bilden. Es lässt sich beweisen, dass die Klasse der LOOP-Programme identisch mit der der primitiv-rekursiven Funktionen ist. Jede LOOP-berechenbare Funktion lässt sich also auch durch eine primitiv-rekursive Funktion berechnen und andersherum.

Diese Erkenntnis hat auch eine praktische Bedeutung in der Programmierung: Jedes durch Iteration lösbare Problem lässt sich auch durch Rekursion lösen.

Auch in anderen Fachbereichen findet Iteration breite Anwendung: In der numerischen Mathematik wird Iteration bei Näherungsverfahren verwendet (z.B.: Nullstellenbestimmung). In der Chemie lassen sich Versuchsverfahren iterativ beschreiben, beispielsweise die Titration (Es wird solange ein Tropfen der Maßlösung in die Probelösung gegeben, bis eine gewünschte chemische Reaktion eintritt). In der Physik wiederholt man Messverfahren mehrmals, um statistische Fehler zu vermeiden. Die Linguistik bildet einen speziellen Fall: hier bezeichnet man als Iteration die mehrmalige Aneinanderreihung von Silben (z.B. Urururgroßvater).

Iteration lässt sich auf jedem intellektuellen Niveau aufzeigen und vermitteln: Schleifen werden bereits für sehr simple Funktionen, wie beispielsweise die Berechnung der Quersumme einer Zahl oder die sequentielle Suche benötigt. Kompliziertere Algorithmen, z.B. Sortieralgorithmen wie BubbleSort, SelectionSort oder InsertionSort, sind ohne Schleifen nicht realisierbar. Aber auch komplexe Verfahren, wie der Ameisenalgorithmus, basieren auf Iteration.

Literatur
Klüver, Christina; Klüver, Jürgen (2012): Lehren, Lernen und Fachdidaktik: Theorie, Praxis und Forschungsergebnisse am Beispiel der Informatik. Wiesbaden: Vieweg+Teubner.

Standop, Jutta; Jürgens, Eiko (2015): Unterricht planen, gestalten und evaluieren. Bad Heilbrunn: Julius Klinkhardt.