סיבוכיות של אלגוריתמים בקורס "מבוא למדעי המחשב" באוניברסיטה:

כיצד נוכל לשפר את הוראתה?

ד"ר אלה צור

תמי וילנר

פרופ' יהודית גל-עזר

האוניברסיטה הפתוחה

האוניברסיטה הפתוחה

האוניברסיטה הפתוחה

ela@openu.ac.il

tami@openu.ac.il

galezer@openu.ac.il

 

המסר של ההרצאה הוא כיצד ללמד את המושג סיבוכיות של אלגוריתמים תוך כדי התרכזות בדוגמאות שממחישות את המושג.

 

מבוא

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

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

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

במהלך המחקר בדקנו תשובות של סטודנטים לשאלות שונות מסוג זה שתיארנו.

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

 

המחקר

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

נתון מערך a בגודל n-1 שכל איבר בו הוא שלם בין 1 ל- n. כל האיברים במערך שונים זה מזה.

נתונה הפונקציה הבאה:

int something (int a[n-1])

{

      int i, j, flag;

      for (j=1; j<=n; j++)

      {

        flag = 0;

        for (i=0; i<n-1; i++)

        {

              if (a[i]==j)

              {

                   flag = 1;

                   break;

              }

        }

        if (!flag)

             return j;

      }

     return -1;

}    

א. מה מבצעת הפונקציה something?

    הסבר בקצרה מה מבצעת הפונקציה באופן כללי, ולא כיצד היא מבצעת זאת.

ב. מהו סדר הגודל של זמן הריצה של הפונקציה something?

ג. כתוב את הפונקציה something כך שתפתור את הבעיה

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

   פונקציה שתהיה בסיבוכיות גדולה יותר (מבחינת זמן ו/או מבחינת זיכרון)

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

 

הממצאים

התשובה לסעיף א היא שהפונקציה מחזירה את הערך החסר במערך.

מתוך 189 נבחנים, 120 ענו נכון על סעיף א, כלומר 63%.

סעיף ב בדק מהי סיבוכיות הפונקציה (שהיא כידוע, O(n2)). הפעם, 168 מתוך 189 (89%) ידעו לענות נכון על השאלה.

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

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

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

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

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

5.      גם כאן הסטודנט מיין את המערך בעזרת מיון מיזוג, אך הפעם לא השתמש בתוצאה המיוחדת המתקבלת מכך שכל האיברים במערך שונים זה מזה וכולם בטווח המספרים 1..n. הוא עבר על כל המספרים מ- 1 עד n ובדק באמצעות חיפוש בינרי (שהוא בסיבוכיות O(log2n)) איזה מספר לא נמצא. גם חלק זה לוקח O(n·log2n) צעדים. סך-הכול, הפתרון שהוריד את סיבוכיות הזמן ל- O(n·log2n), למעשה 2·log2n צעדים.

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

 

התפלגות התשובות לפתרונות השונים היא כזו:

באחוזים

מספר עונים

פתרון

1.06%

2

Summing the array and using the arithmetic sequence formula (n)

2.12%

4

Summing the array and summing the arithmetic sequence (2∙n)

17.46%

33

Using of another array (n time + n space)

31.75%

60

Merge-sort and linear search (n∙log2n)

6.35%

12

Merge-sort and n binary searches (2∙n∙log2n)

5.29%

10

Complexity of n2

35.98%

68

Error solution

 

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

 

לאתר המרכז

לכנס תשס"ד

חזרה