Korrektheitsbeweis Pseudocode Bubblesort?
Also ich hab keine keine Ahnung wie ich dran gehen soll. Ich weis nur ich sollte am besten von innen nach außen anfangen und die Schleifeninvariante benutzen (Ich weis nur grob was das ist, aber ich weis nicht wie ich die Schleifeninvariante erkenne) ? Außerdem muss ich eine Quantifizierung aufstellen für eine Aussage ... aber ich hab auch keine ahnung wie das geht. Und ich hab auch noch gehört bei der Schleifeninvariante muss man Induktionsschritte benutzen ?
Also ich glaub man merkt bin richtig lost.
2 Antworten
Ja, das ist ein richtig dummes Thema :D
Wenn ich mich recht erinnere (ist echt lange her), ist die Schleifeninvariante etwas, was in jedem Ausführungsschritt der Schleife korrekt ist. Induktion kannst du halt nutzen um zu beweisen, dass das stimmt. Finden tust du die einfach durch drauf schauen und überlegen. Hilft immer, so ein paar Beispiele hinzuschreiben und nach Gemeinsamkeiten zu suchen. Kann sein, dass es da auch irgendeinen Algorithmus gibt, aber wenn es den gibt, dann war der irgendwie übermäßig kompliziert.
Ja die Schleifenvariante ist halt nh Aussage die vor während und nach der schleife immernoch stimmt. Aber dunno, wie ich daran gehen soll. Wo soll ich hinschauen auf was soll ich achten... aua....
mach ne schleifen in variante dass sollte als beweis gelten
puh. info studium info studium wo warst du nochmal in meinem gehirn.
spaß bei seite,
nimm beispielsweise n heap oder n array den du dann mittels schleifeninvariante beweist.
würd das zu sortierende array nehmen. welches mit jedem duchlauf der schleife sich ändert und eine sortierung durchführt für die erste for schleife und in der 2ten dann den beweis dass für das jeweilige element x entsprechend voll sortiert ist am ende der invariante beweist du dann nur noch dass alles korrekt ist.
oder machs mittels vollständiger induktion
Ehm ich hab literally nur dis
BubbleSort(Array b)
for v ← length(b) downto 2 do
for i ←1 to v-1 do
if b[i] > b[i+1] then swap(b, i, i+1)
return A
Ich weis nur Schleifeninvariante mit der inneren Schleife anfangen, und dann überlegen was passt. Aber ich komm ja nicht mal auf die Schleifeninvariante (die einrückungen gehen hier nicht sorry)
Einrückungen gehen:
BubbleSort(Array b)
for v ← length(b) downto 2 do
for i ←1 to v-1 do
if b[i] > b[i+1] then swap(b, i, i+1)
return A
und wie geht das