1. Ziele der Vorlesung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1. Organisation der Vorlesung . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Teilnahme an den Übungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Tutorien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Anmeldetermine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5. Anmeldeverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6. Wahl des Passworts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7. Schlechte Passwörter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.8. Gute Passwörter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.9. Umgang mit Passwörtern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.10. Wahl des Benutzernamens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.11. Zugang zu unseren Rechnern . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.12. Benutzungsrichtlinien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.13. Plattenplatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.14. Benutzung unserer Drucker . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.15. E-Mails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.16. Exotik unserer Rechner-Infrastruktur . . . . . . . . . . . . . . . . . 18
1.17. Warum so eine Umgebung? . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.18. Zum Inhalt der Vorlesung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.19. Allgemeine Informatik II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.20. Sie sind willkommen! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2. Einführung in die UNIX-Umgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1. Einfache Abstraktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2. Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3. Ablauf einer Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4. Eingabe unter UNIX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5. Kommandozeile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6. Fehler in der Kommandozeile . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.7. Manual-Seiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.8. Aufbau einer Manual-Seite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.9. Betrachten einer Manual-Seite . . . . . . . . . . . . . . . . . . . . . . . . 32
2.10. Der Namensraum unter UNIX . . . . . . . . . . . . . . . . . . . . . . . . 33
2.11. Der Namensraum als Baum . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.12. Das Arbeitsverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.13. Absolute und relative Pfade . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.14. ls-Kommando . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.15. Was ist in einer Datei enthalten? . . . . . . . . . . . . . . . . . . . . . 38
2.16. Was ist ein Text? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.17. Text, der durch Text erklärt wird . . . . . . . . . . . . . . . . . . . . . 40

2.18. Ein- und Ausgabe-Umlenkung in der Shell . . . . . . . . . . . . 41
2.19. Verknüpfung von Kommandos . . . . . . . . . . . . . . . . . . . . . . . . 44
2.20. Wichtige Kommandos zur Verwaltung von Dateien …. 45
2.21. Konventionen auf der Kommandozeile . . . . . . . . . . . . . . . . 46
2.22. Was ist ein Editor? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.23. Warum nicht WYSIWYG? . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.24. Wie sieht es mit Programmtexten aus? . . . . . . . . . . . . . . . 49
2.25. Woher kommt der vi? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.26. Varianten des vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.27. Erste Schritte mit dem vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.28. Aufbau des Bildschirms beim vi . . . . . . . . . . . . . . . . . . . . . . 53
2.29. Hilfe, wie komme ich hier wieder raus? . . . . . . . . . . . . . . . . 54
3. Rechenmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.1. Modelle für Rechenmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2. John-von-Neumann-Maschine . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3. Ausführungszyklus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4. Rechner-Architekturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5. Redcode-Architektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.6. Redcode-Befehle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.7. Adressierungs-Modi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.8. Core Wars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.9. Beispiel in Redcode: Dwarf . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.10. Repräsentierungen für Programme . . . . . . . . . . . . . . . . . . . . 68
4. Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.1. Maschinennahe Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2. Höhere Programmiersprachen . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3. Einfachheit vs Kompliziertheit . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4. Vom Programmtext zur Ausführung . . . . . . . . . . . . . . . . . . 73
5. Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1. Ein erstes Beispiel mit Oberon . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2. Übersetzen von Oberon-Programmen . . . . . . . . . . . . . . . . . 76
5.3. Übersetzen mit Hilfe eines Makefile . . . . . . . . . . . . . . . . . . . 77
5.4. Übersetzen mit dem neuen System . . . . . . . . . . . . . . . . . . . . 78
5.5. Struktur eines Programmtextes . . . . . . . . . . . . . . . . . . . . . . . 79
5.6. Lexikalische Symbole in Oberon . . . . . . . . . . . . . . . . . . . . . . 80
5.7. Syntaxfehler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.8. Lesbarkeit von Programmtexten . . . . . . . . . . . . . . . . . . . . . . 82

5.9. Rahmen eines Moduls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.10. Dokumentation zu Modulen . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6. Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.1. Produktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.2. Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.3. Sätze und Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.4. Beispiel: Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.5. Beispiel: Einfache Ausdrücke . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.6. Backus-Naur-Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.7. Erweiterte Backus-Naur-Form . . . . . . . . . . . . . . . . . . . . . . . . 95
6.8. Die Grammatik von EBNF . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.9. Die Grammatik von Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.10. Ableitungsbeispiel für Oberon . . . . . . . . . . . . . . . . . . . . . . . . 105
7. Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.1. Beispiel: Summe zweier Zahlen . . . . . . . . . . . . . . . . . . . . . . . . 108
7.2. Variablendeklarationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.3. Einlesen von Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.4. Zuweisung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8. Kontrollstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.1. Bedingte Verzweigungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.2. WHILE-Schleife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
8.3. Beispiel: Hilo-Spiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
9. Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
9.1. Beispiel: Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9.2. Graphische Darstellung endlicher Automaten . . . . . . . . . 119
9.3. Automaten in Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
9.4. Datentyp CHAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9.5. Die CASE-Anweisung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
9.6. Reguläre Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
9.7. Beispiel: Gleitkommazahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.8. Nicht-reguläre Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
9.9. LOOP-Anweisung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.10. Einlese-Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
9.11. Alternative Einlese-Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . 131
9.12. Einlesen mit zusätzlichen Tests . . . . . . . . . . . . . . . . . . . . . . . 132
9.13. Erst einlesen, dann testen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.14. Endliche Automaten mit Textausgabe . . . . . . . . . . . . . . . . 134

9.15. Beispiel für eine Moore-Maschine . . . . . . . . . . . . . . . . . . . . . 135
9.16. Rahmen für den Tennis-Automaten . . . . . . . . . . . . . . . . . . . 136
9.17. Konstantendefinitionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.18. Ausgabe des Zustands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.19. Einlese-Schleife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.20. Übergang zum Folgezustand . . . . . . . . . . . . . . . . . . . . . . . . . . 140
10. Formale Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
10.1. Grammatik einer Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . 142
10.2. Substitutionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
10.3. Modus Ponens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
10.4. Hilbert-Axiome der Aussagenlogik . . . . . . . . . . . . . . . . . . . . 145
10.5. Beispiel für eine Ableitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
10.6. Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10.7. Wahrheitstafeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
10.8. Äquivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.9. Binäre Boolean-Operatoren I . . . . . . . . . . . . . . . . . . . . . . . . . 150
10.10. Binäre Boolean-Operatoren II . . . . . . . . . . . . . . . . . . . . . . . . 151
10.11. Regeln zu den Boolean-Operatoren . . . . . . . . . . . . . . . . . . . 152
10.12. BOOLEAN-Operatoren in Oberon . . . . . . . . . . . . . . . . . . 153
10.13. Kurzschlußbewertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
10.14. Eine kleine Logelei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
10.15. Logelei in Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
10.16. Erzeugung aller Möglichkeiten . . . . . . . . . . . . . . . . . . . . . . . . 158
10.17. Erzeugung aller Möglichkeiten in Oberon . . . . . . . . . . . . . 159
10.18. Iteration bei BOOLEAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
11. Typen in Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
11.1. Numerische Datentypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
11.2. Gleitkommazahlen nach IEEE 754-1985 . . . . . . . . . . . . . . . 163
11.3. Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
11.4. Zufälliges Mischen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
11.5. Datenstrukturen für das Mischen . . . . . . . . . . . . . . . . . . . . . 169
11.6. Einlesen der zu mischenden Werte . . . . . . . . . . . . . . . . . . . . 170
11.7. Der Misch-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
11.8. Ausgabe des Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
11.9. Zählen von Buchstaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
11.10. Typ für kleine Mengen: SET . . . . . . . . . . . . . . . . . . . . . . . . . . 176
11.11. Transitive Hüllen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
11.12. Datenstruktur für die Relation . . . . . . . . . . . . . . . . . . . . . . . . 178

11.13. Einlesen der Knotenpaare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
11.14. Berechnen der transitiven Hülle . . . . . . . . . . . . . . . . . . . . . . . 181
11.15. Ausgabe der transitiven Hüllen . . . . . . . . . . . . . . . . . . . . . . . 183
11.16. Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
11.17. Ein kleines Adreßbuch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
11.18. Zeichenketten in Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
11.19. Einlesen von Kommandos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.20. Einfügen neuer Einträge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
11.21. Ausgabe aller Einträge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
11.22. Suche nach einem Namen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
11.23. Löschen von Einträgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
12. Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
12.1. Prozeduren in Oberon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
12.2. Syntax von Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
12.3. Aufruf von Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
12.4. Arten formaler Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
12.5. Werte-Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
12.6. Referenz-Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
12.7. Werte-Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
12.8. Referenz-Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
12.9. Welche Parameter für was? . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
12.10. Funktions-Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
12.11. Lokale Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
12.12. Globale Variablen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
12.13. Einlese-Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
12.14. Kombination von Einlese-Prozeduren . . . . . . . . . . . . . . . . . 209
12.15. Übersicht durch kleine Zugriffs-Operationen . . . . . . . . . . . 210
12.16. Ausgabe-Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
12.17. Kontroll-Prozedur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
13. Ein- und Ausgabe-Verbindungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
13.1. Einfaches Modell einer Datei . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.2. Unidirektionaler Kommunikationskanal . . . . . . . . . . . . . . . 216
13.3. Bidirektionaler Kommunikationskanal . . . . . . . . . . . . . . . . . 217
13.4. Das Modul Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
13.5. Die Pufferung des Moduls Streams . . . . . . . . . . . . . . . . . . 219
13.6. Eröffnen einer Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13.7. Zulässige Modi für UnixFiles.Mode . . . . . . . . . . . . . . . . . 221
13.8. Lese- und Schreib-Operationen . . . . . . . . . . . . . . . . . . . . . . . . 222

13.9. Status einer Ein- und Ausgabe-Verbindung . . . . . . . . . . . 223
13.10. Schließen eines Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
13.11. Positionierung in einer Datei . . . . . . . . . . . . . . . . . . . . . . . . . . 225
13.12. Zufällige Auswahl eines Spruches . . . . . . . . . . . . . . . . . . . . . 226
13.13. Datenstruktur von FortuneCookie . . . . . . . . . . . . . . . . . . 227
13.14. Durchgang durch die Datei . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
13.15. Lokale Prozeduren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
13.16. Positionierung in einer Datei . . . . . . . . . . . . . . . . . . . . . . . . . . 230
13.17. Hauptteil der Spruchauswahl . . . . . . . . . . . . . . . . . . . . . . . . . 231
14. Argumente aus der Kommandozeile . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
14.1. Aneinanderhängen von Dateien . . . . . . . . . . . . . . . . . . . . . . . 233
14.2. Rahmen des Kopierprogramms . . . . . . . . . . . . . . . . . . . . . . . . 234
14.3. Kopierprozedur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
14.4. Abarbeiten der Kommandozeile . . . . . . . . . . . . . . . . . . . . . . . 236
14.5. Fehlerbehandlung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
14.6. Geschwindigkeitsvergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
14.7. Schnelleres Kopieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
14.8. Verarbeiten von Optionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
14.9. Optionen mit Parametern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
14.10. Einlesen von Feldern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
15. Sortierverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
15.1. Verfahrensvarianten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
15.2. Kriterien zur Verfahrensauswahl . . . . . . . . . . . . . . . . . . . . . . 251
15.3. Sortieren durch Zählen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
15.4. Einfacher Rahmen eines Sortierprogramms . . . . . . . . . . . . 253
15.5. Sortierprozedur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
15.6. O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
15.7. Aufwand des Sortierens durch Zählen . . . . . . . . . . . . . . . . . 256
15.8. Sortieren durch Zählen von Häufigkeiten . . . . . . . . . . . . . . 257
15.9. Aufwand des Sortierens durch Zählen von Häufigkeiten 258
15.10. Sortierprozedur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
15.11. Sortieren durch Austauschen . . . . . . . . . . . . . . . . . . . . . . . . . . 260
15.12. Aufwand des Bubble-Sort-Algorithmus . . . . . . . . . . . . . . . . 261
15.13. Sortierprozedur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
15.14. Abhängigkeiten der Sortierprozedur . . . . . . . . . . . . . . . . . . . 263
15.15. Prozedurtypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
15.16. Typunabhängige Sortierprozedur . . . . . . . . . . . . . . . . . . . . . . 266
15.17. Nachteil von Prozedurtypen . . . . . . . . . . . . . . . . . . . . . . . . . . 267
15.18. Vorteil von Prozedurtypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

15.19. Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
15.20. Partitionierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
15.21. Nachsortierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
15.22. Partitionierungsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
15.23. Flut von zu sortierenden Partitionen . . . . . . . . . . . . . . . . . . 274
15.24. Stapel mit Aufträgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
15.25. Quick-Sort Sortierprozedur . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
15.26. Aufwand des Quicksort-Verfahrens . . . . . . . . . . . . . . . . . . . . 278
16. Testen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
16.1. Test-Prinzipien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
16.2. Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
16.3. Was wird getestet? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
16.4. Test-Strategien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
16.5. Techniken zur Generierung von Testfällen . . . . . . . . . . . . . 285
16.6. Beispiel: Analyse von Dreiecken . . . . . . . . . . . . . . . . . . . . . . . 286
16.7. Äquivalenz-Klassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
16.8. Testfälle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
16.9. Ein Test-Kandidat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
16.10. Die Test-Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
16.11. Ein Testwerkzeug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
16.12. Ein Testlauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
16.13. Mangelbehebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
16.14. Wann werden die Testfälle entwickelt? . . . . . . . . . . . . . . . . 301
16.15. White-Box-Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
16.16. Beispiel für White-Box-Tests . . . . . . . . . . . . . . . . . . . . . . . . . . 303
16.17. White-Box-Testfälle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
17. Koroutinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
17.1. Grund-Operationen für Koroutinen . . . . . . . . . . . . . . . . . . . 307
17.2. Ein erstes Beispiel mit Koroutinen . . . . . . . . . . . . . . . . . . . . 308
17.3. Vor- und Nachteile soweit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
17.4. Interne Pipelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
17.5. Einfügen eines Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
17.6. Trennung von Filtern und Verarbeitung . . . . . . . . . . . . . . . 314
17.7. Kombination von Filtern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
17.8. Mehr Komfort bei interaktiven Programmen . . . . . . . . . . 316
17.9. Virtuelle Tour mit Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
17.10. Datenstruktur für die Historie . . . . . . . . . . . . . . . . . . . . . . . . 318
17.11. Filter für die Historie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

17.12. Zusammenfassung Koroutinen . . . . . . . . . . . . . . . . . . . . . . . . 322

viii