Prof. Dr. A. Poetzsch-Heffter

Dipl.-Inf. J.-M. Gaillourdet

Dipl.-Inf. P. Michel

TU KaiserslauternFachbereich Informatik

AG Softwaretechnik

Übungsblatt 8: Software-Entwicklung 1 (WS 2009/10)

Ausgabe: in der Woche vom 14.12. bis zum 18.12.Abgabe: in der Woche vom 04.01. bis zum 08.01.

Abnahme: max. zwei Tage nach der Übung

Aufgabe 1 Parameterinduktion (Präsenzaufgabe)

Geben Sie die Implementierung der Haskell-Funktion gauss an, welche für gegebenen Parameter n die Sum-me der natürlichen Zahlen von 0 bis n durch rekursive Berechnung ermittelt. Zeigen Sie für Ihre Implemen-tierung unter Verwendung der vollständigen Induktion, dass die folgende Gleichheit gilt:

gauss n =n(n+1)

2

Aufgabe 2 Parameterinduktion (Einreichaufgabe)

a) Geben Sie die Implementierung der Haskell-Funktion multiply an, welche die Multiplikation zweiernatürlicher Zahlen auf Addition / Subtraktion zurückführt. Zeigen Sie für Ihre Implementierung unterVerwendung der vollständigen Induktion, dass die folgende Gleichheit gilt:

multiply x y = x · y

b) Beweisen Sie, dass die Haskell-Funktion

g :: Integer -> Integerg n = h n 1 0

h :: Integer -> Integer -> Integer -> Integerh 0 _ r = rh n l r = h (n-1) r (l+r)

ebenfalls die Fibonacci-Zahlen

f :: Integer -> Integerf 0 = 0f 1 = 1f n = f (n - 1) + f (n - 2)

berechnet, also g n = f n für alle n ∈ N gilt. Zeigen Sie hierzu zunächst mittels Induktion über k, dass

h (n-k) (f (k-1)) (f k) = f n

für n, k ∈ N mit 1 ≤ k ≤ n und n > 0 gilt. Nutzen Sie dieses Teilergebnis, um die eigentliche Aussage zubeweisen.

Hinweis: Im Fall obiger Induktion über k ist es ratsam, bei k = n zu beginnen und den Induktionsschlußk → (k − 1) durchzuführen!

Aufgabe 3 Terminierung (Präsenzaufgabe)

In dieser Aufgabe wollen wir die Terminierung von Funktionen mit dem Verfahren aus der Vorlesung be-weisen. Wir betrachten wieder einmal die Fibonacci Funktion, implementiert durch:

f :: Integer -> Integerf 0 = 0f 1 = 1f n = f (n - 1) + f (n - 2)

Beweisen Sie, dass diese Funktion terminiert, denken Sie aber daran, dass wir uns nur für Parameter aus dennatürlichen Zahlen interessieren.

Aufgabe 4 Terminierung (Einreichaufgabe)

a) Beweisen Sie, dass die Funktion divConstZero, die wir im Rahmen der Expressions-Aufgabe geschriebenhaben, terminiert:

data Expr =Const Integer

| Binary Op Expr Exprderiving (Eq, Ord, Show)

data Op = Mult | Div | Plus | Minusderiving (Eq, Ord, Show)

divConstZero :: Expr -> BooldivConstZero (Const _) = FalsedivConstZero (Binary Div _ (Const 0)) = TruedivConstZero (Binary _ a b) = divConstZero a || divConstZero b

Hinweis: Betrachten Sie ausschließlich endliche Ausdrücke und machen Sie dies im Beweis klar.

b) Wir betrachten folgende Implementierung der Primfaktorzerlegung (für Zahlen ≥ 2) und wollen bewei-sen, dass sie für jede Eingabe terminiert:

primfaktoren :: Integer -> [Integer]primfaktoren c = if c < 2 then [c] else faktor (c, 2)

faktor :: (Integer, Integer) -> [Integer]faktor (c, x) =if c == x then [x] elseif c `mod` x /= 0 then faktor (c, x + 1) else

x : faktor (c `div` x, 2)

Da die Funktion primfaktoren nicht rekursiv ist, terminiert sie, wenn alle von ihr aufgerufenen Funk-tionen terminieren. Wir müssen also beweisen, dass die Funktion faktor terminiert, zumindest auf demParameter-Bereich, der von primfaktoren oder faktor aufgerufen wird. Sei also P der zulässige Parame-terbereich:

P ={(c, x) | 2 ≤ x ≤ c

}⊂ N × N

Beweisen Sie, dass es durch einen Aufruf von primfaktoren (und die Folgeaufrufe durch faktor selbst)nur zulässige Aufrufe von faktor mit einem Parameter aus P geben wird: G(n) ∈ P.

c) Um die Terminierung nun zu beweisen, verwenden wir das Verfahren aus der Vorlesung. Als noether-sche Ordnung verwenden wir die Menge der Paare aus natürlichen Zahlen (N × N,≤) mit der kompo-nentenweisen Ordnung, d.h. ist die erste Komponente gleich wird nach der zweiten geordnet, wie aufnatürlichen Zahlen, ansonsten wird nach der ersten Komponente geordnet. Das kleinste Element ist danneinfach (0, 0).

Geben Sie eine Funktion δ : P 7→ N×N an, die Parameter auf unsere Ordnung abbildet, so dass Sie denTerminierungsbeweis führen können. Im vorhergehenden Aufgabenteil haben Sie schon bewiesen, dassG(n) ∈ P, es bleibt also noch zu zeigen, dass die Parameter echt kleiner werden: δ(G(n)) < δ(n).

Aufgabe 5 Java (Einreichaufgabe)

Im weiteren Verlauf der Vorlesung wird die Sprache Java verwendet. In dieser Aufgabe soll ein kleines“Hallo Welt”-Programm geschrieben, übersetzt und ausgeführt werden.

a) Legen Sie eine Datei mit dem Namen “Hallo.java” an und geben Sie folgendes Javaprogramm ein:

public class Hallo {

static String greeting = "Hallo Java";

public static void main (String[] args) {IO.println(greeting);

}}

Beachten Sie, dass eine Java Quelltextdatei immer den gleichen Namen wie die in ihr enthaltene Klasseplus die Endung “.java” trägt. In unserem Fall heisst die Klasse Hallo und die Datei entsprechendHallo.java.

b) Im nächsten Schritt werden wir diese Datei übersetzen, d.h. Bytecode für die Java Virtuelle Maschineerzeugen. Dazu laden Sie als erstes die Datei “IO.java” von der Webseite der Vorlesung und speicherndiese im gleichen Verzeichnis wie Ihren Quelltext (Quellverzeichnis). Rufen Sie im Quellverzeichnisden Javacompiler auf der Kommandozeile mit folgendem Befehl auf:

> javac Hallo.java

Dem Compiler wird die Datei übergeben, die eine main-Methode enthält. Er erstellt dann zu jeder be-nutzen Klasse eine “.class”-Datei, die sich im selben Verzeichnis befindet. In unserem Fall müsstenSie jetzt Hallo.class und IO.class in ihrem Verzeichnis haben. Um das gerade geschriebene undübersetzte Programm auszuführen, rufen Sie aus dem Quellverzeichnis java mit der Klasse auf, dieeine main-Methode enthält. In unserem Fall also:

> java Hallo

Wenn jetzt der Begrüßungstext auf dem Bildschirm erscheint haben Sie alles richtig gemacht.

c) Um den Bytecode von den Quelldateien sauber zu trennen, können wir angeben wohin der Übersetzerseine Ausgabe speichert. Legen Sie ein Unterverzeichnis “build” an, in dem wir nun alle übersetztenDateien ablegen.

Hinweis: Löschen Sie die “class” Dateien die Sie in b) im Quellverzeichnis erzeugt haben, um Problememit Java zu vermeiden!

Rufen Sie im Quellverzeichnis den Javacompiler auf der Kommandozeile mit folgendem Befehl auf:

> javac -d build Hallo.java

Er erstellt nun im build-Verzeichnis zu jeder benutzen Klasse eine “.class”-Datei. Um das Programmauszuführen rufen Sie aus dem Quellverzeichnis java mit der zusätzlichen Angabe wo sich die Klassenbefinden auf:

> java -cp build Hallo

Wenn jetzt der Begrüßungstext auf dem Bildschirm erscheint haben Sie alles richtig gemacht.

Aufgabe 6 Imperative Programmierung mit Java

Kreuzen Sie an, ob folgende Aussagen wahr oder falsch sind. Bereiten Sie diese Aufgabe bis zu Ihrernächsten Übungsstunde vor, so dass Sie bei Unklarheiten nachfragen und die Antworten diskutieren können.

wahr falsch

� � Ausdrücke in Java erzeugen keine Seiteneffekte.� � Jeder Ausdruck ist eine Anweisung.� � Es gibt Anweisungen, welche die Abfolge, in der Anweisungen abgearbeitet werden,

beeinflussen.� � Auf der rechten Seite einer Zuweisung kann ein Prozeduraufruf stehen.� � Überall dort wo eine einzelne Anweisung stehen kann, kann auch ein Anweisungsblock

stehen.� � Der Rumpf einer while-Anweisung wird mindestens einmal ausgeführt.� � Die Schleifenvariable einer for-Schleife kann auch um mehr als eins pro Schleifendurch-

lauf erhöht werden.� � Geschachtelte Fallunterscheidungen lassen sich durch eine Auswahlanweisung ersetzen.� � Prozeduren enthalten Anweisungen und liefern immer ein Ergebnis.� � Eine Prozedur kann sich in ihrem Rumpf selbst aufrufen.� � Jede Prozedurinkarnation hat ihre eigenen lokalen Variablen.� � Wenn v eine lokale Variable einer Prozedur ist, dann wird mit v immer dieselbe Spei-

chervariable angesprochen.� � Auf jede Variable kann während der gesamten Programmausführung zugegriffen

werden.� � Eine Variable des Typs boolean[] speichert ein Feld.� � Ein Programm kann Felder erzeugen, auf die es später nicht mehr zugreifen kann.� � Es kann mehrere Variablen geben, die auf dasselbe Feld zeigen.

Aufgabe 7 Weihnachtsaufgabe (freiwillige Zusatzaufgabe)

Mit Hilfe von Turtlegraphics lassen sich auf einfache Art und Weise sehr komplexe Grafiken generieren.Man stelle sich dafür vor, dass man eine Schildkröte (engl. Turtle) über eine Fläche steuert, die dabei eineSpur hinterlässt. Die Schildkröte reagiert auf einfache Befehle, wie “vorwärts” oder “drehen”.

Die Schildkröte startet im Ursprung (0, 0) des karthesischen Koordinatensystems und schaut nach rechts(Richtung x-Achse). Sie reagiert auf die folgenden Befehle:

forward x Die Schildkröte läuft vorwärts in Blickrichtung und legt eine Strecke von x zurück.left x / right x Die Schildkröte dreht sich um x Grad nach links/rechts.up / down Die Schildkröte hört auf zu zeichnen / setzt wieder an zu zeichnen.

Wie auch bei Ein-/Ausgabe in Haskell, so ist auch bei Schildkröten-Programmen die Reihenfolge der Be-fehle relevant! Analog zum Typ IO a verwenden wir also Turtle a Befehle, die in do-Blöcken kombiniertwerden können.

Betrachten wir den Effekt des folgenden Turtle-Programms:

nico :: Turtle ()nico = doleft 90forward 100right 45forward (sqrt 5000)right 90forward (sqrt 5000)right 45 -- Bild 1forward 100right 135forward (sqrt 20000)right 135forward 100 -- Bild 2right 135forward (sqrt 20000)left 135forward 100 -- Bild 3

Laden Sie sich die Grundbibliothek “Turtle.hs” sowie die Datei “PDFTurtle.hs” (oder eine andere Turtle-Implementierung Ihrer Wahl) von der Vorlesungsseite. Wenn Sie nun das Modul PDFTurtle importieren,erhalten Sie sowohl alle Turtle-Befehle, als auch die Funktion render :: String -> Turtle a -> IO ().Diese nimmt einen Namen sowie ein Turtle-Programm und gibt das entstehende Bild im Sinne der Im-plementierung aus (hier: als PDF-Dokument). Da alle Implementierungen die gleiche Schnittstelle haben,können Sie jederzeit durch Austauschen des import auf eine andere Implementierung wechseln.

a) Zeichnen Sie ein Dreieck, eine eckige Spirale und einen Kreis:

Hinweis: Da die Schildkröte ausschließlich geradeaus laufen kann, müssen Sie den Kreis approximieren.

Hinweis: Sie müssen sich nicht darum kümmern wie groß Ihre Grafik insgesamt wird. Einzig die relativeGröße und Position zwischen Objekten einer Grafik ist für die Ausgabe relevant.

b) Viele Grafiken lassen sich mit sehr kurzen rekursiven Turtle-Programmen zeichnen, da sie eine großeSelbstähnlichkeit besitzen. Ein Baum, zum Beispiel, besteht letztendlich nur aus Zweigen. Ein Baum derHöhe 1 besteht aus nur einem einzigen geraden Zweig (Stamm). Ein Baum der Höhe 2 hat drei weitere,kürzere Zweige, die aus dem Baum der Höhe 1 entspringen. Bei Höhe 3 kommen wieder jeweils dreikürzere Zweige hinzu. Das gesuchte Programm hat also zwei Parameter, einen für die Höhe, an derabgebrochen werden soll, und einen für die aktuelle Länge des Zweigs.

Schreiben Sie ein rekursives Turtle-Programm tree :: Int -> Double -> Turtle (), welches einenBaum dieser Art zeichnet.

Hinweis: Obwohl das Programm tree schwieriger zu schreiben ist, als das Beispielprogramm nico, istes dennoch ein paar Zeilen kürzer!

Tipp: Achten Sie darauf, in welcher Position sich die Schildkröte vor einem rekursiven Aufruf befindetund in welcher Sie sie nach dem Aufruf wiederfinden. Stellen Sie nützliche Garantien bezüglich Positionund Blickrichtung evtl. vor dem Rücksprung des Programms wieder her!

Hinweis: Wie stark Sie die Länge der Zweige von einer Ebene zur nächsten verkürzen und wie Sie dieWinkel wählen in denen Zweige abstehen, bestimmen maßgeblich das Aussehen des Baums!

c) Eine andere selbstähnliche Figur ist das Sierpinski Dreieck. In der Datei “sierpinski.hs” finden Sieein Turtle-Programm, welches es für verschiedene Stufen zeichnet:

Es gibt auch hier eine wesentlich kürzere – wenn auch nicht einfachere – Variante das Sierpinski Dreieckanzunähern. Anstatt immer kleinere, unabhängige Dreiecke zu zeichnen, wird eine einzige Kurve dafürbenutzt:

Das Grundprimitiv auf Level 0 ist ein einfacher Strich. Level 1 baut drei dieser Striche zu einer Links-kurve mit 60 Grad Neigungen zusammen. Im allgemeinen baut das jeweils nächste Level drei Versionen

des Vorlevels zu einer Links- oder Rechtskurve zusammen! Dabei wird die Drehrichtung der ersten undder dritten Version umgekehrt zur eigenen gewählt, die zweite Version dreht in dieselbe Richtung. Fürdie Abbildungen wurde jeweils die Anfangsdrehrichtung auf jedem Level alterniert, damit das Dreieckinsgesamt richtig zum Betrachter ausgerichtet ist.

Schreiben Sie ein Turtle-Programm sierpinski :: Integer -> Bool -> Turtle (), welches das aktuelleLevel, sowie die aktuelle Drehrichtung nimmt und das Sierpinski-Dreieck als Kurve realisiert.

Hinweis: Die korrekte Lösung ist schon mit wenigen, kurzen Zeilen möglich!

d) Informieren Sie sich über die Drachenkurve und implementieren Sie sie als Turtle-Programm:

e) Zeichnen Sie einen Farn:

Hinweis: Das Rekursionsschema ist im Prinzip dasselbe wie bei Bäumen, jedoch sind die Parametervöllig anders gewählt und der Abbruch der Rekursion wird durch die Größe, anstatt die Höhe, herbei-geführt.