Fehler Übungsblatt Klausur A1

Goma
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Fehler Übungsblatt Klausur A1

Beitrag von 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
Zuletzt geändert von Goma am 23. Sep 2013 18:55, insgesamt 1-mal geändert.

pirate07
Erstie
Erstie
Beiträge: 17
Registriert: 29. Jan 2007 12:01
Wohnort: Darmstadt

Re: Übungsblatt Klausur A1

Beitrag von 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
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Übungsblatt Klausur A1

Beitrag von 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
Neuling
Neuling
Beiträge: 10
Registriert: 10. Sep 2013 15:43

Re: Übungsblatt Klausur A1

Beitrag von 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
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Übungsblatt Klausur A1

Beitrag von Goma »

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

31chh0rn
Neuling
Neuling
Beiträge: 7
Registriert: 23. Apr 2013 17:00

Re: Übungsblatt Klausur A1

Beitrag von 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
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Übungsblatt Klausur A1

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

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: Übungsblatt Klausur A1

Beitrag von 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
Extend my dropbox space (here).
Thanks!

Goma
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Übungsblatt Klausur A1

Beitrag von 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
Neuling
Neuling
Beiträge: 2
Registriert: 22. Sep 2013 18:28

Re: Übungsblatt Klausur A1

Beitrag von 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
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Übungsblatt Klausur A1

Beitrag von Goma »

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

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Re: Übungsblatt Klausur A1

Beitrag von 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
Erstie
Erstie
Beiträge: 22
Registriert: 22. Apr 2012 13:34

Re: Übungsblatt Klausur A1

Beitrag von 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
Erstie
Erstie
Beiträge: 20
Registriert: 28. Jul 2011 12:21

Re: Fehler Übungsblatt Klausur A1

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

Antworten

Zurück zu „Archiv“