Auf einen Blick - Wiley-VCH12 Auf einen Blick Teil VII: Datenstrukturen und Algorithmen für die Ewigkeit..... 489 Kapitel 31: Algorithmen für den Hausgebrauch ..... 491 Kapitel 32:

Auf einen Blick

Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Teil I: Informatik zum Verlieben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Kapitel 1: Informatik im Schnelldurchlauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Kapitel 2: Was die Informatik im Inneren zusammenhält . . . . . . . . . . . . . . . . . . . . . . 49Kapitel 3: Im Dschungel von Bits und Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63Kapitel 4: Wie Informatiker denken. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Teil II: Schöne neue digitale Welt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Kapitel 5: Fingertechnik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Kapitel 6: Heilen mit boolescher Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119Kapitel 7: Schalten und Walten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137Kapitel 8: Fangen mit Schaltnetzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157Kapitel 9: Schaltwerke der Menschheitsgeschichte . . . . . . . . . . . . . . . . . . . . . . . . . . . 173Kapitel 10: Mikroprogramme im Land der Automaten . . . . . . . . . . . . . . . . . . . . . . . . . 197

Teil III: Besichtigung der Maschinenhalle . . . . . . . . . . . . . . . . . . . . . . . 205Kapitel 11: EVA und die Vertreibung aus dem Paradies . . . . . . . . . . . . . . . . . . . . . . . . . 207Kapitel 12: Alle Macht der Zentraleinheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217Kapitel 13: Speicher im ganzen Haus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233Kapitel 14: Mit dem Bus zum BIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245Kapitel 15: Cache me if you can . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

Teil IV: Sprachen für Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269Kapitel 16: Warum alles so kompliziert ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271Kapitel 17: Programmiersprachen und Werkzeuge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287Kapitel 18: Bestandteile einer Programmiersprache . . . . . . . . . . . . . . . . . . . . . . . . . . . 303Kapitel 19: Auf was Sie beim Programmieren achten sollten . . . . . . . . . . . . . . . . . . . . 321Kapitel 20: Programme entwickeln mit System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Teil V: C und andere Vitamine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343Kapitel 21: Wer A sagt, muss auch C sagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345Kapitel 22: C als Muttersprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363Kapitel 23: Fiese Tricks in ANSI C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383Kapitel 24: Abheben mit C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395Kapitel 25: Apps mit Objective-C und Swift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

Teil VI: Eruption aus Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435Kapitel 26: Heißer Kaffee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437Kapitel 27: Felder und mehr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449Kapitel 28: Klasse Klassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457Kapitel 29: Sammeln für Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471Kapitel 30: Apps mit Android . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481

12 Auf einen Blick

Teil VII: Datenstrukturen und Algorithmen für die Ewigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489Kapitel 31: Algorithmen für den Hausgebrauch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491Kapitel 32: Elementare Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505Kapitel 33: Tabellen für alle Einsatzzwecke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519Kapitel 34: Wald und Bäume überblicken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543Kapitel 35: Jede Menge Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555

Teil VIII: Computerarchitektur als Gesamtkunstwerk . . . . . . . . . 565Kapitel 36: Betriebssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567Kapitel 37: Architektur von Software. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581Kapitel 38: Datenbanksysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589

Teil IX: Künstliche Intelligenz gegen natürliche Dummheit 601Kapitel 39: Führung durch die Asservatenkammer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603Kapitel 40: Spielend suchen und finden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611Kapitel 41: Lärmende Systeme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629Kapitel 42: Expertensysteme für Profis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645Kapitel 43: Kunstvolle neuronale Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Teil X: Im Netz der Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681Kapitel 44: Ganz nach Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683Kapitel 45: Gestalten und Gestaltung im Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695Kapitel 46: Skriptsprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705Kapitel 47: Socket- und Threadprogrammierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719Kapitel 48: Durchblick und Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739

Teil XI: Die praktischen Seiten der theoretischen Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747Kapitel 49: Komprimierte Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749Kapitel 50: Formulare für formale Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775Kapitel 51: Logik und Korrektheit für Informatiker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799Kapitel 52: Theorie für Unberechenbare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803Kapitel 53: Mittel gegen theoretische Komplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815

Teil XII: Top Secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829Kapitel 54: Risiken und Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831Kapitel 55: Angriffsarten und Schutzmaßnahmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843Kapitel 56: Vierbeiniger Besuch aus Troja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859Kapitel 57: Alice und Bob im Wunderland der Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 873Kapitel 58: Wände gegen Feuer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891

Teil XIII: Der Top-Ten-Teil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903Kapitel 59: Zehn bedeutende Meilensteine der Informatik . . . . . . . . . . . . . . . . . . . . . . 905Kapitel 60: Die zehn schlimmsten Irrtümer der Informatik . . . . . . . . . . . . . . . . . . . . . . 909

Stichwortverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913

Inhaltsverzeichnis

Über den Autor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Zu diesem Buch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Konventionen in diesem Buch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Törichte Annahmen über den Leser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Wie dieses Buch aufgebaut ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Symbole in diesem Buch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Wie es weitergeht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

TEIL IINFORMATIK ZUM VERLIEBEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Kapitel 1Informatik im Schnelldurchlauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Mathematik der Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Pandoras Büchse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Evolution einer fantastischen Idee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Praktische Theorien in der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Gigantische Möglichkeiten der Technik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Denkende Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Kapitel 2Was die Informatik im Inneren zusammenhält . . . . . . . . . . . . . . 49

Einblicke und Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Säulen der Softwaretechnik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

Modularität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Wiederverwendbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Wechselseitige Impulse durch Hardware und Software . . . . . . . . . . . . . . . . . . . . 57Disziplinen der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Wirtschaftsinformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59Bioinformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59Medizininformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Computerlingusitik 60Medieninformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Geoinformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Umweltinformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Sozioinformatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

14 Inhaltsverzeichnis

Kapitel 3Im Dschungel von Bits und Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Hochgeschwindigkeitstechnik im Kleinstformat . . . . . . . . . . . . . . . . . . . . . . . . . . . 63Atemberaubende Speichermöglichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Die Welt in Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Von Maschinensprache zu Hochsprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68Übersetzen und Interpretieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Steuern und Regeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Kapitel 4Wie Informatiker denken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Logische Vorschriften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75Öffentlich, aber diskret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77Teilen und Herrschen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79Rekursiv statt zurück . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81Nerds am Werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84Zeitloses von nutzlosem Wissen unterscheiden . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

TEIL IISCHÖNE NEUE DIGITALE WELT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

Kapitel 5Fingertechnik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Alles wird digital . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Warum zwei Werte reichen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94Bitte ein Byte! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95Textwerte ermitteln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97Malen statt Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99Konvertierung von Dezimalzahlen in Binärzahlen . . . . . . . . . . . . . . . . . . . . . . . . . 100Hex hex! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102Rechnen im Dualsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104Subtraktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106Multiplikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Festpunkt und Fließkomma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Große und kleine Zahlenbereiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111IEEE-754 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112Fallstricke der Gleitkommaarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

Inhaltsverzeichnis 15

Kapitel 6Heilen mit boolescher Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Allheilmittel Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119Logische Verknüpfungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123Gesetze und Regeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Assoziativgesetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125Kommutativgesetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126Distributivgesetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126Neutralität und Komplement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126Idempotenz und Absorption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127Dualitätsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128De Morgan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

Stunde der Wahrheitstabellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130Digitale Vergatterung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132Basis und Komposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133Antivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133Implikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133NAND und NOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Stolpersteine der booleschen Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Kapitel 7Schalten und Walten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Entwurfsprobleme spielend lösen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137Funktionen in Wahrheitstafeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139Normale Formen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Disjunktive Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144Konjunktive Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Don’t Care? Ist mir doch egal! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146Minimierung von Termen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

KV-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146Der Quine-McCluskey-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Kapitel 8Fangen mit Schaltnetzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

Durchblick in Schaltungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157Lustige Symbole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161Decodiernetzwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162Multiplexer ohne Komplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163Komparator für Dualzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164Halb- und Volladdierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165Gatterlaufzeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168Klitschige Glitches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169


Kapitel 9Schaltwerke der Menschheitsgeschichte . . . . . . . . . . . . . . . . . . . . . 173

Schmerzfreie Rückkopplungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173Zustände wie bei den Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175Kritische Läufe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175Flanken ohne Tore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177Familie der Flipflops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

SR-Flipflop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178Data Latch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179D-Flipflop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180Taktflankengesteuertes Flipflop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181JK-Flipflop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

Zähler mit Flipflops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184Schiebung in den Registern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

Kapitel 10Mikroprogramme im Land der Automaten . . . . . . . . . . . . . . . . . . . 187

Synchrone Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187Mealy-Automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188Moore-Automat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

Entwurf von Schaltwerken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190Steuern für ein gutes Werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193Mikroprogramme als Meisterwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

TEIL IIIBESICHTIGUNG DER MASCHINENHALLE . . . . . . . . . . . . . . . . . . . . . . . 205

Kapitel 11EVA und die Vertreibung aus dem Paradies . . . . . . . . . . . . . . . . . . . 207

Digitale Kernspaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207Eingabe, Verarbeitung und Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208Rechnerarchitektur von Neumann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209Komponenten eines modernen Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212Spannung zwischen Zentrale und Peripherie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Kapitel 12Alle Macht der Zentraleinheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

Kein Prozess ohne Prozessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217Steuern für ein gutes Werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221Konstruktion aus ALU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223Registerspeicher mittendrin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224Die Fäden laufen zusammen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224Laden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227Programme mit System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228An den Start – es geht los! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230


Kapitel 13Speicher im ganzen Haus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

Komische Speichertypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233Ohne RAM läuft nichts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234Alle Wege führen zum ROM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

Speicher für die Massen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241Festplatten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241DVDs & Blu-rays & mehr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Kapitel 14Mit dem Bus zum BIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

Organisation von Ein- und Ausschaltvorgängen . . . . . . . . . . . . . . . . . . . . . . . . . . . 245Unterbrechungen mit Interrupts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

Interrupt Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248Interrupt-Service-Routine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

Fit trotz Ablaufinvarianz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249Schnittstellen ohne Verletzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250Eingabegeräte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

Tastatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251Maus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253Touchpad & Touchscreen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

Ausgabegeräte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255Display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255Drucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

Kapitel 15Cache me if you can . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

Risiken reduzieren mit RISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257Pipelines ohne Öl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259Parallele Welten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

Leckere Mehrkern-Brötchen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262Super, so ein Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263Entwirrung der Fäden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

Cache bringt Cash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265Architekturen der Zukunft – ein Blick in die Glaskugel . . . . . . . . . . . . . . . . . . . . . 266

TEIL IVSPRACHEN FÜR COMPUTER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Kapitel 16Warum alles so kompliziert ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

Fallstricke menschlicher Sprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271Maschinenlesbares Kauderwelsch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274Assemblercode zum Abgewöhnen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278Unterprogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281Gipfel erklimmen mit Hochsprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283


Kapitel 17Programmiersprachen und Werkzeuge . . . . . . . . . . . . . . . . . . . . . . . 287

Programmieren als Kunstform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287Interpreter ohne Spielraum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289Programme, die Programme schreiben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291Werkzeuge zum Übersetzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293Ein bunter Strauß von Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Imperative und deklarative Programmiersprachen . . . . . . . . . . . . . . . . . . . 297Funktionale Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299Objektorientierte Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

Kapitel 18Bestandteile einer Programmiersprache . . . . . . . . . . . . . . . . . . . . . 303

Backus-Naur-Kuchenform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303Bezeichner und Konstanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307Operatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308Gleich ist nicht gleich gleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310Atomare Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310Kontrollstrukturen, so weit das Auge reicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311Erlaubte Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312Ausnahmsweise eine Exception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314Angekettete Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316Ein Strom von Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316Argumente und Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

Kapitel 19Auf was Sie beim Programmieren achten sollten . . . . . . . . . . . . 321

Reusability Reusability Reusability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321Abstraktion als Universalwaffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

Barrieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324Kapselung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325Modularisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325Schnittstellen ohne Schmerzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

Wert eines Ausdrucks und Seiteneffekt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326Ende des Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327Gefährliche Zeiger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

Kapitel 20Programme entwickeln mit System . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Entwickeln in behaglicher Umgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333Bibliotheken ohne Bücher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335APIs effektiv nutzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338Lebenszyklus eines Programms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339


TEIL VC UND ANDERE VITAMINE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

Kapitel 21Wer A sagt, muss auch C sagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

Das kleine A-B-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345Programmaufbau in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

B-Zeichner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349Das sind Argumente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351Musterbeispiel verstehen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355Zeigerzauberwelt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Kapitel 22C als Muttersprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Atomare Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363Operationen mit Operatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366Ein weites Feld von Arrays und Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367Zeichen in Ketten legen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369Kontrollstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

if-else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376

Mit Dateien arbeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378Standardkanäle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

Kapitel 23Fiese Tricks in ANSI C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

Spiel mit den Pointern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383Warum kurz, wenn es noch kürzer geht? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386Zeiger und Felder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388C für flinke Finger. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389Dynamisch trotz static . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391Fehler auf dem Behandlungsstuhl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

Kapitel 24Abheben mit C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

Objekte und Klassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395Die Sache hat Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396Vererbungslehre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400Operatoren überladen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401Ein- und Ausgabe neu ordnen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402Strings zum Verlieben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403Streams und Stringstreams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408Ein Königreich für ein Template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408Öffnungszeiten der Standardbibliothek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410


Werfen und Fangen: Ausnahmebehandlung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411Virtuelle Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413Polymorphie und ihre Heilungschancen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

Kapitel 25Apps mit Objective-C und Swift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

Apps für Eier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419Kurzer Plausch über Smalltalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420Instanzen verstehen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422Synthetische Objekte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422... Faulheit siegt! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425Design Pattern für Apps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426

Model View Controller (MVC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427Delegation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427

Schnelle Aufzählung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429Swift ist besser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

TEIL VIERUPTION AUS JAVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

Kapitel 26Heißer Kaffee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437

Java für alle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437Virtuelle Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438Bezeichner und Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440Nicht einwickeln lassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441Kontrolle mit Struktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446

Kapitel 27Felder und mehr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449

Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449Initialisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449Zugriff auf Elemente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450Kopie und Vergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

Iteration und Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452Grafische Komponenten und Applets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453

Kapitel 28Klasse Klassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Objekte der Begierde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457Kapseln mit Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458Von Face zu Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462Abstrakte Basisklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465Casting von Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466Vergleichen und Kopieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468


Kapitel 29Sammeln für Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

Collections verwenden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471Mit Iteratoren klettern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476Exceptions sinnvoll behandeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477Zugesicherte Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

Kapitel 30Apps mit Android . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481

Entwickeln in der richtigen Umgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481XML und Android . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484UI, tolle Elemente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486

TEIL VIIDATENSTRUKTUREN UND ALGORITHMEN FÜR DIE EWIGKEIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489

Kapitel 31Algorithmen für den Hausgebrauch . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

Systematik von Programmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491Teile und herrsche! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492Zauberkraft durch Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493Türme von Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494Euklid & Co . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497Analyse von Algorithmen ohne Komplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498O-Ton der O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499

Kapitel 32Elementare Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505

Abstrakte Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505Listige Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508Stacks im Keller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509Schlängelnde Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510Doppelt gemoppelte Deques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512Klang der Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

Struktur von Zeichenketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515Aufspüren von Mustern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516

Kapitel 33Tabellen für alle Einsatzzwecke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519

Struktur von Tabellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519Sequenzielle Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522Binäre Suche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523Sortierverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527

Selectionsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528Bubblesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530Für die ganz Eiligen: Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532


Völlig legal: HashTables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539Hashing ohne Kollisionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540

Kapitel 34Wald und Bäume überblicken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

Äste an Wurzeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543Binärbäume für die Informatiker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546Ordnung in den Laden bringen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546

davor (pre) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547dazwischen (in) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548dahinter (post) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549

Früchte der Syntaxbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551Entscheidungsbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553

Kapitel 35Jede Menge Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555

Graphen vor Gericht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555Erforschung von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557Schmerzlose Adjazenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558Planierte Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559Langer Weg zum kürzesten Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561

Minimaler Spannbaum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562Algorithmus nach Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562

TEIL VIIICOMPUTERARCHITEKTUR ALS GESAMTKUNSTWERK . . . . . . . . . . 565

Kapitel 36Betriebssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567

Rechte und Pflichten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567Administratoren und DAUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569Prominente Vertreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570Ordnerstrukturen für Dateien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572Tasks den Prozess machen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575Nadel und Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577Virtuelle Echtzeitanforderungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

Kapitel 37Architektur von Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

Architekten für Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581Gebäude mit drei Stockwerken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583Anforderungsanalysen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584Lasten- und Pflichtenhefte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585Modellieren mit UML. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586Vorgehensmodell zur Software-Entwicklung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587


Kapitel 38Datenbanksysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589

Bank für Daten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589Relationale Datenbanksysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590SQL im Crashkurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595

create . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598NoSQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598

Offene Quellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599

TEIL IXKÜNSTLICHE INTELLIGENZ GEGEN NATÜRLICHE DUMMHEIT 601

Kapitel 39Führung durch die Asservatenkammer . . . . . . . . . . . . . . . . . . . . . . . 603

Cyborgs auf der Spur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603Wissen ohne Gewissen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606Planen und Entscheiden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607Musteranalyse und -erkennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607Intelligente Agenten oder Suche oder was? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607Künstliche Wesen mit eigenem Bewusstsein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608

Kapitel 40Spielend suchen und finden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611

Aufspüren mit GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611Bergsteiger-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614Heuristische Suche im Heu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617Navigieren zu den Sternen mit dem A*-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 619Spaß mit MINIMAX und Moritz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621Beschneidungen von Alpha bis Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624

Kapitel 41Lärmende Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629

Maschinelles Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629Inferenz ohne Sperenzien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631Landung auf der Wissensbasis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632Induktive und deduktive Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632Rauschen im Datenwald . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633Lernen mit Konzept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634Entscheiden lernen mit Bäumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638Lernen ohne Lehrer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644


Kapitel 42Expertensysteme für Profis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645

Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645Expertenwissen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649Diagnosen vom Elektronenhirn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651Fallbasiertes Schließen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652Vorhersagen treffen und reich werden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658

Kapitel 43Kunstvolle neuronale Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Kopieren geht über Studieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659Vorwärts zu den verketteten Netzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662Rosenblatts Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664

Regeln zum Lernen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664Das XOR-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

Fortschritt durch Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668Quetsch mich! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670Herleitung der Fehlerfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672Gewichtsanpassung eines Neurons im Output-Layer . . . . . . . . . . . . . . . . . 673Gewichtsanpassung eines inneren Neurons . . . . . . . . . . . . . . . . . . . . . . . . . 673Diverse Varianten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675

Die Macht der Rückkopplungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676Attraktive Attraktorennetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678Grenzenlose Anwendungsfelder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680

Natürliche Sprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680Wahrnehmung der Umgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680

TEIL XIM NETZ DER NETZE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681

Kapitel 44Ganz nach Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683

Militärische Ideen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683Tanz um die Redundanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684

Das Internet-Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685Schichten und Geschichten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685

Handschlag für TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688Hubs, Switches und Router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690Übersicht der wichtigsten Dienste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691

Kapitel 45Gestalten und Gestaltung im Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695

Webtechnologie für Insider . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695HTTP in Kurzform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696HTML in Kurzform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698

HTML bis XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699Unbegrenzte Möglichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700


Kapitel 46Skriptsprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705

Geschälte Shell-Skripte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705Kein bisschen umständlich: awk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 709Perlentauchen mit perl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711Siegeszug von PHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714JavaScript. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716

Kapitel 47Socket- und Threadprogrammierung . . . . . . . . . . . . . . . . . . . . . . . . . . 719

Spaß mit Client und Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719Socken für die Sockets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 720Prozesse und Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725

Das Erzeuger-Konsumenten-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727Schutz durch Mutexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728POSIX-Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728Eine eigene Bank bauen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729

Kapitel 48Durchblick und Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739

Vom Web getrieben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739Ad hoc statt lang geplant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742Big Data für Big Brother . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743Im Nebel der Cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744Weltweite Aussichten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745

TEIL XIDIE PRAKTISCHEN SEITEN DER THEORETISCHEN INFORMATIK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747

Kapitel 49Komprimierte Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749

Dreiklang der Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749Transportieren und speichern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752Sinnfreies Messen von Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753Gehalt für Entscheidungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 758Entropie als Theorie der Unordnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760Kompressen ohne Mull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763Optimale Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764

Shannon-Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770


Kapitel 50Formulare für formale Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775

Alphabet und Grammatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775Endliche Automaten und Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778Reguläre Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779Immer den Kontext beachten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 781Pumpen für den Beweis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782Freiheit für den Kontext . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784

Kapitel 51Logik und Korrektheit für Informatiker . . . . . . . . . . . . . . . . . . . . . . . 789

Logische Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789Prädikat wertvoll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792Armer Gödel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794Korrektheit von Programmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796Formale Verifikation ohne Schmerzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 798

Kapitel 52Theorie für Unberechenbare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803

Algorithmen entschlüsseln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803Anwerfen der Turing-Maschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805Berechenbare Turing-Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809Halteproblem ohne Züge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811

Kapitel 53Mittel gegen theoretische Komplexe . . . . . . . . . . . . . . . . . . . . . . . . . . 815

P wie praktische Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815SAT-Probleme bei bestem Empfang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818Ganz bestimmt nicht-deterministisch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819Ein schwerer Rucksack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 821Händler auf der Reise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 821Cooks Geniestreich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822NP-Vollständigkeit und der Gral der Weisheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823

Was wäre, wenn? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827

TEIL XIITOP SECRET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829

Kapitel 54Risiken und Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831

Grundfeste der Informationssicherheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831CIA-Triade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832Ganz sichere Fakten über Risiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833Risikolebenszyklus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835Wichtige Rollen und Dokumente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 839Information Security Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841Internationale Sicherheitszertifizierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 842


Kapitel 55Angriffsarten und Schutzmaßnahmen . . . . . . . . . . . . . . . . . . . . . . . . 843

Offene und verborgene Bedrohungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843Einbrecher ohne Handschuhe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844Soziales Hacken und Phishing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844Der Mann in der Mitte und andere Angriffsmöglichkeiten . . . . . . . . . . . . . . . . . . 847

Password Guessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847Password Cracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847Passwort-Sniffing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848Man-In-The-Middle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849

Technische Problemzonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849Designfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849Pufferüberlauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 851Exploit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 852Überflutung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 852

Protokollschwächen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854Schnüffeln und Verschleiern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854IP-Angriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854TCP-Angriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855

Protokolle mit »S« . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855Per Tunnel in die Sicherheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 857WLAN ohne böse Überraschung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 857

Kapitel 56Vierbeiniger Besuch aus Troja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859

Kleinstlebewesen in der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859Funktionsprinzip der Viren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860Infektionsarten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861Gemeine Viren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861Rasende Würmer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862Pferde, die keine sind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862Spam, Spam, Spam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866Antiviren als Antikörper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868EICAR-Test positiv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870Logische Bomben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870

Kapitel 57Alice und Bob im Wunderland der Zahlen . . . . . . . . . . . . . . . . . . . . . 873

Dieser Abschnitt ist geheim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873Wfstdimvfttfmvohtwfsgbisfo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874

Caesar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 875

Symmetrische Klassiker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 878DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8793DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 881AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 882

One Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 882


Paradox: Sichere Kommunikation über unsicheren Kanal . . . . . . . . . . . . . . . . . . 884Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 886

Aufbau von Kryptosystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888Ring of Trust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 890

Kapitel 58Wände gegen Feuer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891

Moderne Sicherheitsinfrastrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891Filteranlage für Pakete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893Besuch beim Statusinspektor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895Stellvertreter-Systeme für und gegen alles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897Eindringlinge geschickt identifizieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899

TEIL XIIIDER TOP-TEN-TEIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903

Kapitel 59Zehn bedeutende Meilensteine der Informatik . . . . . . . . . . . . . . 905

Eine sehr, sehr alte Rechenmaschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905Die digitale (Zeit-)Rechnung beginnt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906Der wirklich erste Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906Was wirklich berechenbar ist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907Spielend voranschreiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907Personal Computer erobern die Welt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907Fenster und Mäuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907Im Netz der Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908Die mobile Revolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908Jetzt sind Sie am Zug! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908

Kapitel 60Die zehn schlimmsten Irrtümer der Informatik . . . . . . . . . . . . . . 909

1943, Thomas John Watson, Vorstand IBM . . . . . . . . . . . . . . . . . . . . . . . . . . 9091949, John von Neumann, Informatikpionier. . . . . . . . . . . . . . . . . . . . . . . . . 9091962, Dennis Gabor, Nobelpreisträger für Physik . . . . . . . . . . . . . . . . . . . . . 9101977, Ken Olson, Gründer DEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9101979, Ian Sharp, Gründer Sharp Associates . . . . . . . . . . . . . . . . . . . . . . . . . . 9101982, Jan Timmer, Vorstand Philips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9101985, Steve Jobs, Gründer Apple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9101989, Bill Gates, Gründer Microsoft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9101992, Ron Sommer, Vorstand Telekom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9101995, Robert Metcalfe, Gründer 3com, Erfinder Ethernet . . . . . . . . . . . . . . 911

Ende . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911

Stichwortverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913

Documents

Auf einen Blick - Wiley-VCH12 Auf einen Blick Teil VII: Datenstrukturen und Algorithmen für die Ewigkeit..... 489 Kapitel 31: Algorithmen für den Hausgebrauch ..... 491 Kapitel 32: