Kurz & Krass: Pfannkuchen stornieren

20.04.2015
Aufgepasst! Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der theoretischen Informatik. Dabei geht es darum, einen Stapel ...

Aufgepasst! Das Pfannkuchen-Sortierproblem ist ein Problem aus dem Bereich der theoretischen Informatik. Dabei geht es darum, 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 in der Zeitschrift American Mathematical Monthly. Anwendung findet das Problem unter anderem bei Mutationen in der Genetik.