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

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

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

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

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

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

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

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

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

רמת קושי:

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

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)

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

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^{'} = 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)

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

C \subseteq V

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

e = {u, v} \in E

מתקיים

u \in C

או

v \in C

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

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

G

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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 · סמסטר א

★★★★★

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

נתונה נוסחת 3-CNF

φ = φ_{1} \land \dots \land φ_{m}

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

x_{1}, \dots, x_{n}

בזה אחר זה, ולכל משתנה

x_{i}

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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