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

6 נקודות זכות ברמה רגילה

שיוך: תואר ראשון / מדעים / מדעי המחשב

מחלקה: מתמטיקה ומדעי המחשב

דרישות קדם

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

ידע קודם מומלץ: הקורסים חשבון אינפיניטסימלי 1, אלגברה לינארית 1 (‏או אלגברה לינארית לתלמידי מדעים‎)‏, הסתברות ומבוא לסטטיסטיקה למדעי המחשב (‏או מבוא לסטטיסטיקה ולהסתברות למדעים).[3990]

שפת ההוראה

עברית

תיאור הקורס ומטרותיו

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

ידע כישורים ומיומנויות שירכשו בקורס (תוצרי הלמידה)

עם סיום הקורס, הסטודנטים:

1. ידעו לנתח סיבוכיות של אלגוריתמים במקרה הטוב, במקרה הגרוע ובמקרה הממוצע (תוחלת) תוך שימוש בכלים מתמטיים.
2. יוכלו להוכיח נכונות של אלגוריתמים באמצעות שמורות לולאה ואינדוקציה.
3. ישלטו במנגנוני הפעולה של מבני נתונים דינמיים ויידעו מתי להעדיף מבנה אחד על פני אחר.
4. יפתחו מיומנות בתכנון אלגוריתמים יעילים לבעיות מורכבות תוך שימוש בטכניקות של "הפרד ומשול".
5. יפתחו יכולת למימוש מעשי של מבני נתונים ואלגוריתמים בשפת תכנות, תוך הקפדה על יעילות.

שיטת ההוראה

הקורס מבוסס על מודל למידה משולב:

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

נושאי הלימוד

הקורס מבוסס על פרקים 1-14 בספר מבוא לאלגוריתמים (תרגום של פרקים 1-14 מהספר Introduction to Algorithms של CLRS):

• יסודות: ניתוח אלגוריתמים, סימונים אסימפטוטיים (), ונוסחאות נסיגה (שיטת האב, עץ הרקורסיה ועוד).
• מיון: מיון ערמה (Heapsort), מיון מהיר (Quicksort), חסמים תחתונים למיון השוואתי, ומיונים בזמן ליניארי (מיון מניה, מיון בסיס, מיון דלי).
• מבני נתונים בסיסיים: מחסניות, תורים, רשימות מקושרות וערמות.
• טבלאות גיבוב (Hash Tables): פונקציות גיבוב, פתרון התנגשויות באמצעות שרשור ומיעון פתוח.
• עצי חיפוש: עצי חיפוש בינאריים (BST) ועצים מאוזנים (עצים אדומים-שחורים).
• הרחבת מבני נתונים: תכנון מבנים מתקדמים על בסיס מבנים קיימים (כגון עצי ערכי מיקום).

_____________________________________________________________________________

להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים) ראו פירוט החפיפה

הערות