Algorithmen & Datenstrukturen
Programmieren 1


von Prof. Jürgen Plate

1.5 Vom Problem zur Lösung

Programming today is a race between software engineers striving to build bigger and better idiot-proof programs and the universe trying to produce bigger and better idiots.
So far, the universe is winning.

Richard Cook

1.5.1 Überblick

Bevor der Softwareerstellungsprozeß beginnt, ist das Wichtigste das Ziel festzulegen: Wofür und warum muß Software erstellt werden und was muß sie können, um diese Aufgabe zu erledigen. Im folgenden Bild ist der Softwareprozeß, den Sie am ENde des vorhergehenden Kapitels schon gesehen haben, stark vereinfacht in der Übersicht dargestellt:

Es gibt mindestens zwei Beteiligte, wobei der eine mehrere Rollen verkörpert: den Kunden und den Entwickler. Der erste Schritt ist die Aufschreibung der Kundenanforderungen. Der Entwickler schlüpft hier in die Rolle des Systemanalytikers. Er versucht den Kunden und dessen Anwendungswelt zu verstehen und aus einer unstrukturierten Aufgabenbeschreibung (Lastenheft) die für die Softwareerstellung nötigen Zusammenhänge zu erfassen und daraus eine realisierbare in sich konsistente - für die Realisierung verbindliche - Aufgabenbeschreibung (Pflichtenheft) zu erstellen. Er muß vor allem das Wesentliche vom Unwesentlichen unterscheiden, abstrahieren und auf den Kunden eingehen können, um das zu erfassen, was zu tun ist. Im nächsten Schritt ist der Entwickler in der Rolle des Systemdesigners. Ähnlich einem Architekten konstruiert er, geleitet von seinen Lösungsideen und der Machbarkeit, die Softwarestruktur (Softwaredesign). Er legt fest wie die Aufgabe in Software umgesetzt wird. Parallel dazu wechselt er in die Rolle des Testplaners (Qualitätssicherung) und überlegt sich die notwendige Vorgehensweisen und erstellt die Testspezifikation. Bislang ist nur Papier entstanden und ungefähr die Hälfte der verfügbaren Zeit vergangen. Im nächsten Schritt übernimmt er die Rolle des Programmierers (Programmcode und Dokumentation) und hoffentlich ein Anderer die Rolle des Testers ( Testprotokolle). Irgendwann ist die Software getestet fertig und wird vom Kunden abgenommen (Abnahme). Hier testet der Kunde die Software gegen die im Pflichtenheft versprochenen Funktionen auf Fehlerfreiheit, oftmals im Beisein des Entwicklers. Es wird ein Protokoll erstellt und bei Fehlerfreiheit der Software muß der Kunde den vereinbarten Preis bezahlen.

Selbstverständlich ist der Entwicklungsablauf nicht so zeitlich und Aufgaben-sequentiell wie hier geschildert. Je nach Größe des Projektes kommen immer noch während der Entwicklungsphase Änderungswünsche der unterschiedlichsten Art vom Kunden und auch vom Entwickler. Der Kunde entwickelt sich mit seinen Aufgaben weiter und der Entwickler versteht immer besser seine Aufgabe je länger er daran arbeitet. Damit das alles nicht aus der Kontrolle läuft gibt es noch die Rolle des Projekt- oder Entwicklungsleiters. Dessen Verantwortung und Aufgabe ist es mit den Hilfsmitteln des Projektmanagements die Softwareentwicklung so zu steuern, daß die Software in der geplanten Zeit, geplantem Umfang und festen Budget fertig wird; das ist keine leichte Aufgabe.

1.5.2 Problemanalyse

Heuristik (griech.: Kunst des Findens bzw. Erfindens). In seinen "Regeln zur Leitung des Geistes" stellt der französische Philosoph und Mathematiker Descartes folgende Maximen auf:
  1. Übereilung und Vorurteil sind sorgfältig zu meiden.
  2. Jede der zu untersuchenden Schwierigkeiten ist in so viele Teile zu zerlegen, wie es möglich und zur besseren Lösbarkeit wünschenswert ist.
  3. Mit den einfachsten und faßlichsten Objekten ist zu beginnen und von da aus schrittweise zur Erkenntnis der kompliziertesten fortzuschreiten.
  4. Hinreichend vollständige Aufzählungen und allgemeine Übersichten sind anzufertigen, um sicher zu gehen, daß nichts ausgelassen wurde.
Dies sind allgemeine Regeln, die jedem Problemlöser kommen. Für den Fall daß das zu entwerfende Verfahren einer Maschine zur Ausführung überantwortet werden soll, nehmen sie eine spezielle Gestalt an, die Thema der folgenden Kapitel ist.

Die wichtigste Phase beim Erstellen eines Algorithmus ist die Analyse der Problemstellung und das Nachdenken über die Lösung. Dieser Teil, die Problemanalyse und die nachfolgende Skizze des Lösungswegs, ist wesentlich wichtiger und zeitaufwendiger als die eigentliche Kodierung in irgendeiner Programmiersprache. Nicht zu Unrecht arbeiteten in den Anfängen der EDV die Systemanalytiker und Programmierer relativ getrennt voneinander. Damals gab es aber auch keinerlei wissenschaftliche Aufarbeitung des Problems, also das, was heute als "Softwaretechnik" bezeichnet wird. Programmieren fand eher intuitiv und mit "Versuch und Irrtum" statt - so wie heute auch oft noch von Anfängern programmiert wird. Welche Phasen beim Entwickeln eines Algorithmus durchlaufen werden, soll an zwei Beispielen gezeigt werden:

Gesucht wird ein Algorithmus zur Jahrestagberechnung. Zu einem eingegebenen Datum (Tag, Monat, Jahr) soll ausgerechnet werden, um den wievielten Tag im Jahr es sich handelt.

Der erste Schritt ist natürlich immer das Nachdenken über die Problemlösung. Diese Phase sollte nicht zu kurz sein, denn oft findet sich eine optimale Lösung erst nach dem zweiten oder dritten Ansatz. Und kürzere Programme sind nicht nur schneller, sondern haben (rein statistisch betrachtet) auch weniger Fehler. Dann sollte man den Lösungsweg skizzieren und dabei auch überlegen, ob auch alle Randbedingungen und Ausnahmesituationen berücksichtigt wurden.

Oft hilft es, den Algorithmus zuerst anhand eines Beispiels durchzuspielen. Dabei werden einem oft Zusammenhänge und Fallstricke klar. Versuchen wir das gleich mit der Problemstellung von oben:

Das Verfahren addiert also bis zum Juni die Monatslängen und zählt dann noch die 7 Tage des Juli hinzu. Spätestens hier sollte einem einfallen, daß der Februar auch 29 Tage haben kann. Der Programmierer sollte sich hier eine Notiz machen: "Nachsehen, wann ein Jahr ein Schaltjahr ist".

Danach sollte eine problemnahe Darstellung des Algorithmus folgen. Diese sieht beispielsweise so aus:

  1. Eingabe von Tag, Monat, Jahr.
  2. Ermittle die Monatslänge des Februar (Schaltjahr?).
  3. Addiere die Monatslängen der Vormonate (also bis Monat-1) und den Tageswert des eingegebenen Monats.
  4. Gib das Ergebnis aus.

Dabei wird davon ausgegangen, daß die Eingabe korrekt ist (also nicht z. B. der 35.13.19999 eingegeben wird. Eine Optimierungsmöglichkeit des Algorithmus ist gegeben, wenn man für Werte von Monat, die kleiner als 2 sind, die Schaltjahresberechnung wegläßt.

Für die Schaltjahresberechnung brauchen wir noch einen Teilalgorithmus. Selbst bei diesem recht einfachen Beispiel zeigt sich also schon ein Grundsatz der strukturierten Programmierung, die Zerlegung einer Aufgabe in kleinere und damit überschaubare Teilaufgaben. Nach dem Gregorianischen Kalender handelt es sich um ein Schaltjahr,

Das Jahr 2000 ist also ein Schaltjahr (was viele Programme nicht richtig machen). Der Algorithmus lautet also:

  1. Eingabe Jahr.
  2. Falls (Jahr mod 4) != 0: Ausgabe "NEIN" und ENDE.
  3. Falls (Jahr mod 100) != 0: Ausgabe "JA" und ENDE.
  4. Falls (Jahr mod 400) = 0: Ausgabe "JA" sonst: Ausgabe "NEIN".

Anmerkungen: mod sei der Modulo-Operator = Rest der ganzzahligen Division. != bedeutet "ungleich".

Nun steht der Jahreszahlberechnung eigentlich nichts mehr im Weg. Die einzige Schwierigkeit liegt noch darin, daß die Monatslängen unterschiedlich sind:
Jan. Feb. März April Mai Juni Juli Aug. Sept. Okt. Nov.
31 28/29 31 30 31 30 31 31 30 31 30

Nun ließe sich ein Algorithmus niederschreiben, der 11 WENN-DANN-Abfragen enthält, welche die Tagessumme der Vormonate berechnen:

  1. Eingabe Tag, Monat, Jahr.
  2. Wenn Monat = 1 dann Jahrestag = Tag und ENDE.
  3. Wenn Monat = 2 dann Jahrestag = 31 + Tag und ENDE.
  4. Wenn Monat = 3 dann Jahrestag = 31 + 28 + Tag.
    Wenn Schaltjahr, erhöhe Jahrestag um 1.
    ENDE.
  5. Wenn Monat = 4 dann Jahrestag = 31 + 28 + 31 + Tag.
    Wenn Schaltjahr, erhöhe Jahrestag um 1.
    ENDE.
  6. Wenn Monat = 5 dann Jahrestag = 31 + 28 + 31 + 30 + Tag.
    Wenn Schaltjahr, erhöhe Jahrestag um 1.
    ENDE.
  7. ....

Damit ist die Aufgabe sicher zufriedenstellend gelöst.

Es stellt sich die Frage, ob es nicht einfacher, kürzer und "eleganter" geht. Denn es ist nicht immer der erste Lösungsweg der einem einfällt, auch der beste und effizienteste Weg. Setzt man versuchsweise alle Monate mit 31 Tagen an, werden ab März zu viele Tage genommen, und zwar:
März April Mai Juni Juli Aug. Sept. Okt. Nov. Dez.
3 3 4 4 5 5 5 6 6 7

Nach einigem Nachdenken und/oder Probieren kommt man vielleicht auf eine höchst interessante Korrekturformel:

Y = 0,4 * Monat + 2,3

Diese Formel liefert die Werte:
März April Mai Juni Juli Aug. Sept. Okt. Nov. Dez.
3,3 3,9 4,3 4,7 5,1 5,5 5,9 6,3 6,7 7,1

Der ganzzahlige Teil der Ergebnisses stimmt offensichtlich mit den Fehlerwerten der vorhergehenden Tabelle überein. Mit dieser Formel kann man den Jahrestags-Algorithmus folgendermaßen definieren (INT nimmt den Ganzzahlanteil einer Zahl):

  1. Eingabe Tag, Monat, Jahr.
  2. Jahrestag = Tag + 31 * (Monat -1).
  3. Falls Monat > 2 ist:
    1. Vermindere Jahrestag um INT(0,4 * Monat + 2,3).
    2. Falls Schaltjahr = "JA" erhöhe Jahrestag um 1.
  4. Ausgabe Jahrestag.

Wie man leicht sieht, ist dieser Algorithmus wesentlich kürzer als der erste Ansatz - sowohl von der Laufzeit, als auch von Speicherbedarf her. Nachteilig gegenüber dem ersten Ansatz ist nur, daß dieser Algorithmus dem Leser nicht sofort einleuchtet und daher sorgfältig dokumentiert werden muß.

Untersuchen wir einen zweiten Fall:

Gesucht wird ein Algorithmus, der feststellt ob eine gegebene Zahl eine Primzahl ist.

Eine positive Zahl X ist genau dann eine Primzahl, wenn sie nur durch sich selbst und durch 1 teilbar ist. Ein erste Lösungsansatz ist:

  1. Setze den Teiler T auf 2.
  2. ist X ohne Rest durch T teilbar, gib "nicht prim" zurück und beende.
  3. erhöhe T um 1.
  4. ist T < X, fahre fort bei Schritt 2.
  5. gib "prim" zurück und beende.
Formuliert man das als C-Programmfragment, ergibt sich:
T = 2;                    /* Schritt 1 */
do
  {
  if ((X % T) == 0)       /* Schritt 2 */
    {
    printf("nicht prim"); 
    return 0; 
    }
  T++;                     /* Schritt 3 */
  }
while (T < X);          /* Schritt 4 */
printf("p r i m");         /* Schritt 5 */
Näheres zur Syntax von C folgt im zweiten Kapitel.

Dieser Algorithmus ist (hoffentlich) effektiv, d. h. er leistet das Gewünschte. Ist er aber auch effizient, d. h. leistet er das Gewünschte bestmöglich? Die Antwort ist natürlich ein dickes "NEIN". Es werden nämlich unnötig viele Zahlen getestet. Bereits durch kleine Modifikationen kann man den Aufwand für den Primzahlentest deutlich verringern:

Das geänderte Programm lautet dann wie folgt (die genaue Bedeutung der einzelnen Begriffe wird in Kapitel 2 erlätert):
#include<stdio.h>

int X, T;

int main(void)
/* optimierter Entwurf */
  {
  scanf("%d",&X);           /* X einlesen */
  if ((X % 2) == 0)         /* Zahl gerade? */
    {
    printf("nicht prim, gerade\n"); 
    return (0);             /* Programmende */ 
    }
  T = 3;   
  do
    {
    if ((X % T) == 0)
      {
      printf("nicht prim, Teiler = %d\n", T); 
      return (0);         /* Programmende */ 
      }
    T = T + 2;
    }
  while (T*T < X); 
  printf("p r i m!\n");
  return (0);            /* Programmende */ 
  }

1.5.3 Lösungsstrategien

Programmieren heißt, den zeichnerisch oder verbal dargestellten Algorithmus in eine Programmiersprache umzusetzen und zu testen. Dabei werden die Schritte Codierung, Eingabe, Übersetzung und Testen zumeist wiederholt durchlaufen. Der Übersetzungslauf als gesonderter Schritt ist bei Sprachen mit Compiler, nicht aber bei solchen mit Interpreter erforderlich. Das Testen erfolgt nicht nur als Computertest, sondern auch als Schreibtischtest. Der Compiler hilft uns zwar, syntaktische Fehler zu finden; logische Fehler im Programm lassen sich aber nur durch Nachdenken und Schreibtischtests herausfinden.

Dokumentation: Ein verantwortungsbewußter Programmierer sollte seine Tätigkeit als Erfüllung eines Kontraktes auffassen: zu einem vertraglich fixierten Problem wird ein Programm geliefert, welches das Problem mehr oder weniger effizient löst. Voraussetzung der genauen Erfüllung eines solchen Kontraktes ist eine Spezifikation des Problems mit der Eigenschaft, daß sowohl Auftraggeber als auch Auftragnehmer wissen, was sie unterschreiben. Das Programm als Vertragsgegenstand muß in einer Weise geliefert werden, daß es durch den Auftraggeber angewandt (benutzt) und gewartet werden kann; unentbehrliches Hilfsmittel hierfür ist die Dokumentation. Man unterscheidet zwei Arten von Dokumenten:

Problemanalyse und Entwicklung des Algorithmus: Zentraler Teil der Programmentwicklung ist der Programmentwurf und nicht - wie es manchem Anfänger scheinen mag - die Programmierung bzw. Codierung in einer Programmiersprache.

Software-Engineering: Angesichts der steigenden Software-Kosten geht man immer mehr dazu über, die Programmentwicklung und dabei besonders den Programmentwurf industriell und ingenieurmäßig vorzunehmen: Software-Engineering lautet die darauf verweisende Begriffsbildung. Auf einige der im Rahmen des Software-Engineering eingesetzten Programmiertechniken sowie Entwurfsprinzipien gehe ich nachfolgend ein.

Entwurfstechniken und -prinzipien

Entwurfstechniken werden durch Begriffe wie Modularisierung, Normierung, Jackson-Methode, Top-Down-Entwurf, Bottom-Up-Entwurf, Unterprogrammtechnik, Menütechnik und Strukturierter Entwurf geprägt. Im folgenden werden diese Begriffe erläutert:

Die oben nur stichwortartig dargestellten Prinzipien dürfen nicht getrennt betrachtet werden; unter dem Informatik-Sammelbegriff strukturierte Programmierung faßt man sie zu einem heute allgemein anerkannten Vorgehen zusammen. Die tragenden Prinzipien sind:

  1. Top-Down-Entwurf mit der schrittweisen Verfeinerung.
  2. Strukturierter Entwurf mit der Blockbildung.

1.6 Entwicklung und Darstellung des Algorithmus

Die Anweisungen (Befehle) eines Programms bestehen aus wenigen, festen Strukturen. Im folgenden werden diese Strukturen besprochen und ihre Darstellung als Programmablaufplan (PAP) und Struktogramm gezeigt. Die Struktogramme verzichten auf Ablauflinien und vermeiden so die Gefahr der Unübersichtlichkeit. Zudem ist es mit dieser Darstellung schwerer, unbedingte Sprünge aus Anweisungsstrukturen heraus darzustellen, die vielfach zu Fehlern oder zu "trickreicher" Programmierung führen ("Spaghetti-Code").

Die Programmstrukturierung in Anweisungsblöcke mit fest definierten Eintritts- und Austrittspunkten bietet zudem die Möglichkeit, Programme zu verifizieren, d. h. Programme mit garantierter Zuverlässigkeit zu erstellen, indem für jeden Anweisungsblock eine wohldefinierte Beziehung zwischen den Werten einer Variablen vor und nach Durchlaufen einer Anweisungsstruktur festgelegt werden kann (das dies bei großen Programmsystemen aus Zeitgründen nicht gemacht wird, ändert nichts am Faktum).

1.6.1 Programmstrukturen

Es gibt vier grundlegende Programmstrukturen: Folge, Auswahl, Wiederholung und Unterprogramm. Sie sind die grundlegenden Ablaufarten der Programmierung überhaupt. Grundlegend in zweifacher Hinsicht:

Grundsätzlich lassen sich Programmstrukturen beliebig schachteln, d. h. innerhalb einer Programmstruktur kann wieder eine andere Programmstruktur ausgeführt werden und so fort.

Programmstrukturen:

  1. Sequenz (Folgestruktur):
    Erst Anweisung 1 ausführen, dann Anweisung 2, usw.
  2. Auswahlstrukturen(Bedingte Verzweigung, Mehrfachauswahl):
    Wenn Bedingung erfüllt, dann Anweisung(en) ausführen
  3. Wiederholungsstrukturen:
    Wiederhole Anweisungen, bis (Abbruch-)Bedingung erfüllt ist
  4. Unterablaufstrukturen:
    Führe Anweisungen aus, führe Unterprogramm aus, kehre zurück und fahre im Hauptprogramm fort.

Sequenz (Folgestruktur)

Linearer Ablauf: Jedes Programm besteht aus einer Aneinanderreihung von Anweisungen an den Computer. Die Sequenz ist eine Folge von Anweisungen, die in der Reihenfolge ihrer Niederschrift ausgeführt werden. Man spricht deshalb auch vom linearen Ablauf bzw. unverzweigten Ablauf, vom Geradeaus-Ablauf oder von einer Sequenz. In verschiedenen Programmiersprachen wird die "Klammerung" einer solchen Anweisungsfolge unterstützt (Pascal: BEGIN ... END, C: { ... }).

Auswahl (Bedingte Verzweigung, Mehrfachauswahl)

Sie ist gekennzeichnet durch einen nicht linearen Ablauf mit einer Vorwärtsverzweigung. Der Ablauf gelangt an einen Entscheidungspunkt, an dem, abhängig von einer Bedingung, unterschiedliche Verarbeitungswege eingeschlagen werden. Das Entscheidungssymbol gibt eine Bedingung an (i. a. ein bedingter Ausdruck), deren Ergebnis ein Wahrheitswert ist (WAHR oder FALSCH).

Wiederholung

Wiederholungsstrukturen ergeben sich, wenn eine Anweisungsfolge zur Lösung einer Aufgabe mehrfach durchlaufen werden soll (z. B. das Bearbeiten aller Komponenten eines Vektors oder Berechnung des Monatslohns aller Mitarbeiter). Es liegt ein nichtlinearer Verlauf mit Rückwärtsverzweigung vor. Die Programmierung einer Wiederholungsstruktur führt zu einer sogenannten "Programmschleife". Wichtig ist die Terminierung der Schleife, d. h. mindestens eine Anweisung muß dafür sorgen, daß nach einer endlichen Zahl von Durchläufen die Bedingung für die Wiederholung nicht mehr erfüllt ist.

Unterablaufstrukturen (Unterprogramme)

Es wurde bereits die Aufteilung von Programmen in einzelne Module angesprochen. Diese Aufteilung auch in einem Programm zu vollziehen erscheint daher wünschenswert. In allen höheren Programmiersprachen und auch im Befehlsumfang nahezu aller Prozessoren ist diese Möglichkeit in Form von Unterprogrammen realisiert. Für die Verwendung von Unterprogrammen (UP) sprechen weitere Gründe:

Ein Unterprogramm muß vor seiner Verwendung vereinbart werden. Die Anweisungsfolge des Unterprogramms wird unter einem möglichst aussagekräftigen Namen zusammengefaßt. Der Aufruf besteht dann nur noch in der Nennung des Unterprogramm-Namens. Dem Unterprogramm können beim Aufruf aktuelle Werte zur Verarbeitung übergeben werden --> Argumente oder Parameter (siehe später).

Einige Programmiersprachen unterscheiden bei Unterprogrammen Prozeduren und Funktionen (z. B. Pascal). Funktionen sind Unterprogramme, die einen Wert zurückliefern und daher auf der rechten Seite einer Wertzuweisung auftreten dürfen (z. B. Y = SIN(X), SIN ist eine Funktion mit einem Real-Argument, die einen Real-Wert zurückliefert). Prozeduren sind Unterprogramme, die keine Wert zurückliefern. Bei anderen Sprachen (z. B. C) gibt es ausschließlich Funktionen. Zusätzlich gibt es einen Datentyp VOID, den "leeren" Datentyp, mit dem Funktionen gekennzeichnet werden, die keinen Wert zurückliefern. Für die technische Realisierung von Unterprogrammen auf Maschinenebene bieten sich zwei Möglichkeiten an:

Anmerkungen:

Darstellung von Algorithmen

Algorithmen lassen sich auf unterschiedliche Weise darstellen:

PAP und Struktogramm werden in der folgenden Beschreibung der Anweisungsstrukturen gezeigt.

1.6.2 Programmablaufplan

Allgemeine Symbole

Sequenz

Einseitige Auswahl

Zweiseitige Auswahl

Mehrfachauswahl

Abweisende Wiederholung

Nichtabweisende Wiederholung

Unterprogramm

1.6.3 Struktogramm

Sequenz

Einseitige Auswahl

Zweiseitige Auswahl

Mehrfachauswahl

Abweisende Wiederholung

Nichtabweisende Wiederholung

Unterprogramm

1.7 Programmentwicklung

Dieser Abschnitt will Ihnen die Techniken der Programmentwicklung ein wenig näher bringen, denn die Programme, die in diesem Skript dargestellt sind, haben wegen ihrer Kürze wirklich nur Beispielcharakter. Bei der Leistungsfähigkeit der heutigen Großrechner können Programmsysteme mit 100 000 oder mehr Zeilen entstehen. Es zeigte sich in den sechziger Jahren, daß die Programme ab einer bestimmten Größe stets Fehler enthielten. Die Fehler ließen sich auch fast nie vollständig beseitigen, weil die Korrekturen neue Fehler zur Folge hatten.

Aus diesem Grund entwickelte sich eine neue Disziplin der Informatik, das "Software Engineering". Im Rahmen dieser Disziplin werden Modelle und Methoden entworfen, mit denen auch große und größte Programmsysteme so geschrieben werden können, daß sie fehlerfrei arbeiten. Die wichtigsten Kriterien, denen solche Programme genügen, sind:

Es ist klar, daß solche Anforderungen besondere Methoden der Programmentwicklung notwendig machen. Die Programmentwicklung beginnt nicht mit der Programmierung, sondern, wie bereits in Abschnitt 1.5 erwähnt, schon lange vorher, die Programmierung ist eine der letzten Stufen der Programmentwicklung. Zuerst muß das programmtechnisch zu lösende Problem genau analysiert werden. Diese Problemanalyse ist auch wieder in einzelne Phasen unterteilt, die ich im folgenden kurz umreißen will. Zuerst wird die gegebene Situation genau untersucht, wobei die Wünsche für die EDV und die Einsatzmöglichkeiten der EDV festgehalten werden (Istanalyse). Ausgehend von der Beschreibung der Probleme wird dann eine Beschreibung der Lösungen für den Anwender und eine Aufgabendefinition für den Hersteller der Software erstellt (Sollkonzept). Nun wird festgestellt, ob es möglich ist, eine derartige Aufgabe überhaupt zu lösen (technische Durchführbarkeit) und ob die gefundenen Lösungen wirtschaftlich sind (ökonomische Durchführbarkeit). Die optimale Lösungsmethode wird vervollständigt (Projektplanung).

Der Aufwand der Vorarbeiten zu einem Programm ist natürlich von der Größe des Projekts abhängig, das Planungsprinzip ist aber auch auf kleine Programme anwendbar. Auf jeden Fall sollten die Aufgabenstellung, die Lösungsmethoden, die Benutzerwünsche, die Qualifikation der Benutzer und die im Rahmen der Problemanalyse zu Tage getretenen Argumente schriftlich fixiert werden.

In diesem Kapitel können wir Sie mit theoretischen Betrachtungen nicht ganz verschonen, aber gerade die in diesem Kapitel unternommenen Betrachtungen sind sehr wichtig für die praktische Programmierarbeit.

Es wurden schon kurz Fehler erwähnt, die sich bei der Erstellung großer Programme einschleichen. Damit Ihnen später nicht das gleiche passiert, wird Ihnen im folgenden Abschnitt gezeigt, wie das Problem und nachher das Programm strukturiert und modularisiert, das heißt in kleinere Teile zerlegt wird. Die Strukturierung wird von C durch das Sprachkonzept unterstützt und gefördert. Im Rahmen der Projektplanung wird die Aufgabe des Programms beschrieben, über die Entwicklung des Programms wollen wir hier sprechen. Anhand eines Beispielprogramms wird demonstriert, wie Sie von der Aufgabenstellung durch schrittweise Verfeinerung des Problems schließlich zu einem fertigen Programm kommen. Die Vorgehensweise -der schrittweisen Verfeinerung- ist immer dieselbe, egal wie groß das Programm wird:

Das Problem wird in einzelne Teilprobleme zerlegt. Dies können Funktionen sein oder aber auch sog. Objekte (Gegenstände). Die Kunst ist es die Zelegung derart intelligent zu gestalten, daß die Teilprobleme möglichst nicht voneinander abhängen (Prinzip der starken lokalen Bindung) und das Teilproblem in sich alleine -ohne Zuhilfenahme der Lösung anderer Teilprobleme der gleichen Zerlegungsstufe- zu lösen ist (Prinzip der möglichst losen Koppelung). Diese so gefundenen Teilprobleme werden weiter zerlegt (verfeinert) bis die einzelnen Verfeinerungsstufen so wenig umfangreich sind, daß sie problemlos programmiert werden können (Top-Down-Design). Diese Methode sichert sauber strukturierte und verifizierbare Programme (später: Objekte), wenn Sie die folgenden Grundregeln beachten.

Jedes Teilproblem hat einen gewissen Abstraktionsgrad, der für alle Probleme etwa gleich ist. Wenn Sie an die Teilprobleme gewisse Anforderungen stellen, wird die Korrektheit des Entwurfs überprüfbar; man sagt, das Programm ist dann verifizierbar. Die Verifizierbarkeit eines Programms ist wohl die wichtigste Folge der strukturierten Programmierung. Die Beschreibung eines Teilproblems besteht aus

Aus dieser Beschreibung lassen sich dann die Voraussetzungen und Anforderungen für die Probleme der nächsten Schicht definieren.

Ein derart beschriebenes Teilproblem wird Programm-Modul, kurz Modul genannt. Ein Modul hat also Eingänge (die Voraussetzungen), Ausgänge (die Ergebnisse) und eine genau festgelegte Funktion mit definierten Operationen.

Zum Schluß dieses Abschnitts will ich noch einige Bemerkungen zu den "Programming Standards" machen. Das sind Vorschriften und Regeln, an die sich alle an einem Projekt beteiligten Programmierer zu halten haben. Diese Regeln können Länge und Komplexität von Unterprogrammen betreffen, sie können Bezeichnungskonventionen oder Schreibweisen betreffen oder auch Regeln für die Erstellung von Kommentaren sein.

Ein Beispiel für einen einfachen "Programming Standard" wäre: "Ein Unterprogramm soll höchstens eine DIN-A4-Seite umfassen. Namen beginnen mit "K-", falls es sich um Konstante handelt. Zu jedem Unterprogramm wird im Kommentar am Anfang des Unterprogramms der Verfasser, das Herstellungsdatum, die Änderungsdaten und eine genaue Beschreibung der Parameter festgehalten. Jeder Sprung ist ausführlich zu kommentieren."

Solche Regeln dienen der übersichtlichen Gestaltung von Programmen und damit auch wieder der Lesbarkeit. In unseren Beispielen folgen wir auch einem gewissen Standard (wenn auch nicht sklavisch) durch Einrücken der einzelnen Strukturelemente. Diese optische Wiederholung der Programmstruktur bringt eine erhebliche Verbesserung der Übersichtlichkeit und so bessere Lesbarkeit. Grundgedanke bei der Erstellung der Einrückungsregeln war, daß Anweisungen, die von anderen Anweisungen kontrolliert werden, um eine feste Anzahl von Spalten eingerückt werden.

Zum Inhaltsverzeichnis Zum nächsten Abschnitt


Copyright © FH München, FB 04, Prof. Jürgen Plate