Zur Entwicklung des Computers und der Informatik 14


1 Wissenschaftliche und historische Grundlagen 17

1.1 Was ist Informatik 17
1.1.1 Algorithmen und Algorithmierung 22
1.1.2 Gliederung der Wissenschaft Informatik 23

1.2 Der Informationsbegriff und das Maß der Information 26
1.2.1 Der Begriff der Information 26
1.2.2 Das Maß der Information 26

1.3 Der Computer als Werkzeug 27

1.4 Die Entwicklung der Informatik 30
1.4.1 Erleichterung der arithmetischen Arbeit und Steigerung der Rechengeschwindigkeit 30
1.4.2 Programmierbare Rechenmaschinen oder Computer 32
1.4.3 Generationen der Computer 34
1.4.4 Computerstruktur und Programmierung nach von Neumann 36

1.5 Übungen 47
1.5.1 Kontrollfragen 47
1.5.2 Aufgaben 48
1.5.3 Referate 50

1.6 Literatur 50


2 Technische Grundlagen 53

2.1 Einführung in die Computertechnik 53
2.1.1 Computergenerationen, Mikroprozessorgenerationen 53
2.1.2 Äußerer Aufbau eines Computers 55
2.1.3 Innerer Aufbau eines Computers 56
2.1.4 Übersicht über den derzeitigen Stand der Computertechnik 56
2.1.4.1 Systematisierung nach der Leistung des Computers 57
2.1.4.2 Systematisierung nach dem installierten Betriebssystem 59
2.1.4.3 Systematisierung nach der CPU-Architektur 60
2.1.5 Zahlensysteme und Zahlendarstellung 61

2.2 Das Grundkonzept der von-Neumann-Rechnerarchitektur 65
2.2.1 Die Blockstruktur eines Digitalrechners 65
2.2.2 Prinzipieller Ablauf der Befehlsabarbeitung 67
2.2.3 Befehls- und Registersatz eines Mikrorechners, Programmiermodelle 70
2.2.3.1 Befehlssatz 70
2.2.3.2 Programmiermodell 71
2.2.4 Einige Besonderheiten der Intel-Prozessoren 80x86 (Pentium) 73
2.2.5 Datenaustausch zwischen CPU und Ports 77
2.2.5.1 Steuerung der Ein- und Ausgabe 77
2.2.5.2 Portadressen 78
2.2.5.3 Interrupts 78

2.3 Bus- und Schnittstellenkonzepte 80
2.3.1 Busvarianten von IBM-kompatiblen PCs 81
2.3.1.1 Vorläufer der aktuellen Busstruktur 81
2.3.1.2 PCI-Bus (Peripheral Component Interconnect) 82
2.3.1.3 Taktverhältnisse zwischen den Bussystemen 84
2.3.2 Geräteschnittstellen und Gerätebusse 85
2.3.2.1 Serielle und parallele Schnittstellen 86
2.3.2.2 Festplattenschnittstellen 87
2.3.2.3 SCSI-Bus 89
2.3.2.4 PCMCIA-Schnittstelle 89
2.3.2.5 USB-Schnittstelle (Universal Serial Bus) 90
2.3.2.6 IEEE 1394 (Firewire) 90

2.4 Monitore, Grafikkarten und Grafikstandards 90
2.4.1 Funktionsprinzip und wichtige Kennwerte 91
2.4.1.1 Bildschirmaufbau durch den Monitor 91
2.4.1.2 Wichtige Kennwerte 92
2.4.1.3 Aufbau und Funktionsweise einer Grafikkarte 94
2.4.2 Übersicht zu bestehenden Standards 96
2.4.3 Moderne Konzepte bei Grafikkarten hoher Leistung 97
2.4.3.1 Windows-Beschleunigerkarten 98
2.4.3.2 3D-Grafikkarten 98
2.4.4 Alternative Monitortechniken - Flachbildschirme 99

2.5 Speichertechniken 101
2.5.1 Klassifizierung und Kenngrößen von Speichern 101
2.5.2 Schnelle Datenspeicher (Halbleiterspeicher) 104
2.5.3 Massenspeicher 107
2.5.3.1 Disketten 108
2.5.3.2 Festplatten 109
2.5.3.3 CD-ROM und DVD 111
2.5.3.4 Magnetooptische Speicher 118
2.5.3.5 WORM 119
2.5.3.6 Streamer und Bandlaufwerke 119

2.6 Drucker und Plotter 120
2.6.1 Einführung 120
2.6.2 Klassifizierung und Kennwerte 121
2.6.3 Drucktechnologien 124
2.6.3.1 Nadeldrucker 124
2.6.3.2 Laserdrucker 125
2.6.3.3 Tintenstrahldrucker 127
2.6.3.4 Thermodrucker 128
2.6.4 Druckersteuersprachen 129
2.6.5 Plottertechnologie, Steuersprachen und Treiber 132
2.6.6 Grundlagen der Zeichendarstellung 133

2.7 Scanner 134
2.7.1 Aufgaben und Typen von Scannern 134
2.7.2 Aufbau und Funktionsprinzip von Flachbettscannern 135
2.7.3 Kennwerte 135
2.7.4 Software für Scanner und Optimierung der Scanparameter 136

2.8 Multimediaerweiterungen 138
2.8.1 Audiokarten 139
2.8.2 Videokarten 140
2.8.3 Digitale Kameras und digitale Videokameras 141
2.10 Literaturverzeichnis 141


3 Betriebssysteme 143

3.1 Betriebssysteme: was und wozu? 143
3.1.1 Installation eines Betriebssystems 143
3.1.2 Was ist ein Betriebssystem? 144
3.1.3 Geschichte der Betriebssysteme 145
3.1.4 Konzepte von Betriebssystemen 147
3.1.5 Strukturen von Betriebssystemen 147
3.1.6 Ziele bei der Entwicklung von Betriebssystemen 150

3.2 Klassische Einrechnersysteme 150
3.2.1 Geräteverwaltung und Dateisysteme 151
3.2.2 Verwaltung des Hauptspeichers 155
3.2.3 Prozesse, Threads und ihre Adressierung 159
3.2.4 Probleme bei der Verwaltung von Betriebsmitteln 162
3.2.5 Kommunikation und Synchronisation von Prozessen 166
3.2.6 Schutz und Sicherheit von Objekten 167

3.3 Verteilte Systeme 169
3.3.1 Verteilte Systeme und Netzwerke 169
3.3.2 Probleme verteilter Systeme (Zeitverwaltung) 170
3.3.3 Remote Procedure Call (RPC) 173
3.3.4 CORBA 175

3.4 Literatur 176


4 Algorithmen 179

4.1 Strukturelemente von Algorithmen 179
4.1.1 Algorithmen und Programme 179
4.1.2 Eigenschaften von Algorithmen 183
4.1.3 Kontrollelemente von Algorithmen 184
4.1.3.1 Folge 186
4.1.3.2 Auswahl 186
4.1.3.3 Wiederholung 191
4.1.4 Strukturierung von Algorithmen - Blöcke 197
4.1.4.1 Parameterübergabe zwischen Blöcken 198
4.1.4.2 Ineinander geschachtelte Blöcke und Gültigkeitsbereiche 201
4.1.4.3 Ablaufsteuerung und Lebensdauer von Daten und Blöcken 205
4.1.4.4 Verlassen von Blöcken - Abbruchanweisung 206
4.1.5 Rekursion 207
4.1.6 Übungen 208

4.2 Methodische Hilfsmittel für den Entwurf von Algorithmen 211
4.2.1 Spezifikation von Algorithmen und Zusicherungen 211
4.2.2 Prinzipien zur Konstruktion von Algorithmen 213
4.2.3 Schrittweise Verfeinerung 215
4.2.4 Zusicherungen und Korrektheit von Algorithmen 219
4.2.5 Konstruktion und Verifikation iterativer Algorithmen 220
4.2.6 Übungen 226

4.3 Datentypen 229
4.3.1 Datentypen, konstante und variable Daten 229
4.3.2 Einfache Datentypen 231
4.3.2.1 Ordinale Datentypen 232
4.3.2.2 Der Datentyp Real 238
4.3.3 Strukturierte Datentypen 240
4.3.3.1 Feld 241
4.3.3.2 Verbund 243
4.3.4 Zeigerdatentypen 244
4.3.4.1 Dynamische Variablen und Zeiger 244
4.3.4.2 Zeiger und dynamische Datenstrukturen 248
4.3.5 Datenabstraktion und Modularisierung 253
4.3.6 Übungen 258

4.4 Literatur 260


5 Programme 261

5.1 Einführung in Sprachen 261
5.1.1 Beschreibung von Sprachen 261
5.1.2 Grammatiken 263

5.2 XML 265
5.2.1 Einführung zu XML 265
5.2.2 Dokumenttyp-Definition 266
5.2.3 Schema Spezifikation 268
5.2.4 Transformationen mit XSL 270

5.3 Programmiersprachen 273
5.3.1 Historie der Programmiersprachen 274
5.3.2 Lexik von Programmiersprachen 275
5.3.3 Syntax von Programmiersprachen 276
5.3.4 Semantik von Programmiersprachen 276
5.3.5 Pragmatik in Programmiersprachen 276
5.3.6 Werkzeuge der Programmentwicklung 276

5.4 Java 278
5.4.1 Historischer Hintergrund 278
5.4.2 Grundprinzipen der Java-Technologie 279
5.4.3 Einführungsbeispiel 280
5.4.4 Lexik von Java 283
5.4.5 Syntax und Semantik von Java 284

5.5 Abschlussbemerkungen 309

5.6 Literatur 309


6 Softwaretechnik 311

6.1 Einführung und Überblick 311

6.2 Beispielprojekt Umfragesystem 311

6.3 Vorgehensmodelle 312
6.3.1 Klassische Vorgehensmodelle 312
6.3.2 Inkrementelle Softwareentwicklung 314
6.3.3 Übungen 315

6.4 Softwareerstellung 315
6.4.1 Machbarkeitsanalyse 315
6.4.2 Grundbegriffe der Objektorientierung 319
6.4.3 Analyse 322
6.4.4 Entwurf 328
6.4.5 Implementierung 330
6.4.6 Übungen 331

6.5 Qualitätssicherung 331
6.5.1 Reviews und formale Inspektionen 332
6.5.2 Test 335
6.5.3 Übungen 340

6.6 Zusammenfassung und Ausblick 340

6.7 Literatur 341


7 Datenbanken 343

7.1 Übersicht 343
7.1.1 Einführende Beispiele 343
7.1.2 Was ist eine Datenbank? 344
7.13 Eigenschaften, Funktion und Architektur von Datenbanksystemen 344
7.1.4 Übungen 346

7.2 Datenbankmodelle 346
7.2.1 Datenstrukturen 346
7.2.2 Relationenmodell 348
7.2.3 Entity-Relationship-Modell (ERM) 350
7.2.4 Beziehungstypen 352
7.2.5 Übungen 354

7.3 Relationale Datenmodellierung 354
7.3.1 Relationale Integritätsregeln 354
7.3.2 Normalisierung 357
7.3.3 Umsetzung des Entity-Relationship-Modells in das relationale Modell 360
7.3.4 Übungen 361

7.4 Die Datenbanksprache SQL 362
7.4.1 Datendefinition 363
7.4.2 Der Abfragebefehl SELECT 365
7.4.3 Änderungsoperationen 372
7.4.4 Übungen 373

7.5 Literatur 373


8 Theorie der Informatik 375

8.1 Formale Sprachen 375
8.1.1 Sprache, Syntax und Semantik 375
8.1.2 Grundbegriffe 376
8.1.3 Generative Grammatik und formale Sprache 379
8.1.4 Reguläre Sprachen 383
8.1.5 Satzanalyse und -verarbeitung 386
8.1.6 Kontextfreie Sprachen 387
8.1.7 Compiler und Interpreter 390
8.1.8 Compiler-Entwicklungswerkzeuge 392

8.2 Berechenbarkeit 393
8.2.1 Der intuitive Algorithmusbegriff 393
8.2.2 Präzisierung des Algorithmusbegriffes 394
8.2.3 Die Turing-Maschine 395
8.2.4 Turingberechenbare Funktionen 397
8.2.5 Die Church'sche These 398
8.2.6 Turingberechenbare und definierbare Funktionen 399
8.2.7 Absolute Unlösbarkeit 401

8.3 Algorithmen und Komplexität 402
8.3.1 Grenzen algorithmischer Lösbarkeit 402
8.3.2 Bit-Komplexität und Effizienz 404
8.3.3 Aufwandsordnung und Aufwandsklassen 404
8.3.4 Analyseformen: best case, average case, worst case 405
8.3.5 Die Klassen P und NP 406
8.3.6 Näherungsverfahren 407

8.4 Literatur 407


Sachwortverzeichnis 409