Pfannkuchen-Sortierproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der diskreten Mathematik bzw. der theoretischen Informatik, bei dem es anschaulich darum geht, einen Stapel Pfannkuchen der Größe nach zu sortieren. Der Stapel besteht aus Pfannkuchen unterschiedlicher Größe und soll so sortiert werden, dass am Ende der größte Pfannkuchen an unterster Stelle ist, der zweitgrößte darüber bis zum kleinsten ganz oben. Dazu darf in jedem Schritt ein von der aktuellen Spitze des Stapels ausgehender Teilstapel ausgewählt und als ganzer umgekehrt werden. Gefragt ist nach der kleinsten Anzahl an Schritten dieser Art, die benötigt werden, um unabhängig von der Ausgangslage den gesamten Stapel zu sortieren.

Der Teilstapel bestehend aus den drei obersten Pfannkuchen wird umgekehrt.

Erstmals veröffentlicht wurde das Problem 1975 von Jacob E. Goodman unter dem Pseudonym Harry Dweighter (gesprochen wie harried waiter, also gequälter Ober) in der Zeitschrift American Mathematical Monthly. Seitdem wurden zahlreiche ernsthafte Forschungsergebnisse zum Thema veröffentlicht. Anwendung findet das Problem unter anderem bei Mutationen in der Genetik.[1]

Pfannkuchen-Zahlen[Bearbeiten]

Die Anzahl der nötigen Schritte, um einen Stapel aus n Pfannkuchen in jedem Fall zu sortieren, wird als P_n bezeichnet. Die Werte sind für kleine n bekannt, für größere gibt es Abschätzungen. Offensichtlich gilt P_1=0, da ein Stapel aus einem Pfannkuchen bereits sortiert ist, und P_2=1, da im Fall, dass der größere Pfannkuchen zu Beginn oben liegt, der Stapel dadurch sortiert werden kann, dass er einfach umgekehrt wird.

Ein einfacher Algorithmus zeigt P_{n+1} \leq 2 + P_n: Dazu wird der größte Pfannkuchen zunächst an die Spitze gebracht, anschließend wird der Stapel umgewendet, dass er sich ganz unten befindet. Nach diesen zwei Schritten wird der restliche Stapel sortiert, ohne den untersten Pfannkuchen zu beachten, dies geschieht in P_n Schritten. Zusammen mit P_2=1 gilt also P_n \leq 2n-3.

Die Schranken wurden im Laufe der Zeit immer weiter verbessert: Eine erste Abschätzung bewiesen William H. Gates (heute bekannt als Bill Gates) und Christos Papadimitriou im Jahr 1979:[2]

P_n<\frac{5n+5}{3}

Diese Abschätzung wurde inzwischen verbessert auf \frac{15n}{14}+O(1)<P_n<\frac{18n}{11}+O(1).[3] Dabei steht O(1) für eine von n unabhängige Konstante, siehe O-Notation.

Pfannkuchen-Zahlen
(Folge A058986 in OEIS)
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
P_n 0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19

Verbrannte-Pfannkuchen-Problem[Bearbeiten]

Eine Variante des Problems handelt von Pfannkuchen, die auf einer Seite verbrannt sind. Auch hier soll ein Stapel Pfannkuchen durch Umkehren von Teilstapeln der Größe nach sortiert werden, allerdings wird zusätzlich gefordert, dass am Ende die verbrannten Seiten alle nach unten zeigen. Für die Anzahl der notwendigen Schritte in dieser Variante konnten 1995 David S. Cohen (heute David X. Cohen) und Manuel Blum die folgende Abschätzung beweisen: 3n/2\leq P'_n\leq 2n-2 (wobei die obere Schranke nur für n>9 gilt).[4]

Verbrannte-Pfannkuchen-Zahlen
(Folge A078941 in OEIS)
n 1 2 3 4 5 6 7 8 9 10 11 12
P'_n 1 4 6 8 10 12 14 15 17 18 19 21

Einzelnachweise[Bearbeiten]

  1. Brian Hayes: Gene und Pfannkuchen. In: Spektrum der Wissenschaft. Oktober 2008. (online)
  2. William H. Gates, Christos Papadimitriou: Bounds for Sorting by Prefix Reversal. In: Discrete Mathematics. Vol. 27, 1979, S. 47–57. DOI:10.1016/0012-365X(79)90068-2. (online)
  3. B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, W. Voit: An upper bound for sorting by prefix reversals. In: Theoretical Computer Science. 410, Nr. 36, 2009, S. 3372–3390. DOI:10.1016/j.tcs.2008.04.045.
  4. David S. Cohen, Manuel Blum: On the problem of sorting burnt pancakes. In: Discrete Applied Mathematics. 61, Nr. 2, 1995, S. 105–120. DOI:10.1016/0166-218X(94)00009-3.

Weblinks[Bearbeiten]