פורטל הסטודנטים

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

פקולטה: מדעי המחשב
|תואר ראשון |תארים מתקדמים

מקצועות קדם

(46002 - תכן וניתוח אלגוריתמים ו- 104034 - מבוא להסתברות ח') או (94412 - הסתברות מ ו- 234247 - אלגוריתמים 1) או (104034 - מבוא להסתברות ח' ו- 104291 - אלגוריתמים קומבינטוריים)