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

שנה"ל תשע"ז

תכנון וניתוח אלגוריתמים
Design and Analysis of Algorithms

0510-6401-01

הנדסה | ביה"ס להנדסת חשמל


סמ' א'	1500-1800	'ג	238	וולפסון - הנדסה	שיעור	פרופ גולדרייך רון דנה

D:\Inetpub\shared\yedion\syllabus\05\2016\0510\0510640101_desc.txt סילבוס מקוצר משקל: 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.

ש"ס: 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.

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