Schwierigkeit des Problems

Bevor die Lernenden das Problem mittels DNA-Computing lösen, sollen sie erkennen, worin die Schwierigkeiten liegen. Dabei beschäftigen sie sich unter anderem mit einem ungerichteten Hamilton-Pfad- und einem ungerichteten Hamilton-Kreis-Problem.

Komplexere Aufgaben

Einzel- oder Gruppenarbeit

Die Schülerinnen und Schüler sollen intuitiv erfassen, dass ein Problem wie das des Geschäftsmannes Peter Müller bei höherer Komplexität durchaus recht schwierig zu bewältigen ist (es soll hier nicht das Thema NP-Vollständigkeit oder eine exakte Laufzeitanalyse behandelt werden). Dazu wird ein Aufgabenblatt mit weiteren Probleminstanzen verteilt, das die Lernenden in Einzel- oder Gruppenarbeit bearbeiten sollen.

Das Haus vom Nikolaus und Hamiltons Dedokaeder

Auf dem Arbeitsblatt werden zwei Probleme thematisiert. Das "Haus vom Nikolaus" ist vielen bekannt und dient zur Motivation. Dort wird das ungerichtete Hamilton-Pfad-Problem vorgestellt. Bei Hamiltons Dedokaeder beschäftigen sich die Schülerinnen und Schüler mit dem ungerichteten Hamilton-Kreis-Problem. Bei diesem Problem einen Hamilton-Zyklus zu finden, ist nach einigem Probieren durchaus machbar. Dabei kann die Software "Graphenspiele" zum Einsatz kommen.

Download

Ein Problem ohne Lösung

Um das Prinzip zu verdeutlichen, kommt auch eine komplexere Aufgabe zum Einsatz. Man präsentiert den Schülerinnen und Schülern eine komplizierte Grafik, die sie mit der Software "Graphenspiele" bearbeiten sollen. Ihre Aufgabe besteht darin, einen Hamilton-Zyklus (der im Unterricht nicht so genannt werden muss) zu finden. Die Überprüfung, ob der Graph einen Hamilton-Zyklus hat, gestaltet sich schwierig - denn es gibt keinen ;-). Die Lernenden müssen versuchen die Lösung selbst zu finden, können sich dabei aber auch vom Programm anleiten lassen. Nach spätestens zehn Minuten wird die Suche nach dem nicht vorhandenen Hamilton-Zyklus abgebrochen.

Frei nutzbares Material
Die von Lehrer-Online angebotenen Materialien können frei für den Unterricht genutzt und an die eigene Zielgruppe angepasst werden.