הפשטה כמושג מרכזי בהוראת מדעי המחשב: סקר ספרות

עמדות תלמידי תיכון כלפי הפשטה פרוצדורלית

ב. הברמן

Haberman, B. (2004). High-school students' attitudes regarding procedural abstraction. Education and Information Technologies, 9(2), 131-145.

 

כל החומרים עומדים לרשותכם וניתן להשתמש בהם להוראה ללא תשלום.

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

 

תקציר

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

 

מבוא

הפשטה היא מושג מרכזי במדעי המחשב (Denning et al., 1989). Aho & Ullman (1995) מתארים את מדעי המחשב כ"מדע של הפשטה- יצירת מודל נכון לחשיבה על בעיה ובחירת טכניקות מתאימות לפתרון". במדעי המחשב מקובל להתייחס להפשטת נתונים והפשטה פרוצדורלית (Dale & Walker, 1996). אנשי חינוך העוסקים במחקר בהוראת מדעי המחשב ובפיתוח קווים מנחים לתכניות לימודים בתחום, סבורים שיש לשלב הפשטה כמושג מרכזי בהוראה.

תכנית הלימודים החדשה במדעי המחשב לתיכון בישראל שהטמעתה החלה לפני קצת למעלה מעשור, מדגישה עקרונות ומושגים שאינם תלויי מימוש, בצד יישום פרקטי שלהם בשפות תכנות קונקרטיות ובפרדיגמות תכנות שונות  (Gal-Ezer, Yehudai, Harel & Beeri, 1995, Gal-Ezer & Harel 1999). הכרות עם מושג ההפשטה נערכת בהדרגה לאורך יחידות הלימוד, החל מ"יסודות מדעי המחשב", דרך יחידות המציגות פרדיגמות תכנות שונות כדוגמת "תכנות לוגי" או "תכנות פונקציונלי" , היחידה "עיצוב תוכנה" שאחת ממטרותיה המרכזיות היא פיתוח חשיבה מופשטת ופיתוח יכולות של פתרון בעיות דרך שימוש בטיפוסי נתונים מופשטים (טנ"מ). 

 

פתרון בעיות תוך שימוש בטיפוסי נתונים מופשטים

דוגמה

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

הבעיה:

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

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

 

פתרון 1:

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

Num-of-Nodes(T)

1.         if  Is_Empty ? (T) then  return  0

2.        else

2.1  if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

           ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then

2.1.1return

          1 + Num-of-Nodes(Left_Sub_Tree (T) ) +  Num-of-Nodes(Right_Sub_Tree (T) )

         2.2  else  return   Num-of-Nodes(Left_Sub_Tree (T) ) + Num-of-Nodes(Right_Sub_Tree (T) )

 

פתרון 2:

הפתרון מאורגן בשתי רמות הפשטה. הוא מבוסס על חלוקת הבעיה לשתי תת משימות:

(א) הגדרת  פעולה חדשה מופשטת (abstract primitive) (Leron, 1987) :  Has_Single_Child ? (T)  הממומשת במונחים של ממשק "עץ בינרי" באלגוריתם נפרד;

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

 

Num-of-Nodes(T)

1.         if Is_Empty ? (T) then return  0

2.        else

          2.1  if Has_Single_Child ? (T) then

2.1.1return

          1+ Num-of-Nodes(Left_Sub_Tree (T)  + Num-of-Nodes(Right_Sub_Tree (T) )

         2.2  else  return  Num-of-Nodes(Left_Sub_Tree (T) ) +  Num-of-Nodes(Left_Sub_Tree (T) )

 

 Has_Single_Child ? (T)

      1.   if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

     ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Right _Sub_Tree (T) ) ) then

1.1           return  True

      2. else  return  False

 

פתרון 3:

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

 

Num-of-Nodes (T)

1.        if Is_Empty ? (T) then return  0

2.        else

2.1     return  Compute_Node (T) + Num-of-Nodes(Left_Sub_Tree (T) + Num-of-Nodes(Right_Sub_Tree (T) )

          

 Compute_Node (T)

      1.   if  Has_Single_Child ? (T)  then

2.2           return  1

      2.   else  return  0

 

Has_Single_Child ? (T)

      1.   if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

          ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then

1.2           return  True

      2. else  return  False

 

פתרון 4:

זהו הפתרון המופשט ביותר, מאורגן בארבע רמות הפשטה- כל רמה מהווה מימוש של תת משימה אחת. האלגוריתם הראשי מזמן פעולה Compute (T, L, R) תוך שימוש בקריאות רקורסיביות לחישוב ערכים מוחזרים מתתי העצים. Compute (T, L, R) מזמנת אתCompute_Node (T)  לצורך השלמת חישוב הערך המבוקש.

 

Num-of-Nodes(T)

      1.            if Is_Empty ? (T) then return  0

      2.            else

  2.1  return  Compute (T, Num-of-Nodes(Left_Sub_Tree (T), Num-of-Nodes(Right_Sub_Tree (T) )

          

 Compute (T, Left_Value, Right_Value)

       1.  return  Compute_Node (T) + Left_Value + Right_Value

 

 Compute_Node (T)

      1.   if  Has_Single_Child ? (T)  then

2.3           return  1

      2.   else  return  0

 

 Has_Single_Child ? (T)

     1.   if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

      ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then

1.3           return  True

     2.  else  return  False

 

לפתרון 4 יש צורה כללית ביותר, ובדומה לפתרון 3 היא יכולה להיות מותאמת בקלות לפתור בעיות אחרות. 

טבלה 1 מסכמת את מאפייני ארבעת הפתרונות.

 

פתרון 1

פתרון 2

פתרון 3

פתרון 4

מאפיין

1

2

3

4

רמות הפשטה

נכון

נכון

נכון

נכון

נכונות

מורכב

בינוני

פשוט

פשוט

מורכבות קוד בכל רמה

קיים

קיים

לא קיים

לא קיים

קוד מיותר

לא קיים

קיים

קיים

קיים

זימון של פעולה מופשטת

קריאות רקורסיביות

זימון פשוט, קריאות רקורסיביות

זימון פשוט, קריאות רקורסיביות

מורכב,

קינון קריאות רקורסיביות

אופן הזימון

נמוך

גבוה

גבוה

גבוה

מידת התאמה לפתרון בעיות דומות

 

המחקר

מטרת המחקר הייתה לבדוק את עמדות התלמידים כלפי שימוש בהפשטה פרוצדורלית, ולבחון היתכנות  תרומה דידקטית של כלים תומכים לפיתוח אלגוריתמים (Haberman, 2002). אוכלוסית המחקר כללה 39 תלמידי תיכון שלמדו עיצוב תוכנה (ייקראו מתחילים), ו- 19 סטודנטים לתואר ראשון במדעי המחשב (ייקראו מתקדמים) אשר למדו טיפול במבני נתונים במסגרת קורס אלגוריתמים מתקדמים ומבני נתונים. למשתתפים במחקר ניתנה הבעיה שתוארה לעיל מלווה בארבעה פתרונות מוצעים, שניים מהם שונים קלות מהפתרונות שהוצגו בסעיף הקודם. חשוב לציין שהפתרונות המוצעים בסעיף הקודם בנויים  בצורה דידקטית ומומלצים להצגה באופן זה בתהליך הוראה/למידה היות והם משקפים התפתחות הדרגתית ברמות הפשטה. לעומת זאת, שינוי האלגוריתמים לצורך עריכת המחקר נעשה כדי לטשטש במידת מה את ההבדלים הבולטים ביניהם (האלגוריתמים שהוצגו לתלמידים במחקר נמצאים בנספח 1). נסכם בקצרה את מאפייני האלגוריתמים שהוצגו לתלמידים במחקר: כל ארבעת האלגוריתמים רקורסיביים, פותרים נכונה את הבעיה ונבדלים ברמות ההפשטה. פתרון 1 הוא בעל רמת ההפשטה הנמוכה ביותר, לפתרון 2 יש שתי רמות הפשטה, והוא היחיד העושה בשימוש בפעולה Has_Single_Child ? (T). שני הפתרונות הראשונים מכילים כפילות קוד. בדומה לפתרון 2, פתרון 3 מאורגן בשתי רמות הפשטה, אך אין בו כפילות של קוד. פתרון 4 הוא המופשט ביותר וכולל קינון של קריאות רקורסיביות.

התלמידים נתבקשו להעריך את הנכונות, הקריאות, והכלליות של כל פתרון, ולדרגם על סקלה של 1-4 (1- הפתרון המועדף ביותר, 4- הפתרון הכי פחות מועדף).

 

ממצאים

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

 

Table 2. Students' assessment regarding the correctness, readability, and generality of algorithms

 

 

Algorithm 1

Algorithm 2

Algorithm 3

Algorithm 4

Comparison between alg.

Beginners

Correctness

87 %

87%

86%

79%

 

Generality

92%

87%

84%

79%

 

Readability Avg. (Std)

3.28

(0.97)

3.76

(0.49)

3.11

(0.81)

2.26

(0.92)

4<(3,1)<2

F(3,107)=21.6

p=0.0001

Advanced

Correctness

100%

100%

100%

94%

 

Generality

100%

100%

100%

94%

 

Readability

Avg. (Std)

3.35

(0.7)

3.41

(0.71)

3.47

(0.94)

2.53

(1.12)

4<(1,2,3)

F(3,48)=7.1

p=0.0005

Comparison between groups

Correctness

n.s.

n.s.

n.s.

n.s.

 

Generality

n.s.

n.s.

n.s.

n.s.

 

Readability

n.s.

p=0.038  t=2.13

n.s.

n.s.

 

 

נכונות וכלליות: כל התלמידים המתקדמים הצליחו בהערכת אלגוריתמים 1-3, ורק 6% לא הצליחו בהערכת אלגוריתם 4. התלמידים המתחילים אמנם הצליחו פחות לעומת המתקדמים, אך רובם ציינו את אלגוריתמים 1-3 כנכונים וכלליים. כחמישית מהמתחילים לא הצליחו להעריך נכונה את אלגוריתם 4.  לא נמצאו הבדלים מובהקים בין בקבוצות בהערכת נכונות וכלליות של כל אלגוריתם.

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

העדפת אלגוריתמים: טבלה 3 מתארת ציון הערכה ממוצע של כל קבוצה לגבי כל אחד מהאלגוריתמים (סקלה 1-4, 1- האלגוריתם הכי פחות מועדף). התלמידים המתחילים דירגו אלגוריתמים 1 ו- 2 יותר גבוה באופן מובהק לעומת התלמידים המתקדמים. המתקדמים, לעומת זאת, מעדיפים את אלגוריתם 3 יותר מהמתחילים, דבר המעיד על כך שקל להם יותר להסתדר עם יותר רמות הפשטה. לא נמצא הבדל מובהק בהעדפות שתי הקבוצות את אלגוריתם 4, ממצא המעיד על כך שלשתי הקבוצות, יותר מדי רמות הפשטה מפריעות לקריאות.

Table 3. Students' preference of algorithms

 

 

Algorithm 1

Algorithm 2

Algorithm 3

Algorithm 4

Beginners

Avg. (Std)

2.92

(1.12)

3.03

(0.83)

2.51

(1.1)

1.54

(0.77)

Advanced

Avg. (Std)

2.18

(1.13)

2.29

(0.59)

3.59

(0.62)

1.94

(1.25)

Comparison between groups

t

2.26

3.27

-4.58

-1.22

p

0.028

0.002

0.0001

n.s.

 

התפלגות העדפות הקבוצות (באחוזים) לכל אלגוריתם מומחשת על ידי הצגה גראפית. רוב התלמידים המתחילים דירגו את אלגוריתם 1 ו- 2 במקום השני (~70% ו- ~80% בהתאמה), המתקדמים דירגו את אלגוריתם 3 במקום ראשון ושני (~95%). לא נמצא הבדל מובהק בין הקבוצות מבחינת דירוג אלגוריתם 4 במקום רביעי (~60% בכל קבוצה). לעומת זאת, היה הבדל בקבוצות בנוגע לדירוג אלגוריתם 4 כמקום ראשון, כמקום שני, וכמקום שלישי. יותר תלמידים מתקדמים דירגו את אלגוריתם 4 במקום ראשו ובמקום שני (~35%) לעומת התלמידים המתחילים (פחות מ- 10%). 

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

 

 

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

 

מסקנות

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

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

תוצאות המחקר שהוצג במאמר זה שימשו לפיתוח כלים תומכים ברמות הפשטה שונות כמתואר ב- (Haberman, 2002; ראה תקציר בעבודה זו).

נספח 1: פתרונות חלופיים לבעיה בשאלון המחקר

 

Solution 1

Num-of-Nodes(T)

1.  if  Is_Empty ? (T) then  return  0

2. else

2.1  if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

           ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then

2.1.2 return 1 + Num-of-Nodes(Left_Sub_Tree (T) ) +  Num-of-Nodes(Right _Sub_Tree (T) )

             2.2  else  return Num-of-Nodes(Left_Sub_Tree (T) ) + Num-of-Nodes(Right _Sub_Tree (T) )

Solution 2

Num-of-Nodes(T)

     1.  if Is_Empty ? (T) then return  0

2. else

2.1  if Has_Single_Child ? (T) then

                    return  1+ Num-of-Nodes(Left_Sub_Tree (T)  + Num-of-Nodes(Left_Sub_Tree (T) )

           2.2  else  return Num-of-Nodes(Left_Sub_Tree (T) ) +  Num-of-Nodes(Left_Sub_Tree (T) )

 Has_Single_Child ? (T)

1.   if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

          ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then return  True

2. else  return  False

Solution 3

Num-of-Nodes(T)

1.  if Is_Empty ? (T) then return  0

2. else

2.1  return  Compute_Node(T) + Num-of-Nodes(Left_Sub_Tree (T) + Num-of-Nodes(Right_Sub_Tree (T) )

          

 Compute_Node (T)

         1. if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

          ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then return  1

            2.   else  return  0

Solution 4

Num-of-Nodes(T)

1. if Is_Empty ? (T) then return  0

2. else

2.1  return  Compute (T, Num-of-Nodes(Left_Sub_Tree (T), Num-of-Nodes(Right_Sub_Tree (T) )

          

 Compute (T, Left_Value, Right_Value)

              1.   return  Compute_Node (T) + Left_Value + Right_Value

 

Compute_Node (T)

1.   if  ( ( Is_Empty? (Left_Sub_Tree (T) and  not Is_Empty? (Right_Sub_Tree (T) ) ) or

          ( ( Is_Empty? (Right_Sub_Tree (T) and  not Is_Empty? (Left_Sub_Tree (T) ) ) then return  1

2. else  return  0

 

חזרה לעמוד הראשי