- Der µ-Operator: Was macht der eigentlich genau …
Hier hab ich schon mal ein paar Worte dazu gesagt. Vielleicht hilft das ja
schonmal weiter. Sonst frag nochmal nach [img]
http://www.fb18.de/gfx/23.gif[/img]
in WP steht Jede μ-rekursive Funktion entspricht einer WHILE-Schleife und umgekehrt. Das ist toll, aber was macht die WHILE-Schleife genau und wie wende ich den Operator an, wenn ich eine gegebene Funktion (meinetwegen Ackermann) durch µ-Rekursion erzeugen will?
Was der µ-Operator macht, ist ja eigentlich eine While-
Schleife: er sucht die kleinste Nullstelle bzgl. der letzten
Argumentstelle, d.h. er wertet die Funktion solange mit
fortlaufenden Argumenten in der letzten Argumentstelle aus,
bis die Funktion mal 0 zurückliefert. Und das Argument, das
er als Nullstelle identifiziert hat, gibt er zurück.
Um den µ-Operator nun als While-Schleifen-Ersatz zu verwenden,
muss man die Bedingung fürs Schleifenende als Nullstellengleichung
schreiben. Als Beispiel für eine While-Schleife, die man
mit dem µ-Operator schreibt, bietet sich z.B. das Suchen
der natürlichzahligen Wurzel an. Angenommen, wir haben das
Programm
input: n
a:=0;
while(a*a != n && a != n) {
a:=a+1;
}
return a;
Dann setzt man [img]
http://mokrates.de/cgi-bin/texstring?f(n%2Ca)%3D(a%5E2-n)(a-n)[/img].
(das ist offensichtlich primitiv-rekursiv). Dann ist
f an der Stelle (n,a) genau dann ungleich 0, wenn a*a != n
und a!=n. Also berechnet die Funktion [img]
http://mokrates.de/cgi-bin/texstring?%5Cpsi%3A%3D%5Cmu%20f[/img]
die natürlichzahlige Wurzel, d.h. [img]
http://mokrates.de/cgi-bin/texstring?%5Cpsi(n)%3D%5Csqrt%7Bn%7D[/img],
falls n eine Quadratzahl ist und [img]
http://mokrates.de/cgi-bin/texstring?%5Cpsi(n)%3Dn[/img], falls n
keine Quadratzahl ist.
Umgekehrt geht man entsprechend vor: man programmiert eine
While-Schleife, die die Funktion f an allen möglichen Stellen
auswertet und das solange, bis f 0 liefert. Hier sieht man auch,
warum das Ergebnis der Nullstellensuche nur dann definiert ist,
wenn alle Funktionswerte bei kleineren Werten definiert sind,
denn die Whileschleife muss ja f bei allen kleineren Werten
auswerten.
- Wie verhalten sich jetzt die totalen Funktionen zu den partiell-rekursiven?
Total bedeutet nur, dass die Funktion auf allen Eingabewerten
definiert ist. Wenn eine Funktion nun nicht total ist, kann sie
trotzdem berechenbar sein, z.B. von einer TM, die für die
Stellen, an denen f nicht definiert ist, kein Ergebnis liefert.
Und berechenbar ist äquivalent zu partiell-rekursiv.
Muß eine berechenbare Funktion entweder total oder partiell-rekursiv sein?
Als nicht-ausschließendes Oder: ja, denn berechenbare Funktionen
sind alle partiell rekursiv (und viele sind total).
Als XOR: Nein, denn viele berechenbare (und damit
partiell-rekursive) Funktionen sind total.
- Wie zur Hölle komme ich von einem gegebenen Algorithmus auf dessen Komplexität?
Du suchst dir ein Maß für die Größe der Eingabe und schätzt bis
auf einen konstanten Faktor ab, wie lange das Programm in
Abhängigkeit von diesem Maß läuft. "Bis auf einen konstanten
Faktor" bedeutet: du nimmst an, dass jede Einheit, deren
Ausführungsdauer nicht von der Größe der Eingabe abhängt, eine
Zeiteinheit benötigt.
Z.B. bei einer Funktion, die eine ROT13-Verschlüsselung macht:
dort nimmt man als Maß vernünftigerweise die Länge des zu
kodierenden Strings. Und der Algorithmus wird für jede
Position im String eine Umrechnung machen. Eine Umrechnung
eines Zeichens dauert immer gleich lang, egal wie lang der
String ist, also wird für jede Position im String eine
Zeiteinheit verbraucht, d.h. man hat Zeitkomplexität n.
Konstante Summanden (z.B. für das initialisieren einer Tabelle)
kann man dabei übrigens meistens vernachlässigen, denn wenn der
Rest des Programms Zeitkomplexität f hat, dann ist 2*f ab irgend-
einer Eingabegröße sicher größer als f+k (wenn k die Konstante ist),
denn Zeitschranken (f, in diesem Fall), sind meistens monoton.
Und O(2f)=O(f).
Ist das klar geworden?
(Ich weiß nicht, was man auf der allgemeinen Ebene noch dazu
sagen kann).
