Also wir stellen jetzt das, was wir anhand von zwei Beispielen,

die wir in den letzten beiden Sitzungen gemacht haben, mal auf etwas formalere Füße.

Das heißt, wir verwandeln es von ad hoc-rumstochern in eine Methode, die sogenannte Potentialmethode.

Wir müssen dazu einiges an dem, was wir da im allgemeinen Rahmenwerk von algorithmischen

Heritten hatten, etwas formalisieren. Und zwar definieren wir mal kurz formal, was wir also

unter diesen Operationen verstehen, von denen wir uns Sequenzen ansehen, die dann in amortisiert

so und so langer Zeit laufen sollen. Dazu muss man erstens reden über Zustände,

die von diesen Operationen transformiert werden.

Zustände sind aber einfach Werte der globalen Variablen des Ganzen. Wir stellen uns immer

vor, wir haben eine Datenstruktur, die ist beschrieben durch irgendwelche globalen

Variablen und die ändern sich. Der jeweilige Inhalt dieser globalen Variablen,

den nennen wir Zustand. Nehmen wir aber als Beispiel hier dieses unbeschränkte Array,

das wir implementiert haben, was ist da der Zustand. Da gab es eine Variable n, das war

die Füllhöhe des Arrays im Moment, dann gab es W, das ist die Gesamtgröße gerade

alloziert des Arrays und dann gab es noch seinen tatsächlichen Inhalt. Und diese drei

Größen zusammen, die bestimmen halt den aktuellen Zustand. Die Menge dieser Zustände,

die kriegt einen Namen, die heißt Groß S. Und dann zeichnen wir noch einen besonderen

Zustand S0 in S aus. Das ist der Anfangszustand. Was war der Anfangszustand bei unserem unbeschränkten

Array? Es war dieser hier, 0 ist die Füllhöhe, 1 ist der insgesamt allozierte Platz und

naja, der tatsächliche Inhalt des Arrays ist natürlich auch einfach eine leere Liste

von Werten, weil wir keinen Inhalt haben. Gut. Ja, das sind Zustände und da auf diesen

Zuständen agieren Operationen. Als typischen Namen für so eine allgemeine Operation verwende

ich Groß X. So, und diese Operation, wenn ich sie ausführe, bewirken Zustandsübergänge.

Was sie tun, hängt natürlich vom aktuellen Zustand ab und abhängig von diesem aktuellen

Zustand liefern sie einen neuen Zustand. So, die schreiben wir so. Schreiben wir so ein

Pfeil zwischen zwei Zuständen, schreiben das X über den Pfeil und typischerweise nennen

wir den Nachzustand S'. Das ist ohnehin eine übliche Konvention, dass man Dinge, die nach

einer Operation vorliegen, mit einem Strich bezeichnet. Und die haben Kosten. Und die Kosten,

die hängen natürlich einerseits von der Operation und andererseits vom aktuellen

Zustand ab. Zum Beispiel könnte, wenn ich ein Pushback durchführe, der aktuelle Zustand

gerade so sein, dass ich neuen Platz alluzieren muss, dann dauert es sehr lange. Das bezeichnen

wir mit T index X von S. Und das S ist nicht umsonst dasselbe wie hier. Ja, also die Kosten,

die messen wir also in Abhängigkeit vom Ausgangszustand, nicht vom Zustand, der dann erreicht wird.

Ja, nehmen wir mal wieder ein Beispiel. Nehmen wir also eine Pushbackoperation. Gut, die sollte

irgendein Argument haben, aber das Argument interessiert mich nicht. So, die bewirkt einen

Zustandsübergang von N, W und irgendwelchem Inhalt. Der Inhalt ist für die ganze Rechnung

wie immer egal. Und da kommt raus im Normalfall, im Normalfall heißt ohne reallocate, N plus

W. Also es wird ein weiteres Element ins Array geschrieben, der Füllstand erhöht sich um

eins, W bleibt unverändert und dann kommt hier noch der neue Inhalt, der wie gesagt

für die meisten Betrachtungen egal ist. So, das ganze also falls N kleiner W, das ist

die formale Bedingung dafür, dass kein reallocate stattfindet. Wir sehen, der Zustand ist genug,

um tatsächlich auch die wichtigen Informationen zu extrahieren, um zu sehen, wie lange es

dauert. Na ja, die Zeit in diesem Falle T, T von Pushback, also T Pushback von N, W und

W ist egal, ist dann per Konvention einfach gleich eins. Also gut, es geht irgendwie in

konstanter Zeit, welche konstante Zeit das genau ist, ist uns also egal. Gut. Und das,

was uns nachher eigentlich interessiert, also was wir zeitlich messen wollen, sind ja nicht

einzelne Operationen, sondern Sequenzen von Operationen und zwar solche, die beginnen

beim Anfangszustand. Das heißt, als allgemeinen Namen für Sequenzen nehmen wir aus irgendeinem

Grund F. So, ich hoffe, ich halte es durch die Zahloperation mit M weiterhin zu bezeichnen,

also eine Sequenz von M Operationen x1 bis xM. Die bewirken wiederum Zustandsübergänge.