28 Nov 08 Aufgaben zu Rekursiven Funktionen
Hier noch einiges Übungsaufgaben, die jeder für sich lösen kannHinweis.
Operationen auf Sequenzen $$\mathrm{Seq} \langle T \rangle$$
- Wiederhole generische Funktionen und Sequenzen auf dem Merkblatt zu FJava.
- Schreibe die Funktionen <T> int length( Seq<T> seq ), <T> T last( Seq<T> seq ) ohne irgendwo nachzuschlagen.
- Entwickle eine Funktion <T> Seq<T> reverse( Seq<T> seq ), die eine Sequenz umdreht – aus [1,2,3,4] würde [4,3,2,1] werden.
- Entwickle eine Funktion <T> T _getNth( Seq<T> seq, int n ), die das n-te Element ($$n \ge 0$$) aus der Sequenz zurückgibt. Wir fangen an bei 0 zu zählen, also _getNth( [0,1,2,3,4], 3 ) = 3.
- Entwickle eine Funktion <T> T getNth( Seq<T> seq, int n ), die das n-te Element aus der Sequenz zurückgibt. Ist $$n < 0$$, so gebe das $$-n$$-te Element vom Ende der Sequenz zurück, also getNth( [4,3,2,1], -2 ) = 2.
- Schreibe eine Funktion <T> boolean isEqual( Seq<T> a, Seq<T> b ), die überprüft, ob alle Elemente in der Sequenz a gleich denen in b sind (in der gleichen Reihenfolge), also isEqual( [1,2,3], [1,2,3] ) = true, aber isEqual( [1,2,3], [3,2,1] ) = false und natürlich isEqual( [], [] ) = true und isEqual( [1,2], [1,2,3] ) = false.
Beachte hierbei, dass T auch String sein kann, also muss man vergleichen mit a.equals( b ) für a, b aus der Sorte T´. - Schreibe eine Funktion <T> boolean isPalindrome( Seq<T> a ), die überprüft, ob a ein Palindrom ist, d.h. a ist vorwärts und rückwärts gelesen gleich.
- Schreibe eine Funktion <T> boolean inSeq( T element, Seq<T> seq ), die überprüft, ob element in der Sequenz seq vorkommt.
Beachte hierbei, dass T auch String sein kann, also muss man vergleichen mit a.equals( b ) für a, b aus der Sorte T.
- Entwickle eine Funktion <T> int count( Seq<T> seq, T element ), die zurückgibt, wie oft element in der Sequenz seq vorkommt.
Beachte hierbei, dass T auch String sein kann, also muss man vergleichen mit a.equals( b ) für a, b aus der Sorte T. - Entwickle eine Funktion <T> int remove( Seq<T> seq, T element ), die alle Vorkommen von element aus seq löscht.
Sequenzen als Mengen
Mengen sind ein Spezialfall von Sequenzen, bei denen jedes Element höchstens einmal vorkommen darf und die Reihenfolge der Elemente egal ist (wenn man auf Gleichheit o.ä. prüfen will).
- Schreibe eine Funktion <T> boolean isSet( Seq<T> seq ), die zurückgibt, ob seq eine Menge ist, also ob jedes Element höchstens einmal in seq vorkommt.
- Schreibe eine Funktion <T> boolean inSet( T element, Seq<T> set ), die zurückgibt, ob element in set ist.´
- Schreibe eine Funktion <T> Seq<T> insertIntoSet( Seq<T> set, T element ), die element zur Menge set hinzufügt. Wenn für set gilt: isSet( set ) = true, dann soll dies auf für den Rückgabewert von insertIntoSet gelten.
- Schreibe analog eine Funktion removeFromSet.
- Entwickle Funktionen union und intersect die analog Mengen vereinen und schneiden.
- Entwickle eine Funktion <T> boolean isSubset( Seq<T> subSet, Seq<T> set ), die überprüft, ob $$ \mathbf{subSet} \subseteq \mathbf{set} $$ gilt.
- Entwickle eine Funktion <T> boolean isSetEqual( Seq<T> aSet, Seq<T> bSet ), die überprüft, ob die Mengen aSet und bSet gleich sind.
Wieso ist isSetEqual für Mengen weniger effizient als isEqual für Sequenzen?´ - Entwickle eine Funktion <T> Seq<Seq<T>> powerSet( Seq<T> set ), welche die Potenzmenge der Menge set konstruiert. Für jedes Sequenz s aus dem Rückgabewert gilt also: isSet( s ) = true und isSubset( s, set ) = true.
Hinweis: Man entwickle zuerst eine Funktion <T> Seq<Seq<T>> setsWithoutOneElement( Seq<T> set ), welche alle Teilmengen von set zurückgibt, die ein Element weniger enthalten.´
Operationen auf Sequenzen von Sequenzen´
- Entwickle eine Funktion <T> Seq<Seq<T>> expandFront( Seq<T> seq, Seq<T> choices ), die alle Sequenzen s zurückgibt, für die gilt: isEqual( rest( s ), seq ) = true und inSeq( first( s ), choices ) = true.´
- Entwickle eine analoge Funktion <T> Seq<Seq<T>> expandBack( Seq<T> seq, Seq<T> choices ), für die obigen Bedingungen für reverse( s ) statt s gelten. Wie sehen dann Nachbedingungen für expandBack aus?´
- Schreibe die Funktion <T> Seq<Seq<T>> expandAcyclicFront( Seq<T> seq, Seq<T> choices ), die nur Sequenzen s zurückgibt für die gilt: inSeq( first( s ), rest( s ) ) = false.
- Schreibe analog zu expandBack, die Funktion expandAcyclicBack.
- Entwickle eine Funktion <T> Seq<T> getNeighbors( Seq<Seq<T>> neighborSeq, T node ), die den Rest der Untersequenz zurückgibt, die als erstes Element node hat, oder die leere Sequenz, falls es keine solche Sequenz gibt, wobei jede Sequenz von neighborSeq ein anderes erstes Element besitzt, also wäre [[1,2],[1,2,3] keine gültige Sequenz.
Beispiel: getNeighbors( [[1,2,3], [2,1,4], [3,1]], 2 ) = [1, 4].
Reflexive, Transitive Hüllen
Die reflexive, transitive Hülle $$ \rightarrow ^{\star} $$ über einer Menge $$\mathbf{G}$$ und einer Relation $$ \rightarrow : \mathbf{G} \times \mathbf{G} \rightarrow \mathbf{G}, \left( a, b \right) \mapsto a \rightarrow b $$ (gelesen: “a zeigt zu b”) ist folgendermaßen definiert´:
$$ \\\\
\forall a, b \in \mathbf{G}:\\
\begin{array}{lcl}
a \rightarrow ^ 0 b & :\Leftrightarrow & \begin{cases}
true & \text{ : } a = b \\
false & \text{ : } a \not = b
\end{cases} \\\\
a \rightarrow ^ 1 b & : \Leftrightarrow & a \rightarrow b \\\\
a \rightarrow ^{n+1} b & : \Leftrightarrow & \exists x \in \mathbf{G}: a \rightarrow ^{n} x \land x \rightarrow b\\
\\
\\
a \rightarrow ^ {\star} b & : \Leftrightarrow & \exists n \in \mathbb{N}: a \rightarrow ^ n b
\end{array}
$$
Wir können diese Konstruktion auch in FJava nachvollziehen, wenn wir die Relation in einer Adjanzentliste speichern, d.h. gilt:
$$
\mathbf{ G = \left \{ a, b, c, d, e \right \} }
$$
und
$$
\mathbf{
a \rightarrow b, a \rightarrow c, a \rightarrow d, b \rightarrow c, b \rightarrow d,
c \rightarrow a, d \rightarrow b, d \rightarrow e }
$$
so speichern wir das als:
$$\mathbf{seq := \left[\left[a, b, c, d \right], \left[b, c, d \right], \left[c, a \right], \left[d, b, e \right], \left[ e \right] \right]}$$
Sprich: Jedes Element kommt genau einmal als erstes Element in einer Untersequenz vor und der Rest der jeweiligen Untersequenz gibt die Elemente an, auf die das erste Element “zeigt”.
Dann können wir aus $$\mathbf{seq}$$ sowohl $$\mathbf{G}$$, als auch $$\rightarrow$$ bestimmen, da diese durch die Adjazenzliste eindeutig festgelegt sind.
Außerdem können wir getNeighbors benutzen um aus solch einer Sequenz, alle Elemente zu finden, auf die ein bestimmes zeigt.
Im Folgenden sei mit neighborSeq immer die Adjazenzliste von $$ \rightarrow $$ bezeichnet.
In dem Beispiel von oben: getNeighbors( seq, “a” ) = [ “b”, “c”, “d” ].
- Schreibe eine Funktion <T> Seq<Seq<T>> zeroHull( Seq<Seq<T>> neighborSeq ), die für die Relation, die durch die Adjazenzliste neighborSeq bestimmt ist, die Adjazenzliste aller Elemente bestimmt für $$ \rightarrow^0 $$.
Im Beispiel von oben wäre dies:
$$\mathbf{seq := \left[\left[a, a \right], \left[b, b \right], \left[c, c \right], \left[d, d\right], \left[ e, e \right] \right]}$$ - Entwickle eine Funktion <T> Seq<T> squareHullForElement( Seq<Seq<T>> neighborSeq, T element ), die die Menge aller Elemente x enthält, die von element in zwei Schritten erreichbar sind, also: $$ \mathbf{ \exists y \in G: element \rightarrow y \rightarrow x }$$
- Entwickle eine Funktion <T> Seq<Seq<T>> squareHull( Seq<Seq<T>> neighborSeq ), die $$ \rightarrow ^2 $$ von neighborSeq zurückgibt.
- Entwickle eine Funktion <T> Seq<T> nthHull( Seq<Seq<T>> neighborSeq, int n ), die für $$ n \ge 0 $$ die n-te Hülle von $$\rightarrow$$ bestimmt, also $$ \rightarrow^n $$.
Hinweis:
Man schreibe zuerst eine Funktion <T> Seq<Seq<T>> concatenateRelation( Seq<Seq<T> neighborSeqN, Seq<Seq<T>> neighborSeq ), die zwei Relationen $$ \prec $$ und $$ \propto $$, die durch neighborSeqN bzw. neighborSeq beschrieben werden, auf $$ \mathbf{G}$$ hintereinanderausführt und die sich ergebende Relation $$ \sqsubset $$ als Adjanzenzliste zurückgibt, so dass für alle Teilsequenzen mit erstem Element e und restlichen Elementen x, gilt:
$$ \mathbf{ \exists y \in G: e \prec y \land y \propto x :\Leftrightarrow e \sqsubset x }$$.´ - Schreibe eine Funktion <T> Seq<Seq<T>> transitiveHull( Seq<Seq<T>> neighborSeq ), die $$ \rightarrow ^{\star} $$ konstruiert. Die Funktion kann immer terminieren, da $$ \mathbf{G} $$ endlich ist.
Tags: Add new tag, Aufgaben, FJava, Mengen, Sequenzen, Transitive Hülle
Leave a Comment
You must be logged in to post a comment.
