GGT Beweis der Finitheit
Neue Frage »

18.01.2007, 14:51 Moeki Auf diesen Beitrag antworten »
GGT Beweis der Finitheit
Moin Moin.


Seien x,y,u und v Variablen vom Typ Interger sowie m und n beliebige natürliche Zahlen. Zu Beginn des Spiels werden x und u auf m sowie y und v auf n gesetzt.

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

VAR 	x,y,u,v : INTEGER;
          m,n	   : NAT;

	RANDOM(m);
	RANDOM(n);

	x:=m;
	u:=m;
	y:=n;
	v:=n;


Anschließend führt man so oft, wie möglich folgenden Zug aus:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

	WHILE (x<>y) DO
	BEGIN
              IF x<y THEN 
                       BEGIN 
                               y:=y-x;
                               v:=v+u;
		       END;

		IF y<x THEN
			BEGIN
				x:=x-y;
				u:=u+v;
			END;
	END;


Interpretieren wir das Spiel so, dass x=y die Abbruchbedingung der Wiederholung und damit das Ende des Spiels darstellt.

Die Berechnung von x und y stellt offensichtlich die Berechnung des ggT von m und n dar. Wie zeige ich, dass ober genannter Algorithmus immer endet? Reicht es zu sagen, dass es die ggT Funktion ist und diese immer definiert ist? Was stellt dann u und v dar?

Gruß,
Marko.
18.01.2007, 20:11 Abakus Auf diesen Beitrag antworten »
RE: GGT Beweis der Finitheit
Zitat:
Original von Moeki
Wie zeige ich, dass ober genannter Algorithmus immer endet? Reicht es zu sagen, dass es die ggT Funktion ist und diese immer definiert ist? Was stellt dann u und v dar?


Die Frage gehört eher ins Gebiet "Programmverifikation" und damit in die Informatik (d.h. du könntest die Frage im Informatik-Board stellen).

Es reicht nicht, sich nur auf die ggT-Funktion zurück zu ziehen. Fraglich ist, was ihr hier für Verifikations-Methoden zur Verfügung gestellt bekommen habt.

Für einen Überblick, siehe hier.

Grüße Abakus smile
19.01.2007, 12:57 Marko Auf diesen Beitrag antworten »

Eine Frage noch:

Die beiden Regeln/Fälle x:=x-y; und y:=y-x führen ja immer auf x=y. Das ist ein bekanntes math. Gesetz, ich weiß nur nicht mehr welches.

Welches denn?
19.01.2007, 21:01 Frooke Auf diesen Beitrag antworten »

Nicht speziell...

x=x-y führt zu y=0

Oder meinst Du hier eine Zuweisung?

Als Nebeninfo: In der Informatik ist etwas wie i=i+1 für Iterationen geeignet, in der Mathematik ist das eine schlicht falsche Aussage...

Oder missverstehe ich, wass deine Doppelpunkte meinen?

LG
19.01.2007, 22:41 Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Marko
Die beiden Regeln/Fälle x:=x-y; und y:=y-x führen ja immer auf x=y. Das ist ein bekanntes math. Gesetz, ich weiß nur nicht mehr welches.


Wenn m oder n am Anfang Null sind (und das ist möglich wohl), wird der Algorithmus nicht terminieren.

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » GGT Beweis der Finitheit