Springers Lehrbücher
der Informatik
Herausgegeben von
o. Univ.-Prof. Dr.-lng. Gerhard-Helge Schildt
Technische Universität Wien
Springer-Verlag Wien GmbH
Johann Blieberger
Johann Klasek
Alexander Redlein
Gerhard-Helge Schildt
Informatik
Dritte, erweiterte
Auflage
Springers Lehrbiicher
der Informatik
Springer-Verlag Wien GmbH
Univ.-Ass. Dipl.-Ing. Dr. Johann Blieberger
Univ.-Ass. Dipl.-Ing. Johann Klasek
Univ.-Ass. Dipl.-Ing. Mag. Alexander Redlein
o. Univ.-Prof. Dr.-Ing. Gerhard-Helge Schildt
Institut fiir Automation
Technische Universitat, Wien, Osterreich
Das Werk ist urheberrechtlich geschtitzt.
Die dadurch begrtindetcn Rechte,
insbesondere die der Obersetzung, des Nachdruckes,
der Entnahmc von Abbildungen, der Funksendung,
der Wiedergabe auf photomechanischem oder ahnlichem Wege
und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bci nur auszugswciser Verwertung, vorbehalten.
© 1990, 1992 und 1996 Springer-Verlag Wien
Ursprünglich erschienen bei Springer-Verlag/Wien
Satz: Reproduktionsfertige Vorlage der Autoren
Graphisches Konzept: Ecke Bonk
Gedruckt auf saurefreiem, chlorfrei gebleichtem Papier- TCF
Mit 183 Abbildungen
ISSN 0938-9504
ISBN 978-3-211-82860-1 ISBN 978-3-7091-4051-2 (eBook)
DOI 10.1007/978-3-7091-4051-2
Vorwort
Für euch, Kinder der Wissenschaft und der Weisheit,
haben wir dieses geschrieben. Erforschet das Buch
und suchet euch unsere Ansicht zusammen, die wir
verstreut und an mehreren Orten dargetan haben;
was euch an einem Orte verborgen bleibt, das haben
wir an einem anderen offengelegt,
damit es faßbar werde für eure Weisheit.
Heinrich Cornelius Agrippa von Nettesheirn,
"De occulta philosophia".
Angesichts einer wahren Flut von Büchern über Informatik erhebt sich die berechtigte Frage,
was vier in der Informatiker-Ausbildung an der Technischen Universität Wien tätige Autoren
veranlaßt, beinahe ein ganzes Jahr ihrer ohnedies knappen Zeit zu opfern und ein weiteres zu
schreiben ". .. damit es faßbar werde für eure Weisheit"?
Initiales Moment für die Beschäftigung mit dieser Idee war das Problem, den Hörern der für
das erste Semester vorgesehenen Vorlesung "Einführung in die Informatik" geeignete schriftliche
Unterlagen empfehlen zu müssen. Die Ziele dieser insgesamt sechsstündigen Lehrver2nstaltung
haben, im Gegensatz zu der parallel stattfindenden "Einführung in das Programmieren", jedoch
kaum etwas mit der Entwicklung von Software zu tun. Vielmehr werden hier gerrau jene Aspekte
der Informatik abgedeckt, die nicht die eigentliche Programmierung betreffen.
Nun erwies sich aber ein Großteil der in der letzten Zeit erschienenen (guten) Bücher über
Informatik als zu anspruchsvoll beziehungsweise zu spezialisiert; etwa 80% der in technischen
Buchhandlungen zu findenden Werke sind eigentlich Programm- oder Hardware-Beschreibungen.
Im Endeffekt konnten wir daher kein deutschsprachiges Buch finden, das eine dem Niveau des
ersten Semesters angemessene Einführung in die moderne Informatik bietet - und dabei die
eigentliche Programmierung ausklammert.
Der stoffliche Aufbau unserer INFORMATIK ist daher zunächst einmal darauf ausgerichtet,
einige der wesentlichen theoretischen Grundlagen zu erarbeiten. Dadurch werden nicht zuletzt
auch die Voraussetzungen für die anschließenden Kapitel geschaffen, die sich mit der FUnk-
tionsweise moderner Computersysteme beschäftigen. Die Lektüre des Buches soll den Leser
letztendlich in die Lage versetzen, zu verstehen, was bei der Ausführung eines Programmes auf
einem Computer nun tatsächlich vor sich geht. Auf diese Weise kann das Flair des "Mysteriösen",
das der- im Zuge der eigentlichen Programmierung notwendigen - Verwendung eines Computers
anfänglich anhaftet, im Laufe eines Semesters durch ein dem Informatiker eher anstehendes
Wissen um die tieferen Zusammenhänge ersetzt werden.
Das Buch ist streng hierarchisch aufgebaut, das heißt, der Inhalt späterer Kapitel setzt den
Inhalt früherer Kapitel voraus, nicht aber umgekehrt. Im Vordergrund steht dabei ein umfas-
sender Überblick über die einzelnen Themen, aber natürlich unter Berücksichtigung des für das
Verständnis notwendigen und zurnutbaren Detaillierungsgrades. Die Intention war, eine Art "stu-
dienbegleitende Übersicht" zu schaffen, also ein einführendes Werk, dessen Gültigkeit nicht mit
dem ersten Semester endet; diese Absicht äußert sich nicht zuletzt schon in einem umfangreichen
vi
Index. Daß dies aber in Anbetracht der ungeheuer schnell vor sich gehenden Weiterentwicklung
der Informatik nur ein Versuch sein kann, liegt auf der Hand.
Was den Stil und die Aufmachung des Ganzen betrifft, haben wir versucht, den normalerweise
üblichen, trockenen Sachbuchcharakter von "Definition- Satz- Beweis" zugunsten einer lockeren
und das intuitive Verständnis fördernden Darstellung aufzugeben. In den Text eingestreut finden
sich etwa, neben vielen Abbildungen, auch diverse Literaturzitate aus den verschiedensten Berei-
chen. Diese zu suchen haben wir nicht nur auf uns genommen, um Ihnen etwas von dem Spaß zu
vermitteln, den uns die Beschäftigung mit informatischen Belangen bereitet, sondern auch, um
anzudeuten, wie viele Assoziationsmöglichkeiten mit nicht minder wichtigen und interessanten
Gebieten der menschlichen Kultur eine angeblich trockene Materie bieten kann.
Es bleibt uns nur mehr, jenen Studenten Dank zu sagen, die mit ihren Kommentaren und Ver-
besserungsvorschlägen dazu beigetragen haben, daß das Buch in der vorliegenden Form präsen-
tiert werden kann. Ferner gebührt unser Dank Monika Stöckler für den Entwurf des Titelbildes
und nicht zuletzt Martina Lunzer für die Erstellung vieler Abbildungen und die Erledigung so
mancher Tipparbeit.
Vorwort zur 3. Auflage
Leider mußten wir bei der dritten Auflage auf zwei unserer Autoren verzichten. Stefan Stöcklerist
mittlerweile aus unserem Institut ausgeschieden; Dr. Ulrich Schmid war aus zeitlichen Gründen
nicht in der Lage, bei dieser Auflage mitzuwirken. Wir möchten uns hiermit bei beiden für die
geleistete Arbeit und für die Überlassung wertvoller Teile der letzten Auflage bedanken.
Gleichzeitig sind wir glücklich darüber, zwei fachlich versierte Autoren gefunden zu haben,
die die verwaisten Kapitel betreuen, nämlich Herrn Johann Klasek und Herrn Alexander Redlein.
Die nunmehr vorliegende dritte, erweiterte Auflage unterscheidet sich von der zweiten in
wesentlichen Teilen:
• Die Gesamtstruktur des Buches wurde einer Revision unterzogen und an den Stand der
Technik angepaßt.
• Die Kapitel, die sich mit Hardware beschäftigen, wurden überarbeitet.
• Einige der in der ersten und zweiten Auflage enthaltenen Kapitel gewinnen erst jetzt
anläßlich der Euphorie im Zusammenhang mit dem W orld- Wide Web (als Bestandteill
des Internet genannt) ihre ihnen zukommende Bedeutung. Dies betrifft vor allem die Ka-
pitel über Public Key Cryptosystems und die ausführliche Behandlung von Computer-
Netzwerken.
Wir hoffen, mit den von uns nunmehr hinzugefügten Teilen den Trend der Zeit richtig
erkannt zu haben. So werden nach unserer Meinung die Themen elektronisches Geld und
informationsreduzierende Codierung wichtige Themen der zukünftigen Entwicklung der
Informatik sein.
Abschließend wollen wir uns bei den Lesern bedanken, die mit ihren Kommentaren dazu
beigetragen haben, Fehler zu beheben und Lücken in der Präsentation zu schließen.
Oberwaltersdorf, Wien, Klosterneuburg, Preßbaum, September 1996
J. Blieberger, J. Klasek, A. Redlein, G.-H. Schildt
Inhaltsverzeichnis
Einführung 1
1 Entwicklung des Berufsbildes 3
2 Inhaltsübersicht 7
Theoretische Grundlagen 13
3 Informationstheorie 15
301 Der Begriff Information und seine Entstehung 0 15
302 Der nachrichtentechnische Informationsbegriff 0 17
303 Grundlagen der Codierung 0 0 0 0 0 19
304 Informationstheorie nach Shannon 0 0 0 0 0 0 0 21
4 Codierungstheorie 25
401 Datenverdichtung 0 0 0 0 0 0 0 0 0 0 0 25
401.1 Der Hufiman-Code 0 0 0 0 0 0 25
4ol.2 Ein adaptiver Hufiman-Code 27
4ol.3 Arithmetisches Codieren 0 27
402 Datenkompression 0 0 0 29
40201 Modeliierung 0 0 0 0 0 0 0 29
40202 Übliche Modelle 0 0 0 0 0 31
403 Fehlererkennende und fehlerkorrigierende Codes 0 35
40301 Die Hammingdistanz 0 0 0 36
40302 Fehlererkennende Codes 0 38
40303 Fehlerkorrigierende Codes 40
404 Zifferncodierung 0 41
4.401 BCD-Code 0 0 0 0 0 o o o 42
40402 Gray-Code 0 0 0 0 0 0 0 0 42
4o5 Codierung alphanumerischer Zeichen 42
40501 Der ASCII-Code 0 0 0 0 0 42
40502 Der ISO 10646 Standard 0 0 0 42
406 Cryptographie 0 0 0 0 0 0 0 0 0 0 0 0 45
40601 Traditionelle Verschlüsselungsmethoden 45
40602 Ersetzungsmethoden 0 0 0 0 0 0 47
40603 Verschiebungsmethoden 0 0 0 0 49
40604 Der Data Encryption Standard 50
40605 Public Key Cryptosystems 52
40606 Die RSA-Methode 0 53
40607 Authentisierung 0 0 54
40608 Elektronisches Geld 55
viii INHALTSVERZEICHNIS
5 Informationsreduzierende Codierungen 59
5.1 Matrizen . . . . . . . . . . . . . . . . . 59
5.2 Diskrete Cosinus-Transformation . . . . . . . . . . . . . . . . . . . 62
5. 2.1 Einige Eigenschaften der diskreten Cosinus-Transformation 62
5.2.2 Algorithmische Durchführung der DCT . . . 64
5.3 Anwendungen der diskreten Cosinus-Transformation 65
5.3.1 Signale und Sprache 65
5.3.2 Bilder . . . . . . 65
5.3.3 Ein Beispiel . . . . . 67
5.3.4 Film und Video . . . 68
5.4 Wavelet-Transformationen . 69
5.5 Fraktale Bildkompression 69
6 Zahlendarsteilungen 71
6.1 Zahlensysteme 71
6.2 Der ideelle Zahlenbegriff . 73
6.3 Zahlenumwandlungen . . 73
6.3.1 Konversion von ganzen Zahlen 74
6.3.2 Konversion von Zahlen mit Nachkommastellen 75
6.3.3 Konversion zwischen binärer und hexadezimaler Darstellung 76
6.4 Rechnen im binären System . . . . . . . . . . . . 77
6.4.1 Die Addition im binären Zahlensystem . . . . 77
6.4.2 Die Subtraktion im binären Zahlensystem .. 78
6.4.3 Die Multiplikation im binären Zahlensystem. 79
6.4.4 Die Division im binären Zahlensystem 80
6.5 Rechnen im hexadezimalen System 81
6.6 Rechnen mit überlangen Zahlen . 81
6. 7 Potenzieren . . . . . . . . . . . . . 83
6.8 Darstellung negativer Zahlen . . . 84
6.8.1 Darstellung durch Vorzeichen und Betrag 84
6.8.2 Exzeßdarstellung . . . . . . . . 85
6.8.3 Einerkomplementdarstellung 85
6.8.4 Zweierkomplementdarstellung . 87
6.9 Darstellung reeller Zahlen .. . 88
6.9.1 Festkommadarstellung . . . . . 88
6.9.2 Gleitkommadarstellung . . . . 88
6.9.3 IEEE-Formate zur Darstellung von Gleitkommazahlen . 89
6.9.4 Normalisieren von Gleitkommazahlen . . . . . . . 90
6.9.5 Addition und Subtraktion von Gleitkommazahlen 90
6.9.6 Multiplikation und Division für Gleitkommazahlen 92
6.9.7 Genauigkeitsbetrachtungen . . . . . . . . . . . . . 92
7 Algorithmen 95
7.1 Analyse von Algorithmen . . . . . . . . . . . . . 95
7.2 Präludium und Fuge über ein Thema von Hoare 99
8 Boolesche Algebra 109
8.1 Operationen der Booleschen Algebra 109
8.2 Gesetze der Booleschen Algebra . . . 110
8.3 Funktionen über der Booleschen Algebra . 112
8.4 Normalformen . . . . . . . . . . . 114
8.4.1 Disjunktive Normalform . 114
8.4.2 Konjunktive Normalform 115
INHALTSVERZEICHNIS ix
8.5 Vereinfachen von Funktionen . . . . . . . . . 115
8.5.1 Verfahren nach Quine und McCluskey 116
8.5.2 Verfahren nach Karnaugh und Veitch 121
9 Fuzzy-Logik 127
9.1 Fuzzy-Mengen. 128
9.2 Fuzzyfizierung . 129
9.3 Regelbasis . . . 131
9.4 Inferenz . . . . 132
9.5 Defuzzyfizierung 134
Hardware 137
10 Logische Schaltungen 139
10.1 Grundbegriffe . . . . . . . . . 139
10.2 Realisierung von Funktionen 142
10.2.1 Halbaddierer 143
10.2.2 Volladdierer . 144
10.2.3 Codierer 146
10.2.4 Decodierer . 147
10.2.5 Multiplexer . 148
10.2.6 Demultiplexer . 150
10.3 Sequentielle Logik .. 151
10.3.1 Latches (Flip-Flops) 151
10.3.2 Register . . 156
10.3.3 Zähler . . . . . . 160
10.4 Halbleiterspeicher . . . . 163
10.4.1 Tabellenspeicher 164
10.4.2 Funktionsspeicher (ASICs) 168
11 Mikroprozessoren 171
11.1 Endliche Automaten 171
11.2 Prozessoren . . . . . 177
11.2.1 Arithmetic Logic Unit 177
11.2.2 Register File und Busverbindungen. 181
11.2.3 Speieheranbindung . 184
11.2.4 Control Unit . . . . . . . . . . . . . 187
11.2.5 Miere-Programm . . . . . . . . . . . 191
11.2.6 Very Large Scale Integration (VLSI) 194
12 Computersysteme 195
12.1 Prozessoren . . . . . . . . . 195
12.1.1 Maschinen-Code .. 195
12.1.2 Adressierungsarten . 207
12.1.3 Architekturen . . . . 211
12.1.4 Parallelverarbeitung innerhalb eines Rechners . 212
12.1.5 CISC versus RISC . 217
12.2 Speicher . . . . . . . . . . . 218
12.2.1 Interleaved Memory 219
12.2.2 Caches . . . . . . . . 221
12.2.3 Direct Memory Access (DMA) 225
12.2.4 Controller und Co-Prozessoren 227
X INHALTSVERZEICHNIS
12.2.5 Interconnection . 229
12.3 Periphere Geräte . . . 230
12.3.1 Externspeicher 231
12.3.2 Dialoggeräte . 238
Betriebssysteme und Systemsoftware 247
13 Historische Entwicklung 249
14 Prozesse 253
14.1 Threads 255
14.2 Objekte 259
14.3 Parallelität 261
14.4 Prozeßhierarchien . 264
14.5 Prozeßzustände .. 267
14.6 Scheduling . . . . . 273
14.6.1 Prozeß-Scheduling 273
14.6.2 Thread-Scheduling 276
14.6.3 Job-Scheduling 277
15 Speicherverwaltung 279
15.1 Virtuelle Adreßzuordnung 281
15.2 Physikalische Adreßzuordnung 286
15.2.1 Swapping . . . 287
15.2.2 Paging . . . . . 290
15.2.3 Segmentierung 294
16 Interprozeß-Kommunikation 299
16.1 Server-Prozesse . . .. 299
16.2 Synchrone Methoden .. 304
16.2.1 Semaphore . . . 304
16.2.2 Message Passing 307
16.2.3 Höhere Mechanismen . 309
16.3 Asynchrone Methoden 310
17 Netzwerke 313
17.1 Struktur . 314
17.2 Standardisierung 316
17.3 Architekturen .. 317
17.3.1 OSI Reference Model . 319
17.3.2 Fallbeispiele .. 323
18 Betriebssystem-Struktur 329
18.1 System-Calls . . . . 331
18.2 Netzwerkintegration 333
18.3 Sicherheitsaspekte . 337
19 Resource-Management 341
19.1 Objektorientierung in Betriebssystemen 341
19.1.1 Protection . . . . . . . . 343
19 .1. 2 Device-Unabhängigkeit 345
19.2 Ressourcen-Klassen .. 347
19.2.1 Externspeicher . . . . . 347
INHALTSVERZEICHNIS Xl
19.2.2 Rardeopies .. 360
19.2.3 Dialog-Geräte . 362
19.3 Deadlocks .. 364
20 Human Interface 369
20.1 User-IDs . . . 370
20.2 Logirr . . . . . . . . . . 372
20.3 Job Control Languages . 374
21 Assemblersprachen 381
21.1 Assembler . . . . 381
21.2 Macra-Assembler 382
22 Höhere Programmiersprachen 385
22.1 Wichtige Konzepte höherer Programmiersprachen. 385
22 .1.1 Kontrollstrukturen . . . . 386
22.1.2 Rautirren und Parameter 387
22.1.3 Modulkonzepte . . . . . 389
22.1.4 Objektorientierung .. . 389
22.1.5 Entwicklungstendenzen 390