|
|
עמוד:201
נניח שאפשר לבצע כל תת-מטלה ביחידת זמן אחת . א . מאחר שהגרף G אינו מכיל מעגל , האם חייב להיות לפחות קדקוד אחד G-1 שאין לו קדקוד קודם ? נמקו את תשובתכם . ב . בתרשים הנתון מהי תת-המטלה שאין לה תת-מטלה קודמתי ג . איזו תת-מטלה ניתן לבצע ביחידת הזמן הראשונה ? ד . ברגע שתת-מטלה 1 תושלם , הצע תהליך ביצוע של פעולות כזה שלאחריו יתקבל גרף חדש שבו תת-המטלות 2 3-ו מיוצגות בעזרת קדקודים שאין להם קדקודים קודמים . ה . אילו תת-מטלות ניתן לבצע ביחידת הזמן השנייה ? ו . איזו תת-מטלה ניתן לבצע ביחידת הזמן השלישית ? ז . אילו תת-מטלות ניתן לבצע ביחידת הזמן הרביעית ? ח . איזו תת-מטלה ניתן לבצע ביחידת הזמן החמישית ? ט . לאור האמור לעיל , כתבו אלגוריתם מילולי בעברית מבנית לפתרון הבעיה הנתונה . י . מה צריך הקלט לכלול ? יא . נניח שמספר התת-מטלות אינו ידוע . . 1 באיזה ייצוג של גרף תשתמשו ? נמקו את תשובתכם . . 2 כיצד אפשר לקבוע בכל צעד של האלגוריתם לאיזה קדקוד אין קדקוד קודם ? . 3 כיצד אפשר לקבוע אילו תת-מטלות ניתן לבצע באותה יחידת זמן ? . 4 איזה מידע יש לשמור בכל צומת בגרף ? . 5 לאור האמור לעיל , כתוב אלגוריתם הקובע אילו תת-מטלות ניתן לבצע בעת ובעונה אחת בכל יחידת זמן . יב . האם ייתכן שגרף זה , המתאר את סדר הקדימות בין תת-המטלות , יכיל מעגל ? נמקו את תשובתכם . יג . כיצד ניתן לגלות , בעזרת האלגוריתם שהצעתם בסעיף הקודם , אם הגרף G מכיל מעגל ? יד . כתבו תכנית בשפה עילית אשר קולטת זוגות סדורים של תת-המטלות , כאשר תת-המטלה הראשונה בזוג סדור זה צריכה להתבצע לפני תת-המטלה השנייה בזוג סדור זה . התכנית תדפיס את מספר יחידות הזמן הקטן ביותר שבו ניתן
|
|