חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תשע"ה

  תכנון וניתוח אלגוריתמים
  Design and Analysis of Algorithms  
0510-6401-01
הנדסה | ביה"ס להנדסת חשמל
סמ'  ב'1600-1900205 הנדסה כתות חשיעור פרופ רון-גולדרייך דנה
ש"ס:  3.0

סילבוס מקוצר

משקל: 3

 דרישות קדם: מבני נתונים ואלגוריתמים או יעילות של חישובים.
 
לקורס שתי מטרות. האחת היא לחשוף את הסטודנטים למבחר של טכניקות מתקדמות באלגוריתמיקה, והשנייה היא לתת לסטודנטים הזדמנות לחוות את הרוח העכשווית במחקר אלגוריתמי.
נושאי הקורס יבחרו מתוך הרשימה הבאה.
מושגי יסוד: בעיות אופטימיזציה, אלגוריתמי קירוב, סכימות קירוב פולינומיאליות, אלגוריתמים הסתברותיים מסוג Monte-Carlo ו Las-Vegas.
בעיות קירוב בסיסיות: בעיית כיסוי הקדקודים (Vertex Cover),בעיית כיסוי הקבוצות (Set Cover), בעיית הסוכן הנוסע (Traveling Sales Person) , בעיית הסכום החלקי (Subset Sum).
השיטה ההסתברותית ויישומה לקירוב Max-Cut ו Max-Sat.
שיטת העיגול האקראי (Randomized Rounding) ויישומה ל Max-Sat.
דגימה מקרית ויישומה לקירוב מספר ההשמות המספקות נוסחאת DNF, למשפט Occam בלמידה חישובית, ולבדיקת תכונות מקורבת.
בעיות Online.
אלגוריתמים מבוזרים ומקביליים.
 
 
Course description
Credits: 3
Prerequisites: Data Structures and Algorithms
 
This course aims at two targets. One is to get the students acquainted with a selection of advanced techniques in algorithmic theory, and the other is to let the students experience what is the spirit in contemporary algorithmic research. Namely, what problems are considered interesting, and how to evaluate possible solutions
 
The course will include topics from the following list: (1) Approximation background: Decision and optimization problems, NP Hardness, approximation algorithm, approximation scheme. (2) Basic approximation algorithms: load balancing, vertex and set cover, traveling salesman, subset sum, knapsack. (3) Randomized algorithms: the probabilistic method with applications to max-cut and max-SAT; randomized rounding; random sampling. (4) Online problems: ski rentals, self-organizing lists, best-expert and bandit, paging, load balancing, call admission in communication networks. (5) Distributed and parallel computation: models and algorithms. Algorithms include Bellman-Ford, maximal independent set, prefix sums, minimum spanning tree.

להצהרת הנגישות


אוניברסיטת ת