פרויקטי גמר - הנדסת מחשבים - רשתות וחישוב תש"פ

101 Non-uniform multi-coverage in Client-Server Networks

כיסוי מרובה לא אחיד ברשתות לקוח-שרת

שם המנחה: דר' דרור רביץ

אחראי אקדמי: דר' דרור רביץ 

תיאור הפרויקט:

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

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

  1. לקוח מקבל משאבים רק משרתים שנמצאים בתת הקבוצה שלו,
  2. סך הדרישות שמשוייכות לשרת לא עולה על הקיבול שלו.

מותר ללקוח לקבל שירות מכמה שרתים.

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

תכולת בפרויקט:

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

דרישות:

  • מבני נתונים ואלגוריתמים 2 (83224)
  • אוטומטים וחישוביות (83250)
  • גיאומטריה חישובית (83655)
  • תורת הגרפים ושימושיה (83652)

מקורות:

  1. D. B. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming 62:461-474, 1993.
  2. C. Chekuri and S. Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing 35(3):713-728, 2006.
  3. D. Amzallag, R. Bar-Yehuda, D. Raz, G. Scalosub. Cell selection in 4G cellular networks. IEEE Transactions on Mobile Computing 12(7): 1443-1455, 2013.
  4. O. Gurewitz, Y. Sandomirsky, and G. Scalosub. Cellular Multi-Coverage with Non-uniform Rates. 33rd INFOCOM, 1330-1338, 2014.


           

102 2-Party computation resilient to an unknown amount of errors

חישוב מבוזר (2 מחשבים) עמיד לכמות לא ידועה מראש של שגיאות

שם המנחה: דר' רן גלס

אחראי אקדמי: דר' רן גלס 

הרקע לפרויקט:

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

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

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

מטרת הפרויקט:

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

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

תכולת בפרויקט:

שלבי הפרויקט יכילו:

  1. לימוד רקע תיאורטי על קידוד פרוטוקולים אינטראקטיביים
  2. מימוש בתוכנה של סכמת קידוד תקשורת אינטראקטיבית מתקדמת
  3. ביצוע סימולציית רעש ומדידת איכות הקידוד המתקבל (הסתברות הצלחה, אורך החישוב כפונקציה של כמות השגיאות, וכו׳)

המימוש יבוצע בשפה עילית כלשהי (C, ג׳אווה, פייתון וכו׳) על גבי מחשב יחיד שידמה את שני המחשבים המתקשרים ואת ערוץ התקשורת ביניהם.

דרישות:

  • מבוא לתורת הצפינה (נדרש במקביל)
  • נושאים מתקדמים בפרוטוקולים אינטראקטיביים (לא חובה אבל יתרון)

מקורות:

  1. Varsha Dani, Thomas P. Hayes, Mahnush Movahedi, Jared Saia, Maxwell Young. (2018) “Interactive communication with unknown noise rate”. Inf. Comput. 261(Part): 464-486 https://doi.org/10.1016/j.ic.2018.02.018
  2. Ran Gelles, Siddharth Iyer. (2018) “Interactive coding resilient to an unknown number of erasures”. https://arxiv.org/abs/1811.02527 
  3. R. Gelles. (2017) “Coding for Interactive Communication: A Survey.” Foundations and Trends in Theoretical Computer Science, .http://www.eng.biu.ac.il/~gellesr/survey.pdf 
     

103 Web-based system for learning assembly language. Part I: The Backend

מערכת web ללימוד תכנות בשפת סף. חלק א: Backend

שם המנחה: דר' רן גלס

אחראי אקדמי: דר' רן גלס 

 

הרקע לפרויקט:

יכולת תכנות הפכה לאחת המיומנות הנדרשות ביותר במאה ה-21. אנשים רבים ברחבי העולם (לרבות העולם השלישי) מבקשים ללמוד יכולת זו ולהשתלב בפיתוח תוכנה ובתעשייה העילית (ההי-טק). כמענה לצורך זה, גופים רבים מקימים אתרי web חופשיים ללימוד יכולות תכנות, דוגמת code-academy, edX, Udacity, Coursera וכיו״ב. אתרים אלו מציעים קורסי לימוד מקוונים עבור שפות תכנות עילית כגון פייתון , C או ג׳אווה.

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

מטרת הפרויקט:

בפרויקט זה נבנה אתר דוגמת HackerRank (ראו מקור [1]) שיציע לימוד תכנות בשפת סף ו-Embedded.

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

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

תכולת בפרויקט:

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

כזכור, המשתמש במערכת (שאינו מנוסה בכתיבת קוד) כותב את קוד שפת הסף שהמערכת בודקת. על כן המערכת נדרשת להתמודד עם קוד שגוי, קוד לא תקין (לא מתקמפל), קוד ש״נתקע״, וקוד זדוני. מערכת הבדיקה נדרשת להריץ את הקוד ב״סביבה בטוחה״ שלא תפגע בפעולה השוטפת של השרת עליה המערכת רצה. ככל הנראה יידרש לבנות אמלוטור מתאים לשפת סף או להשתמש בקוד C של האמולטור DosBOX [2] ולפתח את המערכת מעליו

המימוש יבוצע בשפה עילית כלשהי (C, פייתון וכו׳) מעל שרת מבוסס UNIX או לינוקס.
הפרוייקט הינו פרוייקט תכנותי רחב ומצריך הבנה עמוקה בשפת סף ופעולת מערכות embedded.

שימו לב: לפרויקט יש חלק ב׳ (frontend development) שיבוצע ע״י זוג אחר. הפרויקטים הינם נפרדים באופן עקרוני אבל ניתן גם לשלב פעולה בין הצוותים (במידה ששני הצוותים מתקדמים באותו קצב).

דרישות מוקדמות:

  • מיקרומעבדים ושפת אסמבלר
  • מערכות הפעלה
  • מבנה מחשבים.
  • מתאים במיוחד למסלול סייבר
  • ניסיון תכנות low-level מהווה יתרון.

מקורות:

  1. https://www.hackerrank.com
  2. https://sourceforge.net/projects/dosbox/files/dosbox/
  3. Barry Brey, “Intel Microprocessors”

104 Web-based system for learning assembly language. Part II: The Front-end

מערכת web ללימוד שפת סף. חלק ב: Frontend

שם המנחה: דר' רן גלס

אחראי אקדמי: דר' רן גלס 

הרקע לפרויקט:

יכולת תכנות הפכה לאחת המיומנות הנדרשות ביותר במאה ה-21. אנשים רבים ברחבי העולם (לרבות העולם השלישי) מבקשים ללמוד יכולת זו ולהשתלב בפיתוח תוכנה ובתעשייה העילית (ההי-טק). כמענה לצורך זה, גופים רבים מקימים אתרי web חופשיים ללימוד יכולות תכנות, דוגמת code-academy, edX, Udacity, Coursera וכיו״ב. אתרים אלו מציעים קורסי לימוד מקוונים עבור שפות תכנות עילית כגון פייתון , C או ג׳אווה.

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

מטרת הפרויקט:

בפרויקט זה נבנה אתר דוגמת HackerRank (ראו מקור [1]) שיציע לימוד תכנות בשפת סף ו-Embedded.

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

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

תכולת בפרויקט:

בחלק ב׳ של הפרויקט יבנה ה-frontend של המערכת: הסטודנטים יידרשו

  • לפתח אתר אינטרנט מבוסס WEB
  • ללימוד שפת סף.

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

  1. רישום ומעקב אחרי התקדמות של כל משתמש; אימות משתמשים בOAuth2
  2. הצגת תרגילים לפי נושאים שונים – לכל תרגיל עמוד מידע המסביר רקע; עמוד עם שאלת התרגיל, ורכיב שמסוגל לקבל קלט ולהעביר למערכת הבדיקה את הנתונים, לקבל ולשמור ציון לכל תרגיל
  3. הצגת ״טבלת הובלה״ (leader board). 

צוות הפרויקט יידרש לבצע גם:

  1. הגדרת תרגילים בנושאים שונים בשפת סף (בתאום עם יכולות מערכת הבדיקה).

הפרויקט הינו פרויקט תכנותי רחב ומצריך הבנה טובה של (או יכולת למידה של) פיתוח מערכות WEB.

המימוש יבוצע ב-HTML5/CSS ועשוי לדרוש שימוש בJavascript ו-SQL (לחלופין, Python/Django או כלים אחרים).

הפרויקט יתמקד בפיתוח ה-frontend אבל יכיל גם חלקים של ה-backend מבחינת ניהול האתר והמשתמשים.

שימו לב:

לפרויקט יש חלק א׳ (backend development) שיבוצע ע״י זוג אחר – פיתוח מערכת הבדיקה עצמה. הפרויקטים הינם נפרדים באופן עקרוני אבל ניתן גם לשלב פעולה בין הצוותים (במידה ששני הצוותים מתקדמים באותו קצב). הפרויקט הנוכחי יהיה אחראי על המנשק (Interface) שבין הfrontend ל-backend.

דרישות מוקדמות:

קורסים נדרשים:

  • תכנות מונחה עצמים.
  • הנדסת תוכנה.
  • רשתות מחשבים 1
  • ניסיון תכנות low-level מהווה יתרון.
  • קורס פיתוח לווב יתרון 

מקורות:

  1. https://www.hackerrank.com
  2. HTML & CSS : design and build websites / Jon Duckett
  3. https://www.djangoproject.com
  4. https://oauth.net/2/

106  Formal Verification of Neural Networks and Deep Learning

אימות פורמלי של רשתות נוירונים ולמידה עמוקה

שם המנחה: דר' הלל קוגלר

אחראי אקדמי: דר' הלל קוגלר

הרקע לפרויקט:

אימות פורמלי (Formal Verification) מאפשר שימוש באלגוריתמים ושיטות מתמטיות להוכחת נכונות של מערכות תוכנה וחומרה מורכבות. אחד האתגרים המרכזיים הנוכחיים הוא לתאר פתרונות שהתקבלו בשיטות של Deep Learning ולהוכיח שהם אכן עומדים בדרישות. החשיבות של הוכחת נכונות של מערכת נוירונים נעשית משמעותית לאור ההתקדמות הדרמטית בשיטות ללמוד רשתות אך המגבלות הקיימות בהבנת ההתנהגות של הרשת שנלמדה.

מטרת הפרויקט:

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

תכולת בפרויקט:

פיתוח אלגוריתמים שמאפשרים לתאר ולאפיין התנהגות דינמית של רשתות נוירונים ולנתח את התנהגות הרשת.

דרישות:

  • 83691 Formal Verification and Synthesis (במקביל לפרויקט)
  • חשיבה אלגוריתמית, יכולת תכנות גבוהה.

מקורות:

  1. Ian Goodfellow, Yoshua Bengio and Aaron Courville. Deep Learning. MIT Press, 2016.
  2. G. Katz, C. Barrett, D. Dill, K. Julian and M. Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks.Proc. 29th Int. Conf. on Computer Aided Verification (CAV). Heidelberg, Germany, July 2017. To appear.
  3. Manna, Zohar, and Amir Pnueli. "Temporal verification of reactive systems: safety." Springer (1995).

107  Scalable Synthesis from Temporal Logic Specifications

אלגוריתמים לסינתזה מאפיון דרישות בלוגיקת הזמן

שם המנחה: דר' הלל קוגלר

אחראי אקדמי: דר' הלל קוגלר

הרקע לפרויקט:

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

מטרת הפרויקט:

מטרת הפרויקט להבין ולפתח אלגוריתמים לסינתזה מאפיון בלוגיקת הזמן (temporal logic)

תכולת בפרויקט:

במהלך הפרויקט הסטודנטים ירכשו ידע בשיטות אימות פורמלי וסינתזה (Formal Verification and Synthesis) וייפתחו ויבדקו אלגוריתמים לפתרון יעיל ככל הניתן לבעיית הסינתזה מ Temporal Logic .

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

דרישות:

  • 83691 Formal Verification and Synthesis (במקביל לפרויקט)

מקורות:

  1. Manna, Zohar, and Amir Pnueli. "Temporal verification of reactive systems: safety." Springer (1995).
  2. A. Pnueli and R. Rosner "On the synthesis of a reactive module". POPL '89 Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, Pages 179-190, 1989.
  3. S. Jacobs et al. "The 4th Reactive Synthesis Competition (SYNTCOMP 2017): Benchmarks, Participants & Results." (2017): 116-143.

108  Computational inference of network motifs in partially known networks

שיטות חישוביות למציאת מוטיבים ברשתות

שם המנחה: דר' הלל קוגלר

אחראי אקדמי: דר' הלל קוגלר

הרקע לפרויקט:

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

מטרת הפרויקט:

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

תכולת בפרויקט:

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

דרישות:

  • 83691 Formal Verification and Synthesis (במקביל לפרויקט)
  • 83670 Biological Computation (במקביל לפרויקט)

מקורות:

  1. Hillel Kugler, Sara-Jane Dunn, Boyan Yordanov. Formal Analysis of Network Motifs, CMSB'18.
     
  2. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Networkmotifs: simple building blocks of complex networks. Science, 2002.

109 Modeling and verification of complex systems using process calculus

מידול ואימות מערכות מורכבות בשיטות של אלגברה של תהליכים

שם המנחה: דר' הלל קוגלר

אחראי אקדמי: דר' הלל קוגלר

הרקע לפרויקט:

שיטות של אלגברה של תהליכים (Process Calculus) מאפשרות תיאור וניתוח של מערכות מקביליות מורכבות על בסיס מתמטי מדויק, המאפשר ניתוח ואימות של התנהגות המערכת בשיטות אלגוריתמיות.

בפרויקט נשתמש באלגברה של תהליכים[1] שפותחה לאחרונה Beacon Calculus המאפשרת לתהליכים מקביליים לתקשר באמצעות Beacons וכך לבנות מודלים קומפקטיים לתיאור מערכות מקביליות.

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

מטרת הפרויקט:

מטרת הפרויקט היא לבנות מודלים ביולוגיים [2,3] באמצעות Beacon Calculus ולהבין את ההתנהגות של המודלים באמצעות ויזואליזציה, סימולציה ואימות פורמלי.

תכולת הפרויקט:

במהלך הפרויקט הסטודנטים ילמדו את הרקע התאורטי ל Beacon Calculus וכן ירכשו ידע באימות פורמלי [4] (Formal Verification) ויישמו אותו באמצעות פיתוח אלגוריתמים שמאפשרים לתאר ולאפיין התנהגות דינמית של מודלים המתוארים ב Beacon Calculus .

משימות:

  • לימוד רקע תאורטי של Beacon Calculus ו Formal verification.
  • בניית מודלים ביולוגיים פשוטים ופיתוח ממשק גרפי המאפשר לראות בצורה אפקטיבית את התנהגותהמערכת.
  • שימוש בשיטות של אימות פורמלי והתאמתן לניתוח התנהגות המערכות.

קורסי קדם:

  • 83691 Formal Verification and Synthesis (במקביל לפרויקט)
  • 83670 Biological Computation (במקביל לפרויקט)

מקורות:

  1. Michael A. Boemo, Luca Cardelli, Conrad A. Nieduszynski The Beacon Calculus: A formal method for the flexible and concise modelling of biological systems, 2019.
  2. Yaki Setty, Diana Dalfó, Dorota Z. Korta, E. Jane Albert Hubbard, Hillel Kugler. A model of stem cell population dynamics: in silico analysis and in vivo validation. Development, 2012.
  3. Kathryn Atwell, Zhao Qin, David Gavaghan, Hillel Kugler, E. Jane Albert Hubbard, James M. Osborne. Mechano-logical model of C. elegans germ line suggests feedback on the cell cycle. Development, 2015.
  4. Manna, Zohar, and Amir Pnueli. "Temporal verification of reactive systems: safety." Springer (1995).

פרויקטים נוספים מומלצים

801  Data Fusion of strings and applications to movies & scripts

היתוך מידע של מחרוזות ושימושיו בסרטים

שם המנחה: פרופ' צביקה לוטקר וד"ר רן גלס

אחראי אקדמי: פרופ' צביקה לוטקר

הרקע לפרויקט:

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

מטרת הפרויקט:

לפתח אלגוריתמים של היתוך מידע שתפקידם לאחד בסיסי נתונים של מחרוזות

תכולת בפרויקט:

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

דרישות:

  • אלגוריתמים 1

מקורות:

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS 2018: 979-990

802  Differentially Private Clustering Algorithms

אלגוריתמי קלאסטרינג פרטיים

שם המנחה: Or Sheffet

אחראי אקדמי: Or Sheffet

הרקע לפרויקט:

Differential privacy has been established in recent years as the "de-facto" gold standard of privacy preserving data analysis. In this project the students are expected to read, understand, implement and test a differentially private algorithm for locating a cluster / multiple clusters in a given dataset of points in the Euclidean space.

מטרת הפרויקט:

This project is centered around the problem of private data clustering. The students are expected to implement randomized algorithms that deal with clustering, including: noisy counting, above-threshold, locally-sensitive hashing, and randomly chosen axes.

Furthermore, the students are expected to test and compare the performance of said algorithms over multiple datasets.

Academically, the goal of the project is to have the students acquainted with differential privacy (DP) and the high-level ideas of differential privacy, as well as the technical difficulties that arise from the promise of DP.

Practically, the goal is to publish the project's code online, available for researchers world-wide.

תכולת בפרויקט:

The project's main focus is on understanding and implementing a scientific paper in differential privacy.

The project is based on 3 stages:

  1. reading and understanding existing work,
  2. implementation of algorithms in code and
  3. testing empirical performance over synthetic / real-life data.

The main focus of the project is the 1-cluster algorithm of Nissim and Stemmer, composed of multiple building blocks.

The students are required to implement each of these subroutines and then wrap it all together in an algorithm of bounded privacy lose (i.e. a (\epsilon,\delta)-DP algorithm).

דרישות:

  • Advanced algorithms
  • Probability / statistics --- a significant component of the course is centered on randomized algorithms
  • Differential privacy as a co-requisite.

מקורות:

803  Differentially Private Linear Regression

רגרסיה ליניארית פרטית

שם המנחה: Or Sheffet

אחראי אקדמי: Or Sheffet

הרקע לפרויקט:

Differential privacy has been established in recent years as the "de-facto" gold standard of privacy preserving data analysis. In this project the students are expected to read, understand, implement and test a suite of differentially private algorithms for the classic problem of linear regression, and test performance under the classical Ordinary Least Squares (OLS) model.

מטרת הפרויקט:

This project is centered around the problem of private linear regression. The students are expected to implement randomized algorithms that deal with a single and multiple regressions. Furthermore, the students are expected to test and compare the performance of said algorithms over multiple datasets.

Academically, the goal of the project is to have the students acquainted with differential privacy (DP) and the high-level ideas of differential privacy, as well as the technical difficulties that arise from the promise of DP. Practically, the goal is to publish the project's code online, available for researchers world-wide.

תכולת בפרויקט:

The project's main focus is on understanding and implementing a scientific paper in differential privacy.

The project is based on 3 stages:

  1. reading and understanding existing work
  2. implementation of algorithms in code
  3. testing empirical performance over synthetic / real-life data.

The project is centered around implementation of multiple different algorithms for linear regression: output perturbation, input perturbation, stochastic gradient descent, Analyze Gauss and the Johnson-Lindenstrauss transform.

דרישות:

  • Advanced algorithms
  • Probability / statistics --- a significant component of the course is centered on randomized algorithms
  • Differential privacy as a co-requisite.

מקורות:

804  Parallel Computation of Distance Maps

חישוב מקבילי של מפות מרחקים

שם המנחה: פרופ' אופיר וובר

אחראי אקדמי: פרופ' אופיר וובר

הרקע לפרויקט:

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

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

מטרת הפרויקט:

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

תכולת בפרויקט:

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

דרישות:

  • עיבוד דיגיטלי של גיאומטריה (83-656). ניתן לקחת במקביל.
  • מומלץ (לא חובה) - חישוב מקבילי ב-GPU (83-920). ניתן לקחת במקביל.
  • מומלץ (לא חובה) - אופטימיזציה והבנה של צורות (83-641). ניתן לקחת במקביל.
  • יכולת תכנות טובה.
  • יכולת עבודה עצמאית והגדלת ראש.

מקורות:

http://www.eng.biu.ac.il/~weberof/Publications/PMM/SIGGRAPH08.zip

805 Geometric Deep Learning

למידה גיאומטרית עמוקה

שם המנחה: פרופ' אופיר וובר
אחראי/ת אקדמי/ת: פרופ' אופיר וובר

הרקע לפרויקט:

בעשור האחרון חלה התפתחות מרעישה בתחום של לימדת מכונה ובעיקר זו המבוססת על רשתות נוירונים בעלות מספר רב של שכבות. בולטות במיוחד הן ארכיטקטורות המבוססות על רשתות קונבולוציה (Convolutional Neural Network) שהתפתחו יד ביד עם התפתחות חומרה גרפית מקבילית (GPU) המאפשרת עיבוד וחישוב מסיבי בזמן יחסית קצר. אלה הביאו לפריצות דרך משמעותיות בתחומים כמו ראייה ממוחשבת על ידי בניית אלגוריתמי סיווג והבנה סמנטית של תמונות.

הפרויקט יעסוק במימוש אלגוריתמי למידה אשר פותחו בשנה האחרונה ומאפשרים יישום של טכנולוגיות כמו Convolutional Neural Network. הייחוד של הפרויקט הוא בכך שהלמידה תתבצע על אובייקטים גאומטריים ולא על תמונות או אותות קול כפי המקובל בראייה ממוחשבת קלאסית ועיבוד אותות.

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

מטרת הפרויקט:

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

תכולת הפרויקט:

הפרויקט ידרוש מימוש של אלגוריתם מורכב בתוכנה ולו כמה שלבים.

ראשית, המודלים התלת מימדיים ימופו לתחום שטוח תוך שימוש בשיטות גאומטריות מתקדמות תוך שימוש בחבילות תוכנה גרפיות וחישוביות מסחריות (כמו למשל Matlab, Autodesk Maya, CGAL).

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

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

בתום תהליך הלמידה והאימון, המודל יופעל על צורות חדשות.

קורסי קדם:

• עיבוד דיגיטלי של גיאומטריה (83-656). ניתן לקחת במקביל.
• אופטימיזציה והבנה של צורות (83-641). ניתן לקחת במקביל.

דרישות נוספות:

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

מקורות:

http://geometricdeeplearning.com/

806 Metric Parameterization

פרמטריזציה מטרית

שם המנחה: פרופ' אופיר וובר
אחראי/ת אקדמי/ת: פרופ' אופיר וובר

הרקע לפרויקט:

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

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

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

מטרת הפרויקט:

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

תכולת הפרויקט:

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

הפרויקט ידרוש מימוש של אלגוריתם מורכב בתוכנה תוך שימוש בחבילות תוכנה גרפיות וחישוביות מסחריות כמו למשל Matlab, Autodesk Maya, CGAL.

בסיס האלגוריתם מתואר במאמר 2) ברשימת המקורות. בפרויקט נשנה את האלגוריתם באופן שיוביל למימוש יעיל יותר מזה המוצע במאמר ע"י מימוש אופטימיזציה בטכניקת Sequential Quadratic Programming.

קורסי קדם:

  • חובה - עיבוד דיגיטלי של גיאומטריה (83-656).
  • מומלץ (לא חובה) - אופטימיזציה והבנה של צורות (83-641).
  • מומלץ (לא חובה) - עיבוד דיגיטלי של גיאומטריה 2 (83-633).

          דרישות נוספות:

  • תכנות Matlab ו C++.
  • יכולת עבודה עצמאית והגדלת ראש.

מקורות:

  1. Polygon mesh processing (book). Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., & Lévy, B. (2010). CRC press.
  2. http://www.eng.biu.ac.il/~weberof/Publications/Metric-Param/Bounded_Distortion_Parametrization_in_the_Space_of_Metrics.pdf

208 Solving matchbox riddles using formal verification

פתרון חידות גפרורים בשיטות אימות פורמלי

שם המנחה: דר' הלל קוגלר
אחראי/ת אקדמי/ת: דר' הלל קוגלר

הרקע לפרויקט:

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

מטרת הפרויקט:

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

תכולת הפרויקט:

לימוד רקע תאורטי ושימוש בכלים של אימות פורמלי.

פיתוח ממשק גרפי להצגה של החידות ודרכי הפתרון.

פיתוח וממוש של שיטות של פתרון אלגוריתמי לחידות.

קורסי קדם:

83691 Formal Verification and Synthesis (במקביל לפרויקט)

מקורות:

  1. Manna, Zohar, and Amir Pnueli. "Temporal verification of reactive systems: safety." Springer (1995).
  2. Federico Chesani, Paola Mello, Michela Milano. Solving Mathematical Puzzles: A Challenging Competition for AI. Association for the Advancement of Artificial Intelligence, 2017.
  3. http://matchstickpuzzles.blogspot.co.il/

614 A web-based tool for cancer meta-analysis

ממשק מבוסס רשת לניתוח נתונים גנומיים מגידולים סרטניים

שם המנחה: ירון טרינק
אחראי/ת אקדמי/ת: ד"ר תומר קליסקי

הרקע לפרויקט:

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

מטרת הפרויקט:

בניית יישום רשת (web application) מבוסס python או R להצגת נתונים רב מימדיים של ביטוי גנים ממאות ואלפי גידולים סרטניים הטלה למרחב דו\תלת מימדי בשיטות PCA ו tSNE בהתאם לבחירת המשתמש.

תכולת הפרויקט:

  • בניית יישום רשת (web application) מבוסס python או R להצגת נתונים רב מימדיים של ביטוי גנים ממאות\אלפי גידולים סרטניים.
  • הצגת המידע באמצעות הטלה למרחב דו מימדי בשיטות PCA ו tSNE בהתאם לבחירת המשתמש.
  • סימון תאים המבטאים גן מסויים על פי בחירת המשתמש.
  • ייצור היסטוגרמה של רמות ביטוי של גן מסויים על פי בחירת המשתמש.
  • מתן אפשרות למשתמש להגדיל ולהקטין ולסובב את התמונה.
  • מתן אפשרות למשתמש לסמן קבוצות של תאים לייצר גרף עמודות (bar plot) של ממוצעי רמות ביטוי היסטוגרמות של שלהם עבור גנים נבחרים על פי בחירת המשתמש.
  • ביצוע שאילתות על חתכים שונים של המידע (למשל, בחירת תת קבוצה של תאים והוצאת רשימת הגנים המאפיינים אותה ביחס לשאר) בהתאם לבחירת המשתמש.

קורסי קדם:

קורס בסיסי בתיכנות

דרישות נוספות:

  • ביולוגיה חישובית
  • ביג דאטה
  • גנומיקה

מקורות:

  1. Plotly R Open Source Graphing Library
  2. The Jupyter Notebook
  3. t-SNE
  4. Trink A, Kanter I, Pode-Shakked N, Urbach A, Dekel B, Kalisky T. Geometry of Gene Expression Space of Wilms’ Tumors From Human Patients. Neoplasia. Elsevier; 2018;20: 871–881. doi:10.1016/j.neo.2018.06.006