עיצוב תכנה

הזמן הנדרש

· עיוני - 60 שעות

· מעשי - 30 שעות

דרישות קדם

ידיעה טובה ושליטה בנושאים האלה:

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

אוכלוסיית יעד

תלמידי רמה מוגברת במדעי המחשב שסיימו לפחות יסודות מדעי המחשב 1 ויסודות מדעי המחשב 2.

מטרות היחידה

· להקנות את עיקרי הגישה המערכתית.

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

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

· להגדיר טיפוסי נתונים מופשטים חדשים ומימושם.

· להקנות יכולת לנתח את יעילותם של אלגוריתמים ואת התכניות המממשות אותם.

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

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

טבלת הפרקים וחלוקת השעות המוצעת

פרקי הלימוד	עיוני	מעשי
פרק 1 – מבוא ורקורסיה	8	4
פרק 2 - יחידת ספרייה - חזרה	2
פרק 3 - טיפוסי נתונים	8	4
פרק 4 - מחסנית	3	3
פרק 5 - יעילות	9	1
פרק 6 - רשימה	14	9
פרק 7 - עץ בינרי	11	6
פרק 8 – שילוב והרכבה של מבני נתונים מופשטים – תרגיל מסכם.	5	3
סה"כ	60	30

סביבת העבודה

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

ביבליוגרפיה

· בית הספר לטכנולוגיה של האוניברסיטה הפתוחה (1988), מבנה נתונים הנחיות והשלמות.

· האוניברסיטה הפתוחה (1987), מבני נתונים, כרכים א-ב.

· הראל ד.(1986), פרקי יסוד במדעי המחשב, ספרית האוניברסיטה המשודרת וגלי צה"ל.

· הראל ד. (1991), אלגוריתמיקה - יסודות מדעי המחשב, האוניברסיטה הפתוחה.

· Aho, Hopcroft, Ullman (1983), Data Structures and Algorithms, Addison-Wesley.

· Horowitz, Sahni (1990), Fundamentals of Data Structures in Pascal, 3^rd Ed., Computer Science Press.

· Koffman (1989), Pascal, 3^rd Ed., Addison-Weseley.

· Reingold, Hansen (1986), Data Structures in Pascal, Little, Brown and Co.

פרק 1 : מבוא ורקורסיה (12 שעות)

מטרות הפרק

· להכיר הכרה ראשונית את המושג רקורסיה ככלי לפתרון בעיות.

· להכיר את היתרונות והחסרונות של כתיבה רקורסיבית.

· להציג את הרקע הכללי ליחידת הלימוד "עיצוב תכנה".

· להציג את הצורך והתועלת שבחלוקת מערכת לתת-משימות.

· להעמיק בשיטת התכנון מלמעלה למטה.

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

פירוט התכנים

הנדסת תכנה; תכנון מהכלל אל הפרט; מפרט מערכת; מודול; ממשק; מימוש; הסתרת מידע; שימוש חוזר בקוד; ממשק למשתמש.

מערכת תכנה: תכונות ( נכונות, עמידות, יעילות, תיעוד) , תחזוקה, שדרוג.

רקורסיה: קריאה רקורסיבית; בסיס הרקורסיה; תנאי עצירה; מעקב על אלגוריתמים רקורסיבים; כתיבת אלגוריתם רקורסיבי.

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

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

פרק 2: יחידת ספרייה - חזרה ( 2 שעות )

מטרות הפרק

· לחזור על יחידת הספריה שנלמדה עבור תלמידי הרמה המוגברת ביסודות 2

· לערוך היכרות מעמיקה עם יחידת הספרייה בסביבת העבודה.

· לחדד את רעיון המודולריות של מערכת תכנה באמצעות בנייה של יחידות ספרייה ושימוש בהן.

פירוט התכנים

בניית יחידת ספרייה בסביבת העבודה; משתנה פנימי; שגרה פנימית; קישור יחידת ספרייה לתכנית.

פרק 3: טיפוסי נתונים מופשטים ( 12 שעות )

מטרות הפרק

· לערוך היכרות עם המושג 'טיפוס נתונים מופשט'.

· ללמוד ולתרגל שלבי הגדרה, ייצוג המימוש והשימוש בטיפוס נתונים מופשט.

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

פירוט התכנים

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

פרק 4: מחסנית ( 6 שעות )

מטרות הפרק

· לתרגל הגדרה של טיפוס נתונים מופשט.

· לערוך היכרות עם טיפוס הנתונים המופשט 'מחסנית' על ידי שימושים שונים.

· לתרגל את מימוש טיפוס הנתונים מחסנית.

פירוט התכנים

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

פרק 5: יעילות ( 10 שעות )

מטרות הפרק

· להבין את המושג 'יעילות', באמצעות הכרת המדד של סיבוכיות זמן הריצה, ואת חשיבות של מדד זה.

· ללמוד מושגים בסיסיים בתחום היעילות (המקרה הגרוע ביותר).

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

· להכיר את המושג 'סדר גודל' (O גדול).

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

פירוט התכנים

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

ניתוח יעילות של מיון-בועות ומיון-מיזוג (שנלמדו ביסודות מדעי המחשב 2 ).

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

פרק 6: רשימה ( 23 שעות )

מטרות הפרק

· להכיר את טיפוס הנתונים 'רשימה'.

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

· להכיר את המנגנון של הקצאת זיכרון דינמית.

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

פירוט התכנים

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

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

פרק 7: עץ בינרי ( 17 שעות )

מטרות הפרק

· להכיר את טיפוס הנתונים 'עץ בינרי' ושימושים שונים שלו.

· לתרגל את השימוש בשגרות רקורסיביות ולהעריך את יעילותן.

· להכיר מהו עץ חיפוש בינרי והשימוש בו למיון.

פירוט התכנים

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

סריקה בסדר סופי; סריקה בסדר תוכי; סריקה בסדר תחילי; סריקה לפי רמות; עץ חיפוש; מיון על ידי עץ חיפוש.

פרק 8 - שילוב והרכבה של מבני נתונים מופשטים ( 16 שעות )

הזמן הנדרש

עיוני - 5 שעות

מעשי - 3 שעות

תרגיל מסכם

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

· במסגרת התרגיל מומלץ לאפשר לתלמידים גישה חופשית למעבדת מחשבים גם מעבר לשעות הלימודים הרשמיות (OPEN SHOP).

· כל מורה ינהל את התרגיל המסכם כראות עיניו, תוך התייחסות, קרובה ככל האפשר, למטרות הבאות:

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

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

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

נספח: ממשקים לטיפוסי נתונים בפרקים השונים

הממשק לטיפוס הנתונים מחסנית

אתחל-מחסנית	פעולה המחזירה מחסנית ריקה.
מחסנית-ריקה? (S)	פעולה המקבלת כפרמטר מחסנית S, מחזירה 'אמת' אם המחסנית ריקה, ו'שקר' אחרת. הנחה: המחסנית S מאותחלת.
דחוף-למחסנית (S, x)	הפעולה מכניסה את האיבר x לראש המחסנית S. הנחה: המחסנית S מאותחלת.
שלוף-ממחסנית (S)	פעולה המוציאה את האיבר שבראש המחסנית S ומחזירה את ערכו. הנחות: המחסנית S מאותחלת ואינה ריקה.
הצץ-למחסנית (S)	פעולה המחזירה את ערכו של האיבר שבראש S מבלי להוציאו. הנחות: המחסנית S מאותחלת ואינה ריקה.

הממשק לטיפוס הנתונים רשימה

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

עדכן-רשימה (L, p, x)	פעולה המעדכנת את האיבר הנמצא במקוםp ברשימה להיות x. הנחות: הרשימה L מאותחלת. p הוא מקום ב-L שאינו סוף-רשימה או עוגן-רשימה.
אחזר-מרשימה (L, p)	פעולה המחזירה את האיבר הנמצא במקום p ברשימה. הנחות: הרשימה L מאותחלת. p הוא מקום ב-L שאינו סוף-רשימה או עוגן-רשימה.
רשימה-ריקה? (L)	פעולה המחזירה 'אמת' אם הרשימה L היא רשימה ריקה, ו'שקר' אחרת. הנחה: הרשימה L מאותחלת.

הממשק לטיפוס הנתונים תור

אתחל-תור	פעולה המחזירה התור הריק.
הכנס-לתור (Q, x)	פעולה המקבלת תור Q ואיבר x ומכניסה את האיבר x בסוף Q. הנחה: התור Q מאותחל.
הוצא-מתור (Q)	פעולה המקבלת תור Q, מוציאה את האיבר שנמצא בראש התור ומחזירה אותו. הנחות: התור Q מאותחל ואינו ריק.
ראש-התור (Q)	פעולה המקבלת תור Q ומחזירה את ערכו של האיבר שבראשו בלי להוציאו משם. הנחות: התור Q מאותחל ואינו ריק.
תור-ריק? (Q)	פעולה המחזירה 'אמת' אם התור Q הוא תור ריק, ו'שקר' אחרת.הנחה: התור Q מאותחל.

הממשק לטיפוס הנתונים עץ בינרי

אתחל-עץ	פעולה המחזירה עץ בינרי ריק.
בנה-עץ (x L, R,)	פעולה המחזירה עץ בינרי שבשורשו האיבר x, התת-עץ השמאלי שלו L והתת-עץ הימני שלו R. הנחות: העצים L ו-R מאותחלים.
תת-עץ-שמאלי (T)	פעולה המחזירה את התת-עץ השמאלי של T. הנחות: T מאותחל ואינו ריק.
תת-עץ-ימני (T)	פעולה המחזירה את התת-עץ הימני של T. הנחות: T מאותחל ואינו ריק.
החלף-תת-עץ-שמאלי (T, new_tree)	פעולה המחליפה את התת-עץ השמאלי של T בעץ הבינרי new_tree. הנחות: העצים T ו-new_tree מאותחלים, T אינו ריק.
החלף-תת-עץ-ימני (T, new_tree)	פעולה המחליפה את התת-עץ הימני של T בעץ הבינרי new_tree. הנחות: העצים T ו-new_tree מאותחלים, T אינו ריק.
אחזר-שורש (T)	פעולה המחזירה את האיבר שבשורשו של T. הנחות: T מאותחל ואינו ריק.
עדכן-שורש (T, x)	פעולה המשנה את התוכן של שורש T להיות x. הנחות: T מאותחל ואינו ריק.
עץ-ריק? (T)	פעולה המחזירה 'אמת' אם העץ הבינרי T הוא עץ ריק, ו'שקר' אחרת. הנחה: T מאותחל.