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

מצגות שיעור

3.9.2014
בשיעור דיברנו על מדידת זמן ריצה של אלגוריתמים והכרנו את המושג ‘שיפור בקבוע’ ו-’שיפור בסדר גודל’.

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

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

1.10.2014
בשיעור למדנו את האלגוריתם למיון בועות (Bubble Sort), ראינו דוגמאות לתופעת הרקורסיה וכתבנו פונקציות רקורסיביות.

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

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

5.11.2014
בשיעור הכרנו את טיפוס הנתונים המופשט 'מחסנית' ואת פעולות הממשק המוגדרות עליו, למדנו על ייצוג תוכי (infix), תחילי (prefix) וסופי (postfix), וראינו כיצד ניתן להשתמש במשפט לפתרון נוסחאות נסיגה.

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

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

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

8.12.2014
בשיעור הכרנו את טיפוס הנתונים המופשט 'תור', וראינו כיצד ניתן לממש אותו באמצעות רשימה מקושרת.

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

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

28.12.2014
בשיעור למדנו על משפט האב (Master Theorem), וראינו כיצד אפשר להשתמש בו כדי לפתור נוסחאות נסיגה.

31.12.2014
בשיעור למדנו על עצי חיפוש בינאריים (BST) והכרנו אלגוריתמים יעילים הפועלים עליהם.

4.1.2015
בשיעור בשיעור הכרנו מושגים בסיסיים בתורת הקבוצות (Set Theory), אשר ישמשו אותנו בהמשך הקורס, והכרנו את האלגוריתם Select למציאת איבר מיקום בזמן לינארי.

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

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

18.1.2015
בשיעור הוכחנו חסם תחתון על סיבוכיות זמן הריצה של אלגוריתמי מיון המתבססים על השוואות.

21.1.2015
בשיעור הכרנו את האלגוריתם לסריקה לרוחב (BFS), את שיטת AVL לעצי חיפוש בינארי מאוזנים, ואת האלגוריתם למיון מנייה (מיון ספירה – Counting Sort).

25.1.2015
בשיעור הכרנו את טיפוס הנתונים המופשט 'תור קדימויות' (Priority Queue) ואת טיפוס הנתונים המופשט 'מילון' (Dictionary), והשווינו בין מימושים שונים שלהם.

28.1.2015
בשיעור פתרנו את בעיית הגשרים של קניגסברג והכרנו את מסלולי ומעגלי אוילר, למדנו את האלגוריתם לסריקה לעומק (DFS) של גרף, הכרנו את אלגוריתם קרוסקל (Kruskal) למציאת עץ פורש מינימלי בגרף ממושקל, וראינו כיצד יש לפתור משוואות נסיגה לינאריות הומוגניות.

4.2.2015
בשיעור למדנו על ערימה בינארית (Binary Heap), והשתמשנו בה על מנת לממש ביעילות תור קדימויות, ועל מנת לכתוב אלגוריתם מיון בשם 'מיון ערימה' (Heap Sort).

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

9.2.2015
בשיעור הכרנו את מבנה הנתונים 'טבלת גיבוב' (Hash Table) וראינו כיצד אפשר להשתמש בהם כדי לממש ביעילות, בממוצע, את טיפוס הנתונים המופשט 'מילון'.

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

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

16.2.2015
בשיעור הכרנו את האלגוריתם של בלמן-פורד (Bellman-Ford) למציאת מסלול קצר ביותר בגרף ממושקל, ולמדנו על האלגוריתם למיון בסיס (Radix Sort).

25.2.2015
בשיעור הכרנו את האלגוריתם למיון מהיר (َQuick Sort), וראינו משפט לפתרון נוסחאות נסיגה לינאריות אי-הומוגניות.

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

תרגילים

תרגיל מס' 1
להכנה עד יום ד', 10.9.

תרגיל מס' 2
להכנה עד יום ד', 17.9.

תרגיל מס' 3
להכנה עד יום א', 28.9.

תרגיל מס' 4
להכנה עד יום א', 19.10.

תרגיל מס' 5
להכנה עד יום א', 19.10.

תרגיל מס' 6
להכנה עד יום ד', 5.11.

תרגיל מס' 7
להכנה עד יום ד', 12.11.

תרגיל מס' 8
להכנה עד יום ד', 19.11.

תרגיל מס' 9
להכנה עד יום ד', 26.11.

תרגיל מס' 10
להכנה עד יום ד', 10.12.

תרגיל מס' 11
להכנה עד יום ד', 24.12.

תרגיל מס' 12
להכנה עד יום ד', 31.12.

תרגיל מס' 13
להכנה עד יום א', 4.1.

תרגיל מס' 14
להכנה עד יום ד', 7.1.

תרגיל מס' 15
להכנה עד יום א', 18.1.

תרגיל מס' 16
להכנה עד יום ד', 28.1.

תרגיל מס' 17
להכנה עד יום ד', 4.2.

תרגיל מס' 18
להכנה עד יום ד', 11.2.

תרגיל מס' 19
להכנה עד יום א', 15.2.

תרגיל מס' 20
להכנה עד יום ב', 16.2.

תרגיל מס' 21
להכנה עד יום ד', 18.2.

תרגיל מס' 22
להכנה עד יום א', 22.2.

תרגיל מס' 23
להכנה עד יום א', 22.2.

תרגיל מס' 24
להכנה עד יום א', 1.3.

תרגיל מס' 25
להכנה עד יום א', 1.3.

תרגיל מס' 26
להכנה עד יום א', 8.3.

תרגיל מס' 27
להכנה עד יום א', 8.3.

חומר עזר

ספר הלימוד "מבוא לחקר ביצועים"
הועלה ספר הלימוד "מבוא לחקר ביצועים", בהוצאת מט"ח. זהו ספר לימוד בעברית, שפרקים 4-6 בו עוסקים באלגוריתמים בתורת הגרפים, ופרקים 1-3 בו ישמשו עבור הקורס "אלגברה לינארית", הנלמד בכיתה יד'.

המחשות של האלגוריתם למיון בחירה
אנימציות הממחישות את פעילותו של האלגוריתם למיון בחירה (Selection Sort).

המחשות של האלגוריתם למיון בועות
אנימציות הממחישות את פעילותו של האלגוריתם למיון בועות (Bubble Sort).

המחשות של האלגוריתם למיון הכנסה
אנימציות הממחישות את פעילותו של האלגוריתם למיון הכנסה (Insertion Sort).

המחשות של האלגוריתם למיון מיזוג
אנימציות הממחישות את פעילותו של האלגוריתם למיון מיזוג (Merge Sort).

המחשות של האלגוריתם למיון ספירה
אנימציות הממחישות את פעילותו של האלגוריתם למיון ספירה (Counting Sort).

המחשות של האלגוריתם למיון ערימה
אנימציות הממחישות את פעילותו של האלגוריתם למיון ערימה (Heap Sort).

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

המחשה של עץ חיפוש בינארי ושל ערימה
אתר ובו יישומונים אינטראקטיביים הממחישים את השימוש בעצי חיפוש בינארי (כולל עצי AVL) ובערימות מינימום ומקסימום.

קישורים

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

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

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

הרצאות וידאו במדעי המחשב
קישורים לאתרים של קורסים שלימד מדען המחשב Steven Skiena. ההרצאות הוקלטו בוידאו, והועלו לאינטרנט. חלק מהנושאים רלוונטיים גם לקורס שלנו: קורס באלגוריתמים – כולל שיעורים בנושא מבני נתונים (עצים, ערימות, וכו'), תורת הגרפים (מציאת מסלול קצר ביותר, מציאת עפ"מ, וכו'), שיטות מיון, פתרון נוסחאות נסיגה; וקורס באתגרי תכנות – כולל שיעורים העוסקים באסטרטגיות לפתרון בעיות אלגוריתמיות (בסגנון ה-'חידות לחימום').

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

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