בעיית סידור הפנקייקים

בעיית סידור הפנקייקים (באנגלית: Pancake sorting problem) היא בעיה בקומבינטוריקה, שהגה המתמטיקאי מהסיטי קולג' של ניו יורק בשנת 1975.

גודמן חשב על בעיה זו בביתו, בזמן שעסק בקיפול מגבות. הוא התבונן בערימה המבולגנת והחליט שהוא רוצה לסדר אותה מהמגבת הגדולה לקטנה, אך לא היה לו מקום לערימה נוספת אז הוא פשוט הפך את הערימה מספר פעמים על ראשה (כל פעם הוא לקח מספר שונה של מגבות) עד שהערימה הייתה מסודרת באופן הרצוי. גודמן שאל את עצמו מה התרחיש הגרוע ביותר? כלומר, עבור מספר כלשהו של מגבות מה מספר ההיפוכים הרב ביותר אותו יש לבצע על מנת שהערימה תסתדר? הוא החליט לשלוח שאלה זו לירחון האמריקאי למתמטיקה "American Mathematical Monthly" כבעיית סידור פנקייקים, ופרסם אותה בשם בדוי, "הארי דוויטר" (נשמע כמו "harried waiter" - מלצר נחפז).

לבעיה הוצעו מספר ואריינטים ויש לה השלכות על תכנון רשתות ובעיית של סידור גנום.

==נוסח הבעיה כפי שהופיע בירחון האמריקאי למתמטיקה==
השף במסעדה שלנו מעט מרושל. כאשר הוא מכין פנקייקים, הם יוצאים בגדלים שונים והוא עורם אותם באקראי. לכן, בדרכי לסועד אני מארגן אותם מחדש כך שהגדול ביותר למטה והקטן ביותר למעלה על ידי כך שאני לוקח מספר פנקייקים מראש הערימה והופך אותם. אני חוזר על פעולה זו מספר פעמים (כל פעם עם כמות שונה של פנקייקים) עד שהערימה מסודרת בסדר המבוקש. והשאלה היא: אם יש n פנקייקים, מהו המספר המקסימלי של היפוכים (כפונקציה של n) שאני אאלץ לבצע?

==הידוע אודות הבעיה==
בעיה זו אמנם קלה לניסוח, אך עדיין לא נמצא לה פתרון כללי. ידוע שעבור <math>n=2</math> המספר המקסימלי של היפוכים הוא <math>f(2)=1</math>. עבור <math>n=3</math> זה <math>f(3)=3</math> וככל ש-n גדל, כך נעשה יותר ויותר מורכב לחשב את מספר ההיפוכים. כמו כן, ידוע כי <math>f(17)=19</math>, <math>f(18)=20</math>, <math>f(19)=22</math>. אך טרם ידוע מהו מספר ההיפוכים עבור <math>n=20</math>.

הבעיה עוררה עניין רב ובתגובה הראשונה לפרסומה גרי, ג'ונסון ולין ב-1977 הראו כי <math> n+1 \leq f(n) \leq 2n-6</math>. זמן קצר לאחר מכן הראו ביל גייטס, שהיה אז סטודנט בהארוורד, והמרצה שלו כריסטוס פאפאדימיטריו כי הטווח למספר ההיפוכים, עבור n מכפלה של 16 הוא: <math>{17n \over 16} \le f(n) \le {(5n+5)\over 3}</math>.

התוצאה הטובה ביותר הידועה היום היא <math>\frac{15}{14} n \leq f(n) \leq \frac{18}{11} n</math>.

==סידור פנקייקים שרופים==
גייטס ופאפאדימיטריו הציגו במאמרם וריאציה נוספת של הבעיה לפיה תחתית הפנקייקים שרופה ויש לסדרם כך שהצד השרוף יישאר כלפי מטה, כלומר, על כל פנקייק לעבור מספר זוגי של היפוכים. במצב זה הטווח למספר ההיפוכים הוא <math>{3n \over 2}-1 \le f(n) \le 2n-3</math>

==שימושים בתחומים שונים==
לבעיית סידור הפנקייקים, יש שימושים בתחומים שונים. ניתן להגדיר רשת או גרף של פנקייקים, בו כל צומת מתאים לפרמוטציה של הפנקייקים ושני צמתים קשורים אם ניתן להגיע מסידור אחד למישנהו בפעולת הפיכה יחידה. זהו גרף רגולרי עם דרגה קטנה מ-log מספר הצמתים. השאלה אודות הערך של f(n) שקולה לשאלה מה קוטר הגרף הזה. לרשת זו תכונות של עמידות בנפילות צמתים והיא הוצעה כבסיס לרשת P2P.

השאלה קשורה גם לבעיות מרחק בין גנומים של מינים שונים. למשל, הבנת מספר הפעולות הנדרשות למיון יכולה לסייע לביולוגים לדעת מה הזמן הדרוש לשינוי סדר הגנים בדנ"א, כשאורגניזמים שונים מכילים את אותם הגנים רק ברצף שונה.

== קישורים חיצוניים==

* 
<div class="mw-content-ltr">
* William H. Gates, Christos Papadimitriou, [https://web.archive.org/web/20070610154429/http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf BOUNDS FOR SORTING BY PREFIX REVERSAL], Discrete Mathematics 27, 1979
* David S. Cohen, [http://www.sciencedirect.com/science/article/pii/0166218X94000093 On the problem of sorting burnt pancakes], Discrete Applied Mathematics Volume 61, Issue 2, 28 July 1995
* B. Chitturi, W. Fahle, Z. Meng, L. Morales, C.O. Shields, I.H. Sudborough,, W. Voit, [http://www.sciencedirect.com/science/article/pii/S0304397508003575 An (18/11)n upper bound for sorting by prefix reversals], Theoretical Computer Science Volume 410, Issue 36, 31 August 2009
* Simon Singh, [http://www.theguardian.com/science/blog/2013/nov/14/flipping-pancakes-mathematics-jacob-goodman Flipping pancakes with mathematics], באתר theguardian
* David S. Cohen, Manuel Blum, [http://www.sciencedirect.com/science/article/pii/0166218X94000093 On the problem of sorting burnt pancakes], Discrete Applied Mathematics Volume 61, Issue 2, 28 July 1995
</div>

== הערות שוליים ==

קטגוריה:אלגוריתמי מיון
קטגוריה:בעיות פתוחות במתמטיקה בדידה