Möchten Sie Informatik studieren und sich vorbereiten, um peinliche Wissenslücken zu vermeiden? Dann ist dieses Buch genau das richtige für Sie! Es verschafft Ihnen einen verständlichen und strukturierten Einblick in die Grundlagen der Informatik. Von der notwendigen Mathematik über erste Programmierschritte mit Python und Java bis zu Kryptografie, Datenbanken und Theoretischer Informatik ist alles dabei. Der Autor kennt die typischen Probleme und Verständnishürden der Erstsemester und hilft Ihnen, einen guten Start ins Informatikstudium zu finden. Und dazu brauchen Sie außer Schulmathe und Interesse für Informatik keinerlei Vorkenntnisse. Also los geht? s, starten Sie gut vorbereitet ins Studium.
Inhaltsverzeichnis
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
