Skip to main content
main-content

Über dieses Buch

Mathematik für die Informatik: Dieses Buch bringt Ihnen die Grundlagen bei

Das Buch bietet eine Einführung in die grundlegenden Begriffe und Strukturen der Mathematik, welche am Anfang eines Informatikstudiums relevant sind. Weiterhin demonstriert es Anwendungen von mathematischen Konzepten und Methoden in der Informatik. Diese betreffen insbesondere formale Methoden der Programmverifikation und -entwicklung und den Entwurf von generischen Programmen.

Ein spezielles Konzept mit einer leicht verständlichen Vermittlung des Stoffs, vielen Beispielen mit Rückgriffen auf die Schul-Mathematik und detaillierten Beweisen (verbunden mit der Erklärung des logischen Hintergrunds) erleichtert den Einstieg in die Mathematik an einer wissenschaftlichen Hochschule. Dadurch werden die Studierenden auch auf spätere Begriffe und tiefergehende Anwendungen der Mathematik in der Informatik gut vorbereitet.

Die 157 Übungsaufgaben, aufgeteilt in die 12 einzelnen Kapitel, sollen helfen, das Erlernte zu festigen und zu kontrollieren. Zahlreiche Lösungsvorschläge am Ende des Buchs ermöglichen die Überprüfung der eigenen Lösungen.

Mit diesem Buch gelingt der Einstieg ins Informatik-Studium

Mit diesem Buch schaffen Sie eine solide Basis für die Mathematikausbildung im Rahmen des Informatikstudiums. Zudem sind Sie durch die vorgestellten Problemstellungen in der Lage, selbstständig mathematische Konzepte und Methoden anzuwenden. Zielgruppen dieses Buchs über Mathematik in der Informatik sind Bachelor-Studierende in den ersten Studiensemestern folgender Fachbereiche:

Informatik

Mathematik

Ingenieurwissenschaften

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Mengentheoretische Grundlagen

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 2. Logische Grundlagen

Zusammenfassung
Neben der Mengenlehre ist die Logik das zweite Fundament der Mathematik. Die Mengenlehre wird gebraucht, um die Objekte, für die man sich in der Mathematik interessiert, zu konstruieren, zu modellieren und zu manipulieren. Bisher kennen wir Paare, Relationen und Funktionen. Später werden z.B. noch Tupel, lineare Listen, Bäume und Graphen dazukommen.Die Logik wird gebraucht, wenn in der Mathematik Beweise geführt werden,also in einer gewissen (logischen) Art undWeise argumentiert wird, um zu zeigen, dass eine Aussage wahr ist. Im Folgenden gehen wir auf die logischen Grundlagen der Mathematik ein. Auch hier wählen wir wieder einen naiven Zugang. Für die formale mathematische Logik gibt es im Laufe des Informatik-Studiums eigene Vorlesungen.
Rudolf Berghammer

Kapitel 3. Allgemeine direkte Produkte und Datenstrukturen

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 4. Mathematische Beweise

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 5. Anwendung: Spezifikation und Programmverifikation

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 6. Spezielle Funktionen

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 7. Spezielle Relationen und gerichtete Graphen

Zusammenfassung
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 ×N mit zwei beliebigen Mengen M und N sind, betrachten wir in diesem Kapitel nur Relationen des Typs R \(\subseteq \) M ×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.
Rudolf Berghammer

Kapitel 8. Elementare Kombinatorik und ungerichtete Graphen

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 9. Diskrete Wahrscheinlichkeitstheorie

Zusammenfassung
Wahrscheinlichkeiten und Methoden der Statistik spielen in der Informatik eine immer größere Rolle. Am Ende von Kapitel 10 werden wir skizzieren, wie sie beispielsweise bei der Analyse von evolutionären Algorithmen eingesetzt werden. Ein evolutionärer Algorithmus ist ein Spezialfall eines randomisierten Algorithmus. Solch ein Algorithmus versucht, mit Hilfe zufällig ausgewählter Zwischenschritte zu einem gegebenen Problem eine im Mittel gute bzw. korrekte Lösung zu finden. Das bekannte Quicksort-Sortierverfahren ist ein weiteres Beispiel für einen randomisierten Algorithmus. Mit Hilfe der Wahrscheinlichkeitstheorie kann man zeigen, dass bei n > 0 zu sortierenden Objekten die erwartete Laufzeit \(\mathcal{O} (n\,glog_2(n))\) ist, wobei \(glog_2(n)\) den ganzzahligen Anteil des dualen Logarithmus \(log_2(n)\) von n bezeichnet. In diesem Kapitel stellen wir die Grundlagen der Wahrscheinlichkeitstheorie vor. Weil uns die Hilfsmittel aus der Analysis und der mathematischen Maßtheorie nicht zur Verfügung stehen, beschränken wir uns auf die sogenannte diskrete Wahrscheinlichkeitstheorie. Diese ist für die meisten Anwendungen von Wahrscheinlichkeiten in der Informatik ausreichend.
Rudolf Berghammer

Kapitel 10. Anwendung: Generische Programmierung

Zusammenfassung
Abstraktion und Wiederverwendung sind zwei bestimmende Faktoren beim mathematischen Arbeiten. Bei einer Abstraktion versucht man, durchWeglassen von als unwesentlich erachteten Einzelheiten zum wesentlichen Teil eines gerade behandelten Sachverhalts (etwa eines mathematischen Problems) vorzudringen. Typische Abstraktionen sind algebraische Strukturen, die wir in Kapitel 11 behandeln werden. 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.
Rudolf Berghammer

Kapitel 11. Grundbegriffe algebraischer Strukturen

Zusammenfassung
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.
Rudolf Berghammer

Kapitel 12. Formale Einführung der natürlichen Zahlen

Zusammenfassung
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 Kapitel 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 (\({\mathbb{N}}\),\(\le \)) 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 vonder Struktur der natürlichen Zahlen(in der angegebenen Weise) 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.
Rudolf Berghammer

Backmatter

Weitere Informationen

Premium Partner