בשנת 2014, הגיעה ארצות הברית להסכם ארוך טווח עם ממשלת ג'יבוטי כדי להמשיך להשתמש במחנה למונייה. הצבא האמריקני משתמש גם במסלולי המראה בחלקים נידחים יותר של המדינה לצורך פעולות מזל"ט מחוץ לבסיס ההסכם, הנשיא ברק אובמה אף התחייב להגדיל את הסיוע הכספי לג'יבוטי, ואף לעזור להרחיב את כישורי ההדרכה וסיוע החוץ.
רשת מיון
במדעי המחשב, רשת השוואה היא מבנה מתמטי הכולל רשת של "חוטים" שעליהם "זורמים" ערכים, ושל יחידות השוואה המחברות בין זוגות חוטים ומחליפות בין הערכים שבהם כדי לסדרם, אם יש צורך. כאשר רשת השוואה מסוימת מצליחה לסדר כל קבוצת ערכים המוכנסת אליה כקלט היא נקראת רשת מיון.
מיון בעזרת רשתות מיון שונה משיטות מיון אחרות בכך שכל רשת יכולה למיין מספר קבוע מראש של קלטים. כלומר אי אפשר לקחת רשת ולהשתמש בה לכל בעיית מיון. היתרון הגדול של רשת מיון הוא שהיא נוחה למיקבול (כלומר לחלוקה למשימות היכולות להתבצע במקביל). כך, כשהמיון נעשה על מחשב המאפשר ביצוע מקבילי ניתן להגיע באופן מעשי לביצועים של formula_1, להבדיל מהגבול הנמוך האפשרי עבור מיון טורי של formula_2. ישנן גם רשתות הנותנות סיבוכיות תאורטית טובה יותר (לוגריתמית) אך עם קבועים גבוהים מדי כדי לאפשר שימוש מעשי.
רשתות מיון הוצגו לראשונה ב-1954 על ידי ארמסטרונג, נלסון, ואו-קונור שהוציאו פטנט על הרעיון.
הגדרה.
רשת השוואה כוללת שני סוגי רכיבים - חוטים ויחידות השוואה. על החוטים ניתן לחשוב כמעבירים ערכים ה"זורמים" עליהם בו זמנית משמאל לימין. כל יחידת השוואה מקשרת שני חוטים. כשזוג ערכים "מגיע" ליחידת השוואה, היחידה מחליפה את הערכים אם ורק אם הערך הגבוה גדול מהערך הנמוך (במילים אחרות, יחידות ההשוואה מעבירות ערכים גבוהים למטה וערכים נמוכים למעלה).
בעזרת נוסחה ניתן להגדיר שאם החוט העליון נושא ערך formula_3 והתחתון ערך formula_4 אז אחרי המפגש עם יחידת ההשוואה הערכים על החוטים יהיו formula_5 ו formula_6 בהתאמה. רשת השוואה כזאת שתצליח להוציא (בצד ימין) ערכים ממוינים עבור כל סדר של ערכי קלט (בצד שמאל) נקראת רשת מיון.
הפעלה מלאה של רשת מיון פשוטה מופיעה באיור להלן. קל לראות שרשת זו תצליח למיין כל קלט אפשרי של ארבעה מספרים. שימו לב שארבע יחידות ההשוואה הראשונות "ישקיעו" את הערך הגדול למטה ו"יציפו" את הערך הקטן למעלה. היחידה האחרונה פשוט ממיינת את שני הערכים האמצעיים.
עומק ויעילות.
היעילות של רשת מיון יכולה להמדד ב"גודלה" - כלומר במספר יחידות ההשוואה שבה, או ב"עומקה" - כלומר במספר המקסימלי של יחידות ההשוואה שערך כלשהו עלול להזדקק לעבור דרכם. חלק מההשוואות ברשת יכולות להתבצע במקביל - כפי שמסומן על ידי יחידות השוואה הממוקמות על אותו קו אנכי. אם מניחים שכל השוואה לוקחת יחידת זמן אזי ניתן לראות שעומק הרשת שווה לזמן הדרוש לבצוע המקבילי של המיון.
בניית רשת מיון על ידי הוספת ערכים או על ידי בחירתם.
לכל מספר נתון של קלטים ניתן לבנות רשת מיון עם מספר מתאים של חוטים באופן רקורסיבי על ידי הוספת חוט לרשת קטנה יותר. נניח שנתונה רשת מיון עם formula_7 חוטים (כלומר המצליחה למיין כל קלט של formula_7 מספרים). ניתן להרחיב את הרשת (בהשראת מיון הכנסה) על ידי הוספת חוט נוסף ובצוע סדרה של השוואות על החוטים שמוינו על ידי הרשת הנתונה (ראו איור 4). ניתן גם להשיג את המטרה (בהשראת מיון בועות) על ידי "השקעה" מוקדמת של הערך המינימלי ואחר כך מיון שאר הערכים בעזרת הרשת הנתונה (ראו איור 5).
המבנה של שתי הרשתות המתקבלות הוא דומה. למעשה אם מסדרים את ההשוואות הניתנות לבצוע מקבילי זו מעל זו אזי ניתן לראות ששתי הרשתות למעשה זהות. ראו איורים 8-6.
לרשתות האלה יש עומק של formula_9. זהו שיפור על הסיבוכיות של לפחות formula_10 פעולות השוואה הדרושות למיון טורי במקרה הגרוע. למעשה ניתן לבנות רשתות מיון עם סיבוכיות טובה אף יותר ובעלות עומק של formula_1 כפי שיתואר להלן.
עקרון אפס-אחד.
בכמה מקרים, כמו בבניית רשת על ידי הוספת ערכים או על ידי בחירתם כפי שתואר למעלה, קל להראות שרשת ההשוואה הנוצרת היא רשת מיון. למרות זאת, לגבי רשת כללית ההוכחה שהרשת ממיינת בהצלחה כל קלט אפשרי היא משימה קשה. ברשת בעלת formula_7 חוטים יש לבדוק formula_13 סידורים אפשריים של ערכים על החוטים. אפשר להקטין מספר זה במידה משמעותית ל formula_14 בעזרת עקרון אפס-אחד. זהו עדיין מספר אקספוננציאלי של בדיקות אך הוא קטן מ-formula_13 לכל formula_16, וההבדל הולך וגדל עם formula_7.
נראה שלא תמצא דרך יעילה יותר לבעיית הבדיקה אם רשת השוואה היא רשת מיון, אלא אם יסתבר שP=NP, כיוון שבעיה זאת ידועה כבעיה co-NP-שלמה.
עקרון אפס-אחד קובע שאם רשת השוואה מצליחה למיין את כל formula_14 סידורי הקלטים עם הערכים 0 ו 1, אזי היא גם תצליח למיין קלטים עם כל ערך בכלל. הוכחת העקרון בקווים כלליים מראה שאם formula_19 היא פונקציה מונוטונית אזי לכל זוג ערכים formula_3 ו-formula_4 מתקיים formula_22 וגם formula_23.
מכאן נובע שאם רשת ממפה את ערכי הקלט formula_3 ו-formula_4 ל formula_26 ו-formula_27, אזי היא גם תמפה את formula_28 ו-formula_29 ל formula_30 ו-formula_31. אפשר להכליל טענה זאת באינדוקציה ללמה הטוענת שאם רשת ממפה את הקלטים formula_32 ל formula_33, אזי היא גם תמפה את formula_34 ל formula_35. המשך ההוכחה הוא בדרך השלילה. נניח שהרשת שמצליחה למיין כל סדרת קלטים של 0 ו-1 לא מצליחה למיין את הסדרה formula_32, כלומר קיימים זוג ערכים כך ש formula_37 והרשת מחליפה את ערכיהם שלא כראוי. אם כך, הרשת גם תמיין לא כראוי את סדרת הערכים formula_34 עבור הפונקציה המונוטונית:
זאת בסתירה להנחה שהרשת ממיינת נכון כל סדרת ערכי 0 ו-1. ומכאן שההנחה שעקרון אפס-אחד לא מתקיים אינה נכונה.
עקרון אפס-אחד שימושי גם לבניות של רשתות מיון כיוון שבכל שלב מספיק לוודא שהרשת מצליחה למיין קלטים של 0 או 1.
בניית רשת מיון יעילה.
ישנם מספר אלגוריתמים לבניית רשתות מיון פשוטות ויעילות בעלות עומק של formula_1 (ולכן גם גודל של formula_41) כמו מיון ביטוני, מיון מיזוג זוגי-אי-זוגי של בטשר, מיון של, ורשת מיון בזוגות. ברשתות אלה נעשה שימוש מעשי.
אפשר גם תאורטית לבנות רשתות מיון עם עומק מעריכי (לוגריתמי) לכל מספר של קלטים, בעזרת מבנה המכונה רשת AKS, על שם מגליו Ajtai, Komlós, Szemerédi. זאת הייתה תגלית חשובה אך ללא חשיבות מעשית בשל הקבועים החבויים בנוסחת הסיבוכיות שהם בגודל של "הרבה הרבה אלפים". זאת, בין השאר, בשל השימוש בגרף מרחיב. גרסה פשוטה יותר של רשת AKS הוצגה על ידי פטרסון אך גם כאן הקבועים מונעים כל שימוש מעשי. גודריך הציע בניה של רשת מיון בעלת עומק formula_2. הקבועים הפעם קטנים בהרבה מאשר ברשתות AKS, אך עומק של formula_2 לא נותן יתרון לבצוע מקבילי.
רשתות מיון אופטימליות.
עבור מספר קטן של קלטים ניתן לבנות רשתות מיון עם עומק אופטימלי (לבצוע המקבילי ביותר האפשרי) או עם גודל אופטימלי (מספר יחידות ההשוואה). רשתות אלה יכולות לשמש כדי לשפר ביצועים של רשתות גדולות יותר שנבנו באופן רקורסיבי, למשל בשיטת בטשר (ראה מעלה) על ידי עצירה מוקדמת של הרקורסיה והכנסת הרשת האופטימלית.
הטבלה להלן מסכמת את התוצאות האופטימליות המוכרות:
שש-עשר הרשתות בעלת עומק מינימלי מופיעות בספר "The Art of Computer Programming" של דונלד קנות' במהדורת 1973. האופטימליות של שמונה הרשתות הראשונות הוכחה על ידי פלויד וקנות' בשנות ה-1960, ושל שאר הרשתות רק ב 2014 (הרשתות של 9 ו-10 קלטים הוכחו כאופטימליות ב 1991).
רשתות מיון בעלות גודל מינימלי ידועות עד 10 קלטים. עבור יותר קלטים ידוע גבול עליון של הגודל כפי שמצוין בטבלה. כל עשר הרשתות הנ"ל היו מוכרות כבר משנת 1969 ושמונה הראשונות היו ידועות כאופטימליות מאז עבודתם של פלויד וקנות', אבל האופטימליות של הרשתות של 9 ו-10 קלטים הוכחה רק בשנת 2014.
נעשו גם ניסיונות לבנות רשתות מיון בעזרת אלגוריתמים גנטים: קנות' מזכיר שרשתות מיון עבור 9 ו-11 קלטים נמצאו כך על ידי לורן שוויברט ב-2001.
הבולים של האי פיטקרן
תושביו של האי הנידח פיטקרן קיבלו שירותי דואר ממגוון של מקורות החל ממחצית המאה ה-19. בשנת 1940 הנפיק דואר פיטקרן את סדרת הבולים הראשונה הנושאת את שם המושבה, ומאז הוא ממשיך בהנפקת בולי דואר המציגים ברובם את טבע האי ואת ההיסטוריה הסוערת שהובילה להתיישבות בו.
שירות הדואר במאה ה-19.
במהלך המאה ה-19 משלוח דברי הדואר מן האי פיטקרן לא היה מאורגן, והתבסס במידה רבה על ניצול הזדמנויות. תושבי האי, שלא היו ברשותם בולים, נאלצו לבקש מקברניטי הספינות שעצרו ליד האי שייקחו עימם את המכתבים, ימסרו אותם בבית הדואר המסודר הראשון אליו יגיעו, וירכשו שם בול דואר מתאים שיאפשר את העברת המכתב לתעודתו. מכתבים מוקדמים מן האי פיטקרן הם נדירים ביותר, הן בגלל מיעוט האוכלוסייה באי והן בגלל מיעוט כלי השייט שפקדו את המקום.
המכתב המתועד הראשון נשלח מפיטקרן ביום 17 במרץ 1830 על ידי הקברניט הבריטי שביקר באי כמפקדה של אניית הצי "סרינגפטם" (HMS Seringapatam). המכתב המתועד הראשון שנכתב על ידי תושב האי פיטקרן נשלח בחודש ספטמבר 1844 אל איש הדת האנגליקני ויליאם ארמסטרונג, שישב בעיר ולפראיסו שבצ'ילה וגילה התעניינות בגורלם של תושבי האי. ידוע גם על מספר מכתבים שנשלחו מן המתיישבים בפיטקרן ובין קרובי משפחתם שהיגרו אל האי נורפוק.