Grundlagen der Informatik I: Programmierung
1
Einführung
1
1.1
Das Ziel: Qualitativ hochwertige Informationssysteme
2
1.2
Theoretische Schwerpunkte der ersten beiden Semester
4
1.2.1
Logik für die Problemlösung 6
1.2.2
Funktionen für die Problemlösung 8
1.2.3
Problemorientierte imperative Sprachen 10
1.2.4
Maschinennahe Sprachen 13
1.2.5
Schaltungen zur Problemlösung 14
1.2.6
Zusammenhang der Ebenen 14
1.3
Methodisch-Technische Schwerpunkte
16
1.3.1
Programmieren: Anwendung formaler Systeme 16
1.3.2
Strukturierungskonzepte 17
1.3.3
Schrittweise Verfeinerung 18
1.3.4
Prozeduralisierung 20
1.3.5
Modularisierung 21
1.3.6
Klassifizierung 21
1.3.7
Zusammenfassung 23
2
Grundlagen: Logik und formale Sprachbeschreibungen
25
2.1
Formale Sprachbeschreibungen
27
2.1.1
Syntax 27
2.1.2
Die Syntax der Aussagenlogik 31
2.1.3
Semantik 34
2.1.4
Konversion - Ableitung 38
2.1.5
Zusammenhang zwischen Syntax, Ableitungssystem und Semantik 42
2.2
Logik als Spezifikationssprache
43
2.2.1
Umsetzung natürlichsprachlicher Aussagen in solche der Logik 43
2.2.2
Prädikatenlogik 44
2.2.3
Syntax der Prädikatenlogik 45
2.2.4
Semantik der Prädikatenlogik 46
2.2.5
Ableitungskalkül für die Prädikatenlogik 49
2.2.6
Dreiwertige Logik 50
2.3
Formale Beschreibung von Programmiersprachen
51
2.3.1
Funktionen und zusammengesetzte Ausdrücke 51
2.3.2
Bedingte Ausdrücke 52
2.3.3
Abkürzungen 52
2.3.4
Tabellen 53
2.3.5
Listen 55
2.4
Diskussion
56
2.5
Ergänzende Literatur
57
3
Klassen und Objekte
59
3.1
Objekte
61
3.1.1
Einfache Objekte 61
3.1.2
Verweise 61
3.2
Klassen
63
3.2.1
Abstrakte Datentypen 64
3.2.2
Klassen in
Eiffel
67
3.2.3
Typen und Verweise 68
3.2.4
Kunden, Lieferanten und Selbstreferenz 69
3.3
Routinen
70
3.3.1
Aufruf von Routinen 70
3.3.2
Definition von Routinen 71
3.3.3
Lokale Variablen 72
3.3.4
Standardoperationen für alle Klassen 73
3.3.5
Das aktuelle Exemplar 77
3.3.6
Nicht-standardmäßiges Erzeugen 78
3.4
Das Geheimnisprinzip
79
3.5
Copy- und Referenz-Semantik
82
3.5.1
Einfache Typen und Klassentypen 82
3.5.2
expanded
: Klassen mit Copy-Semantik 84
3.6
Generische Klassen
85
3.6.1
Parametrisierung von Klassen 85
3.6.2
Typprüfung 86
3.6.3
Felder: Beispiele generischer Klassen 88
3.7
Verträge für Software-Zuverlässigkeit
89
3.7.1
Zusicherungen 90
3.7.2
Vor- und Nachbedingungen 91
3.7.3
Klasseninvarianten 93
3.7.4
Grenzen der Anwendbarkeit von Zusicherungen 95
3.8
Vererbung
96
3.8.1
Erben und Vorfahren 96
3.8.2
Export geerbter Features 98
3.8.3
Redefinition 100
3.8.4
Polymorphismus 102
3.8.5
Deklaration durch Assoziation 105
3.8.6
Deferred Classes: Abstrakte Datentypen in
Eiffel
106
3.8.7
Mehrfachvererbung 109
3.8.8
Umbenennung 111
3.8.9
Wiederholtes Erben 113
3.8.10
Vererbung und Zusicherungen 115
3.8.11
Kaufen oder Erben? 117
3.9
Arbeiten mit
Eiffel
117
3.10
Diskussion
119
3.11
Sprachbeschreibung
121
3.11.1
Syntax 122
3.11.2
Statische und Dynamische Semantik 124
3.12
Ergänzende Literatur
124
3.13
Deutsch-Englisches Begriffswörterbuch
124
4
Systematische Entwicklung zuverlässiger Software
127
4.1
Systematischer Entwurf von Softwaresystemen
127
4.1.1
Analyse und Gestaltung 128
4.1.2
Grundideen des objektorientierten Entwurfs 129
4.1.3
Aufspüren der Klassen 130
4.1.4
Schnittstellentechniken 130
4.1.5
Vererbungstechniken 131
4.1.6
Beispiel: Bibliothekenverwaltung 132
4.1.7
Ästhetik der Programmierung 137
4.2
Verifikation
138
4.2.1
Korrektheit von Routinen und Klassen 139
4.2.2
Ein Kalkül für Verifikation 141
4.3
Strukturierung von Routinen
144
4.3.1
Wertzuweisung 144
4.3.2
Routinenaufruf 146
4.3.3
Zusammengesetzte Anweisungen 150
4.3.4
Bedingte Anweisung und Fallunterscheidung 152
4.3.5
Wiederholung 157
4.3.6
überprüfung 163
4.3.7
Umgang mit Fehlern: Disziplinierte Ausnahmen 164
4.3.8
Debugging 166
4.3.9
Einfache Ein- und Ausgabe 167
4.3.10
Die Verifikation rekursiver Routinen 169
4.3.11
Diskussion 172
4.3.12
Sprachbeschreibung 173
4.4
Ausdrücke: Grundbausteine von
Eiffel
-Programmen
174
4.4.1
Konstanten 175
4.4.2
Größen 175
4.4.3
Current
175
4.4.4
Funktionsaufrufe 176
4.4.5
Ausdrücke mit Operatoren 176
4.4.6
Sprachbeschreibung 177
4.4.7
Diskussion 178
4.5
Systematische Implementierung von Routinen
178
4.5.1
Allgemeine Prinzipien 178
4.5.2
Programmierung als zielgerichtete Tätigkeit 182
4.5.3
Entwurf von Schleifen 184
4.5.4
Sinnvoller Einsatz von Rekursion 186
4.6
Ethik und Verantwortung
189