Gruppenarbeit zum Heiratsproblem

Heiratsproblem Unterrichtseinheit - Hinweise für den Lehrer

Zuordnungsprobleme sind alltägliche Probleme, die jedem bekannt sind. Ob das Finden einer Tischordnung, Zusammenstellen von Teams, Einteilen von Studenten in Übungsgruppen oder Zimmerbelegungen in einem Schullager, all dies sind letztendlich Zuordnungsprobleme. Diese Unterrichtseinheit setzt sich mit dem berühmtesten Zuordnungsproblem, dem sogenannten "Heiratsproblem", eingehend auseinander. Der Unterricht gliedert sich in zwei Teile.

Der erste Teil beschäftigt sich mit dem Heiratsproblem auf rein algorithmischer Basis ohne jeglichen Bezug zur Implementation. Für diesen Teil inklusive Gruppenarbeit werden zwei Stunden benötigt.

In einem zweiten Teil soll der vorgestellte Algorithmus als Programmierübung in Microsoft Excel mit Visual Basic ausprogrammiert werden. Dafür ist mit mindestens zwei weiteren Stunden zu rechnen, je nach Programmierkenntnissen der Schüler auch mit mehr.

Voraussetzungen an die Infrastruktur

Der Unterrichtsraum sollte neben dem Lehrervortrag die Arbeit in 3er-Gruppen ermöglichen. Für die Programmierübung des zweiten Unterrichtsteils müssen Computer mit Microsoft Excel zur Verfügung stehen. Am idealsten wäre, wenn pro Schüler ein Computer vorhanden ist. Es kann aber auch in 2er-Teams programmiert werden.

Vorausgesetzte Kenntnisse der Studierenden

• Anwender-Grundkenntnisse in Tabellenkalkulation.
• Variablen und Funktionen aus Mathematik.
• von Vorteil:

  • Grundverständnis der Begriffe "Algorithmus" und "Programm".
  • Für den Programmierteil: Prozeduren, Funktionen, Variablen, Schleifen (in beliebiger Programmiersprache. z.B. Colobot, Kara, ...).

  Einführung in diese Grundkenntnisse kann in diesen Unterricht eingebaut werden. Dann verlängert sich die Unterrichtszeit natürlich entsprechend.

Lernziele

Leitidee

Für Computer-Benutzer ist oft schwer zu verstehen, wie ein Computer Probleme lösen kann. Dies führt nicht selten zu Missverständnissen und Schwierigkeiten, ja sogar zu Berührungsängsten mit der "technischen Wunderkiste".

Am Beispiel eines typischen und allgemeinverständlichen Problems aus der theoretischen Informatik soll deshalb das Verständnis von Algorithmen und Programmen vertieft werden. Die Teilnehmer erfahren, dass Informatik nicht zwingend am Computer stattfinden muss, sondern (wie alle Wissenschaften) vor allem im Kopf beginnt. Ein Problem kann vom Computer schliesslich nur dann gelöst werden, wenn es einen Algorithmus dafür gibt.

Damit der Computer den Algorithmus schliesslich für uns durchführen kann, müssen wir den Algorithmus in einer für den Computer verständlichen Sprache ausprogrammieren. In Microsoft Excel steht dafür mit Visual Basic ein weit verbreitetes Programmiertool zur Verfügung. Damit implementieren wir im zweiten Teil den Algorithmus, um aufzuzeigen, wie man sich mühsame Arbeiten am Computer durch kleine eigene Programme erleichtern kann.

Fundamentale Idee

Computer können für uns Probleme lösen, wenn es einen Algorithmus zum Lösen des Problems gibt. Der Algorithmus muss dazu jedoch in einer für den Computer verständlichen formalen Sprache beschrieben werden. Wir können den Algorithmus natürlich auch selbst durchführen, dies kann aber unter Umständen sehr mühsam werden.

Dispositionsziele

Die Schüler verstehen, wie ein Computer bei der Lösung eines Problems helfen kann. Sie entwickeln ein Gefühl dafür, was ein Computer kann und was nicht. Wenn die Schüler auf ein Problem stossen, welches einem der Computer abnehmen könnte, so erkennen sie das. Wenn sie ein besonders mühsames Problem haben, welches sie immer wieder lösen müssen, werden sie versuchen ein Programm dafür zu entwickeln.

Operationalisierte Lernziele

• Die Schüler kennen das "Heiratsproblem" und können erklären was man dabei unter einer "stabilen Heirat" versteht.
• Sie kennen den Algorithmus zum Finden einer Mann- oder Frau-optimalen Lösung und können ihn in eigenen Worten formulieren.
• Sie können den Algorithmus von Hand durchführen.
• Sie kennen die Grundstrukturen von Programmen in Visual Basic (Prozeduren, Funktionen, Variablen, While-Schleifen, If-Then-Else-Verzweigungen).
• Sie wissen, wie man aus Visual Basic Programmen auf Microsoft Excel Tabellen und deren Zelleninhalte zugreifen kann.
• Sie können in Visual Basic einfache kleine Programme unter Microsoft Excel schreiben.

Ablauf des Unterrichts

U'methode	Beschreibung	Material
Lehrervortrag / Diskussion	Zuordnungsprobleme: Beispiele aus dem Alltag (Brainstorming) Ausführliches Beispiel: Für ein Programmierprojekt sollen 2er-Teams aus Algorithmikern und Programmierern gebildet werden. Halbieren der Klasse in Algorithmiker und Programmierer mit persönlichen Präferenzlisten. Wie bilden wir 2er-Teams? Kurze Diskussion über mögliche Lösungsansätze im Plenum.	Slides Persönliche Präferenzliste für jeden Schüler und jede Schülerin.
IU	Überleitung zum "Heiratsproblem". Ablauf der Doppelstunde: Wer macht wann was? Ziele der Doppelstunde	Slides
Lehrervortrag	"stabile Heirat"	Slides
Rollenspiel im Klassenverband	Algorithmus als Rollenspiel durchführen gemäss verteilten Präferenzlisten.	Slide Nr. 14 Präferenzlisten
Lehrervortrag	Algorithmus zum Lösen des Problems Durchführen an Wandtafel am Beispiel von Slide Nr. 13 Mann- und Frau-optimale Lösungen	Slides Wandtafel
Gruppenarbeit (3er Gruppen)	Trennung von Algorithmus und Datenstruktur (2 Tabellen) durch Verteilung auf 3 Personen. Gemeinsames Durchspielen des Algorithmus	Aufgabenblätter Tabellen "Männer" und "Frauen" Algorithmus-Blatt Lösungsblätter
Einzelarbeit	Selbständiges Lösen eines kleineren Heiratsproblems. Ausformulieren des Algorithmus in eigenen Worten.	Aufgabenblätter evtl. Algorithmus-Blatt Lösungsblätter
Gruppenarbeit	Kurze Diskussion der Algorithmus-Formulierungen. Gemeinsame Formulierung des Algorithmus.	Aufgabenblätter
Diskussion	Jede Gruppe präsentiert kurz ihre Ausformulierung des Algorithmus. Kurze Diskussion der Resultate.	Aufgabenblätter Algorithmus-Blatt Slides als Handout
IU	Ablauf: Wer macht wann was? Motivation Ziele	Slides
Lehrervortrag	Excel als Welt (Tabellen als Datenstrukturen) und Visual Basic als Programmiertool welches darauf operieren kann Zugriff auf Exceltabellen und deren Zelleninhalte von Visual Basic aus. Die wichtigsten Sprachelemente von Visual Basic (Variablen, While und If-Then-Else). Kurze Demonstration in Excel.	Slides PC und Beamer für Demonstration Handout "Sprachübersicht"
Einzelarbeit (individualisiertes Lernen)	Ausprogrammieren des Heiratsproblems	Aufgabenblätter Handout "Sprachübersicht" Datei heiratsproblem.xls mit Tabellen "Männer" und "Frauen" Lösung: heiratsproblem_loesung.xls
Lehrervortrag / Diskussion	Diskussion der Resultate kurze weiterführende Informationen zu Visual Basic in Excel (Makro-Recorder, Hilfe) Schluss	Slides Slides als Handout

Hinweise zur Gruppenarbeit

• Für die Gruppenarbeit gibt es keine Zeitvorgabe. Die Schüler sollen sich beim Lehrer melden, so bald sie eine Aufgabe gelöst haben.
• Es liegt beim Lehrer nach jeder Aufgabe zu entscheiden, wie die Schüler weiter machen sollen.
• Wenn die Schüler die Aufgabe 1 gleich beim ersten Anlauf richtig gelöst haben, so wird sie die Aufgabe 2 eventuell langweilen. In diesem Fall reicht es auch, wenn sie kurz gemeinsam diskutieren, was man zum Finden einer Mann-optimalen Lösung anders machen müsste.
• Lässt man Aufgabe 2 weg, so sollten sich die Gruppenmitglieder bei Aufgabe 3 dafür so absprechen, dass nicht alle die gleiche Lösung (Mann- oder Frau-optimal) berechnen. Dann können auch bei dieser Aufgabe beide Lösungen verglichen werden.

Hinweise zum Heiratsproblem

• Der Algorithmus von Gale und Shapley wurde verwendet, um Medizinstudenten in den USA zu Praktikumplätzen in Spitälern zuzuweisen. Natürlich wurden die Spitäler dabei bevorzugt. Dies führte zu einer hitzigen Diskussion im "New England Journal of Medicine".
• Anhand des Heiratsproblems können auch viele weitere Themen aus der Informatik angesprochen werden. Zum Beispiel: Korrektheit, Terminierung, Laufzeit, Künstliche Intelligenz, Objekt Orientierte Programmierung, Verteilte Systeme, ...
• Einen sehr interessanten Text von Dr. Harry Mairson über "The Stable Marriage Problem" und seine vielseitigen Bezüge zur Informatik findet man unter http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html.