Einleitung 19
Über dieses Buch 19
Konventionen in diesem Buch 19
Was Sie nicht lesen müssen 20
Törichte Annahmen über den Leser 20
Wie dieses Buch aufgebaut ist 21
Teil I: Programmieren 21
Teil II: Algorithmen 21
Teil III: Mathematik 21
Teil IV: Codierung 22
Teil V: Praktische Informatik 22
Teil VI: Theoretische Informatik 22
Teil VII: Top-Ten-Teil 23
Symbole, die in diesem Buch verwendet werden 23
Wie es weitergeht 24
Bitte und Danke sagen 24
Teil I: Programmieren 25
Kapitel 1 Programmieren in Java 27
Wertzuweisung 27
Variablen deklarieren 28
Wozu Datentypen? 28
Einen Wert zuweisen 29
Einen Wert überschreiben 30
Numerische Datentypen und Operationen 31
Typumwandlung bei numerischen Datentypen 32
Bedingte Anweisung 33
If-Anweisung 33
If-Else-Anweisung 34
Flussdiagramme zeichnen 35
Datentyp boolean 36
Boolesche Operationen 38
Kommentare 39
Zum Üben 39
Kapitel 2 Programmschleifen, Datenfolgen und Zeichenketten 41
While-Schleife 41
Fakultäten berechnen 43
Programmschleifen entwerfen 44
Iterationsschema aufstellen 44
Iterationsgleichungen ableiten 44
Regeln für das Aufstellen der Iterationsgleichungen 45
Iterationsgleichungen in eine While-Schleife umsetzen 45
For-Schleife 46
Arrays 47
Array erzeugen 47
Array durchlaufen 48
Strings 49
Strings verketten 50
String-Methoden anwenden 50
Zum Üben 52
Iterationsschema aufstellen und in While-Schleife umsetzen 52
Primzahlen mit dem Sieb des Eratosthenes 52
Kapitel 3 Funktionen 55
Funktionen definieren und aufrufen 55
Funktionsdefinition 56
Funktionsaufruf 57
So funktioniert ein Stack 58
Lokale Variablen benutzen 59
Funktionen mit mehreren Parametern 60
Funktionen ohne Parameter 61
Funktionen ohne Rückgabewert 61
Rekursive Funktionen 63
Ausführung einer rekursiven Funktion 63
Zum Üben 66
Ziehung der Lottozahlen 66
Kapitel 4 Objektorientiert programmieren 69
Klasse und Objekt 69
Attribute und Methoden 69
Kommentare und Benennungen 70
Bruchrechnung 70
Methoden 71
Rechenoperationen mit Brüchen 73
Bruch normalisieren 74
Bruch kürzen 75
Objektorientierung in Java 76
Zum Üben 76
Teil II: Algorithmen 77
Kapitel 5 Algorithmus 79
Typische Anweisungsformen 79
Algorithmisch denken 80
Kapitel 6 Binäre Suche 81
Suchstrategie 81
Logarithmus 82
Algorithmus binäre Suche 83
Zum Üben 84
Kapitel 7 Einfaches Sortieren 85
Minimum einer Datenfolge bestimmen 85
Selectionsort 86
Array sortieren 87
Programm 87
Zeitkomplexität 88
Analyse von Selectionsort 89
Kapitel 8 Zeitkomplexität von Algorithmen 91
Zeitkomplexität 92
Untere und obere Schranken 92
Schlechtester Fall 93
Asymptotische Analyse 93
O-Notation 94
Zum Üben 95
Kapitel 9 Mergesort 97
Divide-and-Conquer-Strategie 97
Ablauf von Mergesort 98
Verschmelzen zweier sortierter Hälften eines Arrays 98
Implementierung 99
Zeitkomplexität 101
Untere Schranke für das Sortieren 101
Zum Üben 102
Kapitel 10 Kürzeste Wege in einem Graphen 103
Idee des Verfahrens 103
Greedy-Strategie 105
Umsetzung in einen Algorithmus 105
Kapitel 11 Kürzeste Rundreise 107
Problem des Handlungsreisenden 108
Die Mengen P und NP 108
Nichtdeterministischer Algorithmus 109
Polynomielle Zeitkomplexität 110
NP-vollständige Probleme 111
Erfüllbarkeitsproblem (SAT) 112
Reduktion von SAT auf CLIQUE 112
Teil III: Mathematik 115
Kapitel 12 Logik 117
Logische Aussagen 117
Logische Verknüpfungen 118
Formale Logik 120
Allgemeingültige Aussagen 121
Gesetze der Logik 121
Logik im Alltag 123
Entweder Oder oder Entweder-Oder 123
Wenn-dann in der Umgangssprache 123
Die Tücken der logischen Folgerung 124
Prädikate 125
Quantoren 125
Zum Üben 127
Kapitel 13 Menge 129
Mengen bilden 129
Teilmenge 131
Die leere Menge 132
Potenzmenge 134
Mengen verknüpfen 134
Komplement 135
Gesetze der Mengenlehre 136
Duale Gesetze 136
Zum Üben 137
Kapitel 14 Relation 139
Kartesisches Produkt 139
Relation als Teilmenge eines kartesischen Produkts 140
Schreibweise von Relationen 141
Relationen anschaulich darstellen 141
Eigenschaften von Relationen 143
Beispiele dieser Eigenschaften 143
Ordnungsrelation und Äquivalenzrelation 144
Operationen auf Relationen 145
n-stellige Relationen 146
Wozu brauchen wir das? 146
Zum Üben 147
Kapitel 15 Abbildung 149
Abbildung als spezielle Relation 149
Schreibweise für Abbildungen 151
Wertetabelle einer Abbildung 151
Funktion 152
Verknüpfungen 153
Wertetabelle einer Verknüpfung 153
Verknüpfungstafel 154
Eigenschaften von Abbildungen 154
Injektive Abbildung 154
Surjektive Abbildung 155
Wertetabellen von injektiven und surjektiven Abbildungen 156
Bijektive Abbildung 157
Mächtigkeit von Mengen 157
Folgen 158
Endliche Folgen 158
Zum Üben 159
Kapitel 16 Graph 161
Knoten und Kanten 161
Pfad 162
Baum 163
Ungerichteter Graph 164
Markierte Graphen 165
Zum Üben 166
Kapitel 17 Teilbarkeit und Modulo-Rechnung 167
Teilbarkeit 167
Ist null durch null teilbar? 168
Teiler einer Zahl 169
Größter gemeinsamer Teiler 169
Primzahlen 170
Modulo-Rechnung 171
Modulo n rechnen 173
Zum Üben 174
Kapitel 18 Gruppen, Ringe und Körper 175
Die Gruppenaxiome 175
Elemente verknüpfen 176
Halbgruppe 177
Gruppe 178
Die Gruppe ¿¿n 179
Ring 180
Körper 181
Zum Üben 181
Kapitel 19 Beweistechniken 183
Direkter Beweis 183
Äquivalente Umformung 183
Direkte Umformung 184
Kontraposition 184
Beweis durch Widerspruch 185
Es gibt unendlich viele Primzahlen 185
Varianten des Widerspruchsbeweises 186
¿2 ist irrational 186
Gaußsche Summenformel 187
Beweis durch Induktion 187
Dominoeffekt 188
Zum Üben 190
Teil IV: Codierung 191
Kapitel 20 Boolesche Funktionen 193
Boolesche Funktionen darstellen 194
Boolesche Funktionen minimieren 195
Algebraische Umformung 195
KV-Diagramm 196
Blöcke mit Einsen zusammenfassen 197
Drei und vier Argumentvariablen 197
Anwendung 199
Realisierung mit Nand-Verknüpfungen 200
Zum Üben 201
Kapitel 21 Zahlendarstellung 203
Zahlensysteme zur Basis b 203
Zwischen Zahl und Darstellung hin und her rechnen 204
Programme 206
Zahlensysteme zu anderer Basis 207
Ganze Zahlen im Binärsystem 207
Betrag-Vorzeichen-Darstellung 208
Exzess-Darstellung 208
Einerkomplement-Darstellung 209
Zweierkomplement-Darstellung 209
Kommazahlen im Binärsystem 210
Rechnen mit Kommazahlen 211
Genauigkeit von Gleitkommazahlen 211
Zum Üben 212
Kapitel 22 Einfache Codes 213
Blockcodes 214
Hamming-Abstand 216
Fehlererkennung 216
Binärcode mit Paritätsbit 217
Kapitel 23 Daten komprimieren 219
Konstruktion des Huffman-Baums 219
Konstruktion des Huffman-Codes 221
Eigenschaften des Huffman-Codes 221
Informationsgehalt eines Textes 222
Zum Üben 222
Kapitel 24 Fehler erkennen mit CRC 223
Idee des Verfahrens 223
Polynom 224
Polynomdivision 225
Der CRC-Algorithmus 225
Erkennung von Fehlern 226
Zum Üben 227
Teil V: Praktische Informatik 229
Kapitel 25 Datenbanken 231
Datenbankrelationen 232
Attribut 233
Schlüssel 234
Datenbankentwurf 235
Entitäten und Beziehungen 235
Schlüssel und Fremdschlüssel 236
Entity-Relationship-Diagramm 237
Datenbankanfragen 238
Index 240
Datenbankmanagementsystem 242
Zum Üben 242
Kapitel 26 Computernetze 243
Adressen 243
Protokoll 244
Protokolle im täglichen Leben 244
Protokollstapel 245
Schnittstellen 246
Protokolle in der Informatik 246
Kapitel 27 Verschlüsseln mit öffentlichem Schlüssel 249
Diffie-Hellman-Schlüsselvereinbarung 250
Ablauf des Verfahrens 251
Problem des diskreten Logarithmus 251
Public-Key-Verschlüsselung 252
RSA-Verfahren 253
Schlüssel erzeugen 254
Sicherheit 254
Berechnungsverfahren 254
Primzahltest 254
Schnelle Exponentiation 255
Größter gemeinsamer Teiler 257
Zum Üben 257
Teil VI: Theoretische Informatik 259
Kapitel 28 Berechenbarkeit 261
Das Halteproblem 262
Praktisch nicht berechenbar 263
Kapitel 29 Reguläre Sprachen 265
Regulärer Ausdruck 266
Reguläre Operationen 266
Endlicher Automat 268
Arbeitsweise des Automaten 269
Formale Definition 270
Deterministisch und nichtdeterministisch 271
Simulation eines nichtdeterministischen endlichen Automaten 273
Teilmengenkonstruktion 275
Endliche Automaten und reguläre Sprachen 276
Sprachen, die nicht regulär sind 277
Zum Üben 278
Kapitel 30 Kontextfreie Grammatik und Stackautomat 279
Kontextfreie Grammatik 279
Wörter ableiten 280
Eine Sprache erzeugen 281
Wörter reduzieren 281
Rechtslineare Grammatik 282
Noch ein Beispiel 283
Stackautomat 283
Erkennung von Wörtern 285
Zum Üben 286
Kapitel 31 Sprachklassen und Turingmaschinen 289
Hierarchie der Sprachklassen 289
Die Sprachklassen L0 und L1 290
Grammatiken für L0 290
Grammatiken für L1 290
Turingmaschine 292
Formale Definition 293
Arbeitsweise der Turingmaschine 293
Turingtabelle 294
Mit Turingmaschinen erkennbare Sprachen 295
Entscheidbare Sprachen 295
Nichtdeterministische und deterministische
Turingmaschinen 296
Kapitel 32 Parser und Compiler 299
Grammatik als Ausgangspunkt 299
Parser für arithmetische Ausdrücke 300
Compiler für arithmetische Ausdrücke 303
Basisfunktionen für Parser und Compiler 304
Zum Üben 307
Teil VII: Top-10-Teil 309
Kapitel 33 Vier mal sieben 311
Die 7 elementarsten Begriffe 311
Die 7 verrücktesten Dinge 312
Die 7 cleversten Algorithmen 313
Die 7 bedeutendsten Informatik-Pioniere 315
Teil VIII: Anhang 317
Anhang A: Lösungen zu den Übungsaufgaben 319
Teil I: Programmieren 319
Teil II: Algorithmen 323
Teil III: Mathematik 325
Teil IV: Codierung 329
Teil V: Praktische Informatik 331
Teil VI: Theoretische Informatik 333
Anhang B: Zum Weiterlesen 337
Literaturverzeichnis 341
Stichwortverzeichnis 345
Vorbesteller Neu
