Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2024 | Buch

Mengentheoretische Grundlagen Kapitel lesen Erstes Kapitel lesen

Mathematik für die Informatik

Grundlegende Begriffe, Strukturen und Anwendungen

verfasst von: Rudolf Berghammer

Verlag: Springer Fachmedien Wiesbaden

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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

Dieses Lehrbuch 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 Schulmathematik 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 5. Auflage erweitert den Inhalt um die Grundlagen der linearen Algebra.

Die Übungsaufgaben zu den einzelnen Kapitel 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.

Der Inhalt

Mengentheoretische Grundlagen • Logische Grundlagen • Allgemeine direkte Produkte und Datenstrukturen • Mathematische Beweise • Spezifikation und Programmverifikation • Spezielle Funktionen • Spezielle Relationen und gerichtete Graphen • Elementare Kombinatorik und ungerichtete Graphen • Diskrete Wahrscheinlichkeitstheorie • Generische Programmierung • Grundbegriffe algebraischer Strukturen • Formale Einführung der natürlichen Zahlen - Grundbegriffe der linearen Algebra

Mit diesem Buch gelingt der Einstieg ins Informatik-Studium

Mit diesem Buch schaffen Sie eine solide Basis für die Mathematikausbildung im Rahmen desInformatikstudiums. 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 ⊆ M ×N mit zwei beliebigen Mengen M und N sind, betrachten wir in diesem Kapitel nur Relationen des Typs R ⊆ 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 O(n glog2(n)) ist, wobei glog2(n) den ganzzahligen Anteil des dualen Logarithmus log2(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 (N,≤) 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 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
Kapitel 13. Grundbegriffe der linearen Algebra
Zusammenfassung
Die lineare Algebra (oder Vektoralgebra) ist ein wichtiges Teilgebiet der Algebra. Sie entwickelte sich unter anderem aus der algebraischen Behandlung von Problemen der Geometrie, beispielsweise, ob zwei Geraden in der Euklidschen Ebene parallel sind oder sich schneiden. Durch die Einführung von Koordinaten für Punkte, die Abstraktion von so dargestellten Punkten zu Vektoren und deren algebraische Behandlung durch Vektorräume ist es mit Hilfsmitteln der linearen Algebra in vielen Fällen möglich, solche Aufgabenstellungen rein rechnerisch zu lösen, ohne die Anschauung zu Hilfe zu nehmen. Diese rechnerischen Lösungen betreffen oft Systeme von linearen Gleichungen. Neben der grundlegenden Struktur eines Vektorraums und den entsprechenden strukturerhaltenden Funktionen spielen deshalb lineare Gleichungssysteme eine herausragende Rolle. Durch sie ergeben sich zahlreiche Anwendungen in anderen Disziplinen, auch in der Informatik. In diesem Kapitel behandeln wir nur die wichtigsten Grundbegriffe der linearen Algebra. Einige haben wir schon genannt. Dazu kommen noch Matrizen, welche es beispielsweise erlauben, lineare Gleichungssysteme kompakt darzustellen und ihre Lösungsmengen zu analysieren.
Rudolf Berghammer
Backmatter
Metadaten
Titel
Mathematik für die Informatik
verfasst von
Rudolf Berghammer
Copyright-Jahr
2024
Electronic ISBN
978-3-658-44149-4
Print ISBN
978-3-658-44148-7
DOI
https://doi.org/10.1007/978-3-658-44149-4

Premium Partner

    Bildnachweise