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