Kapitel 1

1 Mathematische Modelle, Algorithmen und Programme

Bei der wissenschaftlichen Bearbeitung praktisch relevanter Problemstellungen ist die moderne Computertechnik zum unverzichtbaren Hilfsmittel geworden. Der Rechner unterstützt den Wissenschaftler bei der Systematisierung, Darstellung und Präsentation der eigenen Resultate und ist ein äußerst effizientes Rechercheinstrument im weltweiten Daten- und Wissensfundus. Die tatsächliche Innovationskraft der gegenwärtigen Leistungsexplosion auf dem Gebiet der Computertechnik zeigt sich jedoch vor allem dann, wenn der Computer aktiv in den Problemlösungszyklus integriert wird und mit Hilfe neuer effizienter Algorithmen und Programme Aufgaben mit sehr hoher Komplexität bewältigt werden können. Heute ist die Simulation komplizierter naturwissenschaftlich-technischer Zusammenhänge auf der Grundlage exakter mathematischer Modelle ohne den Einsatz von Höchstleistungscomputern und modernen Methoden des wissenschaftlichen Rechnens nahezu unmöglich.

Abb. 1 Problemlösungszyklus

Der Problemlösungszyklus (Abbildung 1) beginnt mit der Beschreibung der zu untersuchenden realen Erscheinung, des Forschungsobjektes. Die Eingangs- und Zielgrößen des Problems werden definiert und die physikalischen Gesetzmäßigkeiten, die den Zusammenhang zwischen diesen Größen beschreiben, formuliert. Mit Hilfe von Idealisierungen, Vereinfachungen und Abstraktionen wird versucht, ein möglichst adäquates Modell der Realität zu finden. Es resultiert ein mathematisches Modell, in der Regel ein System von algebraischen, Differential- und/oder Integralgleichungen. Im nächsten Schritt werden nun die Eigenschaften des mathematischen Modellproblems gründlich analysiert, der Lösungsbegriff wird definiert und es wird untersucht, ob das Problem korrekt gestellt ist und welche a priori Aussagen über die Lösung gemacht werden können. Schließlich muß ein geeignetes analytisches oder numerisches Lösungsverfahren ausgewählt werden. Jetzt ist zu entscheiden, ob und in welchem Maße der Computer in den Lösungsprozeß einbezogen werden kann. Soll ein numerisches Verfahren eingesetzt werden, muß zunächst das mathematische Modell durch ein numerisches (diskretes) Modell ersetzt und die Problemanalyse für dieses Modell wiederholt werden. Hat man sich für einen konkreten Lösungsalgorithmus entschieden, der nur auf einem Computer realisiert werden kann, schließt sich die Auswahl der Rechnerklasse (PC, Workstation, Parallelrechner), des Betriebssystems und der Programmiersprache (prozedural, objektorientiert, logisch) an. Der Programmierzyklus beginnt mit dem Entwurf der Programmstruktur, dem Daten- und Schnittstellendesign, wird mit der Implementierung der Teilalgorithmen fortgesetzt und endet mit ausführlichen Testsimulationen der einzelnen Komponenten und schließlich des Gesamtsystems. Nach der erfolgreichen Verifikation des Programmsystems kann nun die Lösung des eigentlichen Problems in Angriff genommen werden. Die Ergebnisse zahlreicher Simulationsläufe müssen interpretiert und ausgewertet werden. Eine gründliche Fehleranalyse bildet die Grundlage für die Einordnung und Bewertung der gefundenen Lösung. Hier müssen die Fehler in den Eingangsdaten, die Modellfehler und die Verfahrensfehler gleichermaßen berücksichtigt werden. Entspricht die Lösung noch nicht den gestellten Anforderungen, wird der gesamte Problemlösungszyklus wiederholt.

Das folgende sehr einfache Beispiel soll die einzelnen Etappen der Problemlösung noch einmal verdeutlichen.

Herr Komisch, Herr Ernst und Herr Witzig treffen sich zum Skat. Ihre Vornamen sind (möglicherweise in anderer Reihenfolge) Klaus, Egon und Walter. Einer von ihnen trägt keinen Schlips, ein anderer einen einfarbigen und der dritte einen witzigen Schlips. Nach dem Spiel stellen sie fest:

Der Gewinner der Skatrunde trägt den einfarbigen Schlips.
Herr Ernst saß noch nie vorher auf Herrn Komischs Sofa.
Walter trägt keinen Schlips.
Herr Komisch findet es komisch, daß er nicht gewonnen hat.
Klaus saß schon das vorige Mal auf Herrn Komischs Sofa.
Herr Witzig trägt den witzigen Schlips.

Stellen Sie die Vor- und Familiennamen richtig zusammen und ordnen Sie die Schlipse richtig zu.

Offensichtlich sind die Eingangsgrößen des vorliegenden Problems die drei Namen Komisch, Ernst und Witzig, die drei Vornamen Klaus, Egon und Walter, die drei Schlipse kein, einfarbig und witzig, sowie die sechs Aussagen über die Beziehungen zwischen den Eingangsgrößen. Betrachtet man zunächst einmal die logischen Aussagen etwas genauer, so erkennt man leicht, daß sich die Aussagen 1 und 4 und die Aussagen 2 und 5 vereinfachen lassen. Diese Aussagen können ohne Informationsverlust durch die folgenden beiden Aussagen ersetzt werden:

Herr Komisch trägt nicht den einfarbigen Schlips.
Herr Ernst heißt nicht Klaus.

Die gesuchten Zuordnungen der Vornamen zu den Namen und der Schlipse zu den Namen lassen sich mathematisch ebenfalls leicht beschreiben. Bezeichne N die Menge der Namen:

N : = { Komisch, Ernst, Witzig }

V die Menge der Vornamen:

V : = { Klaus, Egon, Walter },

und S die Menge der Schlipse:

S : = { kein, einfarbig, witzig },

so sind die gesuchten Zuordnungen eineindeutige Abbildungen:

v : N ® V

und

s : N ® S.

Nun können die logischen Aussagen wie folgt mathematisch formuliert werden:

s(Komisch)	!=	einfarbig
v(Ernst)	!=	Klaus
s(v^-1(Walter))	=	kein
s(Witzig)	=	witzig

(1)

Identifiziert man die Mengen N, V und S jeweils mit der Menge X = { 0,1,2 }, erhält man das äquivalente mathematische Modell:

Gesucht sind eineindeutige Abbildungen

v : X ® X

und

s : X ® X

mit

s(0) != 1

v(1) != 0

s(v^-1(2)) = 0

s(2) = 2

(2)

Um einen Lösungsalgorithmus zu finden, benutzt man die Tatsache, das jede eineindeutige Abbildung einer dreielementigen Menge auf eine dreielementige Menge mit einer Permutation der Zahlen (0,1,2) identifiziert werden kann. Ein möglicher Lösungsalgorithmus kann dann wie folgt formuliert werden:

Finde alle Permutationen der Zahlen (0,1,2)
Finde zu jeder Permutation die zugehörige Abbildung
Teste die Bedingungen (2) für jede mögliche Abbildung v und jede mögliche Abbildung s>s].

Das folgende Listing enthält ein C-Programm. daß diesen Algorithmus realisiert.

Der Quelltext ist weitestgehend selbsterklärend, enthält aber einige wenige Besonderheiten, die im folgenden etwas genauer erklärt werden sollen.

Die in den Zeilen 3-5 deklarierten Aufzählungstypen n, v und s liefern implizit die bijektiven Abbildungen der entsprechenden Mengen N, V und S auf die Menge X. Somit können anstelle der Bedingungen (2) die leichter lesbaren Bedingungen (1) direkt programmiert werden (Zeilen 29-32).
Die Berechnung der inversen Abbildung v^-1(Walter) erfolgt über einen einfachen Suchalgorithmus in den Zeilen 23-27.
Um eine lesbare Ausgabe zu erzeugen, ist es erforderlich die (abstrakten) Aufzählungstypen n, v und s auf entsprechende Zeichenketten abzubilden (Zeilen 7-9,37-40).

Die Ermittlung aller Permutationen der Zahlen (0,1,2) wird getreu dem Prinzip Teile und Herrsche, aber auch unter dem Gesichtspunkt der Wiederverwendbarkeit von Softwarekomponenten in eine eigenständige Funktion permutationen(n) ausgelagert. Im weiteren werden zwei unterschiedliche Permutationsalgorithmen vorgestellt, implementiert und miteinander verglichen.

Der erste Algorithmus wird folgendermaßen formuliert:

Setze nacheinander alle noch nicht benutzten Zahlen an die nächste freie Position.
Wiederhole Schritt 1. bis alle Positionen besetzt sind.

Ein anderer Algorithmus zur Erzeugung aller Permutationen lautet:

Permutiere die Zahlen an den Positionen 0,¼,n-2.
Für alle i, i = 0,¼,n-2 tausche die Positionen n-1 und i und wiederhole Schritt 1.

Beide Algorithmen sind rekursiv, die Rekursivität des zweiten Algorithmus ist aber deutlicher zu erkennen. Für die Realisierung des ersten Algorithmus muß man sich zusätzlich die schon benutzten Zahlen merken, um sie in den weiteren Berechnungen auszuschließen. Generell scheint der zweite Algorithmus auch etwas klarer formuliert zu sein. Die folgenden Quelltexte zeigen Implementierungen dieser Algorithmen. Dabei enthalten die Funktionen append bzw. permutiere die jeweils wesentlichen Elemente der beiden Algorithmen.

Algorithmus 1:

Algorithmus 2:

Zur Verdeutlichung der Arbeitsweise der beiden Algorithmen kann man die rekursiven Funktionen durch einige geeignete Druckbefehle erweitern. Dann liefert die Berechnung der Permutationen der Zahlen (0,1,2) die folgenden Ausgaben:

Algorithmus 1:

setze 0 an pos 0 start
        setze 1 an pos 1 start
                setze 2 an pos 2 start
                                          012
                setze 2 an pos 2 ende
        setze 1 an pos 1 ende
        setze 2 an pos 1 start
                setze 1 an pos 2 start
                                          021
                setze 1 an pos 2 ende
        setze 2 an pos 1 ende
setze 0 an pos 0 ende
setze 1 an pos 0 start
        setze 0 an pos 1 start
                setze 2 an pos 2 start
                                          102
                setze 2 an pos 2 ende
        setze 0 an pos 1 ende
        setze 2 an pos 1 start
                setze 0 an pos 2 start
                                          120
                setze 0 an pos 2 ende
        setze 2 an pos 1 ende
setze 1 an pos 0 ende
setze 2 an pos 0 start
        setze 0 an pos 1 start
                setze 1 an pos 2 start
                                          201
                setze 1 an pos 2 ende
        setze 0 an pos 1 ende
        setze 1 an pos 1 start
                setze 0 an pos 2 start
                                          210
                setze 0 an pos 2 ende
        setze 1 an pos 1 ende
setze 2 an pos 0 ende

Algorithmus 2:

permutiere pos 0 bis 2 start
        permutiere pos 0 bis 1 start
                permutiere pos 0 bis 0 start
                                              012
                permutiere pos 0 bis 0 ende
        tausche pos 1 <-> 0 ( 1 <-> 0 )
                permutiere pos 0 bis 0 start
                                              102
                permutiere pos 0 bis 0 ende
        permutiere pos 0 bis 1 ende
tausche pos 2 <-> 0 ( 2 <-> 0 )
        permutiere pos 0 bis 1 start
                permutiere pos 0 bis 0 start
                                              210
                permutiere pos 0 bis 0 ende
        tausche pos 1 <-> 0 ( 1 <-> 2 )
                permutiere pos 0 bis 0 start
                                              120
                permutiere pos 0 bis 0 ende
        permutiere pos 0 bis 1 ende
tausche pos 2 <-> 1 ( 2 <-> 1 )
        permutiere pos 0 bis 1 start
                permutiere pos 0 bis 0 start
                                              021
                permutiere pos 0 bis 0 ende
        tausche pos 1 <-> 0 ( 2 <-> 0 )
                permutiere pos 0 bis 0 start
                                              201
                permutiere pos 0 bis 0 ende
        permutiere pos 0 bis 1 ende
permutiere pos 0 bis 2 ende