UEber den Autor 9
Danksagungen 9
Einleitung 25
UEber 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 fuer 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 duerfen wir hinweisen? 28
Wann ist genug genug? 29
Und weitere Literatur ? 29
Kommunikation mit Autoren 30
Teil I: Natuerliche Zahlen und Mengen - im Auge des Informatikers 31
Kapitel 1 Zahlen und ihre Logik 33
Was es ueber die Vielfalt der Zahlen zu sagen gibt 33
Zahlen zaehlen 34
Zahlen aufs Papier - und spaeter auf den Rechner 35
Es darf auch etwas mehr sein - ueber die natuerlichen Zahlen hinaus 36
Ganzzahlige Brueche - ein zweiter Nachschlag 37
Die Welt der rationalen Zahlen ist fuer 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, ueber was wir reden, wir wollen jetzt wissen, wie wir darueber reden 45
Praedikat - 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
Fuer den einen ist es duplo, fuer den anderen die laengste Praline der Welt - zur Doppelrolle der Zahlen in der formalen Logik 49
Quantoren in der Logik - Praedikate erhalten durch sie ihre Power 52
Der Existenzquantor ? 53
Umsetzung des Existenzquantors in eine Schleife fuer Programmierer 53
Allquantor ? 54
Kapitel 2 Im Assembler-Code der Mathematik - Handreichungen fuer Unglaeubige 57
Gehen wir zurueck auf Los 57
Was passiert eigentlich beim Rechnen? 58
Wir bringen dem Computer das Rechnen bei 58
Wie sehen die naechsten Schritte aus? 59
Rekursion - Vorbereitungen fuer 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 Zaehlen her - koennen wir sie auch abstract charakterisieren? 65
Unendlich viele Zahlen auf einem endlichen Rechner? 66
Kapitel 3 Mengenlehre - im Maschinenraum der Mathematik 69
Mengenlehre - faengt man damit nicht immer an? 70
Die Sprache der Mengenlehre - Goethe waere >>not<< 70
Erste Anforderungen an den Mengenbegriff 71
Mengentheoretische Operationen 72
AEquivalenz von Aussagen - Gleichheit von Mengen 74
Eigenschaften der Operationen ?, ? und ? 74
Fallstricke und Sicherungen 76
Weitere mengentheoretische Operationen 77
Mengen als logische Bausteine fuer die Implementierung von Zahlen 80
Spezielle Realisierungen des Zaehlprozesses 80
Mengen - was kann man sich darunter vorstellen 83
Linux-Filesystem als Modell fuer ein Mengensystem 83
Infinite in all directions 85
Mengen fuer Datenbanker 86
Abstraktionen 87
Datenbanken? - Keep it simple and stupid 88
Nur fuer Theoretiker: Suchen, bis die Sterne vergluehen 88
Wer hat Angst vor Graphen? 90
Urlemente - ein bisschen Medienbruch 92
Mengenlehre fuer >>Informatiker mit der harten Kinnlade<< 93
Praedikatenlogik mit einem einzigen Praedikat 93
Skolemisierung - oder wie destilliert man Operationen aus Aussagen 96
Teil II: Diskrete Strukturen 99
Kapitel 4 Spezielle Beziehungen - AEquivalenzen und Ordnungen 101
AEquivalenzrelationen - das Gleiche versus dasselbe 102
AEquivalenzrelation - die Erste 103
AEquivalenzrelation - die Zweite 108
Ordnungsrelationen - Ordnung in der mathematischen Welt 109
Geordnete Zahlen - die kleiner/gleich Beziehung 109
Vertraeglichkeiten 110
Teilbarkeit - auch eine Ordnung 111
Auch die Teilbarkeit ist relativ vertraeglich und pflegeleicht 111
Die mengentheoretische Inklusion - eine Ordnung fuer sich 112
Die Ordnungsbeziehungen - was haben sie gemein, was unterscheidet sie 112
Ordnungsbeziehungen und Grenzen 113
Graphen als Medium fuer 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
Spezialfaelle: Verknuepfungen mit der inversen Beziehung 124
Verknuepfungen unterschiedlicher Relationen 125
Ausblick auf Relationen zwischen unterschiedlichen Mengen 126
Eindeutige Beziehungen - auf dem Weg zu Funktionen 127
Vaeter und Vaeter von Vaetern 128
Funktionen und ihre allgemeinen Eigenschaften 129
Kapitel 6 Gruppen - es kann nicht nur eine geben 131
UEber 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 Koerper 147
UEberblick Ringe 148
UEberblick Koerper 149
Ein Rueckblick 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 Verschluesselungsverfahren 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
Zusammenhaengende und unzusammenhaengende Graphen 161
Schlingen und parallele Kanten, Nullgraph und einfacher Graph 162
Eckengrad 163
Algorithmische Eigenschaften des Eckengrads 164
Handshake-Lemma 164
Koenigsberger Brueckenproblem 166
Eulergraph und Eigenschaften 167
Eulerkreis/Eulersche Touren 168
Adjazenzmatrix 168
Wann sind Graphen isomorph? - Adjazenzmatrizen 169
Alternative Tabellendarstellung - Inzidenzmatrizen 170
Baeume 171
Definition und Eigenschaften eines Baumes 171
Spannbaum 171
Definition von Waeldern 171
Wurzelbaum 172
Binaerbaeume 174
Suchbaum 175
Traversieren von Wurzelbaeumen 175
Wie gehoeren Binaerbaeume und algebraische Ausdruecke zusammen? 176
Kuerzeste Wege finden 177
Kruskal-Algorithmus 180
Prim-Algorithmus 180
Dijkstra-Algorithmus 181
Teil III: Analysis fuer 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 Einfuehrung der reellen Zahlen - fuer Informatiker eine kleine Revolution 188
Elementare Eigenschaften der reellen Zahlen 189
Abschaetzungen, 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 beschraenkter Folgen 198
Wichtige Spezialfaelle: Die Folgen (1 + 1?n)n und (1 + 1?n)n+1 200
Rekursiv definierte Folgen 201
Haeufungspunkte von Folgen 205
Grenzwertsaetze fuer Folgen - Handreichungen fuer Klausuren 206
Beweis des ersten Grenzwertsatzes 206
Beispielhafte Folgerungen aus den Grenzwertsaetzen 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 fuer unendliche Reihen 212
Einfache Beispiele unendlicher Reihen 212
Wurzel- und Quotientenkriterium - die wichtigsten Konvergenzkriterien fuer Reihen 213
Absolute Konvergenz 218
Die allgemeine binomische Formel 224
Die Fakultaetsfunktion 224
Binomialkoeffizienten 225
Binomische Formel 226
Kapitel 10 Pflegeleichte Funktionen - Stetigkeit und Differenzierbarkeit 229
Grundsaetzliche Bemerkungen 230
>>Durchhalteparolen<< fuer die Analysis 231
Der Grenzwertbegriff bei Funktionen 232
Konvergenz mithilfe des Umgebungsbegriffs 233
Konvergenz unter Rueckgriff auf Folgenkonvergenz 233
Konvergenzsaetze 235
Anwendung der Konvergenzsaetze 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 aequivalent 247
Rechenregeln fuer Ableitungen 249
Vertraeglichkeit 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 fuer 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 Flaechenberechnung 279
Stammfunktionen >>in action<< 281
Teil IV: Vom Wuerfelspiel 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 zufaelliger Ereignisse 303
Zufallsvariable - UEbertragung von Wahrscheinlichkeiten auf Zahlenmengen 304
Summen und Produkte von Zufallsvariablen 305
Von der Zufallsvariablen zur Verteilungsfunktion 306
Mittelwerte in verschiedenen Auspraegungen: Erwartungswerte und Varianzen 308
Der Erwartungswert der Streuung - die Varianz 311
Korrelationen - synchrone Streuungen 313
Kapitel 13 Die klassischen Verteilungen 317
Binomialverteilung 317
Muenzwurf mit geaenderten Spielregeln 318
Erwartungswerte und Varianzen fuer binomialverteilte Zufallsvariablen 319
Geometrische Verteilung 321
Geaenderte Spielregeln 322
Poissonverteilte Zufallsvariablen 323
Naeherungsverfahren fuer 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 Gegenueberstellung 345
Tschebyscheffsche Ungleichung und die Gesetze der grossen Zahlen 347
Beispielhafte Anwendung des Maximum-Likelihood-Prinzips 349
UEber das Testen von Hypothesen 350
Signifikanztests 350
Alternativtests 353
?2-Anpassung und ?2-Test 358
Kapitel 15 Probabilistische Algorithmen - theoretisch interessant aus praktischen Gruenden 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
Kraefte koennen 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 koennen mit Zahlen multipliziert werden 380
Auch Geschwindigkeiten sind Vektoren 380
Das Skalarprodukt - hiermit erhaelt die Vektorrechnung ihre eigentliche Power 382
Das Skalarprodukt als Mittel zur Berechnung physikalischer Arbeit 382
Das Skalarprodukt erfasst geometrisch wichtige Sachverhalte - Orthogonalitaet, Laenge 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: Vektorraeume 397
Einstieg in die Klasse Vector 397
Spezifikation von Vektorraeumen 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 UEbergang zwischen ko- und kontravarianten Koordinaten bei orthonormierten Basen 423
Nicht orthonormale Basen - koennten wir auf sie verzichten? 424
Asymmetrische Verschluesselungsverfahren 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 zugehoerige Matrizen 440
Bedingungen der Loesbarkeit von Gleichungssystemen 441
Der Gausssche 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: Hoehere 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 fuer die Differenzierbarkeit 461
Behandlung von Funktionen beliebig vieler Variablen 462
Vektorwertige Funktionen 463
Differenzierbarkeit vektorwertiger Funktionen 463
Rechenregeln fuer 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
Ansaetze 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 fuer Vektorfelder 476
Kurvenintegrale ueber Vektorfelder 477
Hinreichende Integrationsbedingungen fuer Vektorfelder 480
Existenz eines globalen Potenzials trotz Existenz einer Singularitaet 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
AEquivalente Modelle komplexer Zahlen 487
Alternative Modelle 488
Auch AEquivalenzklassen von Polynomen verhalten sich wie komplexe Zahlen 490
Komplexe Differenzierbarkeit 492
Quick-and-dirty-UEberlegungen 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
Analytizitaet komplex differenzierbarer Formeln 498
Drei wichtige Folgerungen 500
Kapitel 22 Hilbertraeume 503
Komplexe Vektorraeume 504
Komplexe Skalarprodukte 505
Beispiele komplexer Vektorraeume 507
Hilbertbasen fuer Tupel 510
Hilbertbasen fuer 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 >>Aussenskelett<< fuer Hilbertraeume 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 fuer 2?l-periodische Funktionen 530
Analyse des UEbergangs l ? ? 530
Die Fouriertransformationen als Basistransformationen 532
Hilbertraeume 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 Unschaerferelation 536
Hilbertraeume im Quantencomputing -elementare Konzepte 539
Bits und Qubits 539
Bloch-Sphaere 540
Operationen auf der Bloch-Sphaere 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: Matrizenkalkuele 581
Matrixmultiplikation 581
Anhang F: Benutzte Symbole 585
Stichwortverzeichnis 589
