Open Source im professionellen Einsatz
Linux-Magazin 08/2015
© HONGQI ZHANG, 123RF

© HONGQI ZHANG, 123RF

Vermeintlich einfache Mathe-Probleme lösen mit Perl

Gruppenzwang

Manche mathematischen Spielereien klingen zunächst, als wären sie kinderleicht zu lösen. Doch wer das tatsächlich versucht, merkt, wie schnell er sich daran die Zähne ausbeißen kann.

910

Es war vor fast 20 Jahren, im lauen Sommer 1996. Ich verdiente gerade mein Geld als Entwickler bei einer bekannten Softwareschmiede im Münchner Osten, als ein Arbeitskollege aufgeregt von einem einfach klingenden, aber offenbar schwer zu lösenden Problem berichtete:

Der Rektor einer Schule sieht sich mit der Aufgabe konfrontiert, neun Lehrer, 27 Schülerinnen und 18 Schüler derart in neun täglich wechselnde Gruppen einzuteilen, dass die Schüler an jedem Tag mit anderen Lehrern und anderen Mitschülern in der Klasse sitzen. Jede Gruppe soll aus genau einem Lehrer, zwei Buben und drei Mädchen bestehen, und pro Tag finden neun Gruppensitzungen in verschiedenen Klassenräumen statt, jeweils geführt von einem der insgesamt neun Lehrer. Wie viele Tage lang könnte die Schule nun den Unterricht durchziehen, ohne dass sich die Besetzung der Gruppen überlappt? Vielleicht fünf?

"Nichts leichter als das!" riefen meine Kollegen und ich sofort, legten die Projektarbeit kurzfristig auf Eis und begannen, die ersten Programme in unsere Workstations zu klopfen. Abbildung 1 zeigt den ersten Versuch mit einem einfachen Algorithmus, der pro Tag neun Gruppen mit immer den gleichen Lehrern und noch nicht eingeteilten Schülern auffüllt. Dabei führt er Buch darüber, wer schon mit wem zusammen war, und nimmt für eine Gruppe im Überlappungsfall einfach den nächsten Schüler aus dem noch nicht eingeteilten Kontingent.

Abbildung 1: Wer die Gruppen der Reihe nach mit Schülern auffüllt, schafft nicht mal zwei Tage ohne Überlappungen.

Die Lehrer sind mit dem Buchstaben »i« (für Instructor) von 1 bis 9 durchnummeriert, die Buben von »b1« bis »b18« (Boy) und die Mädchen mit »g1« bis »g27« (Girl). So leitet zum Beispiel Lehrer »i1« am ersten Tag die Klasse im Gruppenraum 1, und zwar mit den Schülern »b1« und »b2« und den Schülerinnen »g1« , »g2« und »g3« :

day1 group1: i1 b1 b2 g1 g2 g3

Am zweiten Tag stellt der Algorithmus in Gruppe 1 fest, dass die Buben »b1« und »b2« am Vortag schon mit Lehrer »i1« zusammen waren, und teilt Letzterem deswegen »b3« und »b5« zu. So geht das eine Weile.

Allerdings ist schon gegen Ende des zweiten Schultags Schicht im Schacht, denn für Gruppe 7 finden sich keine Schülerinnen mehr: »g19« , »g20« und »g21« waren schon am ersten Tag mit »i7« in Gruppe 7. »g22« , »g23« und »g24« waren mit »b15« in Gruppe 8. Und »g25« , »g26« und »g27« waren mit »b17« in Gruppe 9, also steckt das Verfahren fest!

Schwer verschätzt

Nach einigen Fehlversuchen begann uns langsam zu dämmern, dass dies wohl etwas mehr Hirnschmalz und Rechenleistung erfordert, als zunächst angenommen. Also begannen die ersten Informatiker damit, unsere damals brandheißen HPUX-Workstations mit Backtracking-Algorithmen zu traktieren.

Zur allgemeinen Überraschung stellte sich jedoch nach einigen Stunden gnadenloser Brute-Force-Attacken kein Erfolg, sondern allgemeine Ernüchterung ein. Es gab einfach viel zu viele Kombinationen, die alle durchzuprobieren von vornherein zum Scheitern verurteilt war. Keiner, weder ein Jungfuchs noch ein alter Hase, hatte eine Lösung für auch nur mehr als zweieinhalb Tage.

Wo Hilfe suchen? Das Internet steckte 1996 noch in den Kinderschuhen, insbesondere das Web war völlig unbrauchbar, weil es hauptsächlich aus "Homepages" bestand, die aufgeregt mit »BLINK« -Tags und den schaufelnden Bauarbeitern des "Under Construction"-Zeichens warben. Google kam erst zwei Jahre später, also hätte ich etwaige Lösungen, selbst wenn es sie gegeben hätte, in Bergen von Spam- Seiten nie gefunden. Aber das Usenet gab es schon und wurde hauptsächlich von Universitätsangestellten frequentiert, also machte ich mich daran, das Problem auf der Newsgroup »rec.puzzles« zu schildern und die Gemeinde dort um Hilfe zu bitten ([2], Abbildung 2).

Abbildung 2: Der Usenet-Artikel von 1996, mit dem alles anfing.

Antikes Internet hilft

Ein paar Tage später kam die Antwort eines Mathematikers namens Barry Wolk von der Universität Manitoba in Kanada. Er hatte das Problem mit schweren Geschützen diskreter Mathematik gelöst: einem Galoiskörper mit neun Elementen und neun daraus generierten, zueinander orthogonalen Lateinischen Quadraten (Latin Squares, [3], [4]). Ich fabrizierte aus seinen glasklaren und selbst für Laien verständlichen Instruktionen schnell ein Perl-Skript, das im Bruchteil einer Sekunde eine Lösung für nicht nur fünf, sondern neun Tage ausspuckte (Abbildung 3). Ich war der Held!

Abbildung 3: In Sekundenschnelle druckt der diskret-mathematische Ansatz eine Lösung für insgesamt neun Tage aus.

Der kanadische Mathematiker schlug vor, eine Sammlung von Lateinischen Quadraten zu konstruieren. Diese matrixförmigen, an Soduko-Rätsel erinnernden Gebilde, an denen schon der kauzige Mathematiker Leonhard Euler im 18. Jahrhundert seine Freude fand, enthalten die Zahlen von 1 bis n pro Spalte oder Reihe genau einmal.

Abbildung 4 zeigt ein Lateinisches Quadrat der Dimension 9x9 mit den Zahlen 1 bis 9. Wer durch die Spalten und Reihen fährt, kann leicht feststellen, dass sich keine einzige Zahl – weder auf der Senkrechten noch auf der Waagrechten – jemals wiederholt. Euler füllte seine Quadrate damals übrigens statt mit Zahlen mit lateinischen Großbuchstaben A, B, …, so kam der "lateinische" Namenszusatz zustande.

Abbildung 4: Beispiel für ein Lateinisches Quadrat, hier in der Größe 9x9.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 5 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Web ID wird Incubator Group beim W3C

    Eine Reihe Firmen und Organisationen haben beim World Wide Web Consortium (W3C) eine Arbeitsgruppe im Bewährungsstadium für das Protokoll Web ID ins Leben gerufen, das SSL/TLS-basierte Benutzerauthentifizierung im Web definiert.

  • Rumäniens Lehrer lassen Linux liegen

    Dass Linux-Migrationen häufig weniger an technischen und vielmehr an menschlichen Problemen scheitern, zeigt ein aktueller Bericht aus Rumänien.

  • Vorsicht, Falle!

    Gerade das leicht erlernbare Perl, mit dem der Autor seine Informatik-Vorlesungen immer beginnt, weckt bei Studierenden Kreativität und Motivation. Was allerdings nicht vor Missverständnissen schützt, die zuweilen Schmunzeln lassen. Einige Perlen der Programmierirrtümer mit Perl stellt dieser Beitrag vor.

  • Deutsche Java User Groups ärgern sich über Oracle

    Oracles Informationpolitik in Sachen Java ist für die im Interessenverbund der Java User Groups e.V. (IJUG) zusammengeschlossenen deutschen Java-Anwender ein Ärgernis.

  • Q3/2008: Zwanzig Prozent mehr Sommer für IBM

    Big Blue steigerte im dritten Quartal 2008 seinen Gewinn um ein Fünftel auf gut zwei Milliarden Euro. Ende des Quartals war am 30. September.

comments powered by Disqus

Ausgabe 04/2017

Digitale Ausgabe: Preis € 6,40
(inkl. 19% MwSt.)

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.