Korrektheit eines Algorithmus beweisen |
| 29.01.2012, 18:04 | Auf diesen Beitrag antworten » |
| Kallinski1 | Korrektheit eines Algorithmus beweisen Meine Frage: Halli Hallo, ich soll in einer Aufgabe die Korrektheit von folgendem Algorithmus beiwesisen: Die Aufgabe genau: Sei X eine endliche Menge der Karidnalität n. Ein Wert x von X heißt Median von X, wenn weniger als n/2 Elemente von X kleiner als x und weniger als n/2 Elemente von X größer als x sind. Folgender Algorithmus dient der Bestimmung des Medians eines Arrays: Funktion Median (X) Eingabe: Array X= [X[0],...,X[n-1]] x <- minus unendlich y <- 0 SOLANGE y < n/2 ---m <- unendlich ---FÜR i=0,...,n-1 TUE ------WENN X[i] > x DANN -----------WENN x[i] = m DANN --------------c <- c+1 -----------WENN X[i] < m DANN --------------m <- X[i] --------------c <- 1 ---x <- m ---y <- y+c ZURÜCK x Ja soweit der Algorithmus. Ich würde mich sehr freuen wenn mir jemand beistehen könnte Augenzwinkern Dies ist leider der letzte Aufgabenzettel den ich abgeben muss und somit ist mein bestehen des Moduls davon abhängig unglücklich Meine Ideen: Ich habe mir bereits artikel über Quicksort, Medians, etc. durchgelgesen und ich verstehe auch ungefähr wie der Algorithmus funktioniert aber ich habe keine Ahnung wie ich beweisen soll, dass er auch richtig funktioniert. Bin für jede Hilfe dankbar. |
|
|
|
| 29.01.2012, 22:50 | Auf diesen Beitrag antworten » |
| Karlito | Hallo, was ich dir als Tipp geben kann ist, das ganze mit dem Hoare Kalkül zu beweisen. Ein anderes verfahren fällt mir gerade nicht ein. Ich bin aber leider, was das Hoare-Kalkül angeht auch nicht besonders fit, so dass ich dir da nicht weiter unter die Arme greifen kann. VG, Karlito |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
