סילבוס

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

הקורס עוסק בדרכים היסודיות לארגון נתונים במערכת דיגיטלית (מחשב), כך שניתן יהיה לגשת אליהם ביעילות ובמהירות לצורך פתרון בעיות שונות. הקורס מעניק ללומדים הן כלים טכניים-מתמטיים והן מיומנויות חשיבה החיוניים בפתרון בעיות במדעי המחשב.

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

מנושאי הקורס:
שיטות לניתוח סיבוכיות: חסמי סיבוכיות, שיטות לניתוח סיבוכיות של אלגוריתמים רקורסיביים, סיבוכיות amortized.
מבני הנתונים ואלגוריתמים: מערכים ורשימות מקושרות, עצי חיפוש ועצי חיפוש מאוזנים (למשל AVL, עצי B), טבלאות hash, ערמות בינאריות, ערימות בינומיות וערימות פיבונאצ'י, מיון ערימה, מיון מהיר, חסם תחתון לבעית המיון ומיונים שאינם מיוני השוואות, בעית הבחירה ואלגוריתם חציון החציונים, מבנה נתונים לניהול קבוצות זרות (Union-Find). בהתאם לזמן, עצי סיומות.

חלק מנושאי הקורס דורשים רקע בסיסי בהסתברות, בפרט המושגים: משתנה מקרי, תוחלת, התפלגות (אחידה, גאומטרית). כמו כן דרוש רקע במתמטיקה בדידה וידע בתכנות.

מטלות הקורס כוללות תרגילים עיוניים ותרגילים מעשיים.