Vorkurs Informatik für Dummies

Produktbeschreibung

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 

Autoreninfo

Hans Werner Lang studierte Informatik an der Universität Kiel und promovierte dort 1990 zu einem Thema aus dem Bereich "Parallele Architekturen und Algorithmen". Von 1994 bis 2017 war er Professor für Informatik an der Hochschule Flensburg und hat in dieser Zeit zahlreiche Vorlesungen zur Informatik gehalten.