איך לתרגל שאלות הוכחת נכונות באלגוריתמים?

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

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

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

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

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

אלגוריתמים - הוכחת נכונות

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

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

תתי-נושאים של הוכחת נכונות

רמת קושי:

נתון גרף לא מכוון

G = (V, E)

משוקלל, עם משקלים שלמים וחיוביים

w (e) > 0

לכל הצלעות. קבוצת צלעות

F \subseteq E

נקראת מנתקת-מעגלים אם לאחר הסרתה לא נותרים מעגלים בגרף, כלומר

G^{'} = (V, E ∖ F)

חסר-מעגלים. משקלה של קבוצת צלעות

F

הוא

w (F) = \sum_{e \in F} w (e)

.

הציגו אלגוריתם למציאת קבוצת צלעות מנתקת-מעגלים בעלת משקל מזערי, והוכיחו את נכונותו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון גרף לא מכוון

G = (V, E)

. תת-קבוצה של קדקודים

C \subseteq V

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

e = {u, v} \in E

מתקיים

u \in C

או

v \in C

(כיסוי קדקודים). ברצוננו למצוא קבוצה מיוחדת מזערית.

הציגו אלגוריתם למציאת קבוצה מיוחדת מזערית כאשר נתון ש-

G

הוא יער (גרף חסר מעגלים), והוכיחו את נכונותו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

אלגוריתמים חמדנייםגרפיםהוכחת נכונות

נתון גרף לא מכוון

G = (V, E)

. מעגל פשוט ב-

G

נקרא ענק אם הוא עובר בכל הקדקודים (מעגל המילטוני). בבעיית המעגלים הענקיים, אלגוריתם-הכרעה נדרש לקבוע האם קיים ב-

G

מעגל ענק (משיב "כן"/"לא"), ואלגוריתם-חיפוש נדרש למצוא מעגל ענק אם קיים, ואחרת לדווח שאין.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

רדוקציהגרפיםהוכחת נכונותהוכחה

נתונה רשת-זרימה: גרף מכוון

G = (V, E)

עם מקור

s \in V

ועם יעד

t \in V

(כאשר

s \neq = t

), ועם קיבולות חיוביות

c (e) > 0

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

u, v

לכל היותר אחת מבין הצלעות

(u, v)

(v, u)

נמצאת בגרף. בשאלה זו "זרימה-חוקית" הינה פונקציה

f : E \to R

, המקיימת את שתי הדרישות הבאות:

(א) לכל קדקוד

v \neq = s, t

מתקיים

\sum_{(u, v) \in E} f (u, v) = \sum_{(v, w) \in E} f (v, w)

(חוק שימור-הזרימה, כרגיל).

(ב) לכל צלע

e \in E

מתקיים

f (e) \geq c (e)

(הקיבולת חוסמת בשאלה זו את הזרימה מלמטה דווקא ולא מלמעלה, בניגוד לרגיל).

נניח שנתונה לכם זרימה-חוקית

f

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

זרימה ברשתותרדוקציההוכחת נכונותאלגוריתמים

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

G = (V, E)

עם משקלים

w (e)

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

עם משקלי צלעות

w (e) > 0

. תהי

\emptyset \neq = S ⊊ V

. למת-החתך קובעת: אם

e^{*}

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

S

ל-

V ∖ S

), אזי יש עץ פורש מזערי

T^{*}

המקיים

e^{*} \in T^{*}

.

לפניכם ניסיון הוכחה:
1. יהי

T

עץ פורש מזערי. אם

e^{*} \in T

אז אין מה להוכיח. אחרת,
2. כל עץ פורש חייב לחבר בין

S

ל-

V ∖ S

, ולכן ישנה צלע

e \in T

החוצה את החתך.
3. תת-הגרף החדש

T^{*} := (T \cup {e^{*}}) ∖ {e}

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

T

עפ"מ אז גם

T^{*}

עפ"מ, המקיים

e^{*} \in T^{*}

.

א. החלק השגוי היחיד בטיעון הוא מספר 3. הסבירו במילים מהי הטעות. (11 נק')

ב. הציגו דוגמה נגדית ממושקלת פשוטה של

G, T, e, e^{*}

הממחישה את הטעות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

עם משקלי צלעות

w (e) > 0

ייחודיים. נתבונן בוריאנט הבא של Kruskal למציאת עפ"מ, שבו שלב הבחירה משתנה:

> בכל איטרציה בוחרים באקראי בהתפלגות אחידה את אחד העצים

T

ביער, ואז מוסיפים ליער את הצלע

e

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

T

ליתר הגרף.

(שאר האלגוריתם כמו Kruskal המקורי: מתחילים ביער של קדקודים בודדים, ומסתיימים כשנותר עץ יחיד.)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון גרף מכוון

G = (V, E)

עם משקלים

w (e) > 0

וקדקוד מקור

s

. בנוסף נתון עץ פורש מכוון

T

המושרש ב-

s

. הציגו אלגוריתם המכריע האם

T

הוא אכן עץ מסלולים מזעריים (עמ"מ) מ-

s

. האלגוריתם חייב לרוץ מהר יותר אסימפטוטית מ-Dijkstra, ופלטו הוא "כן (Accept)" או "לא (Reject)" בלבד (אינכם נדרשים לחשב עמ"מ בעצמכם).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מסלולים קצריםהוכחת נכונותגרפיםסיבוכיות

נזכיר את בעיית המסלולים המזעריים ממקור יחיד: נתון גרף מכוון

G = (V, E)

עם משקלים

w (e) > 0

וקדקוד מקור

s

; מחפשים מסלולים מזעריים מ-

s

ליתר הקדקודים. נניח לשם פשטות שאין ב-

G

שני קדקודים שונים בעלי אותו מרחק מהמקור. יהי

T

העץ ש-Dijkstra מתחזק במהלך ריצתו.

הוכיחו באינדוקציה את הטענה:

> בכל איטרציה

i

של Dijkstra יש מספר ממשי

d_{i}

, כך שהעץ

T

פורש בסיום אותה איטרציה בדיוק את כל הקדקודים שמרחקם מהמקור ב-

G

הוא לכל היותר

d_{i}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

עם משקלים

w (e)

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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