Was haben Bill Gates und Homer Simpson gemeinsam? Beide beschäftigten sich

bereits mit der Frage: 'Wie oft muss ein Stapel von n unterschiedlich großen Pfannkuchen in der ungünstigsten Anordnung mindestens gewendet werden, damit er der Größe nach sortiert vorliegt? (also der größte Pfannkuchen unten, der kleinste oben usw.)'. Vor ziemlich genau 40 Jahren veröffentlichte Jacob E. Goodman unter dem Pseudonym 'Harry Dweighter' einen Artikel, der dieses Problem erstmals beschrieb. Hierbei geht es um die Sortierung eines ungeordneten Pfannkuchenstapels mit Hilfe von Flips. Die zunächst einfach klingende Fragestellung, die sich Homer und Bill Gates gestellt haben, wird allerdings für zunehmend größere n deutlich komplizierter. Bill Gates und Christoph Papadimitriou kamen zwar zu einer Annäherung der sogenannten Pfannkuchenzahl der Stapelgröße n, jedoch ist bis heute keine Lösung dieses Problems in Sicht. Die Pfannkuchenzahlen bis 19 sind bekannt, für eine Stapelgröße ab 20 Pfannkuchen konnte bisher niemand die Pfannkuchenzahl feststellen. Die Fragestellung ist allerdings nicht nur für Mathematiker oder gelbe Männchen interessant, denn in der Genetik oder in der Verwaltung von Daten gibt es einige Analogien zum Pfannkuchen-Sortier-Problem.

In unserer Arbeit wenden wir unterschiedliche Ansätze aus den Bereichen der Mathematik und Informatik auf das Pfannkuchen-Sortier-Problem an und zeigen eine mögliche Lösungsfunktion M(k) auf.