TI: Einzelschritt- und Schrittzahlfunktion sowie Übergangsrelationen (Update)

Einzelschrittfunktion

Manchmal ist es notwendig den Funktionswert einer Funktion zu berechnen. Die Funktion ist uns durch ein Flussdiagramm mit initialer Registerbelegung (Eingabewerte) gegeben und wir möchten nun das Ergebnis berechnen. Dazu ein Beispiel anhand eines Flussdiagramms aus dem Skript.

Beispiel (das - in Block 1 und 2 ist mangels mathematischer Zeichen in Open Office Draw als arithmetische Differenz zu deuten):

Wir möchten z.B. nun $f_M(2,1)$ berechnen (okay, das Beispiel ist etwas blöd, da das Ergebnis in $R_0$ immer 0 ist, aber sei es drum). Wir verwenden hierzu die Einzelschritt-Notation für die Berechnung um die Schritte nachvollziehbar zu machen. Diese haben die Form: $ES^n(Block,(R_0, R_1, R_2, 0, ...)$. Merke: in $R_0$ steht das Ergebnis. Block gibt an in welchem Block wir uns befinden, $n$ gibt uns die noch durchzuführenden Schritte an und in $R_1, ..., R_n$ ist die derzeitige Registerbelegung aller weiteren verwendeten Register (ohne das Ergebnisregister). Die restlichen Register sind mit 0 gefüllt und werden mit $0,...$ angedeutet.

Wir stellen also eine kleine Tabelle auf und füllen diese Schritt für Schritt. Da wir unser $n$ aus $ES^n$ noch nicht wissen, wird es als letztes gefüllt. Für die Berechnung von $f_M(2,1)$ starten wir also bei Block 0 mit der Belegung $R_0 = 0$ (unser Ergebnis, initial mit 0 belegt), $R_1 = 2$ (unser Register Nr. 1) und $R_2 = 1$ (unser Register Nr. 2). Das führt uns zur Tabelle:

Damit haben wir schon unseren ersten Schritt mit $ES^n(0(,0,2,1,...))$. $n$ können wir, wie gesagt, noch nicht füllen, da wir die Schritte noch nicht abzählen können. Nun schauen wir nach, was in Block 1 passiert. Hier wird das Register $R_1$ auf 0 getestet. Ist das wahr, so landen wir bei Block 3 (HALT). Ist es nicht wahr, bei Block 1. In unserem Fall landen wir bei Block 1 und füllen die zweite Spalte unserer Tabelle. Achtung: die einzutragende Registerbelegung ist die beim Eintritt gültige Belegung der Register, d.h. der Berechnungsschritt aus dem Block fand noch nicht statt. Wir füllen der Abkürzung halber noch schnell alle anderen Spalten:

Wir erreichen nach 7 Schritten den Block 3 (HALT) und beenden die Berechnung. Damit haben wir nun unser $f_M(2,1) = 0$ (Ergebnis steht ja am Ende Register $R_0$ wie wir wissen). Und auch unser $n$ aus $ES^n$ ist mittlerweile gefunden. Die Gesamtrechnung für den Lösungsweg sieht dann so aus:

$ES^7(0,(0,2,1,...) = ES^6(1,(0,2,1,...) = ES^5(2,(0,1,1,...) = ES^4(0,(0,1,0,...) = ES^3(1,(0,1,0,...) = ES^2(2,(0,0,0,...) = ES^1(0,(0,0,0,...) = (3,(0,0,0,...)$

und somit

$f_M(2,1) = 0$.

Schrittzahlfunktion

Die Schrittzahlfunktion $SZ(q,d)$ bedeutet nichts anderes, als die Anzahl der Schritte dir man ausgehend von der Konfiguration $d$ bei der Anfangsmarke $q$ benötigt um zu einer Endkonfiguration zu kommen. Nehmen wir einfach das beispiel von oben: Für $(q,d) = (0,(0,2,1))$ wäre $SZ(0,(0,2,1)) = 7$.

Gesamtschrittfunktion

Die Gesamtschrittfunktion $GS(q,d)$ ist die Endkonfiguration bei der Eingabe von $(q,d)$. Führen wir das beispiel von oben fort, so landen wir bei der Eingabe von $(0,(0,2,1))$ am Ende bei $(3,(0,0,0))$. Damit ist $GS(0,(0,2,1) = (3,(0,0,0))$.

Übergangsrelationen

Das wird uns noch häufiger begegnen, deswegen werde ich das mal hier noch in aller Deutlichkeit aufschreiben. Die Übergangsrelation ist auch definiert als:

$k_1 \vdash^t k_2\Longleftrightarrow{ES^t(k_1) = k_2}$

Hier bedeutet es, dass das Flussdiagramm mit der Eingabekonfiguration $k_1$ gestartet wird und in $t$ Schritten in die Endkonfiguration $k_2$ übergeht. Um das Beispiel von oben zu bemühen wäre das:

$(0,(0,2,1)) \vdash^7 (3,(0,0,0)) \Longleftrightarrow{ES^7(0,(0,2,1) =(3,(0,0,0))}$

That's it. Ggf. füge ich noch die anderen Definitionen der Übergangsrelation bei Gelegenheit ein. Die sollten aber ziemlich selbsterklärend sein wenn man das Beispiel sieht.

Wie immer gilt: bei Fehlern bitte melden!

Buchempfehlung

Datum: 4. Oktober 2012
Kategorie: Fernuni, Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url