Blatt 15
| Aufgabe 2 | zurück |
Geben Sie eine Komplexitätsklasse an, die alle Sprachen enthält, deren charakteristische Funktion von einem LOOP-Programm nach Definition (d.h. nur Wertzuweisungen der Form xi := xj + c bzw. xi := xj - c sind zugelassen) mit nur zwei LOOP-Anweisungen berechnet werden kann.
Begründung!
| Lösung | zurück |
Wie sieht das Programm im schlimmsten Fall (größtes Ergebnis) aus?
LOOP x DO
x := x + c1;
x := x + c2;
...
x := x + cn;
LOOP x DO
x := x + d1;
...
x := x + dm;
END
END
Um die Komplexitätsklasse zu erhalten, müssen wir den Aufwand abschätzen und zwar nach oben, weil O(n) gerade eine obere Schranke angibt.
Es kommen nur Additionen vor, also müssen wir diese abschätzen und das machen wir mithilfe von k.
k sei gerade so groß, wie alles, was bei einem Durchlauf addiert wird.
d.h. k = Summe über alle vorkommenden c's und d's
Mit dem k haben wir jetzt also alle Additionen vor und im innerern LOOP abgeschätzt (zu einer zusammengefasst x := x + k).
Da wir nach oben abschätzen wollen, sagen wir einfach, alle Additionen kämen innerhalb des inneren LOOP vor.
Da dieses gerade x mal ausgeführt wird erhalten wir für den gesamten Teil innerhalb der äßeren Loop-Schleife die Komplexität O(x * k).
Jetzt kommt noch die äußere Schleife hinzu und damit ergibt sich die uniforme Komplexität O(x * k^x).
Wir wollen das Ergebnis im logarithmischen Kostenmaß, also müssen wir noch die Länge der Variablen bei jedem Durchgang berücksichtigen.
Nehmen wir an, unsere Eingabe habe in der TuringMaschine n Stellen.
Daraus ergibt sich, dass sie dezimal höchstens 2^n beträgt.
(binär gespeichert
-> n Stellen
=> maximal 1111...11, also 2^(n-1)+2^(n-2)+...+2^0 = 2^n - 1
2^n - 1 < 2^n)
Unser dezimales Ergebnis ist also in O(2^n * k^[2^n]) und damit sind auch die Kosten pro Schritt sicher innerhalb dieser Klasse(, denn das bedeutete pro Schritt alles in Unärkodierung durchlaufen).
Die Anzahl der Schritte, die die Maschine durchläuft liegt auch innerhalb dieser Komplexität (das bedeutete pro Schritt 1 addieren).
Unser Ergebnis ist somit: #Schritte * $ pro Schritt
Uk DTIME ([ 2^n * k^[2^n] ]*[ 2^n * k^[2^n] ]) = Uk DTIME ([ 2^n * k^[2^n] ]^2)