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

הצגה ותרגול של חישובי סיבוכיות תוך חזרה על אלגוריתמים לפתרון בעיות בסיסיות

ארנה מילר, אורט מעלות

 

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

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

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

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

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

 

לאתר עיצוב תכנה

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

חזרה