Montag, 19. Juli 2010

Primitive Rekursion III - Suche

In der Rekursion gibt es zwei Arten von Suche: Beschränkte und unbeschränkte Suche.

Erste lässt sich problemlos in der primitiven Rekursion nutzen, die andere ändert jedoch die Klasse der Funktion zu Mü-rekursiv (entsprechenden griechischen Buchstaben vorstellen.)

Kommen wir zuerst zur beschränkten Suche. Zu unterscheiden sind Minimierung und Maximierung.
Erste sucht von 0 bis zu einer bestimmten Schranke. Letztere von einer bestimmten Schranke bis hin zu 0.

Das Schema schaut wie folgt aus. (Ich beschreibe hier nur die beschränkte Minimierung, die Maximierung verhält sich analog)

(a) Min_g[f].

Auf gut deutsch: Suche das kleinste g', aber nur bis du g erreicht, für das f 0 ergibt. Gib dieses g' aus, sonst gib die Grenze addiert mit 1 aus

g ist eine primitiv-rekursive Funktion, es handelt sich hierbei zumeist um die Konstantenfunktion.



Nun zu den Mü-Rekursiven Funktionen.

Wie bereits erwähnt, ist deren Suche unbeschränkt. Die Berechnung eines Funktionswertes kann sich also bis zur Unendlichkeit hinziehen.
Erstmals werden hier auch nicht totale Funktionen betrachtet.
Das Schema für unbeschränkte Suche schaut wie folgt aus:

(b) mü f := min{y|f(x,y) = 0} falls dieses existiert und f(x,i) definiert für alle i............. _|_ sonst

Zu gut Deutsch: Suche solange, bis du etwas hast, dass in der Funktion 0 ergibt, so es denn existiert, und die Funktion für jeden Wert, den du vorher überprüft hast definiert ist. Sonst gibt "undefiniert" zurück

Primitive Rekursion II - Programmierung durch Fallunterscheidung

Soderle, weiter geht's.



Angenommen man möchte der Einfachheit halber eine Funktion der Form

(a) h(x) = | f(x) falls t(x) = 0
...........| g(x) sonst

darstellen. Also eine Funktion, die abhängig von einer Prüffunktion t entweder die Funktion f oder g auf die Eingabe anwendet.
Auch solche Funktionen sind primitiv-rekursiv, wenn jeder ihrer Bestandteile ebenfalls primitiv-rekursiv ist.

Mithilfe der Signum-Funktion sign, die 1 ausgibt, wenn ein bestimmter Ausdruck einen positiven Wert annimmt und 0 andernfalls, lässt sich die Funktion h leicht umsetzen.

h(x) = (1−sign(t(x))) ∗ f (x) + sign(t(x)) ∗ g(x)


Die Intuition dahinter ist die Folgende:
Ich multipliziere das Signum-Ergebnis der Prüffunktion subtrahiert von 1 mit der Funktion f(x) und addiere das ganze mit dem Signum-Ergebnis der Prüffunktion multipliziert mit g(x).

Ergibt die Prüffunktion nun 0, multipliziere ich das Ergebnis der Funktion f(x) mit 1 und das Ergebnis von g(x) mit 0. f(x) wird also ausgeführt.
Andersherum ergibt die Subtraktion 0, und das Ergebnis von g(x) wird da Ergebnis von h(x).

Obwohl eine Addition stattfindet, wird immer nur das Ergebnis einer der beiden Teilfunktionen genutzt, da das andere unweigerlich einer Multiplikation mit 0 entgegensteht.

In ordentlicher primitiv-rekursiver Schreibweise sieht das ganze dann so aus:

h = add o (mul o (sub o (c(k,1), sign o t), f ), mul o (sign o t, g))


Soviel dazu. Weiter mit Suche.

Donnerstag, 13. Mai 2010

Primitive Rekursion

Hier nochmal ein paar Infos zu den primitiv-rekursiven Funktionen.
Zur Notation: Für Konstanten schreibe ich c(1,0), für Projektionen pr(3,3).


Möchte man zeigen, dass eine Funktion primitiv rekursiv ist, muss man zeigen, dass diese sich nur mit Hilfe von bereits als primitiv-rekursiv bewiesenen Funktionen darstellen lässt und das entstandene Konstrukt auch wirklich das berechnet, was es soll.

An sich ist es nichts anderes als Programmieren: Ihr überlegt euch, wie ihr die Funktion mit Hilfe der zur Verfügung stehenden Notationen entwickeln können.

Exerzieren wir das noch einmal am Beispiel des kleinsten gemeinsamen Vielfachen.
Wir gehen davon aus, dass das Berechnen des größten gemeinsamen Teilers noch nicht als primitiv rekursiv bewiesen wurde.

Schritt 1: Gedanken machen

Schritt 2: Den Ausdruck aufbauen

Schritt 3: Korrektheit zeigen

Schritt 4: Schnittigen Antwortsatz finden

Exerzieren wir das mal für zwei Beispiele durch, die unterschiedliche Herangehensweisen erlauben, Addition und Teilbarkeit.

Addition – Schritt 1: Gedanken machen

Wenn ich zwei Zahlen auf rekursive Weise addieren will, muss ich mir Gedanken machen über den Rekurssionsabbruch und den Rekrusionsschritt machen.

Der triviale Fall, der Rekursionsabbruch tritt ein, wenn einer der beiden Parameter 0 ist. In der primitiven Rekursioin wird immer der letzte Parameter bis zu einem bestimmten Punkt verringert, so dass die zweite Zahl 0 sein muss, im trivialen Fall.

add(x,0) = x

Dies ist der Rekursionsfall:

add(x,y+1) = succ(add(x,y))

Addition – Schritt 2: Den Ausdruck aufbauen

Hier wollen wir nun das abstrakte Programm entwickeln.

Es ist definiert durch Pr[Rekursionsabbruch,Rekurssionsschritt]

Rekursionsabbruch = add(x,0) = add(x) = x := pr(1,1)

Der Rekursionsabbruch hat, da der Zählparameter bei 0 angekommen ist, eine Stelle weniger als die zu beschreibende Funktion.

Der Rekursionsschritt hingegen hat eine Stelle mehr. Die letzten beiden Stellen sind für uns von besonderem Interesse, sie enthalten den bereits verringerten Zählparameter und den eigentlichen Rekusionsauffruf mit dem verringerten Zählparameter.

Kurz: f(x_1,.....x_n,y+1) = g(x_1,...,x_n,y,f(x,y))

Rekurssionsschritt = add(x,y+1) = succ(add(x,y)) = s o pr(3,3)

Warum ist hier der ein Ausdruck der Art s o add o (pr(3,1),pr(3,2))? Selbstreferenz dieser Art ist im Schema verboten. Der Funktionsname darf so nicht im Ausdruck auftauchen. Dafür ist die letzte Projektion da.

Der gesamte Ausdruck, der die Addition berechnen soll sieht zusammengesetzt folgendermaßen aus:

add = Pr[pr(1,1),succ o pr(3,3)]

Die benutzten Funktion successor, sowie die Projektion, das Ausgeben von Konstanten und die Komposition sind primitiv rekursiv. Der Ausdruck, den wir gebaut haben, ist also auch primitiv rekursiv.

Addition - Schritt 3: Korrektheit zeigen

Um zu zeigen, dass der Ausdruck auch wirklich die Addition berechnet, analysieren wir das rekursive Verhalten des Ausdrucks:

add(x,0) = pr(1,1)(x) = x

add(x,y+1) = so pr(3,3)(x,y,add(x,y)) = succ(add(x,y)) = add(x,y)+1

Hey, das sieht ja haargenau aus, wie die Überlegung, die wir uns ursprünglich gemacht haben! Dieser Ausdruck berechnet tatsächlich die Addition.

Addition - Schritt 4: Schnittigen Antwortsatz finden

Da ein Asudruck gefunden wurde, der primitiv rekursiv ist (→ Schritt 2) und nachweislich die Addition berechnet (→ Schritt 3), ist gezeigt, dass die Addition eine primitiv-rekursive Funktion ist



Der Rest folgt noch! Schaut immer mal wieder rein. :)

TBD:

Programmierung durch Fallunterscheidung

Programmierung durch beschränkte Suche

Unbeschränkte Minimierung

Dienstag, 29. September 2009

Heute gelernt:

Das chinesische Wort für "beautiful puppy" bedeutet wohl das gleiche wie "pawn controlled by an evil mastermind".

Schau an, schau an.

Freitag, 18. September 2009

Stilblüten

Ein paar schöne Funde aus dem Netz.

* Verbal contracts aren't even worth the paper they are written on.

* wie auf dem Foto ersichtlich, ist das Fell auf der Unterseite (nicht sichtbar) etwas aufgeraut.