Vorwort

Die sehr natürliche Frage "wozu noch eine Einführung?" kann man relativ leicht beantworten: Die vorhandenen, in vieler Hinsicht nützlichen Lehrbücher sprechen die spezifischen Bedürfnisse eines Informatikers oft nicht ausreichend an. Was man in der Einführungen für Informatiker vermisst, ist zum Beispiel eine nicht-traditionelle, "Informatik-orientierte" Sichtweise der klassischen mathematischen Themen. Wie kann man aus einem mathematischen Beweis einen Algorithmus erhalten? Stichwort: "Das Prinzip des maximalen Gegenbeispiels". Was hat mathematische Induktion mit dem Entwurf von Algorithmen zu tun? Stichwort: Dynamisches Programmieren. Wie zeigt man, dass ein Objekt existiert, ohne ein solches Objekt mühsam konstruieren zu müssen? Stichwort: Taubenschlagprinzip und die probabilistische Methode. Was hat der Chinesische Restsatz in der Informatik zu suchen? Stichwort: "Fingerprinting". Was hat der Rang einer Matrix mit ihrem Informationsgehalt zu tun? Stichwort: Kommunikationskomplexität. Wie kann man die lineare Unabhängigkeit benutzen, um die Anzahl der Elemente in einer Menge abzuschätzen? Stichwort: Lineare-Algebra-Methode.

Im Vergleich zur Mathematik ist die Informatik nur ein kleines, wenn auch sehr rasch wachsendes "Kind", das gerade laufen lernt. Das "Kind" ist zur Zeit mit sehr schwierigen Problemen konfrontiert, für deren Lösung mathematische Werkzeuge dringend benötigt werden. Weitgehende Verallgemeinerungen in der Informatik stehen noch nicht auf der Tagesordnung! Aus diesem Grund habe ich ganz bewusst auf einige Verallgemeinerungen verzichtet und die Dinge "so wie sie sind" dargestellt. Aus demselben Grund bin ich sehr sparsam mit Bezeichnungen und mit der Einführung allgemeinerer Konzepte umgegangen: Oft steckt hinter einer komplizierten Formel oder einem abstrakten Konzept ein eigentlich einfacher und intuitiv klarer Sachverhalt. Daher könnte das Buch auch Mathematik ganz konkret heißen.

Mein Ziel war also, einen Text zu schreiben, der

• sich ganz pragmatisch auf die tatsächlichen Bedürfnisse eines Informatikers beschränkt;
• relativ kurz und trotzdem ausreichend für die späteren Theorie-Vorlesungen ist;
• möglichst viele Anhaltspunkte gibt ("warum ist ein Begriff so und nicht anders definiert, was steckt dahinter, wozu ist er gut?") -- dieser Aspekt könnte auch für diejenigen nützlich sein, die "normale" Mathe-Vorlesungen besuchen, um wieder festen Boden unter den Füßen zu bekommen;
• ein Gesamtbild der für die Informatik relevanten Mathematik darstellt -- wenn nötig, kann man später die Feinheiten leicht in "echten" Mathematikbüchern nachschlagen;
• die Sache naiv, so wie sie ist, darstellt -- keine mathematischen Besonderheiten, mit denen die meisten Informatiker nie konfrontiert werden;
• nur Schulkenntnise voraussetzt und für einen Schulabgänger bereits im ersten Semester (mit etwas Anstrengung) vermittelbar ist;
• sich auch für den Bachelor-Studiengang eignet.

Dieser Text ist aus meiner Vorlesung "Mathematische Grundlagen der Informatik" für das erste Semester an der Universität Frankfurt entstanden. Was muss man in einen solchen, durch ein Semester beschränkten "Rucksack" packen, damit Theorie-Vorlesungen erfolgreich absolviert werden können? Daher dieser "Pragmatismus" in der Auswahl des Stoffes.

Natürlich wird der Leser von Zeit zu Zeit fehlende Details in anderen Mathematik-Bücher nachschlagen müssen. Es ist absolut unmöglich, die ganze, mehr als 2000 Jahre alte Mathematik auf ca. 300 Seiten zu "komprimieren": Für jeden der fünf Teile in diesem Buch gibt es mindestens zwei, drei umfassende Bücher. Mein Buch stellt eher einen Begleiter dar, der den Leser durch den "Dschungel" der für die Informatik relevanten Mathematik führen sollte.

Das Buch enthält viele motivierende Anwendungen und Beispiele, von denen einige erstmals in einem Lehrbuch vorkommen. Insgesamt machen die Beispiele den Großteil des Buches aus. Einige Abschnitte sind mit * als optional markiert -- sie stellen vertiefendes Material dar.

Musterlösungen für die Aufgaben zusammen mit weiteren Zusatzmaterialien befinden sich auf der Webseite des Buches. Daher eignet sich das Buch auch für das Selbststudium.

An dieser Stelle möchte ich sehr herzlich Georg Schnitger, Maik Weinard, Markus Schmitz-Bonfigt, Uli Laube und natürlich meinen Studenten für ihre Interesse, wertvolle Hinweise und zahlreiche Verbesserungsvorschläge danken. Gregor Gramlich bin ich insbesondere dankbar -- seine Hilfe während der Arbeit an der letzten Version des Buches war entscheidend. Mein Dank geht auch insbesondere an Ingo Wegener für die Unterstützung des Projektes und an den Lektor vom Teubner-Verlag, Ulrich Sandten, für die hervorragende Zusammenarbeit.