 Korrektheit eines Algorithmus beweisen |
Kallinski1
unregistriert
 |
|
| 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 18:04 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
29.01.2012 22:50 |
|
|
|
