Mathematik für die Informatik

Die Mengenlehre ist ein Teilgebiet der Mathematik. Sie wurde vom deutschen Mathematiker Georg Cantor (1845-1918) etwa zwischen 1870 und 1900 begründet. Heutzutage baut die gesamte moderne und wissenschaftliche Mathematik, wenn sie formal axiomatisch betrieben wird, auf der axiomatischen Mengenlehre auf. Für Anfänger in der Mathematik ist ein axiomatischer Mengenbegriff sehr schwer zu verstehen. Deshalb wählen wir in diesem Kapitel einen, wie man sagt, naiven Zugang zu Mengen. Man spricht in diesem Zusammenhang auch von naiver Mengenlehre.

In Abschnitt 1.4 haben wir direkte Produkte M × N als Mengen von Paaren (a, b) von Objekten eingeführt. Paare bestehen aus genau zwei Komponenten. In diesem Kapitel führen wir zuerst Tupel ein, die aus endlich vielen Komponenten bestehen, und, als deren Verallgemeinerungen, dann noch Folgen und Familien. Mengen von Tupeln nennt man allgemeine direkte Produkte. Schließlich zeigen wir noch, wie man mit Hilfe von direkten Produkten zwei in der Informatik sehr wichtige Datenstrukturen formal mathematisch erklären kann, nämlich lineare Listen und Binärbäume.

Beweise zu führen ist das Kerngeschäft der Mathematik. In ihnen wird mit logischen Mitteln nachgewiesen, dass eine mathematische Aussage gültig ist. Es gibt verschiedene Stile, um mathematische Beweise aufzuschreiben. Früher, als die Formelsprache der Mathematik noch nicht oder noch nicht so weit wie heute entwickelt war, waren Beweise hauptsächlich Argumentationen in der Umgangssprache; ein Argumentieren, wie es sich aus der Philosophie entwickelt hat. Heutzutage sind mathematische Beweise in der Regel viel formaler, insbesondere dann, wenn sie durch Computerprogramme überprüft werden sollen. Auf den Gebrauch der Umgangssprache wird aber nicht völlig verzichtet, da umgangssprachliche Formulierungen die Verständlichkeit und Lesbarkeit oft sehr verbessern. In diesem Kapitel wollen wir die wichtigsten Beweistechniken vorstellen und anhand von ausgewählten Beispielen demonstrieren. Dabei gehen wir auch auf die den Beweistechniken zugrundeliegenden logischen Regeln ein.

Eine der Hauptaufgaben der Informatik ist das Entwerfen von Algorithmen, also von effektiv ausführbaren Verfahren, die eine bestimmte Klasse von verwandten Problemen lösen. Von der höheren Schule her kennt man solche Verfahren in der Regel aus dem Geometrie-Unterricht. Typische Algorithmen sind hier das Halbieren einer Strecke oder das Fällen eines Lots nur unter Verwendung von Zirkel, Lineal und Bleistift. Die Informatik ist insbesondere an solchen Algorithmen interessiert, die mit Hilfe eines Computers ausgeführt werden können. Dazu werden sie in „Kunstsprachen“ formuliert, welche von Computern verstanden werden. Diese Kunstsprachen heißen Programmiersprachen, die in ihnen formulierten Algorithmen nennt man Programme und als Programmieren bezeichnet man das Entwerfen und Niederschreiben von Programmen. Letztere sollen natürlich eine Reihe günstiger Eigenschaften besitzen. Etwa sollen sie so geschrieben sein, dass man sie gut lesen und verstehen kann. Die entscheidende Eigenschaft aber, die Programme zu erfüllen haben, ist ihre Korrektheit, also die Eigenschaft, dass sie die Probleme, zu deren Lösung sie entworfen wurden, auch wirklich lösen. Insbesondere dürfen sie keine falschen Resultate produzieren. Um Anwendungen von den bisher behandelten mathematischen Konzepten in der Informatik zu demonstrieren, zeigen wir in diesem Kapitel ansatzweise, wie man mittels Mathematik die Korrektheit von Programmen formal beweisen kann. Diesem Gebiet ist ein großer Teil eines Informatik-Studiums gewidmet. Wir beschränken uns auf die imperative Programmierung.

In Abschnitt 1.4 haben wir Funktionen als spezielle Relationen eingeführt und auch einige Sprech- und Schreibweisen festgelegt. Bisher haben wir Funktionen aber nur zu Beispielszwecken verwendet, etwa um Sachverhalte zu beschreiben oder Möglichkeiten zu schaffen, vorgegebene Objekte zu manipulieren. Insbesondere bei den zweiten Anwendungen sprachen wir dann oftmals von Operationen statt von Funktionen, um diesen Charakter zu betonen. Man vergleiche mit den Operationen auf den linearen Listen oder den knotenmarkierten Binärbäumen. In diesem Kapitel studieren wir nun den Funktionsbegriff näher. Zuerst befassen wir uns mit einigen grundlegenden Eigenschaften von Funktionen. Dann vergleichen wir mit Hilfe von speziellen Funktionen die Kardinalitäten beliebiger (also auch nichtendlicher) Mengen. Und schließlich untersuchen wir noch einige Klassen von speziellen konkreten Funktionen, die für die Informatik wichtig sind, wenn man sich etwa mit der Laufzeit von Algorithmen beschäftigt.

Im letzten Kapitel haben wir einige Klassen und Eigenschaften von Funktionen im Detail behandelt, also, genau genommen, von speziellen Relationen, nämlich eindeutigen und totalen. Nun betrachten wir weitere wichtige Klassen von Relationen und einige ihrer Eigenschaften näher. Im Gegensatz zu den Funktionen, die in ihrer Urform Relationen des Typs \( f \subseteq M \times N \) mit zwei beliebigen Mengen M und N sind, betrachten wir in diesem Kapitel nur Relationen des Typs \( R \subseteq M \times M \), also Relationen, bei denen Quelle und Ziel gleich sind. Solche Relationen auf einer Menge werden auch homogen genannt. Homogene Relationen kann man anschaulich gut durch Pfeildiagramme darstellen und zwar durch solche, wie wir sie in Abschnitt 1.4 ursprünglich eingeführt haben. In der Sprache der Mathematik werden diese Pfeildiagramme auch gerichtete Graphen genannt. Diesen Strukturen, die in der Informatik insbesondere zu Modellierungszwecken eingesetzt werden, ist der letzte Teil des Kapitels gewidmet.

Im letzten Abschnitt des vorhergehenden Kapitels wurden gerichtete Graphen behandelt. Dies sind im Prinzip nichts anderes als Relationen auf Knotenmengen, deshalb geschah die Zuordnung zum Kapitel über Relationen. Es gibt auch noch ungerichtete Graphen, bei denen die Verbindungen zwischen den Knoten keine Richtung besitzen, graphisch also keine Pfeile mit Spitzen an einem Ende darstellen. In diesem Kapitel behandeln wir nun die ungerichteten Graphen. Diese stehen oft in Verbindung mit Kombinatorik, also der Teildisziplin der Mathematik, die sich mit Aufzählungen von Möglichkeiten, Größen bestimmter endlicher Mengen usw. beschäftigt. Wir beginnen im ersten Abschnitt des Kapitels mit einigen elementaren Begriffen und Fragestellungen der Kombinatorik.

Große Teile der Mathematik und der theoretischen Informatik untersuchen mathematische Strukturen und wenden solche zur Lösung von Problemen an. Sehr allgemein betrachtet besteht eine mathematische Struktur aus einer Liste von nichtleeren Mengen, genannt Trägermengen, von Elementen aus den Trägermengen, genannt Konstanten, und von mengentheoretischen Konstruktionen über den Trägermengen. Bisher kennen wir etwa geordnete Mengen, gerichtete Graphen und ungerichtete Graphen als mathematische Strukturen. In den ersten beiden Fällen gibt es genau eine Trägermenge, keine Konstanten und genau eine mengentheoretische Konstruktion, welche jeweils eine Relation über der Trägermenge ist. Beim dritten Fall gibt es ebenfalls genau eine Trägermenge und keine Konstanten. Die einzige mengentheoretische Konstruktion ist nun jedoch eine spezielle Teilmenge der Potenzmenge der Trägermenge. In diesem Kapitel behandeln wir fast nur algebraische Strukturen. Dies heißt konkret, dass die mengentheoretischen Konstruktionen Funktionen über den Trägermengen sind. Wir beschränken uns weiterhin größtenteils auf den Fall einer einzigen Trägermenge. Solche Strukturen werden auch homogen genannt. Alle speziell behandelten homogenen algebraischen Strukturen stammen aus der klassischen Algebra. Auf allgemeinere mathematische Strukturen gehen wir im letzten Abschnitt des Kapitels noch kurz ein. Wir hoffen, dass die Leserin oder der Leser durch den gewählten allgemeinen Ansatz dieses Kapitels gut auf die Verwendung allgemeiner mathematischer Strukturen vorbereitet wird.

Abstraktion und Wiederverwendung sind zwei bestimmende Faktoren beim mathematischen Arbeiten. Bei einer Abstraktion versucht man, durch Weglassen von als unwesentlich erachteten Einzelheiten zum wesentlichen Teil eines gerade behandelten Sachverhalts (etwa eines mathematischen Problems) vorzudringen. Typische Abstraktionen sind die algebraischen Strukturen von Kapitel 9. Auch Graphen werden oft als Mittel zur Abstraktion verwendet. Abstraktion ist sehr häufig mit Wiederverwendung verbunden. Hat man z.B. ein konkretes Problem auf Zahlen durch Weglassen von Einzelheiten in ein abstraktes Problem über Gruppen überführt und dieses gelöst, so gilt diese Lösung für alle Gruppen. Sie kann also beim Lösen von Problemen auf allen Gruppen verwendet werden, also auch auf solchen Gruppen, die mit Zahlen nichts oder nur wenig zu tun haben, wie beispielsweise die Gruppe aller bijektiven Funktionen auf einer Menge oder die Gruppe, welche dadurch entsteht, dass man die Punkte der Euklidischen Ebene um den Ursprung (0, 0) mit einem fest vorgegebenen Winkel dreht. Abstraktion und Wiederverwendung sind mittlerweile auch bestimmende Faktoren beim Algorithmenentwurf und Programmieren geworden. Bei der generischen Programmierung versucht man z.B., Programme unter Verwendung von Variablen (oder Parametern) für wesentliche Dinge so allgemein wie möglich zu entwerfen, um sie in möglichst vielen unterschiedlichen Situationen einsetzen zu können. Als Weiterführung von Kapitel 5 und unter Verwendung der Begriffe der letzten Kapitel behandeln wir in diesem Kapitel zwei Beispiele von generischen imperativen Programmen, welche minimale bzw. maximale Teilmengen berechnen, die eine vorgegebene Eigenschaft erfüllen. Wir motivieren die Programme durch Beispiele mit Graphen und wenden sie auf graphentheoretische Probleme an. Dadurch erweitern wir auch die für die Informatik wichtige Graphentheorie im Hinblick auf Anwendungen.

In Kapitel 1 haben wir die von der Schule her bekannten Mengen der natürlichen Zahlen, ganzen Zahlen, rationalen Zahlen und reellen Zahlen eingeführt. Dies geschah in sehr informeller Weise und bei der Verwendung dieser Mengen und ihrer Operationen und Relationen haben wir bisher immer ein intuitives Verständnis von Zahlen vorausgesetzt. In Kapitel 1 haben wir auch erwähnt, dass es ein allgemeines Bestreben der an den Grundlagen orientierten Teile der Mathematik ist, alles, was man an mathematischen Objekten konstruiert, auf Mengen zurückzuführen. In diesem Anhang zeigen wir, wie man natürliche Zahlen in der Sprache der Mengenlehre ausdrücken kann. Dieser Zahlenbereich ist eigentlich der einzige, von dem wir bisher wesentliche (und in der Schule wahrscheinlich nicht explizit so angesprochene) Eigenschaften verwendet haben, etwa, dass die geordnete Menge \( \left( {{\mathbf{\mathbb{N}}},\, \le } \right) \) linear und Noethersch geordnet ist. Wir beginnen im ersten Abschnitt mit einer axiomatischen Einführung der natürlichen Zahlen, also mit der Forderung von Eigenschaften, weil eine solche Vorgehensweise den Zugang wesentlich erleichtert. Im Prinzip wird dann durch die im zweiten Abschnitt angegebene mengentheoretische Konstruktion bewiesen, dass es mathematische Strukturen gibt, die die Eigenschaften des ersten Abschnitts erfüllen. Wir werden sogar zeigen, dass alle diese Strukturen isomorph sind, man also von der Struktur der natürlichen Zahlen (in der angegebenenWeise) sprechen kann. In den letzten zwei Abschnitten zeigen wir dann, wie man von dieser Struktur der natürlichen Zahlen zu den Operationen und Relationen kommt, die wir von den natürlichen Zahlen her kennen, und auch die bekannten bzw. von uns bisher verwendeten Eigenschaften gelten.

Aufgrund des einführenden Charakters werden alle in dem Text vorgestellten mathematischen Gebiete nur auf relativ elementarem Niveau behandelt. Nachfolgend geben wir zu den einzelnen Kapiteln noch einige Literaturhinweise an, in denen der behandelte Stoff teilweise beträchtlich vertieft wird und auch viele weitere Beispiele zu finden sind. Wir beschränken uns dabei auf (in der Regel) Lehrbücher neueren Datums und vermeiden Hinweise auf Originalartikel aus Zeitschriften oder Konferenzbänden. Es ist jedoch auch reizvoll und sogar für einen Anfänger manchmal hilfreich, einen Blick in Originalarbeiten zu werfen.