Je suis bloque et besoin d aide

Bonjour,
j ai besoin de la resolution de ces Excercises.
Je vous remercie




1. Applikative Algorithmen 6 Punkte
Gegeben die Definitionen
g(a,b) = if (a > b) then a – b else b – a fi
h(a,b) = g( g(a,b), g(b,a) )
k(a) = g(a, g(a,a) )
a) Welchen Wert liefert
h(1,3) =
h(3,1) =
h(10,15) =
b) Welche Funktion berechnet h(x,y) allgemein, also für beliebige x und y ∈ℤ?
c) Welche Funktion berechnet k(x) allgemein, also für beliebige x∈ℤ?
2. Imperative Algorithmen 4 Punkte
Algorithmus unknown(x,y)
Eingabe: x, y: integer
Ausgabe: z: integer
z := 0;
h := 0;
while h ≠ x do
h := h + 1
od;
while h ≠ y do
h := h + 1;
z := z + 1;
od
a) Welchen Wert liefert der Algorithmus für die
Eingabe x=5 und y=3?
b) Welchen Wert liefert der Algorithmus für die
Eingabe x=5 und y=0?
c) Welchen Wert liefert der Algorithmus für
allgemeine Eingaben x,y∈ℤ ?
Algorithmik 1 (Bachelor)
Wintersemester 2009/10, Prof. Dr. Jörg R. Weimar, Fachhochschule Braunschweig/Wolfenbüttel
Testat 1, Abgabe spätestens 14.10.2009 vor der Vorlesung
Name:
Matrikelnummer:

3. Binäre Suche 7 Punkte
a) Führen Sie den folgenden Algorithmus zur binären Suche (nach k=3) auf dem Feld F
durch. Notieren Sie für jeden Durchlauf der Schleife alle Variablenwerte.
Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14
F[i] 2 3 3 3 5 7 11 13 17 19 23 29 31 37
u m o
Algorithm searchFirst(F, k)
Eingabe: sortiertes Feld F, Schlüssel k
Ausgabe: erste Position von k in F oder NO_KEY
u := 1; o := F.length;
while u < o do
m := (u+o)/2;
if F[m] < k then
u := m+1
else
o := m
fi
od;
if f[m] = k then
return m
else
return NO_KEY
b) Beschreiben Sie mit Pseudocode einen Algorithmus, der in einer geordneten Folge
die Position des letzten Auftretens eines Schlüsselwertes k liefert (separates Blatt)
4. Instabile Sortierverfahren 8 Punkte
a) Welche der Sortierverfahren aus der Vorlesung sind instabil, welche stabil?
b) Wählen Sie ein instabiles Sortierverfahren aus und demonstrieren Sie die Instabilität
an einem Beispiel. Markieren Sie identische Elemente i∈ℕ mit i, i', i'' usw. und
demonstrieren Sie den Ablauf des Sortierverfahrens mit Zwischenschritten.