Schleifeninvariante

17.04.2010, 22:07

Hellboy256

Schleifeninvariante

Give a suitable loop invariant for the loop starting at line 6 and ending at line 12. Using the invariant it should be possible to conclude
a = min(a[0],...,a[a.length-1]
for non-empty arrays a, where i is the return value of the algorithm.

Also hier wär mal der code:

code:

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

1 static int minimum (int[] a) {
2 if (a. length > 0) {
3 int m = a [0];
4 int i = 0;
5 int j = 1;
6 while (j < a. length ) {
7 if (a[j] < m) {
8 i = j;
9 m = a[j];
10 }
11 j++;
12 }
13 return i;
14 } else {
15 throw new RuntimeException (" minimum not defined ");
16 }
17 }

Also ich hab mir den Artikel in Wikipedia über Schleifeninvarianten durchgelesen doch ich komm bei diesem Code einfach nicht drauf, hätt vlt einer von euch ne Ahnung wie das funktioniert??

18.04.2010, 15:49

Auf diesen Beitrag antworten »

ed209

1. Versuch mal den Code richtig zu formatieren, das hilft beim lesen.

2. Kannst du die Aufgabe mit eigenen Worten (und auf Deutsch) wiedergeben?
(ich behaupte da ist ein Fehler in der Aufgabenstellung)

3. Kannst du mit Worte beschreiben wie und warum der Algorithmus funktioniert, und was er tut?

4. Was ist dir unklar? Weisst du was du zum zeigen der Invariante alles brauchst?
Was sind gute Kandidaten für eine Invariante?

Gruß,
ED

18.04.2010, 17:30

Auf diesen Beitrag antworten »

Hellboy256

1. Formatiert ist der Code bei mir richtig ging nur im Forum nicht wirklich

2. Also soweit ich die Aufgabe verstehe soll man eine Schleifeninvariante von Zeile 6 bis 12 ermitteln, welche das Minimum des Arrays ermittelt

3. Der Algorithmus überprüft jedes Element des Arrays auf das Minimum wobei er das jeweilige nächste Element mit dem momentanen Minimum vergleicht und gegebenenfalls ein neues Minimum findet

4. Die Schleifeninvariante ist einfach die Eigenschaft einer Schleife, welche in jedem Schleifendurchlauf wahr ist

Könnte eine Schleifeninvariante vlt so sein:
m wäre mein Minimum und j mein derzeitiges Element

m = min(a[0]...a[j])

18.04.2010, 21:52

Auf diesen Beitrag antworten »

ed209

Zitat:

m = min(a[0]...a[j])

Sieht vielversprechend aus. Ich vermute du sollst jetzt auch noch beweisen daß die Invariante wahr ist.
Das bedeutet zu zeigen dass sie im ersten Durchlauf wahr ist und dass mit jedem Induktions schritt die Aussage wahr bleibt. (unter verwendung der Invariante aus dem vorherigen durchlauf).

19.04.2010, 15:20

Auf diesen Beitrag antworten »

Hellboy256

Ich hab da jetzt nur ein Problem mit dem Beweisen, ich glaub das sollte man über Induktion machen oder?
Also Induktionsanfang:

m=min(a[0]...a[0])
m=a[0]
...
m=min(a[0]...a[j])
m=min(a[0]...a[j+1])

nur hab ich keine Ahnung wie ich das Beweisen soll

24.04.2010, 17:46

Auf diesen Beitrag antworten »

OhneName

Vorsicht: Die Invariante lässt sich gut über Induktion beweisen und ist im Kern eigentlich die Induktionsvorraussetzung. Aber damit ist dann halt noch nicht der Algorithmus bewiesen. Da es aber hier nur um die Invariante geht, könnte das so aussehen:

Invariante: Nach dem i-ten Durchlauf enthält m das Minimum aus a[0]..a[i] (*Hier auf die Definition aufpassen, häufig geht man davon aus, dass bereits am Ende der Schleife die Zäglervariable um 1 erhöht wird. Gegebenenfalls muss dann hier a[0]...a[i-1] stehen!*)

Nun der Induktionsbeweis:

I.A. (Induktionsanfang) a[] enthält nur ein Element. Damit ist m = a[0], was offensichtlich das minimale Element ist..
I.V. die Invariante
I.S. (Induktionsschluss) Einfach gesagt, stellt man sich hier folgende Frage: Gilt die Invariante auch noch bei einem Array der Länge 0...i+1 ? Für ein Array der Länge 0...i haben wir das ja schon mit der Invariante vorrausgesetzt und sogar für ein Array der Länge 1 beweisen (siehe I.A.)
Also geht man hier so vor:

Nach der Invariante gilt, dass m bereits das minimale Element bis i enthält. Nun geht man den Code Zeile für Zeile durch, also so:
- Falls ein kleineres Element als m gefunden wird:
- so nimmt m dessen Wert an
- die Position von dieses Elementes wird sich gemerkt
- Falls kein kleines Element als m gefunden wird, so geschieht nichts, da m offensichtlich immernoch das minimale Element ist
zu guter letzt wird die Laufvariable um Eins erhöht

Damit ist offensichtlich nach i+1 Durchläufen m immernoch das minimale Element. Das wars Augenzwinkern

Neue Frage »

Antworten »

Schleifeninvariante

Verwandte Themen