Theoretische Informatik - Registermaschinen (kurz: RM)

Nächste Seite: Turingmaschinen (kurz: DTM oder Aufwärts: Berechenbarkeit Vorherige Seite: Berechenbarkeit Inhalt

Unterabschnitte

Registermaschinen (kurz: RM)

Registermaschinen-Berechenbar RM-berechenbar: Eine partielle Funktion $f: \mathbb{N}\rightarrow \mathbb{N}^{k}$ wird RM-berechenbar genannt, wenn es eine Registermaschine

gibt, so daß $f=f_{R}$ .

Aufbau und Befehle

Eine Registermaschine besteht aus

Befehlszähler:	Dieser zeigt auf den aktuellen Befehl.
Programmspeicher:	Hier findet man die Befehlszeilen, welche RM-Befehle beinhalten.
Akkumulator:	Das Register, auf dem die RM Operationen ausgeführt werden. Der Akkumulator wird auch mit bezeichnet.
unendlich viele Register:	Diese nehmen Werte (Variablen) auf
	Register werden mit bezeichnet.

Eine Registermaschine verfügt über folgende Befehle, die im Programmspeicher stehen können:

LOAD	Register in Akkumulator laden
STORE	Akkumulator in Register speichern
ADD	Zum Akkumulator ein Register hinzuaddieren
SUB	... subtrahieren
MULT	... multiplizieren
DIV	... dividieren
GOTO	Sprungbefehl. Der Befehlszähler wird verändert.
IF (... $\bowtie$ ...) THEN ...	Bedingte Anweisung
END	Der Befehlszähler wird auf $\infty$ gesetzt.
	Das Programm endet.

Zu jedem der fett geschriebenen Befehle kommt eine Variable³, von denen es drei Arten gibt:

Konstante	#	k
direkte Variable	nichts	c(i)
indirekte Variable	$\ast$	c(c(i))

Kostenmaße

Es existiert sowohl das uniforme als auch das logarithmische Kostenmaß. Weiterhin existiert eine Zeit und eine Platzkomplexität:

$t_{R}^{u}$	uniforme Zeit
$t_{R}$	logarithmische Zeit
$s_{R}^{u}$	uniformer Platz
$s_{R}$	logarithmischer Platz

Die Zeitkomplexität wird gemessen an den abgearbeiteten Befehlen. Die Platzkomplexität an den besuchten Registerzellen.

Für das logarithmische Kostenmaß wird die Wortlänge des zu bearbeitenden Wortes betrachtet. Hierbei gilt für das logarithmische Kostenmaß:

$\begin{displaymath}L(n)=\Bigl\{\begin{array}{ll} 1&f\uml {u}r\,n=0\\ 1+\lfloor \log n \rfloor&f\uml {u}r\,n\ge 1\\ \end{array}\end{displaymath}$

Effiziente Algorithmen

Als effizient gelten Algorithmen, für die die Laufzeit polynomiell beschränkt ist:

$\begin{displaymath}T(n)=O(poly(n)) \Leftrightarrow T(n) \leq p(n), wobei\,p(n)\,ein\, Polynom\end{displaymath}$

Fußnoten

... Variable ³: Ein-Adress-Registermaschinen haben dieselbe Mächtigkeit wie Null, zwei oder drei Adressregistermaschinen.

Nächste Seite: Turingmaschinen (kurz: DTM oder Aufwärts: Berechenbarkeit Vorherige Seite: Berechenbarkeit Inhalt