Pfannkuchen-Sortierproblem

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. Erstmals veröffentlicht wurde das Problem 1975 von unter dem Pseudonym Harry Dweighter (gleicht in der Aussprache harried waiter, „gestresster Kellner“) 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.