אלגוריתמים. שאלה על בעית תזמון פעילויות

אלגוריתמים. שאלה על בעית תזמון פעילויות

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

בספר כתוב האלגוריתם Greedy Activity Selector:
(G.A.S(s,f

[n = len[s
{A={1
j = 1
for i =2 to n
do if s_i>=f_j
{A=AU{i
j = i
return A

כמה שאלות:

שאלה ראשונה:

הקלטים s,f הם מערכים.

s בהכרח ממויין לפי זמני התחלה? מדוע?

שאלה שנייה:

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

יש שלב בהוכחה שלא ברור לי..ארשום אותה את השלב הלא ברור:

תהי {S={1,..,n קבוצת הפעילויות שיש לקבוע להן לוח זמנים. מאחר שאנו מניחים כי הפעילויות ממויינות ע"פ זמני הסיום, הרי שזמן הסיום של פעילות 1
הוא המוקדם ביותר. ברצונו להראות שקיים פתרון אופטימלי המתחיל בבחירה חמדנית, דהיינו, בבחירה של פעילות 1.

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

המשך הוכחה:

נניח A תת קבוצה של S היא פתרון אופטימלי למופע הנתון של בעיית בחירת הפעילויות.
נמיין את הפעילויות ב-A לפי זמני סיומן.
עוד נניח שהפעילות הראשונה ב-A היא הפעילות k. אם k=1, לוח הזמנים של A מתחיל בבחירה חמדנית.

שאלה 4: k=1, זה אומר שהפעילות הראשונה ב-A היא הפעילות הראשונה בקבוצה S (זו שזמן הסיום שלה ב-S הוא הקטן ביותר?)

אם k שונה מ-1, ברצוננו להראות שקיים עבור S פתרון אופטימלי אחר B, שמתחיל בבחירה החמדנית של פעילות 1.
שאלה 5: למה זה מה שרוצים להראות?