החומר המופיע בעמוד זה פורסם לראשונה בכתב העת "הבטים בהוראת מדעי המחשב" גליון ינואר 2004, עמודים 52-56

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

הוראת הסיבוכיות על-ידי שיפורים באלגוריתם

ד"ר יבגני קנל ושי שגב
מקיף עירוני א', אשקלון

kanel@netvision.net.il , Shai_segev@walla.co.il

 


הקדמה

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

* יעילות של אלגוריתם נלמדת בשלב מאוחר יחסית.

* על פי רוב בשימוש בבעיות חיפוש ומיון.

* עדיף ללמד יעילות של אלגוריתם בשלב מוקדם יותר ובאופן אינטואיטיבי.

* קורסי מבוא בתכנות מלמדים את הידע הבסיסי ומיומנויות תכנות ותכנון. (skills of program design)

* למידת תכנות "נכון" נעשית יותר נפוצה אך קיים ויכוח על השיטות הפורמאליות.

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

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

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

 

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

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

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

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

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

 

פתיחה

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

 

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

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

 

דוגמה נוספת שבה נתמקד בהמשך היא הבעיה הבאה:

נתבונן על המספרים הטבעיים מ- 1 עד M ונמחק את אחד המספרים בסדרה הזו N. כעת נחשב את סכום המספרים לפני N ואת סכום המספרים אחרי N.

יש למצוא M,N כאלו כך ששני הסכומים יהיו שווים.

המטרה היא למצוא כמות מירבית של זוגות M,N.

לדוגמה: אם   M=10 , N=7  הסכומים יהיו 21, 27.

הסבר: סכום המספרים לפני N יהיה 21 (כי 1+2+3+4+5+6=21, וסכום המספרים אחרי N יהיה 27 (כי 8+9+10=27).

 

כל התכניות שיובאו בהמשך נכתבו על פסקל בורלנד 7 ונבדקו על ידי שני מחשבים. האחד ישן מאוד עם מעבד i386 (20Mhz), והשני חדיש יותר עם מעבד פנטיום 3 (1000Mhz).

 

כל הפתרונות הסתיימו מהסיבות הבאות:

1. חלפה שעה מרגע ההפעלה.

2. בגלל גלישה Overflow.

בכל מקרה בסוף העבודה מציינים לאיזה ערך של M הגענו.

 

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

 

אלגוריתם 1

{$A+, B-, D+, E+, F+, G-, I+, L+, N-, O-, P-, Q-, R+, S+, T-, V+, X+, Y+}

Program mn1;

Uses Dos; {is requied for getttime()}

const tmax=360000;

var {משתני עזר}

     exitSave: pointer;

     tStart:   longint;

var        m, n, s1, s2, i:     longint;

             k:        integer;

 

function gtime: longint;

   {מחזירה זמן מתחילת היממה במאיות שנייה}

var        hour, min, sec, sec100: word;

begin

     gettime(hour, min, sec,sec100);     

     gtime:= longint(hour)*36000 + longint(min)*6000 + longint(sec)*100 + longint(sec100)

end;

 

procedure finish;   {מדפיסה זמן חישוב בשניות}

begin

     exitProc:=exitSave;

     writeln('(זמן חישוב(שניות');

     writeln( (gtime-tstart)/100:0:2);

     writeln('M=', m, '  N=',n)

end;

 

procedure start;

begin

     tstart:=gtime;

     exitSave:= exitProc;

     exitProc:=@finish;

end;

 

begin

     start;

     k:=0;

     for m:=1 to maxlongint do

     begin

     for n:=1 to m do

     begin

           s1:=0;

           for i:=1 to n-1 do s1:=s1+i;

           s2:=0;

           for i:=n+1 to m do s2:=s2+i;

           if s1=s2 then

            begin

             inc(k);

             writeln(k:2,')', m:12, n:12)

           end;

     end;

     if gtime-tstart> tmax then halt;

  end

end.

 

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

התוצאה של אלגוריתם 1 היתה שאחרי שעה של ריצה ערכו של M היה 9350 ונמצאו 5 זוגות.

 

אלגוריתם 2

program mn2;

var

  m, n   : longint;

  s1, s2 : longint;

  k      : integer;

begin

 k:=0;

 for m:= 1 to maxlongint do

  begin

   for n:=1 to m do

    begin

     s1:= (n-1)* n div 2;

     s2:= (m-n)*(m-n+1) div 2;

     if s1=s2 then

      begin

             inc(k);

             writeln(k:2,')',m:12, n:12)

     end;

    end

  end;

end

 

השינוי הראשון הוא לא להשתמש בלולאות לחישוב סכום. מדובר בסכום של סדרה חשבונית ולכן ניתן להשתמש בנוסחה. השינוי השפיע באופן משמעותי על התוצאות. אחרי 6.5 דקות נמצאו 6 זוגות, עצירה בגלישה  ו- M=46,341.

 

אלגוריתם 3

program mn3;

var

 m,n     : longint;

 s1, s2  : longint;

 k       : integer;

begin

  k:=0;

  for m:=1 to maxlongint do

   begin

    n:=1;

    s1:=0;

    s2:=m*(m+1)div 2 -1;

    while s1 < s2 do

     begin

      s1:=s1 + n;

      n:=n + 1;

      s2:=s2 - n

     end;

     if s1=s2 then

     begin

             inc(k);

             writeln(k:2,')', m:12, n:12)

     end

   end

end.

 

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

תוצאת השיפור: 6 זוגות וגלישה. ערכו של M היה 46,341  תוך 15 שניות.

 

אלגוריתם 4

program mn4;

var

 m,n     : longint;

 s       : longint;

 k       : longint;

 begin

 start;

  k:=0;

  for m:=1 to maxlongint do

   begin

    s:=m*(m+1) div 2;

    n:= round(sqrt(s));

    if sqr(n)= s then

     begin

             inc(k);

             writeln(k:2,')', m:12, n:12)

     end

   end;

 end.

 

השיפור בכך שאין צורך לבדוק את כל ה- N. מובן של- M יכול להיות רק N מתאים אחד.

הנוסחאות לסכומים ידועות:

(1)

  

 

 

ועם שינויים קלים נקבל:

2))

       

 

לכל M צריך לבדוק את הנוסחה לעיל, אם מתקיימת.

התכנית מחשבת בזמן 0.5 שנייה אבל לא משפרת את התוצאה: 6 זוגות וגלישה ב- M=46,341.

 

אלגוריתם 5

program mn5;

var

  m, n    : longint;

  s1,s2   : longint;

  k       : integer;

 begin

 start;

  k:=0;

  m:=1; s1:=1;

  n:=1; s2:=1;

  while m < maxlongint do

   begin

    if s1 > s2 then

                begin

                     n:=n+1;

                     s2:=s2 + 2*n -1

               end

               else if s1 < s2

                            then

                            begin

                                    m:=m+1;

                                    s1:=s1+m

                            end

                            else

                            begin

                                    inc(k);

                                    writeln(k:2,')', m:12, n:12);

                                    n:=n+1;

                                    s2:=s2 + 2*n -1;

                                    m:=m+1;

                                    s1:=s1+m;

                            end

   end

 end.

 

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

ממשוואה (2) נקבל שהאגף השמאלי הולך וגדל עם גידול של N. האגף הימני עם גידולו של M.

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

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

התוצאות: זמן החישוב גדול יותר מהקודם אבל במקום 6 זוגות מצאנו הפעם 7 זוגות והגלישה מגיעה כאשר M=65,535 ,  N=46,341.

 

מדוע הביאו השינויים הקוסמטיים לאיכות חדשה?

הגלישה מתרחשת כאשר ,

 

החישוב:  יותר גדול מהתוצאה האמצעית.

לפיכך, כדאי לשנות קצת את הפתרונות 2-4 ולבצע את חישוב החילוק לפני הכפל, ללא שארית.

 

אלגוריתם 6

program mn6;

var

  m, n    : longint;

  s       : longint;

  k       : integer;

 begin

 {start;}

  k:=0;

  m:=1;

  n:=1;

  s:= 0;

  while m < maxlongint do

   begin

             if s > 0

                     then

                     begin

                            n:=n+1;

                            s:=s - 2*n +1

                     end

                     else  if s < 0

                                    then  begin

                                            m:= m + 1;

                                            s:= s + m;

                                    end

                                    else begin

                                            inc(k);

                                            writeln(k:2,')', m:12, n:12);

                                            n:= n + 1;

                                            s:= s - 2*n + 1;

                                            m:= m + 1;

                                            s:= s+m;

                                    end

   end

 end.

 

אין הרבה טעם בכל השיפורים אם לא נצליח לבטל את הגלישה. ישנן מספר דרכים לנסות להתגבר על הגלישה ונבחר בדרך הפשוטה ביותר. הזוג האחרון שמתקבל הוא: 57,121 , 40,391. אלו מספרים קטנים יחסית הרחוקים מ- maxlongint. הסיבה לגלישה היא חישובי העזר "המסבכים" את המצב. לכן, במקום השוואת סכומים ננסה להשוות את ההפרש עם אפס ובהתאם לתוצאה נגדיל את המשתנה המתאים. התוצאה משתפרת מאוד. אחרי שעה של חישובים לא קיבלנו גלישה, עצרנו כש- M גדול מ- 400 מליון ומצאנו 12 זוגות.

 

שיפור אלגוריתמים 5,6 

program mn5a;

 var

  m, n    : longint;

  s1,s2   : longint;

  k       : integer;

 begin

 start;

  k:=0; s1:=0;

  n:=1; s2:=1;

  for m:=1 to maxlongint do

   begin

   s1:=s1 + m;

   if s1=s2

             then begin

                            inc(k);

                            writeln(k:2,')', m:12, n:12)

             end;

   if s1 > s2

             then begin

                            n:= n + 1;

                            s2:= s2 + 2*n -1

             end

   end

 end.

 

program mn6a;

var

  m, n    : longint;

  s       : longint;

  k       : integer;

 begin

 start;

  k:=0;

  n:=1; s:= -1;

  for m:=1 to maxlongint do

   begin

   s:=s + m;

   if s=0

     then begin

                     inc(k);

                     writeln(k:2,')', m:12, n:12)

     end;

   if s > 0

     then begin

                     n:=n+1;

                     s:=s - 2*n +1

     end

   end

 end.

 

N אינו משתנה פעמיים. באלגוריתמים 5,6 מתקבל אותו הפתרון. באלגוריתם 6 מתקיים בתחילה אי השויון M ≤ 2N-1 . אם N הולך וגדל או M, N גדלים יחד, אי השוויון נשאר. אם רק M גדל אזי s יהיה שלילי. ברגע ש- M מגיע ל-  2N-1 אזי s יהיה אי שלילי, ובשלב הבא תהיה הגדלה של M.

N אף פעם אינו משתנה פעמיים ברציפות. לכן ניתן לכתוב את התכנית בצורה כזו ש- M ישתנה בכל לולאה ו- N ישתנה לפי הצורך.

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

אלגוריתם 5 המשופר מגיע לגלישה ב- sec 0.33 במקום ב- sec 0.60 ואילו אלגוריתם 6 המשופר מגיע במשך שעה ל- 700M במקום ל- 400M אבל לא מצא יותר מ- 12 הזוגות הידועים. כלומר, ישנה התקדמות אבל היא איננה משביעת רצון. ניצחנו את הגלישה אבל החיפוש במספרים הגדולים איטי מאוד. לא מספיקה שעה כדי לגלות את הזוג ה- 13. מובן שכל זוג חדש ידרוש זמן נוסף ובדיקה סדרתית באופן דומה לא תהיה יעילה.

 

אלגוריתם 7

program mn7; { ללא פעולות העזר }

var        m, n, mm, nn      : longint;

             k         : integer;

begin

     start;

     k:= 0;

     m:= 0; n:= 0;

     while m < maxlongint do

     begin

          mm:= 3*m + 4*n + 1;

          nn:= 2*m + 3*n + 1;

          m:= mm; n:=nn;

          inc(k);

          writeln(k:2,')', m:12, n:12);

     end;

end.

 

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

אחרי הזוג (M1,N1)   בא הזוג  (M2,N2)  .

לכן נוסיף את המשוואות הבאות:

(2)

 

(3)

 

 

(4) הנחת האינדוקציה

  

 

על ידי חיסור משוואה (2) מ- (3) ועוד מספר שינויים אריתמטיים נקבל את משוואה (5).

(5)

 

(6)

 

ממשוואות (4) ו- (6) נקבל את משוואה (7).

 

(7)

 

 

(8)

 

 

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

לפי (7) אפשר להפוך את הסדרה. אם יודעים זוג אחד ניתן לקבל ממנו את הזוג הקודם. מספיק להציב ב- (7) את הזוג (M1,N1) ונקבל את (8).

נניח שיש פתרונות שלא ניתן לקבל אותם מהזוג (1,1).  בגלל ש- (M,N) טבעיים ניקח מהפתרונות האלה את הפתרון הקטן ביותר (M2,N2) והוא עונה על (3). נשתמש ב- (8) ונקבל את הזוג (M1,N1) שעונה על (2).

מ- (3) נובע

 

 

ממשוואה זו ומ- (8) נובע ש- M1>0 ו- N1>0. לכן קיבלנו זוג נוסף (M1,N1) של פתרונות שלא נכנס לסדרה הראשית וסותר את ההנחה שהזוג שלקחנו הוא הזוג הקטן ביותר. מכך נובע שהסדרה הראשית כוללת את כל הפתרונות לבעיה וסיימנו את ההוכחה.

 

עכשיו יהיה פשוט לכתוב פתרון לחיפוש כל הפתרונות במסגרת של longint, ולקבל את הפתרון mn7. התכנית מחזירה 12 זוגות כל כך מהר שה- Timer בבורלד לא מצליח אפילו לחשב את הזמן.

 

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

להלן תוצאות ההרצה של כל אלגוריתם:

 

Pentium III (1000 MHz)

386 (20 MHz)

תוכנית

ארך סופי של M

זמן חישוב, שניות

מספר פתרונות

ארך סופי של M

זמן חישוב, שניות

מספר פתרונות

9,350

3,601.02

5

1,265

3,604.49

4

MN1

46,341

398.70

6

13,657

3,600.25

6

MN2

65,536

846.01

7

13,007

3,600.42

6

MN2a

46,341

14.99

6

34,277

3,600.21

6

MN3

65,536

29.77

7

33,454

3,600.14

6

MN3a

46,341

0.50

6

46,341

47.62

6

MN4

65,536

0.66

7

65,536

70.25

7

MN4a

65,535

0.60

7

65,535

36.52

7

MN5

65,535

0.33

7

65,535

21.48

7

MN5a

408,426,657

3,600.04

12

6,490,624

3,600.03

9

MN6

673,942,915

3,600.03

12

10,899,593

3,600.04

9

MN6a

 

0.00

12

 

0.00

12

MN7

 

תוצאות הזוגות שהתקבלו:

M

N

מספר פיתרון

1

1

1

8

6

2

49

35

3

288

204

4

1,681

1,189

5

9,800

6,930

6

57,121

40,391

7

332,928

235,416

8

1,940,449

1,372,105

9

11,309,768

7,997,214

10

65,918,161

46,611,179

11

384,199,200

271,669,860

12

 

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

 

פתרונות לפי אלגוריתם MN7  - ייצוג של "מספרים גדולים" על ידי מערך

M

N

מספר פיתרון

1

1

1

8

6

2

49

35

3

288

204

4

1,681

1,189

5

9,800

6,930

6

57,121

40,391

7

332,928

235,416

8

1,940,449

1,372,105

9

11,309,768

7,997,214

10

65,918,161

46,611,179

11

384,199,200

271,669,860

12

2,239,277,041

1,583,407,981

13

13,051,463,048

9,228,778,026

14

76,069,501,249

53,789,260,175

15

443,365,544,448

313,506,783,024

16

2,584,123,765,441

1,827,251,437,969

17

15,061,377,048,200

10,650,001,844,790

18

87,784,138,523,761

62,072,759,630,771

19

511,643,454,094,368

361,786,555,939,836

20

2,982,076,586,042,449

2,108,646,576,008,245

21

17,380,816,062,160,328

12,290,092,900,109,634

22

101,302,819,786,919,521

71,631,910,824,649,559

23

590,436,102,659,356,800

417,501,372,047,787,720

24

3,441,313,796,169,221,281

2,433,376,321,462,076,761

25

20,057,446,674,355,970,888

14,182,756,556,724,672,846

26

116,903,366,249,966,604,049

82,663,163,018,885,960,315

27

681,362,750,825,443,653,408

481,796,221,556,591,089,044

28

3,971,273,138,702,695,316,401

2,808,114,166,320,660,573,949

29

23,146,276,081,390,728,245,000

16,366,888,776,367,372,354,650

30

134,906,383,349,641,674,153,601

95,393,218,491,883,573,553,951

31

 

 

מקורות

Ginat, D. (1996). Efficiency of algorithms for programming beginners. ACM SIGCSE Bulletin, Vol. 28, No. 1, pp. 256-260

 

אתר המרכז הארצי

אתר הבטים

גליון ינואר 2004

חזרה לתחילת העמוד