Mathematik für Informatiker für Dummies

Ist der Mathematik-Schein auch für Sie die größte Hürde im Studium? Dabei brauchen Sie als Informatiker solide mathematische Grundkenntnisse, um Algorithmen zu verstehen und mit Anwendern aus Naturwissenschaft und Technik auf Augenhöhe zu kommunizieren. Dieses Buch vermittelt Ihnen auf verständliche Weise und immer mit Querbezügen zur Informatik die mathematischen Grundlagen, die alle Informatiker benötigen: Aussagenlogik, Rekursion, Induktion, Relationen, Analysis, Wahrscheinlichkeitsrechnung, Statistik und lineare Algebra. Keine Sorge: Es werden lediglich Schulkenntnisse in Mathematik vorausgesetzt.

Autorentext
Hans-Jürgen Steffens ist Mathematiker und Professor für Software-Engineering und Systemanalyse an der Hochschule Kaiserslautern. Christian Zöllner hat einen Bachelor in Medizintechnischer Informatik und mehrjährige Erfahrung in der Hochschullehre. Kathrin Mühlmann studiert noch und hat selbst gerade erst alle Mathescheine für Angewandte Informatik bestanden.

Inhalt

Über den Autor 9

Danksagungen 9

Einleitung 25

Über dieses Buch 25

Wen hatten wir bei diesem Buch besonders vor Augen 25

Durch welche Brille sehen wir also den Informatiker? 26

Und was bedeutet dies für uns? 26

Haben wir auch Nichtinformatiker als potenzielle Leser im Blick 27

Wie kann man dieses Buch lesen? 27

Welche Besonderheiten finden sich in unserem Buch 27

Auf welche weiteren (kleinen) Innovationen dürfen wir hinweisen? 28

Wann ist genug genug? 29

Und weitere Literatur ? 29

Kommunikation mit Autoren 30

Teil I: Natürliche Zahlen und Mengen - im Auge des Informatikers 31

Kapitel 1 Zahlen und ihre Logik 33

Was es über die Vielfalt der Zahlen zu sagen gibt 33

Zahlen zählen 34

Zahlen aufs Papier - und später auf den Rechner 35

Es darf auch etwas mehr sein - über die natürlichen Zahlen hinaus 36

Ganzzahlige Brüche - ein zweiter Nachschlag 37

Die Welt der rationalen Zahlen ist für Informatiker genug - Mathematiker sind weniger bescheiden 39

Komplexe Zahlen erweitern den Zahlenraum ein weiteres Mal 41

Blick auf die Gipfel: Hyperkomplexe Zahlen und Oktionen 44

Wir wissen nun, über was wir reden, wir wollen jetzt wissen, wie wir darüber reden 45

Prädikat - besonders wertvoll 45

(Mathematische) Wahrheit 46

Operatoren - Aus Zahlen werden Zahlen 47

Logische Operatoren - Schnittstellen zur Logik 48

Verrechnung von Wahrheitswerten 48

Junktoren 48

Wahrheitstabellen 49

Für den einen ist es duplo, für den anderen die längste Praline der Welt - zur Doppelrolle der Zahlen in der formalen Logik 49

Quantoren in der Logik - Prädikate erhalten durch sie ihre Power 52

Der Existenzquantor 53

Umsetzung des Existenzquantors in eine Schleife für Programmierer 53

Allquantor 54

Kapitel 2 Im Assembler-Code der Mathematik - Handreichungen für Ungläubige 57

Gehen wir zurück auf Los 57

Was passiert eigentlich beim Rechnen? 58

Wir bringen dem Computer das Rechnen bei 58

Wie sehen die nächsten Schritte aus? 59

Rekursion - Vorbereitungen für die Induktion 60

Induktion - mit Warp 10 durch alle Zahlen 62

Anwendungen der Induktion - Return on invest 63

Beweis des Assoziativgesetzes 64

Wir kennen die Zahlen vom Zählen her - können wir sie auch abstract charakterisieren? 65

Unendlich viele Zahlen auf einem endlichen Rechner? 66

Kapitel 3 Mengenlehre - im Maschinenraum der Mathematik 69

Mengenlehre - fängt man damit nicht immer an? 70

Die Sprache der Mengenlehre - Goethe wäre 'not' 70

Erste Anforderungen an den Mengenbegriff 71

Mengentheoretische Operationen 72

Äquivalenz von Aussagen - Gleichheit von Mengen 74

Eigenschaften der Operationen , und 74

Fallstricke und Sicherungen 76

Weitere mengentheoretische Operationen 77

Mengen als logische Bausteine für die Implementierung von Zahlen 80

Spezielle Realisierungen des Zählprozesses 80

Mengen - was kann man sich darunter vorstellen 83

Linux-Filesystem als Modell für ein Mengensystem 83

Infinite in all directions 85

Mengen für Datenbanker 86

Abstraktionen 87

Datenbanken? - Keep it simple and stupid 88

Nur für Theoretiker: Suchen, bis die Sterne verglühen 88

Wer hat Angst vor Graphen? 90

Urlemente - ein bisschen Medienbruch 92

Mengenlehre für 'Informatiker mit der harten Kinnlade' 93

Prädikatenlogik mit einem einzigen Prädikat 93

Skolemisierung - oder wie destilliert man Operationen aus Aussagen 96

Teil II: Diskrete Strukturen 99

Kapitel 4 Spezielle Beziehungen - Äquivalenzen und Ordnungen 101

Äquivalenzrelationen - das Gleiche versus dasselbe 102

Äquivalenzrelation - die Erste 103

Äquivalenzrelation - die Zweite 108

Ordnungsrelationen - Ordnung in der mathematischen Welt 109

Geordnete Zahlen - die kleiner/gleich Beziehung 109

Verträglichkeiten 110

Teilbarkeit - auch eine Ordnung 111

Auch die Teilbarkeit ist relativ verträglich und pflegeleicht 111

Die mengentheoretische Inklusion - eine Ordnung für sich 112

Die Ordnungsbeziehungen - was haben sie gemein, was unterscheidet sie 112

Ordnungsbeziehungen und Grenzen 113

Graphen als Medium für die Darstellung partieller Ordnungen 114

Kapitel 5 Allgemeine Beziehungen und Beziehungskisten 117

Beziehungen als Tabellen 118

Inoffizielle Beziehungen 119

Realisierungen inoffizieller Beziehungen 120

Operieren mit Beziehungen 122

Jemanden kennen, der jemanden kennt, der Beziehungen hat 123

Spezialfälle: Verknüpfungen mit der inversen Beziehung 124

Verknüpfungen unterschiedlicher Relationen 125

Ausblick auf Relationen zwischen unterschiedlichen Mengen 126

Eindeutige Beziehungen - auf dem Weg zu Funktionen 127

Väter und Väter von Vätern 128

Funktionen und ihre allgemeinen Eigenschaften 129

Kapitel 6 Gruppen - es kann nicht nur eine geben 131

Über die Addition ganzer Zahlen 131

Beweis der Eindeutigkeit des neutralen Elements 132

Von den ganzen Zahlen zum allgemeinen Gruppenbegriff 132

Abstrakte kommutative Gruppen G 133

Nichtkommutative Gruppen 133

Beispiele von in der Natur auftretenden Gruppen - Symmetriegruppen 134

Gruppen und Faktorgruppen 139

Faktorgruppen der ganzen Zahlen 139

Allgemeine Gruppen und Faktorgruppen 141

Der Index einer Untergruppe H G 142

Untergruppen endlicher Gruppen 143

Kapitel 7 Ringe und Körper 147

Überblick Ringe 148

Überblick Körper 149

Ein Rückblick auf die Teilbarkeit und die Primzahlen 149

n als Restklassenring 151

Wohldefiniertheit der Operationen auf den Restklassen 151

Der Euklidische Algorithmus 152

Einheiten in n 153

Eulersche **-Funktion 153

Return on Invest - das RSA Verfahren in der Kryptologie 154

Asymmetrische Verschlüsselungsverfahren 155

Das RSA-Verfahren in der Theorie 155

Praktische Bemerkungen zum RSA-Verfahren 157

Kapitel 8 Graphentheorie 159

Zur Motivation 159

Das Haus vom Nikolaus 160

Gerichtete und ungerichtete Graphen 160

Zusammenhängende und unzusammenhängende Graphen 161

Schlingen und parallele Kanten, Nullgraph und einfacher Graph 162

Eckengrad 163

Algorithmische Eigenschaften des Eckengrads 164

Handshake-Lemma 164

Königsberger Brückenproblem 166

Eulergraph und Eigenschaften 167

Eulerkreis/Eulersche Touren 168

Adjazenzmatrix 168

Wann sind Graphen isomorph? - Adjazenzmatrizen 169

Alternative Tabellendarstellung - Inzidenzmatrizen 170

Bäume 171

Definition und Eigenschaften eines Baumes 171

Spannbaum 171

Definition von Wäldern 171

Wurzelbaum 172

Binärbäume 174

Suchbaum 175

Traversieren von Wurzelbäumen 175

Wie gehören Binärbäume und algebraische Ausdrücke zusammen? 176

Kürzeste Wege finden 177

Kruskal-Algorithmus 180

Prim-Algorithmus 180

Dijkstra-Algorithmus 181

Teil III: Analysis für Informatiker 183

Kapitel 9 Reelle Zahlen - der virtuelle Sprung in die Unendlichkeit 185

Irrationale Zahlen 185

2 ist eine irrationale Zahl 186

Reelle Zahlen 187

Die E…