Übungen Klausur A2,A3,A4

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Übungen Klausur A2,A3,A4

Beitrag von onbes »

Hey,

ich habe ein Problem mit der Aufgabenstellung bei A2 zum Thema Mergesort.

Es ist die Rede von
- "...vor und nach dem Rekursionsschritt die Schleifeninvariante":
Diese Formulierung ist bei einem rekursiven Algorithmus, insbesondere bei der Rekursionsinvariante von Mergesort, nicht einfach zu verstehen. Oder zielt es implizit auf die Invariante vom Merge-Algorithmus ab?

und

- "zum Zustand unmittelbar nach dem Rekursionsschritt die Schleifenvariante":
Selbes Problem wie in der vorherigen Formulierung. Wenn sich das wieder auf den Merge-Algorithmus bezieht, dann müsste doch angegeben werden, welche Iteration wir betrachten sollen, weil wir eine Aussage über i1 und i2 treffen müssen.

Vermutlich ein Copy&Paste Fehler, ich will nur sichergehen.

EDIT:

Bei der A3)
Wenn ich mich nicht irre sollte es gar keine 8. Iteration geben. Nach 4 Iterationen terminiert der Algorithmus, weil ja genau 4 swaps durchgeführt werden und ein swap nur 1 mal in einer Iteration durchgeführt wird.

Zur A5)
Um den Dijkstra Algorithmus anwenden zu können muss (zumindest in der Variante des Wikis) ein gerichteter Graph gegeben sein.

Grüße

Stephoogle
Neuling
Neuling
Beiträge: 10
Registriert: 10. Sep 2013 15:43

Re: Übungen Klausur A2,A3,A4

Beitrag von Stephoogle »

Hallo!

"ich habe ein Problem mit der Aufgabenstellung bei A2 zum Thema Mergesort."

Die Aufgabe verlangt, dass die Input Sequenz mit den Algorithmen von Mergesort geteilt und mittles Merge wieder zusammengeführt werden. Da nach dem Endergebnis gefragt wird, müssen alle folgenden Rekursionsschritte durchgeführt werden und somit auch jedesmal Invariante und Variante gezeigt werden. Das Hauptaugenmerk liegt also auf dem Algorithmus Mergesort; im Idealfall betrachten Sie zusätzlich noch Merge mit dessen Invariante und Variante.

"Bei der A3)
Wenn ich mich nicht irre sollte es gar keine 8. Iteration geben. Nach 4 Iterationen terminiert der Algorithmus, weil ja genau 4 swaps durchgeführt werden und ein swap nur 1 mal in einer Iteration durchgeführt wird."

Dies ist leider ein Fehler auf den Übungsblatt und wird zeitnah durch eine neue Inputsequenz (wird im moodle wieder hochgeladen) ersetzt.

"Zur A5)
Um den Dijkstra Algorithmus anwenden zu können muss (zumindest in der Variante des Wikis) ein gerichteter Graph gegeben sein. "

Ihr Einwand ist berechtigt, allerdings sollte hier nochmal ein Graphenalgorithmus verbunden mit der Berechnung der Kanten im Fokus stehen. Den Algorithmus von Dijkstra kann man dann trotzdem darauf anwenden.

Muqy
Neuling
Neuling
Beiträge: 2
Registriert: 20. Sep 2013 18:39

Re: Übungen Klausur A2,A3,A4

Beitrag von Muqy »

Hi.

Ich habe die neue Version von Aufgabe 3 bearbeitet. Leider klappt es bei mir immer noch nicht, weil ich hier nur bis zur 5. Iteration komme, in der Aufgabe aber nach der 6. gefragt ist. Ich komm nicht drauf, wo der Fehler liegt :(

Von der Ausgangssequenz sind fünf Tausche nötig, eh alle Werte in der richtigen Teilsequenz stehen. Das bedeutet 5 Iterationen, oder nicht? Oder hab ich das Wiki da falsch verstanden und schon das Vorrücken eines Iterators gilt als Iteration, sodass gar nicht zwingend in jeder getauscht wird?
Aber in dem Fall wäre man bei der alten Version doch auch problemlos auf 8 Iterationen gekommen.

LG und danke im Voraus

Stephoogle
Neuling
Neuling
Beiträge: 10
Registriert: 10. Sep 2013 15:43

Re: Übungen Klausur A2,A3,A4

Beitrag von Stephoogle »

Nein es sind genau sechs Iterationen. Hast du bedacht, dass auch der pivot-Wert an die richtige Stelle muss? ;)
Wenn es dir noch nicht einleuchtet: Musterlösung wird wohl morgne hochgeladen

Antworten

Zurück zu „Archiv“