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

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

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

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

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

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

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

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

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

רמת קושי:

(שאלה רלוונטית לסטודנטים משנת 2024 בלבד)

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

G = (V, E)

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

w (e) > 0

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

e_{1} \neq = e_{2}

מתקיים

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

.

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

(נדרשת הוכחה מדויקת או דוגמה נגדית של גרף עם

n

קדקודים גדול כרצוננו.)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה81 · 2026 · סמסטר א

★★★★★

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

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

G = (V, E)

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

w (e) > 0

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

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

לכל

e_{1} \neq = e_{2}

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

G^{'} = (V, F)

F \subseteq E

. בתחול, קבוצת הצלעות

F

ריקה. בכל איטרציה:

א. ראשית, נסרוק את רשימת כל רכיבי-הקשירות

C_{1}, ..., C_{k}

בתת-הגרף הנוכחי

G^{'}

, ועבור כל רכיב

C_{i}

נמצא את הצלע

e_{i}

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

C_{i}

(הקלט

G

קשיר, לכן מכל

C_{i}

יוצאת לפחות צלע אחת, ולכן קיימת צלע מזערית שיוצאת מ-

C_{i}

).

ב. שנית, נוסיף לתת-הגרף

G^{'}

את כל הצלעות שמצאנו בשלב א', כלומר נעדכן

F \leftarrow F \cup {e_{1}, ..., e_{k}}

(הצלעות שהוספנו לא דווקא שונות — לדוגמה, הצלע שמחברת בין

C_{2}

ל-

C_{4}

עשויה להיות גם הצלע המזערית שיוצאת מ-

C_{2}

וגם מ-

C_{4}

, ולכן

e_{2} = e_{4}

. כשמוסיפים צלע שמחברת

C_{i}, C_{j}

— שני הרכיבים מתלכדים לכדי רכיב אחד חדש).

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

G^{'}

כולל רכיב-קשירות יחיד, ונחזיר את

G^{'}

כפלט.

הוכיחו/הפריכו: גרף הפלט

G^{'}

הינו חסר מעגלים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה81 · 2026 · סמסטר א

★★★★★

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

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

G = (V, E)

, ונתונות שתי קבוצות של קדקודים זרות

A, B \subseteq V

.

קבוצה של צלעות

D \subseteq E

תקרא "קבוצה מפרידה" אם הסרתה מהגרף תנתק את

A

מ-

B

(כלומר, בגרף

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

לא נותר אף מסלול שמתחיל בקדקוד של

A

ומסתיים בקדקוד של

B

). קבוצה מפרידה מזערית הינה קבוצה מפרידה בעלת גודל

∣ D ∣

מזערי.

קבוצה של צלעות

C \subseteq E

תקרא "קבוצת חתך" אם ישנה קבוצת קדקודים

\emptyset \neq = S \subseteq V

כך ש-

C

זהה לקבוצת כל הצלעות שיוצאות מ-

S

(כלומר

C = {(x, y) \in E ∣ x \in S, y \in / S}

).

הוכיחו/הפריכו כל אחת מהטענות הבאות (טענה א' 11 נק', טענה ב' 22 נק'):

טענה א': "כל קבוצה מפרידה הינה קבוצת חתך."

טענה ב': "כל קבוצה מפרידה מזערית הינה קבוצת חתך."

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה81 · 2026 · סמסטר א

★★★★★

גרפיםזרימה ברשתותהוכחההוכח או הפרך

בבעיית המסלולים המזעריים נתון גרף מכוון

G = (V, E)

עם קדקוד מוצא

s

ומשקלי צלעות

w (e) > 0

. עץ

T

של מסלולים מזעריים (עמ"מ) מ-

s

הוא תת-גרף פורש שבו לכל קדקוד המרחק מ-

s

שווה למרחק ב-

G

(למשל, עץ הפלט של Dijkstra). לכל גרף קלט יש לפחות עמ"מ אחד.

הוכיחו או הפריכו:

> "ישנם מספר עמ"מ שונים

T_{1} \neq = T_{2}

מהמוצא

s

— אם ורק אם יש קדקוד

v

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

s

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מסלולים קצריםגרפיםהוכחההוכח או הפרך

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

G = (V, E)

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

C \subseteq V

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

e = {u, v} \in E

מתקיים

u \in C

או

v \in C

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

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

G^{'} = G

ואת

C

להיות הקבוצה הריקה. נמשיך באיטרציות: (א) נוסיף ל-

C

קדקוד

v

בעל דרגה מרבית בגרף הנוכחי

G^{'}

, ואז (ב) נמחק את

v

מ-

G^{'}

ונסיר את הצלעות הנוגעות בו. הפלט

C

הוא תמיד קבוצה מיוחדת.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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)

עם קדקוד מוצא

s

ומשקלים

w (e)

(חלקם עשויים להיות שליליים). ידוע שאין ב-

G

מעגלים שליליים, ולכן קיים עץ מסלולים מזעריים (עמ"מ)

T

מ-

s

. הגדרה: הגרף

G

ייקרא "מיוחד" אם לכל קדקוד

v \neq = s

קיימת לפחות צלע שלילית אחת שיוצאת מ-

v

.

הכריעו את נכונותן של הטענות הבאות:

א. "לכל גרף מיוחד יש עמ"מ

T

שכולל לפחות צלע שלילית אחת."

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

T

כולל רק צלעות חיוביות.\"

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

מסלולים קצריםגרפיםהוכח או הפרך

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

G = (V, E)

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

w (e) > 0

בצלעות. נתונים גם עץ-פורש מסוים

T = (V, F)

של

G

וצלע מסוימת

e = {u, v} \in F

מהעץ. ניתן להוכיח (ומבחינתכם הדבר נתון), שאם מסירים מהעץ-הפורש

T

את הצלע

e

, אז מתקבלים שני עצים זרים בצורה שנסמנם

T_{1} = (V_{1}, F_{1})

ו-

T_{2} = (V_{2}, F_{2})

. נסמן ב-

G ∖ V_{j}

את הגרף שמתקבל מ-

G

, לאחר שמשמיטים ממנו את כל הקדקודים של

V_{j}

. ניתן להוכיח (ושוב, הדבר נתון עבורכם) כי

T_{1}

הינו עץ-פורש של

G ∖ V_{2}

, וכי

T_{2}

הינו עץ פורש של

G ∖ V_{1}

. הוכיחו/הפריכו את הטענה הבאה:

"אם

T

הינו עפ"מ של

G

אזי (

T_{1}

הינו עפ"מ של

G ∖ V_{2}

ו-

T_{2}

הינו עפ"מ של

G ∖ V_{1}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

בבעיית המסלולים המזעריים נתון גרף מכוון

G = (V, E)

עם קדקוד מוצא

s

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

w (e) > 0

. ברצוננו לחשב, כרגיל, עץ

T

של מסלולים מזעריים (עמ"מ) מ-

s

לכל יתר הקדקודים הנגישים בגרף. כזכור, לכל גרף קלט יש לפחות עמ"מ אחד

T

(למשל, עץ הפלט של האלגוריתם של Dijkstra).

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

> "ישנם מספר עמ"מ שונים

T_{1} \neq = T_{2}

מהמוצא

s

, אם ורק אם יש קדקוד

v

עם מספר מסלולים מזעריים שונים מהמוצא

s

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

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

w (e) > 0

ייחודיים. נזכיר את אלגוריתם Kruskal: (א) מתחילים ביער

F

שבו כל קדקוד הוא עץ נפרד; (ב) בכל איטרציה מוסיפים ליער את הצלע

e^{*}

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

G

המחברות שני עצים שונים של

F

, ומאחדים אותם; (ג) עד שנותר עץ פורש יחיד.

נתבונן בוריאנט הבא, שבו שלב (ב) משתנה:

> בכל איטרציה בוחרים קדקוד כלשהו

v^{*}

שממנו יוצאת לפחות צלע אחת אל מחוץ לעץ שלו

T (v^{*})

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

e^{*}

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

v^{*}

אל מחוץ ל-

T (v^{*})

.

הוכיחו או הפריכו את נכונות הווריאנט (מציאת עפ"מ). זו אינה שאלה על יעילות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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