T2: Beispiel 2

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!
Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

T2: Beispiel 2

Beitrag von Hallo » 3. Sep 2016 19:16

Hi, ich möchte hier mal mein Lösungsvorschlag zum 2. Beispiel des Theorie 2 vorschlagen:


Input: Ein Aufsteigensortierter Array a und ein zu suchendes Element int x.

Wohldefiniertheit: Es gibt keine Instruktionen, die auf Attribute oder Methoden == null verweisen oder zugreifen. Es gibt keine Divisionen durch 0.

Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.

Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.

Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.

Induktionsanfang: Vor dem 1. Reksursionschritt liegt der gesuchte Element (x) im Intervall i bis array.length-1 (j), ein Parameter m wird als Pivotposition auf Mitte des Arrays initialisiert = (i+j)/2.

Induktionsschritt: Entweder x ist größer bzw. kleiner als den Wert des Pivotposition und es wird die erste bzw. die zweite Hälfte des Arrays vernachlässigt, bzw. i wird gleich m+1 oder j wird gleich m-1 gesetzt.

Korrektheit: Dank der Variante, dass der Intervall sich ständig halbiert, erreicht der Algorithmus einer der beiden Abbruchbedingung und der Korrekte Ergebnis wird zurückgeliefert.

Sonne34
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 3. Mai 2015 18:10

Re: T2: Beispiel 2

Beitrag von Sonne34 » 15. Sep 2016 08:51

Vielen Dank für die Bereitstellung deiner Lösung. Ich habe sie mal mit meinen verglichen.
Anbei nun meine zusätzlichen Ideen, über Feedback würde ich mich freuen :wink:
Hallo hat geschrieben:
Input: Ein Aufsteigensortierter Array a und ein zu suchendes Element int x.
Ich habe hier: Ein Array a mit ganzen Zahlen, dass aufsteigend sortiert ist, wobei a[0]+...+a[a.length-1] <= Integer.MAX_VALUE. Zudem eine ganze Zahl x, welche das gesuchte Element in a darstellt.
Hallo hat geschrieben: Wohldefiniertheit: Es gibt keine Instruktionen, die auf Attribute oder Methoden == null verweisen oder zugreifen. Es gibt keine Divisionen durch 0.
Es existieren keine Instruktionen die auf Attribute oder Methoden von null zugreifen und auch keine Division durch 0. Ein Überlauf kann aufgrund der Einschränkung des Inputs nicht passieren.
Hallo hat geschrieben: Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.
Hier habe ich: Aufgrund der Variante, wird die Abbruchbedingung i>j nach endlich vielen Schritten erreicht. Ich schätze mal das meine Aussage zu knapp ist oder? :roll:

Hallo hat geschrieben: Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.
Auch hier bin ich mir unsicher mit meiner Formulierung : m wird in jedem Aufruf echt kleiner, da entweder i größer wird, oder j kleiner wird.
Hallo hat geschrieben: Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.
Nach i>=0 Iterationen wurden die ersten i - Stellen des Arrays nach dem gesuchten Wert x durchsucht.
Kann es sein, dass du hier eig das Beispiel 3 gepostet hast? Schließlich liegt bei Beispiel zwei die iterative Version vor und nicht die rekursive?
Hallo hat geschrieben: Induktionsanfang: Vor dem 1. Reksursionschritt liegt der gesuchte Element (x) im Intervall i bis array.length-1 (j), ein Parameter m wird als Pivotposition auf Mitte des Arrays initialisiert = (i+j)/2.
Vor der Schleife, also nach 0 Iterationen wurden keine Stellen des Arrays durchsucht.

Liebe Grüße

yokop
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 13. Apr 2016 12:49

Re: T2: Beispiel 2

Beitrag von yokop » 15. Sep 2016 09:58

Hallo hat geschrieben: Terminierung: Entweder das gesuchte Element wurde gefunden, oder die variablen i (Anfangsposition des Intervalls) und j (Intervallende) stehen auf die gleiche Position im Array.
Wenn i == j dann wird die Schleife noch ausgeführt, da die Bedingung i <= j ist. Passender ist hier wohl i > j als Abbruchbedingung.
Hallo hat geschrieben: Variante: Der Intervall indem das Element gesucht wird, wird ständig halbiert.
Kann man wahrscheinlich so stehen lassen. In jeder Iteration wird entweder i = m+1 oder j = m-1 gesetzt, wobei m = (i+j)/2. Das heisst, dass sich i und j in jedem Schritt echt aufeinander zu bewegen.
Hallo hat geschrieben: Invariante(Induktionshypthese) Vor und nach jedem Rekursionsschritt liegt der gesuchte Element,falls es im Array vorhanden ist zwischen dem Intervall i bis j.
Zwischen dem Intervall i bis j ? Ich würde hier schreiben, im Intervall [i,j].
Hallo hat geschrieben: Induktionsanfang: Vor dem 1. Reksursionschritt liegt der gesuchte Element (x) im Intervall i bis array.length-1 (j), ein Parameter m wird als Pivotposition auf Mitte des Arrays initialisiert = (i+j)/2.
Es handelt sich nicht um eine Rekursion. Sonst passt es, jedoch das mit dem Parameter m ist nicht wirklich nötig. Vielleicht könnte man noch erwähnen, dass es falls vorhanden in dem Intervall ist.
Hallo hat geschrieben: Induktionsschritt: Entweder x ist größer bzw. kleiner als den Wert des Pivotposition und es wird die erste bzw. die zweite Hälfte des Arrays vernachlässigt, bzw. i wird gleich m+1 oder j wird gleich m-1 gesetzt.
Hier fehlt wieso folgt, dass das Element dann in dem neuen Intervall seien muss. Hier habe ich folgendes geschrieben:
Nach Induktionsvoraussetzung befindet sich x, falls vorhanden in a..a[j]. Falls nun a[m] == x, mit m = (i+j)/2, dann ist das Element gefunden und die Position m wird zurückgegeben. Sei nun a[m] != x, dann muss das Element also in dem restlichen Bereich zu finden sein (falls vorhanden..). Je nachdem ob also a[m] < x oder a[m] > x, befindet sich x in a[m+1=i]...a[j] bzw. a..a[m-1=j] aufgrund der aufsteigenden Sortierung des Array. Also ist das Element auch nach einer Iteration noch im von i und j begrenzten Bereich.

Max_S
Erstie
Erstie
Beiträge: 14
Registriert: 16. Apr 2015 17:09

Re: T2: Beispiel 2

Beitrag von Max_S » 16. Sep 2016 16:00

Die offizielle Lösung findet ihr übrigens in den Tutorien... (ich glaub das war in Tutorium 2) :D

Antworten

Zurück zu „AuD: Theoretische Aufgaben“