איך לתרגל שאלות דייקסטרה באלגוריתמים?

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

כמה שאלות דייקסטרה יש באלגוריתמים?

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

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

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

אלגוריתמים - דייקסטרה

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

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

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

רמת קושי:

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

G = (V, E)

עם קדקוד מוצא

s \in V

ויעד

t \in V

s \neq = t

, ועם משקלים

w (e) \neq = 0

על הצלעות. בגרף ישנן

Θ (∣ V ∣^{2})

צלעות במשקל שלילי, וגם

Θ (∣ V ∣^{2})

צלעות במשקל חיובי. מסלול

P : s ⇝ t

ב-

G

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

Θ (∣ V ∣^{2 + c})

ומעלה (

c

מציין כאן קבוע חיובי).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

גרפיםדייקסטרהמסלולים קצריםרדוקציה

השאלה עוסקת במימושים שונים לתור-קדימויות עם

n

מפתחות, במסגרת הפעלת האלגוריתם של Dijkstra או של Prim. שלושה מימושים: רשימה דו-כיוונית לא ממוינת, ערימה-בינארית, וערימת-פיבונאצ'י (שזמני-הריצה שלה amortized). לכל אורך התשובה השמיטו את הסימנים האסימפטוטיים

O, Θ

. נסמן

n = ∣ V ∣

m = ∣ E ∣

.

(א) השלימו את זמני-הריצה של כל פעולה בכל מימוש.

(ב) רשמו את זמן-הריצה הכולל של Dijkstra/Prim בכל מימוש (בניית התור

+ n \cdot

שליפת-מינימום

+ m \cdot

הקטנת-מפתח), וקבעו לאילו צפיפויות עדיף כל מימוש.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

עם קדקוד מוצא

s

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

w (e) > 0

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

T

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

s

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

T

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

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

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

T_{1} \neq = T_{2}

מהמוצא

s

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

v

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

s

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

הקלט לאלגוריתם Dijkstra הוא גרף

G

עם קדקוד מוצא

s

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

w (e)

, והפלט הוא עץ מסלולים מזעריים (עמ"מ) מ-

s

.

הוכיחו או הפריכו בקצרה:

> "אם

T

הוא עמ"מ ביחס למשקלים

w (e)

, אזי

T

הוא עמ"מ גם ביחס למשקלים

w^{'} (e) := k_{1} \cdot w (e) + k_{2}

, כאשר

k_{1}, k_{2}

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

עם משקלים

w (e) > 0

וקדקוד מקור

s

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

s

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

G

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

T

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

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

> בכל איטרציה

i

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

d_{i}

, כך שהעץ

T

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

G

הוא לכל היותר

d_{i}

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתונה רשת-תחבורה קשירה עם

n

עיירות המחוברות ב-

m

כבישים. ברצוננו לרכוש רכב עם מיכל-דלק שגודלו

f

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

\leq n

) הנדרשת לחצייתו. בכל עיירה יש תחנת-דלק, אך אין תחנות-דלק על הכבישים (צריכת הדלק בתוך עיירה זניחה).

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

f

. (לא יינתנו יותר מ-3 נק' לאלגוריתם הרץ בזמן

Θ (n^{c})

עבור קבוע

c > 2

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

שאלות דייקסטרה באלגוריתמים עם פתרונות

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