Grundkurs Informatik

Hartmut Ernst Jochen Schmidt

•

Gerd Beneken

Grundkurs Informatik
Grundlagen und Konzepte für die
erfolgreiche IT-Praxis – Eine umfassende,
praxisorientierte Einführung
6. Auflage 2016
Hartmut Ernst Jochen Schmidt
Hochschule Rosenheim Hochschule Rosenheim
Rosenheim, Deutschland Rosenheim, Deutschland

Gerd Beneken
Hochschule Rosenheim
Rosenheim, Deutschland

ISBN 978-3-658-14633-7 ISBN 978-3-658-14634-4 (eBook)

DOI 10.1007/978-3-658-14634-4

Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie;

detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.

Springer Vieweg
© Springer Fachmedien Wiesbaden 1999, 2000, 2003, 2008, 2015, 2016
Die 1. Auflage 1999 und die 2. Auflage 2000 erschienen unter dem Titel „Grundlagen und Konzepte der
Informatik“
Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung, die nicht
ausdrücklich vom Urheberrechtsgesetz zugelassen ist, bedarf der vorherigen Zustimmung des Verlags.
Das gilt insbesondere für Vervielfältigungen, Bearbeitungen, Übersetzungen, Mikroverfilmungen und die
Einspeicherung und Verarbeitung in elektronischen Systemen.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt
auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und
Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften.
Der Verlag, die Autoren und die Herausgeber gehen davon aus, dass die Angaben und Informationen in diesem
Werk zum Zeitpunkt der Veröffentlichung vollständig und korrekt sind. Weder der Verlag noch die Autoren
oder die Herausgeber übernehmen, ausdrücklich oder implizit, Gewähr für den Inhalt des Werkes, etwaige
Fehler oder Äußerungen.

Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier

Springer Vieweg ist Teil von Springer Nature

Die eingetragene Gesellschaft ist Springer Fachmedien Wiesbaden GmbH
Vorwort
Wer sich heute als Student oder als Praktiker im Beruf ernsthaft mit Informatik beschäftigt, dem ist
die Frage nach der Standortbestimmung seines Fachgebiets vertraut: Was ist eigentlich Informatik?
Es gibt wenige Arbeitsfelder, die so interdisziplinär angelegt sind wie gerade die Informatik. Wer
beispielsweise die Darstellung des Stoffes in Lehrbüchern über Wirtschaftsinformatik betrachtet,
wird ganz erhebliche Unterschiede im Vergleich mit diesem Buch bemerken. Ebenso wird der
Datenbank-Profi oder der mehr an der Hardware orientierte Entwickler manches Detail vermissen.
Dennoch, die grundlegenden Konzepte, auf die es wirklich ankommt, sind für die verschiedenen
Richtungen dieselben.
Es wurde daher mit diesem Buch der Versuch unternommen, einen möglichst umfassenden
Überblick und Einblick in die wesentlichen Grundlagen und Konzepte der Informatik zu vermitteln.
Dabei geht es nicht nur um die Darstellung von Sachverhalten, sondern auch darum, Zusammenhänge
verständlich zu machen und zu vertiefen. Ferner sollte der Zugang zu weiterführenden Büchern und
Originalliteratur erleichtert werden. Ziel war nicht ein weiteres Programmierlehrbuch zu schreiben,
sondern eine umfassende Einführung in die Informatik.
Als roter Faden wird die Betonung des algorithmischen An-
    satzes verfolgt, denn gerade Algorithmen und deren effiziente
Implementierung in Software und Hardware bilden ein zen-
   trales Thema der Informatik. Die Stoffauswahl ist außerdem
an Themen orientiert, die über längere Zeit relevant bleiben
dürften. Dieses Lehrbuch versteht sich als praxisnah und an-
wendungsbezogen, wenn auch nicht in einem an Produkten
  
 und kommerziellen Softwaresystemen orientierten Sinne der
angewandten Informatik. Vielmehr wurden die Autoren von
der Überzeugung geleitet, dass Innovationen in der Praxis nur
der leisten kann, der kreativ auf der Basis von „first principles“


    zu denken gelernt hat. Der Stellenwert der Theorie auch für
 
 
den Praktiker wird damit betont. Auf der anderen Seite erfor-
dert die hier angestrebte Orientierung an der Praxis nicht, dass
jeder Satz im mathematischen Sinne streng bewiesen werden müsste. Es ist ja gerade der überbetonte
Formalismus mancher Theorie, der auf den Praktiker abschreckend wirkt. Für den Theorie-Nutzer
genügt es oft, die Formulierung eines Satzes zu verstehen, seinen Anwendungsbereich und seine
Grenzen zu begreifen sowie Einsicht in seine Gültigkeit zu gewinnen. Dazu ist aus didaktischer
Sicht an Stelle eines trockenen Beweises ein erhellendes Beispiel oft dienlicher.
Man kann die Informatik in manchen Aspekten mit einem voll im Leben stehenden Baum
vergleichen. Weithin sichtbar ist vor allem seine Krone mit grünen Blättern und bunten Früchten,
entsprechend den vielfältigen kommerziellen Anwendungen der Informatik. Und das ist es auch,
was der praxisorientierte Informatikanwender von dem breiten Spektrum, das unter dem Begriff
„Informatik“ subsumiert wird, aus der Distanz in erster Linie wahrnimmt: Computer-Aided Anything,
die anwendungsbetonte Informatik, die Lösungen für konkrete Probleme verkauft. Dort arbeitet die
Mehrzahl der Informatiker, dort wird gutes Geld verdient.
vi Vorwort

Doch so wie die Krone eines Baumes im Wechsel der Jahreszeiten ihr Aussehen ändert, so
ist auch dieser Teil der Informatik von kurzen Produktzyklen und in stetem Wandel begriffenen
Systemumgebungen geprägt. Hier trägt die Informatik zwar ihre Früchte, doch sind diese oft leicht
verderbliche Ware mit einem kurzfristigen Verfallsdatum. Für ein tiefer gehendes Informatikver-
ständnis genügt eine hauptsächlich an Produkten orientierte Sichtweise daher definitiv nicht. Ohne
profundes Hintergrundwissen ist es unmöglich, nachhaltige Entwicklungen von Sackgassen und
Modeströmungen zu unterscheiden. Es mag ja sehr verlockend sein, Bill Gates nachzueifern und
gleich in der obersten Etage der Informatikbranche einzusteigen. Doch an dieser Stelle muss man
sich klar machen, dass es der Stamm ist, der die Krone trägt. In diesem Sinne ruht auch die an-
wendungsorientierte Informatik auf einem stabilen Unterbau, der Kerninformatik. Diese unterliegt
einem vergleichsweise langsamen Wandel und sie gründet ihrerseits in tiefen Wurzeln auf einem
zeitlosen mathematisch-naturwissenschaftlichen Fundament.
Um den Stamm des Informatikbaumes, die Kerninformatik, geht es in diesem Buch. Wer sich
auf diesem Terrain sicher zu bewegen weiß, der wird keine Schwierigkeiten haben, auf einem
tragfähigen Grundlagenwissen professionell die höchsten Äste der Baumkrone zu erklimmen – oder
auch tiefer zu schürfen, um die wissenschaftliche Basis zu ergründen.
Zur Erleichterung des Einstiegs in die Lektüre werden im Folgenden die Themen der einzelnen
Kapitel kurz charakterisiert.
In Kapitel 1 wird nach einer geschichtlichen Einführung und einem kurzen Überblick über den
prinzipiellen Aufbau von Rechnern die binäre Arithmetik behandelt.
Kapitel 2 beschäftigt sich ausführlich mit den begrifflichen und mathematischen Konzepten der
fundamentalen Begriffe Nachricht und Information. Jeder, der sich ernsthaft mit der Informatik
befasst, sollte mit diesen Grundlagen gut vertraut sein, da so das Verständnis der folgenden Kapitel
erleichtert wird. Da Information und Wahrscheinlichkeit in enger Beziehung zueinander stehen,
werden auch die erforderlichen mathematischen Methoden erläutert. Im letzten Abschnitt dieses
Kapitels geht es dann um einen zentralen Begriff der Informatik, die Entropie.
In Kapitel 3 werden aufbauend auf Kap. 2 zunächst die grundlegenden Begriffe Redundanz,
Codeerzeugung und Codesicherung erläutert. Dazu gehört auch eine detaillierte Erläuterung der
wichtigsten einschlägigen Algorithmen. Anschließend wird auf den in der Praxis besonders wichti-
gen Aspekt der Codierungstheorie eingegangen, nämlich auf Methoden zur Datenkompression.
Kapitel 4 behandelt die Verschlüsselung von Daten. Es wird sowohl auf klassische Verfahren
eingegangen als auch auf moderne Methoden zur symmetrischen und asymmetrischen Verschlüsse-
lung. Zusammen mit den Kapiteln 2 und 3 umfasst und vertieft der Stoff den Inhalt entsprechender
Grundvorlesungen.
Kapitel 5 gibt einen Überblick über die Grundlagen der Computerhardware. Nach einer knappen
Einführung in die Aussagenlogik und die boolesche Algebra wird auf Schaltnetze und Schaltwerke
eingegangen. Am Schluss des Kapitels steht ein Abschnitt über Maschinensprache und Assembler.
In Kapitel 6 geht es dann um Rechnerarchitekturen. Nach Einführung der üblichen Klassifikati-
onsschemata folgt eine Erläuterung der für die Mehrzahl der Rechner noch immer maßgeblichen
von-Neumann-Architektur sowie eine Einführung in die Konzepte der Parallelverarbeitung.
Kapitel 7 beschreibt den Aufbau von Rechnernetzen. Zentral ist hier das OSI-Schichtenmodell.
Die im Internet verwendeten Übertragungsprotokolle werden erläutert.
Kapitel 8 beschreibt Architekturen und die wichtigsten Aufgaben von Betriebssystemen. Am
Ende wird auch auf die immer wichtiger werdende Virtualisierung eingegangen.
Kapitel 9 bietet einen Überblick über Datenbankkonzepte, mit dem Fokus auf relationalen
Datenbanken, der Datenbankabfragesprache SQL sowie XML. Auch Data Warehousing und Data
Vorwort vii

Mining werden gestreift.

Kapitel 10 beschäftigt sich mit der Automatentheorie und der Theorie der formalen Sprachen,
die in der theoretischen Informatik als Grundlage von Programmiersprachen und Compilern einen
wichtigen Platz einnehmen. Auch das Konzept der Turing-Maschine, die als algebraische Beschrei-
bung eines Computers aufgefasst werden kann, wird ausführlich erklärt. Dabei wird mehr Wert auf
eine verständliche Darstellung der grundlegenden Konzepte gelegt, als auf mathematische Strenge.
Am Ende des Kapitels wird ohne Vertiefung des Themas kurz auf Compiler eingegangen.
Kapitel 11 baut unmittelbar auf Kap. 10 auf. Zunächst werden die Begriffe Berechenbarkeit und
Komplexität erläutert und die Grenzen des mit Computern überhaupt Machbaren aufgezeigt. Es
schließen sich Abschnitte über probabilistische Algorithmen und Rekursion an. Die Kapitel 10 und
11 entsprechen zusammen einem Grundkurs in theoretischer Informatik.
In Kapitel 12 geht es im Detail um die in kommerzieller Software am häufigsten verwendeten
Operationen, nämlich Suchen (einschließlich Hashing) und Sortieren.
Kapitel 13 ist den wichtigen Datenstrukturen Binärbäume, Vielwegbäume und Graphen gewidmet.
Die Kapitel 12, 13 und 14.4 decken den Stoff einschlägiger Vorlesungen über Algorithmen und
Datenstrukturen ab.
Kapitel 14 beginnt mit einer Diskussion der prinzipiellen Struktur höherer Programmiersprachen
einschließlich Backus-Naur-Form und Syntaxgraphen. Es folgt ein Überblick über die weit verbrei-
tete Programmiersprache C, der aber keinesfalls speziell diesem Thema gewidmete Lehrbücher
ersetzen kann. Die Beschreibung der C-Funktionsbibliothek beschränkt sich auf einige Beispie-
le. Der letzte Abschnitt befasst sich intensiv mit den Datenstrukturen lineare Listen, Stapel und
Warteschlangen.
Kapitel 15 bietet eine Einführung in das objektorientierte Paradigma. Exemplarisch wird auf die
Sprache Java eingegangen.
Kapitel 16 befasst sich mit der Anwendungsprogrammierung im Internet. Neben der Beschrei-
bung grundlegender Technologien liegt der Schwerpunkt auf der Entwicklung von Webanwendungen
mit JavaScript.
Kapitel 17 gibt einen Überblick über Software-Engineering. Nach einer Beschreibung des Soft-
ware-Lebenszyklus werden zwei in der Praxis häufig anzutreffende Vorgehensmodelle erläutert,
nämlich das V-Modell und Scrum. Hilfsmittel für den Algorithmenentwurf werden vorgestellt.
Nachdem die fünfte Auflage komplett überarbeitet und erweitert wurde, enthält die jetzt vorlie-
gende sechste Auflage in erster Linie Korrekturen und Klarstellungen. Herzlichen Dank an unsere
aufmerksamen Leser für die Hinweise.
Ein Buch schreibt man nicht alleine; etliche Freunde und Kollegen haben uns dabei mit wertvollen
Anregungen geholfen. Insbesondere bedanken wir uns bei den Kollegen Ludwig Frank, Helmut
Oechslein und Theodor Tempelmeier, deren Hinweise und Sachverstand zur Qualität des Buches
wesentlich beigetragen haben; außerdem bei Herrn Alexander Scholz für die tatkräftige Unterstüt-
zung bei der Neuerstellung der Zeichnungen. Besonderer Dank gilt unseren Frauen und unseren
Familien für die ausgezeichnete Unterstützung während des Buch-Projektes.

Rosenheim, Hartmut Ernst

18. Juni 2016 Jochen Schmidt
Gerd Beneken
Hinweise zu den Übungsaufgaben
An die meisten Kapitel schließen sich Übungsaufgaben an. Die Lösungen sind auf der das Buch
ergänzenden Internetseite http://www.gki-buch.de zu finden. Die Übungsaufgaben sind
thematisch sowie nach ihrem Schwierigkeitsgrad klassifiziert:

T für Textaufgaben,

M für mathematisch orientierte Aufgaben,

L für Aufgaben, die logisches und kombinatorisches Denken erfordern,

P für Programmieraufgaben.

0 bedeutet „sehr leicht“. Diese Aufgaben können unmittelbar gelöst werden, ggf. mit etwas
Blättern im Buch.

1 bedeutet „leicht“ und kennzeichnet Aufgaben, die innerhalb von einigen Minuten mit wenig
Aufwand zu lösen sind.

2 bedeutet „mittel“. Solche Aufgaben erfordern etwas geistige Transferleistung über den Bu-
chinhalt hinaus und/oder einen größeren Arbeitsaufwand.

3 bedeutet „schwer“ und ist für Aufgaben reserviert, die erheblichen Arbeitsaufwand mit
kreativen Eigenleistungen erfordern.

4 kennzeichnet „sehr schwere“ Aufgaben und aufwendige Projekte.

Inhaltsverzeichnis
1 Einführung 1
1.1 Was ist eigentlich Informatik? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Zur Geschichte der Informatik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Frühe Zähl- und Rechensysteme . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Die Entwicklung von Rechenmaschinen . . . . . . . . . . . . . . . . . . . 4
1.2.3 Die Computer-Generationen . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Prinzipieller Aufbau von Computern . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.1 Analog- und Digitalrechner . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Das EVA-Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 Zentraleinheit und Busstruktur . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Systemkomponenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Zahlensysteme und binäre Arithmetik . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.1 Darstellung von Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Umwandlung von Zahlen in verschiedene Darstellungssysteme . . . . . . . 18
1.4.3 Binäre Arithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.4 Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2 Nachricht und Information 37

2.1 Abgrenzung der Begriffe Nachricht und Information . . . . . . . . . . . . . . . . 37
2.2 Biologische Aspekte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Sinnesorgane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Datenverarbeitung im Gehirn . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.3 Der genetische Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 Diskretisierung von Nachrichten . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.1 Abtastung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.2 Quantisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4 Wahrscheinlichkeit und Kombinatorik . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4.1 Die relative Häufigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4.2 Die mathematische Wahrscheinlichkeit . . . . . . . . . . . . . . . . . . . 47
2.4.3 Totale Wahrscheinlichkeit und Bayes-Formel . . . . . . . . . . . . . . . . 49
2.4.4 Statistische Kenngrößen . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.4.5 Fakultät und Binomialkoeffizienten . . . . . . . . . . . . . . . . . . . . . 55
2.4.6 Kombinatorik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5 Information und Wahrscheinlichkeit . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5.1 Der Informationsgehalt einer Nachricht . . . . . . . . . . . . . . . . . . . 60
2.5.2 Die Entropie einer Nachricht . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.5.3 Zusammenhang mit der physikalischen Entropie . . . . . . . . . . . . . . 64
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
x Inhaltsverzeichnis

3 Codierung 69
3.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.1 Definition des Begriffs Codierung . . . . . . . . . . . . . . . . . . . . . . 69
3.1.2 Mittlere Wortlänge und Code-Redundanz . . . . . . . . . . . . . . . . . . 70
3.1.3 Beispiele für Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2 Code-Erzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2.1 Codebäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2.2 Der Huffman-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2.3 Der Fano-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.3 Codesicherung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.3.1 Stellendistanz und Hamming-Distanz . . . . . . . . . . . . . . . . . . . . 82
3.3.2 m-aus-n-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.3 Codes mit Paritätsbits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.4 Fehlertolerante Gray-Codes . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3.5 Definition linearer Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.3.6 Lineare Hamming-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.3.7 Zyklische Codes und Code-Polynome . . . . . . . . . . . . . . . . . . . . 98
3.3.8 CRC-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.3.9 Sicherung nicht-binärer Codes . . . . . . . . . . . . . . . . . . . . . . . . 103
3.3.10 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3.4 Datenkompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.4.1 Vorbemerkungen und statistische Datenkompression . . . . . . . . . . . . 115
3.4.2 Arithmetische Codierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.4.3 Lauflängen-Codierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
3.4.4 Differenz-Codierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.4.5 Der LZW-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.4.6 Datenreduktion durch unitäre Transformationen (JPEG) . . . . . . . . . . 128
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4 Verschlüsselung 137
4.1 Klassische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.1.1 Substitutions-Chiffren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.1.2 Transpositions-Chiffren und Enigma . . . . . . . . . . . . . . . . . . . . . 143
4.2 Moderne symmetrische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.2.1 Der Data Encryption Standard (DES) . . . . . . . . . . . . . . . . . . . . 150
4.2.2 Der Advanced Encryption Standard (AES) . . . . . . . . . . . . . . . . . 151
4.2.3 One-Time-Pads und Stromchiffren . . . . . . . . . . . . . . . . . . . . . . 154
4.3 Moderne asymmetrische Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.3.1 Diffie-Hellman Schlüsselaustausch . . . . . . . . . . . . . . . . . . . . . 156
4.3.2 Der RSA-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.3.3 Digitale Unterschrift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

5 Computerhardware und Maschinensprache 169

5.1 Digitale Grundschaltungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.1.1 Stromkreise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Inhaltsverzeichnis xi

5.1.2 Dioden, Transistoren und integrierte Schaltkreise . . . . . . . . . . . . . . 171

5.1.3 Logische Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.2 Boolesche Algebra und Schaltfunktionen . . . . . . . . . . . . . . . . . . . . . . 177
5.2.1 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.2.2 Der boolesche Verband . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.2.3 Das boolesche Normalform-Theorem . . . . . . . . . . . . . . . . . . . . 181
5.2.4 Vereinfachen boolescher Ausdrücke . . . . . . . . . . . . . . . . . . . . . 182
5.3 Schaltnetze und Schaltwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.3.1 Schaltnetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.3.2 Spezielle Schaltnetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.3.3 Schaltwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.4 Die Funktion einer CPU am Beispiel des M68000 . . . . . . . . . . . . . . . . . . 194
5.4.1 Die Anschlüsse der CPU M68000 . . . . . . . . . . . . . . . . . . . . . . 194
5.4.2 Der innere Aufbau der CPU M68000 . . . . . . . . . . . . . . . . . . . . 199
5.4.3 Befehlsformate und Befehlsausführung . . . . . . . . . . . . . . . . . . . 204
5.4.4 Adressierungsarten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
5.5 Maschinensprache und Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . 213
5.5.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
5.5.2 Der Befehlssatz des M68000 . . . . . . . . . . . . . . . . . . . . . . . . . 214
5.5.3 Programmbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

6 Rechnerarchitektur 227
6.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
6.2 Die von-Neumann-Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
6.2.1 Komponenten eines von-Neumann-Rechners . . . . . . . . . . . . . . . . 230
6.2.2 Operationsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
6.3 Befehlssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
6.3.1 Mikroprogramme und CISC . . . . . . . . . . . . . . . . . . . . . . . . . 234
6.3.2 Reduced Instruction Set Computer: RISC . . . . . . . . . . . . . . . . . . 235
6.3.3 Abwärtskompatibilität . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.4 Klassifikation nach Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
6.5 Parallelität innerhalb einer Befehlssequenz . . . . . . . . . . . . . . . . . . . . . . 238
6.5.1 Fließbandverarbeitung – Optimierte Befehlsausführung . . . . . . . . . . . 238
6.5.2 Superskalare Mikroprozessoren . . . . . . . . . . . . . . . . . . . . . . . 239
6.5.3 VLIW – Very Long Instruction Word . . . . . . . . . . . . . . . . . . . . 240
6.6 Parallelität in Daten nutzen: Vektorprozessoren und Vektorrechner . . . . . . . . . 240
6.7 Parallele Ausführung mehrerer Befehlssequenzen . . . . . . . . . . . . . . . . . . 241
6.7.1 Simultanes Multi-Threading innerhalb einer CPU . . . . . . . . . . . . . . 243
6.7.2 Multi-Core-CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
6.7.3 Multiprozessor-Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
6.7.4 Multicomputer-Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
6.8 Speicherhierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
6.8.1 Speichertechnologien: Register, Cache und Hauptspeicher . . . . . . . . . 245
6.8.2 Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
6.8.3 Memory Management Unit und virtueller Speicher . . . . . . . . . . . . . 249
xii Inhaltsverzeichnis

6.8.4 Festplatten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

6.8.5 Flash-Speicher und Solid State Disks . . . . . . . . . . . . . . . . . . . . 250
6.9 Ein- und Ausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
6.9.1 Unterbrechungen (Interrupts) . . . . . . . . . . . . . . . . . . . . . . . . . 251
6.9.2 Direct Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
6.10 Verbindungsstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
6.10.1 Gemeinsamer Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
6.10.2 Zugriffsprotokolle für Busse und gemeinsame Speicher . . . . . . . . . . . 255
6.10.3 Punkt-Zu-Punkt Verbindungen . . . . . . . . . . . . . . . . . . . . . . . . 256
6.10.4 Weitere Verbindungsstrukturen . . . . . . . . . . . . . . . . . . . . . . . . 256
6.10.5 Allgemeine topologische Verbindungsstrukturen . . . . . . . . . . . . . . 257
6.11 Mikrocontroller und Spezialprozessoren . . . . . . . . . . . . . . . . . . . . . . . 259
6.11.1 Mikrocontroller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
6.11.2 Digitale Signalprozessoren . . . . . . . . . . . . . . . . . . . . . . . . . . 260
6.11.3 Grafikprozessoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

7 Rechnernetze 263
7.1 Das OSI-Schichtenmodell der Datenkommunikation . . . . . . . . . . . . . . . . 263
7.2 Bitübertragungsschicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
7.3 Technologien der Sicherungsschicht . . . . . . . . . . . . . . . . . . . . . . . . . 274
7.3.1 Netze im Nahbereich (PAN) . . . . . . . . . . . . . . . . . . . . . . . . . 274
7.3.2 Lokale Netze: LAN und WLAN . . . . . . . . . . . . . . . . . . . . . . . 275
7.3.3 Vorgriff: Leitungs- und Paketvermittlung . . . . . . . . . . . . . . . . . . 279
7.3.4 Datenfernübertragung und der Zugang zum Internet . . . . . . . . . . . . . 281
7.3.5 Die Behandlung von Übertragungsfehlern . . . . . . . . . . . . . . . . . . 286
7.4 Netzwerk- und Transportschicht: TCP/IP und das Internet . . . . . . . . . . . . . . 287
7.4.1 Überblick über das Internet . . . . . . . . . . . . . . . . . . . . . . . . . . 287
7.4.2 IP: Internet Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
7.4.3 TCP: Transmission Control Protocol . . . . . . . . . . . . . . . . . . . . . 292
7.4.4 UDP: User Datagram Protocol . . . . . . . . . . . . . . . . . . . . . . . . 293
7.5 Anwendungsschicht: Von DNS bis HTTP und URIs . . . . . . . . . . . . . . . . . 294
7.5.1 DNS: Domain Name System . . . . . . . . . . . . . . . . . . . . . . . . . 294
7.5.2 E-Mail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
7.5.3 IRC: Internet Relay Chat . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
7.5.4 FTP: File Transfer Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 296
7.5.5 SSH: secure shell und TELNET: teletype network . . . . . . . . . . . . . . 296
7.5.6 HTTP: Hypertext Transfer Protocol . . . . . . . . . . . . . . . . . . . . . 297
7.5.7 URI: Uniform Resource Identifier . . . . . . . . . . . . . . . . . . . . . . 298
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

8 Betriebssysteme 301
8.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
8.1.1 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
8.1.2 Betriebsarten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
8.2 Betriebssystem-Architekturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
Inhaltsverzeichnis xiii

8.3 Aufgaben eines Betriebssystems im Detail . . . . . . . . . . . . . . . . . . . . . . 309

8.3.1 Prozessverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
8.3.2 Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
8.3.3 Interprozess-Kommunikation . . . . . . . . . . . . . . . . . . . . . . . . . 316
8.3.4 Speicherverwaltung und virtueller Speicher . . . . . . . . . . . . . . . . . 317
8.3.5 Geräteverwaltung und -treiber . . . . . . . . . . . . . . . . . . . . . . . . 320
8.3.6 Dateiverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
8.4 Benutzerschnittstelle: Shell und GUI . . . . . . . . . . . . . . . . . . . . . . . . . 322
8.4.1 Kommandozeilen-Interpreter am Beispiel UNIX . . . . . . . . . . . . . . 322
8.4.2 Besonderheiten am Beispiel der UNIX-Shell . . . . . . . . . . . . . . . . 323
8.4.3 Grafische Benutzerschnittstelle . . . . . . . . . . . . . . . . . . . . . . . . 326
8.5 Beispiele für Betriebssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
8.5.1 Microsoft-Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
8.5.2 UNIX, LINUX und Android . . . . . . . . . . . . . . . . . . . . . . . . . 328
8.6 Betriebssystem-Virtualisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
8.6.1 Anwendungsbereiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
8.6.2 Hypervisoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
8.6.3 Virtuelle Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.6.4 Grundlegende Aktivitäten der Virtualisierung . . . . . . . . . . . . . . . . 334
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

9 Datenbanken 337
9.1 Einführung und Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
9.2 Relationale Datenbankmanagement-Systeme . . . . . . . . . . . . . . . . . . . . 341
9.2.1 Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
9.2.2 Schlüssel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
9.2.3 Beziehungen (Relationships) . . . . . . . . . . . . . . . . . . . . . . . . . 343
9.3 Relationale Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
9.4 Die Datenbanksprache SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
9.4.1 SQL als deklarative Sprache . . . . . . . . . . . . . . . . . . . . . . . . . 348
9.4.2 Definition des Datenbankschemas . . . . . . . . . . . . . . . . . . . . . . 348
9.4.3 Einfügen, Ändern und Löschen von Daten . . . . . . . . . . . . . . . . . . 350
9.4.4 Suchen mit SELECT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
9.4.5 Programmiersprachen und SQL . . . . . . . . . . . . . . . . . . . . . . . 352
9.5 NoSQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
9.6 Transaktionen, OLTP und ACID . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
9.7 OLAP, Data Warehousing und Data-Mining . . . . . . . . . . . . . . . . . . . . . 356
9.8 Semi-Strukturierte Daten mit XML . . . . . . . . . . . . . . . . . . . . . . . . . . 362
9.8.1 Der Aufbau von XML-Dokumenten . . . . . . . . . . . . . . . . . . . . . 363
9.8.2 Wohlgeformtheit und Validität . . . . . . . . . . . . . . . . . . . . . . . . 365
9.8.3 XML-Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
9.8.4 XPath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
9.8.5 XSL: Extended Style Sheet Language . . . . . . . . . . . . . . . . . . . . 366
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
xiv Inhaltsverzeichnis

10 Automatentheorie und formale Sprachen 371

10.1 Grundbegriffe der Automatentheorie . . . . . . . . . . . . . . . . . . . . . . . . . 371
10.1.1 Definition von Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . 371
10.1.2 Darstellung von Automaten . . . . . . . . . . . . . . . . . . . . . . . . . 374
10.1.3 Die akzeptierte Sprache von Automaten . . . . . . . . . . . . . . . . . . . 376
10.1.4 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
10.1.5 Turing-Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
10.2 Einführung in die Theorie der formalen Sprachen . . . . . . . . . . . . . . . . . . 393
10.2.1 Definition von formalen Sprachen . . . . . . . . . . . . . . . . . . . . . . 393
10.2.2 Die Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
10.2.3 Das Pumping-Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
10.2.4 Die Analyse von Wörtern . . . . . . . . . . . . . . . . . . . . . . . . . . 403
10.2.5 Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414

11 Algorithmen – Berechenbarkeit und Komplexität 415

11.1 Berechenbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
11.1.1 Entscheidungsproblem und Church-Turing These . . . . . . . . . . . . . . 417
11.1.2 Das Halteproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
11.1.3 Satz von Rice und weitere unentscheidbare Probleme . . . . . . . . . . . . 422
11.1.4 LOOP-, WHILE- und GOTO-Berechenbarkeit . . . . . . . . . . . . . . . 423
11.1.5 Primitiv rekursive und µ -rekursive Funktionen . . . . . . . . . . . . . . . 426
11.2 Komplexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
11.2.1 Die Ordnung der Komplexität: O-Notation . . . . . . . . . . . . . . . . . 431
11.2.2 Analyse von Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . 435
11.2.3 Die Komplexitätsklassen P und NP . . . . . . . . . . . . . . . . . . . . . 439
11.2.4 NP-vollständige Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . 441
11.2.5 Weitere Komplexitätsklassen . . . . . . . . . . . . . . . . . . . . . . . . . 445
11.3 Probabilistische Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
11.3.1 Pseudo-Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
11.3.2 Monte-Carlo-Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
11.3.3 Probabilistischer Primzahltest . . . . . . . . . . . . . . . . . . . . . . . . 455
11.4 Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
11.4.1 Definition und einführende Beispiele . . . . . . . . . . . . . . . . . . . . 459
11.4.2 Rekursive Programmierung und Iteration . . . . . . . . . . . . . . . . . . 460
11.4.3 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466

12 Suchen und Sortieren 469

12.1 Einfache Suchverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
12.1.1 Sequentielle Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
12.1.2 Binäre Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
12.1.3 Interpolationssuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
12.1.4 Radix-Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
12.2 Suchen von Mustern in Zeichenketten . . . . . . . . . . . . . . . . . . . . . . . . 474
12.2.1 Musterabgleich durch sequentielles Vergleichen . . . . . . . . . . . . . . . 474
Inhaltsverzeichnis xv

12.2.2 Musterabgleich durch Automaten . . . . . . . . . . . . . . . . . . . . . . 475

12.2.3 Die Verfahren von Boyer-Moore und Knuth-Morris-Pratt . . . . . . . . . . 476
12.2.4 Ähnlichkeit von Mustern und Levenshtein-Distanz . . . . . . . . . . . . . 478
12.3 Gestreute Speicherung (Hashing) . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
12.3.1 Hash-Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
12.3.2 Kollisionsbehandlung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
12.3.3 Komplexitätsberechnung . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
12.4 Direkte Sortierverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
12.4.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
12.4.2 Sortieren durch direktes Einfügen (Insertion Sort) . . . . . . . . . . . . . . 492
12.4.3 Sortieren durch direktes Auswählen (Selection Sort) . . . . . . . . . . . . 494
12.4.4 Sortieren durch direktes Austauschen (Bubblesort) . . . . . . . . . . . . . 496
12.5 Höhere Sortierverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
12.5.1 Shellsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
12.5.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
12.5.3 Vergleich der Sortierverfahren . . . . . . . . . . . . . . . . . . . . . . . . 504
12.6 Sortieren externer Dateien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
12.6.1 Grundprinzipien des sequentiellen Datenzugriffs . . . . . . . . . . . . . . 506
12.6.2 Sequentielle Speicherorganisation . . . . . . . . . . . . . . . . . . . . . . 509
12.6.3 Direktes Mischen (Direct Merge, Mergesort) . . . . . . . . . . . . . . . . 513
12.6.4 Natürliches Mischen (Natural Merge) . . . . . . . . . . . . . . . . . . . . 516
12.6.5 n-Band-Mischen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521

13 Bäume und Graphen 523

13.1 Binärbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
13.1.1 Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
13.1.2 Speichern und Durchsuchen von Binärbäumen . . . . . . . . . . . . . . . 525
13.1.3 Binäre Suchbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
13.1.4 Ausgleichen von Bäumen und AVL-Bäume . . . . . . . . . . . . . . . . . 537
13.1.5 Heaps und Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
13.2 Vielwegbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
13.2.1 Rückführung auf Binärbäume . . . . . . . . . . . . . . . . . . . . . . . . 548
13.2.2 Definition von (a, b)-Bäumen und B-Bäumen . . . . . . . . . . . . . . . . 549
13.2.3 Operationen auf B-Bäumen . . . . . . . . . . . . . . . . . . . . . . . . . 552
13.3 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
13.3.1 Definitionen und einführende Beispiele . . . . . . . . . . . . . . . . . . . 560
13.3.2 Speicherung von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . 564
13.3.3 Suchen, Einfügen und Löschen von Knoten und Kanten . . . . . . . . . . 570
13.3.4 Durchsuchen von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . 571
13.3.5 Halbordnung und topologisches Sortieren . . . . . . . . . . . . . . . . . . 584
13.3.6 Minimal spannende Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . 587
13.3.7 Union-Find Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
xvi Inhaltsverzeichnis

14 Höhere Programmiersprachen und C 597

14.1 Zur Struktur höherer Programmiersprachen . . . . . . . . . . . . . . . . . . . . . 597
14.1.1 Überblick über höhere Programmiersprachen . . . . . . . . . . . . . . . . 597
14.1.2 Ebenen des Informationsbegriffs in Programmiersprachen . . . . . . . . . 602
14.1.3 Systeme und Strukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
14.2 Methoden der Syntaxbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . . 607
14.2.1 Die Backus-Naur Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
14.2.2 Syntaxgraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
14.2.3 Eine einfache Sprache als Beispiel: C- - . . . . . . . . . . . . . . . . . . . 611
14.3 Einführung in die Programmiersprache C . . . . . . . . . . . . . . . . . . . . . . 616
14.3.1 Der Aufbau von C-Programmen . . . . . . . . . . . . . . . . . . . . . . . 617
14.3.2 Einfache Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
14.3.3 Strukturierte Standard-Datentypen . . . . . . . . . . . . . . . . . . . . . . 626
14.3.4 Operatoren und Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . 629
14.3.5 Anweisungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632
14.3.6 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
14.3.7 Ein- und Ausgabefunktionen . . . . . . . . . . . . . . . . . . . . . . . . . 641
14.3.8 Verarbeitung von Zeichenketten . . . . . . . . . . . . . . . . . . . . . . . 643
14.3.9 Das Zeigerkonzept in C . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
14.4 Sequentielle Datenstrukturen mit C . . . . . . . . . . . . . . . . . . . . . . . . . . 654
14.4.1 Vorbemerkungen zu Algorithmen und Datenstrukturen . . . . . . . . . . . 654
14.4.2 Lineare Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
14.4.3 Stapel und Schlangen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665

15 Objektorientierte Programmiersprachen und Java 667

15.1 Entstehung objektorientierter Sprachen . . . . . . . . . . . . . . . . . . . . . . . . 667
15.2 Einführung in die Programmiersprache Java . . . . . . . . . . . . . . . . . . . . . 670
15.2.1 Grundlegender Aufbau eines Java-Programms . . . . . . . . . . . . . . . . 672
15.2.2 Syntax ähnlich wie in C . . . . . . . . . . . . . . . . . . . . . . . . . . . 674
15.2.3 Datentypen und Variablen: Statische Typisierung . . . . . . . . . . . . . . 675
15.3 Klassen und Objekte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
15.3.1 Attribute und Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
15.3.2 Statische Attribute und Methoden . . . . . . . . . . . . . . . . . . . . . . 682
15.3.3 Pakete (Packages) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
15.3.4 Kapselung und Geheimnisprinzip . . . . . . . . . . . . . . . . . . . . . . 685
15.3.5 Vererbung und Polymorphie . . . . . . . . . . . . . . . . . . . . . . . . . 687
15.4 Fortgeschrittene Java-Themen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
15.4.1 Generische Klassen, Behälter und Algorithmen . . . . . . . . . . . . . . . 690
15.4.2 Ausnahmen und Fehlerbehandlung . . . . . . . . . . . . . . . . . . . . . . 694
15.4.3 Annotationen und Reflection . . . . . . . . . . . . . . . . . . . . . . . . . 695
15.4.4 Testgetriebene Entwicklung mit Java . . . . . . . . . . . . . . . . . . . . . 697
15.4.5 Threads, Streams und parallele Verarbeitung . . . . . . . . . . . . . . . . 698
15.4.6 Lambda-Ausdrücke und funktionale Programmierung . . . . . . . . . . . 702
15.4.7 Das Java-Ökosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
Inhaltsverzeichnis xvii

16 Anwendungsprogrammierung im Internet 707

16.1 Client-Server-Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
16.2 Grundlegende Technologien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
16.2.1 HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
16.2.2 DOM: Domain Object Model . . . . . . . . . . . . . . . . . . . . . . . . 714
16.2.3 CSS: Cascading Style Sheets . . . . . . . . . . . . . . . . . . . . . . . . . 715
16.3 Webanwendungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
16.3.1 HTML Formulare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
16.3.2 Auswertung von Formularen . . . . . . . . . . . . . . . . . . . . . . . . . 721
16.4 JavaScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
16.4.1 Grundlegende Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . 723
16.4.2 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
16.4.3 Objekte und Prototypen . . . . . . . . . . . . . . . . . . . . . . . . . . . 727
16.4.4 JSON: JavaScript Object Notation . . . . . . . . . . . . . . . . . . . . . . 729
16.4.5 JavaScript und DOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
16.4.6 Ereignisgesteuerte Programmierung mit JavaScript . . . . . . . . . . . . . 732
16.4.7 AJAX: Asynchronous JavaScript And XML . . . . . . . . . . . . . . . . . 733
16.5 Serverseitige Skripte mit PHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
16.5.1 Grundlegende Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . 734
16.5.2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736
16.5.3 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738
16.5.4 Objektorientierte Programmierung in PHP . . . . . . . . . . . . . . . . . . 740
16.5.5 Datenübergabe von HTML-Formularen an PHP-Skripte . . . . . . . . . . 741
16.5.6 Sitzungsdaten: Session und Cookie . . . . . . . . . . . . . . . . . . . . . 742
16.5.7 Datei- und Datenbankzugriff mit PHP . . . . . . . . . . . . . . . . . . . . 743
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745

17 Software-Engineering 747
17.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
17.1.1 Was ist Software? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
17.1.2 Was bedeutet Engineering? . . . . . . . . . . . . . . . . . . . . . . . . . . 748
17.1.3 Warum ist Software-Engineering schwierig? . . . . . . . . . . . . . . . . 749
17.2 Tätigkeiten im Software-Lebenszyklus . . . . . . . . . . . . . . . . . . . . . . . . 751
17.2.1 Anforderungsanalyse und Spezifikation . . . . . . . . . . . . . . . . . . . 751
17.2.2 Architekturentwurf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
17.2.3 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
17.2.4 Test und Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
17.2.5 Inbetriebnahme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
17.2.6 Wartung und Weiterentwicklung . . . . . . . . . . . . . . . . . . . . . . . 753
17.3 Querschnittsdisziplinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
17.3.1 Projektmanagement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
17.3.2 Qualitätsmanagement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755
17.3.3 Konfigurationsmanagement . . . . . . . . . . . . . . . . . . . . . . . . . 756
17.4 Vorgehensmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
17.4.1 Basismodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759
17.4.2 V-Modell XT als plangetriebenes Vorgehensmodell . . . . . . . . . . . . . 761
xviii Inhaltsverzeichnis

17.4.3 Scrum als agiles Vorgehensmodell (-Framework) . . . . . . . . . . . . . . 763

17.5 Modelle im Software-Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . 765
17.5.1 Vom Problem zur Lösung . . . . . . . . . . . . . . . . . . . . . . . . . . 765
17.5.2 Die Unified Modeling Language . . . . . . . . . . . . . . . . . . . . . . . 766
17.5.3 Ausgewählte Diagramme der UML im Detail . . . . . . . . . . . . . . . . 768
17.6 Hilfsmittel für den Entwurf von Algorithmen . . . . . . . . . . . . . . . . . . . . 776
17.6.1 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776
17.6.2 Flussdiagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776
17.6.3 Struktogramme nach Nassi-Shneiderman . . . . . . . . . . . . . . . . . . 777
17.6.4 Entscheidungstabellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 780
Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783

Index 785

Die Autoren 809