Mathematik für Informatiker für Dummies

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 9Danksagungen 9Einleitung 25Über dieses Buch 25Wen hatten wir bei diesem Buch besonders vor Augen 25Durch welche Brille sehen wir also den Informatiker? 26Und was bedeutet dies für uns? 26Haben wir auch Nichtinformatiker als potenzielle Leser im Blick 27Wie kann man dieses Buch lesen? 27Welche Besonderheiten finden sich in unserem Buch 27Auf welche weiteren (kleinen) Innovationen dürfen wir hinweisen? 28Wann ist genug genug? 29Und weitere Literatur ? 29Kommunikation mit Autoren 30Teil I: Natürliche Zahlen und Mengen – im Auge des Informatikers 31Kapitel 1 Zahlen und ihre Logik 33Was es über die Vielfalt der Zahlen zu sagen gibt 33Zahlen zählen 34Zahlen aufs Papier – und später auf den Rechner 35Es darf auch etwas mehr sein – über die natürlichen Zahlen hinaus 36Ganzzahlige Brüche – ein zweiter Nachschlag 37Die Welt der rationalen Zahlen ist für Informatiker genug – Mathematiker sind weniger bescheiden 39Komplexe Zahlen erweitern den Zahlenraum ein weiteres Mal 41Blick auf die Gipfel: Hyperkomplexe Zahlen und Oktionen 44Wir wissen nun, über was wir reden, wir wollen jetzt wissen, wie wir darüber reden 45Prädikat – besonders wertvoll 45(Mathematische) Wahrheit 46Operatoren – Aus Zahlen werden Zahlen 47Logische Operatoren – Schnittstellen zur Logik 48Verrechnung von Wahrheitswerten 48Junktoren 48Wahrheitstabellen 49Für den einen ist es duplo, für den anderen die längste Praline der Welt – zur Doppelrolle der Zahlen in der formalen Logik 49Quantoren in der Logik – Prädikate erhalten durch sie ihre Power 52Der Existenzquantor ∃ 53Umsetzung des Existenzquantors in eine Schleife für Programmierer 53Allquantor ∀ 54Kapitel 2 Im Assembler-Code der Mathematik – Handreichungen für Ungläubige 57Gehen wir zurück auf Los 57Was passiert eigentlich beim Rechnen? 58Wir bringen dem Computer das Rechnen bei 58Wie sehen die nächsten Schritte aus? 59Rekursion – Vorbereitungen für die Induktion 60Induktion – mit Warp 10 durch alle Zahlen 62Anwendungen der Induktion – Return on invest 63Beweis des Assoziativgesetzes 64Wir kennen die Zahlen vom Zählen her – können wir sie auch abstract charakterisieren? 65Unendlich viele Zahlen auf einem endlichen Rechner? 66Kapitel 3 Mengenlehre – im Maschinenraum der Mathematik 69Mengenlehre – fängt man damit nicht immer an? 70Die Sprache der Mengenlehre – Goethe wäre »not« 70Erste Anforderungen an den Mengenbegriff 71Mengentheoretische Operationen 72Äquivalenz von Aussagen – Gleichheit von Mengen 74Eigenschaften der Operationen ∪, ∩ und ∖ 74Fallstricke und Sicherungen 76Weitere mengentheoretische Operationen 77Mengen als logische Bausteine für die Implementierung von Zahlen 80Spezielle Realisierungen des Zählprozesses 80Mengen – was kann man sich darunter vorstellen 83Linux-Filesystem als Modell für ein Mengensystem 83Infinite in all directions 85Mengen für Datenbanker 86Abstraktionen 87Datenbanken? – Keep it simple and stupid 88Nur für Theoretiker: Suchen, bis die Sterne verglühen 88Wer hat Angst vor Graphen? 90Urlemente – ein bisschen Medienbruch 92Mengenlehre für »Informatiker mit der harten Kinnlade« 93Prädikatenlogik mit einem einzigen Prädikat 93Skolemisierung – oder wie destilliert man Operationen aus Aussagen 96Teil II: Diskrete Strukturen 99Kapitel 4 Spezielle Beziehungen – Äquivalenzen und Ordnungen 101Äquivalenzrelationen – das Gleiche versus dasselbe 102Äquivalenzrelation – die Erste 103Äquivalenzrelation – die Zweite 108Ordnungsrelationen – Ordnung in der mathematischen Welt 109Geordnete Zahlen – die kleiner/gleich Beziehung 109Verträglichkeiten 110Teilbarkeit – auch eine Ordnung 111Auch die Teilbarkeit ist relativ verträglich und pflegeleicht 111Die mengentheoretische Inklusion – eine Ordnung für sich 112Die Ordnungsbeziehungen – was haben sie gemein, was unterscheidet sie 112Ordnungsbeziehungen und Grenzen 113Graphen als Medium für die Darstellung partieller Ordnungen 114Kapitel 5 Allgemeine Beziehungen und Beziehungskisten 117Beziehungen als Tabellen 118Inoffizielle Beziehungen 119Realisierungen inoffizieller Beziehungen 120Operieren mit Beziehungen 122Jemanden kennen, der jemanden kennt, der Beziehungen hat 123Spezialfälle: Verknüpfungen mit der inversen Beziehung 124Verknüpfungen unterschiedlicher Relationen 125Ausblick auf Relationen zwischen unterschiedlichen Mengen 126Eindeutige Beziehungen – auf dem Weg zu Funktionen 127Väter und Väter von Vätern 128Funktionen und ihre allgemeinen Eigenschaften 129Kapitel 6 Gruppen – es kann nicht nur eine geben 131Über die Addition ganzer Zahlen 131Beweis der Eindeutigkeit des neutralen Elements 132Von den ganzen Zahlen zum allgemeinen Gruppenbegriff 132Abstrakte kommutative Gruppen G 133Nichtkommutative Gruppen 133Beispiele von in der Natur auftretenden Gruppen – Symmetriegruppen 134Gruppen und Faktorgruppen 139Faktorgruppen der ganzen Zahlen 139Allgemeine Gruppen und Faktorgruppen 141Der Index einer Untergruppe H ⊂ G 142Untergruppen endlicher Gruppen 143Kapitel 7 Ringe und Körper 147Überblick Ringe 148Überblick Körper 149Ein Rückblick auf die Teilbarkeit und die Primzahlen 149ℤn als Restklassenring 151Wohldefiniertheit der Operationen auf den Restklassen 151Der Euklidische Algorithmus 152Einheiten in ℤn 153Eulersche 𝜑-Funktion 153Return on Invest – das RSA Verfahren in der Kryptologie 154Asymmetrische Verschlüsselungsverfahren 155Das RSA-Verfahren in der Theorie 155Praktische Bemerkungen zum RSA-Verfahren 157Kapitel 8 Graphentheorie 159Zur Motivation 159Das Haus vom Nikolaus 160Gerichtete und ungerichtete Graphen 160Zusammenhängende und unzusammenhängende Graphen 161Schlingen und parallele Kanten, Nullgraph und einfacher Graph 162Eckengrad 163Algorithmische Eigenschaften des Eckengrads 164Handshake-Lemma 164Königsberger Brückenproblem 166Eulergraph und Eigenschaften 167Eulerkreis/Eulersche Touren 168Adjazenzmatrix 168Wann sind Graphen isomorph? – Adjazenzmatrizen 169Alternative Tabellendarstellung – Inzidenzmatrizen 170Bäume 171Definition und Eigenschaften eines Baumes 171Spannbaum 171Definition von Wäldern 171Wurzelbaum 172Binärbäume 174Suchbaum 175Traversieren von Wurzelbäumen 175Wie gehören Binärbäume und algebraische Ausdrücke zusammen? 176Kürzeste Wege finden 177Kruskal-Algorithmus 180Prim-Algorithmus 180Dijkstra-Algorithmus 181Teil III: Analysis für Informatiker 183Kapitel 9 Reelle Zahlen – der virtuelle Sprung in die Unendlichkeit 185Irrationale Zahlen 185√2 ist eine irrationale Zahl 186Reelle Zahlen 187Die Einführung der reellen Zahlen – für Informatiker eine kleine Revolution 188Elementare Eigenschaften der reellen Zahlen 189Abschätzungen, die Analysis lebt davon 191Betragsfunktion und Dreiecksungleichung 191Bernoullische Ungleichung 193Der Umgebungsbegriff 194Unendliche Folgen 194Technische Definition der Konvergenz 196Arbeiten mit der technischen Definition 196Besondere Eigenschaften konvergenter Folgen 197Hinreichende Konvergenzbedingungen beschränkter Folgen 198Wichtige Spezialfälle: Die Folgen (1 + 1∕n)n und (1 + 1∕n)n+1 200Rekursiv definierte Folgen 201Häufungspunkte von Folgen 205Grenzwertsätze für Folgen – Handreichungen für Klausuren 206Beweis des ersten Grenzwertsatzes 206Beispielhafte Folgerungen aus den Grenzwertsätzen 207Mehr Werkzeuge zur Bestimmung des Konvergenzverhaltens 209Das Cauchysche Konvergenzkriterium 209Grenzwerte unendlicher Reihen 210Die harmonische Reihe 210Begriffliche Einordnung der unendlichen Reihen 211Cauchysche Konvergenzkriterium für unendliche Reihen 212Einfache Beispiele unendlicher Reihen 212Wurzel- und Quotientenkriterium – die wichtigsten Konvergenzkriterien für Reihen 213Absolute Konvergenz 218Die allgemeine binomische Formel 224Die Fakultätsfunktion 224Binomialkoeffizienten 225Binomische Formel 226Kapitel 10 Pflegeleichte Funktionen – Stetigkeit und Differenzierbarkeit 229Grundsätzliche Bemerkungen 230»Durchhalteparolen« für die Analysis 231Der Grenzwertbegriff bei Funktionen 232Konvergenz mithilfe des Umgebungsbegriffs 233Konvergenz unter Rückgriff auf Folgenkonvergenz 233Konvergenzsätze 235Anwendung der Konvergenzsätze auf die Exponentialfunktion 236Stetige Funktionen 239Beispiel einer Funktion, die nur an einer Stelle stetig ist 240Wichtige Eigenschaften stetiger Funktionen 240Differenzierbare Funktionen 243Die Landau-Symbole o() und O() 243Differenzierbarkeit via o(x) 244Differenzierbarkeit via Differenzenquotient 245Beide Definitionen der Differenzierbarkeit sind äquivalent 247Rechenregeln für Ableitungen 249Verträglichkeit der Differenzialquotienten mit der Summenbildung 249Produktregel 249Quotientenregel 250Kettenregel 251Wichtige Beispiele differenzierbarer Funktionen 252Differenzierbarkeit der Polynome 252Ableitung der e-Funktion und des Logarithmus 253Ableitungen der trigonometrischen Funktionen 254Der Mittelwertsatz der Differenzialrechnung 257Der Satz von Rolle 258Folgerungen aus dem Mittelwertsatz 259Die Regeln von l’Hospital 259Wichtige Beispiele für die Anwendung der l’Hospitalschen Regeln 261Taylorpolynome und Taylorentwicklung 263Beispiele von Taylorentwicklungen 267Analytische Funktionen als »ganzheitliche« Funktionen 270Kapitel 11 Integrale 271Stammfunktionen 271Integrale elementarer Funktionen 272Partielle Integration 273Integration per Substitution 275Rationale Funktionen und Partialbruchzerlegungen 276Bestimmte Integrale 279Einstieg in die Flächenberechnung 279Stammfunktionen »in action« 281Teil IV: Vom Würfelspiel zum Algorithmus 283Kapitel 12 Wahrscheinlichkeitsrechnung – Regeln im Regellosen 285Am Anfang war das Spiel – grundlegende Begrifflichkeiten der Wahrscheinlichkeitsrechnung 286Ereignisse und Elementarereignisse 286Wahrscheinlichkeiten 290Ereignisse und Wahrscheinlichkeiten im formalen Rahmen 295Bedingte Wahrscheinlichkeiten – corriger la fortune 297Bedingte Wahrscheinlichkeiten reengineered – die Formel von Bayes 302Zufallsvariable – geeignete Codierungen zufälliger Ereignisse 303Zufallsvariable – Übertragung von Wahrscheinlichkeiten auf Zahlenmengen 304Summen und Produkte von Zufallsvariablen 305Von der Zufallsvariablen zur Verteilungsfunktion 306Mittelwerte in verschiedenen Ausprägungen: Erwartungswerte und Varianzen 308Der Erwartungswert der Streuung – die Varianz 311Korrelationen – synchrone Streuungen 313Kapitel 13 Die klassischen Verteilungen 317Binomialverteilung 317Münzwurf mit geänderten Spielregeln 318Erwartungswerte und Varianzen für binomialverteilte Zufallsvariablen 319Geometrische Verteilung 321Geänderte Spielregeln 322Poissonverteilte Zufallsvariablen 323Näherungsverfahren für die Binomialverteilung – die Poissonverteilung 324Erwartungswerte und Varianzen poissonverteilter Zufallsvariablen 326Stetige Verteilungen 328Exponentialverteilung 329Normalverteilung 333Kapitel 14 Testen! – Denn Vertrauen ist nicht immer gut 341Die Ungleichung von Tschebyscheff 343Normalverteilung und Tschebyscheffsche Ungleichung in der Gegenüberstellung 345Tschebyscheffsche Ungleichung und die Gesetze der großen Zahlen 347Beispielhafte Anwendung des Maximum-Likelihood-Prinzips 349Über das Testen von Hypothesen 350Signifikanztests 350Alternativtests 353χ2-Anpassung und χ2-Test 358Kapitel 15 Probabilistische Algorithmen – theoretisch interessant aus praktischen Gründen 361Sortierverfahren 362Statistische Analyse des Quicksorts 362Monte Carlo und Las Vegas – die ganze Wahrheit und nichts als die Wahrheit 364Quicksort durch die Brille von Las Vegas betrachtet 364Las Vegas liberalisiert – nur noch »nichts als die Wahrheit« 364Monte Carlo – »die ganze Wahrheit« 370Teil V: Sprung in den Hyperraum 375Kapitel 16 Vektoren – aggregierte Zahlen 377Erste Operationen mit Vektoren: Addition und skalare Multiplikation 377Kräfte können in unterschiedlichen Reihenfolgen addiert werden 378Die Addition von drei oder mehr Vektoren kann unterschiedlich geklammert werden 378Zu jedem Vektor gibt es einen inversen Vektor 379Vektoren können mit Zahlen multipliziert werden 380Auch Geschwindigkeiten sind Vektoren 380Das Skalarprodukt – hiermit erhält die Vektorrechnung ihre eigentliche Power 382Das Skalarprodukt als Mittel zur Berechnung physikalischer Arbeit 382Das Skalarprodukt erfasst geometrisch wichtige Sachverhalte – Orthogonalität, Länge und Abstand 383Die Algebraisierung der Geometrie 383Algebraisierung der Geometrie 384Die Algebraisierung der Geometrie zum Zweiten 387Die Seitenhalbierenden – revisited 387Vektoren in Koordinatensystemen 389Auch umgekehrt wird ein Schuh draus: Vektoren erzeugen ein Koordinatensystem 393Abstrakte Vektoren: Vektorräume 397Einstieg in die Klasse Vector 397Spezifikation von Vektorräumen 399Strategische Begriffe 401Auch der abstrakte Vektorraum kann als Aggregat von Zahlen aufgefasst werden 406Aber wie decodieren wir ein 𝑣 eines abstrakten Vektorraumes V praktisch? 408Erweiterung der Vektorraumspezifikation durch abstrakte Skalarprodukte 411Die zweite Chance des Mathematikers 417Die Natur spielt mit 418Kapitel 17 Transformationen 419Duale Basen 420Kovariante und kontravariante Komponenten 422Die Beziehungen zwischen kovarianten und kontravarianten Komponenten 422Der Übergang zwischen ko- und kontravarianten Koordinaten bei orthonormierten Basen 423Nicht orthonormale Basen – könnten wir auf sie verzichten? 424Asymmetrische Verschlüsselungsverfahren mit Hilfe dualer Basen 426Lineare Abbildungen 427Drehungen 427Matrizen – operationelle Codierung linearer Abbildungen 428Basistransformationen 434Matrizen der Basistransformation 434Besondere Eigenschaften der Matrizen der Basistransformationen 434Die Matrizen der Basistransformationen als Matrizen einer Abbildung 435Basistransformationen orthonormierter Basen 437Kapitel 18 Lineare Gleichungssysteme – Number Crunching in der linearen Algebra 439Gleichungssysteme und zugehörige Matrizen 440Bedingungen der Lösbarkeit von Gleichungssystemen 441Der Gaußsche Algorithmus 442Homogene und inhomogene Gleichungssysteme 445Determinanten in Aktion 446Eigenwerte und Eigenvektoren 448Auffinden der Eigenwerte 449Berechnung der Eigenvektoren 449Eigenvektoren und Diagonalisierung von Matrizen 450Besonderheiten symmetrischer Matrizen 451Teil VI: Höhere Weihen in der Analysis 453Kapitel 19 Skalierung der Differenzierbarkeit 455Behandlung von Funktionen zweier Variablen 455Differenzierbarkeit von Funktionen zweier Variablen 456Nichtdifferenzierbare Funktionen trotz Existenz partieller Ableitung 458Hinreichende Bedingungen für die Differenzierbarkeit 461Behandlung von Funktionen beliebig vieler Variablen 462Vektorwertige Funktionen 463Differenzierbarkeit vektorwertiger Funktionen 463Rechenregeln für Gradienten und Funktionalmatrizen 464Hesse-Matrix und Taylorentwicklungen 466∇ als Vektoroperator 466Kritische Punkte und Extremwerte 468Analyse der Hesse-Matrix 469Beispielrechnung zur Analyse kritischer Punkte 470Kapitel 20 Potenziale als Stammfunktionen 473Generelle Bemerkungen zum Begriff Stammfunktion 473Ansätze zur Definition des Integrals ∫x⃗x0F(⃗s)ds 474Notiz zu F(si) ⋅ (Δs)i = F(α(ti)) ⋅ α(ṫ i)(Δt)i 475Vektorfelder 475Notwendige Integrationsbedingungen für Vektorfelder 476Kurvenintegrale über Vektorfelder 477Hinreichende Integrationsbedingungen für Vektorfelder 480Existenz eines globalen Potenzials trotz Existenz einer Singularität 481Beispielhafte Berechnung einer Potenzialfunktion 482Kapitel 21 Steilkurs in komplexer Funktionentheorie 485Das formale Rechnen mit komplexen Zahlen 485Addition komplexer Zahlen 486Multiplikation komplexer Zahlen 486Inverse komplexer Zahlen 486Komplexe Zahlen als abstrakter Datentyp 487Äquivalente Modelle komplexer Zahlen 487Alternative Modelle 488Auch Äquivalenzklassen von Polynomen verhalten sich wie komplexe Zahlen 490Komplexe Differenzierbarkeit 492Quick-and-dirty-Überlegungen 492Ein zweiter Blick auf die Differenzierbarkeit komplexwertiger Funktionen 493Komplexe Kurvenintegrale 494Kurvenintegrale und komplexe Differenzierbarkeit 495Auf dem Weg zur Cauchyschen Integralformel 496Beweis der Cauchyschen Integralformel 496Analytizität komplex differenzierbarer Formeln 498Drei wichtige Folgerungen 500Kapitel 22 Hilberträume 503Komplexe Vektorräume 504Komplexe Skalarprodukte 505Beispiele komplexer Vektorräume 507Hilbertbasen für Tupel 510Hilbertbasen für Treppenfunktionen 511Reduktionen der Treppenbreite 512Treppenfunktionen der Treppenbreite 512Ein neuer Ansatz – eine letzte Chance 515Neue Basen, neue Normierungen 519Die δ-Funktion – ein »Außenskelett« für Hilberträume 522Management summary des Wegs hin zur δ-Funktion 524Der Hilbertraum der periodischen Funktionen 526Funktionen mit Periode 2π 526Die e-Funktionen als universelle Bausteine 526Fourieranalyse und Fourierkoeffizienten 527Basistransformationen 528Fouriertransformationen nicht periodischer Funktionen 529Basisfunktionen für 2πl-periodische Funktionen 530Analyse des Übergangs l → ∞ 530Die Fouriertransformationen als Basistransformationen 532Hilberträume in der Physik 533Vektoren in der klassischen Physik 533Vektoren in der Mikrophysik 534Abstrakte Vektoren im Hilbertraum 534Orte und Impulse 535Die Heisenbergsche Unschärferelation 536Hilberträume im Quantencomputing –elementare Konzepte 539Bits und Qubits 539Bloch-Sphäre 540Operationen auf der Bloch-Sphäre 5412-Qubits 542EPR-Paare und Quantenteleportation 544Teil VII: Anhang 547Anhang A: Methoden einer funktionellen Mengentheorie 549Zielkonflikte 549Java-Z-Funktionen 550Anhang B: Binomialverteilung versus Poissonverteilung 565Anhang C: Programmierung komplexer Zahlen als abstrakte Datentypen 567Anhang D: Berechnung von Determinanten 575Anhang E: Matrizenkalküle 581Matrixmultiplikation 581Anhang F: Benutzte Symbole 585Stichwortverzeichnis 589