Scribd
Hochladen
3 Ansichten11 Seiten

In Variant e

Das Dokument behandelt die Konzepte von Invarianten und Algorithmenentwurf, wobei Invarianten als grundlegende Gesetze für Algorithmen betrachtet werden. Es wird ein Beispiel zur Wandlung von Dezimalzahlen in eine andere Basis vorgestellt, das die Anwendung von Invarianten und die Struktur von Algorithmen in C demonstriert. Zudem wird ein Programmbeweis zur Validierung der Invarianz während der Ausführung des Algorithmus präsentiert, einschließlich der Herausforderungen bei der Behandlung des Falls Z = 0.

Hochgeladen von

HATIM GHABOUBI
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PPT, PDF, TXT herunterladen oder online auf Scribd lesen
3 Ansichten11 Seiten

In Variant e

Das Dokument behandelt die Konzepte von Invarianten und Algorithmenentwurf, wobei Invarianten als grundlegende Gesetze für Algorithmen betrachtet werden. Es wird ein Beispiel zur Wandlung von Dezimalzahlen in eine andere Basis vorgestellt, das die Anwendung von Invarianten und die Struktur von Algorithmen in C demonstriert. Zudem wird ein Programmbeweis zur Validierung der Invarianz während der Ausführung des Algorithmus präsentiert, einschließlich der Herausforderungen bei der Behandlung des Falls Z = 0.

Hochgeladen von

HATIM GHABOUBI
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PPT, PDF, TXT herunterladen oder online auf Scribd lesen

Invariante und

Algorithmenentwurf
Timm Grams
Hochschule Fulda
Fachbereich Elektrotechnik und
Informationstechnik

© Timm Grams, Fulda, 07.09.02 (6.5.07)


Einführung
Was dem Naturwissenschaftler die Naturgesetze,
das sind dem Informatiker die Invarianten.
Die Invariante erfasst den wesentlichen Kern
eines Algorithmus, sie ist sein „Gesetz“.
Die Invariante ist Grundlage des Algorithmenent-
wurfs.
Bei einem Algorithmus ist konsequent zu unterscheiden
zwischen der Handlungsanweisung und der Invarianten.

Die Handlungsanweisung erfasst den dynamischen, die


Invariante den statischen Aspekt eines Algorithmus.
Beispiel: Zahlenwandlung

Wandlung der Dezimalzahl 202 in die


Darstellung zur Basis 5
Stufe k Relation
0 202 = 20250
1 202 = 4051 + 250
2 202 = 852 + 051 + 250
3 202 = 153 + 352 + 051 + 250
Zahlenwandlung - Operatoren
Die Zahlenwandlung basiert auf der
ganzzahligen Division mit Rest
Die dafür nötigen Operatoren in C sind / und
%
/ ist der Divisionsoperator
% ist der Modulo-Operator zur Bestimmung des Rests

Beispiele: 202/5 = 40 und 202%5 = 2


Fundamentale Formel der ganzzahligen
Arithmetik:
z = ( z /b ) · b + z %b
Invariante und
Endebedingung

Die Invariante ist eine Aussage, die vor


Eintritt in den Rechenschritt eines
Algorithmus erfüllt ist, und die nach dem
Schritt erneut wahr ist.
Der Algorithmus endet, wenn die
Endebedingung erfüllt ist
Grundstruktur von Algorithmen
in C
A
while(B)S A

I
A Initialisierungs-
Anweisungen
I  (B =0)
B Schleifenbedingung. B
Für B  0 wird S I  (B 0)
ausgeführt,
für B = 0
(Endebedingung) nicht S
S Schleifenanweisung
(meist eine I
Verbundanweisung)
Beispiel: Wandlung der
Zahl Z in Darstellung zur
Basis B
k=0;

k=0;
I
while(z){
I  (z =0)
r[k++]=z%b; z
z=z/b; I  (z 0)
}
r[k++]= z%b;
z= z/b;
Invariante: I
b=B
Z = zbk+r[k-1]bk-1+...+r[1]b1+r[0]b0
0 ≤ r[i ] < B für i < k
Programmbeweis mit der symbolischen
Methode 1

Kursive Großbuchstaben bezeichnen mathematische


Variable. Programmfragmente werden in
Anführungszeichen geschrieben. Anfangs sei z=Z und
durchweg gilt b=
b B.
Zu zeigen ist zuerst, dass die Initialisierung
„k=0;“
die Invariante wahr macht. Jedenfalls gilt nach der
Initialisierung z=Z und k=0. Also:
Z =z
= zb0

= zbk + r[k-1]bk-1+...+r[1]b1+r[0]b0
Programmbeweis mit der symbolischen
Methode 2
Im zweite Schritt ist zu zeigen, dass die Anweisungsfolge
„r[k++]=z%b; z=z/b;“
die Invariante erhält: Vor der Anweisungsfolge ist k=K
und z=A. Die Invariante wird zu
Z = AbK+r[K-1]bK-1+...+r[1]b1+r[0]b0
Nach der Anweisungsfolge ist r[K]=A%b, k=K+1 und
z=A/b (ganzzahliger Quotient). Wegen A=(A/b)b+A%b
gilt
Z = ((A/b)b+A%b)
%b bK+r[K-1]bK-1+...+r[1]b1+r[0]b0
= zbK+1 +r[K]bK+r[K-1]bK-1+...+r[1]b1+r[0]b0

= zbk + r[k-1]bk-1+...+r[1]b1+r[0]b0
Programmbeweis mit der symbolischen
Methode 3
Im dritten und letzten Schritt ist zu zeigen, dass aus der
Bedingung I  (z=0) das gewünschte Resultat folgt.
In der Invarianten
Z = zbk + r[k-1]bk-1+...+r[1]b1+r[0]b0
ist z=0 zu setzen. Damit ergibt sich
Z = r[k-1]bk-1+...+r[1]b1+r[0]b0
Das Array r enthält die Zahlendarstellung der Zahl Z zur
Basis B.

Problem

Für Z = 0 ist die Summe


r[k-1]bk-1+...+r[1]b1+r[0]b0
leer. Das ist auch richtig so: Eine leere Summe
hat konventionsgemäß den Wert null.
Aber das Wandlungsprogramm kann mit einer
leeren Summe nichts anfangen.
Was ist zu tun?

Das könnte Ihnen auch gefallen