Vorkurs Informatik für Dummies

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.

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