יסודות מדעי המחשב 2

הזמן הנדרש

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

· מעשי - 30 שעות

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

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

מטרות היחידה

· להעמיק ולהרחיב את החומר שנלמד ב"יסודות מדעי המחשב 1".

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

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

· להציג אלגוריתמים לבעיות חשובות (למשל מיון), המשמשות אמצעי למידה והדגמה לנושאים שנלמדו.

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

מעשי	עיוני	פרקי הלימוד
--	8	פרק 1 - פיתוח אלגוריתמים
10	8	פרק 2 - פרוצדורות
4	6	פרק 3 - תווים, מחרוזות ופעולות עליהן
6	18	פרק 4 - בעיות אלגוריתמיות מתקדמות
--	10	פרק 5 - יעילות ונכונות של אלגוריתמים - הרחבה
6	8	פרק 6 – טיפוסים ומבוא למבני-נתונים
4	2	פרק 7 – יחידת ספריה
30	60	סה"כ

* חלוקת השעות בטבלה מתייחסת לתלמידי הרמה המוגברת.

סביבת העבודה

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

ביבליוגרפיה

· האונ' הפתוחה (1987), מבוא למדעי המחשב ושפת פסקל.

· E. Koffman (1992), Pascal: Problem solving and program design, 4^th Ed, Addison-Wesely

· J.S.Rohl (1984),Recursion via Pascal, Cambridge University Press.

· R. Sedgwick (1988), Algorithms, 2nd edition, Addison-Wesely.

· N. Wirth, K. Jensen (1988), Pascal: User manual and report, 3^rd Ed., Springer-Verlang.

פרק 1: פיתוח אלגוריתמים ( 8 שעות )

מטרת הפרק

· לתרגל ולהעמיק בניתוח בעיה ובפתרונה.

פירוט התכנים

ניתוח בעיה מורכבת יותר ופיתוח פתרונה בשלבים מלמעלה למטה (top-down); תכנות מודולרי.

פרק 2: פרוצדורות ( 18 שעות )

מטרות הפרק

· להבין שהפרוצדורה היא אמצעי נוסף לפתרון בעיה בעזרת תתי -בעיות.

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

פירוט התכנים

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

הערה: יש לקשור לכאן את הנלמד בפרק 8 של "יסודות מדעי המחשב 1" ולעמוד על ההבדלים שבין פרוצדורה לבין פונקציה.

פרק 3: תווים ומחרוזות ( 6 שעות )

מטרת הפרק

· להקנות כלים לפתרון בעיות לעיבוד טקסט.

פירוט התכנים

מחרוזות; יחס סדר מילוני; ייצוג מחרוזות כמערכי תווים; בניית אלגוריתמים עבור מחרוזות.

המחרוזת היא מערך של תווים; דחיסת התווים על ידי packed או על ידי שימוש בטיפוס לא-תקני ( למשל על ידי string ).

אורך מחרוזת, השוואת מחרוזות, העתקת מחרוזות, מחיקת מחרוזות, שרשור מחרוזות, מציאת תת מחרוזת.

פרק 4: בעיות אלגוריתמיות מתקדמות ( 24 שעות )

מטרות הפרק

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

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

פירוט התכנים

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

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

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

פרק 5 : יעילות ונכונות של אלגוריתמים - הרחבה ( 10 שעות )

פרק רשות לתלמידי הרמה הרגילה (3 י"ל). חובה לתלמידי הרמה המוגברת.

מטרות הפרק

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

· ללמוד כלים ושיטות לניפוי שגיאות.

פירוט התכנים

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

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

פרק 6: טיפוסים ומבוא למבני-נתונים ( 10 שעות )

מטרות הפרק

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

· להכיר את מבנה הנתונים 'רשומה'.

· לבנות מבנים מורכבים.

פירוט התכנים

המושג טיפוס: הצהרת טיפוס, טיפוס מפורט.

מבני נתונים מורכבים: מערכים. רשומות ושילובם; שדה ברשומה; הגדרת רשומות; גישה לשדה בתוך רשומה; קליטה לתוך רשומה. הגדרת מערך דו-ממדי; מציינים למערך דו-ממדי.

הבהרה:

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

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

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

פרק 7: יחידת ספרייה ( 6 שעות )

לתלמידי הרמה הרגילה כפרק רשות.

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

מטרות הפרק

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

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

פירוט התכנים

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

מציינים למערך דו-ממדי.