Theorietestat #2a: CountOddElements (5.2)

[SophiaLi1]

Hallo,

bei dem Abschnitt zu CountOddElements (5.2) kommen meiner Meinung nach die Indizes etwas durcheinander. In der Invariante steht, dass in der h-ten Iteration i=x+h-1 ist. Diese Definition sollte man auch beibehalten. Wenn also h bezogen auf den aktuellen Iterationsschritt ist, sollte sich x auch auf den aktuellen Iterationsschritt beziehen.

Jetzt kommt das Problematische:
In der Induktionsvoraussetzung, in der man den Iterationsschritt h-1 betrachtet, steht dann

Code: Alles auswählen

A[x]..A[i]

mit i=x+h -2. Hier wird also das i aus dem vorherigen Iterationsschritt zugrunde gelegt. Hier sollte aber zu einem besseren Verständnis eigentlich

Code: Alles auswählen

A[x]...A[i-1]

mit i=x+h-1 stehen. Im h'=h-1-ten Iterationsschritt ist nämlich auch eigentlich i'=i-1.
Ähnlich steht dann im Induktionsschritt am Ende

Code: Alles auswählen

A[x]..A[i+1]

mit i=x+h-2, was der Invariante entspräche. Das ist aber nicht der Fall, denn in der Invariante steht

Code: Alles auswählen

A[x]...A[i]

mit i = x+h-1. Wir sind im Induktionsschritt in der h-ten Iteration. Der aktuelle Index i=x+h-1 und eben nicht i=x+h-2. Was i ist, ist durch den Quellcode definiert. Setzt man es dann ein, kommt der richtige Index heraus, aber die Definition von i ist eben nicht einheitlich, was sie aber sein sollte.

Übernimmt man aber die Definition aus der Invariante von i mit i=x+h-1 und schreibt

Code: Alles auswählen

A[x]..A[i]

im Induktionsschritt, stimmt es wieder und es ist einheitlich. Der Wechsel von der Definition zwischendrin macht es sehr verwirrend.

Ich hoffe, man versteht mein Problem.

[invariant]

Hallo,

da i als Teil der Invariante formuliert ist sollte das auch so durchgezogen werden.
Ich denke das Problem liegt im Induktionsschritt wo es zu Verwirrungen kommen kann.

Nach h-1 Iterationen gilt die Invariante, also enthält counter die Anzahl
der ungeraden Elemente in A[x]...A und i = x+h-2.

In der h-ten Iteration wird das Element A[i + 1] überprüft und counter erhöht, falls das Element ungerade ist.
Damit gilt, dass counter die Anzahl der ungeraden Elemente in A[x]...A[i + 1] enthält, was der Invariante entspricht.

Das könnte man wohl ein bisschen schöner formulieren.

Nach h-1 Iterationen gilt die Invariante, also enthält counter die Anzahl der ungeraden Elemente
in A[x]...A und i = x+h-2. Counter enthält also die Anzahl der ungeraden Elemente in A[x]...A[x+h-2].

In der h-ten Iteration wird i um eins erhöht es gilt also i = x+h -1. Nun wird das Element A = A[x+h-1]
überprüft und counter erhöht, falls das Element ungerade ist.
Damit gilt, dass counter die Anzahl der ungeraden Elemente in A[x]...A mit i = x + h -1 enthält,
was der Invariante entspricht.

Hilft diese Abwandlung beim besseren Verständnis?
Bzw. wäre dadurch das Problem gelöst?

Gruß

[SophiaLi1]

Hi,

verstanden habe ich es schon vorher. Der Induktionsschritt ist jetzt auch besser, nur mit der Induktionsvoraussetzung kann ich mich mathematisch noch nicht anfreunden.

Mein Problem ist nur: Warum definiere ich überhaupt ein i, wenn die Definition nicht konstant bleibt bzw. mit dem Schleifenzähler i aus dem Quellcode nicht übereinstimmt? Also entweder sollte man das i in der Induktionsvoraussetzung und im Induktionsschritt ganz weglassen oder die einheitliche Definition von i = x + h -1 wählen. Ich glaube, das Problem hierbei liegt darin, dass die Invariante für den Zustand nach einer Iteration formuliert wird. h und i werden hier gleichzeitig erhöht. Zu keinem Zeitpunkt ist i =x+h-2. Wenn die Bezeichnung von h sich auf den aktuellen Iterationsschritt bezieht (und man den vorherigen Iterationsschritt mit h'=h-1 bezeichnet), muss auch die Bezeichnung von i sich auf den aktuellen Iterationsschritt beziehen (und damit i' = i-1 und nicht nur i).

Verbesserungsvorschlag:
Invariante: Nach h>=0 Iterationen enthält counter die Anzahl der ungeraden Elemente in

Code: Alles auswählen

A[x]..A[i]

mit i=x+h-1.

Induktionsvoraussetzung: Nach h-1 (=h') Iterationen gilt die Invariante, also enthält counter die Anzahl der ungeraden Elemente in A[x]..A[x+h-2] mit x+h-2 = i-1 ( = i').

Induktionsschritt: Nach der Induktionsvoraussetzung gilt die Invariante, also enthält counter die Anzahl der ungeraden Elemente in A[x]..A[x+h-2]. In der h-ten Iteration wird das Element

Code: Alles auswählen

A[i] = A[x+h-1]

überprüft und counter erhöht, falls das Element ungerade ist. Damit gilt, dass counter die Anzahl der ungeraden Elemente in

Code: Alles auswählen

A[x]..A[i]

mit i =x+h-1 enthält, was der Invariante entspricht.

[invariant]

Hallo,

ich denke ich verstehe das Problem jetzt besser.

h = x + i -2 ? Das ergibt gerade für mich wenig Sinn es gilt i = x + h - 1 also wäre h = i - x + 1.

Der Punkt ist, dass in der Induktionsvoraussetzung der Iterationszähler nicht den Wert h hat, sondern (h-1).
Setzen wir also (h-1) - Ihr h' - in die Invariante ein für den Iterationszähler ergibt sich folgendes:

Code: Alles auswählen

Nach h-1 Iterationen enthält counter die Anzahl der ungeraden Elemente in
A[x]...A[i] und i = x + (h -1) - 1 = x + h - 2.

das x + h - 2 = i - 1 gelten soll ist an dieser Stelle also falsch. Sie beziehen sich dann auf das i aus der Invariante, die bei einem Iterationszählerwert von h gültig wäre. Wir wollen uns in der Induktionsvoraussetzung allerdings auf den Iterationszähler mit Wert (h-1) beziehen.

Da wir in der Invariante den Fall betrachten, dass der Iterationszähler den Wert h hat muss nach diesem Schritt gelten:

Code: Alles auswählen

Nach h Iterationen enthält counter die Anzahl der ungeraden Elemente in
A[x]...A[i] und i = x + h - 1

i ist in dieser Invariante nicht notwendig, sondern sollte nur die Notation für Sie angenehmer machen, dass das zu Problemen führt war dabei nicht beabsichtigt.
Wenn es Ihnen beim Verständnis hilft können Sie die Invariante auch ohne dieses i formulieren.

Code: Alles auswählen

Nach h >= 0 Iterationen enthält counter die Anzahl der ungeraden Elemente in
A[x]...A[x + h -1]

Ich hoffe das hat Ihnen weitergeholfen.

Gruß

[SophiaLi1]

h = x + i -2 ?

Sorry, hatte mich oben vertippt. Hab es korrigiert. Mein Punkt war: Wenn wir uns in der Induktionsvoraussetzung auf den Iterationszähler mit Wert (h-1) beziehen, müssen wir uns auch auf den Schleifenzähler (i-1) beziehen und nicht auf i. Ich denke, ich werde die Induktionsvoraussetzung am besten ohne i formulieren (: