Hallo,
ich habe mich mit der Aufgabe 3 der Runde 2 befasst und mir ist aufgefallen, dass bei der PWUE-Zahl von n, welche die höchste Möglichkeit an Wende-und-Ess-Operationen für einen Stapel S mit der Anzahl der Pfannkuchen n ausgibt, es einen möglichen Fehler gibt, da mir Optionen mit mehr Wende-und-Ess-Operationen gelungen sind als es die angegeben PWUE-Zahlen angeben.
Ein Beispiel dafür wäre ein Stapel mit der Länge n=4
S=(2,4,3,1) hier könnte man zuerst den ganzen Stapel rumdrehen dann hätte man den Stapel S1=(3,4,2). Anschließend muss man den Pfannenwender unter den zweiten Pfannkuchen schieben damit man einen neuen Stapel S2=(3,2) bekommt. Danach muss man den Stapel erneut komplett wenden und würde den Stapel S3=(3) als Ergebnis bekommen.
Bei diesen Wendemöglichkeiten wären es jedoch 3 Operationen, die PWUE Zahl P(n) für n=4 ist jedoch 2.
Lg,
Marvin Thiele
Den Pfannenwender könnte man erst unter den dritten Pfannkuchen schieben (4,2,1) und dann den ganzen Stapel umdrehen (2,4). Die kleinstmögliche Anzahl an Operationen für den Stapel ist also 2 und es gibt keinen Stapel mit n=4 , für den es mindestens 3 Operationen benötigt um eine aufsteigende Sortierung zu erreichen.
Der Knackpunkt bei der PWUE-Zahl ist: Sie stellt ein "maximales Minimum" dar. Für jeden einzelnen Stapel S der Größe n wird die minimale Anzahl der zur Sortierung nötigen Operationen betrachtet, also A(S). Dass es für einen Stapel S auch möglich sein kann, ihn mit mehr Operationen zu sortieren, kann gut sein, ist aber irrelevant. Die PWUE-Zahl für n ist dann die größte Zahl A(S) - also eben das maximale Minimum -, die bei Stapeln S der Größe n vorkommen kann.
Solche maximalen Minima (je nach Problemlage können es auch minimale Maxima sein) spielen in der Informatzik immer wieder eine wichtige Rolle. Sie geben im Allgemeinen Antwort auf die Frage: "Wie hoch kann der Aufwand werden, selbst wenn ein optimales Verfahren verwendet wird?" Konkret für die Aufgabe: "Wie viele Sortier-Operationen kann ich im schlechtesten Fall benötigen, selbst wenn ich optimal, also mit minimalem Aufwand an Operationen, sortiere?"