Termination beweisen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:49 Sa 24.04.2010 | | Autor: | DerGraf |
| Aufgabe | Vorbedingung: Zeichenkette s
Nachbedingung: Zeichenkette s, wobei die Muster ba, ca, cb nicht mehr in s entalten sind
while eines der Muster (ba, ca, cb) ist noch in s enthalten do
ersetze ba in s durch ab
ersetze ca in s durch ac
ersetze cb in s durch bc
end while
return s |
Dieser Pseudocode ist mir gegeben und ich soll zeigen, ob er terminiert oder nicht. Ich würde sagen, ja und habe auch schon ein C-Programm nach dieser Vorlage erstellt, welches mich in meiner Vermutung bestätigt. Doch sieht dieser Algorithmus sehr nach dem Markov-Algorithmus aus, welcher nach sämtlichen Internetseiten nur durch eine haltende Regel terminiert. Hab ich hier einen Denkfehler?
Hier ist erstmal mein Programm:
Ich habe einfach a=1, b=2 und c=3 gesetzt. Das ändert nichts an der Termination, erleichtert mir aber das Programmschreiben :)
#include<stdio.h>
bool test(int s[], int n)
{
int i;
for(i=0; i<n-1; i++)
{
if(s[i]==2 && s[i+1]==1) return true;
if(s[i]==3 && s[i+1]==1) return true;
if(s[i]==3 && s[i+1]==2) return true;
}
return false;
}
int main()
{
int n;
scanf("%d",& n);
int s[n];
int i,t;
for (i=0; i<n; i++)
{
scanf("%d",& s[i]);
}
while(test(s,n))
{
for(i=0; i<n-1; i++)
{
if(s[i]==2 && s[i+1]==1)
{
t=s[i];
s[i]=s[i+1];
s[i+1]=t;
}
if(s[i]==3 && s[i+1]==1)
{
t=s[i];
s[i]=s[i+1];
s[i+1]=t;
}
if(s[i]==3 && s[i+1]==2)
{
t=s[i];
s[i]=s[i+1];
s[i+1]=t;
}
}
}
for(i=0; i<n; i++)
{
printf("%d", s[i]);
}
}
Die Ausgabe stimmt soweit. Ich hebe dies schon mit ein paar Zahlenfolgen getestet. Es wurde immer von der kleinen Zahl nach oben sortiert. Ich würde mich freuen, wenn mir jemand sagen könnte, ob meine Überlegungen stimmen und was es mit dieser Halteregel auf sich hat.
Mit freundlichen Grüßen
DerGraf
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:39 So 25.04.2010 | | Autor: | felixf |
Hallo!
> Vorbedingung: Zeichenkette s
> Nachbedingung: Zeichenkette s, wobei die Muster ba, ca, cb
> nicht mehr in s entalten sind
>
> while eines der Muster (ba, ca, cb) ist noch in s enthalten
> do
>
> ersetze ba in s durch ab
> ersetze ca in s durch ac
> ersetze cb in s durch bc
>
> end while
> return s
>
> Dieser Pseudocode ist mir gegeben und ich soll zeigen, ob
> er terminiert oder nicht. Ich würde sagen, ja
Damit hast du auch Recht.
> Doch sieht dieser Algorithmus sehr nach dem Markov-Algorithmus aus,
Du meinst ![[]](/images/popup.gif) sowas? Es ist so etwas aehnliches.
> welcher nach sämtlichen Internetseiten nur durch eine
> haltende Regel terminiert. Hab ich hier einen Denkfehler?
Bedenke, dass deine while-Schleife eine Bedingung enthaelt. Damit ist es nicht wirklich ein Markov-Prozess.
> Hier ist erstmal mein Programm:
>
> Ich habe einfach a=1, b=2 und c=3 gesetzt. Das ändert
> nichts an der Termination, erleichtert mir aber das
> Programmschreiben :)
Wenn du es mit [code]...[/code] eingebunden haettest, koennte man dein Posting auch richtig zitieren.
> Die Ausgabe stimmt soweit. Ich hebe dies schon mit ein paar
> Zahlenfolgen getestet. Es wurde immer von der kleinen Zahl
> nach oben sortiert. Ich würde mich freuen, wenn mir jemand
> sagen könnte, ob meine Überlegungen stimmen und was es
> mit dieser Halteregel auf sich hat.
Ja, es ist ein Sortieralgorithmus. Er funktioniert aehnlich wie bubble sort, in dem Sinne dass falsch sortierte Paare "richtig" sortiert werden, bis es keine unsortierten mehr gibt.
Um die Korrektheit zu beweisen, kannst du wie folgt vorgehen:
Angenommen, wie in einem Programm ist die Zeichenkette [mm] $s_0, \dots, s_{n-1}$. [/mm] Dann setze [mm] $f(s_0, \dots, s_{n-1}) [/mm] := [mm] \sum_{i=0}^{n-1} [/mm] i [mm] s_i$. [/mm] Zeige, dass jedes Austauschen eines Musters wie im Programm den Wert von $f$ erhoeht. Da der Wert von $f$ nach oben beschraenkt ist (durch [mm] $\sum_{i=0}^{n-1} [/mm] i [mm] \cdot [/mm] 3$) kann das Programm also nicht ewig etwas ersetzen -- wenn jedoch nichts mehr zu ersetzen ist, ist die Bedingung der while-Schleife nicht mehr erfuellt, und das Programm bricht ab.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:16 So 25.04.2010 | | Autor: | DerGraf |
Vielen Dank für deine Antwort. Die Aufgabe ist soweit fertig :)
Gruß
DerGraf
|
|
|
|
