Informatik - Skript zum Unterricht
(II) Software
3. Programmentwicklung
3.1 Implementierung
Bei der Implementierung wird eine abstrakte Beschreibung des Problems (erstellt in der Designphase) in ein Programm in einer spezifischen Programmiersprache überführt. Dieser Prozess wird in der folgenden Grafik veranschaulicht.
3.2 Grafische Darstellung der Algorithmen
Grafische Ablaufdarstellungen können unter den Begriffen Programmablaufplan (PAP), Flussdiagramm, Struktur- oder Blockdiagramm zusammengefasst werden.
Ein Ablaufplan stellt eine grafische Veranschaulichung der Algorithmenstruktur durch entsprechende, standardisierte Operationssymbole dar. Die gebräuchlichsten Formen von Programmablaufdarstellungen sind:
1. Sinnbilddarstellung (Blockbild, Blockdarstellung)
2. Programmlinienstruktur (Programmablaufplan im engeren Sinn)
3. Struktogramm
4. Petri-Netz
Die Auswahl der grafischen Darstellungsform ist von mehreren Faktoren abhängig. Wird eine schnell zu erarbeitende Flussdarstellung erforderlich, ist die Programmliniendarstellung vorteilhaft, da das Zeichnen der geometrischen Figuren der Sinnbilddarstellung entfällt. Diese Darstellungsformen verführt jedoch dazu, mit zahlreichen Einzelverzweigungen zu arbeiten, die nicht mehr der Gesamtstruktur untergeordnet sind (sog. Spaghetticode). Eine gut strukturierte Programmierung wird durch das Struktogramm begünstigt. Allerdings führen umfangreichere Programme in dieser Darstellungsmethode wieder zu schwer lesbaren Übersichten.
Um gut strukturierte Programme entwickeln zu können, werden heutzutage i.A. den Struktogrammen der Vorrang gegeben.
3.3 Struktogramm und Programmablaufplan
Die Programmdokumentation ist eine notwendige Voraussetzung zur Entwicklung und Wartung eines Programms. Vor allem müssen die Programme grafisch dargestellt werden, weil nur so ein Überblick möglich ist. Speziell dafür verwendet man genormte Sinnbilder nach DIN 66001 (Programmablaufplan) oder auch DIN 66261 (Struktogramm nach Nassi und Schneiderman).
Weiter führende Informatitonen finden Sie in Wikipedia
Struktogramm
Programmablaufplan
3.4 Schritte der Programmentwicklung
Die Lösung eines Problems mit Hilfe eines Computers kann in folgende Schritte eingeteilt werden.
- 1. Problemstellung
- 2. Problempräzisierung bzw. -analyse / mathematisches Modell
- 3. Formulierung des Algorithmus mit Hilfe des EVA-Prinzips
- 4. grafische Darstellung des Algorithmus
- 5. Nachweis der Leistungsfähigkeit des Algorithmus
- 6. Umsetzung des Algorithmus in eine Programmiersprache durch die Formulierung des Quelltextes
- 7. Programmtest
- 8. Bewertung des Algorithmus nach Zeitkomplexität und Speicherkomplexität
- 9. lauffähiges Programm bzw. ausführbare Datei
- 10. Erstellung der Programmdokumentation
Die Schritte werden zwar der Reihe nach durchlaufen, es kommen aber von jedem Schritt Rücksprünge zu vorangegangenen Schritten vor (Rückkopplung). Darüber hinaus ist es vom Problem abhängig, wie umfangreich ein Schritt ausfällt. Hierbei ist es auch möglich, dass die Reihenfolge variiert, ein Schritt in einen anderen integriert wird bzw. entfällt.
Grob kann man für die Algorithmusformulierung ein Drittel, für die Umsetzung in eine Programmiersprache mit Fehleranalyse ein weiteres Drittel und die Bewertung des Algorithmus mit Programmdokumentation das letzte Drittel des gesamten Zeitaufwandes ansetzen.
3.5 Beispiel der Programmentwicklung
Bei der Umsetzung des Beispiels ging es nicht darum, die optimale Programmierung, sondern ein verständliche Lösung anzugeben.
3.5.1 Problemstellung
Vater Max richtet seinem Sohn Otto bei dessen Geburt zu einem fest vereinbarten Zinssatz p ein Konto ein, indem er G € einzahlt. Dieses Konto bleibt n Jahre unangetastet.
3.5.2 Problempräzisierung bzw. -analyse / mathematisches Modell
Aus der Problemstellung lassen sich Aufgaben ableiten, wobei im folgenden nur die Aufgabe 1 näher betrachtet werden soll.
| Aufgabe 1: | Wie hoch ist das Kapital nach n Jahren? |
| Aufgabe 2: | Nach wie viel Jahren hat sich das eingezahlte Kapital verdoppelt? |
Verfahren: Zinsrechnung (Zinseszins)
3.5.3 Formulierung des Algorithmus mit Hilfe des EVA-Prinzips
In diesem Beispiel wird die mathematisch rekursive Berechnung mit Hilfe einer Schleife durchgeführt, da dieser Lösungsweg einfach auf die zweite Aufgabe zu übertragbar ist. Die explizite Berechnung des Kapitals wird zur Kontrolle verwendet.
Algorithmus: Eingabe Kapital K
Anzahl der Jahre n
Zinssatz p
Verarbeitung wiederhole
K := K + G × z/100
(neues Kapital := altes Kapital + Zinsen)
i := i + 1 (Zähler für die durchlaufenen Jahre)
solange, bis i >= n
Ausgabe neues Kapital K
3.5.4 grafische Darstellung des Algorithmus
3.5.5 Nachweis der Leistungsfähigkeit des Algorithmus
Es wird ein Testdurchlauf (Trockentest) für 10 Jahre mit einem Startkapital von 100€ und einem Zinssatz von 5% durchgeführt.
3.5.6 Umsetzung des Algorithmus in eine Programmiersprache durch die Formulierung des Quelltextes
Nachfolgend wurde als Beispiel die Programmiersprache Turbo Pascal ausgewählt.
program Vater_Max;
uses crt;
var Jahre, i :byte;
Kapital, Zins :real;
begin
clrscr;
Write('Kapital in Euro = '); readln(Kapital);
Write('Laufzeit in Jahren = '); readln(Jahre);
Write('Zinssatz in Prozent = '); readln(Zins);
Writeln;
i:=0;
repeat
Kapital:=Kapital+Kapital*Zins/100;
i:=i+1;
until i=Jahre;
Write('Das Kapital beträgt nach ',Jahre,' Jahren ', Kapital:10:2,' DM');
end.
3.5.7 Programmtest
Ein Programmtest muss mit verschiedene Werten durchgeführt werden. So ist es notwendig, Grenzfälle (n=0, K=0 oder p=0) zu untersuchen, um Laufzeitfehler bzw. logische Fehler zu vermeiden. Syntaxfehler (Schreibfehler) werden i.A. durch den eingesetzten Compiler oder Interpreter angezeigt.
3.5.8 zeit- und speicherkomplexe Bewertung des Algorithmus
Die Zeitkomplexität setzt sich aus Elementaroperationen zusammen. Generell wird jeder Rechenschritt des Computers, z.B. eine Addition oder der Aufruf eines Unterprogramms, als ein Schritt gewertet. Wird eine Schleife n-mal durchlaufen, so ergeben sich (abgesehen von den Operationen, die innerhalb der Schleife zusätzlich anfallen) n Schritte für den Algorithmus. Zur Initialisierung einer Schleife ist gewöhnlich eine konstante Zahl c von Schritten nötig, für den Schleifendurchlauf werden in der Regel konstant d Schritte benötigt, so dass bei n-maligem Durchlauf ein Aufwand von d×n+c entsteht.
Die Zeitkomplexität ist in diesem Fall eine lineare Funktion, d.h. die Anzahl der Schritte steigt proportional
zur Anzahl der Jahre. Bei Verwendung der expliziten Berechnungsmöglichkeit
(
)
muss in Turbo Pascal berücksichtigt werden, dass hier keine Potenzfunktion zur Verfügung steht. Diese kann z.B. mit
Hilfe einer Schleife emuliert werden, so dass sich die Zeitkomplexität bei Verwendung diese mathematischen Modells
nur unwesentlich ändert.
Die Speicherkomplexität ist in diesem Beispiel der Zeitkomplexität untergeordnet. Durch die Wahl nur einer
Variable K (Kapital) werden bei der Wertzuweisung
3.5.9 lauffähiges Programm bzw. ausführbare Datei
Der Quelltext liegt in Turbo Pascal vor. Mit Hilfe des Compilers kann eine ausführbare, für das entsprechende Betriebssystem lauffähige Datei erzeugt (compiliert) werden, die den Anforderungen genügt.
3.5.10 Erstellung der Programmdokumentation
Die Dokumentation muss eine Programmbeschreibung, Zielangabe, Variablenbelegung, Fehlerbetrachtung, Programmerweiterungsmöglichkeiten u.a. enthalten.
