Mathematik in Informatik?

[Michael Schröpl]

Hi Frank,

Falls du das Springer-Problem (nicht Läufer) meinst: dazu habe ich
sogar im ersten Semester mal ein Programm zur Lösung geschrieben. Aber
ob das so erkenntnisreich und sinnvoll ist?

Bekannter ist aber doch eigentlich das Damenproblem, oder? Dabei muss
man n Damen auf einem n*n-Schachfeld (zb. für n=8) verteilen, ohne
dass zwei der Damen sich gegenseitig bedrohen.

das aus der Sicht des Informatikers daran Interessante ist, daß diese beiden Beispiele für recht unterschiedliche Arten von Problemen herhalten, die nur äußerlich aufgrund des gemeinsamen Anwendungsfeldes (Schach) verwandt aussehen:

• Das Springerproblem ist eine schöne Veranschaulichung einer einfachen Rekursion innerhalb einer entsprechenden, ziemlich naheliegenden Datenstruktur, wobei das "Ziehen" des Springers für den Anfänger eine nette Fingerübung für die Codierung abstrakter Informationen in einem konkreten (und nur endlich großen) Koordinatensystem darstellt;

• das Damenproblem dagegen besteht im Wesentlichen aus dem Entwurf der geeigneten Datenstruktur (wie repräsentiert man Diagonalen?), während die Damen hierbei ja nicht "ziehen", sondern "vom Himmel fallen" (das ist etwas einfacher). Das ist schon ein recht gutes Beispiel für eine richtige Programmentwicklung mit Problemanalyse, Datenmodellierung, Codierung und Performance-Tuning (durch rechtzeitiges Beschneiden des Traversierungsbaums).

Gemeinsam haben die Probleme den Trade-Off zwischen Performance und Code-Einsparung bei der Buchführung (Value-Parameter oder manuelle Ausführung/Rücknahme der "Züge").
Die konkreten Datenstrukturen unterscheiden sich aber (bei einer jeweils eleganten Lösung) erheblich: Der Springer läuft auf einem 'richtigen' Schachbrett herum, die Dame jedoch ordnet die Datenstruktur ihren eigenen Fähigkeiten unter.

Diese Abstraktionsfähigkeit bei der Abbildung eines Anwendungsfalles auf ein darunterliegendes Problem und die Erkennung von Gemeinsamkeiten bzw. Unterschieden ist es, welche durch den Umgang mit Mathematik (oder auch mit abstrakten Vorgängen wie Schach selbst) geschult wird - ohne daß in beiden Fällen mehr als elementare Arithmetik an konkreten Vorkenntnissen erforderlich wäre.

Viele Grüße
      Michael