שירי צ'צ'יק

זוכת פרס קריל 2017

ד"ר שירי צ'צ'יק (Shiri Chechik)

אוניברסיטת תל אביב

 

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

 

תיאור עבודת המחקר

 

בעיות הנובעות מרשתות בעולם האמיתי מובילות לחלק ניכר מהמחקר הבסיסי ביותר במדעי המחשב.

 

מחקרי מתרכז בין השאר בשאלות הנובעות מקנה המידה הגדול של הרשת עם דגש מיוחד על סביבות בהן אנו נדרשים לתכנן אלגוריתמים אשר להם מידע חלקי בלבד על הרשת כולה. דוגמאות לכך הן אלגוריתמים דינמיים (כאשר הגרף/הרשת משתנים עם הזמן והשינויים אינם ידועים לנו מראש ובכל זאת אנחנו רוצים לתחזק איזשהו מבנה נתונים או מידע כלשהו על הגרף) ואלגוריתמים מבוזרים (בהן כל צומת ברשת/גרף הוא מעבד עצמאי אשר מודע רק למה שקורה בסביבתו הקרובה ואין לו ידע גלובלי על כל הגרף).

 

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

 

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

 

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

 

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

 

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

 

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

 

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

זוכי פרס קריל

// order posts by year $posts_by_year;