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 11
1.3.1 Text 11
1.3.2 ASCII-Code 11
1.3.3 ASCII-Erweiterungen 12
1.3.4 Unicode, UCS und UTF-8 13
1.3.5 Zeichenketten 15
1.3.6 Logische Werte und logische Verknüpfungen 15
1.3.7 Programme 16
1.3.8 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 30
1.5.4 Informationsverarbeitung – Datenverarbeitung 31
1.6 Hardware 31
1.6.1 PCs, Workstations, Mainframes, Super-Computer 31
1.6.2 Aufbau von Computersystemen 33
1.6.3 Der Rechner von außen 34
1.6.4 Das Innenleben 34
1.6.5 Ein Motherboard 38
1.6.6 Die Aufgabe der CPU 40
1.6.7 Die Organisation des Hauptspeichers 42
1.6.8 Speichermedien 45
1.6.9 Magnetplatten 46
1.6.10 Festplattenlaufwerke 47
1.6.11 Optische Laufwerke 50
1.6.12 Flash-Speicher 51
1.6.13 Vergleich von Speichermedien 52
1.6.14 Bildschirme 53
1.6.15 Text- und Grafikmodus 54
1.7 Von der Hardware zum Betriebssystem 54
1.7.1 Schnittstellen und Treiber 56
1.7.2 BIOS 58
1.7.3 Die Aufgaben des Betriebssystems 59
1.7.4 Prozess- und Speicherverwaltung 59
1.7.5 Dateiverwaltung 59
1.7.6 DOS, Windows und Linux 62
1.7.7 Bediensysteme 63
1.8 Anwendungsprogramme 66
1.8.1 Textverarbeitung 66
1.8.2 Zeichen und Schriftarten 66
1.8.3 Formatierung 67
1.8.4 Desktop Publishing 69
1.8.5 Textbeschreibungssprachen 69
1.8.6 Tabellenkalkulation: spread sheets 73
1.8.7 Vom Fenster zur Welt zur zweiten Welt 75
2 Grundlagen der Programmierung 77
2.1 Programmiersprachen 78
2.1.1 Vom Programm zur Maschine 78
2.1.2 Virtuelle Maschinen 79
2.1.3 Interpreter 81
2.1.4 Programmieren und Testen 81
2.1.5 Programmierumgebungen 82
2.1.6 Pascal 83
2.1.7 Java 84
2.2 Spezifikationen, Algorithmen, Programme 84
2.2.1 Spezifikationen 85
2.2.2 Algorithmen 87
2.2.3 Algorithmen als Lösung von Spezifikationen 91
2.2.4 Terminierung 92
2.2.5 Elementare Aktionen 93
2.2.6 Zuweisungen 93
2.2.7 Vom Algorithmus zum Programm 94
2.2.8 Ressourcen 96
2.3 Daten und Datenstrukturen 98
2.3.1 Der Begriff der Datenstruktur 98
2.3.2 Boolesche Werte 99
2.3.3 Zahlen 101
2.3.4 Natürliche Zahlen 101
2.3.5 Der Datentyp Integer 103
2.3.6 Rationale Zahlen 105
2.3.7 Reelle Zahlen 105
2.3.8 Mehrsortige Datenstrukturen 106
2.3.9 Zeichen 108
2.3.10 Zusammengesetzte Datentypen – Strings 110
2.3.11 Benutzerdefinierte Datenstrukturen 111
2.3.12 Informationsverarbeitung und Datenverarbeitung 113
2.4 Speicher, Variablen und Ausdrücke 114
2.4.1 Deklarationen 115
2.4.2 Initialisierung 116
2.4.3 Kontexte 116
2.4.4 Ausdrücke, Terme 117
2.4.5 Auswertung von Ausdrücken 120
2.4.6 Funktionsdefinitionen 121
2.4.7 Typfehler 123
2.4.8 Seiteneffekte 123
2.5 Der Kern imperativer Sprachen 124
2.5.1 Zuweisungen 124
2.5.2 Kontrollstrukturen 126
2.5.3 Drei Kontrollstrukturen genügen 126
2.5.4 Die sequentielle Komposition 127
2.5.5 Die Alternativanweisung 128
2.5.6 Die while-Schleife 129
2.5.7 Unterprogramme 130
2.5.8 Lauffähige Programme 132
2.6 Formale Beschreibung von Programmiersprachen 133
2.6.1 Lexikalische Regeln 133
2.6.2 Syntaktische Regeln 134
2.6.3 Semantische Regeln 137
2.7 Erweiterung der Kernsprache 137
2.7.1 Bedingte Anweisung 138
2.7.2 Fallunterscheidung 139
2.7.3 do-Schleife 140
2.7.4 Allgemeinere Schleifenkonstrukte 142
2.7.5 Die for-Schleife 142
2.7.6 Arrays – indizierte Variablen 144
2.8 Rekursive Funktionen und Prozeduren 145
2.8.1 Rekursive Programme 147
2.8.2 Die Türme von Hanoi 148
2.8.3 Spielstrategien als rekursive Prädikate – Backtracking 149
2.8.4 Wechselseitige Rekursion 151
2.8.5 Induktion – Rekursion 151
2.8.6 Allgemeine Rekursion 152
2.8.7 Endrekursion 153
2.8.8 Lineare Rekursion 155
2.8.9 Eine Programmtransformation 157
2.9 Typen, Module, Klassen und Objekte 158
2.9.1 Strukturiertes Programmieren 159
2.9.2 Blockstrukturierung 160
2.9.3 Strukturierung der Daten 160
2.9.4 Objektorientierte Konstruktion neuer Datentypen 165
2.9.5 Modulares Programmieren 167
2.9.6 Schnittstellen – Interfaces 169
2.9.7 Objektorientiertes Programmieren 171
2.9.8 Vererbung 173
2.9.9 Summentypen in objektorientierten Sprachen 175
2.9.10 Datenkapselung 177
2.10 Verifikation 179
2.10.1 Vermeidung von Fehlern 180
2.10.2 Zwischenbehauptungen 180
2.10.3 Partielle Korrektheit 181
2.10.4 Zerlegung durch Zwischenbehauptungen 182
2.10.5 Zuweisungsregel 184
2.10.6 Rückwärtsbeweis 185
2.10.7 if-else-Regel 187
2.10.8 Abschwächungsregel und einarmige Alternative 188
2.10.9 Invarianten und while-Regel 189
2.10.10 Starke und schwache Invarianten 191
2.10.11 Programm-Verifizierer 193
2.10.12 do-Schleife 195
2.10.13 Terminierung 196
2.10.14 Beweis eines Programmschemas 196
2.11 Deklarative Sprachen 197
2.11.1 Prolog 198
2.11.2 Erlang 202
2.12 Zusammenfassung 206
3 Die Programmiersprache Java 207
3.1 Die lexikalischen Elemente von Java 209
3.1.1 Kommentare 209
3.1.2 Bezeichner 210
3.1.3 Schlüsselwörter 211
3.1.4 Literale 211
3.2 Datentypen und Methoden 213
3.2.1 Variablen 213
3.2.2 Referenz-Datentypen 214
3.2.3 Arrays 215
3.2.4 Methoden 216
3.2.5 Klassen und Instanzen 218
3.2.6 Objekte und Referenzen 220
3.2.7 Objekt- und Klassenkomponenten 221
3.2.8 Attribute 222
3.2.9 Überladung 223
3.2.10 Konstruktoren 224
3.2.11 Aufzählungstypen 225
3.3 Ausführbare Java-Programme 226
3.3.1 Java-Dateien – Übersetzungseinheiten 228
3.3.2 Programme 228
3.3.3 Packages 229
3.3.4 Standard-Packages 231
3.4 Ausdrücke und Anweisungen 232
3.4.1 Arithmetische Operationen 232
3.4.2 Vergleichsoperationen 233
3.4.3 Boolesche Operationen 234
3.4.4 Bitweise Operationen 234
3.4.5 Zuweisungsausdrücke 234
3.4.6 Anweisungsausdrücke 236
3.4.7 Sonstige Operationen 236
3.4.8 Präzedenz der Operatoren 237
3.4.9 Einfache Anweisungen 238
3.4.10 Blöcke 239
3.4.11 Alternativ-Anweisungen 239
3.4.12 switch-Anweisung 240
3.4.13 Schleifen 241
3.4.14 Die for-Anweisung 242
3.4.15 break- und continue-Anweisungen 244
3.5 Klassen und Objekte 244
3.5.1 Vererbung 246
3.5.2 Späte Bindung (Late Binding) 251
3.5.3 Finale Komponenten 252
3.5.4 Zugriffsrechte von Feldern und Methoden 252
3.5.5 Attribute von Klassen 253
3.5.6 Abstrakte Klassen 253
3.5.7 Rekursiv definierte Klassen 255
3.5.8 Schnittstellen (Interfaces) 257
3.5.9 Wrapper-Klassen 261
3.5.10 Generische Klassen 261
3.5.11 Typschranken 262
3.5.12 Vererbung generischer Typen 263
3.6 Fehler und Ausnahmen 263
3.6.1 Exceptions in Java 264
3.6.2 Zusicherungen – Assertions 267
3.7 Dateien: Ein- und Ausgabe 271
3.7.1 Dateidialog 272
3.7.2 Schreiben einer Datei 272
3.7.3 Lesen einer Datei 273
3.7.4 Testen von Dateieigenschaften 274
3.8 Threads 275
3.8.1 Thread-Erzeugung 275
3.8.2 Kontrolle der Threads 277
3.8.3 Thread-Synchronisation 277
3.8.4 Deadlock 279
3.9 Grafische Benutzeroberflächen mit Java (AWT) 281
3.9.1 Ein erstes Fenster 281
3.9.2 Ereignisse 282
3.9.3 Beispiel für eine Ereignisbehandlung 284
3.9.4 Buttons 285
3.9.5 Grafikausgabe in Fenstern 286
3.9.6 Maus-Ereignisse 287
3.9.7 Paint 291
3.9.8 Weitere Bedienelemente von Programmen und Fenstern 292
3.10 Ausblick: Java 7 und dann 292
3.10.1 Closures 292
3.10.2 Ausblick 297
4 Algorithmen und Datenstrukturen 299
4.1 Suchalgorithmen 301
4.1.1 Lineare Suche 301
4.1.2 Exkurs: Runden, Logarithmen und Stellenzahl 303
4.1.3 Binäre Suche 304
4.1.4 Lineare Suche vsbinäre Suche 305
4.1.5 Komplexität von Algorithmen 306
4.2 Einfache Sortierverfahren 309
4.2.1 Datensätze und Schlüssel 309
4.2.2 Invarianten und Assertions 312
4.2.3 BubbleSort 314
4.2.4 SelectionSort 316
4.2.5 InsertionSort 318
4.2.6 Laufzeitvergleiche der einfachen Sortieralgorithmen 320
4.2.7 ShellSort und CombSort 321
4.3 Schnelle Sortieralgorithmen 322
4.3.1 Divide and Conquer – teile und herrsche 322
4.3.2 QuickSort 323
4.3.3 Die Partitionierung 324
4.3.4 Korrektheit von QuickSort 326
4.3.5 Komplexität von QuickSort 326
4.3.6 MergeSort 327
4.3.7 Stabilität und RadixSort 329
4.3.8 Optimalität von Sortieralgorithmen 330
4.3.9 Distribution Sort 330
4.3.10 Wieso und wie gut funktioniert DistributionSort? 332
4.3.11 Implementierung von DistributionSort 332
4.3.12 Laufzeit der schnellen Sortieralgorithmen 334
4.3.13 Externes Sortieren 336
4.4 Abstrakte Datenstrukturen 337
4.4.1 Datenstruktur = Menge + Operationen 337
4.4.2 Die axiomatische Methode 338
4.5 Stacks 339
4.5.1 Stackoperationen 339
4.5.2 Implementierung durch ein Array 341
4.5.3 Implementierung durch eine Liste 342
4.5.4 Auswertung von Postfix-Ausdrücken 344
4.5.5 Entrekursivierung 344
4.5.6 Stackpaare 345
4.6 Queues, Puffer, Warteschlangen 347
4.6.1 Implementierung durch ein „zirkuläres“ Array 347
4.6.2 Implementierung durch eine zirkuläre Liste 349
4.6.3 DeQues: Queues mit zwei gleichberechtigten Enden 349
4.6.4 Anwendung von Puffern 350
4.7 Container Datentypen 351
4.7.1 Listen 353
4.7.2 Einfach verkettete Listen 355
4.7.3 Listen als Verallgemeinerung von Stacks und Queues 359
4.7.4 Array-Listen 360
4.7.5 Doppelt verkettete Listen 361
4.7.6 Geordnete Listen und Skip-Listen 361
4.7.7 Adaptive Listen 362
4.8 Bäume 363
4.8.1 Beispiele von Bäumen 364
4.8.2 Binärbäume 365
4.8.3 Implementierung von Binärbäumen 366
4.8.4 Traversierungen 367
4.8.5 Kenngrößen von Binärbäumen 371
4.8.6 Binäre Suchbäume 372
4.8.7 Implementierung von binären Suchbäumen 372
4.8.8 Balancierte Bäume 379
4.8.9 AVL-Bäume 380
4.8.10 2-3-4-Bäume 382
4.8.11 B-Bäume 383
4.8.12 Vollständige Bäume 384
4.8.13 Heaps 386
4.8.14 HeapSort 389
4.8.15 Priority-Queues 390
4.8.16 Bäume mit variabler Anzahl von Teilbäumen 390
4.9 Graphen 391
4.9.1 Wege und Zusammenhang 392
4.9.2 Repräsentationen von Graphen 393
4.9.3 Traversierungen 395
4.9.4 Tiefensuche und Backtracking 396
4.9.5 Breitensuche 397
4.9.6 Transitive Hülle 398
4.9.7 Kürzeste Wege 399
4.9.8 Schwere Probleme für Handlungsreisende 401
4.9.9 Eine Implementierung des TSP 403
4.10 Zeichenketten 407
4.10.1 Array-Implementierung 407
4.10.2 Nullterminierte Strings 407
4.10.3 Stringoperationen 408
4.10.4 Suchen in Zeichenketten 408
4.10.5 Der Boyer-Moore-Algorithmus 409
5 Rechnerarchitektur 411
5.1 Vom Transistor zum Chip 411
5.1.1 Chips 413
5.1.2 Chipherstellung 414
5.1.3 Kleinste Chip-Strukturen 415
5.1.4 Chipfläche und Anzahl der Transistoren 415
5.1.5 Weitere Chip-Parameter 416
5.1.6 Speicherbausteine 416
5.1.7 Logikbausteine 417
5.1.8 Schaltungsentwurf 418
5.2 Boolesche Algebra 419
5.2.1 Serien-parallele Schaltungen 419
5.2.2 Serien-parallele Schaltglieder 420
5.2.3 Schaltoperationen 421
5.2.4 Boolesche Terme 421
5.2.5 Schaltfunktionen 422
5.2.6 Gleichungen 422
5.2.7 Dualität 423
5.2.8 SP-Schaltungen sind monoton 424
5.2.9 Negation 424
5.2.10 Boolesche Terme 425
5.2.11 Dualitätsprinzip 426
5.2.12 Realisierung von Schaltfunktionen 426
5.2.13 Konjunktive Normalform 427
5.2.14 Algebraische Umwandlung in DNF oder KNF 428
5.2.15 Aussagenlogik 429
5.2.16 Mengenalgebra 430
5.3 Digitale Logik 430
5.3.1 Logikgatter 430
5.3.2 Entwurf und Vereinfachung boolescher Schaltungen 433
5.3.3 KV-Diagramme 433
5.3.4 Spezielle Schaltglieder 435
5.3.5 Gatter mit mehreren Ausgängen 436
5.3.6 Codierer und Decodierer 437
5.3.7 Addierer 438
5.3.8 Logik-Gitter 439
5.3.9 Programmierbare Gitterbausteine 441
5.4 CMOS Schaltungen und VLSI Design 442
5.4.1 Logikgatter in CMOS-Technik 443
5.4.2 CMOS-Entwurf 445
5.4.3 Entwurf von CMOS Chips 446
5.4.4 VLSI-Werkzeuge 447
5.5 Sequentielle Logik 448
5.5.1 Gatterlaufzeiten 449
5.5.2 Rückgekoppelte Schaltungen 450
5.5.3 Einfache Anwendungen von Flip-Flops 452
5.5.4 Technische Schwierigkeiten 453
5.5.5 Synchrone und asynchrone Schaltungen 454
5.5.6 Getaktete Flip-Flops 455
5.5.7 Zustandsautomaten 456
5.5.8 Entwurf sequentieller Schaltungen 457
5.5.9 Eine Fußgängerampel 458
5.5.10 Die Konstruktion der Hardwarekomponenten 459
5.5.11 Tristate Puffer 460
5.5.12 Speicherzellen 461
5.5.13 MOS-Implementierung von Speicherzellen 462
5.5.14 Register 464
5.5.15 Die Arithmetisch-Logische Einheit 466
5.6 Von den Schaltgliedern zur CPU 470
5.6.1 Busse 471
5.6.2 Mikrocodegesteuerte Operationen 472
5.6.3 Der Zugang zum Hauptspeicher 475
5.6.4 Der Mikrobefehlsspeicher – das ROM 477
5.6.5 Sprünge 478
5.6.6 Berechnete Sprünge 479
5.6.7 Der Adressrechner 480
5.6.8 Ein Mikroprogramm 481
5.6.9 Maschinenbefehle 482
5.6.10 Der Maschinenspracheinterpretierer 484
5.6.11 Argumente 486
5.7 Assemblerprogrammierung 486
5.7.1 Maschinensprache und Assembler 487
5.7.2 Register der 80x86-Familie 488
5.7.3 Allzweckregister und Spezialregister 489
5.7.4 Flag-Register 490
5.7.5 Arithmetische Flags 491
5.7.6 Größenvergleiche 493
5.7.7 Logische Operationen 494
5.7.8 Sprünge 495
5.7.9 Struktur eines vollständigen Assemblerprogrammes 497
5.7.10 Ein Beispielprogramm 498
5.7.11 Testen von Assemblerprogrammen 499
5.7.12 Speicheradressierung 501
5.7.13 Operationen auf Speicherblöcken 502
5.7.14 Multiplikation und Division 503
5.7.15 Shift-Operationen 504
5.7.16 LOOP-Befehle 505
5.7.17 Der Stack 506
5.7.18 Einfache Unterprogramme 507
5.7.19 Parameterübergabe und Stack 508
5.7.20 Prozeduren und Funktionen 510
5.7.21 Makros 510
5.7.22 Assembler unter DOS 511
5.7.23 Assembler unter Windows 513
5.8 RISC-Architekturen 514
5.8.1 CISC 515
5.8.2 Von CISC zu RISC 516
5.8.3 RISC-Prozessoren 516
5.8.4 Pipelining 518
5.8.5 Superskalare Architekturen 519
5.8.6 Cache-Speicher 519
5.8.7 Leistungsvergleich 519
5.8.8 Konkrete RISC-Architekturen 520
5.9 Architektur der Intel-PC-Mikroprozessorfamilie 523
5.9.1 Adressierung 527
5.9.2 Die Segmentierungseinheit 527
5.9.3 Adressübersetzung 529
5.9.4 Datenstrukturen und Befehle des Pentium 530
5.9.5 MMX-Befehle 530
5.9.6 Betriebsarten des Pentium 530
5.9.7 Ausblick 531
6 Betriebssysteme 533
6.1 Basis-Software 534
6.2 Betriebsarten 536
6.2.1 Teilhaberbetrieb 536
6.2.2 Client-Server-Systeme 536
6.3 Verwaltung der Ressourcen 538
6.3.1 Dateisystem 539
6.3.2 Dateioperationen 540
6.3.3 Prozesse und Threads 540
6.3.4 Vom Programm zum Prozess 541
6.3.5 Prozessverwaltung 542
6.3.6 Prozesskommunikation 544
6.3.7 Kritische Abschnitte – wechselseitiger Ausschluss 545
6.3.8 Semaphore und Monitore 547
6.3.9 Deadlocks 549
6.3.10 Speicherverwaltung 550
6.3.11 Paging 551
6.3.12 Page faults 554
6.4 Das Betriebssystem UNIX 555
6.4.1 Linux 555
6.4.2 Das UNIX-Dateisystem 555
6.4.3 Dateinamen 557
6.4.4 Dateirechte 557
6.4.5 Namen und Pfade 558
6.4.6 Special files 560
6.4.7 Externe Dateisysteme 560
6.4.8 UNIX-Shells 560
6.4.9 UNIX-Kommandos 561
6.4.10 Optionen 562
6.4.11 Datei-Muster 562
6.4.12 Standard-Input/Standard-Output 563
6.4.13 Dateibearbeitung 564
6.4.14 Reguläre Ausdrücke 565
6.5 UNIX-Prozesse 566
6.5.1 Pipes 566
6.5.2 Sind Pipes notwendig? 568
6.5.3 Prozess-Steuerung 570
6.5.4 Multitasking 572
6.5.5 UNIX-Shell-Programmierung 573
6.5.6 Die C-Shell 574
6.5.7 Kommando-Verknüpfungen 574
6.5.8 Variablen 575
6.5.9 Shell-Scripts 576
6.5.10 Ausführung von Shell-Scripts 577
6.5.11 UNIX-Kommandos und Shell-Kommandos 577
6.5.12 UNIX als Mehrbenutzersystem 578
6.5.13 UNIX-Tools 579
6.5.14 Editoren 579
6.5.15 C und C++ 581
6.5.16 Scanner- und Parsergeneratoren 582
6.5.17 Projektbearbeitung 583
6.6 X Window System 584
6.6.1 Window-Manager und Terminal Emulator 585
6.6.2 Grafische Oberflächen 586
6.7 MS-DOS und MS-Windows 587
6.7.1 Dynamic Link Libraries 588
6.7.2 Object Linking and Embedding 588
6.7.3 Windows NT, Windows 2000 589
6.7.4 Windows XP 590
6.7.5 Windows Vista 591
6.8 Alternative PC-Betriebssysteme 592
7 Rechnernetze 595
7.1 Rechner-Verbindungen 596
7.1.1 Signalübertragung 596
7.1.2 Physikalische Verbindung 598
7.1.3 Synchronisation 600
7.1.4 Bitcodierungen 601
7.2 Datenübertragung mit Telefonleitungen 602
7.2.1 ISDN 603
7.2.2 DSL, ADSL und T-DSL 604
7.2.3 ADSL2+ 606
7.3 Protokolle und Netze 606
7.3.1 Das OSI-Modell 607
7.3.2 Netze 609
7.3.3 Netztopologien 610
7.3.4 Netze von Netzen 612
7.3.5 Zugriffsverfahren 615
7.3.6 Wettkampfverfahren: CSMA-CD 615
7.4 Netztechnologien 617
7.4.1 Ethernet 617
7.4.2 FDDI 617
7.4.3 ATM 618
7.4.4 SONET/SDH 619
7.5 Drahtlose Netze 622
7.5.1 Bluetooth 622
7.5.2 WLAN 623
8 Das Internet 629
8.0.1 Bildung von Standards im Internet 630
8.1 Die TCP/IP Protokolle 632
8.1.1 Die Protokolle TCP und UDP 633
8.1.2 Das IP Protokoll 635
8.2 IP-Adressen 637
8.2.1 Adressklassen 638
8.2.2 Adressübersetzung 640
8.3 Das System der Domain-Namen 643
8.3.1 DNS-lookup in Java 646
8.3.2 Programmierung einer TCP-Verbindung 648
8.4 Intranets, Firewalls und virtuelle private Netzwerke 652
8.5 Die Dienste im Internet 654
8.5.1 E-Mail 654
8.5.2 News 659
8.5.3 FTP 660
8.5.4 Secure Shell 661
8.5.5 Gopher 661
8.6 Das World Wide Web 662
8.6.1 HTTP 664
8.6.2 HTML 665
8.6.3 Die Struktur eines HTML-Dokumentes 668
8.6.4 Querverweise: Links 669
8.6.5 Tabellen und Frames 670
8.6.6 Formulare 672
8.6.7 Style Sheets 673
8.6.8 Weitere Möglichkeiten von HTML 674
8.7 Web-Programmierung 674
8.7.1 JavaScript 674
8.7.2 Applets 677
8.7.3 Die Struktur eines Applets 678
8.7.4 Der Lebenszyklus eines Applets 679
8.7.5 Interaktionen 679
8.7.6 PHP 682
8.7.7 XML 684
8.7.8 DOM, Ajax und Web 2.0 693
9 Theoretische Informatik und Compilerbau 695
9.1 Analyse von Programmtexten 695
9.1.1 Lexikalische Analyse 696
9.1.2 Syntaxanalyse 697
9.2 Reguläre Sprachen 698
9.2.1 Reguläre Ausdrücke 699
9.2.2 Automaten und ihre Sprachen 701
9.2.3 Implementierung endlicher Automaten 703
9.2.4 e-Transitionen und nichtdeterministische Automaten 704
9.2.5 Automaten für reguläre Sprachen 704
9.2.6 Von nichtdeterministischen zu deterministischen Automaten 705
9.2.7 Anwendung: flex 706
9.3 Kontextfreie Sprachen 707
9.3.1 Kontextfreie Grammatiken 708
9.3.2 Ableitungen 709
9.3.3 Stackautomaten (Kellerautomaten) 710
9.3.4 Stackautomaten für beliebige kontextfreie Sprachen 712
9.3.5 Nichtdeterministische Algorithmen und Backtracking 712
9.3.6 Inhärent nichtdeterministische Sprachen 715
9.3.7 Ableitungsbaum, Syntaxbaum 715
9.3.8 Abstrakte Syntaxbäume 716
9.4 Grundlagen des Compilerbaus 717
9.4.1 Parsen durch rekursiven Abstieg (recursive descent) 718
9.4.2 LL(1)-Grammatiken 719
9.4.3 Äquivalente Grammatiken 721
9.4.4 Top-down und bottom-up 723
9.4.5 Shift-Reduce Parser 724
9.4.6 Die Arbeitsweise von Shift-Reduce-Parsern 725
9.4.7 Bottom-up Parsing 726
9.4.8 Konflikte 727
9.4.9 Ein nichtdeterministischer Automat mit Stack 727
9.4.10 Übergang zum deterministischen Automaten 730
9.4.11 Präzedenz 732
9.4.12 LR(1) und LALR(1) 733
9.4.13 Parsergeneratoren 734
9.4.14 lex/flex & yacc/bison 736
9.4.15 Grammatische Aktionen 737
9.4.16 Fehlererkennung 739
9.4.17 Synthetisierte Werte 739
9.4.18 Symboltabellen 740
9.4.19 Codeoptimierung 741
9.5 Berechenbarkeit 742
9.5.1 Berechenbare Funktionen 742
9.5.2 Beispiele berechenbarer Funktionen 743
9.5.3 Diagonalisierung 745
9.5.4 Nicht berechenbare Funktionen 746
9.5.5 Algorithmenbegriff und Churchsche These 746
9.5.6 Turingmaschinen 747
9.5.7 Turing-Post Programme 750
9.5.8 Turing-berechenbare Funktionen 751
9.5.9 Registermaschinen 751
9.5.10 GOTO-Programme 752
9.5.11 While-Programme 753
9.5.12 For-Programme (Loop-Programme) 755
9.5.13 Effiziente Algorithmen als For-Programme 755
9.5.14 Elementare (primitive) Rekursion 757
9.5.15 Allgemeine Rekursion (μ-Rekursion) 758
9.5.16 Die Ackermannfunktion 759
9.5.17 Berechenbare Funktionen – Churchsche These 760
9.5.18 Gödelisierung 761
9.5.19 Aufzählbarkeit und Entscheidbarkeit 762
9.5.20 Unlösbare Aufgaben 762
9.5.21 Semantische Probleme sind unentscheidbar 763
9.6 Komplexitätstheorie 765
9.6.1 Rückführung auf ja/nein-Probleme 766
9.6.2 Entscheidungsprobleme und Sprachen 766
9.6.3 Maschinenmodelle und Komplexitätsmaße 767
9.6.4 Sprachen und ihre Komplexität 768
9.6.5 Effiziente parallele Lösungen 768
9.6.6 Nichtdeterminismus 770
9.6.7 Die Klasse NP 771
9.6.8 Reduzierbarkeit 772
9.6.9 Der Satz von Cook 774
9.6.10 NP-Vollständigkeit 776
9.6.11 CLIQUE ist NP-vollständig 776
9.6.12 Praktische Anwendung von SAT-Problemen 777
9.6.13 P = NP ? 780
10 Datenbanksysteme 781
10.1 Datenbanken und Datenbanksysteme 781
10.2 Datenmodelle 783
10.2.1 Entity/Relationship-Modell 783
10.2.2 Das Relationale Datenbankmodell 785
10.2.3 Relationen 786
10.2.4 Die relationale Algebra 787
10.2.5 Erweiterungen des relationalen Datenmodells 788
10.2.6 Abbildung eines E/R-Datenmodells in ein relationales Modell 788
10.3 Die Anfragesprache SQL 789
10.3.1 Datendefinition 789
10.3.2 Einfache Anfragen 791
10.3.3 Gruppierung und Aggregate 792
10.3.4 Verknüpfung verschiedener Relationen 793
10.3.5 Einfügen, Ändern und Löschen von Datensätzen 793
10.3.6 Mehrbenutzerbetrieb 794
10.4 Anwendungsprogrammierung in Java 796
10.4.1 Das SQL-Paket in Java 797
10.4.2 Aufbau einer Verbindung 798
10.4.3 Anfragen 798
10.5 Zusammenfassung 800
11 Grafikprogrammierung 801
11.1 Hardware 801
11.1.1 Auflösungen 802
11.1.2 Farben 802
11.2 Grafikroutinen für Rastergrafik 803
11.2.1 Bresenham Algorithmus 805
11.3 Einfache Programmierbeispiele 806
11.3.1 Mandelbrot- und Julia-Mengen 808
11.3.2 Turtle-Grafik 812
11.3.3 L-Systeme 815
11.3.4 Ausblick 818
11.4 3-D-Grafikprogrammierung 819
11.4.1 Sichtbarkeit 820
11.4.2 Beleuchtungsmodelle 821
11.4.3 Ray-Tracing 823
11.4.4 Photon-Mapping 824
11.4.5 Die Radiosity Methode 825
11.4.6 Ausblick 826
12 Software-Entwicklung 827
12.1 Methoden und Werkzeuge für Projekte 828
12.2 Vorgehensmodelle 830
12.2.1 Code and fix-Verfahren 830
12.2.2 Wasserfall-Modelle 831
12.2.3 Transformations-Modelle 834
12.2.4 Nichtsequentielle Vorgehensmodelle 834
12.2.5 Prototyping und Spiralmodelle 835
12.2.6 Modelle zur inkrementellen Systementwicklung 836
12.2.7 Evolutionäre Entwicklungsmodelle 836
12.2.8 Modelle zur objektorientierten Systementwicklung 837
12.3 Traditionelle Methoden zur Programmentwicklung 839
12.3.1 Strukturierte Programmierung 839
12.3.2 Schrittweise Verfeinerung und Top-down-Entwurf 839
12.3.3 Geheimnisprinzip, Daten-Abstraktion und Modularisierung 840
12.3.4 Strukturierte Analyse- und Entwurfstechniken 841
12.3.5 Entity/Relationship-Modellierung 842
12.3.6 Systematische Test-, Review- und Inspektionsverfahren 843
12.4 Objektorientierte Software-Entwicklungsmethoden 843
12.4.1 Prinzipien der Objektorientierung 843
12.4.2 Objektorientierter Entwurf 844
12.5 Objektorientierte Analyse und Modellierung 845
12.5.1 Standardisierung der objektorientierten Modellierung 846
12.5.2 Die Modellierungssprache UML 846
12.5.3 Software-Architektur 850
12.5.4 Entwurfsmuster und Frameworks 851
12.5.5 Aspekt-orientierte Entwicklung 851
12.5.6 Modell-getriebene Architektur 852
12.6 Projekt-Management 853
12.6.1 Projektinitialisierung und -planung 853
12.6.2 Projektsteuerung und -koordination 854
12.6.3 Projektabschluss und -bericht 855
12.7 Software-Qualitätssicherung 855
12.7.1 Qualitätsnormen und Zertifizierung 857
12.8 Werkzeuge und Programmierumgebungen 859
12.8.1 Klassifizierung von Werkzeugen 859
12.8.2 Werkzeuge zur Analyse und Modellierung 860
12.8.3 Werkzeuge für Spezifikation und Entwurf 860
12.8.4 Programmier-Werkzeuge 861
12.8.5 Test- und Fehlerbehebungs-Werkzeuge 861
12.8.6 Tätigkeitsübergreifende Werkzeuge 863
12.8.7 Entwicklungs-Umgebungen 864
A Literatur 867
A.1 Einführende Bücher 867
A.2 Lehrbücher der Informatik 867
A.3 Programmieren in Java 868
A.4 Algorithmen und Datenstrukturen 869
A.5 Rechnerarchitektur 869
A.6 Betriebssysteme 870
A.7 Rechnernetze 871
A.8 Internet 871
A.9 Theoretische Informatik und Compilerbau 872
A.10 Datenbanken 873
A.11 Grafikprogrammierung 874
A.12 Software-Entwicklung 875
A.13 Mathematischer Hintergrund 876
A.14 Sonstiges 876