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

Informatiker Board » Themengebiete » Praktische Informatik » Schleifeninvariante » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 6 Beiträge
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
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
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).
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])
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
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??