Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Schleifeninvariante » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Schleifeninvariante
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Hellboy256
Grünschnabel


Dabei seit: 17.04.2010
Beiträge: 8

Schleifeninvariante Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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??
17.04.2010 22:07 Hellboy256 ist offline E-Mail an Hellboy256 senden Beiträge von Hellboy256 suchen Nehmen Sie Hellboy256 in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 324

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 15:49 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
Hellboy256
Grünschnabel


Dabei seit: 17.04.2010
Beiträge: 8

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 17:30 Hellboy256 ist offline E-Mail an Hellboy256 senden Beiträge von Hellboy256 suchen Nehmen Sie Hellboy256 in Ihre Freundesliste auf
ed209
Routinier


Dabei seit: 07.09.2006
Beiträge: 324

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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).
18.04.2010 21:52 ed209 ist offline E-Mail an ed209 senden Beiträge von ed209 suchen Nehmen Sie ed209 in Ihre Freundesliste auf
Hellboy256
Grünschnabel


Dabei seit: 17.04.2010
Beiträge: 8

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
19.04.2010 15:20 Hellboy256 ist offline E-Mail an Hellboy256 senden Beiträge von Hellboy256 suchen Nehmen Sie Hellboy256 in Ihre Freundesliste auf
OhneName
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
24.04.2010 17:46
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Schleifeninvariante