G.Heyer Digitale Informationsverarbeitung1
Pascal-Datentypen
Skalare Typen
Strukturierte Typen
Zeiger-Typen
REAL Aufzählungs-typen
BOOLEAN
INTEGER
CHAR
SelbstvereinbarteTypen
Unterbereichs-typen
HomogeneTypen
InhomogeneTypen
Verbunde
Felder
Mengen
Dateien
G.Heyer Digitale Informationsverarbeitung2
14. Implementierung und Entwurf
Die Tätigkeit der Implementierung beinhaltet u.a. folgende Einzelaktivitäten:
• Konzeption von Datenstrukturen und Algorithmen• Strukturierung des Programms durch geeignete Verfeinerungsebenen• Dokumentation der Problemlösung und der Implementierungsentscheidungen
durch geeignete Verbalisierung und Kommentierung• Umsetzung der Konzepte in die Konstrukte der verwendeten
Programmiersprache• Angaben zur Zeit- und Speicherkomplexität des Programms in Abhängigkeit
von den Eingabegrössen• Test oder Verifikation der entwickelten Programmes einschliesslich
Testplanung und Testfallerstellung bei Anwendung einer Testmethode
Ergebnisse der Implementierung:• Quellprogramm einschliesslich integrierter Dokumentation• Objektprogramm• Testplanung und Testprotokoll bzw. Verifikationsdokumentation
G.Heyer Digitale Informationsverarbeitung3
Entwurf von Algorithmen
Kreativer Prozeß, der nicht automatisiert werden kann.
Lösungsheuristik:
- Ist dasselbe Problem oder ein ähnliches bzw. vergleichbares Problem bekannt?
Wenn ja, dann versuche man, Kenntnisse über die Lösung dieser Probleme zu erhalten. Man prüfe, ob das gegebene Problem als Sonderfall des allgemeinen Problems behandelt werden kann. Wenn ja, dann wende man die allgemeine Problemlösung an.
Wenn sich das Problem verallgemeinern läßt, ohne daß die Lösung erheblich schwerer wird, dann löse man das allgemeinere Problem.
- Läßt sich das Problem in ein einfacheres Teilproblem oder in mehrere einfachere, in sich geschlossene Teilprobleme aufteilen? Wenn ja, dann teile man das Problem auf und formuliere die Problemstellung der Teilprobleme.
- Man stelle einen in Schritten gegliederten Lösungsplan auf. Sind Teilprobleme zu lösen, dann nehme man für jedes Teilproblem einen Schritt.
G.Heyer Digitale Informationsverarbeitung4
Entwurf der Datenstrukturen
- Wesentlicher Teil der Entwicklung eines Algorithmus
- Datenstrukturen bestimmen weitgehend die Möglichkeiten der
Modularisierung und die Wahl der Kontrollstrukturen
- Entwurf von Datenstrukturen für die Eingabe, Verarbeitung (ggf. mehrere
Transformationen der inneren Datenstrukturen) und Ausgabe
G.Heyer Digitale Informationsverarbeitung5
Weitere Entwurfskonzepte
• Modularität: die Komplexität großer Softwaresysteme beherrschbar nur durch Komposition aus kleineren Einheiten (Modulen)
– Module können unabhängig voneinander entwickelt und validiert werden– (Dienst-) Module stellen (Kunden-) Modulen Dienstleistungen zur
Verfügung– Interaktion zwischen Modulen nur in streng kontrollierter Form
• Information hiding: Wie die Leistungen eines Moduls erzielt werden, bleibt für andere Module verborgen (man spricht auch von Kapselung).
– Vorteil: Änderungen eines Moduls erfordern nicht Änderungen in anderen Modulen
• Die Schnittstelle (Interface) eines Moduls beschreibt die von ihm bereitgestellten Dienstleistungen, die (für andere Module verborgene) Implementierung, wie diese erzielt werden
– Module in modernen Programmiersprachen können unabhängig voneinander kompiliert und getestet werden
G.Heyer Digitale Informationsverarbeitung6
Wichtige Entwurfsregeln
Voraussetzungen
- Festlegen der Bedingungen, unter denen der Algorithmus arbeiten soll
- Spezifikationsregel: Lege Eingabe (E) und Ausgabe (A) des Algorithmus fest und beschreibe ihre funktionale Abhängigkeit.
Vorgehensweise beim Entwurf
Zerlegungsregel: Entwerfe einen Algorithmus durch Zerlegen des Problems in (bekannte) Teilprobleme und setze die Teillösungen zur Gesamtlösung zusammen.
Verifikation des Entwurfs
- Terminierung
- Korrektheit
- Verifikationsregel: Weise nach, daß der Entwurf eines Lösungsverfahrens ein Algorithmus ist, der den Spezifikationen genügt und terminiert.
Aufwandsabschätzung
Aufwandsregel: Gib in Abhängigkeit von den E- und A-Größen Schranken für den Zeit- und Speicheraufwand an.
G.Heyer Digitale Informationsverarbeitung7
Prinzipien der Strukturierung
Bei der Implementierung sollten folgende Prinzipien eingehalten werden:
• Prinzip der Verbalisierung• Prinzip der problemadäquaten Datentypen• Prinzip der Verfeinerung• Prinzip der integrierten Dokumentation
Verbalisierung beinhaltet, die Ideen und Konzepte des Programmierers im Programm möglichst gut sichtbar zu machen und zu dokumentieren. Dies kann erreicht werden durch
– aussagekräftige, mnemotechnische Namensgebung– geeignete Kommentare– selbstdokumentierende Programmiersprache
Vorteile: verbesserte Lesbarkeit der Programme, leichte Einarbeitung in fremde bzw. Wiedereinarbeitung in eigene Programme, erleichterte code reviews, Modifikation und Wartung,
G.Heyer Digitale Informationsverarbeitung8
Prinzipien der Strukturierung
Problemadäquate Datentypen beinhaltet, das Angebot an Konzepten einer Programmiersprache optimal zur problemnahen Lösungsformulierung zu verwenden.
– Basistypen– Felder– Verbunde
Vorteile: gut verständliche und wartbare Programme, statische und dynamische Typprüfungen verbessern die Qualität der Programme, die Daten des Problems werden 1:1 in Datentypen des Programms abgebildet (weder Über- noch Unterspezifizierung)
G.Heyer Digitale Informationsverarbeitung9
Prinzipien der Strukturierung
Das Prinzip der Verfeinerung dient dazu, ein Programm durch Abstraktionsebenen zu strukturieren.
Die oberste Verfeinerungsebene - bestehend aus abstrakten Daten und abstrakten Anweisungen - ist kompakt beschrieben. Die Realisierung jeder Verfeinerung wird an anderer Stelle beschrieben.
Vorteile: – der Entwicklungsprozess ist im Quellprogramm dokumentiert– leichtere und schnellere Einarbeitung in ein Programm– die Entwicklungsentscheidungen können besser nachvollzogen werden– die oberen Verfeinerungsschichten können in natürlicher Sprache
formuliert werden– ein Programm wird zweidimensional strukturiert: sowohl durch
Kontrollstrukturen als auch durch Verfeinerungsschichten
G.Heyer Digitale Informationsverarbeitung10
Prinzipien der Strukturierung
Integrierten Dokumentation umfasst• die Angabe von Verwaltungsinformationen• Beschreibung der Entwicklungsentscheidungen
Ziel: • Erleichterung der Einarbeitung
//Programmname: XYZ//************************************************************//Autor 1: Vorname Nachname//Autor 2: Vorname Nachname//************************************************************//Version: V1.0 in Bearbeitung 15.10.1999// vorgelegt 30.10.1999// akzeptiert 5.11.1999//Version: V1.1 in Bearbeitung 15.11.1999// vorgelegt 30.11.1999//************************************************************//Aufgabe:////************************************************************//Zeitkomplexität: O(n log 2n)//Speicherkomplexität: O(2n)//************************************************************
G.Heyer Digitale Informationsverarbeitung11
Methode der schrittweisen Verfeinerung
Top-down Methode für die “Programmierung im Kleinen” (Wirth, Dijkstra)
• 1. Schritt: Abstrakte Problemlösung• 2. Schritt: Definition der Typen, Daten und Anweisungen• 3. Schritt: Sukzessive Zerlegung und Substitution der abstrakten Definitionen
bis alle Typen, Daten und Anweisungen in Termen der verwendeten Programmiersprache beschrieben sind.
Vorgehen: • Daten und Anweisungen sollen parallel verfeinert werden• Es soll so lange wie möglich eine Notation benutzt werden, die das Problem in
natürlicher Form beschreibt• Abstrakte Anweisungen, die durch Auswahl- oder Wiederholungsstrukturen
realisiert werden, sollten zuerst verfeinert werden• Entscheidungen über die Datenrepräsentation sollten solange wie möglich
aufgeschoben werden• Während der Verfeinerung werden Hilfsobjekte eingeführt• Jede Verfeinerung impliziert Implementierungsentscheidungen, die explizit
dargelegt werden sollten• Ausgeprägte Verbalisierung erforderlich
G.Heyer Digitale Informationsverarbeitung12
Häufige Probleme mit Namen
Gibt es in ihrem Programm wirklich keine Namen, die ...
... irreführend sind ?
... eine ähnliche Bedeutung haben ?
... sich nur in ein oder zwei Zeichen voneinander unterscheiden ?
... ähnlich klingen ?
... Zahlen enthalten ?
... absichtlich falsch geschrieben wurden, um sie abzukürzen ?
... gern falsch geschrieben werden ?
... zu einem Konflikt mit Namen von Standard-Bibliotheksroutinen oder mit vordefinierten Variablennamen führen ?
... völlig willkürlich sind ?
... Zeichen enthalten, die schwer auseinanderzuhalten sind ?
G.Heyer Digitale Informationsverarbeitung13
Gute Namen
Name: Orientierung auf das Problem (und nicht die Lösung)
Länge: optimale Länge 10-16 Zeichenlänger: globale Variable, selten gebräuchlichkürzer: lokale Variable, Schleifen
Konventionen für Namensgebung erforderlich - bei mehreren Programmierern
- für bessere Wartung, Strukturierung
allg. Konventionen1) Globale Variable kennzeichnen2) Variable auf Modulebene kennzeichnen3) Typdefinitionen-Konvention4) Konstanten-Konvention5) Aufzählungstypen6) ausschließliche Eingabeparameter7) Formatierung von Namen
G.Heyer Digitale Informationsverarbeitung14
(Lästige) Fragen zu Namen
•Beschreibt der Name den Sachverhalt, den die Variable repräsentiert, vollständig und genau?
•Verweist der Name auf einen Sachverhalt „aus dem wirklichen Leben“, statt sich an Details der Programmiersprache anzulehnen ?
•Ist der Name so lang, daß seine Bedeutung sofort klar zutage tritt ?
•Befinden sich Bezeichner für berechnete Werte (falls vorhanden ) am Ende des Namens ?
G.Heyer Digitale Informationsverarbeitung15
Namen für einzelne Variablenarten
•Haben Sie sich für Schleifenindizes etwas Sinnvolleres einfallen lassen als i, j, oder k ? (Trifft für größere oder verschachtelte Schleifen zu.)
•Haben Sie sämtlichen „temporären“ Variablen sinnvollere Namen als temp gegeben?
•Ist klar, wenn Boolesche Variablen den Wert True haben ?
•Haben Aufzähltypen ein Prä- oder Suffix, das auf die Kategorie verweist - etwa Farbe für FarbeRot, FarbeGruen, FarbeBlau usw. ?
•Verweisen benannte Konstanten eher auf die abstrakten Sachverhalte, die sie repräsentieren, als auf die Zahlen, für die sie stehen ?
G.Heyer Digitale Informationsverarbeitung16
Noch mehr Fragen
•Ermöglicht es die Konvention, zwischen lokalen, modulbezogenen und globalen Variablen zu unterscheiden?
•Gestattet die Konvention eine Unterscheidung zwischen Typennamen, benannten Konstanten, Aufzählungstypen und Variablen ?
•Kennzeichnet die Konvention unveränderliche Eingabeparameter von Routinen? (Trifft für Sprachen zu, die eine solche Kennung nicht von Haus aus erzwingen.)
•Verträgt sich die Konvention gut mit den Standardkonventionen der Sprache?
•Sind die Namen so formatiert, daß eine gute Lesbarkeit erreicht wird ?
G.Heyer Digitale Informationsverarbeitung17
Beispiele für gute Namen
Zweck der Variablen Gute Namen Schlechte Namen
Laufende LaufendeKontrollnr, Kontrollen,
Kontrollnummer LfdKontrollNr, X, X1, X2
nKontrollen
Geschwindigkeit Geschwindigkeit, Gesch, v
eines Zuges ZugGeschwindigkeit, X, X1, X2,
GeschwindigkeitInKmh Zug
Gegenwärtiges Heute, GegenwDatum GD, Datum, X, X1, X2
Datum
Zeilen je Seite ZeilenJeSeite ZjS, Zeilen, Z
X, X1, X2
G.Heyer Digitale Informationsverarbeitung18
Beispiel einer Namenskonvention für Pascal
Name Erläuterung
LokaleVariable Lokale Variable werden in gemischter Klein- und
Großschreibung angegeben. Der Name soll den
Sachverhalt, für den die Variable steht, wiedergeben
und keinerlei Bezüge auf den zugrundeliegenden
Datentyp haben.
RoutinenName () Routinennamen werden in gemischter Klein- und
Großschreibung angegeben.
m_ModulVariable Variablen, die allen Routinen eines Moduls zur
Verfügung stehen und nur diese erhalten das Präfix m_
G.Heyer Digitale Informationsverarbeitung19
Beispiel einer Namenskonvention für Pascal (2)
Name Erläuterung
g_Globale Variable Globale Variable erhalten das Präfix g_
Konstante_c Benannte Konstanten erhalten das Suffix _c
Typ_t Typen enden auf _t
Basis-Aufzähltyp Aufzähltypen werden mit einem Präfix versehen, das
auf den Basistyp verweist.
Beispiel: Farbe_Rot, Farbe_Blau
G.Heyer Digitale Informationsverarbeitung20
Letzte Fragen
•Verwenden Sie lange Namen (falls kurze Namen nicht unbedingt nötig sind) ?
•Machen Sie einen Bogen um Abkürzungen, bei denen nur ein einziger Buchstabe eingespart wird ?
•Werden die Wörter einheitlich abgekürzt ?
•Haben Sie unaussprechliche Namen vermieden ?
•Haben Sie keine Namen eingeführt, die gerne falsch geschrieben werden ?
•Werden kurze Namen in Übersetzungstabellen dokumentiert ?