סילבוס

תוכן הקורס ומטרתו

מבני נתונים ואלגוריתמים

Data Structures and Algorithms

משקל: 3.5
דרישות קדם: תכנות פייתון (0509.1820) ומערכות לוגיות ספרתיות (0512.3561)

הקדמה: חיפוש איבר ברשימה ממוינת, חיפוש בינארי. הגדרת סדר הגודל של פונקציה, ניתוח נכונות וזמן ריצה של אלגוריתמים.
בעיית המיון (Sorting): מיון הכנסה (Insertion Sort). מיון מיזוג (Merge Sort). מיון "מהיר" ((Quick Sort . חסם תחתון למיון במודל ההשוואות ומושג עץ ההכרעה (Decision Tree). מיון בזמן ליניארי.
טיפוסי נתונים מופשטים (Abstract Data Types) ומבני נתונים: מחסנית ותור. תור קדימויות וממוש ע"י ערימה (Heap). עצי חיפוש בינאריים ועצי 2-3. ניהול קבוצות זרות.
טכניקות אלגוריתמיות: פרדיגמת "הפרד ומשול" (Divide and Conquer). אלגוריתמים חמדניים (Greedy Algorithms). תכנון דינאמי .(Dynamic Programming)
אלגוריתמים על גרפים: ייצוג גרפים. חיפוש על גרפים. מציאת עץ פורש מינימאלי, זרימה ברשתות.

ספרי לימוד:

Introduction to Algorithms (2nd edition), Corman, Leiserson, Rivest, Stein

או

Introduction to Algorithms (1st edition), Corman, Leiserson, Rivest

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

Data Structures and Algorithms, Aho, Hopcroft, Ullman