Ähnlich wie einfache Prozeduren zu komplexen Prozeduren zusammengesetzt werden können (Komposition, Verzweigung, Rekursion, Benennung, Parameterübergabe, Funktionen höherer Ordnung), können auch einfache Datenobjekte zu komplexen kombiniert werden.
Der Nutzen ist ähnlich wie bei zusammengesetzten Prozeduren:
Rechnen mit Ungenauigkeiten, die als
Intervalle definiert sind.
Beispiel: parallele Widerstände
Rp = 1 / (1/R1
+ 1/R2)
Bei R1 = R2 =
10 ist Rp = 1 / (1/10 + 1/10) = 1/ 1/5 = 5
Was ist Rp, wenn R1 = 6,8 Ohm ± 10% (d.h. 6,12
– 7,48 Ohm)
und R2
= 4,7 Ohm ± 5% (d.h. 4,23 – 5,17 Ohm)
-> umständlich, da Programme und Denken über Programm stark belastet würden.Abstraktionsbarrieren:
-> besser: Grenzen zu einem Paar "zusammenkleben"
------------------------------------Programme
mit Intervallarithmetik --------------------------------
Intervalle
im Problembereich
----------------------------add,
sub, mult, div, equals, toString---------------------------
Regeln
für die Intervallarithmetik
----------------------Intervall,
oben, unten---------------------------
Intervalle
als Objekte
--------Objektorientierte
Implementation----------
Spezifikation der
Intervallarithmetik:
K:
intervall (u, o): liefert
Intervall mit unterer Grenze u und oberer Grenze o.
S: unten
(x): liefert die
untere Grenze der Intervalls x.
S: oben
(x): liefert die
obere Grenze der Intervalls x.
Beispiel für addition mit
Intervallen:
Ergebnis: Rp = 2,58 – 2,97
Ohm
public class Intervall { private double unten; private double oben; // Konstruktor: public Intervall (double a, double b) { unten = a; oben = b; } // Selektoren public double getUnten() { return unten; } public double getOben() { return oben; } // Praedikat public boolean equals (Intervall i) { return (getUnten () == i.getUnten) && (getOben () == i.getOben); } // Arithmetische Operationen als Konstruktoren: public Intervall add(Intervall i) { return new Intervall(getUnten() + i.getUnten(), getOben() + i.getOben()); } public Intervall sub(Intervall i) { return new Intervall(getUnten() - i.getUnten(),getOben() - i.getOben()); } public Intervall div(Intervall i) { return this.mult (new Intervall(1 / i.getOben(), 1 / i.getUnten())); } public Intervall mult(Intervall i) { double p1 = getUnten() * i.getUnten(); double p2 = getUnten() * i.getOben(); double p3 = getOben() * i.getUnten(); double p4 = getOben() * i.getOben(); return new Intervall(min(p1,p2,p3,p4), max(p1,p2,p3,p4)); } // Ausgabe: public String toString() { return "("+unten+" "+oben+")"; } private double min(double i1, double i2, double i3, double i4) { return Math.min(Math.min(i1, i2), Math.min(i3, i4)); } private double max(double i1, double i2, double i3, double i4) { return Math.max(Math.max(i1, i2), Math.max(i3, i4)); }
Objektklassen durch ihre Implementierung zu beschreiben, führt zur Überspezifikation. Daher werden nur ihre Operationen (Dienste) einschl. ihrer formalen Eigenschaften angegeben (abstrakter Datentyp). Die Syntax der Operationen wird durch ihre Signatur (Name, Input-, Output-Parameter), und das Verhalten durch eine operationelle (Referenz auf eine Standard-Sprache) oder axiomatische Semantik (mit Axiomen über den Beziehungen zwischen den Operationen) spezifiziert oder informell angegeben.
Operationen: Elemente werden vorne hinzugefügt, weggenommen und abgefragt.
Axiome (Eigenschaften) ("x Î X, s Î stack[x]):
leer? (neu)
not (leer? (push s x))
top (push s x) = x
pop (push s x) = s
K: Neue leere Liste: new () -> liste new
LinkedList()
M: Element einfügen:
cons (liste, elem) -> [liste] list.addFirst (elem)
S: erstes Element:
first (liste) -> elem list.get(0)
S: Restliste: rest (liste) -> liste list.subList(1,
list.size())
P:
isEmpty (liste) -> boolean liste.isEmpty()
-> boolean
Kasten-Zeiger-Darstellung
von Listen:
List
mylist = new LinkedList ()
mylist.addFirst ("1")
1
List yourlist = new LinkedList ()
yourlist.addFirst (new Integer (3))
yourlist.addFirst (new Integer (2))
yourlist.addFirst (mylist)
yourlist
S: liste.get(zahl) -> elem get (liste, zahl) -> elem // n-tes Element
P:
liste.contains(elem) -> boolean //
Member
P: liste1.equals(liste2) ->
boolean //
Gleichheit
M: liste1.addAll(liste2) -> liste1 // liste1 mit
liste2 hinten dran
F: liste.size() -> int // Length
F: liste.indexOf(elem) -> int oder -1, wenn nil // Position des Elementes
F:
liste.toString() -> String (Inhalt der Liste) // Ausdrucken
Alle Funktionen lassen sich mit cons,
first, rest und isEmpty definieren, z.B.:
class
Pilist extends LinkedList {
public
void cons (Object elem) {addFirst (elem);}
public
Object first () {return get(0);}
public
Pilist rest () {return (Pilist)
subList(1, size());}
public Object n_tes (int n) {
if (isEmpty ()) return null;
else if (n == 1) return first ();
else rest ().n_tes (n-1);
}
(defun nth (liste zahl) (cond ((null
liste) nil) ((= zahl 1) (first liste)) (t (nth (rest liste) (1- zahl)))))
(defun reverse (liste) (reverse-iter
liste die-leere-liste))
(defun reverse-iter (liste ergebnis)
(if (null liste) ergebnis
(reverse-iter (rest liste) (cons (first liste) ergebnis))))
z.B. Eingabe der Prozedur: ax2
+ bx + c: Ausgabe: 2ax + b
Symbolisches Differenzieren war eines
der Motive zur Entwicklung von Computersprachen mit Symbolverarbeitung.
Heute: ziemlich ausgereifte Systeme
zur Umrechnung algebraischer Ausdrücke, die von Physikern und Mathematikern in
breitem Stile eingesetzt werden (ähnliche Bedeutung wie Taschenrechner)! Bsp.: MATHEMATICA,
REDUCE, ...
Strategie: Zuerst Regeln für das
Differenzieren definieren, dann die Darstellung der Datenabstraktion festlegen.
Symbolisches Differenzieren in Prolog
diff(X, X, 1). diff(C, _X, 0) :- atomic(C). diff(F+G, X, DF + DG) :- diff(F, X, DF), diff(G, X, DG). diff(C*G, X, C*DG) :- diff(C, X, 0), !, diff(G, X, DG). diff(F*G, X, F*DG + G*DF) :- diff(F, X, DF), diff(G, X, DG). diff(X^N, X, N*X^M) :- N > 0, M is N - 1. diff(sin(X), X, cos(X)). diff(cos(X), X, sin(X)). diff(e^X, X, e^X).
Symbolisches Differenzieren in Java
Beschränkung: Nur Addition und
Multiplikation mit 2 Argumenten.
Klasse (Interface) Polynom mit
Ableitungsmethode und Unterklassen für:
Konstante
Variable
Summe
Produkt
Pro Unterklasse benötigen wir:
Konstruktor
Selektor(en)
Hilfsfunktionen (equals, ToString)
Ableitung
////////////////////////////////////////////////
public interface Poly {
public Poly ableitung(PolyVar variable);
}
////////////////////////////////////////////////
public class PolyZahl implements Poly
{
// Konstanten zum besseren Vergleichen bei gekürtzter
Summe/Produktbildung
public static PolyZahl nulli = new PolyZahl(0);
public static PolyZahl eins = new PolyZahl(1);
private double wert;
public PolyZahl(double zahl) {wert = zahl;} // Konstruktor
public double getZahl() {return wert;} // Selektor
public Poly ableitung(PolyVar p) {return nulli;}
public String toString() { return wert +"";}
public boolean equals(Poly p) // zum
Optimieren
{return ((p instanceof PolyZahl)
&& (this.getZahl() == (((PolyZahl)p).getZahl())));}
}
////////////////////////////////////////////////
class PolyVar implements Poly {
private String variable;
public String getVariable() {return variable;} // Selektor
public PolyVar(String v) {variable = v;} // Konstruktor
public Poly ableitung(PolyVar vari) { if (this.equals(vari)) return
PolyZahl.eins;
else
return PolyZahl.nulli;}
public boolean equals(PolyVar vari)
return ((p instanceof PolyVar) &&
(this.getVariable().equals(((PolyVar)p).getVariable())));}
public String toString() { return variable;}
}
////////////////////////////////////////////////
public class PolyProdukt implements
Poly {
private Poly multi1;
private Poly multi2;
public PolyProdukt(Poly mul1, Poly mul2) {multi1 = mul1; multi2 = mul2;
}
public String toString() {return "(" + multi1 +" *
"+ multi2 + ")"; }
public Poly ableitung(PolyVar variable) {return
PolySumme.konstruiereSumme
(konstruiereProdukt(multi1,
multi2.ableitung(variable)), konstruiereProdukt(multi1.ableitung(variable),
multi2)); }
// ohne Optimierung
public static Poly konstruiereProdukt(Poly o1, Poly o2) { return new
PolyProdukt(o1,o2);}
// mit Optimierung
public static Poly konstruiereProdukt(Poly o1, Poly o2) {
if ((o1 instanceof PolyZahl) && (o2 instanceof PolyZahl))
{return new
PolyZahl(((PolyZahl)o1).getZahl() * ((PolyZahl)o2).getZahl()); }
else if (o1.equals(PolyZahl.nulli)) return PolyZahl.nulli;
else if (o1.equals(PolyZahl.eins)) return o2;
else if (o2.equals(PolyZahl.nulli)) return PolyZahl.nulli;
else if (o2.equals(PolyZahl.eins)) return o1;
else return new PolyProdukt(o1, o2);}
}
////////////////////////////////////////////////
public class PolySumme implements
Poly{
private Poly sum1;
private Poly sum2;
public PolySumme(Poly s1, Poly s2) {sum1 = s1; sum2 = s2;}
public String toString() {return "("+sum1+ " + " +
sum2 +")";}
public Poly ableitung(PolyVar variable)
{return konstruiereSumme(sum1.ableitung(variable),
sum2.ableitung(variable));}
// ohne Optimierung
public static Poly konstruiereSumme(Poly s1, Poly s2) { return new
PolySumme(s1,s2);}
// mit Optimierung
public static Poly konstruiereSumme(Poly o1, Poly o2) {
if ((o1 instanceof PolyZahl) && (o2 instanceof PolyZahl))
{return new
PolyZahl(((PolyZahl)o1).getZahl() + ((PolyZahl)o2).getZahl()); }
else if (o1.equals(PolyZahl.nulli)) return o2;
else if (o2.equals(PolyZahl.nulli)) return o1;
else return new PolySumme(o1, o2);}
}
Beispiele:
Ableitung ((x + 3) x) -> (1 + 0)
Ableitung
((x * y) x) -> ((x * 0) + (1 * y))
Ableitung
((x * y) * (x + 3)) x) -> (((x * y) * (1 + 0)) + (((x * 0) + (1 * y)) * (x +
3)))
Aufrufe:
Variable, nach denen alle 3 Bsp.
abgeleitet werden
Poly
x = new PolyVar("x");
// Ableitung ((x + 3) x) -> (1 +
0)
(new
PolySumme(x, new PolyZahl(3))).ableitung(x);
// Ableitung ((x * y) x) -> ((x *
0) + (1 * y))
(new
PolyProdukt(x, new PolyVar("y"))).ableitung(x);
//
Ableitung ((x * y) * (x + 3)) x) -> (((x * y) * (1 + 0)) + (((x * 0) + (1 *
y)) * (x + 3)))
(new
PolyProdukt(
new PolyProdukt(x, new
PolyVar("y")),
new PolySumme(x, new
PolyZahl(3)))).ableitung(x);
Regeln zur Vereinfachung, z.B.:
; Aufrufe: (ableitung '(x + 3) 'x) --> 1
; (ableitung '(x * y) 'x) --> y
; (ableitung '((x * y) * (x + 3)) 'x)
--> ((X * Y) + (Y * (X + 3)))