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 ?