הצגת חשיבות היעילות על ידי שיפורים באלגוריתם

שי שגב

ד"ר יבגני קנל

תיכון מקיף עירוני א' אשקלון

רכז מגמת מדעי המחשב, תיכון מקיף עירוני א' אשקלון

Shai_segev@walla.co.il

kanel@netvision.net.il

 

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

 

יעילות של אלגוריתם נמדדת על ידי פרמטרים ידועים מראש אך אינה מוחשית ללומד. מדובר על תכניות קטנות בדרך כלל ולכן גם יעילות נמוכה אינה משפיעה על זמן הריצה בפועל. המחשבים "החזקים" הנמצאים בשימוש יוכלו להריץ תכניות לא יעילות של תלמידים בזמן מהיר מאוד. כך גם בדוגמאות שהוצגו על ידי ד"ר דוד גינת במאמרו efficiency of algorithms for programming beginners. בדוגמה שלפנינו ניתן לראות את השינויים המשמעותיים בזמן ריצה פיזי במחשב כתלות באלגוריתם. המתכנתים המתחילים אינם מבינים את חשיבות היעילות ובדך כלל שינוי של מאיות שנייה או אלפיות שנייה אינו משחק תפקיד.

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

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

דוגמה נוספת היא הבעיה הבאה: נרשמים המספרים הטבעיים מ- 1 עד M. המספר N שהוא אחד המספרים הללו נמחק. חישבנו את סכום המספרים לפני N ואחרי N. לדוגמא: אם   M=10 , N=7  הסכומים יהיו 21, 27. צריך למצוא M,N  כאלו כך שהסכומים יהיו שווים.

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

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

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

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

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

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

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

לבסוף יוצגו תוצאות מסכמות ומסקנות אופרטיביות.

לאתר המרכז

לכנס תשס"ד

חזרה