THeorie Testat #2 checkerNotZero

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
ceerwyn
Neuling
Neuling
Beiträge: 2
Registriert: 10. Mai 2017 10:39

THeorie Testat #2 checkerNotZero

Beitrag von ceerwyn » 10. Mai 2017 11:04

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! :)

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: THeorie Testat #2 checkerNotZero

Beitrag von invariant » 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.

Hoffe das hilft weiter.

Gruß

unglee
Neuling
Neuling
Beiträge: 3
Registriert: 2. Mai 2017 12:21

Re: THeorie Testat #2 checkerNotZero

Beitrag von unglee » 11. Mai 2017 10:47

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?

ceerwyn
Neuling
Neuling
Beiträge: 2
Registriert: 10. Mai 2017 10:39

Re: THeorie Testat #2 checkerNotZero

Beitrag von ceerwyn » 11. Mai 2017 12:48

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üß

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: THeorie Testat #2 checkerNotZero

Beitrag von invariant » 11. Mai 2017 14:15

Oh Entschuldigung mein Fehler.

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


Gruß

mdk
Mausschubser
Mausschubser
Beiträge: 43
Registriert: 18. Apr 2014 10:33

Re: THeorie Testat #2 checkerNotZero

Beitrag von mdk » 18. Mai 2017 14:41

Weiterhin müsste auf Seite 7 bei Induktionsvoraussetzung stehen: "... sind gleich 0." und nicht "... sind ungleich 0."

Oder übersehe ich hier was?

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: THeorie Testat #2 checkerNotZero

Beitrag von invariant » 18. Mai 2017 21:34

Das ist korrekt, der Fehler hat sich der Stelle fortgesetzt.

Gruß

Robin Ferrari
Erstie
Erstie
Beiträge: 15
Registriert: 15. Apr 2016 10:16

Re: THeorie Testat #2 checkerNotZero

Beitrag von Robin Ferrari » 21. Mai 2017 09:44

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

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: THeorie Testat #2 checkerNotZero

Beitrag von invariant » 23. Mai 2017 13:02

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ß

Robin Ferrari
Erstie
Erstie
Beiträge: 15
Registriert: 15. Apr 2016 10:16

Re: THeorie Testat #2 checkerNotZero

Beitrag von Robin Ferrari » 23. Mai 2017 13:50

okay danke

Antworten

Zurück zu „AuD: Theoretische Aufgaben“