{"id":512,"date":"2012-10-04T18:34:54","date_gmt":"2012-10-04T16:34:54","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=512"},"modified":"2025-11-25T21:37:39","modified_gmt":"2025-11-25T20:37:39","slug":"ti-einzelschrittfunktion","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=512","title":{"rendered":"TI: Einzelschritt- und Schrittzahlfunktion sowie \u00dcbergangsrelationen (Update)"},"content":{"rendered":"

Einzelschrittfunktion<\/h2>\n

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\u00f6chten nun das Ergebnis berechnen. Dazu ein Beispiel anhand eines Flussdiagramms aus dem Skript.<\/p>\n

Beispiel <\/strong>(das – in Block 1 und 2 ist mangels mathematischer Zeichen in Open Office Draw als arithmetische Differenz zu deuten):<\/p>\n

\"\"<\/a><\/p>\n

Wir m\u00f6chten z.B. nun \\(f_M(2,1)\\) berechnen (okay, das Beispiel ist etwas bl\u00f6d, da das Ergebnis in \\(R_0\\) immer 0 ist, aber sei es drum). Wir verwenden hierzu die Einzelschritt-Notation f\u00fcr 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\u00fchrenden 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\u00fcllt und werden mit \\(0,…\\) angedeutet.<\/p>\n

Wir stellen also eine kleine Tabelle auf und f\u00fcllen diese Schritt f\u00fcr Schritt. Da wir unser \\(n\\) aus \\(ES^n\\) noch nicht wissen, wird es als letztes gef\u00fcllt. F\u00fcr 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\u00fchrt uns zur Tabelle:<\/p>\n

\"\"<\/a><\/p>\n

Damit haben wir schon unseren ersten Schritt mit \\(ES^n(0(,0,2,1,…))\\). \\(n\\) k\u00f6nnen wir, wie gesagt, noch nicht f\u00fcllen, da wir die Schritte noch nicht abz\u00e4hlen k\u00f6nnen. 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\u00fcllen die zweite Spalte unserer Tabelle. Achtung: die einzutragende Registerbelegung ist die beim Eintritt g\u00fcltige Belegung der Register, d.h. der Berechnungsschritt aus dem Block fand noch nicht<\/strong> statt. Wir f\u00fcllen der Abk\u00fcrzung halber noch schnell alle anderen Spalten:<\/p>\n

\"\"<\/a><\/p>\n

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\u00fcr den L\u00f6sungsweg sieht dann so aus:<\/p>\n

\\(ES^7(0,(0,2,1,…)\\)
\n\\(=ES^6(1,(0,2,1,…) \\)
\n\\(=ES^5(2,(0,1,1,…)\\)
\n\\(=ES^4(0,(0,1,0,…)\\)
\n\\(=ES^3(1,(0,1,0,…)\\)
\n\\(=ES^2(2,(0,0,0,…)\\)
\n\\(=ES^1(0,(0,0,0,…)\\)
\n\\(=(3,(0,0,0,…)\\)
\nund somit
\n\\(f_M(2,1) = 0\\).<\/p>\n

Schrittzahlfunktion<\/h2>\n

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\u00f6tigt um zu einer Endkonfiguration zu kommen. Nehmen wir einfach das beispiel von oben: F\u00fcr \\((q,d) = (0,(0,2,1))\\) w\u00e4re \\(SZ(0,(0,2,1)) = 7\\).<\/p>\n

Gesamtschrittfunktion<\/h2>\n

Die Gesamtschrittfunktion \\(GS(q,d)\\) ist die Endkonfiguration bei der Eingabe von \\((q,d)\\). F\u00fchren 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))\\).<\/p>\n

\u00dcbergangsrelationen<\/h2>\n

Das wird uns noch h\u00e4ufiger begegnen, deswegen werde ich das mal hier noch in aller Deutlichkeit aufschreiben. Die \u00dcbergangsrelation ist auch definiert als:<\/p>\n

\\(k_1 \\vdash^t k_2\\Longleftrightarrow{ES^t(k_1) = k_2}\\)<\/p>\n

Hier bedeutet es, dass das Flussdiagramm mit der Eingabekonfiguration \\(k_1\\) gestartet wird und in \\(t\\) Schritten in die Endkonfiguration \\(k_2\\) \u00fcbergeht. Um das Beispiel von oben zu bem\u00fchen w\u00e4re das:<\/p>\n

\\((0,(0,2,1)) \\vdash^7 (3,(0,0,0)) \\Longleftrightarrow{ES^7(0,(0,2,1) =(3,(0,0,0))}\\)<\/p>\n

That’s it. Ggf. f\u00fcge ich noch die anderen Definitionen der \u00dcbergangsrelation bei Gelegenheit ein. Die sollten aber ziemlich selbsterkl\u00e4rend sein wenn man das Beispiel sieht.<\/p>\n

Wie immer gilt: bei Fehlern bitte melden!<\/p>\n","protected":false},"excerpt":{"rendered":"

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\u00f6chten 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 … <\/p>\n

\u201eTI: Einzelschritt- und Schrittzahlfunktion sowie \u00dcbergangsrelationen (Update)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,4],"tags":[],"class_list":["post-512","post","type-post","status-publish","format-standard","hentry","category-fernuni","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/512","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=512"}],"version-history":[{"count":21,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions"}],"predecessor-version":[{"id":3506,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions\/3506"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}