Algorithmus

[ChillStudent]

Hallo, es geht hier um folgende Aufgaben:

a) Wir betrachten folgenden Algorithmus:

1. Der Algorithmus bekommt eine endliche Kette bestehend aus Nullen und Einsen.
2. Es werden nun in dieser Kette alle Vorkommen von Zeichenketten, welche “0110”, “100”
oder “0001” lauten, gesucht. Wurde mindestens ein solches Vorkommen gefunden, geht es
mit Schritt 3 weiter, sonst mit Schritt 5.
3. Es wird ein zufälliges Vorkommen ausgewählt und mit diesem wie folgt verfahren:
• Lautet es “0110” wird es in der Kette durch “0111” ersetzt
• Lautet es “100” wird es in der Kette durch “110” ersetzt
• Lautet es “0001” wird es in der Kette durch “1110” ersetzt
4. Weiter mit Schritt 2
5. Der Algorithmus gibt die Kette zurück.


b) Wir betrachten folgenden Algorithmus:

1. Der Algorithmus bekommt eine endliche Kette bestehend aus Nullen und Einsen.
2. Es wird nun das erste in dieser Kette gefundene Vorkommen, welches “0110”, “10” oder
“0001” lautet, gesucht.Wurde ein solches Vorkommen gefunden, geht es mit Schritt 3 weiter,
sonst mit Schritt 5.
3. Es wird mit diesem Vorkommen wie folgt verfahren:
• Lautet es “0110” wird es durch “0011” ersetzt
• Lautet es “10” wird es durch “01” ersetzt
• Lautet es “0001” wird es durch “1001” ersetzt
4. Weiter mit Schritt 2
5. Der Algorithmus gibt die Kette zurück.


In beiden Fällen soll man dies beantworten:

Ist dieser Algorithmus
1. deterministisch (im Ablauf)?
2. determiniert (im Ergebnis)?
3. stets terminierend?
Begründen Sie jeweils Ihre Antworten.



Meine eigentliche Frage wäre hierbei, ob meine Antwort so passt?
Lösung:

Aufgabe a)
1. Nicht deterministisch, da zufällig nach der Zeichenkette gesucht wird und eine unterschiedliche Reihenfolge entsteht.
2. Determinierend, da es bei der Auswahl welche Zeichenkette ersetzen werden soll, auch bei Mehrfachausführung immer dieselbe sein wird.
3. Terminierend, da das Algorithmus irgendwann enden wird, wenn es keine Zeichenkette mehr zu ersetzen gibt.

Aufgabe b)
1. Deterministisch, da der Algorithmus immer stets dieselbe Reihenfolge befolgt, weil es nicht alle auf einmal versucht zu ersetzen, sondern die erste Zeichenkette die der Algorithmus findet.
2. Determinierend, da es bei der Auswahl welche Zeichenkette ersetzen werden soll, auch bei Mehrfachausführung immer dieselbe sein wird.
3. Terminierend, da das Algorithmus irgendwann enden wird, wenn es keine Zeichenkette mehr zu ersetzen gibt.

 

[Bitfehler]

Beim zweiten Algo ist der Match 10 auch in dem Match 0110 enthalten. Es findet laut Aufgabe eine Oder-Auswahl statt. Je nachdem, ob hier zufällig gewählt wird oder nicht, kann dies evtl die Antwort beeinflussen.

 

[ChillStudent]

Danke dir für die Antwort.
Im Punkt 2 steht ja:
Es wird nun das erste in dieser Kette gefundene Vorkommen, welches “0110”, “10” oder
“0001” lautet, gesucht.Wurde ein solches Vorkommen gefunden, geht es mit Schritt 3 weiter,
sonst mit Schritt 5.

Daher ist es ja kein Zufall oder?

 

[stg]

Deine Antworten sind für mich alle unzulänglich. Damit will ich nicht sagen, dass sie falsch sind (ich habe mir selbst keine näheren Gedanken zu der Aufgabe gemacht..), sondern nur, dass ich anhand deiner Begründung in keinster Weise nachvollziehen kann, wieso die Aussage nun stimmen soll. Sowohl die Muster, die ersetzt werden sollen, als auch die Muster, die dabei eingefügt werden, scheinen keine Rolle zu spielen. Du stützt dich allein auf das Wort "zufällig".
Als kleine Anregung: Mach das Spielchen doch mal für "ersetz 0 durch 1 und ersetze 1 durch 0". Dann drehst du dich ewig im Kreis. Laut deiner Argumentation könnte man aber nun auch hier schließen, dass der Algorithmus terminiert.

 

[ChillStudent]

Ich habe zwar dein Beispiel verstanden, aber weiß dadurch leider immer noch nicht,
ob und wo genau mein Fehler wäre.

 

[CSHW89]

Dann mal ein komplexeres Beispiel:
(1) 00 -> 11
(2) 10 -> 01
(3) 101 -> 000
Terminiert der Algorithmus?
Nein:
0001 ->(1) 1101 ->(2) 1011 ->(3) 0001 ...

Du musst dir schon Gedanken machen, ob die Ersetzung der Muster irgendwie zusammenspielen kann, dass eine Eingabe so verändert wird, dass sie wieder die Eingabe ist.

 

[JStein52]

dass eine Eingabe so verändert wird, dass sie wieder die Eingabe ist

Bei Aufgabe a) kann das ja nie passieren. Wie wäre dann deine Antwort auf die drei Fragen ?

 

[ChillStudent]

Habe bei dem zweiten Algo Mehrfachausführungen gemacht, mit verschiedenen Eingaben und jedes mal hat es terminiert.
Ich wüsste jetzt nicht wieso es nicht terminieren sollte? Ich hab iwo en Denkfehler bestimmt.

 

[JStein52]

Lass uns mal bei Aufgabe a) bleiben.
Da wäre meine Antwort ist nicht deterministsich im Ablauf, ist nicht determinierend im Ergebenis aber er terminiert immer. Begründung: durch die Ersetzungen werden immer 0en durch 1en ersetzt, nie umgekehrt. Und irgendwann werden nur noch einzelne 0en vorkommen und der Algo endet dann. Es ist aber weder der Ablauf noch die Stellen wo diese einzelnen 0en sind vorhersagbar (wg. zufällig)

 

[ChillStudent]

Lautet es “0001” wird es in der Kette durch “1110” ersetzt.
hier wird doch die 1 durch die 0 ersetzt?

 

[JStein52]

Ja aber umgekehrt werden drei 0en durch 1en ersetzt. Und bei jeder Ersetzung werden es immer mehr 1en, solange bis keines der Muster mehr matched

 

[CSHW89]

@JStein52 Das wäre mit Sicherheit genügend als Erklärung für die Terminierung. Ähnlich kann man da bei b) vorgehen. Die 3. Regel '0001' -> '1001' fügt eine 1 hinzu, die anderen beiden lassen die Anzahl der '0'en und '1'en gleich. Somit ist die 3. Regel in einem Loop nicht enthalten. Die anderen beiden Regeln schieben die '1'en immer nach rechts, weshalb das Ursprungswort nie erreicht werden kann.

Das Beispiel von 'stg' und auch meins sollten nur verdeutlichen, dass man die Regeln bei der Betrachtung der Terminierung mit berücksichtigen muss.

 

[Xyz1]

a) Wir betrachten folgenden Algorithmus:

1. Der Algorithmus bekommt eine endliche Kette bestehend aus Nullen und Einsen.
2. Es werden nun in dieser Kette alle Vorkommen von Zeichenketten, welche “0110”, “100”
oder “0001” lauten, gesucht. Wurde mindestens ein solches Vorkommen gefunden, geht es
mit Schritt 3 weiter, sonst mit Schritt 5.
3. Es wird ein zufälliges Vorkommen ausgewählt und mit diesem wie folgt verfahren:
• Lautet es “0110” wird es in der Kette durch “0111” ersetzt
• Lautet es “100” wird es in der Kette durch “110” ersetzt
• Lautet es “0001” wird es in der Kette durch “1110” ersetzt
4. Weiter mit Schritt 2
5. Der Algorithmus gibt die Kette zurück.

Hallo, bei mir, getestet, terminiert er immer:

/**
* @author DerWissende on 04/25/2016
*/
public class JavaApplication1 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        for (int i = 0; i < 100000; i++) {
            String s0 = Long.toBinaryString(Double.doubleToLongBits(Math.random()));
            String s1 = new StringBuilder(s0).reverse().toString();
            System.out.println(replace(s0));
            System.out.println(replace(s1));
        }
    }

    private static String replace(String string) {
        for (int i = 0; i < string.length(); i++) {
            if (find(string, i, "0110")) {
                string = string.substring(0, i) + "0111" + string.substring(i + 4);
                return replace(string);
            } else if (find(string, i, "100")) {
                string = string.substring(0, i) + "110" + string.substring(i + 3);
                return replace(string);
            } else if (find(string, i, "0001")) {
                string = string.substring(0, i) + "1110" + string.substring(i + 4);
                return replace(string);
            }
        }
        return string;
    }

    private static boolean find(String string, int i, String string0) {
        if (i + string0.length() > string.length()) {
            return false;
        }
        for (int j = 0; j < string0.length(); j++) {
            if (string.charAt(i + j) != string0.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

deterministisch ist er auch, es sei denn, man wählt diese "Vorkommen§ zufällig.

Grüße

 

[JStein52]

es sei denn, man wählt diese "Vorkommen§ zufällig

Was bitte verstehst du an dem Wörtchen zufällig in Punkt 3.) nicht ?

 

[Xyz1]

Hey, nicht so aggressiv, unter Punkt 2. hätte man auch nicht-zufällig verstehen können. Leider ist die Beschreibung des Algos noch nicht so das Gelbe vom Ei, bei mir lautete sie anders.

 

[JStein52]

Sorry, war nicht agressiv gemeint. Aber es steht ja schliesslich eindeutig da. Und ob dir die Beschreibung des Algos gefällt oder nicht, sie ist nun mal so vorgegeben, oder was meinst du mit Beschreibung ? Und wie lautet sie denn bei dir

 

[Xyz1]

Also fassen wir mal zusammen: Der TO hat irgendwie keine Ahnung, dann ist meine Arbeit auch schon getan, mehr muss ich nicht zeigen. Ihr scheint zwischenzeitlich zu vergessen, dass ich nicht umsonst Der Wissende heiße.

Und ich hätte die umgangssprachliche Formulierung des Algos mehr imperativ und näher gelehnt an einen Maschine geschrieben (sonst könntest du wieder auf Interpretationsspielraum kommen):

Suche alle Vorkommen, die a, b und/oder c heißen, wähle eines davon zufällig, führe eine Substitution durch, und beginne wieder von vorne, bis keine Vorkommen mehr gefunden werden.

Schon verständlicher, gelle? Wenn ich arbeit delegieren will, müssen meine Untertanen auch wissen, was zu tun ist.

 

[JStein52]

Wenn ich arbeit delegieren will, müssen meine Untertanen auch wissen, was zu tun ist.

Du spinnst Es ging nicht um irgendwelche Vorkommen von irgendwas sondern es waren zwei ganz konkrete Aufgaben und die Untertanen haben es ja völlig genial gelöst so dass der TO schon lange kapiert hat was die richtige Lösung ist. Und wenn wir es nicht von alleine gewusst hätten dann hätten wir schon den Wissenden gefragt.

 

[Xyz1]

Sehr löblich. ... Aber mehr Offtopic sollten wir nicht schreiben.

Jedenfalls hält es immer irgendwann an, wie der Test mit der "Zufallswurst" gezeigt hat (bzw. gezeigt haben sollte).

 

[JStein52]

Jedenfalls hält es immer irgendwann an, wie der Test mit der "Zufallswurst" gezeigt hat

Nö, das ist kein Beweis. Es ging darum ob der Algo für alle möglichen Eingaben terminiert (u.a.) Das kannst du ja nicht dadurch beweisen dass du ein Javaprogramm schreibst, dann 10 ( meinetwegen auch 100) mögliche Eingaben testest und dann zufrieden sagst: siehst du, terminiert !

 

[Xyz1]

Du hast den Test doch gar nicht gelesen. Und auch hierbei gilt wieder: Test heißt nicht umsonst Test!

Wie es auch sei, Komplettlösung(en) gibt's von mir nicht.

 

[JStein52]

Ich habe deinen Test gelesen und sogar bei mir ausprobiert und weiss dass deine Schleife bis 10000 geht. Aber das ist völlig wurscht. Es geht hier um eine Begründung und nicht um einen Test. Test heisst deshalb Test weil man damit testet dass man einen gegebenen Algorithmus richtig implementiert hat. Ein Beweis (oder wie hier eine Begründung) ist was ganz anderes ! Häng nochmal 1 - 2 Semester theoretische Informatik dran !