Bill Gates und das Pfannkuchen-Problem der Mathematik
ฝัง
- เผยแพร่เมื่อ 23 มี.ค. 2024
- 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.
![[LIVE] : ONE ลุมพินี 68 | คู่เอก "พระจันทร์ฉาย vs โจนาธาน"](http://i.ytimg.com/vi/F3IM3w-XchI/mqdefault.jpg)
Es wird nicht das effektivste, sondern das effizienteste Verfahren angewandt. Diesen Unterschied sollte man schon kennen…
Das worst cake Szenario...
Nicht Wurst-Käse?
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.
ich glaube es ist aber ein Beweis wichtig (und nötig).
Du kannst deinen Beitrag aber bestimmt als "Ulrikof-Vermutung" einreichen...
@@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.
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?
Nach welchen Krt. sammelt/ordnet der Daten?
Bill Gates schreibt einen Fachartikel wie man lahme Computer vermeidet, dann entwickelte er Windos.😂🤣😂😁
Zum Test:
Den großen runter nehmen, die nächsten beiden drauf legen und zum Schluss den kleinen obendrauf.
P(n) = 3
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
OK, dann hast du sicher recht, wurde nur nicht ganz klar (ca. 4:00 min.)
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
Für mich ist das ein sinnloser Unsinn.