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

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

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

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

נוסח הבעיה כפי שהופיע בירחון האמריקאי למתמטיקה

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

הידוע אודות הבעיה

בעיה זו אמנם קלה לניסוח, אך עדיין לא נמצא לה פתרון כללי. ידוע שעבור $n=2$ המספר המקסימלי של היפוכים הוא הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle f(2)=1} . עבור $n=3$ זה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(3)=3} וככל ש-n גדל, כך נעשה יותר ויותר מורכב לחשב את מספר ההיפוכים. כמו כן, ידוע כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(17)=19} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(18)=20} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(19)=22} . אך טרם ידוע מהו מספר ההיפוכים עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=20} .

הבעיה עוררה עניין רב ובתגובה הראשונה לפרסומה גרי, ג'ונסון ולין ב-1977 הראו כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1 \leq f(n) \leq 2n-6} . זמן קצר לאחר מכן הראו ביל גייטס, שהיה אז סטודנט בהארוורד, והמרצה שלו כריסטוס פאפאדימיטריו כי הטווח למספר ההיפוכים, עבור n מכפלה של 16 הוא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {17n \over 16} \le f(n) \le {(5n+5)\over 3}} .

התוצאה הטובה ביותר הידועה היום היא הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle {\frac {15}{14}}n\leq f(n)\leq {\frac {18}{11}}n} .

סידור פנקייקים שרופים

גייטס ופאפאדימיטריו הציגו במאמרם וריאציה נוספת של הבעיה לפיה תחתית הפנקייקים שרופה ויש לסדרם כך שהצד השרוף יישאר כלפי מטה, כלומר, על כל פנקייק לעבור מספר זוגי של היפוכים. במצב זה הטווח למספר ההיפוכים הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {3n \over 2}-1 \le f(n) \le 2n-3}

שימושים בתחומים שונים

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

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

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

מדיה וקבצים בנושא בעיית סידור הפנקייקים בוויקישיתוף

• בעיית סידור הפנקייקים, באתר MathWorld (באנגלית)   

• William H. Gates, Christos Papadimitriou, BOUNDS FOR SORTING BY PREFIX REVERSAL, Discrete Mathematics 27, 1979
• David S. Cohen, 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, An (18/11)n upper bound for sorting by prefix reversals, Theoretical Computer Science Volume 410, Issue 36, 31 August 2009
• Simon Singh, Flipping pancakes with mathematics, באתר theguardian
• David S. Cohen, Manuel Blum, On the problem of sorting burnt pancakes, Discrete Applied Mathematics Volume 61, Issue 2, 28 July 1995

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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