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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

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

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

הידוע אודות הבעיה[עריכת קוד מקור | עריכה]

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

הבעיה עוררה עניין רב ובתגובה הראשונה לפרסומה גרי, ג'ונסון ולין ב-1977 הראו כי [2]. זמן קצר לאחר מכן הראו ביל גייטס, שהיה אז סטודנט בהארוורד, והמרצה שלו כריסטוס פאפאדימיטריו[3] כי הטווח למספר ההיפוכים, עבור n מכפלה של 16 הוא: .

התוצאה הטובה ביותר הידועה היום היא [4].

סידור פנקייקים שרופים[עריכת קוד מקור | עריכה]

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

שימושים בתחומים שונים[עריכת קוד מקור | עריכה]

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ בעייה E2569
  2. ^ Stack of Pancakes
  3. ^ William H. Gates Christos Papadimitriou, BOUNDS FOR SORTING BY PREFIX REVERSAL, Discrete Mathematics 27, 1979
  4. ^ An 18/11 n upper bound for sorting by prefix reversals
  5. ^ A Churn-Resistant P2P-SystemBased on the Pancake Graph
  6. ^ Combinatorics of Genome Rearrangements By Guillaume Fertin, Anthony Labarre, Irena Rusu, Stéphane Vialette, Eric Tannier
  7. ^ Vineet Bafna and Pavel A. Pevzner Sorting by Transpositions