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.
Inhaltsverzeichnis
Ü 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 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 + 1 n)n und (1 + 1 n)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 Differenzierbarkeit 229
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-Symbole o() und O() 243
Differenzierbarkeit via o(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 der e-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 l'Hospital 259
Wichtige Beispiele fü r die Anwendung der l'Hospitalschen Regeln 261
Taylorpolynome und Taylorentwicklung 263
Beispiele von Taylorentwicklungen 267
Analytische Funktionen als 'ganzheitliche' Funktionen 270
Kapitel 11 Integrale 271
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 Regellosen 285
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 gut 341
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 und 2-Test 358
Kapitel 15 Probabilistische Algorithmen - theoretisch interessant aus praktischen Grü nden 361
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 Zahlen 377
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 Vektorraumes V praktisch? 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 Algebra 439
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 Differenzierbarkeit 455
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 Integrals x x0F( s)ds 474
Notiz zu F(si) ( s)i = F( (ti)) (t i)( t)i 475
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 Funktionentheorie 485
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
Die e-Funktionen als universelle Bausteine 526
Fourieranalyse und Fourierkoeffizienten 527
Basistransformationen 528
Fouriertransformationen nicht periodischer Funktionen 529
Basisfunktionen fü r 2 l-periodische Funktionen 530
Analyse des Ü bergangs l 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
