lehrerbibliothek.deDatenschutzerklärung
Einführung in die Informatik 6. Auflage
Einführung in die Informatik
6. Auflage




Heinz-Peter Gumm, Manfred Sommer

Oldenbourg Schulbuchverlag
EAN: 9783486273892 (ISBN: 3-486-27389-2)
876 Seiten, kartoniert, 17 x 24cm, 2004

EUR 39,80
alle Angaben ohne Gewähr

Umschlagtext
Dieses Buch bietet eine umfassende und anschauliche Diskussion fundamentaler Konzepte der Informatik. Es führt in Grundlagen, Methoden und Theorie der Programmierung ein und stellt anschließend Java als konkrete objektorientierte Programmiersprache vor. Die grundlegenden Algorithmen und Datenstrukturen der Informatik werden zusammen mit Java-Beispielprogrammen erläutert. Der prinzipielle Aufbau eines Computers vom Transistor bis zur mikroprogrammierten CPU wird ausführlich erklärt. Anhand eines Simulators kann der Leser ihre Funktionsweise experimentell nachvollziehen. Die Diskussion von Maschinen- und Assemblersprache mündet in ein Kapitel über Betriebssysteme, in dem insbesondere auf UNIX eingegangen wird.

Nach einer allgemeinen Diskussion von Techniken und Protokollen zur lokalen und weltweiten Vernetzung von Computern führt ein eigenständiges Kapitel über das Internet von den Grundlagen derTCP/IP-Protokolle bis zur Programmierung von TCP-Verbindung in Java. Internet-Dienste wie E-Mail, FTP und WWW werden ebenso ausführlich behandelt wie HTML, Java-Applets und XML

Neu hinzugekommen ist ein Kapitel über Theoretische Informatik, in dem Automaten, Sprachen, Berechenbarkeit und Komplexitätstheorie im Kontext praktischer Anwendungen, insbesondere mit Anwendungen in Compilerbau, Modellüberprüfung und Grid Computing behandelt werden.

Weiterführende Themen der Informatik, darunter Compilerbau, Grafikprogrammierung, Datenbanksysteme und Software-Entwicklung, werden exemplarisch vorgestellt.

Die Beispielprogramme und weitere Software zu diesem Buch sind im Internet erhältlich.



Heinz Peter Gumm ist Professor am Institut für Theoretische Informatik in Marburg. Studium in Darmstadt und Winnipeg (Canada) von 1970-1975. Promotion und Habilitation an der TU Darmstadt. Es folgten Gastprofessuren in Honolulu (Haiwaii), Darmstadt, Kassel und Riverside (California). 1987-1991 Professor für Informatik an der State University of New York. Seit 1991 Professor für Theoretische Informatik an der Universität Marburg. Forschungsgebiete: Formale Methoden, Allgemeine Algebren und Coalgebren. Prof. Gumm hält Vorlesungen über Praktische Informatik, Technische Informatik, Theoretische Informatik, Beweissysteme, Verifikation, Zustandsbasierte Systeme und Abstrakte Datentypen.



Manfred Sommer ist Professor am Institut für Softwareentwicklung in Marburg. Studium in Göttingen und München von 1964 bis 1969, dann Assistent am ersten Informatik-Institut in Deutschland an der TU München. Es folgten zehn Jahre bei Siemens in München. Seit 1984 erster Informatik-Professor in Marburg. Gründung und Aufbau des Fachgebiets Informatik in Marburg mit einem eigenständigen Hauptfachstudiengang Informatik. Prof. Sommer hält derzeit Vorlesungen über Praktische Informatik, Grafikprogrammierung, Multimediakommunikation, Programmieren in C++ und Compilerbau.
Rezension
Die "Einführung in die Informatik" von Heinz-Peter Gumm und Manfred Sommer liegt hier bereits in der 6. Auflage vor und scheint zu einem Standardwerk geworden zu sein. Es enthält alle wesentlichen Informationen für Schüler und Studenten des Faches. Neu in der aktualisierten Auflage ist das Kapitel zur Theoretischen Informatik, wobei ein besonderer Schwerpunkt auf dem Thema Compilerbau liegt. Überarbeitet wurde auch das Kapitel über Rechnerarchitektur. Für diejenigen, die von den bereits umfassenden Informationen noch nicht genug haben, lohnt sich ein Blick auf die Internetseite www.informatikbuch.de. Dort werden die besprochenen Programme zum Download bereitgestellt.

Arthur Thömmes, lehrerbibliothek.de
Verlagsinfo
Eine anschauliche und umfassende Einführung in die grundlegenden Konzepte der Informatik: - Grundlagen, Methoden und Theorie der Programmierung
- Erklärung des Aufbaus eines Computers vom Transistor bis zur CPU
- Maschinen- und Assemblersprache
- Betriebssysteme
- Netze und ihre Protokolle
- das Internet mit E-Mail, FTP und WWW, HTML und Java-Applets zur Gestaltung eigener Web-Seiten.
Abgerundet wird das Lehrbuch durch Ausblicke auf weiterführende Themen, darunter Compilerbau, Graphikprogrammierung, Datenbanksysteme und Software-Entwicklung.
Inhaltsverzeichnis
1 Einführung 1
1.1 Was ist "Informatik"? 1
1.1.1 Technische Informatik. 1
1.1.2 Praktische Informatik. 2
1.1.3 Theoretische Informatik. 2
1.1.4 Angewandte Informatik. 3
1.2 Information und Daten. 4
1.2.1 Bits. 5
1.2.2 Bitfolgen. 6
1.2.3 Hexziffern. 7
1.2.4 Bytes und Worte. 8
1.2.5 Dateien. 8
1.2.6 Datei- und Speichergrößen. 9
1.2.7 Längen- und Zeiteinheiten. 10
1.3 Informationsdarstellung. 10
1.3.1 Text. 11
1.3.2 ASCII-Code. 11
1.3.3 ASCII-Erweiterungen. 12
1.3.4 Unicode und UCS. 13
1.3.5 UTF-8. 13
1.3.6 Zeichenketten. 15
1.3.7 Logische Werte und logische Verknüpfungen. 15
1.3.8 Programme. 16
1.3.9 Bilder und Musikstücke. 16
1.4 Zahlendarstellungen. 17
1.4.1 Binärdarstellung. 17
1.4.2 Das Oktalsystem und das Hexadezimalsystem. 18
1.4.3 Umwandlung in das Binär-, Oktal- oder Hexadezimalsystem. 19
1.4.4 Arithmetische Operationen. 21
1.4.5 Darstellung ganzer Zahlen. 22
1.4.6 Die Zweierkomplementdarstellung. 23
1.5 Standardformate für ganze Zahlen. 25
1.5.1 Gleitpunktzahlen: Reelle Zahlen. 26
1.5.2 Real-Zahlenbereiche in Programmiersprachen. 29
1.5.3 Daten - Informationen. 29
1.5.4 Informationsverarbeitung - Datenverarbeitung. 30
1.6 Hardware. 31
1.6.1 PCs, Workstations, Mainframes, Super-Computer. 31
1.6.2 Aufbau von Computersystemen. 32
1.6.3 Der Rechner von außen. 33
1.6.4 Das Innenleben. 34
1.6.5 Ein Motherboard. 39
1.6.6 Die Aufgabe der CPU. 41
1.6.7 Die Organisation des Hauptspeichers. 43
1.6.8 Speichermedien. 47
1.6.9 Magnetplatten. 47
1.6.10 Disketten. 49
1.6.11 Festplattenlaufwerke. 49
1.6.12 Optische Laufwerke. 51
1.6.13 Vergleich von Speichermedien. 53
1.6.14 Bildschirme. 53
1.6.15 Text- und Grafikmodus. 55
1.7 Von der Hardware zum Betriebssystem. 55
1.7.1 Schnittstellen und Treiber. 57
1.7.2 BIOS. 59
1.7.3 Die Aufgaben des Betriebssystems. 60
1.7.4 Prozess- und Speicherverwaltung. 60
1.7.5 Dateiverwaltung. 61
1.7.6 DOS, Windows und Linux. 63
1.7.7 Bediensysteme. 64
1.8 Anwendungsprogramme. 67
1.8.1 Textverarbeitung. 67
1.8.2 Zeichen und Schriftarten. 68
1.8.3 Formatierung. 68
1.8.4 Desktop Publishing. 70
1.8.5 Textbeschreibungssprachen. 71
1.8.6 Tabellenkalkulation: spread sheets. 74
1.8.7 Der Rechner als Fenster zur Welt. 76
1.8.8 Wie geht es weiter? 78

2 Grundlagen der Programmierung 79
2.1 Programmiersprachen. 80
2.1.1 Vom Programm zur Maschine. 80
2.1.2 Virtuelle Maschinen. 81
2.1.3 Interpreter. 83
2.1.4 Programmieren und Testen. 83
2.1.5 Programmierumgebungen. 84
2.1.6 BASIC. 85
2.1.7 Pascal. 85
2.1.8 Java. 86
2.1.9 Prolog. 87
2.2 Spezifikationen, Algorithmen, Programme. 89
2.2.1 Spezifikationen. 89
2.2.2 Algorithmen. 91
2.2.3 Algorithmen als Lösung von Spezifikationen. 94
2.2.4 Terminierung. 95
2.2.5 Elementare Aktionen. 96
2.2.6 Elementaraktionen in Programmiersprachen. 96
2.2.7 Vom Algorithmus zum Programm. 97
2.2.8 Ressourcen. 100
2.3 Daten und Datenstrukturen. 101
2.3.1 Der Begriff der Datenstruktur. 101
2.3.2 Die Analogie zwischen Taschenrechner und Datenstruktur. 102
2.3.3 Der Datentyp Boolean. 103
2.3.4 Der Datentyp Natürliche Zahl. 105
2.3.5 Der Datentyp Integer. 106
2.3.6 Rationale Zahlen. 107
2.3.7 Die Datenstruktur Real. 107
2.3.8 Mehrsortige Datenstrukturen. 108
2.3.9 Zeichen. 109
2.3.10 Einfache und zusammengesetzte Typen - Strings. 111
2.3.11 Strings in Turbo-Pascal und in Java. 112
2.3.12 Benutzerdefinierte Datenstrukturen. 112
2.3.13 Informationsverarbeitung und Datenverarbeitung. 114
2.3.14 Variablen und Speicher. 115
2.3.15 Deklarationen. 116
2.3.16 Initialisierung. 117
2.3.17 Typkorrekte Ausdrücke. 117
2.3.18 Auswertung von Ausdrücken. 119
2.3.19 Verkürzte Auswertung. 119
2.3.20 Typfehler. 120
2.3.21 Seiteneffekte. 120
2.4 Der Kern imperativer Sprachen. 121
2.4.1 Zuweisungen. 121
2.4.2 Kontrollstrukturen. 123
2.4.3 Drei Kontrollstrukturen genügen. 123
2.4.4 Die Sequentielle Komposition. 124
2.4.5 Die Alternativanweisung. 126
2.4.6 Die while-Schleife. 127
2.5 Formale Beschreibung von Programmiersprachen. 129
2.5.1 Lexikalische Regeln. 129
2.5.2 Syntaktische Regeln. 130
2.5.3 Semantische Regeln. 133
2.6 Erweiterung der Kernsprache. 133
2.6.1 Bedingte Anweisung. 134
2.6.2 Fallunterscheidung. 136
2.6.3 Repeat-Schleife und do-Schleife. 138
2.6.4 Allgemeinere Schleifenkonstrukte. 139
2.6.5 Die for-Schleife in Pascal. 140
2.6.6 Die for-Schleife in Java. 142
2.7 Unterprogramme. 143
2.7.1 Prozedurale Abstraktion. 144
2.7.2 Funktionale Abstraktion. 145
2.7.3 Funktionale und prozedurale Abstraktion in C und Java. 146
2.7.4 Top-Down-Entwurf. 146
2.7.5 Kommunikation zwischen Haupt- und Unterprogramm. 151
2.7.6 Variablen-Parameter. 151
2.7.7 Prozeduren als Funktionsersatz. 154
2.7.8 Funktionen und Prozeduren in C und Java. 154
2.7.9 Schachtelung von Unterprogrammen. 154
2.7.10 Blockstrukturierung in C und Java. 156
2.8 Rekursive Funktionen und Prozeduren. 157
2.8.1 Rekursive Prozeduren. 158
2.8.2 Die Türme von Hanoi. 159
2.8.3 Spielstrategien als rekursive Prädikate - Backtracking. 161
2.8.4 Wechselseitige Rekursion. 162
2.8.5 Induktion - Rekursion. 163
2.8.6 Allgemeine Rekursion. 164
2.8.7 Endrekursion. 165
2.8.8 Lineare Rekursion. 166
2.8.9 Eine Programmtransformation. 169
2.9 Konstruktion neuer Datentypen. 170
2.9.1 Mengenkonstruktionen. 170
2.9.2 Typdefinitionen. 171
2.9.3 Aufzählungstypen. 172
2.9.4 Teilbereichstypen. 172
2.9.5 Arraytypen. 173
2.9.6 Anwendung: Strings. 174
2.9.7 Aggregation. 175
2.9.8 Disjunkte Vereinigungen. 176
2.9.9 Mengentypen. 178
2.9.10 Dateien und Ströme. 179
2.9.11 Dateiprotokoll. 179
2.9.12 Induktiv definierte Typen. 181
2.9.13 Pointer-Datentypen. 184
2.9.14 Dynamische Datenstrukturen mittels Pointern. 184
2.9.15 Induktive Definitionen in Java. 187
2.10 Verifikation. 187
2.10.1 Vermeidung von Fehlern. 188
2.10.2 Zwischenbehauptungen. 189
2.10.3 Partielle Korrektheit. 190
2.10.4 Zerlegung durch Zwischenbehauptungen. 191
2.10.5 Zuweisungsregel. 192
2.10.6 Rückwärtsbeweis. 194
2.10.7 if-then-else-Regel. 196
2.10.8 Abschwächungsregel und einarmige Alternative. 196
2.10.9 Invarianten und while-Regel. 197
2.10.10 Starke und schwache Invarianten. 200
2.10.11 Programm-Verifizierer. 202
2.10.12 repeat-Schleife. 203
2.10.13 for-Schleife. 204
2.10.14 Terminierung. 205
2.10.15 Beweis eines Programmschemas. 206
2.11 Programmieren im Großen. 207
2.11.1 Modulares Programmieren. 208
2.11.2 Objektorientiertes Programmieren (OOP). 209
2.11.3 Datenkapselung. 210
2.11.4 Vererbung. 211
2.11.5 Zusammenfassung. 213

3 Die Programmiersprache Java 215
3.1 Geschichte von Java. 217
3.2 Die lexikalischen Elemente von Java. 217
3.2.1 Kommentare. 218
3.2.2 Bezeichner. 218
3.2.3 Schlüsselwörter. 218
3.2.4 Literale. 219
3.2.5 Ganzzahlige Literale. 219
3.2.6 Gleitpunkt-Literale. 219
3.2.7 Literale für Zeichen und Zeichenketten. 220
3.3 Datentypen und Methoden. 220
3.3.1 Variablen. 221
3.3.2 Default-Werte. 222
3.3.3 Referenz-Datentypen. 222
3.3.4 Arrays. 222
3.3.5 Methoden. 223
3.3.6 Klassen und Instanzen. 225
3.3.7 Objekte und Referenzen. 226
3.3.8 Objekt- und Klassenkomponenten. 227
3.3.9 Attribute. 228
3.3.10 Overloading. 230
3.3.11 Konstruktoren. 230
3.4 Ausführbare Java-Programme. 232
3.4.1 Java-Dateien-Übersetzungseinheiten. 234
3.4.2 Programme. 234
3.4.3 Packages. 235
3.4.4 Standard-Packages. 237
3.5 Ausdrücke und Anweisungen. 238
3.5.1 Arithmetische Operationen. 238
3.5.2 Vergleichsoperationen. 238
3.5.3 Boolesche Operationen. 239
3.5.4 Bitweise Operationen. 240
3.5.5 Zuweisungsausdrücke. 240
3.5.6 Anweisungsausdrücke. 241
3.5.7 Sonstige Operationen. 242
3.5.8 Präzedenz der Operatoren. 243
3.5.9 Einfache Anweisungen. 244
3.5.10 Blöcke. 244
3.5.11 Alternativ-Anweisungen. 245
3.5.12 switch-Anweisung. 246
3.5.13 Schleifen. 247
3.5.14 Die for-Anweisung. 248
3.5.15 break- und continue-Anweisungen. 250
3.6 Klassen und Objekte. 250
3.6.1 Vererbung. 252
3.6.2 Späte Bindung (Late Binding). 257
3.6.3 Finale Komponenten. 257
3.6.4 Zugriffsrechte von Feldern und Methoden. 258
3.6.5 Attribute von Klassen. 259
3.6.6 Abstrakte Klassen. 259
3.6.7 Rekursiv definierte Klassen. 261
3.6.8 Schnittstellen (Interfaces). 263
3.6.9 Generische Datentypen. 265
3.6.10 Ausnahmen. 267
3.6.11 Threads. 271
3.6.12 Producer-Consumer mit Threads. 274
3.7 Grafische Benutzeroberflächen mit Java (AWT). 277
3.7.1 Ein erstes Fenster. 278
3.7.2 Ereignisse. 279
3.7.3 Beispiel für eine Ereignisbehandlung. 280
3.7.4 Buttons. 282
3.7.5 Grafikausgabe in Fenstern. 283
3.7.6 Maus-Ereignisse. 284
3.7.7 Paint. 287
3.7.8 Weitere Bedienelemente von Programmen und Fenstern. 289
3.8 Dateien: Ein- und Ausgabe. 289
3.8.1 Dateidialog. 289
3.8.2 Schreiben einer Datei. 290
3.8.3 Lesen einer Datei. 291
3.8.4 Testen von Dateieigenschaften. 292
3.8.5 Retrospektive und Vergleich mit Smalltalk. 292

4 Algorithmen und Datenstrukturen 295
4.1 Suchalgorithmen. 297
4.1.1 Lineare Suche. 298
4.1.2 Binäre Suche. 299
4.1.3 Lineare Suche vs. binäre Suche. 301
4.1.4 Komplexität von Algorithmen. 302
4.2 Einfache Sortierverfahren. 304
4.2.1 Datensätze und Schlüssel. 304
4.2.2 BubbleSort. 307
4.2.3 SelectionSort. 310
4.2.4 InsertionSort. 312
4.2.5 Laufzeitvergleiche der einfachen Sortieralgorithmen. 314
4.2.6 ShellSort und CombSort. 315
4.3 Schnelle Sortieralgorithmen. 316
4.3.1 Divide and Conquer - teile und herrsche. 317
4.3.2 QuickSort. 317
4.3.3 Die Partitionierung. 319
4.3.4 Korrektheit von QuickSort. 319
4.3.5 Komplexität von QuickSort. 320
4.3.6 MergeSort. 321
4.3.7 DistributionSort. 323
4.3.8 Wieso und wie gut funktioniert DistributionSort? 325
4.3.9 Einsatz und Implementierung von DistributionSort. 326
4.3.10 Laufzeit der schnellen Sortieralgorithmen. 328
4.3.11 Externes Sortieren. 330
4.4 Abstrakte Datenstrukturen. 331
4.4.1 Datenstruktur = Menge + Operationen. 331
4.4.2 Die axiomatische Methode. 331
4.5 Stacks. 332
4.5.1 Stackoperationen. 333
4.5.2 Implementierung durch ein Array. 335
4.5.3 Implementierung durch eine Liste. 337
4.5.4 Auswertung von Postfix-Ausdrücken. 338
4.5.5 Entrekursivierung. 339
4.5.6 Stackpaare. 340
4.6 Queues, Puffer, Warteschlangen. 342
4.6.1 Implementierung durch ein "zirkuläres" Array. 342
4.6.2 Implementierung durch eine zirkuläre Liste. 344
4.6.3 Anwendung von Puffern. 344
4.7 Listen. 345
4.7.1 Einfach verkettete Listen. 346
4.7.2 Der Listeniterator forEach. 349
4.7.3 Listen als Verallgemeinerung von Stacks und Queues. 350
4.7.4 Doppelt verkettete Listen. 351
4.7.5 Geordnete Listen und Skip-Listen. 351
4.7.6 Adaptive Listen. 352
4.7.7 Generische Listen. 353
4.8 Bäume. 356
4.8.1 Beispiele von Bäumen. 357
4.8.2 Binärbäume. 358
4.8.3 Implementierung von Binärbäumen. 359
4.8.4 Traversierungen. 360
4.8.5 Kenngrößen von Binärbäumen. 363
4.8.6 Binäre Suchbäume. 364
4.8.7 Implementierung von binären Suchbäumen. 365
4.8.8 Balancierte Bäume. 372
4.8.9 AVL-Bäume. 374
4.8.10 2-3-4-Bäume. 376
4.8.11 B-Bäume. 377
4.8.12 Vollständige Bäume. 378
4.8.13 Heaps. 379
4.8.14 HeapSort. 382
4.8.15 Priority-Queues. 383
4.8.16 Bäume mit variabler Anzahl von Teilbäumen. 383
4.9 Graphen. 384
4.9.1 Wege und Zusammenhang. 385
4.9.2 Repräsentationen von Graphen. 386
4.9.3 Traversierungen. 389
4.9.4 Tiefensuche. 390
4.9.5 Breitensuche. 391
4.9.6 Transitive Hülle. 392
4.9.7 Kürzeste Wege. 393
4.9.8 Schwere Probleme für Handlungsreisende. 396
4.9.9 Eine Implementierung des TSP. 397
4.10 Zeichenketten. 401
4.10.1 Array-Implementierung. 401
4.10.2 Nullterminierte Strings. 401
4.10.3 Java-Strings. 402
4.10.4 Grundoperationen. 402
4.10.5 Suchen in Zeichenketten. 403
4.10.6 Der Boyer-Moore-Algorithmus. 404

5 Rechnerarchitektur 407
5.1 Vom Transistor zum Chip. 407
5.1.1 Chips. 408
5.1.2 Chipherstellung. 409
5.1.3 Kleinste Chip-Strukturen. 410
5.1.4 Chipfläche und Anzahl der Transistoren. 411
5.1.5 Weitere Chip-Parameter. 411
5.1.6 Speicherbausteine. 412
5.1.7 Logikbausteine. 412
5.1.8 Schaltungsentwurf. 413
5.2 Boolesche Algebra. 414
5.2.1 Serien-parallele Schaltungen. 414
5.2.2 Serien-parallele Schaltglieder. 416
5.2.3 Boolesche Terme. 417
5.2.4 Schaltfunktionen. 418
5.2.5 Gleichungen. 418
5.2.6 SP-Schaltungen sind monoton. 420
5.2.7 Negation. 420
5.2.8 Boolesche Terme. 421
5.2.9 Dualität. 422
5.2.10 Realisierung von Schaltfunktionen. 423
5.2.11 Konjunktive Normalform. 424
5.2.12 Aussagenlogik. 425
5.2.13 Mengenalgebra. 426
5.3 Digitale Logik. 426
5.3.1 Gatter mit mehreren Ausgängen. 431
5.3.2 Logik-Gitter. 432
5.3.3 Programmierbare Gitterbausteine. 434
5.3.4 Rückgekoppelte Schaltungen. 435
5.3.5 Anwendungen von Flip-Flops. 437
5.3.6 Technische Schwierigkeiten. 438
5.3.7 Die Konstruktion der Hardwarekomponenten. 439
5.3.8 Schalter, Codierer, Decodierer. 439
5.3.9 Speicherzellen. 440
5.3.10 Register. 441
5.3.11 Die Arithmetisch-Logische Einheit. 443
5.4 Von den Schaltgliedern zur CPU. 447
5.4.1 Busse. 448
5.4.2 Mikrocodegesteuerte Operationen. 449
5.4.3 Der Zugang zum Hauptspeicher. 452
5.4.4 Der Mikrobefehlsspeicher - das ROM. 454
5.4.5 Sprünge. 454
5.4.6 Berechnete Sprünge. 455
5.4.7 Der Adressrechner. 457
5.4.8 Ein Mikroprogramm. 458
5.4.9 Maschinenbefehle. 459
5.4.10 Der Maschinenspracheinterpretierer. 461
5.4.11 Argumente. 462
5.5 Assemblerprogrammierung. 463
5.5.1 Maschinensprache und Assembler. 463
5.5.2 Register der 80x86-Familie. 464
5.5.3 Allzweckregister und Spezialregister. 466
5.5.4 Flag-Register. 466
5.5.5 Arithmetische Flags. 468
5.5.6 Größenvergleiche. 469
5.5.7 Logische Operationen. 471
5.5.8 Sprünge. 472
5.5.9 Struktur eines vollständigen Assemblerprogrammes. 473
5.5.10 Ein Beispielprogramm. 474
5.5.11 Testen von Assemblerprogrammen. 476
5.5.12 Speicheradressierung. 477
5.5.13 Operationen auf Speicherblöcken. 478
5.5.14 Multiplikation und Division. 479
5.5.15 Shift-Operationen. 480
5.5.16 LOOP-Befehle. 482
5.5.17 Der Stack. 482
5.5.18 Einfache Unterprogramme. 483
5.5.19 Parameterübergabe und Stack. 485
5.5.20 Prozeduren und Funktionen. 486
5.5.21 Makros. 487
5.5.22 Assembler unter DOS. 488
5.5.23 Assembler unter Windows. 490
5.6 RISC-Architekturen. 491
5.6.1 CISC. 491
5.6.2 Von CISC zu RISC. 492
5.6.3 RISC-Prozessoren. 492
5.6.4 Pipelining. 494
5.6.5 Superskalare Architekturen. 495
5.6.6 Cache-Speicher. 496
5.6.7 Leistungsvergleich. 496
5.6.8 Konkrete RISC-Architekturen. 497
5.7 Die Architektur der Intel-PC-Mikroprozessorfamilie. 499
5.7.1 Adressierung. 503
5.7.2 Die Segmentierungseinheit. 504
5.7.3 Adressübersetzung. 505
5.7.4 Datenstrukturen und Befehle des Pentium. 506
5.7.5 MMX-Befehle. 507
5.7.6 Betriebsarten des Pentium. 507
5.7.7 Ausblick. 507

6 Betriebssysteme 509
6.0.1 Basis-Software. 510
6.1 Betriebsarten. 512
6.1.1 Teilhaberbetrieb. 512
6.1.2 Client-Server-Systeme. 512
6.2 Verwaltung der Ressourcen. 514
6.2.1 Dateisystem. 514
6.2.2 Dateioperationen. 516
6.2.3 Prozesse. 516
6.2.4 Bestandteile eines Prozesses. 517
6.2.5 Threads. 518
6.2.6 Prozessverwaltung. 518
6.2.7 Prozesskommunikation. 520
6.2.8 Kritische Abschnitte - wechselseitiger Ausschluss. 521
6.2.9 Semaphore und Monitore. 523
6.2.10 Deadlocks. 524
6.2.11 Speicherverwaltung. 525
6.3 Das Betriebssystem UNIX. 529
6.3.1 Linux. 530
6.3.2 Das UNIX-Dateisystem. 530
6.3.3 Dateinamen. 532
6.3.4 Dateirechte. 532
6.3.5 Pfade. 532
6.3.6 Special files. 534
6.3.7 Externe Dateisysteme. 534
6.3.8 UNIX-Shells. 534
6.3.9 UNIX-Kommandos. 535
6.3.10 Optionen. 536
6.3.11 Datei-Muster. 537
6.3.12 Standard-Input/Standard-Output. 538
6.3.13 Dateibearbeitung. 538
6.3.14 Reguläre Ausdrücke. 540
6.4 UNIX-Prozesse. 541
6.4.1 Pipes. 541
6.4.2 Sind Pipes notwendig? 542
6.4.3 Prozess-Steuerung. 544
6.4.4 Multitasking. 546
6.4.5 UNIX-Shell-Programmierung. 547
6.4.6 Die C-Shell. 547
6.4.7 Kommando-Verknüpfungen. 548
6.4.8 Variablen. 548
6.4.9 Shell-Scripts. 550
6.4.10 Ausführung von Shell-Scripts. 550
6.4.11 UNIX-Kommandos und Shell-Kommandos. 551
6.4.12 UNIX als Mehrbenutzersystem. 552
6.4.13 Verbindung zu anderen Rechnern. 553
6.4.14 Weltweiter Rechnerzugang. 553
6.4.15 UNIX-Tools. 554
6.4.16 Editoren. 555
6.4.17 C und C++. 556
6.4.18 Scanner- und Parsergeneratoren. 557
6.4.19 Projektbearbeitung. 559
6.5 X Window System. 559
6.5.1 Window-Manager und Terminal Emulator. 561
6.5.2 Grafische Oberflächen. 561
6.6 MS-DOS und MS-Windows. 562
6.6.1 Dynamic Link Libraries. 563
6.6.2 Object Linking and Embedding. 564
6.6.3 Windows NT, Windows 2000 und Windows XP. 564
6.6.4 Windows XP. 566
6.7 Alternative PC-Betriebssysteme. 566

7 Rechnernetze 569
7.1 Rechner-Verbindungen. 570
7.1.1 Signalübertragung. 570
7.1.2 Physikalische Verbindung. 572
7.1.3 Synchronisation. 574
7.1.4 Bitcodierungen. 575
7.2 Datenübertragung mit Telefonleitungen. 576
7.2.1 ISDN. 577
7.2.2 DSL, ADSL und T-DSL. 578
7.3 Protokolle und Netze. 580
7.3.1 Das OSI-Modell. 580
7.3.2 Netze. 583
7.3.3 Netztopologien. 584
7.3.4 Netze von Netzen. 586
7.3.5 Zugriffsverfahren. 589
7.3.6 Wettkampfverfahren: CSMA-CD. 589
7.4 Netztechnologien. 591
7.4.1 Ethernet. 591
7.4.2 FDDI. 592
7.4.3 ATM. 592
7.4.4 SONET/SDH. 594
7.5 Drahtlose Netze. 595
7.5.1 Bluetooth. 596
7.5.2 WLAN 597

8 Das Internet 605
8.0.1 Bildung von Standards im Internet. 606
8.1 Die TCP/IP Protokolle. 608
8.1.1 Die Protokolle TCP und UDP. 609
8.1.2 Das IP Protokoll. 611
8.2 IP-Adressen. 613
8.2.1 Adressklassen. 614
8.2.2 Adressübersetzung. 616
8.3 Das System der Domain-Namen. 620
8.3.1 DNS-lookup in Java. 622
8.3.2 Programmierung einer TCP Verbindungen. 624
8.4 Intranets, Firewalls und virtuelle private Netzwerke. 628
8.5 Die Dienste im Internet. 630
8.5.1 E-Mail. 630
8.5.2 News. 635
8.5.3 FTP. 636
8.5.4 Telnet. 637
8.5.5 Gopher. 637
8.6 Das World Wide Web. 638
8.6.1 HTTP. 640
8.6.2 HTML. 641
8.6.3 Die Struktur eines HTML-Dokumentes. 644
8.6.4 Querverweise: Links. 645
8.6.5 Tabellen und Frames. 646
8.6.6 Formulare. 647
8.6.7 Style Sheets. 648
8.6.8 Weitere Möglichkeiten von HTML. 649
8.7 Web-Programmierung. 649
8.7.1 JavaScript. 650
8.7.2 Applets. 652
8.7.3 Die Struktur eines Applets. 653
8.7.4 Der Lebenszyklus eines Applets. 654
8.7.5 Interaktionen. 655
8.7.6 PHP. 657
8.7.7 XML. 660

9 Theoretische Informatik und Compilerbau 665
9.1 Analyse von Programmtexten. 665
9.1.1 Lexikalische Analyse. 666
9.1.2 Syntaxanalyse. 667
9.2 Reguläre Sprachen. 668
9.2.1 Reguläre Ausdrücke. 669
9.2.2 Automaten und ihre Sprachen. 671
9.2.3 Implementierung endlicher Automaten. 673
9.2.4 ε-Transitionen und nichtdeterministische Automaten. 674
9.2.5 Automaten für reguläre Sprachen. 674
9.2.6 Von nichtdeterministischen zu deterministischen Automaten. 675
9.2.7 Anwendung: flex. 676
9.3 Kontextfreie Sprachen. 677
9.3.1 Kontextfreie Grammatiken. 678
9.3.2 Ableitungen. 679
9.3.3 Stackmaschinen (Kellerautomaten). 680
9.3.4 Stackmaschinen für beliebige kontextfreie Sprachen. 681
9.3.5 Nichtdeterministische Algorithmen und Backtracking. 682
9.3.6 Inhärent nichtdeterministische Sprachen. 684
9.3.7 Ableitungsbaum, Syntaxbaum. 685
9.3.8 Abstrakte Syntaxbäume. 686
9.4 Grundlagen des Compilerbaus. 687
9.4.1 Parsen durch rekursiven Abstieg (recursive descent). 687
9.4.2 LL(1)-Grammatiken. 689
9.4.3 Äquivalente Grammatiken. 691
9.4.4 Top-down und bottom-up. 692
9.4.5 Shift-Reduce Parser. 693
9.4.6 Die Arbeitsweise von Shift-Reduce-Parsern. 694
9.4.7 Bottom-up Parsing. 695
9.4.8 Konflikte. 696
9.4.9 Ein nichtdeterministischer Automat mit Stack. 697
9.4.10 Übergang zum deterministischen Automaten. 699
9.4.11 Präzedenz. 702
9.4.12 LR(1) und LALR(1). 703
9.4.13 Parsergeneratoren. 704
9.4.14 lex/flex & yacc/bison. 705
9.4.15 Grammatische Aktionen. 707
9.4.16 Fehlererkennung. 709
9.4.17 Synthetisierte Werte. 709
9.4.18 Symboltabellen. 710
9.4.19 Codeoptimierung. 710
9.5 Berechenbarkeit. 711
9.5.1 Berechenbare Funktionen. 712
9.5.2 Beispiele berechenbarer Funktionen. 713
9.5.3 Diagonalisierung. 715
9.5.4 Nicht berechenbare Funktionen. 716
9.5.5 Algorithmenbegriff und Churchsche These. 716
9.5.6 Turingmaschinen. 717
9.5.7 Turing-Post Programme. 719
9.5.8 Turing-berechenbare Funktionen. 720
9.5.9 Registermaschinen. 721
9.5.10 GOTO-Programme. 722
9.5.11 While-Programme. 723
9.5.12 For-Programme (Loop-Programme). 725
9.5.13 Effiziente Algorithmen als For-Programme. 725
9.5.14 Elementare (primitive) Rekursion. 726
9.5.15 Allgemeine Rekursion (µ-Rekursion). 728
9.5.16 Die Ackermannfunktion. 729
9.5.17 Berechenbare Funktionen - Churchsche These. 730
9.5.18 Gödelisierung. 730
9.5.19 Aufzählbarkeit und Entscheidbarkeit. 731
9.5.20 Unlösbare Aufgaben. 732
9.5.21 Semantische Probleme sind unentscheidbar. 733
9.6 Komplexitätstheorie. 734
9.6.1 Rückführung auf ja/nein-Probleme. 735
9.6.2 Entscheidungsprobleme und Sprachen. 736
9.6.3 Maschinenmodelle und Komplexitätsmaße. 736
9.6.4 Sprachen und ihre Komplexität. 737
9.6.5 Effiziente parallele Lösungen. 738
9.6.6 Nichtdeterminismus. 739
9.6.7 Die Klasse NP. 740
9.6.8 Reduzierbarkeit. 741
9.6.9 Der Satz von Cook. 743
9.6.10 NP-Vollständigkeit. 745
9.6.11 CLIQUE ist NP-vollständig. 746
9.6.12 Praktische Anwendung von SAT-Problemen. 747
9.6.13 P = NP ? 749

10 Datenbanksysteme 751
10.1 Datenbanken und Datenbanksysteme. 751
10.2 Datenmodelle. 753
10.2.1 Entity/Relationship-Modell. 753
10.2.2 Das Relationale Datenbankmodell. 755
10.2.3 Relationen. 756
10.2.4 Die relationale Algebra. 757
10.2.5 Erweiterungen des relationalen Datenmodells. 757
10.2.6 Abbildung eines E/R-Datenmodells in ein relationales Modell. 758
10.3 Die Anfragesprache SQL. 759
10.3.1 Datendefinition. 759
10.3.2 Einfache Anfragen. 761
10.3.3 Gruppierung und Aggregate. 762
10.3.4 Verknüpfung verschiedener Relationen. 763
10.3.5 Einfügen, Ändern und Löschen von Datensätzen. 763
10.3.6 Mehrbenutzerbetrieb. 764
10.4 Anwendungsprogrammierung in Java. 766
10.4.1 Das SQL-Paket in Java. 767
10.4.2 Aufbau einer Verbindung. 767
10.4.3 Anfragen. 768
10.4.4 Zusammenfassung. 770

11 Grafikprogrammierung 771
11.1 Hardware. 771
11.1.1 Auflösungen. 772
11.1.2 Farben. 772
11.2 Grafikroutinen für Rastergrafik. 773
11.2.1 Bresenham Algorithmus. 775
11.3 Einfache Programmierbeispiele. 776
11.3.1 Mandelbrot- und Julia-Mengen. 778
11.3.2 Turtle-Grafik. 782
11.3.3 L-Systeme. 785
11.3.4 Ausblick. 788
11.4 3-D-Grafikprogrammierung. 789
11.4.1 Sichtbarkeit. 790
11.4.2 Beleuchtungsmodelle. 791
11.4.3 Ray-Tracing. 793
11.4.4 Die Radiosity Methode. 794
11.4.5 Ausblick. 795

12 Software-Entwicklung 797
12.1 Methoden und Werkzeuge für Projekte. 798
12.2 Vorgehensmodelle. 800
12.2.1 Code and fix-Verfahren. 800
12.2.2 Wasserfall-Modelle. 801
12.2.3 Transformations-Modelle. 804
12.2.4 Nichtsequentielle Vorgehensmodelle. 804
12.2.5 Prototyping und Spiralmodelle. 805
12.2.6 Modelle zur inkrementellen Systementwicklung. 806
12.2.7 Evolutionäre Entwicklungsmodelle. 806
12.2.8 Modelle zur objektorientierten Systementwicklung. 807
12.3 Traditionelle Methoden zur Programmentwicklung. 809
12.3.1 Strukturierte Programmierung. 809
12.3.2 Schrittweise Verfeinerung und Top-down-Entwurf. 809
12.4 Daten- und Funktionsorientierte Software-Entwicklungsmethoden. 810
12.4.1 Geheimnisprinzip, Daten-Abstraktion und Modularisierung. 811
12.4.2 Strukturierte Analyse- und Entwurfstechniken. 812
12.4.3 Entity/Relationship-Modellierung. 813
12.4.4 Systematische Test-, Review- und Inspektionsverfahren. 813
12.5 Objektorientierte Software-Entwicklungsmethoden. 814
12.5.1 Prinzipien der Objektorientierung. 814
12.5.2 Objektorientierter Entwurf. 815
12.6 Objektorientierte Analyse. 816
12.6.1 Standardisierung der objektorientierten Modellierung. 816
12.6.2 Die Modellierungssprache UML. 817
12.6.3 Software-Architekturen, Muster und Programmgerüste. 821
12.7 Projekt-Management. 822
12.7.1 Projektinitialisierung und -planung. 823
12.7.2 Projektsteuerung und -koordination. 823
12.7.3 Projektabschluss und -bericht. 824
12.8 Software-Qualitätssicherung. 824
12.8.1 Qualitätsnormen und Zertifizierung. 827
12.9 Werkzeuge und Programmierumgebungen. 828
12.9.1 Klassifizierung von Werkzeugen. 828
12.9.2 Werkzeuge zur Analyse und Modellierung. 830
12.9.3 Werkzeuge für Spezifikation und Entwurf. 830
12.9.4 Programmier-Werkzeuge. 831
12.9.5 Test- und Fehlerbehebungs-Werkzeuge. 832
12.9.6 Weitere Werkzeuge zur Qualitätssicherung. 833
12.9.7 Tätigkeitsübergreifende Werkzeuge. 833
12.9.8 Entwicklungs-Umgebungen. 835

A Literatur 837
A.1 Einführende Bücher. 837
A.2 Lehrbücher der Informatik. 837
A.3 Programmieren in Pascal. 838
A.4 Programmieren in Java. 839
A.5 Algorithmen und Datenstrukturen. 840
A.6 Rechnerarchitektur. 840
A.7 Betriebssysteme. 841
A.8 Rechnernetze. 842
A.9 Internet. 842
A.10 Theoretische Informatik und Compilerbau. 844
A.11 Datenbanken. 845
A.12 Grafikprogrammierung. 846
A.13 Software-Entwicklung. 847
A.14 Mathematischer Hintergrund. 849
A.15 Sonstiges. 850

Stichwortverzeichnis 851