Mathematik für die Informatik: Grundlegende Begriffe, Strukturen und ihre Anwendung (German Edition)

Description

Mathematik und Informatik: Dieses Buch bringt beide Disziplinen zusammen Sie haben Ihr Studium begonnen oder möchten den Übergang von Schule zu Hochschule erfolgreich meistern? Dann ist „Mathematik für die Informatik“ die ideale Empfehlung. Das Buch von Rudolf Berghammer bringt Ihnen die Logik der Informatik näher und verknüpft sie mit den wichtigsten Strukturen und Begriffen aus der Mathematik. Im Fokus stehen die gängigen Vorgehensweisen der Programmkonzeption und -verifikation. So beschäftigen Sie sich mit diesem Buch schon frühzeitig mit den tiefergehenden Strukturen der Mathematik in der Informatik. Der Autor ist darauf bedacht, Ihnen die Inhalte nachvollziehbar und verständlich zu vermitteln. Dazu tragen neben ausführlich erklärten Beispielen und Beweisen vor allen Dingen die insgesamt 142 Übungsaufgaben inklusive Lösungen bei. Arbeiten Sie sich von den Grundlagen zu spezifischen Themen vor Um Ihnen den Einstieg zu erleichtern, steht zunächst ein kleiner Ausflug in die Schulzeit an. Mit Blick auf die Mathematik der Informatik wiederholen Sie mit diesem Buch noch einmal kurz und kompakt die Grundlagen der Mengentheorie. Hier stehen beispielsweise Relationen, Potenzmengen und Ergänzungen zum Funktionsbegriff auf dem Programm. Anschließend geht das Buch „Mathematik für die Informatik“ weiter in die Tiefe: • Ungerichtete und gerichtete Graphen • Grundlagen algebraischer Strukturen • Logische Grundlagen • Elementare Kombinatorik • Generische Programmierung Durch diese systematische Verknüpfung von Mathematik und Informatik ist dieses Buch besonders für Studierende in Bachelor-Studiengängen der Bereiche Mathematik, Informatik und Ingenieurwissenschaften ein hilfreicher Begleiter während des Studieneinstiegs. Einleitung zur ersten Auflage Vorwort zur zweiten Auflage Vorwort zur dritten Auflage Vorwort zur vierten Auflage Inhalt 1 Mengentheoretische Grundlagen 1.1 Der Cantorsche Mengenbegriff 1.1.1 Definition: Menge (G. Cantor) 1.1.2 Definition: explizite Darstellung 1.1.3 Beispiele: explizite Darstellungen 1.1.4 Definition: Aussage (Aristoteles) 1.1.5 Definition: deskriptive Mengenbeschreibung 1.1.6 Beispiele: deskriptive Mengenbeschreibungen 1.1.7 Definition: Enthaltenseinsrelation 1.1.8 Definition: Zahlenmengen N,Z,Q,R 1.1.9 Festlegung: deskriptive Darstellung mit Typisierung 1.1.10 Definition: Inklusion, echte Inklusion, Gleichheit 1.1.11 Satz: Reflexivität, Antisymmetrie, Transitivität 1.1.12 Definition: leere Menge 1.1.13 Beispiele: Inklusionen, Gleichheiten 1.2 Einige Konstruktionen auf Mengen 1.2.1 Definition: binäre Vereinigung, binärer Durchschnitt, Differenz 1.2.2 Beispiele: Vereinigungen, Durchschnitte, Differenzen 1.2.3 Satz: Inklusion, Vereinigung, Durchschnitt 1.2.4 Satz: Kommutativität, Assoziativität, Distributivität 1.2.5 Definition: beliebige Vereinigung und beliebiger Durchschnitt 1.2.6 Satz: Einschließungseigenschaft 1.2.7 Satz: rekursives Vereinigen und Schneiden 1.2.8 Definition: indizierte Vereinigung und indizierter Durchschnitt 1.2.9 Satz: Eigenschaften der Mengendifferenz 1.2.10 Satz: Eigenschaften des Komplements 1.3 Potenzmengen und Kardinalitäten 1.3.1 Definition: Potenzmenge 1.3.2 Beispiele: Potenzmengen 1.3.3 Satz: Konstruktion der Potenzmenge 1.3.4 Beispiel: Konstruktion der Potenzmenge 1.3.5 Definition: Endlichkeit einer Menge 1.3.6 Definition: Kardinalität 1.3.7 Satz: Kardinalitätsformel 1.3.8 Beispiel: Kardinalität 1.3.9 Satz: Kardinalität der Potenzmenge 1.4 Relationen und Funktionen 1.4.1 Definition: Paar, binäres direktes Produkt 1.4.2 Bemerkung: Zermelo-Mengenkomprehension 1.4.3 Satz: Kardinalität von direkten Produkten 1.4.4 Definition: Relation 1.4.5 Beispiele: Relationen 1.4.6 Festlegung: Spezifikation von Relationen 1.4.7 Definition: eindeutige und totale Relation 1.4.8 Definition: Funktion 1.4.9 Beispiele: Funktionen 1.4.10 Definition: Gleichheit von Paaren 1.4.11 Satz: Gleichheit von Funktionen 1.5 Ergänzungen zum Funktionsbegriff 1.6 Übungsaufgaben 1.6.1 Aufgabe 1.6.2 Aufgabe 1.6.3 Aufgabe 1.6.4 Aufgabe 1.6.5 Aufgabe 1.6.6 Aufgabe 1.6.7 Aufgabe 1.6.8 Aufgabe 1.6.9 Aufgabe 1.6.10 Aufgabe 1.6.11 Aufgabe 1.6.12 Aufgabe 1.6.13 Aufgabe 2 Logische Grundlagen 2.1 Sprache und Ausdrucksweise der Mathematik 2.1.1 Definition: Konstruktionen der mathematischen Formelsprache 2.1.2 Festlegung: Quantoren mit typisierten Variablen 2.2 Grundlagen der Aussagenlogik 2.2.1 Definition: Formeln der Aussagenlogik 2.2.2 Beispiele: aussagenlogische Formeln 2.2.3 Definition: Wahrheitswerte 2.2.4 Definition: Bedeutung der Junktoren 2.2.5 Beispiel: Berechnung des Wahrheitswerts einer Formel 2.2.6 Definition: logische Äquivalenz 2.2.7 Satz: grundlegende logische Äquivalenzen 2.2.8 Satz: logische Äquivalenz und Wahrheitswert 2.2.9 Satz: weitere logische Äquivalenzen 2.2.10 Beispiele: Beweise von Mengengleichheiten 2.2.11 Definition: logische Implikation 2.2.12 Satz: logische Äquivalenz und logische Implikation 2.3 Grundlagen der Prädikatenlogik 2.3.1 Beispiele: Formeln der Prädikatenlogik 2.3.2 Beispiel: Mehrdeutigkeit bei Umgangssprache 2.3.3 Festlegung der Prädikatenlogik (Skizze) 2.3.4 Beispiele: Wahrheitswerte von Formeln 2.3.5 Definition: freie Variable, logische Äquivalenz 2.3.6 Satz: logische Äquivalenz und Wahrheitswert 2.3.7 Beispiele: Tautologien und Kontradiktionen 2.3.8 Bemerkung: Sätze in der mathematischen Umgangssprache 2.3.9 Satz: Regeln für Quantoren 2.3.10 Beispiele: Umformungen prädikatenlogischer Formeln 2.4 Die Grenzen des naiven Mengenbegriffs 2.5 Übungsaufgaben 2.5.1 Aufgabe 2.5.2 Aufgabe 2.5.3 Aufgabe 2.5.4 Aufgabe 2.5.5 Aufgabe 2.5.6 Aufgabe 2.5.7 Aufgabe 2.5.8 Aufgabe 2.5.9 Aufgabe 2.5.10 Aufgabe 2.5.11 Aufgabe 2.5.12 Aufgabe 2.5.13 Aufgabe 2.5.14 Aufgabe 2.5.15 Aufgabe 2.5.16 Aufgabe 3 Allgemeine direkte Produkte und Datenstrukturen 3.1 Tupel, Folgen und Familien 3.1.1 Definition: Tupel und allgemeines direktes Produkt 3.1.2 Bemerkung 3.1.3 Satz: Kardinalität direkter Produkte 3.1.4 Sprechweisen: Stelligkeit und Wertigkeit 3.1.5 Beispiele: Stelligkeit und Wertigkeit von Funktionen 3.1.6 Definition: komponentenweise Gleichheit 3.1.7 Definition: Folge 3.2 Lineare Listen 3.2.1 Definition: leeres Tupel 3.2.2 Definition: lineare Liste, nichtleere und leere Liste 3.2.3 Definition: Linksanfügen 3.2.4 Definition: Operationen auf linearen Listen 3.2.5 Beispiele: Operationen auf linearen Listen 3.2.6 Satz: Anzahl von Listen einer maximalen Länge 3.2.7 Beispiel: Auto-Kennzeichen 3.3 Knotenmarkierte Binärbäume 3.3.1 Beispiele: knotenmarkierte Binärbäume 3.3.2 Definition: knotenmarkierter Binärbaum 3.3.3 Definition: Baumkonstruktion 3.3.4 Definition: Baumoperationen 3.3.5 Beispiel: Baumoperationen 3.4 Zur induktiven Definition von Mengen 3.5 Übungsaufgaben 3.5.1 Aufgabe 3.5.2 Aufgabe 3.5.3 Aufgabe 3.5.4 Aufgabe 3.5.5 Aufgabe 3.5.6 Aufgabe 3.5.7 Aufgabe 3.5.8 Aufgabe 3.5.9 Aufgabe 3.5.10 Aufgabe 3.5.11 Aufgabe 4 Mathematische Beweise 4.1 Direkte Beweise 4.1.1 Satz: Summenformel von C.F. Gauß 4.1.2 Lemma 4.1.3 Satz: Fixpunktsatz von B. Knaster 4.2 Indirekte Beweise 4.2.1 Satz: ungerade Summen 4.2.2 Satz: ganzzahliger Anteil der Quadratwurzel 4.3 Beweise durch Widerspruch 4.3.1 Satz (Euklid) 4.3.2 Festlegung 4.3.3 Satz (Euklid) 4.3.4 Satz (Euklid) 4.3.5 Satz: Schubfachprinzip 4.3.6 Beispiele: Widerlegen durch Gegenbeispiele 4.4 Induktionsbeweise 4.4.1 Satz: vollständige Induktion 4.4.2 Sprechweisen 4.4.3 Satz: vollständige Induktion, variabler Induktionsbeginn 4.4.4 Satz: Teilbarkeit durch 6 4.4.5 Satz: Summenformel von C.F. Gauß 4.4.6 Satz: Potenzierungsregel 4.4.7 Satz: Kardinalität der Potenzmenge 4.4.8 Satz: Listeninduktion 4.4.9 Satz: Eigenschaften der Konkatenation 4.4.10 Satz: Bauminduktion 4.5 Einige Hinweise zum Finden von Beweisen 4.5.1 Von beiden Seiten her rechnen 4.5.2 Beispiel: Aussagenlogik 4.5.3 Einfache Lösungen bevorzugen 4.5.4 Reduzierend vorgehen und dabei so wenig wie möglich verstärken 4.5.5 Beispiel: Potenzmenge 4.5.6 Beispiel: Mittelwerte 4.5.7 Bezeichnungskollisionen auflösen 4.5.8 Beispiel: nochmals Potenzmenge 4.5.9 Der Quantorenreihenfolge folgen 4.5.10 Beispiel: Grenzwert einer Folge 4.5.11 Sinnvolle Fallunterscheidungen einführen 4.5.12 Beispiel: Absolutbetrag 4.5.13 Beispiel: ganzzahliger Anteil des dualen Logarithmus 4.5.14 Behauptung gegebenenfalls verallgemeinern 4.5.15 Beispiel: Entrekursivierung 4.6 Übungsaufgaben 4.6.1 Aufgabe 4.6.2 Aufgabe 4.6.3 Aufgabe 4.6.4 Aufgabe 4.6.5 Aufgabe 4.6.6 Aufgabe 4.6.7 Aufgabe 4.6.8 Aufgabe 4.6.9 Aufgabe 4.6.10 Aufgabe 4.6.11 Aufgabe 4.6.12 Aufgabe 5 Anwendung: Spezifikation und Programmverifikation 5.1 Imperative Programmierung 5.1.1 Beispiel: Ausführung von Zuweisungen 5.1.2 Definition: Anweisungen der Kernsprache 5.1.3 Beispiel: imperatives Programm über Zahlen 5.1.4 Beispiel: imperatives Programm über linearen Listen 5.2 Partielle Korrektheit und ein Verifikationskalkül 5.2.1 Definition: Hoare-Kalkül für die Kernsprache 5.2.2 Definition: Herleitung im Hoare-Kalkül 5.2.3 Beispiel: Verifikation eines imperativen Programms 5.3 Beweisverpflichtungen und Programmkonstruktion 5.3.1 Satz: Beweisverpflichtungen 5.3.2 Beispiel: Programmverifikation mittels Beweisverpflichtungen I 5.3.3 Beispiel: Programmverifikation mittels Beweisverpflichtungen II 5.3.4 Beispiel: Programmkonstruktion I 5.3.5 Beispiel: Programmkonstruktion II 5.4 Totale Korrektheit und Terminierung 5.4.1 Satz: Totale und partielle Korrektheit 5.4.2 Beispiele: Fehler erster Art 5.4.3 Beispiele: Fehler zweiter Art 5.5 Bemerkungen zu logischen Kalkülen 5.6 Übungsaufgaben 5.6.1 Aufgabe 5.6.2 Aufgabe 5.6.3 Aufgabe 5.6.4 Aufgabe 5.6.5 Aufgabe 5.6.6 Aufgabe 5.6.7 Aufgabe 5.6.8 Aufgabe 5.6.9 Aufgabe 5.6.10 Aufgabe 5.6.11 Aufgabe 5.6.12 Aufgabe 5.6.13 Aufgabe 6 Spezielle Funktionen 6.1 Injektivität, Surjektivität und Bijektivität 6.1.1 Satz: leere Relation als Funktion 6.1.2 Festlegung: nichtleere Quellen 6.1.3 Definition: Injektivität und Surjektivität 6.1.4 Beispiele: bipartite Pfeildiagramme 6.1.5 Definition: strenge Monotonie 6.1.6 Satz: strenge Monotonie impliziert Injektivität 6.1.7 Satz: hinreichende Kriterien für Injektivität und Surjektivität 6.1.8 Beispiele: Injektivität und Surjektivität 6.1.9 Definition: Komposition und identische Funktion 6.1.10 Satz: Eigenschaften Funktionskomposition 6.1.11 Definition: Bijektion 6.1.12 Satz: Bijektivität und Links- bzw. Rechtsinverse 6.1.13 Definition: Umkehrfunktion 6.1.14 Beispiel: Bijektivität im Pfeildiagramm 6.1.15 Definition: Bild(menge) und Urbild(menge) 6.1.16 Satz: Urbilder einelementiger Mengen 6.1.17 Satz: Charakterisierung von Injektivität und Surjektivität 6.1.18 Satz: Injektivität und Linksinverse 6.1.19 Auswahlaxiom (E. Zermelo) 6.1.20 Satz: Surjektivität und Rechtsinverse 6.2 Kardinalitätsvergleich von Mengen 6.2.1 Definition: Kardinalitätsvergleiche 6.2.2 Lemma 6.2.3 Satz: fundamentale Eigenschaften 6.2.4 Beispiele: Kardinalitätsvergleiche 6.2.5 Satz (G. Cantor) 6.2.6 Satz (E. Schröder und F. Bernstein) 6.2.7 Beispiele: Anwendungen des Satzes von Schröder-Bernstein 6.3 Wachstum spezieller Funktionen und Aufwand von Algorithmen 6.3.1 Lemma 6.3.2 Lemma 6.3.3 Definition: Potenzfunktion 6.3.4 Satz: Eigenschaften Potenzfunktion 6.3.5 Definition: Wurzelfunktion 6.3.6 Definition: Exponentialfunktion 6.3.7 Satz: Eigenschaften Exponentialfunktion 6.3.8 Definition: Logarithmusfunktion 6.3.9 Lemma 6.3.10 Lemma 6.3.11 Satz: Exponentiation übertrifft irgendwann Potenzierung 6.3.12 Definition: asymptotische Beschränkung 6.3.13 Korollar 6.3.14 Beispiel: Aufwand und Laufzeiten 6.3.15 Beispiele: Aufwand konkreter Programme 6.4 Zur Berechenbarkeit von Funktionen 6.5 Übungsaufgaben 6.5.1 Aufgabe 6.5.2 Aufgabe 6.5.3 Aufgabe 6.5.4 Aufgabe 6.5.5 Aufgabe 6.5.6 Aufgabe 6.5.7 Aufgabe 6.5.8 Aufgabe 6.5.9 Aufgabe 6.5.10 Aufgabe 6.5.11 Aufgabe 6.5.12 Aufgabe 6.5.13 Aufgabe 6.5.14 Aufgabe 6.5.15 Aufgabe 6.5.16 Aufgabe 6.5.17 Aufgabe 7 Spezielle Relationen und gerichtete Graphen 7.1 Äquivalenzrelationen und Partitionen 7.1.1 Definition: Äquivalenzrelation 7.1.2 Beispiele: Äquivalenzrelationen 7.1.3 Definition: Partition / Zerlegung 7.1.4 Satz: Partition ist Teilmenge der Potenzmenge 7.1.5 Satz: Partitionen und Äquivalenzrelationen 7.1.6 Definition: Äquivalenzklasse 7.1.7 Satz: Eins-zu-Eins-Beziehung zwischen 21M und 3M 7.1.8 Beispiele: Äquivalenzklassen 7.1.9 Definition: Modulo-Relation 7.1.10 Satz: Modulo-Relation ist Äquivalenzrelation 7.1.11 Beispiele: Rechnen modulo 4 und modulo −2 7.1.12 Satz: Modulo-Relation und ganzzahlige Division mit Rest 7.1.13 Beispiel: Zerlegung von Z 7.2 Ordnungsrelationen und geordnete Mengen 7.2.1 Definition: Antisymmetrie, Linearität, Ordnung 7.2.2 Beispiele: Ordnungen 7.2.3 Definition: Striktordnung 7.2.4 Beispiel: graphische Darstellung einer Ordnung 7.2.5 Definition: extreme Elemente 7.2.6 Satz: Eigenschaften extremer Elemente 7.2.7 Beispiel: extreme Elemente 7.2.8 Satz: extreme Elemente und Linearität 7.2.9 Definition: Schranken, Supremum, Infimum 7.2.10 Beispiel: Supremum und Infimum 7.2.11 Definition: monotone Funktion 7.2.12 Satz: Fixpunktsatz von A. Tarski 7.2.13 Lemma 7.2.14 Satz: Fixpunktsatz für monotone Funktionen auf endlichen Ordnungen 7.2.15 Definition: supremums-distributive Funktion 7.2.16 Lemma 7.2.17 Lemma 7.2.18 Satz: Fixpunktsatz von S.C. Kleene 7.2.19 Definition: Noethersche Ordnung 7.2.20 Satz: Noethersche Induktion 7.2.21 Beispiel: Noethersche Induktion 7.2.22 Satz: Existenz der ganzzahligen Division 7.2.23 Definition: echt absteigende unendliche Kette 7.2.24 Satz: Kettencharakterisierung Noethersch geordneter Mengen 7.2.25 Beispiel: Terminierungsbeweis 7.2.26 Satz: Lösung von Rekursionen 7.3 Grundbegriffe gerichteter Graphen 7.3.1 Definition: gerichteter Graph 7.3.2 Beispiele: gerichtete Graphen 7.3.3 Satz: Gradformeln 7.3.4 Beispiel: Graphen als Modelle 7.3.5 Definition: Weg, Kreis, Erreichbarkeit, Kreisfreiheit 7.3.6 Definition: relationale Komposition 7.3.7 Satz: Grundeigenschaften der relationalen Komposition 7.3.8 Beispiel: relationale Komposition 7.3.9 Definition: transitive und reflexiv-transitive Hülle 7.3.10 Satz: Zusammenhang zwischen den Hüllen 7.3.11 Definition: Pfad 7.3.12 Satz: Erreichbarkeit mittels Wegen und Pfaden 7.3.13 Satz: Pfade und Hüllen 7.3.14 Satz: Erreichbarkeit und Hüllen 7.3.15 Satz: Berechnung von Hüllen 7.3.16 Satz: Testen auf das Vorhandensein von Kreisen 7.3.17 Beispiel: Erreichbarkeit und Kreise 7.3.18 Satz: Induktion bei Graphen 7.3.19 Satz: Anwendung Grapheninduktion 7.3.20 Definition: topologische Sortierung 7.3.21 Satz: topologische Sortierung impliziert Kreisfreiheit 7.4 Bemerkungen zu mehrstelligen Relationen 7.5 Übungsaufgaben 7.5.1 Aufgabe 7.5.2 Aufgabe 7.5.3 Aufgabe 7.5.4 Aufgabe 7.5.5 Aufgabe 7.5.6 Aufgabe 7.5.7 Aufgabe 7.5.8 Aufgabe 7.5.9 Aufgabe 7.5.10 Aufgabe 7.5.11 Aufgabe 8 Elementare Kombinatorik und ungerichtete Graphen 8.1 Fakultäten und Binomialkoeffizienten 8.1.1 Definition: Fakultät 8.1.2 Satz: rekursive Beschreibung der Fakultät 8.1.3 Definition: Funktionenmenge 8.1.4 Satz: Kardinalität von Funktionenmengen 8.1.5 Satz: Kardinalitätsvergleich von Funktionenmengen 8.1.6 Definition: Permutation 8.1.7 Definition: Einschieben in eine Permutation 8.1.8 Satz: Berechnung von Permutationsmengen 8.1.9 Beispiel: Berechnung von Permutationsmengen 8.1.10 Satz: Anzahl der bijektiven Funktionen 8.1.11 Beispiel: Unabhängige und abdeckende Türme beim Schachspiel 8.1.12 Definition: Binomialkoeffizient 8.1.13 Satz (B. Pascal) 8.1.14 Definition: Menge der k-Teilmengen 8.1.15 Satz: Rekursion für Mengen von k-Teilmengen 8.1.16 Satz: Anzahl der k-Teilmengen 8.1.17 Beispiel: k-Teilmengen und Binomialkoeffizienten 8.1.18 Satz: Binomischer Lehrsatz 8.2 Grundbegriffe ungerichteter Graphen 8.2.1 Definition: ungerichteter Graph 8.2.2 Beispiel: ungerichteter Graph 8.2.3 Definition: Nachbarschaft, Endknoten, Knotengrad 8.2.4 Satz: Eigenschaften der Knotengrade 8.2.5 Beispiele: Wege, Kreise und Zusammenhangskomponenten 8.2.6 Definition: Gittergraph 8.2.7 Satz: kürzeste Wege in Gittergraphen 8.2.8 Definition: vollständiger Graph 8.2.9 Satz: längste Wege in vollständigen Graphen 8.2.10 Lemma 8.2.11 Satz: alle Wege in vollständigen Graphen 8.2.12 Beispiel: alle Wege in vollständigen Graphen 8.3 Dünne ungerichtete Graphen 8.3.1 Definition: Wald und Baum 8.3.2 Satz: Kantenzahl in Wäldern 8.3.3 Satz: Kantenzahl zur Charakterisierung von Bäumen 8.3.4 Satz: alle Wege in Bäumen 8.3.5 Beispiel: Projektion des Würfels 8.3.6 Definition: planare linealische Graphzeichnung 8.3.7 Definition: planarer Graph 8.3.8 Lemma 8.3.9 Beispiele: planare ungerichtete Graphen 8.3.10 Beispiele: automatisches Zeichnen planarer Graphen 8.3.11 Satz: Eulersche Polyederformel für Graphzeichnungen 8.3.12 Satz: maximale Kantenzahl bei planaren Graphen 8.4 Variationen des Graphenbegriffs 8.5 Übungsaufgaben 8.5.1 Aufgabe 8.5.2 Aufgabe 8.5.3 Aufgabe 8.5.4 Aufgabe 8.5.5 Aufgabe 8.5.6 Aufgabe 8.5.7 Aufgabe 8.5.8 Aufgabe 8.5.9 Aufgabe 8.5.10 Aufgabe 8.5.11 Aufgabe 8.5.12 Aufgabe 9 Diskrete Wahrscheinlichkeitstheorie 9.1 Zufallsexperimente und Zufallsereignisse 9.1.1 Definition: Elementarereignis, Ergebnisraum 9.1.2 Definition: Zufallsereignis, Ereignisraum 9.1.3 Beispiele: Zufallsereignisse 9.2 Diskrete Wahrscheinlichkeitsverteilungen 9.2.1 Definition: Wahrscheinlichkeitsverteilung 9.2.2 Definition: Gleichverteilung 9.2.3 Satz: Wahrscheinlichkeit bei Gleichverteilungen 9.2.4 Beispiele: Gleichverteilungen 9.2.5 Definition: unabhängige Zufallsereignisse 9.2.6 Beispiele: Unabhängigkeit von Zufallsereignissen 9.3 Die bedingte Wahrscheinlichkeit 9.3.1 Beispiel: Motivation von bedingter Wahrscheinlichkeit 9.3.2 Definition: bedingte Wahrscheinlichkeit 9.3.3 Satz: bedingte Wahrscheinlichkeitsverteilung 9.3.4 Satz: Gesetz der totalen Wahrscheinlichkeit 9.3.5 Beispiele: bedingte Wahrscheinlichkeiten 9.3.6 Satz: bedingte Wahrscheinlichkeit und Unabhängigkeit 9.3.7 Satz: Unabhängigkeit und Komplemente 9.3.8 Satz (T. Bayes) 9.3.9 Beispiel: Anwendung des Satzes von T. Bayes 9.3.10 Beispiel: Anwendung des Satzes von T. Bayes 9.4 Reelwertige diskrete Zufallsvariablen 9.4.1 Definition: Zufallsvariable 9.4.2 Definition: Summe, Produkt 9.4.3 Beispiele: Zufallsvariablen 9.4.4 Definition: induzierte Zufallsereignisse 9.4.5 Definition: unabhängige Zufallsvariablen 9.4.6 Beispiele: induzierte Zufallsereignisse 9.4.7 Definition: Wahrscheinlichkeitsfunktion 9.4.8 Definition: Verteilungsfunktion 9.4.9 Satz: Verteilungsfunktion ist Treppenfunktion 9.4.10 Beispiel: Wahrscheinlichkeits- und Verteilungsfunktion 9.5 Erwartungswert, Varianz und Standardabweichung 9.5.1 Definition: Erwartungswert 9.5.2 Beispiel: Erwartungswert und Histogramm 9.5.3 Satz: alternative Darstellung Erwartungswert 9.5.4 Satz: fundamentale Eigenschaften des Erwartungswerts I 9.5.5 Satz: fundamentale Eigenschaften des Erwartungswerts II 9.5.6 Lemma 9.5.7 Satz: fundamentale Eigenschaften des Erwartungswerts III 9.5.8 Beispiele: Erwartungswerte 9.5.9 Satz: Transformationssatz für Erwartungswerte 9.5.10 Satz: Erwartungswert eines Quadrats 9.5.11 Definition: Varianz, Standardabweichung 9.5.12 Satz: alternative Darstellung Varianz 9.5.13 Beispiele: Varianzen 9.5.14 Satz: fundamentale Eigenschaften der Varianz 9.5.15 Satz: Markovsche Ungleichung 9.5.16 Satz: Chebychevsche Ungleichung 9.6 Bernoulli- und binomial-verteilte Zufallsvariablen 9.6.1 Satz: durch Zufallsvariable induzierte Wahrscheinlichkeitsverteilung 9.6.2 Definition: Bernoulli-Verteilung, Bernoulli-verteilte Zufallsvariable 9.6.3 Satz: Charakterisierung Bernoulli-verteilter Zufallsvariablen 9.6.4 Satz: Erwartungswert und Varianz Bernoulli-verteilter Zufallsvariablen 9.6.5 Definition: Binomial-Verteilung, binomial-verteilte Zufallsvariable 9.6.6 Satz: Charakterisierung binomial-verteilter Zufallsvariablen 9.6.7 Satz: Erwartungswert binomial-verteilter Zufallsvariablen 9.6.8 Lemma 9.6.9 Satz: Varianz binomial-verteilter Zufallsvariablen 9.6.10 Beispiel: binomial-verteilte Zufallsvariable 9.7 Hypergeometrisch-verteilte Zufallsvariablen 9.7.1 Satz: Motivation hypergeometrische Verteilung 9.7.2 Lemma 9.7.3 Definition: hypergeometrische Vert., hypergeometrisch-vert. Zufallsvariable 9.7.4 Satz: Charakterisierung hypergeometrisch-verteilter Zufallsvariablen 9.7.5 Satz: Erwartungswert hypergeometrisch-verteilter Zufallsvariablen 9.7.6 Satz: Varianz hypergeometrisch-verteilter Zufallsvariablen 9.7.7 Beispiele: hypergeometrisch-verteilte Zufallsvariablen 9.8 Ergänzungen zu abzählbaren Ergebnisräumen 9.9 Übungsaufgaben 9.9.1 Aufgabe 9.9.2 Aufgabe 9.9.3 Aufgabe 9.9.4 Aufgabe 9.9.5 Aufgabe 9.9.6 Aufgabe 9.9.7 Aufgabe 9.9.8 Aufgabe 9.9.9 Aufgabe 9.9.10 Aufgabe 9.9.11 Aufgabe 9.9.12 Aufgabe 9.9.13 Aufgabe 9.9.14 Aufgabe 9.9.15 Aufgabe 10 Anwendung: Generische Programmierung 10.1 Einige motivierende Beispiele 10.1.1 Definition: absorbierend, stabil, Kern 10.1.2 Satz: Charakterisierung von Kernen I 10.1.3 Satz: Charakterisierung von Kernen II 10.1.4 Lemma 10.1.5 Satz 10.1.6 Definition: transitive Reduktion 10.1.7 Definition: spannender Baum 10.1.8 Satz: Charakterisierung von spannenden Bäumen 10.2 Berechnung minimaler und maximaler Teilmengen 10.2.1 Definition: aufwärts- bzw. abwärts-vererbend 10.2.2 Lemma 10.2.3 Satz: Berechnung inklusionsminimaler Mengen 10.2.4 Satz: Berechnung inklusionsmaximaler Mengen 10.3 Anwendungen und Erweiterungen 10.3.1 Beispiel: Berechnung eines Kerns 10.3.2 Beispiel: Berechnung einer kleinen Knotenüberdeckung I 10.3.3 Satz: spezielle Knotenüberdeckung 10.3.4 Beispiel: Berechnung einer kleinen Knotenüberdeckung II 10.3.5 Beispiel: Berechnung eines spannenden Baums 10.3.6 Beispiel: Modellierung einer Partition durch Bäume 10.3.7 Beispiel: Modellierung einer Partition durch eine Funktion 10.3.8 Beispiel: Wirkungsweise von union 10.4 Bemerkungen zum Lösen schwieriger Optimierungsprobleme 10.5 Übungsaufgaben 10.5.1 Aufgabe 10.5.2 Aufgabe 10.5.3 Aufgabe 10.5.4 Aufgabe 10.5.5 Aufgabe 10.5.6 Aufgabe 10.5.7 Aufgabe 10.5.8 Aufgabe 10.5.9 Aufgabe 10.5.10 Aufgabe 10.5.11 Aufgabe 10.5.12 Aufgabe 11 Grundbegriffe algebraischer Strukturen 11.1 Homogene algebraische Strukturen 11.1.1 Definition: homogene algebraische Struktur 11.1.2 Definition: Monoid 11.1.3 Definition: Potenzierung 11.1.4 Satz: Potenzgesetze 11.1.5 Definition: Gruppe 11.1.6 Beispiel: Kleinsche Vierergruppe 11.1.7 Lemma 11.1.8 Satz: Gruppen der traditionellen Auffassung nicht gleichungsdefinierbar 11.1.9 Satz: Eindeutigkeit neutraler und inverser Elemente 11.1.10 Satz: Rechenregeln 11.1.11 Schreib- und Sprechweisen 11.1.12 Definition: Ring 11.1.13 Beispiel: Mengenring 11.1.14 Satz: Rechenregeln 11.1.15 Satz: Boolesche Ringe sind kommutativ 11.1.16 Definition: Körper 11.1.17 Satz: Eindeutigkeit der linksinversen Elemente 11.2 Strukturerhaltende Funktionen 11.2.1 Beispiel: Motivation von Verträglichkeit 11.2.2 Definition: verträgliche Funktionen 11.2.3 Definition: Strukturisomorphismus 11.2.4 Definition: Strukturhomomorphismus 11.2.5 Definition: Gruppenhomomorphismus 11.2.6 Satz: Eigenschaften von Gruppenhomomorphismen 11.2.7 Beispiele: Gruppenhomomorphismen und -isomorphismen 11.2.8 Satz: Gruppenhomomorphismen sind Strukturhomomorphismen 11.2.9 Definition: Ringhomomorphismus 11.2.10 Satz: Eigenschaften von Ringhomomorphismen 11.2.11 Beispiele: Ringhomomorphismen und -isomorphismen 11.2.12 Satz: Ringhomomorphismen sind Strukturhomomorphismen 11.2.13 Beispiel: Strukturen und Homomorphismen 11.3 Unterstrukturen 11.3.1 Definition: abgeschlossene Teilmenge 11.3.2 Definition: Unterstruktur 11.3.3 Festlegung: Einschränkungen von Operationen 11.3.4 Definition: Untergruppe 11.3.5 Satz: Untergruppen sind Unterstrukturen 11.3.6 Beispiele: Untergruppen 11.3.7 Satz: Durchschnitt von Untergruppen 11.3.8 Definition: Unterring 11.3.9 Satz: Unterringe sind Unterstrukturen 11.3.10 Beispiele: Unterringe 11.3.11 Satz: Durchschnitt von Unterringen 11.3.12 Definition: zyklische Gruppe 11.3.13 Satz: Beschreibung zyklischer Gruppen 11.3.14 Korollar 11.3.15 Satz: Untergruppen zyklischer Gruppen sind zyklisch 11.4 Produkt- und Quotientenstrukturen 11.4.1 Definition: Produktstruktur 11.4.2 Satz: Produktgruppe 11.4.3 Satz: Produktring 11.4.4 Beispiel: Produktring 11.4.5 Beispiele: Produkte von Körpern 11.4.6 Beispiel: Motivation von Vertreterunabhängigkeit 11.4.7 Definition: Verträglichkeit 11.4.8 Definition: Kongruenz 11.4.9 Definition: Quotientenstruktur 11.4.10 Satz: Quotientengruppe 11.4.11 Satz: Quotientenring 11.4.12 Satz: Modulo-Relation ist eine Kongruenz 11.4.13 Beispiele: Quotientenringe der ganzen Zahlen 11.4.14 Lemma (E. Bezout) 11.4.15 Satz: Quotientenringe modulo Primzahlen 11.5 Der Körper der komplexen Zahlen 11.5.1 Definition und Satz: additive Gruppe der komplexe Zahlen 11.5.2 Definition: Multiplikation und Einselement 11.5.3 Lemma 11.5.4 Satz: Ring der komplexen Zahlen 11.5.5 Satz: Körper der komplexen Zahlen 11.5.6 Definition: weitere Funktionen 11.5.7 Satz: Strukturerhaltung 11.5.8 Satz: Rechenregeln 11.5.9 Satz: Dreiecksungleichung 11.5.10 Satz: Einbettung der reellen Zahlen 11.5.11 Beispiel: Dualität 11.6 Einige Ergänzungen zum mathematischen Strukturbegriff 11.7 Übungsaufgaben 11.7.1 Aufgabe 11.7.2 Aufgabe 11.7.3 Aufgabe 11.7.4 Aufgabe 11.7.5 Aufgabe 11.7.6 Aufgabe 11.7.7 Aufgabe 11.7.8 Aufgabe 11.7.9 Aufgabe 11.7.10 Aufgabe 11.7.11 Aufgabe 11.7.12 Aufgabe 11.7.13 Aufgabe 11.7.14 Aufgabe 11.7.15 Aufgabe 12 Formale Einführung der natürlichen Zahlen 12.1 Axiomatische Einführung mittels Peano-Strukturen 12.1.1 Definition: Peano-Struktur 12.1.2 Satz 12.1.3 Satz: Induktion bei Peano-Strukturen 12.1.4 Satz: Rekursionssatz von R. Dedekind 12.2 Eindeutigkeit und Existenz von Peano-Strukturen 12.2.1 Satz: Isomorphiesatz von R. Dedekind 12.2.2 Unendlichkeitsaxiom (E. Zermelo) 12.2.3 Satz: kleinste induktive Menge 12.2.4 Satz 12.2.5 Lemma 12.2.6 Satz: Existenz einer Peano-Struktur 12.2.7 Festlegung: Schreib- und Sprechweisen 12.3 Arithmetsche Operationen 12.3.1 Definition: Addition 12.3.2 Satz: Eigenschaften der Addition I 12.3.3 Satz: Eigenschaften der Addition II 12.3.4 Satz: Eigenschaften der Addition III 12.3.5 Definition: Multiplikation 12.3.6 Satz: Distributivgesetze 12.3.7 Satz: Eigenschaften der Multiplikation I 12.3.8 Satz: Eigenschaften der Multiplikation II 12.3.9 Satz: Eigenschaften der Multiplikation III 12.4 Die Standard-Ordnungsrelation der natürlichen Zahlen 12.4.1 Satz: Ordnungs-Eigenschaft 12.4.2 Satz: Eigenschaften der Ordnung I 12.4.3 Satz: Eigenschaften der Ordnung II 12.4.4 Satz: Eigenschaften der Ordnung III 12.4.5 Satz: Eigenschaften der Ordnung IV 12.5 Zur Definition der restlichen Zahlenbereiche 12.6 Übungsaufgaben 12.6.1 Aufgabe 12.6.2 Aufgabe 12.6.3 Aufgabe 12.6.4 Aufgabe 12.6.5 Aufgabe 12.6.6 Aufgabe 12.6.7 Aufgabe 12.6.8 Aufgabe 12.6.9 Aufgabe 12.6.10 Aufgabe 13 Anhang: Lösungsvorschläge zu Übungsaufgaben 14 Anhang: Einige Literaturhinweise Index