Helmut Herold • Bruno Lurz • Jürgen Wohlrab
Grundlagen der Informatik
Praktisch – Technisch – Theoretisch
ein Imprint von Pearson EducationMünchen • Boston • San Francisco • Harlow, England
Don Mills, Ontario • Sydney • Mexico CityMadrid • Amsterdam
Inhaltsverzeichnis
Kapitel 1 Einleitung 5
1.1 Idee dieses Buches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Beispiele, Übungen und Rätsel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Begleitmaterial zu diesem Buch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Benutzung der mitgelieferten CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5 Danksagung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.6 Hinweis in eigener Sache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Teil I Einführung in die Informatik 11
Kapitel 2 Die Historie und die Teilgebiete der Informatik 13
2.1 Rätsel: Streichholzprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Der Begriff Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3 Historische Entwicklung der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Der Abakus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.2 Der Begriff Algorithmus und Ibn Musa Al-Chwarismi . . . . . . . . . . . . 172.3.3 Wichtige Stationen von 1500 bis 1930 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3.4 Konrad Zuse und der erste funktionstüchtige Computer . . . . . . . . . 202.3.5 Howard H. Aiken und die Mark I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.6 John von Neumann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.7 Generationen der elektronischen Datenverarbeitung . . . . . . . . . . . . . 23
2.4 Einordnung und Einteilung der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.4.1 Verschiedene Einsatzgebiete von Computern (Informatik) . . . . . . . . 272.4.2 Die Teilgebiete der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.4.3 Die Informatik und unsere Abhängigkeit von ihr . . . . . . . . . . . . . . . . . 31
Kapitel 3 Speicherung und Interpretation von Information 33
3.1 Rätsel: Umfüllprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.2 Unterschiedliche Zahlensysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Das römische Zahlensystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.2.2 Positionssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.3 Positionssysteme bei natürlichen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . 363.2.4 Positionssysteme bei gebrochenen Zahlen . . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Dual-, Oktal- und Hexadezimalsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3.1 Das Dualsystem und das Bit im Rechner . . . . . . . . . . . . . . . . . . . . . . . . . 423.3.2 Konvertieren zwischen Dual- und Oktalsystem . . . . . . . . . . . . . . . . . . 433.3.3 Konvertieren zwischen Dual- und Hexadezimalsystem . . . . . . . . . . 43
3.4 Konvertierungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.4.1 Konvertieren von anderen Systemen in das Dezimalsystem . . . . . . 45
INHALTSVERZEICHNIS
3.4.2 Konvertieren vom Dezimalsystem in andere Positionssysteme . . . 453.4.3 Konvertieren echt gebrochener Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.4.4 Konvertieren unecht gebrochener Zahlen . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Rechenoperationen im Dualsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.5.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.5.2 Subtraktion und Darstellung negativer Zahlen . . . . . . . . . . . . . . . . . . . 493.5.3 Multiplikation und Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.5.4 Konvertieren durch sukzessive Multiplikation und Addition . . . . 53
3.6 Reelle Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.6.1 Festpunktzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.6.2 Gleitpunktzahlen und das IEEE-Format . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.7 Codes zur Darstellung von Zeichen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.7.1 ASCII-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.7.2 Unicode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.8 Weitere Codes für Zahlen und Zeichen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613.8.1 BCD-Code für Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613.8.2 Gray-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.8.3 Barcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.9 Duale Größenangaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.10 Die Grunddatentypen in der Programmiersprache C/C++ . . . . . . . . . . . . . . . . 63
Kapitel 4 Boolesche Algebra 79
4.1 Analytische Rätsel (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.2 George Boole und seine Algebra mit nur zwei Werten . . . . . . . . . . . . . . . . . . . . 804.3 Operatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814.4 Boolesche Schaltungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.5 Axiome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.6 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Kapitel 5 Hardware-Komponenten eines Computers 89
5.1 Analytische Rätsel (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.2 Aufbau von Computersystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.1 Zentraleinheit und Peripheriegeräte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.2.2 EVA und das von-Neumann’sche-Rechnermodell . . . . . . . . . . . . . . . . 91
5.3 Die heutigen Personal Computer (PCs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.4 Die Zentraleinheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4.1 Der Prozessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.4.2 Der Arbeitsspeicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.4.3 ROMs zur Speicherung von Programmen und konstanten Daten . 1075.4.4 Das BIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1095.4.5 Busse und Schnittstellen (Anschlüsse) . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.5 Die Peripherie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155.5.1 Massenspeicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155.5.2 Eingabegeräte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1205.5.3 Ausgabegeräte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6
Inhaltsverzeichnis
5.6 Modell eines einfachen Prozessorsystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1255.7 Alternative Rechnerarchitekturen (Neuronale Netze) . . . . . . . . . . . . . . . . . . . . 130
Kapitel 6 Vom Programm zum Maschinenprogramm 131
6.1 Analytische Rätsel (3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1326.2 Entwicklung eines Programms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1326.3 Programmierwerkzeuge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.3.1 Unterschiedliche Arten der Übersetzung . . . . . . . . . . . . . . . . . . . . . . . . . 1336.3.2 Der Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1346.3.3 Der Linker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1356.3.4 Der Lader (und Locator) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1376.3.5 Der Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Teil II Praktische Informatik 141
Kapitel 7 Programmiersprachen 143
7.1 Analytische Rätsel (4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1447.2 Höhere Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1447.3 Grundlagen der Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.3.1 Spezifikation einer Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1477.3.2 Der Begriff Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1487.3.3 Formulierung und Darstellung eines Algorithmus . . . . . . . . . . . . . . . 1487.3.4 Programm = Daten + Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.4 Datentypen und Operatoren in C/C++ und Java . . . . . . . . . . . . . . . . . . . . . . . . . . . 1567.4.1 Datentypen und Konstanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1567.4.2 Bezeichner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1587.4.3 Grundlegende Operatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1587.4.4 Die logischen Operatoren &&, || und ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1597.4.5 Die Shift-Operatoren > . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1597.4.6 Die Postfix- und Präfixoperatoren ++ und −− . . . . . . . . . . . . . . . . . . . 1607.4.7 Die Bit-Operatoren &, |, ^ und ∼ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1617.4.8 Prioritäten und Assoziativitäten der Operatoren . . . . . . . . . . . . . . . . . 162
7.5 Formulierung von Algorithmen in C/C++ und Java . . . . . . . . . . . . . . . . . . . . . . . 1647.5.1 Sequenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1647.5.2 Verzweigungen mit if . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1647.5.3 Verzweigungen mit switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1707.5.4 for-Schleife (Schleife mit der Abfrage am Anfang) . . . . . . . . . . . . . . . 1717.5.5 while-Schleife (Schleife mit der Abfrage am Anfang) . . . . . . . . . . . . 1787.5.6 do… while-Schleife (Schleife mit der Abfrage am Ende) . . . . . . . . . 1817.5.7 Abbruch von Schleifen mit break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1827.5.8 Abbruch eines einzelnen Schleifendurchlaufs mit continue . . . . . 1847.5.9 Abbruch mehrerer geschachtelter Schleifen mit goto . . . . . . . . . . . . . 1847.5.10 Programmabbruch mit exit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1857.5.11 Allgemeines zu Funktionen bzw. Methoden . . . . . . . . . . . . . . . . . . . . . . 1857.5.12 Rekursive Funktionen bzw. rekursive Methoden . . . . . . . . . . . . . . . . . 195
7
INHALTSVERZEICHNIS
7.5.13 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2047.5.14 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2097.5.15 Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2127.5.16 Argumente auf der Kommandozeile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2147.5.17 Ausnahmen (Exceptions) in Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2157.5.18 Dateien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2167.5.19 Strukturen in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.6 Objektorientierte Programmierung mit Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2277.6.1 Meilensteine in der Softwareentwicklung . . . . . . . . . . . . . . . . . . . . . . . . 2277.6.2 Einführung in die Objektorientierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2357.6.3 Klassen und Objekte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2427.6.4 Konstruktoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2487.6.5 Vererbung und Polymorphismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2497.6.6 GUI-Programmierung in Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Kapitel 8 Datenstrukturen und Algorithmen 271
8.1 Analytische Rätsel (5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2728.2 Grundlegende Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
8.2.1 Allgemeine Eigenschaften von Daten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2738.2.2 Basis-Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2738.2.3 Datenstruktur = Daten + Operationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2738.2.4 Verkettete Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2748.2.5 Stack (Stapel) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2878.2.6 Queue (Warteschlange) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
8.3 Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3008.3.1 Grundlegendes zu Bäumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3008.3.2 Binäre Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3028.3.3 Baumrekursion bei Bäumen mit mehr als zwei Zweigen . . . . . . . . . 317
8.4 Komplexität von Algorithmen und O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3288.4.1 Zeitaufwand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3288.4.2 Speicherplatzbedarf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3318.4.3 Klassifikation von Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3328.4.4 Die O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3348.4.5 Wahl eines Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3408.4.6 Einfache Optimierungen bei der Implementierung . . . . . . . . . . . . . . . 341
8.5 Elementare Sortieralgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3448.5.1 Grundsätzliches zu Sortieralgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . 3448.5.2 Bubble-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3458.5.3 Insert-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3478.5.4 Select-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3488.5.5 Zeitmessungen für Bubble-, Insert- und Select-Sort . . . . . . . . . . . . . . 3498.5.6 Distribution Count-Sort (Bucket-Sort) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
8.6 Shell-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3538.7 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3558.8 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
8.8.1 Rekursiver Mergesort für Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
8
Inhaltsverzeichnis
8.8.2 Nicht-rekursiver Mergesort für Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3598.8.3 Analyse des Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3608.8.4 Mischen von zwei sortierten Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
8.9 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3618.9.1 Finden in einem Labyrinth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3618.9.2 Das Achtdamen-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3638.9.3 Rekursives Füllen von Figuren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3658.9.4 Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3658.9.5 Branch-and-Bound-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
Kapitel 9 Betriebssysteme 367
9.1 Rätsel: Überquerung einer Hängebrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3689.2 Der Begriff Betriebssystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3689.3 Die Geschichte von Betriebssystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3689.4 Grundaufgaben von Betriebssystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3719.5 Aufbau und Dienste von Betriebssystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
9.5.1 Schichtenaufbau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3739.5.2 Prozesse, Threads, Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3749.5.3 Synchronisations-Mechanismen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3779.5.4 Zeitdienste (Timer) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3809.5.5 Speicherverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3829.5.6 Dateiverwaltung und Dateisysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3839.5.7 Geräteverwaltung und Treiber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3869.5.8 Benutzerschnittstelle (Kommandozeile bzw. GUI) . . . . . . . . . . . . . . . . 3889.5.9 Programmierschnittstelle (API) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
9.6 Besonderheiten bei Embedded Systemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Kapitel 10 Rechnernetze und das Internet 397
10.1 Synthetische Rätsel (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39810.2 Grundlagen der Vernetzung von Rechnern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39810.3 Das ISO/OSI-Modell und Internet-Protokolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39910.4 Internet-Protokolle in Rechnernetzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
10.4.1 Grundbegriffe zu TCP/IP-Netzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40110.4.2 TCP/IP-Protokolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
10.5 Hubs, Switches, Router und Gateways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40910.6 Grundlagen der Socket-Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40910.7 Verteilte Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40910.8 Das World Wide Web (WWW) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
10.8.1 Wichtige Komponenten und Konzepte des WWW . . . . . . . . . . . . . . . 41110.8.2 Kurze Einführung in HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41310.8.3 Cascading Style Sheets (CSS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42610.8.4 Eine kurze Einführung in XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42810.8.5 XHTML – das neue, XML-basierte HTML . . . . . . . . . . . . . . . . . . . . . . . . 43110.8.6 Web-Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
9
INHALTSVERZEICHNIS
Kapitel 11 Datenbanksysteme 439
11.1 Synthetische Rätsel (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44011.2 Grundlegendes zu Datenbanksystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
11.2.1 Aufgaben einer Datenbank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44011.2.2 Vorteile von Datenbanken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44111.2.3 Datenunabhängigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
11.3 Datenmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44311.3.1 Das Entity-Relationship-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44311.3.2 Das relationale Datenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44411.3.3 Die relationale Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
11.4 Die Datenbanksprache SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44711.4.1 Datendefinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44811.4.2 Einfügen, Ändern und Löschen von Datensätzen . . . . . . . . . . . . . . . . . 44911.4.3 Anfragen mit select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
Kapitel 12 Software Engineering 453
12.1 Synthetische Rätsel (3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45412.2 Die Software-Krise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45412.3 Eine geeignete Software-Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45612.4 UML-Diagramme für die Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
12.4.1 Statische Modellierung in UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45712.4.2 Dynamische Modellierung in UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
12.5 Modellierungsmöglichkeiten für die Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46112.6 Notwendigkeit von Prozessen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46112.7 Der wichtige Prozess „Requirement Engineering“ . . . . . . . . . . . . . . . . . . . . . . . . . 462
12.7.1 Das UML-Anwendungsfalldiagramm (Use Case Diagram) . . . . . . . . 46312.7.2 Das UML-Aktivitätsdiagramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46412.7.3 Genaue Klärung der Kundenanforderungen . . . . . . . . . . . . . . . . . . . . . . 466
12.8 Prozessmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46712.8.1 Schwer- und leichtgewichtige Prozessmodelle . . . . . . . . . . . . . . . . . . . 46712.8.2 Das Wasserfall-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46712.8.3 Das V-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46912.8.4 Inkrementelle und iterative Prozessmodelle . . . . . . . . . . . . . . . . . . . . . . 47012.8.5 Agiles Vorgehen mit eXtreme Programming (XP) . . . . . . . . . . . . . . . . . 472
12.9 Qualität eines Software-Produktes aus Kundensicht . . . . . . . . . . . . . . . . . . . . . . 474
Teil III Technische Informatik 477
Kapitel 13 Transistoren, Chips und logische Bausteine 479
13.1 Synthetische Rätsel (4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48013.2 Transistoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
13.2.1 Funktionsweise und Aufbau von Transistoren . . . . . . . . . . . . . . . . . . . 48013.2.2 Realisierung boolescher Funktionen mit Transistoren . . . . . . . . . . . . 482
10
Inhaltsverzeichnis
13.3 Chips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48313.3.1 Geschichtliche Entwicklung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48313.3.2 Herstellungsprozess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
13.4 Logische Bausteine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48513.4.1 Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48513.4.2 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48613.4.3 Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48713.4.4 Multiplexer (Selektor) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48713.4.5 Demultiplexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
Kapitel 14 Schaltnetze 493
14.1 Ein dialektisches Rätsel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49414.2 Normalformen von Schaltfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
14.2.1 Disjunktive Normalform (DNF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49414.2.2 Konjunktive Normalform (KNF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49514.2.3 Allgemeines Verfahren beim Erstellen einer Schaltung . . . . . . . . . . . 49614.2.4 Schaltkreisrealisierung durch PLAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
14.3 Entwurf von Schaltnetzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50014.4 Minimierung logischer Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
14.4.1 Karnaugh-Veitch-Diagramme (KV-Diagramme) . . . . . . . . . . . . . . . . . . . 50114.4.2 Don’t Care Argumente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50514.4.3 Quine-McCluskey-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
14.5 Addiernetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51414.5.1 Paralleladdierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51414.5.2 Paralleladdierer und -subtrahierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51614.5.3 Carry-Select-Addiernetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51714.5.4 Carry-Save-Addiernetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51914.5.5 Multiplizierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
14.6 Prinzipieller Aufbau einer ALU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
Kapitel 15 Schaltwerke 525
15.1 Rätsel: Waldlauf, Schnapsgläser und mehr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52615.2 Synchrone und asynchrone Schaltwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52715.3 Schaltungen mit Delays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
15.3.1 4-Bit-Ringzähler als synchrones Schaltwerk . . . . . . . . . . . . . . . . . . . . . . 52815.3.2 Delays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52915.3.3 Realisierung von Delays mit Flipflops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
15.4 Zähler und Frequenzteiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53915.4.1 Synchroner 4-Bit-Ringzähler mit JK-Flipflops . . . . . . . . . . . . . . . . . . . . 53915.4.2 Asynchroner 4-Bit-Ringzähler mit T-Flipflops . . . . . . . . . . . . . . . . . . . . 54115.4.3 Synchroner BCD-Zähler (Mod-10) mit T-Flipflops . . . . . . . . . . . . . . . . 54215.4.4 Asynchroner BCD-Zähler (Mod-10) mit JK-Flipflops . . . . . . . . . . . . . 542
15.5 Schieberegister . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54315.6 Entwurf synchroner Schaltwerke mittels Automaten . . . . . . . . . . . . . . . . . . . . . 545
15.6.1 Kurze Einführung in die Automatentheorie . . . . . . . . . . . . . . . . . . . . . . 54515.6.2 Entwurf von Schaltwerken mit Moore- und Mealy-Automaten . . . 548
11
INHALTSVERZEICHNIS
Kapitel 16 Realisierung eines einfachen Mikroprozessors 559
16.1 Rätsel: Hautfarbe, Fahrstuhl, Bienen und Ketten . . . . . . . . . . . . . . . . . . . . . . . . . . 56016.2 Komponenten und Phasen eines Prozessors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56016.3 Grunddaten zum Mikroprozessor MikroOne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56216.4 Die Datenregister des Mikroprozessors MikroOne . . . . . . . . . . . . . . . . . . . . . . . . 56216.5 Die ALU des Mikroprozessors MikroOne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56516.6 Die Spezialregister des Mikroprozessors MikroOne . . . . . . . . . . . . . . . . . . . . . . . 56516.7 Der Mikroprozessor MikroOne als Gesamtsystem . . . . . . . . . . . . . . . . . . . . . . . . . 56716.8 Die Maschinenbefehle von MikroOne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
16.8.1 Initialisierung von MikroOne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56816.8.2 Die Befehlsstruktur des MikroOne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56816.8.3 Der Befehlssatz von MikroOne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
16.9 Arten der Adressierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58416.10 Das Steuerwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
Kapitel 17 Prozessorarchitekturen, Speicher und Caches 591
17.1 Rätsel: Schachbrett-Quadrate, Flickenmuster, Kreuzformfirma . . . . . . . . . . . 59217.2 CISC und RISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59317.3 Pipelining (Fließbandverarbeitung) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
17.3.1 Unterschiedliche Phasen beim Pipelining . . . . . . . . . . . . . . . . . . . . . . . . 59517.3.2 Geschwindigkeitsgewinn beim Pipelining . . . . . . . . . . . . . . . . . . . . . . . 59717.3.3 Hazards beim Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
17.4 Speicher für Prozessoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60217.5 Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
17.5.1 Das Lokalitätsprinzip und der Cache-Controller . . . . . . . . . . . . . . . . . . 60617.5.2 Der Lesezugriff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60717.5.3 Vollassoziative und direktabgebildete Caches . . . . . . . . . . . . . . . . . . . . 60917.5.4 Der Schreibzugriff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
17.6 Virtueller Speicher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61417.6.1 Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61517.6.2 Segmentierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617
Teil IV Theoretische Informatik 619
Kapitel 18 Automatentheorie und formale Sprachen 621
18.1 Rätsel: Weg durch ein Labyrinth und um die Ecke gedacht . . . . . . . . . . . . . . . 62218.2 Lexikalische und syntaktische Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62218.3 Reguläre Sprachen und endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
18.3.1 Alphabet, Wort und Sprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62418.3.2 Reguläre Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62518.3.3 Endliche Automaten und reguläre Sprachen . . . . . . . . . . . . . . . . . . . . . 62718.3.4 Realisierung endlicher Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62918.3.5 lex – Ein Werkzeug für die lexikalische Analyse . . . . . . . . . . . . . . . . . 630
12
Inhaltsverzeichnis
18.4 Kontextfreie Sprachen und Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63418.4.1 Kontextfreie Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63418.4.2 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63718.4.3 yacc – Ein Werkzeug für die Syntaxanalyse . . . . . . . . . . . . . . . . . . . . . . 64018.4.4 lex und yacc im Zusammenspiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64418.4.5 Rekursion bei der Syntaxanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
18.5 Die unterschiedlichen Phasen eines Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
Kapitel 19 Berechenbarkeitstheorie 649
19.1 Rätsel: Kneipen, Ei, stehen gebliebene Uhr und Alter . . . . . . . . . . . . . . . . . . . . . 65019.2 Berechenbare Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65119.3 Nicht berechenbare Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652
19.3.1 Das Diagonalverfahren von Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65219.3.2 Nicht durch einen Algorithmus berechenbare Funktionen . . . . . . . 65319.3.3 Die Church’sche Algorithmus-Definition . . . . . . . . . . . . . . . . . . . . . . . . . 653
19.4 Berechenbarkeitskonzepte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65419.4.1 Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65419.4.2 Turing-berechenbare Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65719.4.3 Registermaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65719.4.4 GOTO- und WHILE-Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65819.4.5 LOOP-Programme (FOR-Programme) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66019.4.6 Primitive Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66119.4.7 µ-Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66319.4.8 Die Ackermann-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66519.4.9 Die Church’sche These und die Chomsky-Hierarchie . . . . . . . . . . . . 667
19.5 Prinzipiell unlösbare Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66819.5.1 Entscheidbare Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66819.5.2 Semi-entscheidbare Mengen (Game of Life und Halteproblem) . . 66919.5.3 Unberechenbarkeit (Fleißiger Biber) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
Kapitel 20 Komplexitätstheorie 677
20.1 Rätsel: Falsche Uhrzeit, Kalenderrechnen und mehr . . . . . . . . . . . . . . . . . . . . . . 67820.2 Die Klasse P für praktisch lösbare Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67820.3 Nichtdeterminismus und die Klasse NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
20.3.1 Das SAT-Problem als erstes NP-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 67920.3.2 Reduzierung auf ja/nein-Probleme mit zugehörigen Sprachen . . . 68020.3.3 Nichtdeterminismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68020.3.4 Die Klasse NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681
20.4 Der Satz von Cook und NP-Vollständigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68320.4.1 Das Dreifarbenproblem als Spezialfall des SAT-Problems . . . . . . . . 68320.4.2 NP-Vollständigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68420.4.3 P = NP? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68520.4.4 Das 3SAT-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68520.4.5 Das Cliquenproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68620.4.6 Das Rucksack- und Teilsummen-Problem . . . . . . . . . . . . . . . . . . . . . . . . 68820.4.7 Das Hamilton-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
13
INHALTSVERZEICHNIS
20.4.8 Das Problem des Handlungsreisenden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69320.4.9 Hierarchie der NP-vollständigen Probleme . . . . . . . . . . . . . . . . . . . . . . . 696
20.5 Approximationsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696
Teil V Codes, Kompression, Kryptografie 701
Kapitel 21 Fehlertolerante Codes 703
21.1 Rätsel: Auf der Demo mit Bruder und Schwester . . . . . . . . . . . . . . . . . . . . . . . . . 70421.2 Motivation für fehlertolerante Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70421.3 „k aus n“-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70421.4 Der Hammingabstand eines Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70521.5 Eindimensionale Parity-Prüfung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70721.6 Zweidimensionale Parity-Prüfung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70821.7 Hamming-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71321.8 CRC-Kodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
Kapitel 22 Datenkompression 719
22.1 Rätsel: Tierseuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72022.2 Verlustbehaftete und verlustlose Kompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72022.3 Codes mit variabel langen Codewörtern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72022.4 Fano-Bedingung für Dekodierbarkeit eines Codes . . . . . . . . . . . . . . . . . . . . . . . . . 72122.5 Lauflängenkodierung („run-length encoding“) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72222.6 Shannon-Fano-Kodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72322.7 Huffman-Kodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72322.8 Arithmetische Kodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72722.9 Lempel-Ziv-Kodierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
22.9.1 Der LZ77-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73222.9.2 Der LZSS-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73322.9.3 Der LZ78-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73422.9.4 Der LZW-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73522.9.5 Varianten der Lempel-Ziv-Kodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
Kapitel 23 Kryptografie 741
23.1 Rätsel: Weinflasche und Erben von Weinfässern . . . . . . . . . . . . . . . . . . . . . . . . . . 74223.2 Allgemeines zu Kryptosystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74223.3 Einfache Verschlüsselungsmethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
23.3.1 Cäsar-Chiffre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74223.3.2 Chiffre mit eigener Zuordnungstabelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 743
23.4 Vigenère-Verschlüsselungsmethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74323.5 Verschlüsselung mittels Zufallsfolgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74423.6 Kryptosysteme mit öffentlichen Schlüsseln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746
23.6.1 Eigenschaften von Public-Key-Systemen . . . . . . . . . . . . . . . . . . . . . . . . . 74623.6.2 Der Satz von Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
14
Inhaltsverzeichnis
23.6.3 Schlüsselerzeugung beim RSA-Algorithmus . . . . . . . . . . . . . . . . . . . . . 74723.6.4 Ver- und Entschlüsselung mit dem RSA-Algorithmus . . . . . . . . . . . . 750
23.7 Quantenkryptografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
Weiterführende Literatur 755
Sachregister 761
Demonstrationsprogramme und HTML-/XML-Dateien 773
Simulationsprogramme 777
15
Grundlagen der Informatik - Praktisch – Technisch – TheoretischInhaltsverzeichnisKapitel 1 EinleitungTeil I Einführung in die InformatikKapitel 2 Die Historie und die Teilgebiete der InformatikKapitel 3 Speicherung und Interpretation von InformationKapitel 4 Boolesche AlgebraKapitel 5 Hardware-Komponenten eines ComputersKapitel 6 Vom Programm zum Maschinenprogramm
Teil II Praktische InformatikKapitel 7 ProgrammiersprachenKapitel 8 Datenstrukturen und AlgorithmenKapitel 9 BetriebssystemeKapitel 10 Rechnernetze und das InternetKapitel 11 DatenbanksystemeKapitel 12 Software Engineering
Teil III Technische InformatikKapitel 13 Transistoren, Chips und logische BausteineKapitel 14 SchaltnetzeKapitel 15 SchaltwerkeKapitel 16 Realisierung eines einfachen MikroprozessorsKapitel 17 Prozessorarchitekturen, Speicher und Caches
Teil IV Theoretische InformatikKapitel 18 Automatentheorie und formale SprachenKapitel 19 BerechenbarkeitstheorieKapitel 20 Komplexitätstheorie
Teil V Codes, Kompression, KryptografieKapitel 21 Fehlertolerante CodesKapitel 22 DatenkompressionKapitel 23 Kryptografie
Weiterführende LiteraturSachregisterDemonstrationsprogramme und HTML-/XML-DateienSimulationsprogramme
Ins Internet: Weitere Infos zum Buch, Downloads, etc.