Skip to main content

2024 | Buch

Mathematische Grundlagen der Informatik

Mathematisches Denken und Beweisen - Eine Einführung

insite
SUCHEN

Über dieses Buch

Die mathematischen Grundlagen der Informatik werden anhand von Definitionen und Beispielen anschaulich eingeführt. Ziel des Buches, nun in einer korrigierten und aktualisierten Fassung, ist es, systematisch die für die Informatik typischen und grundlegenden mathematischen Denkweisen vorzustellen – ohne dabei auf besondere, die übliche Schulmathematik übersteigende Vorkenntnisse aufzubauen.

Inhaltsverzeichnis

Frontmatter

Grundlagen

Frontmatter
Kapitel 1. Aussagen
Zusammenfassung
Wir stellen dar, wie man Sachverhalte mathematisch exakt formulieren kann. Das ist eine Voraussetzung dafür, ihre Allgemeingültigkeit beweisen zu können. Dazu führen wir zunächst grundlegende Begriffe wie Aussagen und Aussageformen ein und betrachten, wie man Aussagen nach logischen Prinzipien verknüpfen kann.
Christoph Meinel, Martin Mundhenk
Kapitel 2. Mengen und Mengenoperationen
Zusammenfassung
Wir führen den grundlegenden Begriff der Menge ein und üben daran das Formulieren und Benutzen von Aussagen und Aussageformen. Dazu betrachten wir Beziehungen zwischen Mengen (Teilmenge, Obermenge), Operationen auf Mengen (Durchschnitt, Vereinigung, Komplement, Produkt) sowie Mengen von Mengen (Potenzmenge, Mengenfamilien).
Christoph Meinel, Martin Mundhenk
Kapitel 3. Mathematisches Beweisen
Zusammenfassung
Um sich und andere gesichert von der Allgemeingültigkeit einer Beobachtung zu überzeugen, führt man in der Mathematik Beweise. Beweise erfordern eine lückenlose Argumentation, wobei jedes der verwendeten Argumente zuvor selbst bewiesen sein muss, aus einer Definition folgen oder einer gültigen „letzten“ Tatsache, einem Axiom, bestehen muss. Übrigens werden die Mathematiker von allen anderen Wissenschaftlern um ihre Beweiskultur beneidet. Wir machen uns im Folgenden grundlegende Gedanken zum Beweisen, damit wir in den folgenden Kapiteln das Beweiseführen erlernen können.
Christoph Meinel, Martin Mundhenk
Kapitel 4. Relationen
Zusammenfassung
Beziehungen zwischen Objekten spielen im realen Leben eine große Rolle. Mathematisch lassen sie sich mit Hilfe spezieller Mengen – den so genannten Relationen – gut beschreiben. Vermittels dieser Mengenbeschreibung können Eigenschaften von Relationen untersucht werden, und es kann mit Relationen gerechnet werden (Invertierung, Komposition, usw.). Mit Hilfe spezieller Typen von Relationen (Äquivalenzrelation, Halbordnungsrelation) lassen sich die aus dem Bereich der Zahlen gut bekannten Gleichheits- und Ordnungsrelationen auf beliebige Objekte verallgemeinern.
Christoph Meinel, Martin Mundhenk
Kapitel 5. Abbildungen und Funktionen
Zusammenfassung
Abbildungen und Funktionen sind Relationen mit besonderen Eigenschaften im Hinblick auf die in Beziehungen stehenden Objekte. Wir werden uns grundlegende Eigenschaften anschauen (surjektiv, injektiv, bijektiv) und sehen, wie man mit ihnen die Größe unendlicher Mengen beschreiben kann.
Christoph Meinel, Martin Mundhenk

Techniken

Frontmatter
Kapitel 6. Grundlegende Beweisstrategien
Zusammenfassung
Mathematiker bezweifeln alles. Um sich und andere von der Richtigkeit eines Sachverhaltes zu überzeugen, verlangen sie einen mathematischen Beweis, also eine geschlossene Argumentationskette, die den sehr strengen Regeln der mathematischen Logik folgt. In diesem Kapitel werden wir Methoden besprechen, mit denen ein solcher Beweis geführt werden kann.
Christoph Meinel, Martin Mundhenk
Kapitel 7. Vollständige Induktion
Zusammenfassung
Vollständige Induktion ist häufig ein ausgezeichnetes Hilfsmittel zum Beweis von Aussagen der Form „\({\forall n \in \mathbb {N}:} \ p(n)\)“. Wir beweisen das hinter dieser Beweismethode stehende Prinzip und führen es an verschiedenen Beispielen vor.
Christoph Meinel, Martin Mundhenk
Kapitel 8. Zählen
Zusammenfassung
In diesem Kapitel befassen wir uns mit der Kombinatorik, also der Bestimmung der Anzahl der Elemente endlicher Mengen. Zuerst werden wir sehen, dass die Kenntnis, wie eine Menge aus anderen Mengen aufgebaut ist, ausgenutzt werden kann, um die Größe dieser Menge aus den Größen der beteiligten „Baustein“-Mengen zu bestimmen. Danach werden wir zählen, wie viele Möglichkeiten es gibt, Elemente einer Menge auszuwählen oder anzuordnen – eine Fragestellung, die in vielen Anwendungen der Mathematik und Informatik von grundlegender Bedeutung ist.
Christoph Meinel, Martin Mundhenk
Kapitel 9. Diskrete Stochastik
Zusammenfassung
In der diskreten Stochastik geht es um das Berechnen der Wahrscheinlichkeit, mit der ein Zufallsexperiment ein bestimmtes Ergebnis liefert. Diese Wahrscheinlichkeitsberechnungen lassen sich zurückführen auf das (normierte) Zählen von Elementen in speziellen Teilmengen eines Ereignisraums. Wir betrachten die Grundbegriffe und typische Arten von Zufallsexperimenten.
Christoph Meinel, Martin Mundhenk

Strukturen

Frontmatter
Kapitel 10. Boole’sche Algebra
Zusammenfassung
Eine Boole’sche Algebra ist eine mathematische Struktur, die unsere Vorstellungen von Aussagen und deren Verknüpfung in einem Rechenkalkül formal beschreibt. In dieser Struktur gibt es bestimmte Rechenoperationen und es gelten bestimmte Rechenregeln. Wir schauen uns verschiedene Beispiele Boole’scher Algebren an und werden sehen, dass sie „eigentlich gleich“ (isomorph) sind.
Christoph Meinel, Martin Mundhenk
Kapitel 11. Graphen und Bäume
Zusammenfassung
Graphen und Bäume werden in der Informatik zur Modellierung verwendet. Sie sind zugleich anschaulich und gut abstrahierbar. Wir geben eine Einführung, führen die grundlegenden Begriffe ein und beweisen interessante Eigenschaften.
Christoph Meinel, Martin Mundhenk
Kapitel 12. Aussagenlogik
Zusammenfassung
Aussagenlogik spiegelt die grundlegenden Ideen des korrekten Schlussfolgerns wider. Zuerst betrachten wir die Verbindung zwischen Boole’scher Algebra und Aussagenlogik. Anschließend werden wir die Resolutionsmethode vorstellen, mit der man korrektes Schlussfolgern überprüfen kann.
Christoph Meinel, Martin Mundhenk
Kapitel 13. Modulare Arithmetik
Zusammenfassung
Wir übertragen die Regeln des Rechnens mit ganzen Zahlen auf endliche Zahlenbereiche. Das ist insbesondere für das Rechnen mit Computern wichtig, die selbst bei größtem Speicher nur mit endlich vielen Zahlen umgehen können. Zur Veranschaulichung stellen wir ein weit verbreitetes und berühmtes Verschlüsselungsverfahren vor – das RSA-Verfahren.
Christoph Meinel, Martin Mundhenk
Backmatter
Metadaten
Titel
Mathematische Grundlagen der Informatik
verfasst von
Christoph Meinel
Martin Mundhenk
Copyright-Jahr
2024
Electronic ISBN
978-3-658-43136-5
Print ISBN
978-3-658-43135-8
DOI
https://doi.org/10.1007/978-3-658-43136-5

Premium Partner