close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

15.10.2008

EinbettenHerunterladen
Was bisher geschah
Motivation
MS-Excel-Makros aufzeichnen und aufrufen
Programmiersprache VBA
VBA-Entwicklungsumgebung
Struktur von VBA-Projekten
Informatik
Wissenschaft von der Verarbeitung symbolischer Information
durch Algorithmen
Algorithmus = in Schritte geordnete Arbeitsvorschrift
endliche Beschreibung
schrittweise Ausführung
zuständig für eine ganze Aufgabenklasse
deterministisch (vorherbestimmt)
zu jedem Schritt ist im Algorithmus definiert:
Was wird getan? (Aktionen, Anweisungen)
Womit wird es getan? (Daten)
Wie geht es weiter? (nächster Schritt)
Programmierung
Programme (Software) entstehen in zwei Phasen:
1. Konzeption (Kopf, Papier):
Spezifikation
Entwurf
Verifikation
weitgehend unabhängig von Implementierungssprache
Ergebnis: Algorithmus (z.B. als Struktogramm)
2. Implementierung (Computer):
Ergebnis: fehlerfrei übersetzbares und lauffähiges
Programm in einer Programmiersprache
Spezifikation
Problemanalyse: Was soll gelöst werden?
Ausgangspunkt:
Ergebnis:
umgangssprachlich formulierte und oft
ungenaue Beschreibung der Aufgabe
exakte und vollständige Definition der
zu erzeugenden Software
Spezifikation beschreibt die gewünschte Beziehung zwischen
Ein- und Ausgabe
Spezifikation enthält
Vorbedingung: Forderung an die Eingaben
Nachbedingung: Forderung an die Ausgaben
Beispiel: Größter gemeinsamer Teiler
Aufgabe:
Zu zwei natürlichen Zahlen soll ihr größter gemeinsamer Teiler
berechnet werden.
Definitionen:
t ist Teiler von x:
t | x gdw. ∃k ∈
◆:t ·k =x
Menge aller gemeinsamen Teiler von x und y :
T (x, y ) = {t : t | x und t | y }.
größter gemeinsamer Teiler von a und b
ggT(x, y ) = t gdw. t ∈ T (x, y ) und für alle
s ∈ T (x, y ) : s | t}
Spezifikation:
Eingabe: x, y ∈
Ausgabe: ggT(x, y )
◆
Vorbedingungen a = x, b = y
Nachbedingungen a = ggT(x, y )
Entwurf
Wie soll das Problem gelöst werden?
Entwurf eines Algorithmus zur Lösung der Aufgabe:
Eingabe
Ausgabe
endliche Beschreibung von Arbeitschritten:
Was wird getan? (Aktionen, Anweisungen)
Womit wird es getan? (Daten)
Wie geht es weiter? (nächster Schritt)
Auswahl der Datentypen, Programmstrukturen
Beispiel ggT
Idee:
Verwendung der folgenden Eigenschaften des ggT:
ggT(x, x) = x
ggT(x, y ) = ggT(x − y , y ) für x > y
(einfacher) Euklidischer Algorithmus:
1. Eingabe a, b
2. falls a = b Übergang zu Schritt 3, sonst
falls a > b berechne a := a − b
sonst berechne b := b − a
Schritt 2. wiederholen
3. Ausgabe a
Verifikation
Ist der entworfene Algorithmus korrekt?
Erfüllt der entworfene Algorithmus die Spezifikation?
Verifikation wiederholter Anweisungen durch Invarianten
Schleife ist korrekt, wenn für eine geeignete Invariante gilt:
1. aus der Vorbedingung folgt die Invariante
2. gilt die Invariante und die Bedingung für Wiederholung,
dann gilt die Invariante auch nach Ausführung der zu
wiederholenden Schritte
3. gilt die Invariante und die Bedingung für Wiederholung
nicht, gilt die Nachbedingung
Beispiel ggT
Spezifikation:
Eingabe: x, y ∈
Ausgabe: ggT(x, y )
Vorbedingungen: a = x und b = y
Nachbedingungen: a = ggT(x, y )
◆
Euklidischer Algorithmus:
1. Eingabe a, b
2. falls a = b Übergang zu Schritt 3, sonst
falls a > b berechne a := a − b
sonst berechne b := b − a
Schritt 2. wiederholen
3. Ausgabe a
Invariante : ggT(a, b) = ggT(x, y )
Verifikation (Tafel)
Beispiel ggT - Verifikation
1. aus Vorbedingung folgt Invariante
aus a = x und b = y folgt ggT(a, b) = ggT(x, y )
2. gilt die Invariante und die Bedingung für Wiederholung,
dann gilt die Invariante auch nach Ausführung der zu
wiederholenden Schritte
aus ggT(a, b) = ggT(x, y ) und a = b folgt
falls a > b berechne a := a − b
ggT(a, b) = ggT(x − y , y ) = ggT(x, y )
sonst berechne b := b − a
ggT(a, b) = ggT(x − y , y ) = ggT(x, y )
3. gilt die Invariante und die Bedingung für Wiederholung
nicht, folgt die Nachbedingung
aus ggT(a, b) = ggT(x, y ) und a = b folgt
a = ggT(a, a) = ggT(a, b) = ggT(x, y ))
Beispiel: Vertauschen mit Hilfsvariable
Aufgabe: Vertauschen zweier Zahlen
Spezifikation:
Vorbedingung:
Nachbedingung:
Algorithmus:
1. c := a
2. a := b
3. b := c
Verifikation (Tafel)
a = x, b = y
a = y, b = x
Implementierung
technische Realisierung des des entworfenen und verifizierten
Algorithmus
Übertragung in Programmiersprache
Ergebnis: ausführbares Programm
Document
Kategorie
Technik
Seitenansichten
7
Dateigröße
51 KB
Tags
1/--Seiten
melden