Forschung

Online-Probleme beschreiben eine besondere Klasse von Optimierungsproblemen, in denen Algorithmen Entscheidungen treffen müssen, ohne die gesamte Eingaben zu kennen. Beispiele sind Cache-Verwaltungsalgorithmen; diese sollen sicherstellen, dass zukünftig angefragte Daten zum Zeitpunkt ihrer Anfrage möglichst oft im Cache vorhanden sind.

Von einem theoretischen Standpunkt aus tappen diese Algorithmen also ein Stück weit im Dunklen. Es ist jedoch in vielen praktischen Szenarien unrealistisch, eine absolute Unkenntnis der Eingabe anzunehmen.

Das Modell der Advice-Komplexität untersucht, inwiefern Zusatzinformationen beim Berechnen einer Lösung hilfreich sein können. Besonders interessant sind in diesem Zusammehang untere Schranken und teils sehr überraschende Schwellenwertphänomene. So gibt es  beispielsweise Probleme, bei denen ein einziges Bit an Information hilft, die Lösungsqualität eines Online-Algorithmus erheblich zu verbessern, aber jedes weitere Bit keinerlei Hilfe darstellt, bis ein bestimmter nicht-konstanter Wert erreicht wird.

Im Zusammenhang mit vielen klassischen Optimierungsproblemen ist es realistisch anzunehmen, dass gewisse Eigenschaften einer zu berechnenden optimalen Lösung bereits bekannt sind. Betrachten Sie z.B. ein Verkehrsnetzwerk, in welchem eine bestimmte Struktur gesucht wird; beispielsweise ein Hamiltonkreis mit minimalen Kosten.

Ist eine solche Lösung gegeben und kommt es zu einer geringfügigen Änderung der Ausgangslage, beispielsweise des Netzwerks, stellt sich die Frage, ob eine neu zu berechnende Lösung auf der bereits bekannten Lösung aufbauen bzw. sich diese zu Nutze machen kann.

Konkret bedeutet dies, dass ein Graph und ein minimaler Hamiltonkreis bekannt sind; nun wird dem Graphen ein einzelner Knoten hinzugefügt und für den so entstandenen Graphen soll wiederum ein minimaler Hamiltonkreis berechnet werden. Interessanterweise ist dieses Problem, trotz der intuitiv sehr hilfreichen Zusatzinformation (der Lösung für einen sehr ähnlichen Graphen), wiederum NP-schwer, besitzt aber einen überraschend guten Approximationsalgorithmus.

Erfreulicherweise wird es immer seltener, dass Informatik mit dem Beherrschen von Anwendungssoftware gleichgesetzt wird. Vielmehr wird der allgemeinbildende Charakter des Informatikunterrichts betont; im Zentrum steht hier das «informatische Denken» (englisch «computational thinking»), welches grob als Beherrschung verschiedener Problemlösestrategien verstanden wird; beispielsweise Abstraktionsvermögen, sinnvolle Informationsdarstellung, Problemzerlegung etc.

Wie aber fördert man diese Kompetenzen und wie misst man ihren Erwerb? Gerade im Bereich der Messinstrumente gab es in den letzten Jahren einigen Fortschritt; jedoch ist die Entwicklung noch lange nicht abgeschlossen. Nun gilt es, den Informatikunterricht so zu gestalten, dass Problemlösekompetenzen aufgebaut werden. Dies geht nur, indem Unterrichtseinheiten entwickelt und im Klassenzimmer getestet werden.

Offensichtlich ist diese angewandte Forschung eng mit dem Erstellen von Unterrichtseinheiten und entsprechenden Werkzeugen verknüpft.

Gerade in unteren Schulklassen müssen Konzepte der Informatik teils mit einer starken didaktischen Reduktion vorgestellt werden. Dazu werden in der Regel Metaphern verwendet, die von gewissen Details abstrahieren.

Viele dieser Metaphern, beispielsweise «Eine Variable beim Programmieren ist wie eine Schublade, in die man Dinge legen kann», können bei den Schülerinnen und Schülern jedoch zu Fehlvorstellungen führen, die sich unter Umständen erst später bemerkbar machen und dann, bereits gefestigt, zu Fehlern führen. Die Gefahr bestimmter Fehlervorstellungen und möglicher Manifestierungen sollten von der Lehrperson erkannt werden, damit sie diese thematisieren kann.

Um mögliche Fehlvorstellungen zu entdecken, betrachten wir die Lösungen von Schülerinnen und Schülern und untersuchen, was konkrete Gründe für falsche Antworten sein könnten.