השראה תיכונית
08/06/2022
רבים סבורים כי פתרון בעיות מינימום הוא נחלתם הבלעדית של שיעורי מתמטיקה בתיכון. נספר סיפור אמיתי על מקרה שבו צוות בהיי-טק השתמש דווקא בבעיה פשוטה כזאת. כיצד? ומה הקשר ללווייתנים?
הפוסט נכתב בשיתוף צוות תכנון באינטל.
"נזכרתי בבעיה מהתיכון: מבין כל המלבנים בעלי שטח נתון, המלבן שהיקפו קטן ביותר הוא ריבוע!" קריאה זו של עמיתי בצוות התכנון הפתיעה את חברי הצוות בעת שעסקנו בדיון על שיטות מתקדמות לתכנון חומרה. מה הקשר בין הבעיה המתמטית לנושא התכנון?
נסביר בעזרת אנלוגיה פשוטה: קבוצה של 16 פקידים קיבלה משימה – להכפיל מספרים. הם יקבלו שתי רשימות ארוכות של מספרים A ו-B, וימלאו טבלה C כך שבמקום שבשורה ה-i ובעמודה ה-j (מה שנהוג לסמן [C[i,j) יכתבו את ערך המכפלה של האיבר [A[i (המספר שבמקום ה-i ברשימה A) ב-[B[j, כמו בלוח כפל. הפקידים מבצעים את פעולת ההכפלה במהירות הבזק, אולם הנתונים מגיעים מהמחסן באיטיות, באמצעות שליח יחיד, שהולך הלוך ושוב ומביא למשרד נתון אחד בכל דקה, מ-A או מ-B. כיוון שדרושים שני נתונים לחישוב כל תוצאה, הזמן בין פעולות עוקבות של כתיבת תוצאות הוא בערך שתי דקות, ונראה שהפקידים שלנו חסרי-מעש רוב הזמן. אז כיצד ניתן לזרז את התהליך?
אפשר לייעל את העבודה אם השליח המביא למשרד נתון מ-A או מ-B, ימסור אותו לכמה פקידים: נושיב את הפקידים בשורה, ונבקש מהשליח שיביא נתון מ-A, למשל [0]A וימסור אותו לכל אחד מן הפקידים. בדקות הבאות יביא השליח נתונים מ-B עבור 16 הפקידים, נתון בכל דקה ([0]B עד [15]B). כך יוכלו הפקידים לחשב את [0,0]C עד [0,15]C. התהליך יחזור על עצמו שוב ושוב, עם שורות ועמודות שונות, ובממוצע לאורך זמן יכתבו הפקידים 16 תוצאות בכל 17 דקות, כלומר הזמן בין פעולות כתיבה יתקצר ל- 17/16 דקות. האם אפשר לזרז עוד?
עתה נושיב את הפקידים בשתי שורות, שמונה בכל שורה, ונבקש מהשליח המגיע מהמחסן למסור נתון מ-A, למשל [0]A, לשמונת הפקידים שבשורה הראשונה, ודקה אחרי כן את [1]A לשמונת הפקידים שבשורה השנייה. לאחר מכן ימסור השליח את [0]B לפקיד הראשון בשורה הראשונה ולראשון בשורה השנייה, את [1]B לפקיד השני בכל שורה, וכן הלאה, במשך 8 דקות, עד למסירת [7]B (ראו איור). בשיטת הצלבה זו מייצרים 16 תוצאות ב-10 דקות, והזמן הממוצע בין שתי פעולות כתיבה מתקצר ל-10/16 דקה. האם אפשר לשפר את קצב החישובים עוד יותר?
ואז זינק עמיתנו ממקומו והזכיר שמבין כל המלבנים בעלי שטח נתון, המלבן שהיקפו קטן ביותר הוא ריבוע. כדי להסביר את ההקשר, נניח שכל שולחן של פקיד הוא ריבוע בגודל מטר על מטר. נסדר את השולחנות האלו בצורת מלבן כלשהו ששטחו 16 מ"ר, ונורה לשליח לעבור לעבור בין השולחנות ולמסור נתונים לפקידים, כמו בתיאור לעיל.
בדוגמה הראשונה גודל המלבן הוא 1 מטר * 16 מטר, ועל השליח להביא נתון אחד מ-A ו-16 נתונים מ-B, ובסך הכול 17=1+16 משלוחים כדי לקבל 16 תוצאות. 17 הוא גם מחצית ההיקף של המלבן. במקרה השני, בסידור של 2*8, היינו זקוקים ל- 10=2+8 משלוחים כדי לקבל 16 תוצאות, ושוב מספר המשלוחים תואם למחצית ההיקף. כיוון שאנו רוצים להגדיל את מספר החישובים ולהקטין את מספר המפגשים עם השליח, נסדר את השולחנות בצורה אופטימלית, כלומר ריבוע 4*4. בסידור כזה יביא השליח ארבעה משלוחים מ-A וארבעה מ-B כדי לקבל 16 תוצאות, סדרת פעולות שתארך שמונה דקות בלבד, וכך הזמן הממוצע בין שתי פעולות כתיבה יתקצר לכדי 8/16, כלומר חצי דקה. נהדר!
פתרון בעיה זו עורר נוסטלגיה וגם סקרנות. כאמור, הזמן בין פעולות כתיבה עוקבות פרופורציוני ליחס בין ההיקף לשטח המלבן שיצרנו. המתמטיקאים דנו רבות על היחס בין היקף לשטח של צורות שונות, והוכיחו שמבין כל המצולעים בעלי N צלעות המצולעים המשוכללים הם בעלי היחס הקטן ביותר, והמעגל הוא הצורה בעלת היחס המינימלי [1].
לעיתים נמצא שימוש בתכונה זו של הריבוע גם בחיי היום-יום: נניח שאתם עומדים לשכור דירת חדר ששטחה 16 מ"ר, ויכולים לבחור בין דירה שממדיה 4 מטר * 4 מטר לבין דירה של 1 מטר * 16 מטר. איזו עדיפה? אם עליכם לצבוע את הקירות, מחיר הצביעה של דירה 1*16 יהיה גבוה פי 17/8 בהשוואה לדירה בגודל 4*4 (יחס ההיקפים). גם אפקט הקירור של המזגן יהיה יעיל יותר בדירה בגודל 4*4, כי שטח המגע עם הסביבה קטן יותר. ובינינו, דירה בגודל 1*16 גם לא כל כך נוחה.
לאחר שמצאנו את הסידור האופטימלי של הפקידים, נראה שנתקענו: אי אפשר לקצר עוד את הזמן הדרוש לחישובים, עקב מגבלת הביצועים של השליח. אולם מחישוב דומה למדנו שאם נעסיק מספר פקידים גדול יותר, למשל 64, ונושיב גם אותם באופן אופטימלי, כלומר בריבוע של 8*8, אזי הזמן הממוצע בין פעולות כתיבה יתקצר מחצי דקה לרבע דקה.
ההרחבה של הנושא לתלת-ממד, היחס בין שטח פנים לנפח, היא נושא חשוב בתכנון הנדסי, וגם במדע – למשל בביולוגיה [2]. כאשר הנפח של גוף גדל, היחס בין שטח הפנים לנפח קטן, כלומר תוֹך הגוף נהייה דומיננטי יותר. תכונה זו עזרה לנו בבעיה הדו-ממדית: כשעברנו מסידור של ריבוע 4*4 ל-8*8 עם 64 פקידים, גילינו שהיחס בין ההיקף לשטח הריבוע, שמייצג גם את הזמן בין יצירת תוצאות, קטן פי שניים. תכונה זו מסבירה נושאים רבים בביולוגיה, לדוגמה הנפח העצום של לווייתן, שמאפשר לו לשמור על חום גופו גם במים הקפואים של האוקיינוסים. לעומת זאת, הריאות בנויות מהרבה נאדיות זעירות, שתפקידן לספוג את מולקולות החמצן מן האוויר, ושטח הפנים הגדול שלהן, יחסית לנפחן הקטן, מייעל את קליטת החמצן.
נחזור לסיפור על 16 הפקידים שמבצעים חישובים רבים. הם מייצגים באנלוגיה אלמנטים של חומרה, למשל מאיצים להכפלת מטריצות, והשליח מייצג את התעבורה מהזיכרון. כיצד יכול השליח לחסוך חלק מהנסיעות? הרעיון: הוא ישמור חלק מהנתונים שכבר הביא בעבר במחסן זמני קטן ליד שולחנות החישוב, מה שקרוי בהנדסה "זיכרון מטמון". כאשר הנתון הדרוש לחישוב נמצא, הנסיעה נחסכת. עד כמה זה יכול לעזור אם ניתן לשמור רק ארבעה נתונים ? ומה לגבי מקרה של שמונה נתונים? ויותר? בעיה זו, שלקוחה מהשטח, מזמינה לפתור פאזלים מתמטיים נחמדים רבים, שמהנדסים חובבי מתמטיקה מתענגים עליהם.
אכן, יש שלל חידות מתמטיות נחמדות בתכנון הנדסי. נשמח להביא דוגמאות נוספות, וגם לקבל רעיונות מהשטח.
עריכה: סמדר רבן
הרחבות:
[1] יחס היקף לשטח
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
