Aufwandsfunktionen

Zeitaufwand:  Die Zeitkomplexität behandelt die Zeitspanne, innerhalb derer die Ergebnisse ausgegeben werden. Diese „Rechendauer“ ist abhängig von der Eingabe: Man definiert in der Regel den Zeitaufwand als Funktion \(t_\pi : \mathbb {N}_0 \rightarrow \mathbb {N}_0\) mit \(t_\pi (n) =\) maximale Zeit/Anzahl der Schritte, die das Programm \(\pi \) für irgendeine Eingabe der Länge \(n\) bis zum Anhalten benötigt. Meist verlangt man, dass \(\pi \) stets terminiert, damit \(t_\pi \) überall definiert ist. Die uniforme Zeitkomplexität geht davon aus, dass für jeden Befehl (Zuweisung, Ausdruck usw.) gleich viel Zeit in Anspruch genommen wird (in der Realität ist dies oft nicht so).

Größenordnung:  Bei der Zeitkomplexität interessiert man sich meist nur für eine Abschätzung, bei der multiplikative und additive Konstanten ignoriert werden. Zur Beschreibung der Größenordnung einer reellwertigen Funktion werden die Landau-Symbole verwendet.

Landau-Symbole:  Sei \(f: \mathbb {R}^+ \rightarrow \mathbb {R}^+\). Dann sind die Landau-Symbole wie folgt definiert:

  • \(\mathcal {O}(f) = \{g: \mathbb {R}^+ \rightarrow \mathbb {R}^+ \;|\; \exists _{C > 0} \exists _{n_0 \in \mathbb {N}} \forall _{n \ge n_0}\; g(n) \le C \cdot f(n)\}\)

  • \(o(f) = \{g: \mathbb {R}^+ \rightarrow \mathbb {R}^+ \;|\; \forall _{\varepsilon > 0} \exists _{n_0 \in \mathbb {N}} \forall _{n \ge n_0}\; g(n) \le \varepsilon \cdot f(n)\}\)

  • \(\Omega (f) = \{g: \mathbb {R}^+ \rightarrow \mathbb {R}^+ \;|\; \exists _{C > 0} \exists _{n_0 \in \mathbb {N}} \forall _{n \ge n_0}\; f(n) \le C \cdot g(n)\}\)

  • \(\omega (f) = \{g: \mathbb {R}^+ \rightarrow \mathbb {R}^+ \;|\; \forall _{\varepsilon > 0} \exists _{n_0 \in \mathbb {N}} \forall _{n \ge n_0}\; f(n) \le \varepsilon \cdot g(n)\}\)

  • \(\Theta (f) = \{g: \mathbb {R}^+ \rightarrow \mathbb {R}^+ \;|\; \exists _{C_1, C_2 > 0} \exists _{n_0 \in \mathbb {N}} \forall _{n \ge n_0}\; C_1 \cdot f(n) \le g(n) \le C_2 \cdot f(n)\}\)

Es gilt \(g \in \Omega (f) \;\Leftrightarrow \; f \in \mathcal {O}(g)\) sowie \(g \in \omega (f) \;\Leftrightarrow \; f \in o(g)\).
Außerdem ist \(\Theta (f) = \mathcal {O}(f) \cap \Omega (f)\).

Komplexitätsklassen:  In der Praxis betrachtet man meistens nur die Funktionsklassen \(\mathcal {O}(1)\) (konstante Fkt.), \(\mathcal {O}(\log n)\) (höchstens logarithmisch wachsende Fkt.), \(\mathcal {O}(\sqrt [k]{n})\) (höchstens mit einer \(k\)-ten Wurzel wachsende Fkt.), \(\mathcal {O}(n)\) (lineare Fkt.), \(\mathcal {O}(n \cdot \log n)\) („ein wenig“ stärker als linear wachsende Fkt.), \(\mathcal {O}(n^2)\) (höchstens quadratisch wachsende Fkt.), \(\mathcal {O}(n^k)\) (höchstens polynomiell vom Grad \(k\) wachsende Fkt.) und \(\mathcal {O}(2^n)\) (höchstens exponentiell zur Basis 2 wachsende Fkt.).

Registermaschinen und andere Rechenmodelle

Registermaschine:  Eine Registermaschine ist wie ein kleiner Mikroprozessor aufgebaut und besteht aus

  • einer Zentraleinheit mit sechs Registern (X, Y und Z für arithmetische/logische Operationen, Adressregister A, Befehlsregister B und Flagregister F),

  • einem endlichen Programmspeicher, in dem nacheinander die Befehle des abzuarbeitenden (endlichen) Programms stehen

  • sowie einem unendlich langen Rechenspeicher mit durchnummerierten Speicherzellen, die jeweils eine beliebig große ganze Zahl aufnehmen können.

Programmieren mit der Registermaschine:  Jedes Ada-Programm lässt sich ein Registermaschinenprogramm übersetzen. Dieser Prozess lässt sich automatisieren (Compiler). Alle Kontrollstukturen lassen sich mit dem bedingten Sprung jump b realisieren (vgl. goto und Marken in Ada).

Befehle der Registermaschine: 

load V,c

V := c

copy V,V’ V := V’
read V

V := R

write V R := V
add

X := Y + Z

sub X := Y - Z
succ

X := X + 1

shift X := X div 2
comp (v) if XvY then F := 1 else F := 0 fi
jump b if F=1 then B := b else B := B + 1 fi
stop

Anhalten

\(V, V’\) Register, \(c \in \mathbb {Z}\), \(b \in \mathbb {N}_0\), \(Rk\) \(k\)-te Speicherzelle, \(v \in \{>, \ge , <, \le , =, \not =\}\), außer bei jump wird nach jedem Befehl B um eins erhöht.

Diese Befehle finden sich bei allen Mikroprozessoren (bei diesen kommen Befehle hinzu).
Die Befehle eines Programms werden bei 0 beginnend durchnummeriert.

Kellerautomat:  Keller/Pushdown-Automaten besitzen ein Eingabe- und ein Ausgabeband, sowie einen Keller, auf den Daten abgelegt werden können. Lässt man das Kellerband weg, so erhält man einen endlichen Automaten (also eine Maschine, die eine Eingabe von links nach rechts liest, synchron dazu ein Ausgabeband beschreibt und nur endlich viel Information in ihrer Zustandsmenge speichern kann).

Endlicher Automat:  \(A = (Q, \Sigma , \Omega , \delta , Q_0, F)\) heißt endlicher Automat, falls

  • \(Q\) nicht-leere endliche Menge (Zustandsmenge),

  • \(\Sigma \) nicht-leere endliche Menge (Eingabealphabet),

  • \(\Omega \) nicht-leere endliche Menge (Ausgabealphabet),

  • \(\delta \subseteq Q \times \Sigma \times Q \times \Omega ^\ast \) endliche Menge (Überführungsrelation),

  • \(Q_0 \subseteq Q\) (Menge der Anfangszustände),

  • \(F \subseteq Q\) (Menge der Endzustände).

\(A\) heißt deterministisch, falls es zu jedem Paar \((q,a) \in Q \times \Sigma \) höchstens ein Paar \((q’,w) \in Q \times \Omega ^\ast \) gibt, sodass \((q,a,q’,w) \in \delta \) ist. \(A\) heißt endlicher Akzeptor, falls \(\Omega \) entfällt, \(\delta \subset Q \times \Sigma \times Q\) ist und es genau einen Anfangszustand \(Q_0 \in Q\) gibt.

Grafische Darstellung:  Die Zustände werden durch Kreise dargestellt, die Übergänge durch Kanten (Pfeile), an die Eingabe/Ausgabe getrennt durch „/“ geschrieben werden. Beim Akzeptor entfällt die Ausgabe, dann steht nur die Eingabe über dem Pfeil. Anfangszustände erhalten einen Pfeil („aus dem Nichts“) und Endzustände werden doppelt umkringelt.

Interpretation als Automat:  \(L(A) = \{(u,v) \in \Sigma ^\ast \times \Omega ^\ast \;|\;\) es gibt eine Folge von Übergängen, die einen Anfangszustand aus \(Q_0\) bei der Eingabe von \(u\) in einen Endzustand aus \(F\) überführen und hierbei die Ausgabe \(v\) erzeugen \(\}\) heißt die von \(A\) realisierte Relation.
Falls \(A\) deterministisch ist, wird \(L(A)\) zu einer (partiellen) Abbildung \(\operatorname {Res}_A: \Sigma ^\ast \rightarrow \Omega ^\ast \). Diese heißt dann die von \(A\) realisierte Abbildung oder die Resultatsfunktion von \(A\).

Interpretation als Akzeptor:  \(L(A) = \{u \in \Sigma ^\ast \;|\;\) es gibt eine Folge von Übergängen, die den Anfangszustand \(Q_0\) bei der Eingabe von \(u\) in einen Endzustand aus \(F\) überführen \(\}\) heißt die von \(A\) erkannte Sprache.