Vom Problem zum Programm

No matter what they tell you, it’s always a people problem.
– Gerald M. Weinberg

Der Software-Entwicklungsprozess

flowchart TB
	subgraph task [ Problem ]
		direction LR
		Aufgabe --> ? --> Lösung
	end
	subgraph eva [ ]
		direction LR
		Eingabe --> Verarbeitung --> Ausgabe
	end
	subgraph code [ ]
		direction TB
			Algorithmus -- implementieren --> Quelltext
			Quelltext -- übersetzen --> Programm
	end

	task -- entwerfen --> code -- ausführen--> eva

Das Bedürfnis, selbst Programme zu schreiben, entsteht dann, wenn es noch kein Programm gibt, welches eine mittels Computer zu bewältigende Aufgabe zufriedenstellend löst. Ein Problem besteht dann, wenn man nicht weiß, wie man zur Lösung kommt. Die Software-Entwicklung geschieht in mehreren Etappen, die (anders als im Bild oben) nicht linear aufeinander folgen, sondern immer wieder auch Rückgriffe auf vorangegangene Tätigkeiten erfordern (Software-Zyklus im Bild unten):

Analyse: Worin besteht die Aufgabe? Welche Lösung wird erwartet? Welche Mittel stehen zur Lösung zur Verfügung? Diese Anforderungen können als Pflichten- oder Lastenheft schriftlich fixiert werden.
Entwurf: Dies ist die spannende Etappe, in der nach Lösungswegen gesucht wird. Erfahrung und Intuition sind erforderlich. Die Transformation der Eingabedaten zu den Ausgabedaten folgt einem Algorithmus. Dies ist ein Verfahren, welches eine bestimmte Klasse von Aufgaben löst. Es führt in endlich vielen, eindeutig definierten Schritten zum hoffentlich korrekten Ergebnis. Ein Algorithmus kann sehr komplex sein. Er muss sich aber in kleinere, einfacher zu bewältigende Teilaufgaben gliedern lassen. Diese muss man auch in der Muttersprache beschreiben können. Schafft man das nicht, gelingt es auch nicht in Fremdsprachen oder Programmiersprachen („native speaker“ natürlich ausgenommen ;-).
Umsetzung: Der Entwurf wird in die Programmiersprache umgesetzt. Ziel ist ein lauffähiges Programm.
Test: Nun muss noch geprüft werden, ob das Programm korrekt arbeitet. Vorbereitete Testdaten sollen sicherstellen, dass die Programmausgaben korrekt sind.

stateDiagram
	direction LR
	Aufgabe --> Analyse
	Analyse --> Entwurf
	Entwurf --> Umsetzung
	Umsetzung --> Test
	Test --> Analyse
	Test --> Auslieferung

Programmieren im Großen bedeutet auch, dass alle Etappen ausreichend dokumentiert werden. Dies hilft nachfolgenden Personen, das entstandene Produkt zu verstehen. Wie, du entwickelst nur für dich allein? Ok, und was ist mit dir selbst? Versteht du dein Programm drei Wochen später?

Aufgabe

Messdaten werden als aufeinanderfolgende Zahlen in Dateien erfasst. Manche Zahlen enthalten ein Dezimalkomma. Auf den Daten sollen statistische Auswertungen erfolgen: Umfang der Stichprobe, Mittelwert und Standardabweichung. Die Auswertung soll maschinell erfolgen. Händisches Importieren in eine Tabellenkalkulation kommt nicht in Frage.

Analyse

Die Aufgabenstellung enthält Fachbegriffe, die zunächst klar definiert werden müssen. Dazu fragen wir Menschen, die etwas von dem Fachgebiet verstehen. Die erklären uns:

Jeder Messwert besteht aus einer einzigen reellen Zahl.
Die Anzahl der Zahlen ist der Umfang der Stichprobe. Mathematisch ist die Bezeichnung $n$ üblich.
Der Mittelwert $\overset{x}{ˉ}$ ist als Quotient aus der Summe aller Werte $X_{i}$ und dem Stichprobenumfang definiert: $\overset{x}{ˉ} = \frac{1}{n} \sum_{i} X_{i}$ .
Die Standardabweichung $σ$ kann als Quadratwurzel der Varianz angegeben werden.
Die Varianz wiederum wird auch als mittlere quadratische Abweichung bezeichnet. Zu ihrer Berechnung kann diese Formel genutzt werden: $\frac{1}{n} \sum_{i} (X_{i} - \overset{x}{ˉ})^{2} = \frac{1}{n} \sum_{i} X_{i}^{2} - (\frac{1}{n} \sum_{i} X_{i})^{2}$ .
Die sogenannte empirische Varianz (Varianz der Stichprobe) enthält statt des Divisors $n$ den Divisor $n - 1$ : $s^{2} = \frac{1}{n - 1} \sum_{i} (X_{i} - \overset{x}{ˉ})^{2}$ . Nur die empirische Varianz ist erwartungstreu, d.h. bei mehr Messungen sollte das Ergebnis nicht allzu weit davon wandern. In anderen Worten: Um die empirische Varianz $s^{2}$ und die empirische Standardabweichung $s$ anzugeben, sind mindestens zwei unterschiedliche Messwerte erforderlich. Mehr Messwerte sind besser. Allerdings sagen Physiker auch: Wer viel misst, misst viel Mist.

Alle Zahlen müssen also nacheinander eingelesen werden. Dabei ist fortlaufend mitzuzählen, wie viele Zahlen erfasst wurden. Eingelesene Zahlen müssen summiert werden, ebenso deren Quadrate. Sind alle Zahlen erfasst, können Mittelwert und Standardabweichung berechnet werden. Die Ergebnisse sind auszugeben in der Form mittelwert +/- standardabweichung.

Entwurf

Wir formulieren den Algorithmus als Folge von Handlungen. Zahlen und Zwischenergebnisse werden unter Variablennamen abgelegt. Neben Unbekannten x benötigen wir die Anzahl n, die Summe sx der Zahlen und die Summe sxx der Quadrate. Bevor ein Wert erhöht werden kann, müssen wir einen Startwert festlegen. Hier sind Nullen sinnvoll. Bei jeder neuen Zahl x werden n, sx und sxx erhöht.

Ergebnis des Entwurfs kann ein Pseudocode wie dieser sein:

Variablen: x, n, sx, sxx
n = 0
sx = 0
sxx = 0
für jede eingelesene Zahl x:
	erhöhe n um eins
	erhöhe sx um x
	erhöhe sxx um x²
 
mittel = sx/n
varianz = sxx/n - mittel²
empirische_standardabweichung = Quadratwurzel(varianz*n/(n-1))
Ausgabe: mittel " +/- " empirische_standardabweichung

Ein Mensch sollte diesen Algorithmus abarbeiten können. Wir testen das mit ausgedachten Eingabewerten wie 2 1 3. Eine Werteverlaufstabelle hilft dabei, den Fortgang zu verfolgen:

Eingabe x	n	sx	sxx
	0	0	0
2	1	2	4
1	2	3	5
3	3	6	14
Also wird der Mittelwert $2$ , die Varianz $\frac{14}{3} - 2^{2} = \frac{2}{3} = 0, 666...$ und die Standardabweichung $\frac{2}{3} \approx 0, 816...$ .

Umsetzung

//> basics/statistik.cpp
import std;
 
int main()
{
	double x;
	int n = 0;
	double sx = 0;
	double sxx = 0;
 
	while (std::cin >> x)
	{
		n += 1;
		sx += x;
		sxx += x*x;
	}
 
	double mittel = sx / n;
	double varianz = sxx / n - mittel * mittel;
	double standardabweichung = std::sqrt(varianz);
 
	std::cout << mittel << " +/- " << standardabweichung << '\n';
}

Test

Starten wir das Programm und geben die Zahlen 2 1 3 nacheinander über die Tastatur ein. Es ist gleichgültig, ob wir zwischen den Zahlen die Leertaste oder die Entertaste drücken. Nach der letzten Zahl drücken wir die Entertaste. Das Programm wartet auf weitere Zahlen. Wir beenden die Eingabe in der Konsole mit der Tastenkombination Strg+Z unter Windows bzw. mit Strg+Dunter Linux. Dann erscheinen die Ergebnisse. Stimmen die mit den vorherigen Überlegungen überein? Gut. Wenn nicht, ist das Programm fehlerhaft. Finde den Fehler. Beachte: Das Programm gibt gebrochene Zahlen mit 6 zählenden Stellen aus.

Noch ein Test. Die Aufgabenstellung besagt, dass die Eingabedateien Zahlen mit Dezimalkomma enthalten dürfen. Daher noch ein Programmlauf mit 1,5 2,5 3,5. Nanu! Das Programm antwortet fehlerhaft mit 1 +/- 0: Warum?

Noch einmal. Diesmal geben wir jede Zah auf einer eigenen Zeile ein. Schon nach der ersten Zahl erscheint das falsche Ergebnis. Aha! Das Programm kann keine Dezimalkommas verarbeiten. Im englischen Sprachraum werden gebrochene Zahlen mit decimal point geschrieben. Ein Programmlauf mit den Eingaben 1.5 2.5 3.5 bestätigt das: Ausgabe 2.5 +/- 0.816....

Wie gehen wir nun mit den Dezimalkommas um? Zurück zum Entwurf. Müssen wir das Programm so umschreiben, dass es Kommas akzeptiert? Möglich ist das, nur für Anfänger zu kompliziert. Uns kommt eine einfachere Idee. Tauschen wir in den Eingabedaten einfach die Kommas mit Punkten aus. Mit einem Editor Eingabedatei öffnen, Komma suchen, ersetzen, speichern? Nein, halt! Die Eingabedateien sollten wir nicht verändern. Der Computer soll die Aufgabe erledigen. Wir schalten unserem Programm ein weiteres Programm vor, welches den Eingabedatenstrom zeichenweise entgegen nimmt und anstelle eines Komma einen Punkt in den Ausgabedatenstrom schickt:

//> basics/komma_zu_punkt.cpp
import std;
 
int main()
{
	char c;
	while (std::cin.get(c))
	{
		if (c == ',') std::cout << '.';
		else std::cout << c; 
	}
}

Die Eingabedaten mit Dezimalkomma schreiben wir in eine Textdatei testdaten.txt:

1,5 2,5 3,5

und schicken sie auf der Konsole per Dateiumlenkung mit dem Kleiner-als-Zeichen zuerst in dieses Programm und koppeln dessen Ausgaben als Eingaben an das Statistikprogramm. Dafür nutzen wir das Pipe-Symbol, den senkrechten Strich:

komma_zu_punkt < testdaten.txt | statistik

Ausgabe: 2.5 +/- 0.816.... Es funktioniert! Die Ausgaben können auch in eine Datei umgelenkt werden:

komma_zu_punkt < testdaten.txt | statistik > ergebnis.txt

Möchtest du die Ausgabe wieder mit Komma? Nun, dann schreibe ein Programm punkt_zu_komma und hänge dessen Aufruf hinten an:

komma_zu_punkt < testdaten.txt | statistik | punkt_zu_komma

Das ist die Philosophie hinter den Unix-Systemen: Small is beautiful. Kleine Programme, die jeweils nur einem einzigen Zweck dienen, diesen aber richtig erfüllen und sich miteinander kombinieren lassen.

Genaugenommen funktionieren beide Zeichenersetzungsprogramme in gleicher Weise, nur mit verschiedenen Zeichen. Dies lässt sich zu einem Programm verallgemeinern. Dann entwickeln wir daraus so etwas wie den Unix-Befehl sed und erweitern diesen solange, bis er E-Mails verschicken kann… ;-)

Eigentlich wären wir fertig. Doch wir geben uns damit nicht zufrieden. Was sollte ausgegeben werden, wenn gar keine Messwerte eingegeben werden? Und was bedeutet die Bemerkung über die empirische Varianz bzw. empirische Standardabweichung? Mit den benutzten Eingabedaten wäre als empirische Varianz und als empirische Standardabweichung der Wert 1 auszugeben. Das nächste Programm berücksichtigt beide Fragen:

//> basics/statistik2.cpp
import std;
 
int main()
{
	double x;
	int n = 0;
	double sx = 0;
	double sxx = 0;
 
	while (std::cin >> x)
	{
		n += 1;
		sx += x;
		sxx += x*x;
	}
	if (n == 0)
	{
		std::cerr << "keine Messwerte\n";
		return -1;
	}
 
	double mittel = sx / n;
	double varianz = sxx / n - mittel * mittel;
 
	std::cout << mittel;
	if (varianz > 0)
	{ 
		double empirische_standardabweichung = std::sqrt(varianz * n / (n-1));
		std::cout << " +/- " << empirische_standardabweichung;
	} 
	else
	{
		std::cerr << "\nBerechnung der Standardabweichung erfordert mehr Messwerte!\n";
	}
	std::cout << '\n';
}

In diesem Programm wurden zugleich noch Fehlerausgaben eingebaut, die vor fehlenden Messwerten oder voreilig als „exakt“ eingestuften Ergebnissen warnt. Eigentlich gilt: Überrasche niemals den Anwender. Es schadet aber nicht, weiter zu denken. Erkennst du als Programmierer ein Problem, informiere den Auftraggeber und unterbreite ihm ein „Angebot, das dieser nicht ablehnen kann“. Nicht immer hat der Auftraggeber alle Fallstricke erkannt.

Wir sind mitten im Programmieren angekommen. Bevor wir weitere Ideen verwirklichen können, müssen wir ein paar offene Fragen klären. In den Programmen stehen Wörter wie char, double, else, if, while. Diese Schlüsselwörter wurden noch gar nicht erklärt! Nun, was könnten die bedeuten? Mehr darüber im Kapitel über Grundlagen von C++. Wir stehen erst am Anfang. Zeit, ein paar Vokabeln und deren Bedeutung zu lernen.

Aufgaben

Erwirb erste Grundkenntnisse in C++. Übe. Schreibe kleine Programme. Übersetze und teste sie.

Finde kleine (!) Aufgaben, die als Programm umsetzbar sind.

namespace cpp {}

Seiten

Vom Problem zum Programm