Fehler Übungsblatt Klausur A1

[Goma]

Hi,
habe die Lösung gesehen zur Aufgabe 1....
bin ich doof oder ist die Lösung der gegebenen Zahlensequenz falsch?
also seit wann ist die 1&2 größer als 4&7 und das nach der 5. Iteration, normal ist man nach der 5. iteration direkt mit dem ganzen sortieren fertig???

Bitte um Erklärung oder korrektur des Fehlers.

Danke

[pirate07]

Also wir sind noch nicht fertig....

Meinst du SelectionSort ? Wenn Ja

In jeder Iteration sucht man nach maximum und tauscht mit dem |S| -i+1 stelle

Nach 1st-Iteration hast du
13 4 7 1 13 12 12 20 0 2 21

i= 2
13 4 7 1 13 12 12 2 0 20 21

i= 3

0 4 7 1 13 12 12 2 13 20 21


usw

[Goma]

Aus welchem Grund muss GDI2 in diesem Fall egtl. eine Sonderrolle einnehmen und nach dem Größten suchen und nicht wie überall sonst nach dem kleinsten? -.-
um nur mal eine zu nennen http://de.wikipedia.org/wiki/Selectionsort da gibts noch zig andere uni seiten wo es mit kleinsten ist... muss sowas verwirrendes echt sein?

Edit:
und müsste die invariante nicht dann so lauten
Invariante: Nach i=6 Iterationen ist S[6] bis S[11] korrekt sortiert
da wir ja 2x die 12 haben und somit schon bis S[6] richtig sortiert haben und müsste i nicht 6 sein, sollten ja vor und nach der 6. iteration aufzeigen und fangen doch mit i=1 (also erste iteration) an?

[Stephoogle]

Streng genommen weisst du gar nicht, dass das soweit sortiert ist, da du pro Iteration nur einen Wert an die richtige Stelle schiebst.

[Goma]

ok das stimmt, müsste aber i nicht trotzdem 6 sein da wir ja die 6. iteration betrachten?

[31chh0rn]

Hi, ich hätte zu dieser Art der Aufgabenstellung auch mal eine Frage. In dem Blatt zur Prüfungsvorbereitung stand, dass wir die Iterationen vorher nicht durchgehen sollen, sondern über die Invariante auf die momentane Situation schließen sollen. Ist es also legitim alle unsortierten Indizes einfach zu ignorieren und sich nur auf die sortierten zu beziehen?
Nur nach diesen ist ja auch gefragt, wobei die der Formulierung "Skizziere den Zustand" durchaus auf das komplette Array zu beziehen ist.

[Goma]

ja hätte auch gerne langsam mal ne öffizielle stellungnahme bzgl. des i's... denn bei der A3 wird auch nach der 6. Iteration gefragt und i=6 und nicht 5...

[Domac]

Hi.

Ich kann keine offizielle Stellungnahme machen, aber laut MuLö ist i=5, da der Algorithmus bei i = 0 beginnt (siehe Invariante).
Das macht so auch Sinn, denn dann ist die Invariante konsistent mit der Tatsache, dass i = 5 betrachtet wird.

Grüße

[Goma]

Hmm,
wie war nochmal die GDI2 Regel, ab wann fängt ein Algo ab i=0 an und ab wann bei i=1?
Weil bei partitioning by scanning scheint er ja dann doch wieder bei 1 anzufangen... bin verwirrt...

[savanna]

Also wenn man sich die ganzen Videos vom SS13 anschaut, gilt eigentlich immer:
i=0 bedeutet, es wurde noch keine Iteration durchgeführt, wir befinden uns
also vor der 1.Iteration. Nach dieser hat i dann den Wert 1 usw.
Ich denke also, dass i in und nach der 6.Iteration den Wert 6 hat.
Die beiden Zustände, die verglichen werden, sind daher i=5 und i=6.

[Goma]

Genau so denk ichh das auch, aber in der Musterlösung steht halt 2mal i=5...

[ob1]

Sieh's mal so: Wir fangen in der Regel bei i=0 an. Vor der "ersten" Iteration (i=0) ist noch nichts passiert, nach der ersten Iteration ist die erste Zahl an der richtigen Position. Dann erst setzen wir i=1. Dann ist die zweite Iteration mit i=1 dran. Während der sechsten Iteration ist dann i=5.
Stell es dir einfach wie eine for-Schleife vor. Die Zahl im Index gilt immer während der gesamten Iteration. Wenn wir sagen, dass etwas "vor" der Iteration mit Index 5 ist, dann ist das sozusagen noch vor dem Schleifenrumpf, nachdem wir i auf 5 gesetzt haben. "Nach" der Iteration mit Index 5 ist dann, wenn der Schleifenrumpf schon durchlaufen ist, aber noch bevor wir i auf 6 setzen.

Für das Pivot Partitioning by scanning ist ein "i" für die Iterationen eigentlich gar nicht definiert. Vielleicht ist die Musterlösung an die Definition in Pivot partitioning angelehnt, wo S den Index i (1...n) hat.

Ist es also legitim alle unsortierten Indizes einfach zu ignorieren und sich nur auf die sortierten zu beziehen?
Nur nach diesen ist ja auch gefragt, wobei die der Formulierung "Skizziere den Zustand" durchaus auf das komplette Array zu beziehen ist.

Das würde mich allerdings auch interessieren. Ohne jede Iteration durchzugehen kann man ja nicht wissen, in welcher Reihenfolge die Elemente [0... n-i-1 ] sind. Das ist zwar eigentlich egal, aber nicht, wenn man das ganze Array hinmalen soll.

[Goma]

@ob1: das Problem ist ja das in der Aufgabe nicht klar zu verstehen ist, ist der 6. durchlauf gemeint oder i=6... es ist einfach nicht sauber formuliert und wie man sieht schwanken selbst die Musterlösungen zwischen "mal ist i=6 und mal i=5" wenn nach der 6. iteration gefragt ist.
Und das hierzu keine klare stellungnahme kommt ist langsam traurig (oder typisch für GDI2 in diesem Semeser...), schließlich steht in dem Vorbereitungs PDF das IN der Klausur solche fragen nicht beantwortet werden.

Edit: grade nochmal geschaut, deine erklärung passt leider auch nicht, denn es müssten laut deiner erklärung 6 zahlen getauscht worden sein auch wenn i=5 ist... wieso steht in der Invariante dann aber das nur bis S[7] alles richtig sortiert ist und nicht bis S[6]?! genauso wie i einmal vor 5 (oder 4 je nachdem nun) und nach 6 (oder 5) sein müsste

und das andere würde mich auch interessieren, wobei das problem ja noch mit mehraufwand lösbar wäre, da es kein verständnis problem ist

[brjan]

Also i ist für mich einfach die Anzahl durchlaufener Iterationen, während gerade keine Iteration durchlaufen wird.

Die Formulierungen in der Musterlösung "Vor i=5" und "Nach i=5" halte ich für unintuitiv.

Eigentlich gibt es doch nur auf dem Übungsblatt Missverständisse. Die Formulierungen lauten sonst doch einheitlich "(Unmittelbar) vor Iteration X" und "(Unmittelbar) nach Iteration X". Und i passt dann doch eigentlich immer auf die Anzahl bislang durchlaufener Iterationen.

Das Übungsblatt ist ohnehin alles andere als fehlerfrei.