Bill Gates und das Pfannkuchen-Problem der Mathematik

In der Mathematik und der Informatik gibt es ein Problem mit Pfannkuchen.
Dabei spielt die Pfannkuchen-Zahl eine entscheidende Rolle. Diese beschreibt wie viele Handgriffe notwendig sind, um einen beliebig großen Stapel an Pfannkuchen möglichst effizient der Größe nach zu Sortieren.
So verrückt sich das auch anhört, das Problem hat tatsächlich einen realen Bezug und eine tiefergehende Bedeutung beim Sortieren und Ordnen von Daten. Die Frage die dahinter steckt, ist, wie viele Schritte sind notwendig um eine große Menge an Daten (bzw. Pfannkuchen) effizient, schnell und ressourcensparend zu sortieren.
Das Problem selbst geht auf Jacob E. Goodman - er schrieb unter dem Namen Harry Dweighter - zurück und wie 2011 bewiesen wurde ist es NP-schwer. Das bedeutet, die Schwierigkeit steigt exponentiell mit der Anzahl an vorhandenen Daten.
1979 verfasste Bill Gates den einzigen Fachartikel seines Lebens zu diesem Problem. Dank seiner Arbeit lässt sich die Lösung zumindest etwas eingrenzen. Ein weiterer bekannter Name ist David X. Cohen, einer der Autoren der Simpsons und von Futurama. Dieser befasste sich mit einer Variante des Pfannkuchen-Problems und der Pfannkuchen-Zahl bei verbrannten Pfannkuchen.

[@benzinunbezahlbar6400]

Das worst cake Szenario...

[@Muck-qy2oo]

Nicht Wurst-Käse?

[@amesads4711]

Ich würde eine interessante Vermutung aufstellen (unbewiesen, kann also auch falsch sein): Der erste Block ist 0,1 mit Länge 2. Der zweite Block 3,4,5 hat Länge 3, der dritte Block 7,8,9,10,11 hat Länge 5, der vierte Block 13,14,15,16,17,18,19,20 hat Länge 8. Das klingt wie der Anfang der Fibonacci-Folge. Dann wäre P(20)=23. Der fünfte Block ist 22,23,24,...,34 mit Länge 13, also P(31)=34?

[@kurtwagner5661]

Man sollte nie einen Mathematiker als Kellner anstellen, die Gäste verlassen nach einer bestimmten Anzahl bestellter Pfannkuchen nach einiger Zeit frustriert das Lokal ;)

[@crazyedo9979]

Bill Gates schreibt einen Fachartikel wie man lahme Computer vermeidet, dann entwickelte er Windos.😂🤣😂😁

[@christianstahl4099]

Es wird nicht das effektivste, sondern das effizienteste Verfahren angewandt. Diesen Unterschied sollte man schon kennen…

[@ulrikof.2486]

5:43 - Einspruch, ich sehe ein klares Muster. Die Pfannkuchenzahl P wächst n0-mal um je +1 pro +1 Anzahl A Pfannkuchen, dann gibt es einen Sprung um +2, danach geht es wieder n1-mal um je +1 pro Schritt hoch, wobei gilt n1 > n0, dann kommt wieder ein Sprung um +2, dann n2-mal +1 usw. Es gilt offenbar: n0 < n1 < n2 < n3 usw. Die in der Tabelle sichtbaren ersten nx sind: 1, 2, 4, 7, ... bzw. die Sprünge um +2 finden an den Positionen 3, 6, 11, 19, ... statt. Für diese Reihen gibt es möglicherweise eine Formel, vorausgesetzt, es wird nicht irgendwann auch +3er Schritte usw. geben, aber auch dafür könnte es eine Formel geben. PS: Ich habe das Video an dieser Stelle angehalten und weiß noch nicht, wie es weiter geht.

[@jaroel]

ich glaube es ist aber ein Beweis wichtig (und nötig). Du kannst deinen Beitrag aber bestimmt als "Ulrikof-Vermutung" einreichen...

[@ulrikof.2486]

@@jaroel im Video wird gesagt da sei kein Muster erkennbar. Dem widerspreche ich. Ein Muster erkennen bedeutet nicht bereits einen mathematischen Beweis zu haben. Im Gegenteil ist schnelle Mustererkennung das Normale, und bringt einen zu einer Vermutung, die überhaupt erst dazu führt dass jemand aus dem Muster etwas konkretisieren kann und dann dazu einen Beweis sucht.

[@laszlonemet4425]

Nach welchen Krt. sammelt/ordnet der Daten?

[@Bakerboy1826]

Für mich ist das ein sinnloser Unsinn.

[@Anrufbeantworter]

Sag das einem LKW-Fahrer, der Stahlplatten in verschiedenen Größen aufladen soll. Der muss die größten, und schwersten Platten unten haben. Auf dem Lagerplatz liegen die Platten so durcheinander, wie sie die Leute mit dem Kran nach der letzten Beladung hinterlassen haben.

[@hennykorting2950]

Bei den drei Pfannkuchen ist bei Fall 5 nur ein Jandgriff nötig, nicht 2. Den oberen runter nehmen und drunterlegen.

[@andiw70]

Zum Test: Den großen runter nehmen, die nächsten beiden drauf legen und zum Schluss den kleinen obendrauf. P(n) = 3

[@minicles]

Deine Lösung ist zwar möglich und tatsächlich in diesem Fall schneller, sie widerspricht jedoch der Aufgabenlogik 🙃 Bei dieser Art der angedachten Sortierstrategie hat der Kellner keine Möglichkeit etwas abzulegen. Stell dir vor, er hat nur einen einzigen Pfannenwender zu Hilfe

[@andiw70]

OK, dann hast du sicher recht, wurde nur nicht ganz klar (ca. 4:00 min.)

[@minicles]

Ich fürchte, dass ist das Problem, wenn man sich zu lange mit etwas beschäftigt. Dann wird man leider blind für kleine aber wichtige Details, weil es einem selbst zu klar ist... Sorry