עכשיו זה מדעי: שום דבר אינו מושלם

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

מגזין “המכון”

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

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

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

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

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

https://www.hayadan.org.il/BuildaGate4/general2/data_card.php?Cat=~~~457044752~~~174&SiteName=hayadan