Komplexitätsmaße (1) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 14:19 Di 14.02.2006 | | Autor: | mathiash |
| Aufgabe | Es sei [mm]M_i, i\in\IN[/mm] eine Aufzählung von Turing-Maschinen, so daß für jede Turing-Maschine [mm]M[/mm] ein [mm]j\in\IN[/mm] existiert
mit [mm]f_M=f_{M_j}[/mm] (wobei wir zu gegebener TM [mm]M[/mm] mit [mm]f_M[/mm] die partielle Funktion bezeichnen, die von [mm]M[/mm] berechnet wird).
Die Aufzählung sei so, daß es eine universelle Turing-Maschine [mm]U[/mm] gibt mit [mm]f_U(i,x)=f_{M_i}(x)[/mm] für alle [mm]i\in\IN[/mm] und Strings [mm]x[/mm].
Eine Folge partieller Funktionen [mm]\Phi_j(x),j\in\IN[/mm] heißt Komplexitätsmaß genau dann, wenn gilt:
(B1) [mm]\Phi_i(x)[/mm] ist definiert genau dann, wenn [mm]f_{M_i}(x)[/mm] definiert ist (d.h. wenn die Berechnung von [mm]M_i[/mm] auf Eingabe [mm]x[/mm] terminiert).
(B2) Die Funktion [mm]R(i,x,m)=\begin{cases}1, & M_i(x)\texttt{ terminiert und }\Phi(i,x) = m\\0, &\texttt{sonst}\end{cases}[/mm]
ist eine totale Turing-berechenbare Funktion.
Dies sind die beiden Blum-Axiome.
Zeige:
(a) Rechenzeit (= Anzahl der Rechenschritte) und Speicherbedarf (=Anzahl benutzter Bandfelder) sind Komplexitätsmaße.
(b) [mm]\Phi(i,x) := f_{M_i}(x)[/mm] ist kein Komplexitätsmaß. |
Hallo zusammen,
diese Frage soll Beginn einer kleinen Serie zur abstrakten Komplexitätstheorie sein -es erwarten
jede(n) Interessierte(n) wunderbare schöne und klassische Resultate, die in Vorlesungen nicht unbedingt behandelt
werden.
Viele Grüße,
Mathias
|
|
|
