Theorie 5 Aufgabenstellung

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Theorie 5 Aufgabenstellung

Beitrag von Kija G »

Hallo,
sollen wir bei der 5. Übung wieder jeweils eine aussagekräftige Iteration auswählen, nach der wir wieder Invariante und Vorgehensweise erläutern?
Normalerweise stand es immer explizit dabei, jetzt heißt es nur noch "halten Sie sich an die Musterlösungen der Aufgaben 1 - 3 der Klausur 2012".

Ich habe auch das Gefühl, dass die Aufgabenstellungen der Theorietestate immer allgemeiner und undeutlicher gehalten werden, was leicht dazu führen kann die Aufgabenstellung falsch zu verstehen.
Danke und Gruß

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorie 5 Aufgabenstellung

Beitrag von JannikV »

Der Trick ist, langsam zu wissen was gefordert ist ;-)
Du hast nämlich vollkommen Recht: aussagekräftige Iteration wählen, Schleifenvariante und -invariante usw. So wie bisher. Praktisch ist ja immer das gleiche gefordert.

VG

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Re: Theorie 5 Aufgabenstellung

Beitrag von Kija G »

Klar weiß man irgendwann was gemeint ist, da hast du recht.
Aber da es um Testate geht hab ich es ganz gerne schwarz auf weiß stehen ;)
Danke für die Antwort

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Theorie 5 Aufgabenstellung

Beitrag von robertH »

Das Darstellen einer einzigen Iteration bedeutet dann bei pivot partitioning by scanning, dass lediglich ein einzelner Zahlentausch stattfindet und wir diesmal nicht
jeden einzelnen Fall im Induktionsschritt zeigen müssen?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorie 5 Aufgabenstellung

Beitrag von JannikV »

Ja, aber schon noch etwas drum herum. Das Initialisieren der Variablen in der Induktionsbasis und auch das Angeben der am Ende fertig partitionierten Sequenz kannst du schon noch dazu machen ;-)

sb.
Neuling
Neuling
Beiträge: 8
Registriert: 10. Mai 2013 10:37

Re: Theorie 5 Aufgabenstellung

Beitrag von sb. »

Geht es in der zweiten Aufgabe um die in-place-Variante von Quicksort? Wenn nein, weiß ich nicht, was ich in der Aufgabe machen soll. Der Wiki-Eintrag des Algorithmus bringt mir diesbezüglich nichts und wenn ich nach dem Algorithmus "Pivot partitioning by scanning" google, gelange ich entweder hier ins Forum oder auf Links zu Quicksort oder auf nicht hilfreiche Seiten.
Insbesondere gibt es kein Video unter diesem Namen, was die Sache zusätzlich erschwert.

Wenn ja, warum wird dies nicht in der Aufgabenstellung erwähnt? Das würde vieles leichter machen, z.B. die Arbeit sparen, herauszufinden, was die Aufgabenstellung von einem will.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorie 5 Aufgabenstellung

Beitrag von JannikV »

Hi,

durchzuführen ist der Algorithmus Pivot partitioning by scanning aus dem Wiki: http://wiki.algo.informatik.tu-darmstad ... y_scanning

Wie du erkannt hast, hat dieser Algorithmus etwas mit der in-place Variante von Quicksort zu tun. Es ist aber nicht der ganze Quicksort Algorithmus. Diesen findest du auf der entsprechenden Wikiseite.
Pivot partitioning ist viel mehr ein wesentlicher Teil von Quicksort. Hier wird die Sequenz so umsortiert, dass bezüglich einem gegebenen Pivot-Element alle kleineren Elemente links und alle größeren Elemente rechts stehen.
Quicksort macht dann nicht viel mehr, als so oft Pivot-Elemente zu wählen und die Teilsequenzen zu partitionieren, bis sie insgesamt sortiert ist.

VG

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

Re: Theorie 5 Aufgabenstellung

Beitrag von Domac »

Hey!

Ich frage lieber nochmal nach, bevor ich jetzt 16 Iterationen bei der 6.1 durchgehe… Ziel ist es als sich nur 1-2 Iterationen rauszupicken; anhand den erklärt man dann Schleifen{varianten,invarianten}, Korrektheit und Abbruchbedingung mit Wiki Notation?

Grüße

EDIT: Hat sich erledigt, habe den Beitrag von Jannik übersehen.
Extend my dropbox space (here).
Thanks!

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Re: Theorie 5 Aufgabenstellung

Beitrag von Kija G »

heißt das, dass pivot partitioning der eigentliche sortieralgorithmus von quicksort (in-place) ist, der rekursiv auf die Teilsequenzen aufgerufen wird?

d.h. eine komplett geordnete (Teil-) sequenz wäre dann eine Rekursionsstufe?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorie 5 Aufgabenstellung

Beitrag von JannikV »

Kija G hat geschrieben:heißt das, dass pivot partitioning der eigentliche sortieralgorithmus von quicksort (in-place) ist, der rekursiv auf die Teilsequenzen aufgerufen wird?
Mehr oder weniger ja. Nur dass ein einzelner Aufruf davon eben nicht komplett durchsortiert, sondern nur nach größer oder kleiner p ordnet.
Kija G hat geschrieben:d.h. eine komplett geordnete (Teil-) sequenz wäre dann eine Rekursionsstufe?
Durch das was ich oben geschrieben habe klar geworden? Sonst bitte nochmal die Frage anders formulieren, ich bin mir nicht ganz sicher was meinst und will nichts verwirrendes sagen.

EDIT: falls ich mich in einem anderen Post irgendwie vertan habe: Quicksort (aus dem Wiki) ruft nicht pivot partitioning by scanning auf. Letzterer ist nur für die in-place Variante. Der beschriebene Quicksort legt ja selbst neue Sequenzen an. Siehe "Further information" auf der Wiki Seite.

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Re: Theorie 5 Aufgabenstellung

Beitrag von Kija G »

Danke, ist soweit denke ich klar geworden :)

Kija G
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2013 18:03

Re: Theorie 5 Aufgabenstellung

Beitrag von Kija G »

Andere Verständnisfrage:
Zur Invariante von Bucketsort aus dem Wiki, Punkt 1.:

"Für j aus [1, ..., N - i], enthält A[j] alle Eingabestrings der Länge j"

Wie kommt man auf das N - i?
Nach meinem Verständnis besteht mein gesamtes A aus 1 bis N Zellen, wobei N die Länge meines längsten Input-Strings darstellt.
Also müsste es doch eigentlich "j aus [1, ..., N]" heißen?

Das aktuelle betrachtet Zeichen und A[j] greif ich mir ja nach jeder Iteration durch N - i + 1

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorie 5 Aufgabenstellung

Beitrag von JannikV »

Hey,

wenn da [1, ..., N] stehen würde wäre A ja konstant. Aber aus A wird in jeder Iteration ein Multiset voller Strings rausgeholt. Und zwar von hinten.
Also ist vor der ersten Iteration (i=0) A gefüllt von 1 bis N-0.
Nach der ersten Iteration (i=1) ist A gefüllt von 1 bis N-1.
Nach der zweiten (i=2) von 1 bis N-2.
usw. usw.

VG

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

Re: Theorie 5 Aufgabenstellung

Beitrag von Domac »

Hey,

ich werde aus dem Wiki nicht wirklich schlau. Das "Pivot partitioning by scanning" ist im Wiki sehr komisch beschrieben… kann man sich alternativ etwas anderes anschauen? Ich verstehe den Algorithmus einfach nicht, so wie er im Wiki beschrieben ist.

Grüße
Extend my dropbox space (here).
Thanks!

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorie 5 Aufgabenstellung

Beitrag von JannikV »

Hey, also ich kann mir nicht vorstellen, dass du dir einfach was anderes ansehen kannst xD

Wann hast denn dein Testat? Wenn nicht gleich morgen, dann kannst du ja morgen in meine Sprechstunde kommen (oder wir sehen uns zufällig im Bus ^^)

Was besseres fällt mir jetzt auch nicht ein.

Antworten

Zurück zu „Archiv“