Data Structures and Algorithms 1
נושא
קריאה נדרשת
הערות
1
סימונים אסימפטוטיים, סידרי גודל, נוסחאות נסיגה ומשפט המסטר
2
מיונים, מיון מיזוג (הפרד ומשול), חסם תחתון למיון במודל השוואות, מיון מהיר, מיון בזמן לינארי
3
טיפוסי נתונים מופשטים ומבני נתונים בסיסיים: רשימה, תור, מחסנית, תור קדימויות, ערימה, יצוג גרפים
4
אלגוריתמים בסיסיים בגרפים: סריקה לרוחב, סריקה לאורך, מיון טופולוגי
5
עצים: עצי חיפוש, עצי 2-3 ועצי B, עצים מאוזנים (למשל AVL)
6
קוד הופמן, אלגוריתמים חמדניים
7
עץ פורש מינימום: אלגוריתמים Prim ו- Kruskal
8
תכנון דינמי: תת סדרה עולה אופטימלית, כפל מטריצות
9
מרחקים קצרים ביותר. אלגוריתם Dijkstra ואלגוריתם Bellman-Ford
10
קבוצות זרות (Union-Find)
11
מילון, טבלת עירבול (Hashing)
12
זרימה ברשתות: אלגוריתםFord-Fulkerson, Edmonds-Karp
13
SAT, 3-SAT, 2-SAT NP Complete problems
1. פיתוח כלים בסיסים לתכנון וניתוח מבני נתונים ואלגוריתמים.
2. הכרות עם מבני נתונים ואלגוריתמים בסיסיים.
3. מימוש ושימוש מעשי של הנ"ל.
הקורס מהווה קורס ראשון במבני נתונים ואלגוריתמים, ויתמקד בנושאים הבאים:
1. שיטות לניתוח נכונות וזמן ריצה של אלגוריתמים.
2. הכרת טיפוסי נתונים מופשטים ומבני נתונים בסיסיים: רשימה, תור, ומחסנית; תור קדימויות וערימה; עצי חיפוש; פונקציות ערבול; קבוצות זרות.
3. טכניקות לתכנון וניתוח אלגוריתמים: אלגוריתמים חמדניים, תכנון דינמי, אלגוריתמים אקראיים, הפרד ומשול.
4. אלגוריתמים לבעיות בסיסיות ברשתות: ייצוג גרפים, סריקה ורוחב ולעומק, מרחקים קצרים ביותר, זרימה ברשתות.
** ייתכנו שינויים בסילבוס בהתאם לקצב ההתקדמות ואפקטיביות הלמידה
הגשת עבודות בית
83120 מבוא לחישוב והנדסת תוכנה
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C,
Third Edition, The MIT Press, 2009.Introduction to Algorithms
Even, S. Graph Algorithms. Cambridge Univeristy Press.