 |
Algorithmen & Datenstrukturen
|
|
Algorithmen & Datenstrukturen
|
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
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 gestestet 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 Augaben-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.
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ält 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:
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 Zelegung 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 Alogorithmus lautet also:
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ät, welche die Tagessumme der Vormanate berechnen:
Damit ist die Aufgabe sicher zufriedenstellend gelöst.
Es stellt sich die Frage, ob es nich 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 zuviele 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):
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 Ansartz 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:
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 (hoffeltlich) 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:
#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 */
}
Dokumentation: Abschließend faßt man mit der 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 gehen wir nachfolgend ein.
Der Begriff des Unterprogramms (Funktion, Prozedur) entspricht dabei in etwa dem des Moduls. Die bekannteste Schnittstelle ist der Unterprogrammaufruf mit Parameterübergabe.
Dabei soll auf unbedingtes Verzweigen aus einer Struktur heraus verzichtet werden. Jede Programmstruktur bildet einen Strukturblock. Blöcke sind entweder
Die teilweise Einschachtelung (Überlappung) ist nicht zulässig. Sogenannte blockorientierie Sprachen wie Pascal, Modula-2 oder C unterstützen das Prinzip des strukturierten Entwurfs weit mehr als die unstrukturierten Sprachen wie BASIC.
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:
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).
Grundsätzlich lassen sich Programmstrukturen beliebig schachteln, d. h. innerhalb einer Programmstruktur kann wieder eine andere Programmstruktur ausgeführt werden und so fort.
WENN Bedingung DANN Anweisungsfolge;
WENN Bedingung DANN Anweisungsfolge 1 SONST Anweisungsfolge 2;
WENN bedingter
Ausdruck Wert1:
Anweisung1;
Wert2:
Anweisung2; ...;
Wertn:
Anweisungn; SONST Anweisungs;
(Wenn der Ausdruck den Wert "Werti" besitzt, wird die Anweisungsfolge "Anweisungi" ausgeführt).
SOLANGE Bedingung FÜHRE AUS Anweisungsfolge;
FÜHRE AUS Anweisungsfolge BIS Bedingung;
VON Zählvariable = Startwert BIS Zählvariable = Endwert FÜHRE AUS Ink./Dek. Zählvariable, Anweisungsfolge;
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). 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:
WENN x größer 0 DANN "berechne Y" SONST "Fehlermeldung ausgeben"
Also genau das, was im Skript bisher verwendet wurde.
PAP und Struktogramm werden in der folgenden Beschreibung der Anweisungsstrukturen gezeigt.
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:
Die Punkte 2 und 4 sind Ergebnisse der strukturierten Programmierung; Punkte 1 und 3 stellen ein "ungeschriebenes" Gesetz dar. Lesbarkeit ist Voraussetzung für Wartbarkeit.!
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 wir im folgenden kurz umreißen wollen. 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.
Unter einer solchen Schicht können Sie die Beschreibung des Problems in einem bestimmten Abstraktionsgrad verstehen. Sie können sich auch vorstellen, daß auf jeder Schicht ganz bestimmte, abstrakte Grundoperationen existieren. Wenn Sie sich zum Beispiel an den Kreisalgorithmus aus dem ersten Kapitel zurückerinnern, so existiert in einer Schicht die Operation der Multiplikation, in der nächstniedrigeren gibt es die Multiplikation nicht mehr, sondern nur noch die Addition.
Die Grundoperationen werden von Schicht zu Schicht nach unten einfacher. Sie bewegen sich so von sehr abstrakten und komplexen Konstruktionen zu konkreten Operationen. In der Informatik wird eine Schicht als abstrakte Maschine aufgefaßt, also als ein gedachter Computer, der alle Operationen der entsprechenden Detaillierungsstufe beherrscht. Aus diesem Gedankenkonzept folgt sofort, daß auch die Verfeinerung schichtweise geschehen soll. Eine Schicht sollte daher erst vollständig aufgebaut sein, bevor die nächste Verfeinerung in Angriff genommen wird. Diese Vorgehensweise hat einen sehr wesentlichen Vorzug, denn alle Teilprobleme haben etwa den gleichen Abstraktionsgrad und ungefähr den gleichen Umfang. Es kann also nicht vorkommen, daß Sie sich einerseits um die Optimierung eines Algorithmus bemühen, während Sie in einem anderen Teilproblem noch nach dem Lösungsweg suchen. Oder Sie stellen fest, daß ein Teilproblem der Stufe zwei unlösbar ist, während der Rest bereits völlig fertig ist.
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 rnit definierten Operationen.
Zum Schluß dieses Abschnitts wollen wir 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 |