המהנדס ג'ון קוסטס היה אחראי על מערכות הסונאר של צי ארה"ב. בעיה חמורה שגילה בתפקודה של מערכת הסונאר חייבה אותו למצוא לה פתרון, והפתרון הזה פתח שדות ידע חדשים במתמטיקה כולה.
מערכת הסונאר שולחת "פינג", כלומר רצף של צלילים בתדרים שונים, ומאזינה להד שחוזר. מדידת הזמן עד לחזרת ההד מספק נתונים על המרחק עד לעצם שבו הפינג פגע. תדר ההד החוזר מספק נתונים גם על כיוון ההתקדמות של העצם ועל מהירותו. אולם כדי שיהיה ניתן לפענח באופן תקין את ההד החוזר היה צורך למצוא דרך ליצור רצפי תדרים שיהיו נטולי דפוס חוזר במידת האפשר. כאן נכנסה המתמטיקה לתמונה.
בסרט שלפניכם מציג סקוט ריקרד את סיפורם של ג'ון קוסטס והמתמטיקאי סולומון גולומב שנחלץ לעזרתו בעזרת רעיונותיו של המתמטיקאי הצרפתי בן המאה ה-19 אווריסט גלואה. הוא ניצל את הדפוסים נטולי החזרות שהם מצאו ליצירת המוזיקה המכוערת ביותר בעולם.
צפייה והאזנה מהנות! תוכלו לבחור בכתוביות בעברית ע"י בחירת CC ו-Hebrew אחרי הפעלת הסרט.
הסרטון תורגם בידי יפעת בן יעקב מצוות דוידסון און-ליין. ההרצאה שבסרטון הוצגה על ידי סקוט ריקרד במסגרת פרויקט TEDx talks.
כעת נסקור על קצה המזלג את תגליותיהם של קוסטס וגולומב.
סרגל גולומב
סרגל גולומב עם n שנתות הוא קבוצה של n מספרים שלמים לא שליליים {a1, a2, ... an}, כך שכל ההפרשים החיוביים בין כל הזוגות האפשריים של אברי הקבוצה i,j=1,....,n, i<>j) |ai - aj|) שונים זה מזה.
לדוגמה, הקבוצה {0,1,3,7} היא סרגל גולומב בעל ארבע שנתות הנראה כך:
|
|
|
|
7 3 1 0
המספרים הם השנתות המסומנות על גבי הסרגל.
ההפרשים בין זוגות המספרים הם:
1-0=1
3-0=3
7-0=7
3-1=2
7-1=6
7-3=4
אפשר לראות שכל ההפרשים שונים זה מזה, ולכן הסרגל הוא סרגל גולומב.
במוזיקה שהופיעה בסרטון נעשה שימוש בסרגל גולומב כדי לקבוע את אורך הצלילים באופן שיתרום לכיעורה של היצירה.
מערך קוסטס
בגלל מגבלות פיסיקליות, קוסטס התעניין בפינגים העונים על הדרישות הבאות:
1. מספר התדרים שווה למספר פרקי הזמן.
2. כל תדר משודר פעם אחת בדיוק.
3. בכל זמן נתון משודר תדר אחד בלבד.
כדי לייצג את התדרים המשודרים השתמש קוסטס במערך בגודל n*n, כאשר n הוא מספר פרקי הזמן הזהה למספר התדרים המשודרים. עמודות המערך מייצגות את זמני השידור. בכל עמודה מסומן 1 בשורה המתאימה לתדר שישודר באותו זמן.
כדי לפתור את בעיית הסונאר חיפש קוסטס דפוסי שידור שלא יהיו תואמים לעצמם בהפרשי זמן שונים. הוא הצליח לעשות זאת באופן ידני רק עד לדפוסים באורך של 12, וכאן נחלץ סולומון לעזרתו. אחת הדרכים לנסח את הבעיה היא זו:
ניקח מערך ריק בגודל n*n ונסמן בו '1'ים כך שכל שורה תכיל 1 יחיד וכל עמודה תכיל 1 יחיד.
נוכל לסמן את המערך הזה בצורה (a1,a2,...,an)
כאשר כל ai מסמן את מספר השורה שבה מופיע 1 בעמודה i.
כעת נבנה משולש הפרשים:
בשורה הראשונה במשולש יופיעו ההפרשים בין כל איבר לאיבר שלפניו, כלומר ההבדלים בין התדרים המשודרים בהפרש זמן של פרק זמן 1.
בשורה השנייה של המשולש יופיעו ההפרשים בין כל איבר לאיבר שנמצא לפניו בהפרש של שני מקומות, כלומר ההבדלים בין התדרים המשודרים בהפרש של שני פרקי זמן.
בשורה השלישית של המשולש יופיעו ההפרשים בין כל איבר לאיבר שנמצא לפניו בהפרש של שלושה מקומות, כלומר ההבדלים בין התדרים המשודרים בהפרש של שלושה פרקי זמן.
בשורה האחרונה יופיע ההפרש בין האיבר האחרון לאיבר הראשון.
מערך יהיה מערך קוסטס אם בכל שורה של משולש ההפרשים, ההפרשים המופיעים בה יהיו שונים זה מזה.
אם הפינגים יורכבו מורכבים מסדרת תדרים שיוצרים מערך קוסטס, נוכל לפענח את ההד החוזר מהם באופן הרבה יותר מדויק.
ראו לדוגמה את המערך הבא:
|
|
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
הייצוג המתאים למערך הוא (3,1,6,2,5,4).
נבנה את משולש ההפרשים:
השורה הראשונה: (1-3,6-1,2-6,5-2,4-5) כלומר: (-2, 5,-4, 3,-1)
השורה השניה: (6-3,2-1,5-6,4-2) כלומר: ( 3, 1,-1, 2)
השורה השלישית: (2-3,5-1,4-6) כלומר: (-1, 4,-2)
השורה הרביעית: (5-3,4-1) כלומר: ( 2, 3)
השורה החמישית: (4-3) כלומר: ( 1).
אפשר לראות שבכל שורה אין חזרות על מספרים, ולכן המערך הוא מערך קוסטס.
גולומב ווולץ' מצאו אלגוריתמים לבניית מערכי קוסטס המבוססים על תורת השדות הסופיים של גלואה. האלגוריתמים שלהם יכולים לבנות מערכי קוסטס במספר גדלים אינסופי, אך לא בכל גודל.
בסרטון נבחר המספר הראשוני 89 ומודגמת בניית מערך קוסטס בגודל 88*88 בעזרת חישוב חזקות של 3. אם המספר המתקבל גדול מ-89, מחשבים את השארית המתקבלת בחלוקה שלו ב-89.
1=30 ולכן נסמן 1 בעמודה הראשונה בשורה מס' 1
3=31 ולכן נסמן 1 בעמודה השנייה בשורה מס' 3.
9=32 ולכן נסמן 1 בעמודה השלישית בשורה מס' 9.
27=33 ולכן נסמן 1 בעמודה הרביעית בשורה מס' 27.
81=34 ולכן נסמן 1 בעמודה החמישית בשורה מס' 81.
243=35 ולכן נסמן 1 בעמודה השישית בשורה מס' 243 mod 89=65
וכך הלאה עד שנסמן 1 בכל העמודות.
מדוע נבחרו המספרים 89 ו-3? עבור אלו מספרים עובד האלגוריתם? מדוע המערך שנוצר הוא מערך קוסטס? התשובות לכך טמונות ברעיונות של גלואה שעליהם האלגוריתם. פרטים נוספים תוכלו למצוא בקישור "מערכי קוסטס – סקירה ושאלות פתוחות".
וכך גילו מהנדס ומתמטיקאי, שניסו רק לשפר מערכת סונאר, עולם חדש ומופלא המשמש עד היום כר נרחב למחקר, ומתברר שגם ליצירת מוזיקה.
עד היום נותרו שאלות הנוגעות למערכי קוסטס שלא נמצאה להן תשובה. אחת השאלות הפתוחות היא: האם קיים מערך קוסטס בכל גודל אפשרי? חוקרים הצליחו למצוא מערכי קוסטס בכל גודל עד ל-31*31. אך עדיין לא נמצא מערך קוסטס בגודל 32*32, ואף לא נמצאה תשובה לשאלה אם קיים מערך קוסטס בגודל של 32*32?" השאלה הזו הפכה ל"שאלת הגביע הקדוש" של המחקר העוסק במערכי קוסטס.
יפעת בן יעקב
מכון דוידסון לחינוך מדעי
מכון ויצמן למדע
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום ואנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
