Algorithmen und Programmierung II

 SS 2004
Probeklausur
Dauer: 180 Minuten
Zum Bestehen sind 20 von 40 Punkten zu erreichen.

Aufgabe 1 (12 Punkte)

Gesucht ist eine Prozedur, die einen gegebenen Text t in Zeilen der Länge l umbricht und diese als Ergebnis abliefert. (Blocksatz ist nicht erforderlich.) Beispiel für l=29:
    Vom Eise befreit sind Strom
    und Bäche durch des Frühlings 
    holden, belebenden Blick.
    |<---------- 29 ----------->|
Der Prozedurkopf soll so aussehen:
    static char[][] umbrechen(char[] t, int l)
Die Aufgabe soll systematisch mit schrittweiser Verfeinerung gelöst werden. Es muss kein zusammenhängender Prozedurrumpf angegeben werden. (Für die Bewertung der Lösung ist die Qualität des Verfeinerungsvorgangs ausschlaggebend.)

Von folgenden Voraussetzungen kann ausgegangen werden:
  1. t ist nicht null und der Text ist nicht leer.
  2. Die Wörter (einschließlich eventueller Interpunktionszeichen) sind voneinander durch genau ein Leerzeichen getrennt.
  3. Alle Wortlängen sind höchstens gleich l.
  4. Der gesetzte Text umfasst höchstens Z Zeilen; Z stehe als Konstante zur Verfügung.

Aufgabe 2 (12 Punkte)

Eine stetige reelle Funktion g mit g(a)<0 und g(b)>0 hat im Intervall (a, b) mindestens eine Nullstelle. Eine solche kann durch die sogenannte Regula falsi approximiert werden: man ermittelt die Nullstelle x der Geraden zwischen den Punkten (a, g(a)) und (b, g(b)), ersetzt das Intervall (a, b) durch (x, b) (falls g(x)<0, sonst (a, x) ) und wiederholt den Vorgang solange, bis g(x) der 0 hinreichend nahe kommt. Für ein gegebenes eps>0 und eine gegebene Funktionsprozedur float g(float a) leistet die folgende Prozedur das Gewünschte:
    float nullstelle(float a, float b){
        /* Vor.: eps>0, a<b, g(a)<0, g(b)>0; g stetig.
         * Eff.: |g(result)|<eps ,’a < result < ’b .
         */
        float x, gx;
        float ga = g(a); float gb = g(b);
        do {x  = (a*gb – b*ga) / (gb - ga); 
            gx = g(x);
            if (gx*ga > 0) {a = x; ga = gx;}
            else           {b = x; gb = gx;}}
        while(Math.abs(gx) > eps); 
        return x;
    }
Wandeln Sie diese Schleife durch systematische Programmtransformation in eine
entsprechende Haskell-Funktion um und benutzen Sie diese zur Angabe einer Haskell-
Funktion
    nullstelle :: Float -> Float -> Float
    --              a        b
eps::Float und die Funktion g::Float->Float seien bereits definiert.

Aufgabe 3 (9 Punkte)

Gegeben sei eine einfach verkettete Liste EVListe von Objekten der Klasse Knoten: 
class EVListe {
    Knoten erster = null;
    void einfuegen(Knoten k) {
        k.naechster = erster;
        erster = k;
    }
    void umdrehen() {
        // zu implementieren
    }
}

class Knoten {
    Knoten naechster = null;
    int wert;
    Knoten(int wert) { this.wert = wert; }
}
Implementieren Sie innerhalb der Klasse EVListe eine effiziente Methode umdrehen zum „Umdrehen“ der Reihenfolge der Listenelemente. Die Variable naechster des letzten Listenelementes enthält null.


Aufgabe 4 (7 Punkte)

Gegeben sei folgender Java-Ausdruck:
 
    a[b[i]] = c < d ? b[i] : x
a) (3 P)  Zeigen Sie durch Angabe eines Syntaxbaums, dass der Ausdruck syntaktisch korrekt ist. Verwenden Sie die Grammatik in der Anlage.

b) (4 P)  Die oben verwendeten Variablen seien wie folgt vereinbart. Geben Sie für jede Alternative an, welchen Typ und welchen Wert der oben stehenden Ausdruck hat, sofern typkorrekt. Andernfalls begründen Sie den Typfehler.

1.
 double[] a = {1.0, 2.0};  
char[]   b = {0, 1}; 
int      i = 1;
double   x = 4;
byte     c = 1;
long     d = 2;

 2.
 int[]    a = {1, 2};   
char[]   b = {0, 0};
byte     i = 0;
double   x = 4;
int      c = 1;
int      d = 2;
3.
 int[]    a = {1, 2};
double[] b = {0.5, 0.7};
int      i = 0;
byte     x = 4;
int      c = 4;
int      d = 2;
 4.
 long[]   a = {1, 2};
int[]    b = {0, 1};
byte     i = 1;
long     x = 4;
long     c = 5;
int      d = 7;