Kurs:Fachdidaktik Informatik/Problemlösen

Problemlösen

Das Problem mit den Problemen

Die folgende Ausführung befasst sich mit dem Problemlösen aus pädagogisch-psychologischer Perspektive und gibt einen ausgewählten Überblick zu den verschiedenen Gegenstandsbereichen, die bei der Auseinandersetzung mit diesem Themenkomplex auftreten. Da das Feld des Problemlösens vielschichtige Ansatzpunkte aufweist, sollen die wichtigsten Fachtermini im Folgenden erläutert werden. Anschließend wird das Problemlösen im informatikdidaktischen Bereich an Hand von Beispielen illustriert.

Problem und Aufgabe werden im heutigen Sprachgebrauch als inflationäre Worthülsen genutzt, die oft synonym verwendet werden und keine klare Abgrenzung voneinander aufweisen. Für die folgende Ausarbeitung ist es jedoch wichtig, diese beiden Wörter zu definieren und die Worthülsen mit einem den Ausdrücken sinngemäßen Inhalt zu füllen. Gudjons (2008) bezeichnet ein Problem und eine (Lern-)Aufgabe aus pädagogischer Perspektive als zwei differierende Sachverhalte, jedoch können beide Typen in drei Bestandteile zerlegt werden:

1. Ausgangszustand

2. Hindernis

3. Endzustand

Bei einer Aufgabe stehen dem Lernenden per Definition das entsprechende Vorwissen und die notwendigen Operatoren zur Verfügung, um die Aufgabe zu lösen. Bei einem Problem ist dem Lernenden hingegen das Verfahren, das zur Lösung führt, nicht bekannt. Somit ist ein Problem eine schwierige Aufgabe oder eine schwer zu beantwortende Frage. Gudjons verweist darauf, dass es beim Problemlöseverfahren selbst fünf Strategien gibt, nach denen die Herangehensweise strukturiert werden kann. Diese Strategien sind:

1. Versuch und Irrtum

2. Umstrukturieren

3. Anwenden von Strategien

4. Systemdenken

5. Kreativität

Zur Visualisierung der geschilderten Unterschiede zwischen Problem und Aufgabe kann nachfolgende Grafik herangezogen werden.

Datei:Aufgabe und Problem.JPG

Diese strikte Trennung findet in der Psychologie nicht statt. So versteht Seel (2000) unter einem analytischen problemlösenden Denken ein Handeln, bei dem der Problemlöser den Schritt vom Ist-Zustand in den angestrebten Soll-Zustand auf Grund der ihm bekannten und vorhandenen Kenntnisse durchführen kann, indem er sie nur noch auf die spezielle Charakteristik des Problems übertragen muss. Somit entspricht das analytische problemlösende Denken Seels der Definition einer Aufgabe nach Gudjons. Das unter Gudjons definierte Problem kann als Äquivalent der produktiv problemlösenden Variante nach Seel angesehen werden. Hier ist dem Proband das Lösungsprinzip noch nicht bekannt und er muss sich dieses erst erarbeiten.

Nach Anderson (2000) zeichnet sich ein Problem durch spezifische Charakteristika aus. Zum einen muss das Verhalten des Probanden zielgerichtet und eindeutig auf eine Endabsicht fokussiert sein. Zum anderen muss das Problem in Teilprobleme zerlegt werden und es muss zu einer Anwendung von Operatoren (Handlungsketten) kommen, die den aktuellen Problemzustand in einen neuen überführen. Operatoren können durch mindestens drei verschiedene Formen in das Repertoire des Problemlösens aufgenommen werden. Die erste Variante ist das Entdecken neuer Operatoren. Ein Kind kann entdecken, dass es durch Wutanfälle besonders viel Aufmerksamkeit von seiner Umwelt erhält und wird diesen Operator in den Verhaltensfundus übernehmen. Eine zweite Variante ist die Instruktion. In diesem Fall wird dem Probanden das Handeln durch exakte Vorgaben übermittelt. Ein Beispiel ist das alleinige Erlernen der Hochsprungtechnik des Fosbury-Flop durch verbale Instruktionen. Die dritte Variante ist das Nachahmen der Handlung einer anderen Person oder der Transfer von einem Sachverhalt auf einen anderen. In diesem Fall liegt ein Analogielernen vor. Als Beispiel verweist Anderson auf den Verhaltensforscher Köhler (1917), der mit Affen experimentiert hat. Folgendes Szenario zählt er zum Analogielernen: Ein Affe war in der Lage sich Futter mit Hilfe eines Stockes außerhalb des Geheges zu beschaffen. Anschließend wurde der Stock gegen zwei Stockhälften getauscht, die man zusammenstecken konnte. Dem Affen gelang es, nach erfolglosem Greifen der Nahrung mit einer Stockhälfte, nach einer Nachdenkphase die Hälften ineinander zustecken und so sein Futter zu erreichen. Nach Anderson erfüllt dieses Handeln alle drei Voraussetzungskomponenten (Zielgerichtetheit, Zerlegung in Teilprobleme, Anwendung von Handlungsketten), die ein Problem ausmachen. Im Idealfall kann der Problemlöser das Problem so weit in einzelne Teile zerlegen, dass er diese und das Gesamtproblem anschließend lösen kann.

Eine pauschale Aussage darüber, wann es sich um eine Aufgabe und wann um ein Problem handelt, kann nicht getroffen werden, da dies vom individuellen Kenntnisstand des Lernenden abhängig ist. Sowohl das individuelle deklarative als auch das prozedurale Wissen und deren Vernetzung untereinander sind hier von essentieller Bedeutung.

Offene und geschlossene Probleme

Neben der Trennung und Beschreibung der beiden Begrifflichkeiten von Aufgabe und Problem lassen sich noch andere hilfreiche Dimensionen festhalten, die zu einer Klassifikation eines Problems beitragen. Man kann des Weiteren den Grad der Offenheit und Geschlossenheit eines Problems als Differenzierungskriterium heranziehen. Ein Ingenieur, der eine Brücke planen soll, bekommt genaue Vorgaben über Länge, Breite, Mindesttragfähigkeit und Anzahl der Brückenpfeiler. Hier kann man von einem geschlossenen Problem sprechen. Ein Komponist hingegen, der eine Sonate komponieren soll, von der er zu Beginn der Arbeit nur eine vage Vorstellung hat, wird vor ein offenes Problem gestellt.

Das Hindernis

Auch das Hindernis, das dem Problemlöser im Wege steht, um an sein Ziel zu gelangen, wird nach Seel in drei weitere Typen eingeteilt: Interpolationshindernisse, Synthesehindernis und dialektische Barrieren. Bei einer Interpolationsbarriere sind der Ausgangszustand und der Zielzustand bekannt. Das Problem besteht darin, dass man eine effektive Anordnung der erforderlichen Transformationen finden muss, um an sein Ziel zu gelangen. Die Barriere kann mit der korrekten Anwendung und Kombination der bekannten Operationen überwunden werden. Ein Beispiel für eine Interpolationsbarriere wäre eine Zugreise von Heidelberg nach Sylt. Bei der Synthesebarriere bemerkt der Proband, dass die zur Verfügung stehenden Operationen nicht ausreichend sind, um die Barriere zu überwinden, obwohl der Ausgangszustand und der Zielzustand klar definiert sind. Ein Beispiel hierfür wäre die Aufgabe aus Stroh Gold herzustellen. Das Problem besteht darin, dass es diese Operation bzw. ein Inventar mit einer Kombination an Operationen nicht gibt, das dieses Problem lösen kann. Die Hauptaufgabe bei dieser Art von Barriere besteht in der Synthese eines Inventars an Operationen, die, wenn möglich, zum Ziel führen. Die dialektische Barriere stellt den Problemlöser vor eine Ausgangssituation, die ihm bekannt ist und eine noch nicht genau im Detail festgelegte Zielsituation. Er verfügt über globale Kriterien und Operationen, die sich jedoch erst in einem Problemlöseprozess vollständig herausbilden müssen. Das Konzipieren und Formulieren einer Abschlussarbeit am Ende eines Studiums stellt eine dialektische Barriere dar. Der Verfasser wird einen ersten Entwurf anfertigen und beim Arbeiten mit dem Datenmaterial bzw. der Literatur immer wieder Änderungen vornehmen. Der Problemlöser durchläuft eine Art Schleife, in der er Korrekturen durchführt, bis diese dem Verfasser selbst bzw. dem Korrektor der Arbeit genügen.

Gestalttheorie und Kognitionspsychologie

Die Gestalttheorie stammt aus der ersten Hälfe des 20. Jahrhunderts (Wertheimer 1880-1943 und Duncker 1903-1940) und befasst sich mit der Frage, wie sich aus einer Problemsituation die Lösung ergibt und welche Wege sich für die Lösung eines Problems aufzeigen. Das Vorgehen beim Bewältigen solcher Lernarrangements wird in dieser Theorie als produktives Denken bezeichnet. Ein Ergebnis dieser Forschung war unter anderem die Methodik des „lauten Denkens“. Nach Seel ist eine zentrale Erkenntnis der Gestalttheorie die Tatsache, dass Problemlösungen durch eine Umstrukturierung des vorliegenden Datenmaterials zu Stande kommen und nicht kleinschrittig, sondern in einer Art Aha-Erlebnis (Archimedes) stattfinden. Neben diesem Fakt spielen die Vorwärtssuche (die Lösung wird aus der Perspektive des Ist-Zustandes heraus erarbeitet) und die Rückwärtssuche (die Lösung wird aus dem Soll-Zustand heraus entwickelt) sowie deren Kombination beim Problemlösen eine weitere wichtige Rolle.

Anderson dagegen verweist darauf, dass der Aha-Effekt nur ein weit verbreiteter Irrglaube ist. Er erläutert, dass solche Probleme als Einsichtsprobleme zu deklarieren sind, die sich dadurch auszeichnen, dass sich die Probanden zu keinem Zeitpunkt der Nähe zur Problemlösung bewusst sind. Er selbst nennt als metaphorisches Beispiel das Irren durch ein Labyrinth, bei dem man durch Zufall, indem man sich unbewusst an einer bestimmten Stelle herumdreht, den Ausgang findet. Den Probanden fehlt die Einsicht, wie nah sie der Lösung sind.

In der Kognitionspsychologie werden spezifische Verfahren des analogen Problemlösens in den Fokus gestellt. Man geht davon aus, dass Menschen spontan Analogien zu bereits vorhandenem Wissen und Handlungsschemata bilden, wenn sie sich in einer neuen Situation befinden. Des Weiteren wird der Problemlöser als ein aktiver Gestalter des Problemlöseprozesses selbst betrachtet, der sein Vorwissen selbst verwalten und organisieren muss. Beim analogen Transfer, den der Proband vollführen muss, um eine Lösungsstrategie zu entwerfen, können zwei Hauptprobleme auftreten, die einer Lösung im Wege stehen. Zum einen kann es sein, dass der Problemlöser nicht in der Lage ist, eine Ähnlichkeit zwischen der Problemaufgabe des Basis- und Zielbereichs zu erkennen und zum anderen kann er nicht in der Lage sein, auf sein deklaratives und prozedurales Wissensgedächtnis zurückzugreifen, obwohl die notwendigen Daten dort zur Verfügung stünden.

Komplexes Problemlösen

Nach heutiger Auffassung handelt es sich bei den in der Vergangenheit verwendeten Aufgaben zur Untersuchung der Problemlösefähigkeit um nicht komplexe Aufgaben, da diese eines oder mehrere der folgenden Merkmale nach Funke (1991) nicht oder nur teilweise erfüllen:

1. Intransparenz der Zusammenhänge

2. Polyteile (multiple Ziele)

3. Eine große Zahl an Variablen

4. Verknüpftheit der Variablen

5. Dynamik der Entwicklungen in einem System

6. Zeitversetzte Effekte

Somit handelt es sich bei den Problemstellungen wie Kannibalen und Missionare, alte Halskette oder Türme von Hanoi um keine komplexen Problemstellungen. Nach Seel ist die Produktion eines Textes für eine andere Person eine komplexe Aufgabe, wenn diese eine Integration kognitiver Fertigkeiten und Kompetenzen voraussetzt. Bei dieser Arbeit benötigt der Lernende interne Planungsprozesse, in denen er themenbezogenes Wissen zur Aufgabenstellung akquirieren muss und dieses in einem Transferprozess in verschriftlichte Sprache umwandelt. Auch die weitere Anwendung von eventuellen Korrekturen (Inhalt oder Formalien) tragen zur Komplexität des Problems bei.

Kooperatives Problemlösen

Eine weitere wichtige Dimension unter der man Problemlösen analysieren kann, ist das kooperative Problemlösen. Bei dieser Variante liegt der Fokus auf der Gruppe und ihren Mitgliedern. Per Definition gibt es Kriterien, die festlegen, welche Voraussetzungen erfüllt sein müssen, damit ein kooperatives Problem vorliegt. Hierbei handelt es sich um fünf Charakteristika:

1. gegenseitige Abhängigkeit beim Erreichen gemeinsamer Ziele

2. direkte persönliche Interaktion zwischen den Teilnehmern

3. individuelle und kollektive Verantwortlichkeit für Entscheidungen

4. soziale Verträglichkeit der Teilnehmer

5. Selbstbeurteilung der Gruppe

Diese Kriterien spielen unter anderem in Schulen eine wichtige Rolle, wenn Unterrichtsinhalte als kooperative Probleme dargeboten werden, um das soziale Lernen zu fördern. Die Inszinierung kooperative Probleme durch die Lehrkraft stellt für diese unter Berücksichtigung der oben geannten Punkte wiederum ein komplexes Problem dar.

Sortieralgorithmus

Das Sortieren von Dingen steckt der Menschheit schon von Klein auf in den Knochen. Beobachtet man Kleinkinder beim Spielen, dann stellt man fest, dass schon im jungen Alter eine Menge sortiert wird. Seien es die Bauklötze, die der Größe nach aufgestellt werden, Puppen die nach einem Niedlichkeitsfaktor getrennt werden oder das an den Rand legen der Erbsen auf einem Teller. Die Menschen sortieren um, aus, ein, alphabetisch, nach Größe, Preis, Menge, nach Gewicht, Alter, Aussehen, nach Effizienz, Verbrauch und einfach so. Menschen scheinen für ihr Leben gern zu sortieren. Im folgenden werden verschiedene Sortiermethoden erklärt und auf ihre Effizienz überprüft. Jedes Mal soll eine bestimmte Zahlenfolge: 56, 23, 67, 01, 45, 12, 78, 34 in aufsteigende Reihenfolge sortiert werden. Diese müsste dann folgendermaßen aussehen: 01, 12, 23, 34, 45, 56, 67, 78.

Sortieren durch direktes Einfügen

Bei dieser Methode hat man zwei Klassen. Zum einen die SORTIERTE KLASSE und zum anderen die RESTKLASSE. Zu Beginn sind alle Zahlen in der Restklasse. Anschließend wird nach und nach jeweils eine Zahl A aus der Restklasse ausgewählt und an den Beginn der Sortierten Klasse, also vor Zahl B, gesetzt. Dann wird die gewählte Zahl A mit der nachfolgenden Zahl B verglichen. Ist A größer, so tauschen die Zahlen A und B ihre Positionen. Jetzt wird die Zahl A mit der nächsten Zahl C verglichen. Ist sie wiederum größer, tauscht sie diesmal mit der Zahl C ihre Position. Dieser Schritt wird so lange durchgeführt, bis die Zahl A kleiner als (/gleich) der (/dem) Nachfolger ist, oder die nachfolgende Position leer ist. Erst dann wird die nächste Zahl aus der Restklasse ausgewählt und das Sortieren beginnt von vorn. Ist die Restklasse leer, dann wurde die Zahlenfolge richtig sortiert. Als Maß für die Effizienz sei hier die Einheit Rechenschritte gegeben:

                         Ein Rechenschritt kann das Einsetzen einer Zahl, das Vergleichen 
                                zweier Zahlen oder das Vertauschen zweier Zahlen sein.

Beispiel:

Schritt	Rechenschritte	Sortierte Klasse	Restklasse
0	0	-	56, 23, 67, 01, 45, 12, 78, 34
1	2	56	23, 67, 01, 45, 12, 78, 34
2	2	23, 56	67, 01, 45, 12, 78, 34
3	7	23, 56, 67	01, 45, 12, 78, 34
4	2	01, 23, 56, 67	45, 12, 78, 34
5	6	01, 23, 45, 56, 67	12, 78, 34
6	4	01, 12, 23, 45, 56, 67	78, 34
7	14	01, 12, 23, 45, 56, 67, 78	34
8	9	01, 12, 23, 34, 45, 56, 67, 78	-

Dieses Sortieren scheint auf den ersten Blick ein gutes Sortierverfahren zu sein. Bei genauerem Hinsehen brauchte der Computer 46 (=2+2+7+2+6+4+14+9) Rechenschritte, bis die Zahlenfolge aufsteigend sortiert war. Bei Verdopplung der Anzahl der Elemente jedoch und dem Anwenden des gleichen Sortierverfahrens, vervierfacht sich die Rechenzeit! (Heidemann & Foegen, 1988) Das sortieren einer Menge an Datensätzen mit Hilfe dieses Verfahrens, ist folglich nicht sinnvoll.

Sortieren durch Zerlegen und Austauschen: Quicksort

Um ein effizienteres Verfahren zu finden, muss man versuchen die Anzahl der Rechenschritte zu verkleinern. Sortieren in der vorherigen Art und Weiße benötigt, pro Vergleich und Verschiebung, jeweils einen Rechenschritt. Allein der 7. Schritt benötigte somit 14 Rechenschritte! Bei diesem wurde die 78 in die Reihe eingefügt. Es würde sich folglich anbieten, ein Sortierverfahren zu entwickeln, welches die Anzahl an Elementen, die ich vergleichen muss, verringert. Quicksort wendet genau diese Methode an: Das verringern von Rechenschritten. Als erstes bestimmt man das mittlere Element der zu sortierenden Liste. In unserem Fall (56, 23, 67, 01, 45, 12, 78, 34) entscheiden wir uns für die Zahl 45. Heidemann und Foegen bezeichnen die auf diese Art und Weiße ermittelte Zahl auch als Vergleichsschlüssel. Nun wird von links kommend eine Zahl gesucht, welche größer-gleich und von rechts kommend eine Zahl die kleiner-gleich dem Vergleichsschlüssel ist. Hat man solch ein Paar gefunden, werden die Positionen dieser getauscht. Wir benötigen deshalb die Formulierung kleiner-gleich bzw. größer-gleich, weil es sonst vorkommen kann, dass eine Zahl, deren Position getauscht werden müsste, keine Tauschposition hat. Dies führt man so lange fort, bis sich die der von links kommende Anzeiger und der von rechts kommende Anzeiger überschneiden. Sollte man dennoch die Zeiger weiterlaufen lassen, würden der von rechts kommende Anzeiger keine Zahl die kleiner und der von links kommende Anzeiger keine Zahl die größer ist finden, da diese Bereiche schon ausgetauscht worden sind. Veranschaulichen lässt sich dieses anhand folgender Skizze.

56, 23, 67, 01, 45, 12, 78, 34	Vergleichsschlüssel: 45
56, 23, 67, 01, 45, 12, 78, 34	Rechenschritte: 7
34, 23, 67, 01, 45, 12, 78, 56	Rechenschritte: 2
34, 23, 12, 01, 45, 67, 78, 56

Diese Zahlenfolge lässt sich nun in zwei Kategorien aufteilen. Zum einen in die Kategorie, welche kleiner und in eine welche größer-gleich dem Vergleichsschlüssel ist. (34, 23, 12, 01) (45, 67, 78, 56) Das Verfahren wird anschließend bei beiden Kategorien separat durchgeführt.

34, 23, 12, 01	Vergleichsschlüssel: 12
34, 23, 12, 01	Rechenschritte: 5
01, 23, 12, 34	Rechenschritte: 1
(01) (12, 23, 34)

45, 67, 78, 56	Vergleichsschlüssel: 78
45, 67, 78, 56	Rechenschritte: 5
(45, 67, 56) (78)

Bei den Zahlen, welche alleine in einer Klammer stehen, bedarf es keiner weiteren Sortierung. Die anderen beiden Klammerausdrücke müssen hingegen solange weiter bearbeitet werden, bis diese auch alleine in einer Klammer stehen. Durch abermaliges Anwenden des Quicksort Verfahrens bekommen wir:

12, 23, 34	Vergleichszahl: 23
(12) (23, 34)	Rechenschritte: 3

45, 67, 56	Vergleichszahl: 67
45, 67, 56	Rechenschritte: 3
(45, 56) (67)	Rechenschritte: 1

Durch letztmaliges sortieren, wird noch die Reihenfolge der 2er Terme festgelegt:

23, 34	Vergleichszahl: 34
(23) (34)	Rechenschritte: 2

45, 56	Vergleichszahl: 56
(45) (56)	Rechenschritte: 2

Schlussendlich ist jetzt jede einzelne Zahl sortiert worden und steht in der Reihenfolge an ihrer richtigen Position. Die Zahlenfolge wurde somit sortiert. Benötigt hat das Ganze 31 (=7+2+5+1+5+3+3+1+2) Rechenschritte. Um diesen Vorgang nicht so komplex aufzuzeigen, genügt eine einfache Skizze, an der sich jedoch nicht die benötigten Rechenschritte ablesen lassen.

• 
  Skizze

Anwendungsbeispiele

Das größte Rolle spielen Sortieralgorithmen in der Datenverarbeitung. Hier wird alles sortiert, seien es Telefonnummern, Inhaltsverzeichnisse, Artikelnummern, Geburtstage, Personalnummern, Artikelnummern usw. „Untersuchungen von Computerherstellern und -nutzern zeigen, dass mehr als ein Viertel der kommerziell verbrauchten Rechenzeit auf Sortiervorgänge entfällt.“ (Uni Oldenburg) Als logische Schlussfolgerung werden Jahr für Jahr, viele Forschungsgelder in die Entwicklung von neuen, effizienteren Sortieralgorithmen gesteckt. Berichte über den Forschungsstand und neuen Methoden, lassen sich in vielen Büchern, Magazinen und Fachzeitschriften verfolgen.

Das Dichteste Punktepaar Problem

Beim dichteste Punktepaar Problem müssen aus einer Menge von Punkten die beiden ausgewählt werden, welche den geringsten Abstand haben. Es eignet sich für den Informatikunterricht, weil es keine direkt ersichtlichen effektiven Lösungen besitzt und daher die verschiedenen Strategien zur Konstruktion eines passenden Algorithmus zur Lösung notwendig sind.

Das Problem

Das dichteste Punktepaar Problem in der euklidischen Ebene

Gegeben sei eine Menge M von Elementen e∈M und ein Abstandsmaß d:M×M→R. Ziel ist es e_a und e_b zu identifizieren, für die gilt:

d(e_a,e_b)=min⁡{d(e_x,e_y)|e_x,e_y∈M,e_x≠e_y}

Es gilt also die beiden Elemente zu finden, die unter dem Abstandsmaß den geringsten Abstand besitzen. Um das Problem zu veranschaulichen verwendet man im Allgemeinen Punkte im R² und den euklidischen Abstand, damit gilt es dann die in einer Menge von Punkten kürzeste Strecke zu finden, welche zwei der Punkte miteinander verbindet. Die Abbildung zeigt ein solches Problem mit dazugehöriger Lösung in rot markiert.

Hierbei wird deutlich, dass durch „scharfes Hinsehen“ zwar sehr viele Lösungen ausgeschlossen und je nach Problem möglicherweise sogar die Punkte der Lösung gefunden werden können. Allerdings ist diese Lösungsstrategie nicht direkt in einen effizienten Algorithmus umsetzbar, bei dem nicht alle möglichen Kombinationen ausprobiert werden müssen.

Eignung für den Schulunterricht

Das dichteste Punktepaar eignet sich gut für den Unterricht, da viele wichtige Elemente des Problemlösens daran vorgestellt werden können, welche wir im Weiteren näher betrachten. Außerdem ist das Grundproblem sehr einfach zu vermitteln. Je nach Klassenstufe kann der Fokus auf unterschiedliche Aspekte gelegt werden, so ist es mögliche über den gesamten Zeitraum des schulischen Informatikunterrichts immer wieder auf dieses Problem zurückzugreifen.

Strukturierung

Das dichteste Punktepaar Problem hat ausreichende Komplexität um die Notwendigkeit einer Strukturierung des Problems und des Lösungsraum aufzuzeigen. Gerade bei einfacheren Problemen, welche leicht ersichtliche Lösungsansätze besitzen, wie das in der Informatik beliebten Sortieren, ist die mathematische Strukturierung schwer zu vermitteln. Beim Problem des dichtesten Punktepaares hingegen kann in Anwendung allgemeiner Problemlösestrategien im ersten Schritt eine Strukturierung mit den Schülern erarbeitet werden. Je nach Klassenstufe und informatischer bzw. mathematischer Vorbildung kann diese Strukturierung sehr unterschiedlich erfolgen. In einer niedrigen Klassenstufe empfiehlt es sich diese Strukturierung etwas freier zu gestalten, indem das Problem nur verbal beschrieben wird. Ist die Ausbildung bereits weit fortgeschritten sollte das Problem möglichst korrekt mathematisch beschrieben werden. Zwischen den beiden Extremen kann dies beliebig an den Leistungsstand der Schüler angepasst werden, um weder zu unter- noch zu überfordern.

Laufzeitberechnung

Die Laufzeitberechnung von Algorithmen ist in der Informatik von großer Bedeutung. Anhand des Problems des dichtesten Punktepaares kann dies leicht den Schülern vermittelt werden. Da die augenscheinliche Lösung des Vergleiches aller Punkte untereinander in O(n²) liegt ist die Suche nach einer Effizienteren Lösung notwendig. Sofern die Schüler bereits über ein Gespür für das Wachstum einer quadratischen Funktion besitzen sollte ihnen die Problematik einer solchen Lösung schnell klar werden. Andernfalls muss auf beispielhafte Berechnungen größerer Zahlen zurückgegriffen werden. Da das Problem durch unterschiedliche Algorithmen zu lösen ist, ist ein Maß für die Güte eines Algorithmus notwendig um eine Vergleichbarkeit herzustellen. Betrachtungen neben der Laufzeit gehen in den meisten Fällen über das schulische Wissen hinaus, weswegen eine Beschränkung auf eben diese keinerlei Problem darstellen sollte.

Algorithmisierung

Das dichteste Punktepaar erfordert zu seiner effizienten Lösung die Durchführung einzelner separater Schritte, weswegen die Formulierung der Lösung in algorithmischer Form angebracht erscheint. Auch hier kann je nach Wissensstand der Schüler variiert werden, ob diese zum Beispiel als einfache verbale Arbeitsanweisung, in Form von Pseudocode oder sogar als fertiges Programm formuliert wird. In jedem Fall können hierbei die Vorteile einer geeigneten Formulierung des Algorithmus, wie Vergleichbarkeit mit anderen Algorithmen oder besseres Verständnis gut vermittelt werden.

Problemlösestrategien

Der vermutlich wichtigste Punkt ist die Anwendung von Problemlösestrategien. Wie bereits erwähnt bringt das dichteste Punktepaar Problem eine Komplexität mit sich, die zur Lösung den Einsatz von Strategien zur Lösungsfindung benötigt, da wohl nur in den wenigsten Fällen eine effizienter Lösungsweg ohne nähere Betrachtung gefunden werden kann. So kann aufgezeigt werden, wie über die Anwendung einer der Lösungsstrategien, zum Beispiel Divide&Conquer oder auch randomisierte Vorgehensweisen, zu einer funktionierenden Lösung führen können.

Anwendungsbeispiele

Um das Problem des dichtesten Punktepaares den Schülern zu vermitteln sollte zunächst der Realitätsbezug der Problematik hergestellt werden können. Am besten kann dies anhand von alltäglichen Problemen der Schüler, mit denen sie oder ihre Umgebung zu kämpfen haben. Da es innerhalb diesen beschränkten Suchraums mitunter schwer fällt geeignete Beispiele zu finden, empfiehlt es sich in diesem Fall auf humorvoll konstruierte Beispiel mit einem Rest Realitätsbezug zurück zu greifen.

Das Sockenproblem

Eines der einprägsameren Anwendungsbeispiele ist das Sockenproblem. Auch den Schülern der untersten Klassenstufen sollte bekannt sein, dass Sockenpaare über die zuverlässige Eigenschaft verfügen irgendwann plötzlich nicht mehr zusammen zu passen. Dadurch entsteht in den meisten Haushalten eine Sammlung einzelner Socken. Sind nun alle passenden Paare aufgebraucht und man benötigt dringend ein weiteres Paar, um die Füße nicht direkt in ein stinkendes Paar Schuhe stecken zu müssen, bleibt nur noch die Sammlung der Singlesocken. Um sich nicht ganz zu blamieren empfiehlt es sich nun die beiden Socken zu wählen, welche sich am ähnlichsten sind. Dieses Problem entspricht exakt dem Problem des dichtesten Punktepaares, die Socken sind die Punkte und das Ähnlichkeitsmaß der Socken ist das Abstandsmaß der Punkte. Je nach Wunsch kann die Ähnlichkeitsfunktion verschieden viele Parameter, wie Farbe, Größe, Material, Löchrigkeit, etc. annehmen, sodass die Komplexität frei angepasst werden kann. Ein solches Beispiel eignet sich vor allem für besonders niedrige oder besonders hohe Stufen, die für einen solchen Zugang offen sind.

Das Slacklineproblem

Für mittlere Klassenstufen, welche sich gerade im „coolen Alter“ befinden ist ein etwas ernsterer Zugang angebracht. Ein Beispiel hierfür wäre ein Szenario, in dem innerhalb einer Parkanlage mit vielen Bäumen eine Slackline aufgespannt werden soll. Um diese möglichst stabil zu befestigen gilt es die beiden Bäume zu finden, welche voneinander den geringsten Abstand haben. Dies ist dann exakt die Problematik des dichtesten Punktepaars in der euklidischen Ebene.

Konstruktion eigener Beispiele

Mit etwas Kreativität lassen sich leicht viele weitere Beispiele konstruieren, um das Problem klassengerecht zu vermitteln, besonders wenn man sich von der Vorstellung löst ein Problem im euklidischen Raum konstruieren zu müssen. Dadurch kann außerdem gleich das Verständnis für allgemeine Abstandsmaße mit den Schülern geübt und so ein weiterer sinnvoller paralleler Lerneffekt erzielt werden.

Lösungen

Für das Problem des dichtesten Punktepaares existieren Lösungsverfahren die sich in die verschiedenen Kategorien der Problemlösestrategien einordnen lassen. So kann die Existenz der einzelnen Strategien gerechtfertigt werden.

Brute Force

Der einfachste Lösungsweg für das dichteste Punktepaar Problem ist ein Brute-force Algorithmus, bei dem der Abstand für alle möglichen Kombinationen an Paarungen einzeln berechnet wird. Wie leicht zu sehen ist, hat diese Methode einen quadratischen Aufwand und ist damit nur für sehr kleine Mengen sinnvoll anwendbar.

Divide & Conquer

Maximal 6 Abstandsberechnungen für jeden Punkt notwendig

Besonders im euklidischen ist die Anwendung eines Divide & Conquer-Ansatzes ohne besondere Schwierigkeiten möglich, so auch hier. Für den erleichterten Zugriff legen wir zwei sortierte Listen der Punkte an, jeweils nach x bzw. y Koordinate sortiert- Indem man den Betrachtungsraum entlang der x-Achse schrittweise aufteilt bis sich jeweils nur noch zwei Punkte in einem Abschnitt befinden, erhält man eine Menge trivialer Probleme, da die Lösung jeweils das einzig vorhandene Paar ist. In unserer Liste sind dies immer zwei direkt benachbarte Punkte. Im zweiten Schritt müssen dann diese Einzellösungen zu einer Gesamtlösung zusammengefasst werden. Für jeden Bereich ist die lokal beste Lösung bekannt, nun müssen beim Zusammenfügen noch die Paarungen zwischen den beiden zusammenzufügenden Bereichen betrachtet werden. Aus den lokalen Lösungen lässt sich ein vorläufiges Minimum δ bilden. Damit müssen nur Punkte betrachtet werden deren Abstand von der Trennlinie kleiner ist als δ. Für jeden dieser Punkte müssen nun nur maximal sechs Abstände berechnet werden, wie die Abbildung zeigt, da die Punkte innerhalb eines Bereiches mindestens Abstand δ besitzen.

Da sich das Zusammenfügen also in linearer Zeit lösen lässt erhält man letztendlich für diese Lösung eine Laufzeit von O(n log ⁡n). Dies ist eine deutliche Verbesserung gegenüber dem Brute-force Ansatz.

Randomisierte Verfahren

Das Randomisierte Lösungsverfahren funktioniert ähnlich zum Divide & Conquer Ansatz. Allerdings wird hierbei quasi die umgekehrte Richtung gewählt. Die Punkte werden in zufälliger Reihenfolge in eine Hashtabelle eingefügt, die Gitterzellen mit der Größe δ⁄2, wobei δ wieder das bisherige Minimum ist, auf die darin enthaltenen Punkte abbildet. Pro Gitterzelle kann maximal ein Punkt enthalten sein, da sonst δ nicht das aktuelle Minimum wäre. Nun muss beim Einfügeschritt, ähnlich zum Divide & Conquer Ansatz nur eine konstante Anzahl (25) an Gitterfelder überprüft und der Abstand berechnet werden. Wird dabei ein neues δ muss zwar die Hashtabelle neu aufgebaut werden. Die Einfüge- und Überprüfoperationen in der Hashtabelle laufen in konstanter Zeit ab, daher ist nur die Anzahl dieser Operationen interessant. Berücksichtigt man die Wahrscheinlichkeit für die Notwendigkeit eines Neuaufbaus der Hashtabelle ergibt sich letztendlich eine lineare Laufzeit und damit die beste unserer drei Lösungsansätze.

Literaturverzeichnis

• Anderson, J.(2000). Kognitive Psychologie (3. Auflage). Heidelberg: Akademischer Verlag.
• Gudjons, H. (2008). Pädagogisches Grundwissen (10. Auflage). Heilbrunn: Klinkhardt.
• Haas, W.-D. (1986). Informatik – Vom Problem zum Algorithmus. Frankfurt/Main: Diesterweg&Sauerländer
• Heidemann, V. & Foegen, M. (1988). Problem. Algorithmus. Lösung. Bonn: Dümmler
• Seel, N. (2000). Psychologie des Lernens. München: Reinhardt Verlag.
• Uni Oldenburg: http://www-cg-hci.informatik.uni-oldenburg.de/~media/nutzen.html (gesehen am: 3. Okt. 2012)
• Wikipedia(deutsch): Dichtestes Punktepaar (http://de.wikipedia.org/wiki/Dichtestes_Punktpaar, Stand: 14.10.12)
• Wikipedia(englisch): Closest pair of points problem (http://en.wikipedia.org/wiki/Closest_pair_of_points_problem, Stand: 14.10.12)