איך לתרגל שאלות פרים באלגוריתמים?

באתר prepd תמצאו שאלות פרים באלגוריתמים ממבחנים אמיתיים של האוניברסיטה הפתוחה. השאלות ממוינות לפי רמת קושי.

כמה שאלות פרים יש באלגוריתמים?

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

מה חשוב לדעת על פרים לקראת מבחן באלגוריתמים?

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

אלגוריתמים - פרים

עיצוב וניתוח אלגוריתמים, תכנות דינמי, אלגוריתמים חמדניים וגרפים

סטטיסטיקות מבחנים

תתי-נושאים של גרפים

רמת קושי:

נתון גרף קשיר ולא-מכוון

G = (V, E)

עם משקלים

w (e)

בצלעות. כל המשקלים חיוביים, למעט צלע בודדת

e^{*} = {u, v}

שמשקלה שלילי. לשם פשטות נתון שהמשקלים שלמים וייחודיים:

w (e_{1}) \neq = w (e_{2})

לכל

e_{1} \neq = e_{2}

.

בשאלה זו נבדוק את נכונותה של "הרצה לסירוגין" של האלגוריתם של Prim משני קצותיה

u, v

של הצלע השלילית.

הגדרת ההרצה לסירוגין. מאתחלים שני עצים

T_{u} \leftarrow {u}

ו-

T_{v} \leftarrow {v}

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

T_{u}

צלע בעלת משקל חיובי מזערי מבין הצלעות היוצאות מ-

T_{u}

; ואז
(ב) מוסיפים ל-

T_{v}

צלע בעלת משקל חיובי מזערי מבין הצלעות היוצאות מ-

T_{v}

.

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

T_{u} \cup T_{v}

פורש את כל קדקודי

G

(העצירה עשויה להתרחש בסוף איטרציה או באמצעה, בהתאם לזוגיות

∣ V ∣

).

הנחה מקלה. נתון ששני העצים לא התאחדו באף איטרציה — הצלעות שנוספו ל-

T_{u}

אינן מובילות ל-

T_{v}

ולהפך. לכן מובטח שברגע העצירה

T := T_{u} \cup {e^{*}} \cup T_{v}

הוא עץ פורש של

G

.

הוכיחו או הפריכו את הטענה: "

T

הוא עפ"מ של

G

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 91 · 2022 · סמסטר א

★★★★★

גרפיםעץ פורש מינימליפריםאלגוריתמים חמדנייםהוכח או הפרךהוכחה

ברצוננו למצוא עץ פורש מזערי (עפ"מ), כשהקלט הוא גרף קשיר ולא-מכוון

G = (V, E)

עם משקלים

w (e)

(חלקם עשויים להיות שליליים). הוכיחו כי האלגוריתמים של Prim ושל Kruskal מפיקים עפ"מ גם כאשר חלק מהמשקלים שליליים.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2020 · סמסטר ב

★★★★★

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

ברצוננו למצוא עץ פורש מזערי, כשהקלט הינו, כרגיל, גרף קשיר ולא-מכוון

G = (V, E)

עם משקלים

w (e)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2020 · סמסטר א

★★★★★

עץ פורש מינימליקרוסקלפריםהוכחת נכונותרדוקציההוכחה

שאלות פרים באלגוריתמים עם פתרונות

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