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.
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.
Über den Autor 9
Danksagungen 9
Einleitung25
Ü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äubige57
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 Mathematik69
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 Ordnungen101
Ä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 Beziehungskisten117
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 geben131
Über die Addition ganzer Zahlen 131
Beweis der Eindeutigkeit des neutralen Elements 132
Von den ganzen Zahlen zum allgemeinen Gruppenbegriff 132
Abstrakte kommutative GruppenG 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 UntergruppeH G 142
Untergruppen endlicher Gruppen 143
Kapitel 7 Ringe und Körper147
Überblick Ringe 148
Überblick Körper 149
Ein Rückblick auf die Teilbarkeit und die Primzahlen 149
nals Restklassenring 151
Wohldefiniertheit der Operationen auf den Restklassen 151
Der Euklidische Algorithmus 152
Einheiten in n153
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 Unendlichkeit185
Irrationale Zahlen 185
2 ist eine irrationale Zahl 186
Reelle Zahlen 187
Die Einführung der reellen Zahlen für Informatiker eine kleine Revolution 188
Elementare Eigenschaften der reellen Zahlen 189
Abschätzungen, die Analysis lebt davon 191
Betragsfunktion und Dreiecksungleichung 191
Bernoullische Ungleichung 193
Der Umgebungsbegriff 194
Unendliche Folgen 194
Technische Definition der Konvergenz 196
Arbeiten mit der technischen Definition 196
Besondere Eigenschaften konvergenter Folgen 197
Hinreichende Konvergenzbedingungen beschränkter Folgen 198
Wichtige Spezialfälle: Die Folgen (1 + 1n)nund (1 + 1n)n+1 200
Rekursiv definierte Folgen 201
Häufungspunkte von Folgen 205
Grenzwertsätze für Folgen Handreichungen für Klausuren 206
Beweis des ersten Grenzwertsatzes 206
Beispielhafte Folgerungen aus den Grenzwertsätzen 207
Mehr Werkzeuge zur Bestimmung des Konvergenzverhaltens 209
Das Cauchysche Konvergenzkriterium 209
Grenzwerte unendlicher Reihen 210
Die harmonische Reihe 210
Begriffliche Einordnung der unendlichen Reihen 211
Cauchysche Konvergenzkriterium für unendliche Reihen 212
Einfache Beispiele unendlicher Reihen 212
Wurzel- und Quotientenkriterium die wichtigsten Konvergenzkriterien für Reihen 213
Absolute Konvergenz 218
Die allgemeine binomische Formel 224
Die Fakultätsfunktion 224
Binomialkoeffizienten 225
Binomische Formel 226
Kapitel 10 Pflegeleichte Funktionen Stetigkeit und Differenzierbarkeit229
Grundsätzliche Bemerkungen 230
»Durchhalteparolen« für die Analysis 231
Der Grenzwertbegriff bei Funktionen 232
Konvergenz mithilfe des Umgebungsbegriffs 233
Konvergenz unter Rückgriff auf Folgenkonvergenz 233
Konvergenzsätze 235
Anwendung der Konvergenzsätze auf die Exponentialfunktion 236
Stetige Funktionen 239
Beispiel einer Funktion, die nur an einer Stelle stetig ist 240
Wichtige Eigenschaften stetiger Funktionen 240
Differenzierbare Funktionen 243
Die Landau-Symboleo() undO() 243
Differenzierbarkeit viao(x) 244
Differenzierbarkeit via Differenzenquotient 245
Beide Definitionen der Differenzierbarkeit sind äquivalent 247
Rechenregeln für Ableitungen 249
Verträglichkeit der Differenzialquotienten mit der Summenbildung 249
Produktregel 249
Quotientenregel 250
Kettenregel 251
Wichtige Beispiele differenzierbarer Funktionen 252
Differenzierbarkeit der Polynome 252
Ableitung dere-Funktion und des Logarithmus 253
Ableitungen der trigonometrischen Funktionen 254
Der Mittelwertsatz der Differenzialrechnung 257
Der Satz von Rolle 258
Folgerungen aus dem Mittelwertsatz 259
Die Regeln von lHospital 259
Wichtige Beispiele für die Anwendung der lHospitalschen Regeln 261
Taylorpolynome und Taylorentwicklung 263
Beispiele von Taylorentwicklungen 267
Analytische Funktionen als »ganzheitliche« Funktionen 270
Kapitel 11 Integrale271
Stammfunktionen 271
Integrale elementarer Funktionen 272
Partielle Integration 273
Integration per Substitution 275
Rationale Funktionen und Partialbruchzerlegungen 276
Bestimmte Integrale 279
Einstieg in die Flächenberechnung 279
Stammfunktionen »in action« 281
Teil IV: Vom Würfelspiel zum Algorithmus 283
Kapitel 12 Wahrscheinlichkeitsrechnung Regeln im Regellosen285
Am Anfang war das Spiel grundlegende Begrifflichkeiten der Wahrscheinlichkeitsrechnung 286
Ereignisse und Elementarereignisse 286
Wahrscheinlichkeiten 290
Ereignisse und Wahrscheinlichkeiten im formalen Rahmen 295
Bedingte Wahrscheinlichkeiten corriger la fortune 297
Bedingte Wahrscheinlichkeiten reengineered die Formel von Bayes 302
Zufallsvariable geeignete Codierungen zufälliger Ereignisse 303
Zufallsvariable Übertragung von Wahrscheinlichkeiten auf Zahlenmengen 304
Summen und Produkte von Zufallsvariablen 305
Von der Zufallsvariablen zur Verteilungsfunktion 306
Mittelwerte in verschiedenen Ausprägungen: Erwartungswerte und Varianzen 308
Der Erwartungswert der Streuung die Varianz 311
Korrelationen synchrone Streuungen 313
Kapitel 13 Die klassischen Verteilungen 317
Binomialverteilung 317
Münzwurf mit geänderten Spielregeln 318
Erwartungswerte und Varianzen für binomialverteilte Zufallsvariablen 319
Geometrische Verteilung 321
Geänderte Spielregeln 322
Poissonverteilte Zufallsvariablen 323
Näherungsverfahren für die Binomialverteilung die Poissonverteilung 324
Erwartungswerte und Varianzen poissonverteilter Zufallsvariablen 326
Stetige Verteilungen 328
Exponentialverteilung 329
Normalverteilung 333
Kapitel 14 Testen! Denn Vertrauen ist nicht immer gut341
Die Ungleichung von Tschebyscheff 343
Normalverteilung und Tschebyscheffsche Ungleichung in der Gegenüberstellung 345
Tschebyscheffsche Ungleichung und die Gesetze der großen Zahlen 347
Beispielhafte Anwendung des Maximum-Likelihood-Prinzips 349
Über das Testen von Hypothesen 350
Signifikanztests 350
Alternativtests 353
2-Anpassung und2-Test 358
Kapitel 15 Probabilistische Algorithmen theoretisch interessant aus praktischen Gründen361
Sortierverfahren 362
Statistische Analyse des Quicksorts 362
Monte Carlo und Las Vegas die ganze Wahrheit und nichts als die Wahrheit 364
Quicksort durch die Brille von Las Vegas betrachtet 364
Las Vegas liberalisiert nur noch »nichts als die Wahrheit« 364
Monte Carlo »die ganze Wahrheit« 370
Teil V: Sprung in den Hyperraum 375
Kapitel 16 Vektoren aggregierte Zahlen377
Erste Operationen mit Vektoren: Addition und skalare Multiplikation 377
Kräfte können in unterschiedlichen Reihenfolgen addiert werden 378
Die Addition von drei oder mehr Vektoren kann unterschiedlich geklammert werden 378
Zu jedem Vektor gibt es einen inversen Vektor 379
Vektoren können mit Zahlen multipliziert werden 380
Auch Geschwindigkeiten sind Vektoren 380
Das Skalarprodukt hiermit erhält die Vektorrechnung ihre eigentliche Power 382
Das Skalarprodukt als Mittel zur Berechnung physikalischer Arbeit 382
Das Skalarprodukt erfasst geometrisch wichtige Sachverhalte Orthogonalität, Länge und Abstand 383
Die Algebraisierung der Geometrie 383
Algebraisierung der Geometrie 384
Die Algebraisierung der Geometrie zum Zweiten 387
Die Seitenhalbierenden revisited 387
Vektoren in Koordinatensystemen 389
Auch umgekehrt wird ein Schuh draus: Vektoren erzeugen ein Koordinatensystem 393
Abstrakte Vektoren: Vektorräume 397
Einstieg in die Klasse Vector 397
Spezifikation von Vektorräumen 399
Strategische Begriffe 401
Auch der abstrakte Vektorraum kann als Aggregat von Zahlen aufgefasst werden 406
Aber wie decodieren wir ein𝑣 eines abstrakten VektorraumesVpraktisch? 408
Erweiterung der Vektorraumspezifikation durch abstrakte Skalarprodukte 411
Die zweite Chance des Mathematikers 417
Die Natur spielt mit 418
Kapitel 17 Transformationen 419
Duale Basen 420
Kovariante und kontravariante Komponenten 422
Die Beziehungen zwischen kovarianten und kontravarianten Komponenten 422
Der Übergang zwischen ko- und kontravarianten Koordinaten bei orthonormierten Basen 423
Nicht orthonormale Basen könnten wir auf sie verzichten? 424
Asymmetrische Verschlüsselungsverfahren mit Hilfe dualer Basen 426
Lineare Abbildungen 427
Drehungen 427
Matrizen operationelle Codierung linearer Abbildungen 428
Basistransformationen 434
Matrizen der Basistransformation 434
Besondere Eigenschaften der Matrizen der Basistransformationen 434
Die Matrizen der Basistransformationen als Matrizen einer Abbildung 435
Basistransformationen orthonormierter Basen 437
Kapitel 18 Lineare Gleichungssysteme Number Crunching in der linearen Algebra439
Gleichungssysteme und zugehörige Matrizen 440
Bedingungen der Lösbarkeit von Gleichungssystemen 441
Der Gaußsche Algorithmus 442
Homogene und inhomogene Gleichungssysteme 445
Determinanten in Aktion 446
Eigenwerte und Eigenvektoren 448
Auffinden der Eigenwerte 449
Berechnung der Eigenvektoren 449
Eigenvektoren und Diagonalisierung von Matrizen 450
Besonderheiten symmetrischer Matrizen 451
Teil VI: Höhere Weihen in der Analysis 453
Kapitel 19 Skalierung der Differenzierbarkeit455
Behandlung von Funktionen zweier Variablen 455
Differenzierbarkeit von Funktionen zweier Variablen 456
Nichtdifferenzierbare Funktionen trotz Existenz partieller Ableitung 458
Hinreichende Bedingungen für die Differenzierbarkeit 461
Behandlung von Funktionen beliebig vieler Variablen 462
Vektorwertige Funktionen 463
Differenzierbarkeit vektorwertiger Funktionen 463
Rechenregeln für Gradienten und Funktionalmatrizen 464
Hesse-Matrix und Taylorentwicklungen 466
als Vektoroperator 466
Kritische Punkte und Extremwerte 468
Analyse der Hesse-Matrix 469
Beispielrechnung zur Analyse kritischer Punkte 470
Kapitel 20 Potenziale als Stammfunktionen 473
Generelle Bemerkungen zum Begriff Stammfunktion 473
Ansätze zur Definition des Integralsxx0F(s)ds474
Notiz zuF(si) (s)i = F((ti)) (ti)(t)i475
Vektorfelder 475
Notwendige Integrationsbedingungen für Vektorfelder 476
Kurvenintegrale über Vektorfelder 477
Hinreichende Integrationsbedingungen für Vektorfelder 480
Existenz eines globalen Potenzials trotz Existenz einer Singularität 481
Beispielhafte Berechnung einer Potenzialfunktion 482
Kapitel 21 Steilkurs in komplexer Funktionentheorie485
Das formale Rechnen mit komplexen Zahlen 485
Addition komplexer Zahlen 486
Multiplikation komplexer Zahlen 486
Inverse komplexer Zahlen 486
Komplexe Zahlen als abstrakter Datentyp 487
Äquivalente Modelle komplexer Zahlen 487
Alternative Modelle 488
Auch Äquivalenzklassen von Polynomen verhalten sich wie komplexe Zahlen 490
Komplexe Differenzierbarkeit 492
Quick-and-dirty-Überlegungen 492
Ein zweiter Blick auf die Differenzierbarkeit komplexwertiger Funktionen 493
Komplexe Kurvenintegrale 494
Kurvenintegrale und komplexe Differenzierbarkeit 495
Auf dem Weg zur Cauchyschen Integralformel 496
Beweis der Cauchyschen Integralformel 496
Analytizität komplex differenzierbarer Formeln 498
Drei wichtige Folgerungen 500
Kapitel 22 Hilberträume 503
Komplexe Vektorräume 504
Komplexe Skalarprodukte 505
Beispiele komplexer Vektorräume 507
Hilbertbasen für Tupel 510
Hilbertbasen für Treppenfunktionen 511
Reduktionen der Treppenbreite 512
Treppenfunktionen der Treppenbreite 512
Ein neuer Ansatz eine letzte Chance 515
Neue Basen, neue Normierungen 519
Die-Funktion ein »Außenskelett« für Hilberträume 522
Management summary des Wegs hin zur-Funktion 524
Der Hilbertraum der periodischen Funktionen 526
Funktionen mit Periode 2 526
Diee-Funktionen als universelle Bausteine 526
Fourieranalyse und Fourierkoeffizienten 527
Basistransformationen 528
Fouriertransformationen nicht periodischer Funktionen 529
Basisfunktionen für 2l-periodische Funktionen 530
Analyse des Übergangsl 530
Die Fouriertransformationen als Basistransformationen 532
Hilberträume in der Physik 533
Vektoren in der klassischen Physik 533
Vektoren in der Mikrophysik 534
Abstrakte Vektoren im Hilbertraum 534
Orte und Impulse 535
Die Heisenbergsche Unschärferelation 536
Hilberträume im Quantencomputing elementare Konzepte 539
Bits und Qubits 539
Bloch-Sphäre 540
Operationen auf der Bloch-Sphäre 541
2-Qubits 542
EPR-Paare und Quantenteleportation 544
Teil VII: Anhang 547
Anhang A:Methoden einer funktionellen Mengentheorie 549
Zielkonflikte 549
Java-Z-Funktionen 550
Anhang B:Binomialverteilung versus Poissonverteilung 565
Anhang C:Programmierung komplexer Zahlen als abstrakte Datentypen 567
Anhang D:Berechnung von Determinanten 575
Anhang E:Matrizenkalküle 581
Matrixmultiplikation 581
Anhang F:Benutzte Symbole 585
Stichwortverzeichnis 589
