מבני נתונים במדעי המחשב: מה לומדים ולמה זה חשוב

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

דימוי מהחיים

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

המבנים שלומדים כמעט בכל קורס

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

סיבוכיות: השפה של הקורס

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

• O(1): הזמן לא תלוי בכמות הנתונים.
• O(log n): הזמן גדל לאט מאוד. חיפוש בינארי ברשימה ממוינת הוא הדוגמה הקלאסית.
• O(n): הזמן גדל ביחס ישר לכמות.
• O(n²): הזמן גדל מהר מאוד. בכמויות גדולות זה כבר מורגש.

איך מצליחים בקורס

לצייר. כמעט כל שאלה על עצים, רשימות או גרפים נעשית קלה יותר כשמציירים אותה על דף.

לממש בעצמכם. לכתוב רשימה מקושרת או עץ מאפס, גם אם בשפה שבה הם כבר קיימים. ההבנה מגיעה מהקוד, לא מהשקפים.

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

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

למה זה חשוב אחרי התואר

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

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