Seite 1 von 1

THeorie Testat #2 checkerNotZero

Verfasst: 10. Mai 2017 11:04
von ceerwyn
Hallo,

bei der Invariant im checkerNotZero steht "Invariante: Nach h >= 0 Iterationen gilt: Die Listenelemente an den Positionen 0...h - 1 sind
ungleich 0."
Aber eine der Abbruchbedingungen ist wenn current.key != 0 ist.
Und bei der Induktionsschritt steht auch: "Induktionsschritt: Nach h >= 1 Iterationen gilt nach Induktionsvoraussetzung die Invariante,
also in den Elementen list[0]...list[h - 2] wurde kein Element ungleich 0 gefunden."

Wie so stehen an den Positionen 0...h - 1 Elemente, die ungleich 0 sind?

Vielen Dank in Voraus! :)

Re: THeorie Testat #2 checkerNotZero

Verfasst: 10. Mai 2017 11:21
von invariant
Wenn in den Elementen 0...h-1 schon ein Element ungleich 0 vorgekommen wäre, wäre der Algorithmus schon terminiert, ergo wäre dieser Iterationsschritt nicht vorhanden. Wenn wir also in der h-ten Iteration sind können wir davon ausgehen, dass der Algorithmus in den Iterationen 0...h-1 nicht terminiert ist, also keine Elemente ungleich 0 vorgekommen sind.

Hoffe das hilft weiter.

Gruß

Re: THeorie Testat #2 checkerNotZero

Verfasst: 11. Mai 2017 10:47
von unglee
invariant hat geschrieben:Wenn in den Elementen 0...h-1 schon ein Element ungleich 0 vorgekommen wäre, wäre der Algorithmus schon terminiert, ergo wäre dieser Iterationsschritt nicht vorhanden. Wenn wir also in der h-ten Iteration sind können wir davon ausgehen, dass der Algorithmus in den Iterationen 0...h-1 nicht terminiert ist, also keine Elemente ungleich 0 vorgekommen sind.

Hoffe das hilft weiter.

Gruß
Hallo,
glaube das Problem liegt eher hier: "Invariante: Nach h >= 0 Iterationen gilt: Die Listenelemente an den Positionen 0...h - 1 sind
ungleich 0." Das ist jedoch genau die Abbruchbedingung.
D.h. eigtl. müsste es ja, wie oben beschrieben, so dort stehen: "Invariante: Nach h >= 0 Iterationen gilt: Die Listenelemente an den Positionen 0...h - 1 sind NICHT ungleich 0. bzw. (noch) gleich 0" oder nicht?

Re: THeorie Testat #2 checkerNotZero

Verfasst: 11. Mai 2017 12:48
von ceerwyn
Danke für die schnelle Antworten!

Ja, die Frage war genau wegen der Formulierung "Invariante: Nach h >= 0 Iterationen gilt: Die Listenelemente an den Positionen 0...h - 1 sind
ungleich 0.
"

Ich bin der gleichen Meinung dass bei der Invariante "Die Listenelemente an den Positionen 0...h - 1 sind NICHT ungleich 0." stehen soll.
Oder "An den Positionen 0...h - 1 wurde kein Element ungleich 0 gefunden."

Wenn der Algorithmus terminiert wenn ein Element ungleich null gefunden wird, dann sollen keine Elemente ungleich 0 an den Positionen 0...h - 1 stehen. Oder?


Grüß

Re: THeorie Testat #2 checkerNotZero

Verfasst: 11. Mai 2017 14:15
von invariant
Oh Entschuldigung mein Fehler.

Das stimmt natürlich, da ist das Nicht verloren gegangen. Wird ergänzt.


Gruß

Re: THeorie Testat #2 checkerNotZero

Verfasst: 18. Mai 2017 14:41
von mdk
Weiterhin müsste auf Seite 7 bei Induktionsvoraussetzung stehen: "... sind gleich 0." und nicht "... sind ungleich 0."

Oder übersehe ich hier was?

Re: THeorie Testat #2 checkerNotZero

Verfasst: 18. Mai 2017 21:34
von invariant
Das ist korrekt, der Fehler hat sich der Stelle fortgesetzt.

Gruß

Re: THeorie Testat #2 checkerNotZero

Verfasst: 21. Mai 2017 09:44
von Robin Ferrari
Hi,

Also dass da NICHT ungleich 0 stehen sollte, wurde ja schon geklärt. Was mir aber nicht ganz verständlich ist, ist dies:
invariant hat geschrieben:
10. Mai 2017 11:21
Wenn in den Elementen 0...h-1 schon ein Element ungleich 0 vorgekommen wäre, wäre der Algorithmus schon terminiert, ergo wäre dieser Iterationsschritt nicht vorhanden. Wenn wir also in der h-ten Iteration sind können wir davon ausgehen, dass der Algorithmus in den Iterationen 0...h-1 nicht terminiert ist, also keine Elemente ungleich 0 vorgekommen sind.
Mein Problem damit: Die Invariante muss doch nach der Terminierung (dem letzten Iterationsschritt) korrekt sein? so verstehe ich zumindest das AlgoWiki:
The invariant of a loop consists of all assertions that are true immediately before the first iteration, immediately after the last iteration, and between two iterations. These assertions are called the invariant assertions of this loop.
Da wir bei Position 0 anfangen würden wir doch in h = 3 Position 2 der Liste anschauen. Nun wäre also dort ein key != 0. Also terminieren wir mit true. Die Invariante würde nun aber sagen, dass an Position 0...2 von head kein key != 0 ist. Was ja falsch ist.

Muss also die Invariante nach Terminierung gar nicht mehr stimmen oder wird der Schritt in dem Terminiert wird nicht als Iteration gezählt?

Vielen Dank für eine Antwort

LG Robin

Re: THeorie Testat #2 checkerNotZero

Verfasst: 23. Mai 2017 13:02
von invariant
In dem Fall zeigen, dass der vorzeitige Abbruch dem geforderten Output entspricht - Invariante muss dann nicht mehr gelten.

Zum Vergleich algowiki:

https://wiki.algo.informatik.tu-darmsta ... list:_find

Gruß

Re: THeorie Testat #2 checkerNotZero

Verfasst: 23. Mai 2017 13:50
von Robin Ferrari
okay danke