Credit points: 3
קורס זה יציג בפני התלמידים אלגוריתמים מתקדמים לגרפים דינמיים. תחוםמחקר פעיל זה עוסק בשאלות מהסגנון הבא: כמה מהר ניתן לפתור בעיותאלגוריתמיות על גרפים המשתנים מעט עם הזמן. בפרט, כמה יותר מהר מאשרחישוב פיתרון מחדש אחרי כל שינוי קטן בגרף. שאלה זו מרכזית עבור בעיותעם קלט המשתנה עם הזמן (למשל, באפליקציות GPS, סגירת ופתיחת כביש משנהמעט את רשת התחבורה), אבל גם מרכזית להאצת אלגוריתמים עם קלט סטטי(באותו אופן שמבני נתונים בסיסיים מאפשרים להאיץ אלגוריתמים קלאסייםאחרים). המטרה של הקורס היא לחשוף סטודנטים לטכניקות ותוצאות לבעיותבסיסיות בתחום (כגון שידוכים, מרחקים קלים ביותר, עצים פורשיםמינימליים, ועוד). כחלק מהקורס, ייחשפו הסטודנטים לכלים מרכזייםבאלגוריתמים ותאוריה של מדעי המחשב הנוגעים בנושא הקורס, כגון תוכניותלינאריות ודואליות, אלגוריתמים רנדומיים ושיטת העדכונים הכפלית. הציוןבקורס מבוסס על תרגילי בית ועבודת סיום.תוצאות למידה: בסיום הקורס הסטודנטיות והסטודנטים יהיו מסוגלים:1. לפתח ולנתח אלגוריתמים יעילים לגרפים דינמיים.2. להאיץ אלגוריתמים סטטיים באמצעות אלגוריתמים דינמיים.3. להוכיח תוצאות קושי לאלגוריתמים דינמיים, תחת השערות נפוצות.
This course will introduce students to advanced algorithms for dynamic graphs. This active research area focuses on questions of the following flavor: “How quickly can we solve algorithmic problems on graphs that change slowly over time? In particular, how much faster than recomputing from scratch after every change in the graph?” This question is central to problems with input that changes over time (for example, in GPS applications, closure and opening of roads changes the road network), but is also key to speeding up algorithms with static inputs (in much the same way that basic data structures can be used to speed up other classic algorithms). The course’s objective is to expose students to techniques and results for basic problems in the field (such as matching, shortest paths, minimum spanning trees, etc). As part of the course, the students will also be exposed to central tools in algorithm design and theory of computer science more broadly that are relevant to the course topic, including linear programming and duality, randomized algorithms and the multiplicative weight update method. The course evaluation will be based on homework and a final project, which includes reading a research paper, summarizing the paper and simplifying it and/or improving on it.
קורס זה יציג בפני התלמידים אלגוריתמים מתקדמים לגרפים דינמיים. תחוםמחקר פעיל זה עוסק בשאלות מהסגנון הבא: כמה מהר ניתן לפתור בעיותאלגוריתמיות על גרפים המשתנים מעט עם הזמן. בפרט, כמה יותר מהר מאשרחישוב פיתרון מחדש אחרי כל שינוי קטן בגרף. שאלה זו מרכזית עבור בעיותעם קלט המשתנה עם הזמן (למשל, באפליקציות GPS, סגירת ופתיחת כביש משנהמעט את רשת התחבורה), אבל גם מרכזית להאצת אלגוריתמים עם קלט סטטי(באותו אופן שמבני נתונים בסיסיים מאפשרים להאיץ אלגוריתמים קלאסייםאחרים). המטרה של הקורס היא לחשוף סטודנטים לטכניקות ותוצאות לבעיותבסיסיות בתחום (כגון שידוכים, מרחקים קלים ביותר, עצים פורשיםמינימליים, ועוד). כחלק מהקורס, ייחשפו הסטודנטים לכלים מרכזייםבאלגוריתמים ותאוריה של מדעי המחשב הנוגעים בנושא הקורס, כגון תוכניותלינאריות ודואליות, אלגוריתמים רנדומיים ושיטת העדכונים הכפלית. הציוןבקורס מבוסס על תרגילי בית ועבודת סיום.תוצאות למידה: בסיום הקורס הסטודנטיות והסטודנטים יהיו מסוגלים:1. לפתח ולנתח אלגוריתמים יעילים לגרפים דינמיים.2. להאיץ אלגוריתמים סטטיים באמצעות אלגוריתמים דינמיים.3. להוכיח תוצאות קושי לאלגוריתמים דינמיים, תחת השערות נפוצות.
This course will introduce students to advanced algorithms for dynamic graphs. This active research area focuses on questions of the following flavor: “How quickly can we solve algorithmic problems on graphs that change slowly over time? In particular, how much faster than recomputing from scratch after every change in the graph?” This question is central to problems with input that changes over time (for example, in GPS applications, closure and opening of roads changes the road network), but is also key to speeding up algorithms with static inputs (in much the same way that basic data structures can be used to speed up other classic algorithms). The course’s objective is to expose students to techniques and results for basic problems in the field (such as matching, shortest paths, minimum spanning trees, etc). As part of the course, the students will also be exposed to central tools in algorithm design and theory of computer science more broadly that are relevant to the course topic, including linear programming and duality, randomized algorithms and the multiplicative weight update method. The course evaluation will be based on homework and a final project, which includes reading a research paper, summarizing the paper and simplifying it and/or improving on it.