{"id":1261,"date":"2013-04-07T12:48:06","date_gmt":"2013-04-07T10:48:06","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1261"},"modified":"2025-11-25T23:10:53","modified_gmt":"2025-11-25T22:10:53","slug":"tib-maschinenmodelle-und-komplexitatsklassen-lernziele-ke1","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1261","title":{"rendered":"TIB: Maschinenmodelle und Komplexit\u00e4tsklassen (Lernziele KE1, Update 4)"},"content":{"rendered":"

Update 6<\/strong>: Gro\u00dfe Fehlerkorrektur. Finde ich super, dass Ihr euch die M\u00fche macht, die Fehler aufzuschreiben. Das hilft dem nachfolgenden Leser ungemein! Danke Walter.<\/p>\n

Update 5<\/strong>: Fehlende Marke 4 im Flussdiagramm hinzugef\u00fcgt. Die Berechnung musste daher geringf\u00fcgig ge\u00e4ndert werden (Danke, Alex).<\/p>\n

Update 4<\/strong>: Tippfehler beseitigt in Lernziel 3 nach Kommentar von Carina.<\/p>\n

Update 3<\/strong>: Nach dem Einwand von Philipp habe ich das Flussdiagramm abge\u00e4ndert. Im Skript wird als Ausgabeband 0 verwendet, Band 1 ist das Eingabeband und der Rest sind Arbeitsb\u00e4nder. Ich habe mich hier nicht so ganz daran gehalten, da es f\u00fcr das Beispiel unwesentlich ist.<\/p>\n

Ist aber nat\u00fcrlich nicht sch\u00f6n wenn ich mich nah am Skript bewegen und Details vernachl\u00e4ssige, die das Verst\u00e4ndnis erschweren. Daher: Danke f\u00fcr das aufmerksame Lesen \ud83d\ude09 Band 0<\/strong> ist nun das Ausgabeband.<\/p>\n

Update<\/strong>: Mittlerweile ist KE7 von TIA<\/a> bereits fertig.<\/p>\n

Update:<\/strong> Hier habe ich bei der \u00dcberarbeitung einige Fehler entfernt, die evtl. zu Verst\u00e4ndnisproblemen gef\u00fchrt h\u00e4tten.<\/p>\n

Lernziel 1<\/h2>\n

Definition der Komplexit\u00e4tsma\u00dfe Zeit und Band f\u00fcr Turing-Maschinen<\/em><\/p>\n

Bevor wir die Komplexit\u00e4tsma\u00dfe definieren k\u00f6nnen, m\u00fcssen wir zun\u00e4chst wissen was Komplexit\u00e4t ist. Hierzu ist im Skript ein sch\u00f6nes Beispiel gegeben: mit der Schrittzahlfunktion<\/a> haben wir die G\u00fcte einer Maschine, bzw. eines konkreten Programms. Wir haben jedoch ein gesteigertes Interesse an der Komplexit\u00e4t des effizientesten Programms<\/strong> f\u00fcr einen Algorithmus. D.h. wir suchen obere (jede Schranke, die \u00fcber der Schranke eines bereits bekannten Programms f\u00fcr unseren Algorithmus liegt) und untere Schranken (die minimalste Schranke f\u00fcr alle Programme zu unserem Algorithmus).<\/p>\n

Zus\u00e4tzlich dazu wird im Skript der Begriff Sprache definiert:<\/p>\n

Sei \\(M\\) eine \\(TM\\) \u00fcber dem Ein-\/Ausgabealphaber \\(\\Sigma\\). Dann ist<\/p>\n

\\(L_M := \\{x\\in\\Sigma^{*}\\mid f_M(x) = \\varepsilon\\}\\) die von \\(M\\) erkannte Sprache.<\/p>\n

Ist \\(f_M\\) total, so sagen wir: \\(M\\) entscheidet die Sprache \\(L_M\\).<\/p><\/blockquote>\n

Wie wir wissen beinhaltet \\(\\Sigma^{*}\\) alle W\u00f6rter \u00fcber dem Eingabealphabet \\(\\Sigma\\). H\u00e4lt die Maschine \\(TM\\) in einem Endzustand wenn ein Wort \\(x\\) aus \\(\\Sigma^{*}\\) in diese eingegeben wird, so wird das Wort \\(x\\) von der Maschine \\(TM\\) akzeptiert. Alle von \\(TM\\) akzeptierten Worte aus \\(\\Sigma^{*}\\) werden die von \\(TM\\) akzeptierte Sprache \\(L_M\\) genannt.<\/p>\n

Erkannte\/Akzeptierte Sprachen sind die rekursiv aufz\u00e4hlbaren<\/a> Sprachen, d.h. sie terminieren ggf. nicht f\u00fcr jede aber in jedem Fall f\u00fcr jede akzeptierte Eingabe. Wir haben also eine Positiv- oder Negativentscheidung f\u00fcr eine akzeptierte Eingabe (aber nicht beides). D. h. die Maschine h\u00e4lt nur bei akzeptierten Eingaben. Bei anderen Eingaben l\u00e4uft sie ewig weiter. Das Problem dabei ist, dass wir letztendlich nicht wissen, ob eine Eingabe nun tats\u00e4chlich erkannt \/ akzeptiert wird. Evtl. rechnet die Maschine ja noch f\u00fcr die Eingabe…<\/p>\n

Die entscheidbaren<\/a> Sprachen – also bei den Eingaben, wo die Maschine in jedem Fall mit einer Positiv- oder Negativentscheidung terminiert, \\(f_M\\) ist als \u00fcberall definiert, d.h. total – nennen wir rekursiv. Hier haben wir f\u00fcr jede Eingabe (irgendwann) einen finalen Zustand der Maschine, der uns f\u00fcr eine EIngabe \\(X\\) die Entscheidung mitteilt.<\/p>\n

Was sind aber nun Komplexit\u00e4tsma\u00dfe Zeit\/Band f\u00fcr \\(TM\\)? Eine \\(TM\\) ist ein abstraktes Modell eines Rechners. Mit der Schrittzahlfunktion \\(t_M\\) haben wir unsere Rechenzeit f\u00fcr die Maschine \\(M\\), d.h. \\(t_M\\) ist unsere Zeitkomplexit\u00e4t<\/strong>. Der Bandbedarf ist unser \\(s_M\\), d.h. unsere Bandkomplexit\u00e4t.<\/strong> Sie gibt an wie viele der Felder beim erreichen der Endkonfiguration (d.h. das Ergebnis steht auf dem Ausgabeband) auf den Arbeitsb\u00e4ndern benutzt wurden. Durch die im Skript gemachten Einschr\u00e4nkungen des Befehlssatzes (Ein- und Ausgabeband kann nicht als Arbeitsband missbraucht werden) f\u00fcr die Maschine, brauchen Ein- und Ausgabeband nicht in die Berechnung einbezogen zu werden. Versuchen wir es an einem einfachen Beispiel zur Verdeutlichung.<\/p>\n

Beispiel f\u00fcr Band- und Zeitkomplexit\u00e4t<\/strong><\/p>\n

Wir nehmen eine simple Maschine \\(M\\), die uns \\(f(n) := n+1\\) ausgibt.<\/p>\n

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

Funktionsweise: die Maschine tut nichts anderes als die Eingabe von Band 1 (Eingabeband) auf Band 2 (Arbeitsband) zu schreiben, eine 1 hinzuzuf\u00fcgen, dann den Lesekopf wieder an den Anfang von Band 2 zu setzen und seinen Inhalt auf Band 0 (Ausgabeband) zu schreiben. Beachtet: \\(c\\) ist das Anfangs- und \\(\\\\\\)$ das Endzeichen. So k\u00f6nnen wir auf den B\u00e4ndern von Wortanfang bis Wortende navigieren. Nachdem wir ein Zeichen auf ein Band geschrieben haben m\u00fcssen wir den Schreibkopf auf Band \\(0\\) auch nicht eine Stelle weiter r\u00fccken, da wir im Skript die \\(TM\\) dahingehend erweitert haben, dass das automatisch passiert.<\/p>\n

Analysieren wir zun\u00e4chst die Zeit und nehmen als Eingabe ein \\(n=2=11\\). Nehmt euch am besten Stift und Paper und spielt die Maschine nach. Wir gehen davon aus, dass sich der Lesekopf zu Beginn auf Band 0 bei \\(c\\) befindet, bei Band 1 und 2 jedoch direkt auf dem ersten leeren Feld nach dem Anfangszeichen \\(c\\). Am Ende sollten die Folge der besuchten Marken so aussehen:<\/p>\n

0,1,2,3,4,1,2,3,4,1,5,6,7,6,7,6,7,6,8,9,10,11,9,10,11,9,10,11,9,12.<\/p>\n

Wenn ich mich nicht verz\u00e4hlt habe sind es genau 30 besuchte Marken.<\/p>\n

Fangen wir also mit der Absch\u00e4tzung an:<\/p>\n