D1 · Decision Mathematics 1

מתמטיקה להחלטות 1 (D1, מסד WDM01/01, 1 שעות 30 דקות, 75 נקודות, בדיקה ראשונה יוני 2019) היא האפשרות הדיסקרטית של IAL: P1–P2 מוגדרים כנתונים, וכל שיטה היא אלגוריתם — רשימה סופית והגדרות מדויקות. אין פניות לספרטוול נוספות מעבר ל בסיסיות: הנקודות מיועדות לביצוע מדויק של הליכים וניסוח תוצאות בצורה המבוקשת. מדריך זה מכסה אלגוריתמי מיון ואריזה, עצי כיסוי מינימליים, מסלולים קצרים, בעיית הדואר הסיני ובעיית הסוחר המסע, ניתוח מסלול קריטי ותכנון ליניארי. חוקי בית לתשובות על אלגוריתמים:

חוקי הבית לתשובות אלגוריתם:

בפעם; מעבר ללא החלפות מסתיים אותו. המיון מהיר בוחר את הפריט האמצעי ברשימה כצירוז, מפצל את שאר הפריטים לרשימות משנה "קטנות מצירוז" ו"גדולות של הרשימה כציר, מפצל את הפריטים הנותרים לקבוצות "קטן ממציר", "שווה לציר" ו"גדול מציר" (שמירה על כל העתקה); הוא מיישר רק אחר כך את הקבוצות הקטנות והגדולות — תמיד ציין את הציר ואת רשימה לאחר כל חלוקה. הספק קובע את בחירת הפריט האמצעי בשיטה המוגדרת ב הגלסרי, ולכן רשימות התרגילים כאן שמרות על מספר אי-זוגי של פריטים והפריט באמצע הוא ה זה במיקום $\tfrac{n+1}2$. אריזת תאים: first-fit מניח כל פריט בתיק הראשון שיש בו מקום; first-fit decreasing ממיין פריטים בגודל יורד ואז מפעיל first-fit; אריזת תאים מלאה מחפש שילובים הממלאים תיק בדיוק. המילוי הראשון; אריזת מיכל מלא מחפש שילובים הממלאים מיכל בדיוק.

דוגמה פותרת – מיון מהיר (מקורי). מיינים 9, 2, 7, 5, 3, 4, 6. הפריט האמצעי (מיקום 4 מתוך 7) הוא 5: קטנים = 2, 3, 4; גדולים = 9, 7, 6, תוך יצירת 2, 3, 4, 5, 9, 7, 6. תת-רשימת 2, 3, 4 (צירוף 3): 2, 3, 4 – ממוינת. תת-רשימת 9, 7, 6 (צירוף 7): 6, 7, 9 — דוגמה מפורשת — אריזת תאים (מקורי). תיקים בקיבולת 2; פריטים 3, 4, 5, 6, 7, 9

דוגמה פותרת – אריזת מיכלים (מקורית). מיכלים בקיבולת 10; פריטים 7, 5, 4, 3, 6, 2 (סה"כ 27, לכן לפחות 3 קופסאות). התאמה ראשונה: 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8): bins (7,3), (5,4), (6,2). First-fit decreasing: 7, 6, 5, 4, 3, 2: 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7): קופסאות (7,3), (6,4), (5,2) — גם 3 קופסאות.

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

דוגמה מפורטת (מקורית). קצבים AB 4, AC 2, BC 3, BD 5, CD 1: קרוסקל לוקח CD 1, AC 2, BC 3 (B מתחבר — ללא מחזור), ואז דוחה AB 4 ו-BD 5 (מחזורים): סך ה-MST הוא 6. פריים מ-A: AC 2, CD 1 (הקצה הזול ביותר מ-{A,C} לצומת חדש), CB 3: אותו עץ, ו הסך הכולל 6 ✓. תמיד סדרו את הקצבים לפי הסדר שנבחרו ותנו את הסך הכולל.

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

דוגמה מפורטת (מקורית). קצבים AB 4, AC 2, BC 1, BD 5, CD 8. סימונים: A = 0 נצחי; C = 2 קבוע; B = מינימום(4, 2+1) = 3 קבוע; D = מינימום(3+5, 2+8) = 8 קבוע. הדרך הקצרה ביותר מ-A ל-D היא באורך 8: A–C–B–D (מעקב אחורי: 8 = 3 + 5 ב-B, 3 = 2 + 1 ב- C).

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

דוגמה פותרת (מקורית). קצוות AB 4, AC 2, BC 3, BD 5, CD 1 (סה"כ 15). דרגות: A 2, B 3, C 3, D 2 — הקודקודים המדומדים הם B ו-C, ולכן מקצרים את BC (משקל 3): המסלול הסגור הקצר העובר על כל קצה לפחות פעם אחת הוא באורך 15 + 3 = 18.

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

דוגמה פותרת (מקורית). רשת שלמה: AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (ה אי-שוויון המשולש מתקיים לאורך כל הדרך. השכן הקרוב ביותר מ-A: A–C (2), C–B (3), B–D (5), D–A (7): אורך סיור 17 — גב עליון. עץ הכיסוי המינימלי הוא AC + BC + BD = 10, ולכן כפילתו נותן את הגב העליון הגס 20, שמשופר ל17 על ידי קיצורי דרך; גב תחתון מתוך מחיקת A (MST של B, C, D הוא 3 + 5 = 8, פלוס שתי הקשתות הזולות ביותר של A: AC + AB = 2 + 4 = 6) הוא 14. ה- מסלול האופטימלי נמצא בין 14 ל17.

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

דוגמה פתורה (מקורית). פעילויות A (3 ימים), B (4), C (4 לאחר A), D (1 לאחר B), E (5 לאחר C ו-D). המסלול A–C–E = 12 ימים; המסלול B–D–E = 10 ימים: המסלול הקריטי הוא A–C–E והפרויקט נמשך 12 ימים; הפער הכולל של D = 12 − (4 + 1 + 5) = 2 ימים.

מצללים את האזור המאפשר, ואז משתמשים ב-שיטת הסרגל (הזזה של סרגל לאורך ה- הגבלה כחוסר שוויון, כולל $x, y \ge 0$. פתור בעיות דו-משתנים גרפית: הצלל את האזור המקובל, ולאחר מכן השתמש ב-שיטת הסרגל (הזז סרגל לאורך ה שיפוע הפונקציה המטרה) או שיטת הקודקודים (הערכת הפונקציה המטרה בכל קודקוד של אזור הניתן לפתרון). פתרונות שלמים: בדיקת נקודות שלמות בסמוך לקודקוד האופטימלי בתוך האזור.

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

דוגמה מפורטת — תכנון ליניארי (מקורי). מקסמי $P = 3x + 2y$ תחת מגבלות $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. קודקודי אזור הניתן לפתרון הם $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$; הערכת $P$: 0, 21, 24, 20 — המקסימום הוא $P = 24$ בנקודה $(4,6)$, שבה שתי המגבלות מחמירות.

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