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...