die korrektheit eines algorithmus beweisen

golden_jubilee

es geht um einen algorithmus für die umwandlung von dezimalzahlen in eine beliebiges anderes system z.B. zur basis 2
10:2 = 5 r = 0
5 :2 = 2 r = 1
2 :2 = 1 r = 0
1 :2 = 0 r = 1

10(2) = 1010
naja, soweit ist das auch kein problem

es soll nun gezeigt werden, dass der algo eine dezimalzahl in ein system mit der basis b konvertiert

erstmal hab ich in den knuth geguckt (volume 1, seite 14...) und zur Induktion sagt er
"However, that approach doesnt`t work out so easily..."

und jetzt suche ich einen ansatz

edit:
ich versteh nicht ob man nur zeigen muss, dass der algo für basis 2 funktioniert
dann sagen, klappt auch mit basis n und dann ahc mit basis n+1?

Borschtsch

Kannst du dich auf die Basisumrechnung beziehen? War so mein erster Gedanke.

Gruß

Prof84

Hi golden_jubilee,

so wie ich die Aufgabenstellung interpretiere handelt es sich hier um eine 'Blackbox'-Prüfung. Somit ist die Prüfung eines Algos nur durch Tests durchzuführen und keinem mathematischen Beweis:

Zu beurteilendes Konzept: dein Algo
Wahrnehmungskonzept: Input =>Basis, Dezimalwert; Output => Basiswert;
Solution Constraints: Basis Element aus N (warum eigentlich?); Dezimalstellen und Basisstellen hinter dem Komma werden nicht zugelassen (ebenfalls warum?);
Prüfungskonzept: Dezimalwert = zb^n + ... + yb^3 + xb^2 + wb mit basiswert {z...yxw} mit n Ziffern ist (wahr/falsch)
Prüfungsergebnis: Map [(Basis, Dezimalwert) => Basiswert, Ergebnis]
Beurteilungskonzept: Ergebnisse von Map sind alle wahr oder nicht.

In der Praxis wird nur ein begrenztes Testfeld mit Regessionstests möglich sein.

.filmor

Hmm? Natürlich ist das beweisbar. Du musst zeigen, dass

sum_(i in N) d_i * 10^i = sum_(i in N) b_i * 2^i

gilt, wobei d_i die Folge der dezimalen Ziffern und b_i die Folge der binären Ziffern sei (natürlich beides 0 für fast alle i, sonst geht's kaputt).
Das wäre jetzt mein Ansatz.

Prof84

.filmor schrieb:

Hmm? Natürlich ist das beweisbar. Du musst zeigen, dass
sum_(i in N) d_i * 10^i = sum_(i in N) b_i * 2^i
gilt, wobei d_i die Folge der dezimalen Ziffern und b_i die Folge der binären Ziffern sei (natürlich beides 0 für fast alle i, sonst geht's kaputt).
Das wäre jetzt mein Ansatz.

Hmm! Und wie willst Du das praktisch beweisen? Für alle b, Dezimalzahlen und Basiswert Element aus N. Mit der Blackbox für Algoritmen!

Christoph

Prof84 schrieb:

so wie ich die Aufgabenstellung interpretiere handelt es sich hier um eine 'Blackbox'-Prüfung. Somit ist die Prüfung eines Algos nur durch Tests durchzuführen und keinem mathematischen Beweis:

Das ist falsch, sorry. Wir sind hier immer noch im Mathematik-Forum; auch wenn man statistische Tests mathematisch bewerten kann, verträgt sich das in keinster Weise mit der Aufgabenstellung "Korrektheit des Algorithmus beweisen".

.filmor hat gut beschrieben, was zu zeigen ist.

Im Prinzip muss man dafür vor allem beweisen, dass die Basendarstellung einer Zahl funktioniert, wobei die einzelnen Ziffern aus dem Algorithmus kommen. Am Beispiel der Basis 2 wäre das:

Für alle natürlichen Zahlen x, n gilt:
Falls 2^(n+1) > x, dann ist x = sum(i=0..n, a_i * 2^i) mit

a_i = { 0 falls (x mod 2^(i+1)) < 2^i
      { 1 sonst

Das lässt sich gut mit vollständiger Induktion über n beweisen:

Sei n=0: Dann ist 2^(0+1) > x, also ist x entweder 0 oder 1. Die Fälle kann man beide durchrechnen, um zu sehen, dass stets x = a_0 ist.

Angenommen die Behauptung gilt für alle m mit 0 <= m < n. Zu zeigen ist, dass die Behauptung dann auch für n gilt. Wir bekommen 2^(n+1) > x und unterscheiden zwei Fälle:
1. Fall: x < 2^n. Dieser Fall folgt aus der Induktionsannahme und der Tatsache, dass (x mod 2^(n+1)) = x < 2^n ist und damit nach Definition a_n = 0.
2. Fall: x >= 2^n. Wir haben also 2^(n+1) > x >= 2^n. Dann ist a_n = 1, weil (x mod 2^(n+1)) = x ist und x nicht kleiner als 2^n ist. Nach Induktionsannahme haben wir außerdem x - 2^n = sum(i=0..(n-1), a_i * 2^i). Zusammen ergibt das

x = sum(i=0..(n-1), a_i * 2^i) + 2^n
  = sum(i=0..(n-1), a_i * 2^i) + a_n * 2^n
  = sum(i=0..n, a_i * 2^i)

Damit ist Behauptung bewiesen. Für andere Basen funktioniert der Beweis sehr ähnlich, man muss dann nur leider mehr als 2 Fälle unterscheiden.

Die Schwierigkeit in der ganzen Sache liegt zum einen darin, die Aussage korrekt hinzuschreiben und zum anderen, dass man zwei allquantifizierte Variablen hat (n und x), aber nur über eine der beiden die Induktion macht und die andere in jedem Schritt des Induktionsbeweises allquantifiziert bleibt.

Christoph

Christoph schrieb:

Prof84 schrieb:

so wie ich die Aufgabenstellung interpretiere handelt es sich hier um eine 'Blackbox'-Prüfung. Somit ist die Prüfung eines Algos nur durch Tests durchzuführen und keinem mathematischen Beweis:

Das ist falsch, sorry. Wir sind hier immer noch im Mathematik-Forum; auch wenn man statistische Tests mathematisch bewerten kann, verträgt sich das in keinster Weise mit der Aufgabenstellung "Korrektheit des Algorithmus beweisen".

Nur um klarzustellen, was ich meine: In richtigen Anwendungen sind Korrektheitsbeweise sehr schwer und sehr unüblich, das ist mir bekannt. Deswegen hättest du meistens wohl recht mit deiner Vermutung. Da die Frage aber im Mathe-Forum gestellt wurde und der OP sogar das Werk von D. Knuth erwähnt hat, finde ich es äußerst schwer, den Bogen zu finden zu "Wir testen ein paar Eingabedaten".

Prof84

Christoph schrieb:

... Das ist falsch, sorry. Wir sind hier immer noch im Mathematik-Forum; auch wenn man statistische Tests mathematisch bewerten kann, verträgt sich das in keinster Weise mit der Aufgabenstellung "Korrektheit des Algorithmus beweisen".

Ach so, das ist hier das "Märchenforum"! -
"Wenn Naturgesetze A und B nicht gelten, aber Naturgesetz C weiter gilt, was hätten wir dann?" - Ist aber nirgendwo in der Aufgabe beschrieben.

Christoph

Prof84 schrieb:

Christoph schrieb:

... Das ist falsch, sorry. Wir sind hier immer noch im Mathematik-Forum; auch wenn man statistische Tests mathematisch bewerten kann, verträgt sich das in keinster Weise mit der Aufgabenstellung "Korrektheit des Algorithmus beweisen".

Ach so, das ist hier das "Märchenforum"! -
"Wenn Naturgesetze A und B nicht gelten, aber Naturgesetz C weiter gilt, was hätten wir dann?" - Ist aber nirgendwo in der Aufgabe beschrieben.

"die korrektheit eines algorithmus beweisen" ist der Titel des Originalpostings.
"Korrektheit" ist ein allgemein anerkannter Fachbegriff, da gibt es wenig zu interpretieren, höchstens etwas zum Nachschlagen.

Außerdem weiß ich nicht, was du mit "Märchenforum" meinst. Glaubst du, es gibt natürliche Zahlen in der Natur? Natürlich beschäftigt sich die Mathematik mit Dingen, die es in der Natur nicht gibt. Aber das gilt eben für die ganze Mathematik und nicht nur für bestimmte Teilgebiete, deswegen verstehe ich deine Äußerung nicht.

Jester

Ich denke auch, dass es um einen Korrektheitsbeweis geht. Schließlich ist auch von einem Algorithmus die Rede und nicht von einer Implementierung.

Meist wird die Korrektheit von Algorithmen bewiesen, deren Implementierung hingegen gestestet. Korrektheit von Implementierungen zu beweisen ist leider meistens schwierig und das Testen von Algorithmen relativ sinnfrei, weil man eben doch nur wieder eine bestimmte Implementierung testen kann.

golden_jubilee

so eben hat mich die nachricht erreicht, dass doch nur lauwarm gekocht werden soll...
werde den post von Christoph trotzdem nutzen um dazu was zu schreiben

danke für eure mühe