234247 - אלגוריתמים 1


spring_15_b
huffman

נתונה טבלת שכיחויות של טקסט TT באורך 100, מעל א"ב בן 6 אותיות:

abcdef30181716109 \begin{array}{|l|l|l|l|l|l|} \hline a&b&c&d&e&f \\\hline 30&18&17&16&10&9 \\\hline \end{array}

א. כמה ביטים, לכל הפחות, נדרשים לקודד את הטקסט כאשר לכל אות קוד באורך זהה?

ב. כמה ביטים נדרשים לקודד את הטקסט כאשר הוא מקודד בקוד הופמן?

ג. נתון העץ הבא:

תנו דוגמה למשקלים על העלים כך שזהו עץ ההופמן המתקבל, או נמקו מדוע לא קיימים כאלו.

ד. הוכיחו/הפריכו: אם בטקסט מסויים השכיחות של האות aa היא 12\frac{1}{2}, אז מספר הביטים שמקודדים את aa בקוד הופמן עבור הטקסט הוא 1.

shortest_path
spring17_a

נתונים גרף מכוון G=(V,E)G = (V,E), שני צמתים s,tVs,t \in V וקבוצת צמתים UVU \subseteq V. הציעו אלגוריתם המכריע האם קיים מסלול קצר ביותר מ-ss ל-tt שעובר דרך כל צמתי UU.

mst

יהיו G1=(V,E1)G_1 = (V,E_1) ו-G2=(V,E2)G_2 = (V, E_2) שני גרפים לא מכוונים וקשירים מעל אותה קבוצת צמתים, עם משקלות על הקשתות. יהיו T1=(V,E1)T_1 = (V, E'_1) ו-T2=(V,E2)T_2 = (V, E'_2) שני עצים פורשים מינימום של G1G_1 ו-G2G_2 בהתאמה. נסמן ב-GG את גרף האיחוד של G1G_1 ו-G2G_2 - G=(V,E1E2)G = (V, E_1 \cup E_2).

1. הוכיחו/הפריכו - כל עץ פורש מינימום של GG מכיל קשתות מ-E1E2E'_1 \cup E'_2 בלבד.

2. הוכיחו/הפריכו - קיים עץ פורש מינימום של GG המכיל קשתות מ-E1E2E'_1 \cup E'_2 בלבד.

3. הציעו אלגוריתם שרץ בסיבוכיות זמן של O(VlogV)O(|V|\log |V|) ובהינתן G1,G2,T1,T2G_1,G_2,T_1,T_2 מוצא עץ פורש מינימום של GG.

winter17-18
shortest_path
dijkstra

נתון גרף מכוון G=(V,E)G = (V,E) וזוג צמתים s,tVs,t \in V. פניה מוגדרת ע"י שלשת צמתים (u,v,w)(u,v,w). מסלול עובר דרך פניה (u,v,w)(u,v,w) אם הצמתים u,v,wu,v,w מופיעים במסלול ברצף. קבוצת הפניות בגרף היא

T={(u,v,w):(u,v)E(v,w)E}T = \{(u,v,w) : (u,v) \in E \land (v,w) \in E\}.

ונתונה תת קבוצה של פניות מסוכנות, DTD \subseteq T.

הציעו אלגוריתם המוצא מסלול מ-ss ל-tt העובר דרך מינימום פניות מסוכנות.

dfs

נתון גרף מכוון G=(V,E)G = (V,E).

א. צומת vVv \in V יקרא יעד גלובלי אם לכל צומת uVu \in V קיים מסלול מ-uu ל-vv.

גרף GG נקרא גרף מעקפים אם לכל u,vVu,v \in V קיים wVw \in V כך שקיים מסלול מכוון מ-uu ל-ww ומ-vv ל-ww.

הוכיחו: GG גרף מעקפים אמ"מ קיים ב-GG יעד גלובלי.

ב. הציעו אלגוריתם יעיל ככל האפשר המכריע האם GG גרף מעקפים.

max_flow
proof

בהינתן רשת זרימה, N=(G,s,t,c)N = (G, s, t, c), נאמר שזרימה f:ERf:E \to \mathbb{R} היא חסרת מעגלים אם לכל מעגל ברשת הזרימה יש לפחות קשת אחת שהזרימה עליה היא 0. כלומר, הקשתות בהן הזרימה חיוביות ממש משרות גרף חסר מעגלים.

הוכיחו כי לכל רשת זרימה, קיימת זרימת מקסימום חסרת מעגלים.

shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות חיוביות על הקשתות, ויהא sVs \in V. נאמר כי קשת היא שימושית אם קיים מסלול קל ביותר מ-ss ל-vv שהקשת uvuv היא האחרונה בו. נאמר שמסלול מ-ss ל-tt הוא שני קל ביותר אם משקלו הוא הקל ביותר מבין כל המסלולים מ-ss ל-tt שמשקלם גדול ממש ממשקל המסלול הקל ביותר מ-ss ל-tt.

  1. יהא PP מסלול מ-ss ל-tt. הוכיחו כי PP מסלול קל ביותר מ-ss ל-tt אם ורק אם כל קשתות PP שימושיות.
  2. יהא PP מסלול מ-ss ל-tt. הוכיחו כי אם PP הוא שני קל ביותר אז ב-PP יש בדיוק קשת אחת שאינה שימושית.
  3. הציעו אלגוריתם, יעיל ככל שתוכלו, המוצא מסלול שני קל ביותר מ-ss ל-tt או מודיע כי לא קיים כזה.
spring_15_b
max_flow
binary_search

בשער הטכניון עובדים nn מאבטחים g1,,gng_1, \ldots, g_n. עליכם לקבוע עבורם את לוח המשמרות. ישנן mm משמרות, וכל מאבטח הגיש לכם רשימה עם משמרות אותן הוא יכול לבצע.

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

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

על האלגוריתם לרוץ בזמן O(m2n)O(m^2n).

ב. לאחר שיושם לוח המשמרות שקבע האלגוריתם מסעיף א', התלוננו חלק מהמאבטחים על חוסר שוויון בחלוקת המשמרות.

הציעו אלגוריתם הקובע משמרות תחת האילוצים של סעיף א', כך שמספר המשמרות המקסימלי שיעשה מאבטח כלשהו הוא קטן ככל האפשר.

bfs
dynamic_programming

יהא G=(V,E)G = (V, E) גרף לא מכוון, ויהא sVs \in V. הצע אלגוריתם המחשב לכל צומת vVv \in V את מספר המסלולים הקצרים ביותר מ-ss ל-vv.

shortest_path
spring_18_b

נתון גרף מכוון, G=(V,E)G = (V, E). הפיכה של קשת uvEuv \in E משמעותה הסרה של הקשת מ-EE והוספה של הקשת האנטי מקבילה שלה ל-EE, כלומר EE{uv}{vu}E \leftarrow E \setminus \{uv\} \cup \{vu\}.

א. נתון הגרף הבא:

tikz

הפכו 2 קשתות כך שיהיה מסלול מ-ss ל-tt.

ב. הציעו אלגוריתם שבהינתן גרף מכוון, G=(V,E)G = (V, E), וזוג צמתים s,tVs, t \in V מוצא את מספר הקשתות המינימלי שיש להפוך על מנת שיהיה מסלול מ-ss ל-tt. יש לנתח סיבוכיות ולהוכיח נכונות.

ג. נתון גרף מכוון, G=(V,E)G = (V, E), זוג צמתים, s,tVs, t \in V,ופונקציית משקל, w:ER+w:E \to \mathbb{R}^+. הציעו אלגוריתם שהופך kk קשתות לכל היותר כך שבגרף המתקבל משקל מסלול קל ביותר מ-ss ל-tt הוא קטן ככל האפשר. יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

spanning_tree
spring17_a
mst

נתונים גרף לא מכוון וקשיר G=(V,E)G = (V,E) ופונקציית משקל על הקשתות w:ERw:E \to \mathbb{R}. כמו כן, נתון ש-E=V+99|E| = |V| + 99 הציעו אלגוריתם המוצא עץ פורש מינימום לגרף GG.

topological_sort

יהא G=(V,E)G = (V,E) גרף מכוון. קבוצה AVA \subseteq V תקרא גרעין אם לכל u,vAu,v \in A מתקיים (u,v)E(u,v) \notin E ולכל vVAv \in V \setminus A קיים aAa \in A כך ש-(a,v)E(a,v) \in E.

הציעו אלגוריתם המוצא גרעין בגרף מכוון חסר מעגלים ופועל בזמן O(V+E)O(|V| + |E|).

עליכם לנתח את סיבוכיות האלגוריתם ולהוכיח את נכונותו.

mst
spring_18_b

נתון גרף לא מכוון, G=(V,E)G = (V, E), ופונקציית משקל w:ERw:E \to \mathbb{R}.

א. הוכיחו/הפריכו: אם ל-GG קיים עפ"מ שמכיל קשת במשקל xx אז לכל קשת במשקל xx קיים עפ"מ של GG שמכיל אותה.

ב. הציעו אלגוריתם שבהינתן גרף לא מכוון, G=(V,E)G = (V, E), פונקציית משקל, w:ERw:E \to \mathbb{R}, וערך xx, מוצא את כל הקשתות במשקל xx כך שקיים עפ"מ של GG שמכיל אותן. על האלגוריתם לרוץ בזמן O(E+V)O(E + V)יש לנתח סיבוכיות ולהוכיח נכונות.

ג. הציעו אלגוריתם שבהינתן גרף לא מכוון, G=(V,E)G = (V, E), ופונקציית משקל, w:ERw:E \to \mathbb{R} מוצא את כל הקשתות כך שקיים עפ"מ של GG שמכיל אותן. על האלגוריתם לרוץ בזמן O(ElogV)O(E \log V). יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

spring_9_b
mst

יהא G=(V,E)G = (V,E) גרף עם משקלות על הקשתות. נניח ונתון בידנו עפ"מ TT של GG. מוסיפים כעת ל-GG צומת חדש, vv, וקשתות ממושקלות מ-vv לחלק מצמתי הגרף. את הגרף המתקבל נסמן ב-GG'.

א. הוכיחו/הפריכו: כל עפ"מ של GG' מכיל את TT.

ב. הציעו אלגוריתם הרץ בזמן O(VlogV)O(V\log V) המוצא עפ"מ של GG'. הוכיחו נכונות ונתחו סיבוכיות.

dfs

יהא G=(V,E)G = (V, E) גרף לא מכוון וקשיר ו-TT עץ DFS\text{DFS} שלו. נסמן את גובהו של TT ב-hh.

א. הוכיחו כי מספר הקשתות של GG הוא לכל היותר Vh|V| \cdot h.

ב. הוכיחו כי ב-GG קיים מסלול פשוט שאורכו לפחות EV\frac{|E|}{|V|}.

ג. הציעו אלגוריתם למציאת מסלול פשוט שאורכו לפחות EV\frac{|E|}{|V|} בגרף לא מכוון וקשיר. על האלגוריתם לרוץ בזמן O(V+E)O(V + E).

mst
min_cut

יהא G=(V,E)G = (V,E) גרף לא מכוון וקשיר עם משקלות על הקשתות. תהא eEe' \in E ו-kk מספר טבעי.

הציעו אלגוריתם המכריע האם ניתן לשנות את משקלן של kk קשתות כלשהן, השונות מ-ee', בגרף כך שלאחר השינוי קיים עפ"מ של GG המכיל את ee'.

greedy

ישנן nn תמונות בתערוכה, המפוזרות לאורך מסדרון (חד ממדי). התמונות מפוזרות בנקודות x1<x2<<xnx_1 < x_2 < \dots < x_n.

אנו מעוניינים להציב שומרים בתערוכה. כל שומר מכסה רדיוס של 1 סביבו (כלומר אם הוא ניצב בנקודה yRy \in \mathbb{R}, אז הוא משגיח על התמונות בקטע [y1,y+1][y - 1, y + 1]). ניתן להציב שומרים רק בנקודות בהן תלויות תמונות.

הציעו אלגוריתם חמדן הרץ בזמן O(n)O(n) ומחשב את מספר השומרים המינימלי שיש להציב כך שלכל תמונה יהיה לפחות שומר אחד שמשגיח עליה.

spring_15_b
dfs
bridge

בגרף לא מכוון וקשיר קשת היא גשר אם הסרתה הופכת את הגרף ללא קשיר.

א. הוכיחו: אם בגרף לא מכוון וקשיר קיים גשר, אז לא ניתן לכוון את קשתות הגרף כך שהגרף המתקבל יהיה קשיר היטב.

ב. הוכיחו: יהי G=(V,E)G = (V, E) גרף לא מכוון וקשיר. יהי vVv \in V הצומת הראשון שנכנס למחסנית בריצת DFS כלשהי על הגרף. אזי vv הוא שורש של עץ ה-DFS המתקבל.

ג. הוכיחו: תהי (u,v)(u,v) קשת בעץ DFS. אם לא קיימת בגרף "קשת עוקפת" היוצאת מצאצא של vv (יתכן vv עצמו), אז (u,v)(u,v) היא גשר.

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

scc
spring17_b

נתונים גרף מכוון G=(V,E)G = (V, E) ופונקציית משקל על הקשתות w:ERw: E \to \mathbb{R}.

נגדיר: vVv \in V הוא צומת שלילי אמ"מ הוא חלק ממעגל שלילי כלשהו בגרף (המעגל לא בהכרח פשוט - ייתכנו צמתים שעוברים דרכם יותר מפעם אחת).

הציעו אלגוריתם הרץ בסיבוכיות זמן O(VE)O(|V||E|) ומחזיר את קבוצת כל הצמתים השליליים ב-GG.

רמז: ניתן להשתמש בגרף הרכיבים הקשירים היטב של GG.

dijkstra

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות אי-שליליות על הקשתות, ויהא sVs \in V.

הציעו אלגוריתם המוצא לכל צומת vVv \in V את משקלו של מעגל קל ביותר (לאו דווקא מעגל פשוט) המכיל הן את ss והן את vv.

dfs

גרף מכוון יקרא טורניר אם לכל שני צמתים u,vVu,v \in V קיימת בדיוק אחת משתי הקשתות (u,v)(u,v) או (v,u)(v,u) (אם הצמתים בגרף מייצגים שחקנים וכל שני שחקנים שיחקו בניהם בדיוק פעם אחת אז הקשתות מסמלות איזה שחקן ניצח בכל משחק).

צומת uu הוא שורש בגרף אם לכל vVv \in V קיים מסלול מכוון מ-uu ל-vv.

  1. הוכיחו: בכל טורניר קיים שורש.
  2. הציעו אלגוריתם המוצא שורש של טורניר בזמן O(E+V)O(|E| + |V|).
dag

יהא G=(V,E)G = (V, E) גרף מכוון. הציעו אלגוריתם המחלק את קשתות הגרף לשתי קבוצות זרות E=E1E2E = E_1 \cup E_2, כך שהגרפים (V,E1)(V, E_1) ו-(V,E2)(V, E_2) הם חסרי מעגלים מכוונים. על האלגוריתם לרוץ בזמן O(V+E)O(|V| + |E|).

shortest_path

נתון גרף מכוון G=(V,E)G = (V, E) וצומת sVs \in V ושתי פונקציות משקל w1,w2:ERw_1,w_2: E \to \mathbb{R}. ידוע שאין בגרף מעגלים שליליים לפי שתי הפונקציות הנתונות.

הציעו אלגוריתם אשר מוצא לכל vVv \in V מסלול קל ביותר מ-ss ל-vv ביחס ל-w2w_2, מבין כל המסלולים הקלים ביותר מ-ss ל-vv ביחס ל-w1w_1. על האלגוריתם לרוץ בסיבוכיות O(VE)O(VE).

spring_9_b
dynamic_programming

יהיו {a1,,an}\{a_1, \ldots, a_n\} קבוצה של מספרים טבעיים.

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

{iIai}I[n] \left\{ \sum_{i \in I} a_i \right\}_{I \subseteq [n]}

כלומר, על האלגוריתם לחשב את קבוצת כל אותם מספרים הניתנים להצגה כסכום של חלק מאיברי הסדרה. כך למשל עבור הקלט {1,2,5}\{1,2,5\} הפלט הוא {0,1,2,3,5,6,7,8}\{0,1,2,3,5,6,7,8\} (0 עבור I=I = \emptyset).

על האלגוריתם לרוץ בזמן O(ni=1nai)O\left(n\displaystyle{\sum_{i = 1}^n}a_i\right). הוכיחו נכונות ונתחו סיבוכיות.

ב. הציעו אלגוריתם המכריע האם קיימת קבוצה I[n]I \subseteq [n] כך ש-

iIai=j[n]Iaj \sum_{i \in I}a_i = \sum_{j \in [n] \setminus I}a_j

הוכיחו נכונות ונתחו סיבוכיות.

shortest_path
bellman_ford

נתונים nn משתנים x1,,xnx_1,\ldots,x_n ו-mm (mnm \geq n) אי-שוויונים מהצורה xixjckx_i - x_j \leq c_k כך ש-ckc_k מספר ממשי לכל 1km1 \leq k \leq m.

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

dynamic_programming
spring_18_a

נתון קטע [s,e][s, e] ונתונים nn אינטרוולים A={a1,,an}A = \{a_1, \ldots, a_n\}. עבור אינטרוול aa נסמן ב-s(a)s(a) ו-e(a)e(a) את נקודת ההתחלה ונקודת הסיום שלו בהתאמה.

תת קבוצה של אינטרוולים, BAB \subseteq A,מכסה את הקטע [s,e][s,e] אם לכל נקודה p[s,e]p \in [s, e] קיים אינטרוול aBa \in B כך ש-s(a)pe(a)s(a) \leq p \leq e(a).

נתונה בנוסף פונקציית משקל אי-שליליתw:AR+w:A \to \mathbb{R}^+.

ברצוננו למצוא קבוצה קלה ביותר של אינטרוולים שמכסה את הישר (משקל הקבוצה הוא סכום משקלי האינטרוולים שבקבוצה).

הערות:

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

א. עבור הקלט הבא, מצאו קבוצה קלה ביותר של אינטרוולים שמכסה את הקטע [0,10][0, 10] (הקיפו בעיגול את האינטרוולים שבקבוצה).

tikz

ב. הוצע האלגוריתם החמדן הבא:

  • אתחל CC \leftarrow \emptyset.
  • כל עוד CC אינה מכסה את הקטע [s,e][s,e] בחר את האינטרוול הכי קל מ-ACA \setminus C הוסף אותו ל-CC והסר מ-AA את כל האינטרוולים שמכוסים על ידי CC.
  • החזר את CC.

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

tikz

ג. הציעו אלגוריתם שבהינתן קטע [s,e][s, e] וקבוצת אינטרוולים A={a1,,an}A = \{a_1, \ldots, a_n\}. מוצא קבוצה קלה ביותר של אינטרוולים שמכסה את הקטע. יש לנתח סיבוכיות, אין צורך להוכיח נכונות.

dynamic_programming
scc

יהא G=(V,E)G = (V, E) גרף מכוון ותהא L:VRL:V \to \mathbb{R} פונקציה המתאימה לכל צומת מספר ממשי. לכל צומת vVv \in V נסמן ב-R(v)R(v) את קבוצת הצמתים אליהם יש מסלול מכוון מ-vv ונגדיר l(v)=minwR(v)L(w)l(v) = \displaystyle{\min_{w \in R(v)}} L(w).

  1. הציעו אלגוריתם שמחשב את l(v)l(v) לכל צומת vVv \in V כאשר GG חסר מעגלים.
  2. הציעו אלגוריתם שמחשב את l(v)l(v) לכל צומת vVv \in V כאשר GG גרף כללי.
winter_14-15_a
mst
shortest_path
proof

נתון גרף ממושקל (משקלים על הקשתות), לא מכוון, קשיר וחסר מעגלים שליליים, GG. עבור קבוע חיובי, cc, נסמן ב-GG' את הגרף המתקבל מ-GG אחרי הוספת cc למשקל של כל קשת, ונסמן ב-GG'' את הגרף המתקבל מ-GG אחרי הכפלת משקל כל קשת ב-cc.

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

א. אם TT הוא עפ"מ של GG, אז TT הוא עפ"מ של GG'.

ב. אם TT הוא עפ"מ של GG, אז TT הוא עפ"מ של GG''.

ג. אם PP מסלול קל ביותר בין שני צמתים ב-GG, אז PP הוא מסלול קל ביותר ביניהם גם ב-GG'.

ד. אם PP מסלול קל ביותר בין שני צמתים ב-GG, אז PP הוא מסלול קל ביותר ביניהם גם ב-GG''.

huffman

הוכיחו/הפריכו את הטענות הבאות המתייחסות לעצי האפמן:

  1. אם כל תו מופיע בקובץ בתדירות קטנה מ-13\frac{1}{3} אזי בהכרח בעץ האפמן לא תהיה מילת קוד באורך 1.
  2. אם קיים תו שתדירותו גדולה מ-25\frac{2}{5} אזי מילת הקוד המתאימה לו בעץ האפמן הינה בהכרח מאורך 1.
  3. האורך הממוצע של מילת קוד בעץ האפמן הינו Ω(logn)\Omega(\log n) כאשר nn הינו מספר התווים.
matching
greedy
dynamic_programming

נתון עץ לא מכוון T=(V,E)T = (V, E). שידוך בגרף הוא קבוצת קשתות MEM \subseteq E, כך שכל צומת vv הוא קצה לכל היותר של קשת אחת בשידוך. לדוגמה, בעץ הבא הקשתות המקווקוות מהוות שידוך בגודל מקסימלי.

א. הציעו אלגוריתם חמדן הרץ בזמן O(V)O(V) המחשב שידוך בגודל מקסימלי בעץ TT.

ב. נתונה פונקציית משקל אי-שלילית על הקשתות w:ER+w:E \to \mathbb{R}^+. נגדיר משקל של שידוך בגרף להיות סכום משקלי הקשתות בשידוך. לדוגמה, בעץ הבא הקשתות המקווקוות מהוות שידוך במשקל מקסימלי:

הציעו אלגוריתם הרץ בזמן O(V)O(V) המחשב שידוך במשקל מקסימלי בעץ.

mst
winter_15-16_a
shortest_path

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

א. נתון G=(V,E)G = (V,E) גרף לא מכוון ופונקציית משקל w:ERw:E \to \mathbb{R}. אם ב-GG יש מעגל, אזי הקשת הכי קלה בו מופיעה בהכרח בכל עפ"מ.

ב. נתון G=(V,E)G=(V,E) גרף לא מכוון פונקציית משקל w:ERw: E \to \mathbb{R} כך שאין שתי קשתות במשקל זהה. אזי, מסלול בן זוג צמתים בעפ"מ הוא בהכרח הקל ביותר בגרף GG.

vertex_cover
matching

כיסוי בצמתים של גרף לא מכוון G=(V,E)G = (V,E) הוא קבוצת צמתים UVU \subseteq V כך שלכל קשת (a,b)U(a,b) \in U מתקיים ש-{a,b}U\{a,b\} \cap U \neq \emptyset. כיסוי בצמתים UU נקרא כיסוי מינימום אם מספר הצמתים בו אינו עולה על מספר הצמתים בכל כיסוי בצמתים.

הציעו אלגוריתם למציאת כיסוי מינימום בגרף דו צדדי.

bfs
dijkstra

נתון גרף לא מכוון G=(V,E)G = (V,E)

ונתונה פונקציית משקל w:E{0,1}w:E \to \{0,1\}.

יהא sVs \in V צומת בגרף. משקל מסלול בגרף הוא סכום משקלי הקשתות לאורכו.

הציעו אלגוריתם המחשב את משקל המסלול הקל ביותר ds(v)d_s(v) לכל צומת vVv \in V בגרף בזמן O(V+E)O(|V| + |E|).

dynamic_programming
scc
spring17_a

נתונים גרף מכוון G=(V,E)G = (V,E), צומת sVs \in V ופונקציית משקל על הצמתים w:VRw:V \to R. נגדיר משקל של מסלול PP, כמשקל הצומת הקל ביותר בו. כלומר: w(P)=minvP{w(v)}w(P) = \displaystyle{\min_{v \in P}}\{w(v)\}.

הציעו אלגוריתם המחזיר לכל vVv \in V את משקל המסלול הקל ביותר מ-ss ל-vv (אם אין מסלול כזה, יש להחזיר \infty).

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

dfs
bfs

נתון גרף לא מכוון וקשיר G=(V,E)G=(V,E). הציעו אלגוריתם שמחזיר סדר על הצמתים שמקיים את התנאי הבא:

הסרת צמתי הגרף בזה אחר זה, לפי הסדר, מותירה את שארית הגרף קשיר.

על האלגוריתם לרוץ בסיבוכיות זמן O(V+E)O(|V| + |E|).

max_flow
spring_18_a

נתונה ליגת כדורסל עם nn קבוצות T={t1,,tn}T = \{t_1, \ldots, t_n\}. בנקודת זמן מסוימת במהלך העונה אנו מעוניינים לדעת אם לקבוצה מסוימת קיים עדיין סיכוי תאורטי לסיים את העונה במקום הראשון, כלומר שמספר הניצחונות הסופי שלה יהיה גדול ממש ממספר הניצחונות של כל קבוצה אחרת.

נסמן ב-w(i)w(i) את מספר הניצחונות של הקבוצה ה-ii בנקודת הזמן הנתונה, וב-p(i,j)p(i, j) את מספר המשחקים שנותרו עד סיום העונה בין הקבוצות tit_i ו-tjt_j.

כדי לתאר תרחיש עתידי, נסמן ב-w~(i,j)\tilde{w}(i, j) את מספר הניצחונות העתידיים של הקבוצה ה-ii על הקבוצה ה-jj. שימו לב ש-0w~(i,j)p(i,j)0 \leq \tilde{w}(i, j) \leq p(i, j).

א. נתון הקלט הבא:

pt1t2t3wt1414t2423t3122 \begin{array}{|l|l|l|l||l|} \hline p & t_1 & t_2 & t_3 & w \\\hline t_1 & - & 4 & 1 & 4 \\\hline t_2 & 4 & - & 2 & 3 \\\hline t_3 & 1 & 2 & - & 2 \\\hline \end{array}
  • האם לקבוצה t1t_1 סיכוי תאורטי לסיים ראשונה? אם כן רשמו ערכי w~\tilde{w} מתאימים עבור כל זוג קבוצות, אם לא מספיק לרשום "לא".

  • האם לקבוצה t2t_2 סיכוי תאורטי לסיים ראשונה? אם כן רשמו ערכי w~\tilde{w} מתאימים עבור כל זוג קבוצות, אם לא מספיק לרשום "לא".
  • האם לקבוצה t3t_3 סיכוי תאורטי לסיים ראשונה? אם כן רשמו את ערכי w~\tilde{w} מתאימים עבור כל זוג קבוצות, אם לא מספיק לרשום "לא".

נסמן ב-pp את מספר המשחקים הכולל שנשארו עד סיום העונה, כלומר:

p=1i<jnp(i,j) p = \sum_{1 \leq i < j \leq n}p(i, j)

וב-p(i)p(i) את מספר המשחקים הכולל שנותרו לקבוצה ה-ii עד סיום העונה, כלומר:

p(i)=j̸=ip(i,j) p(i) = \displaystyle{\sum_{j \neq i} p(i, j)}

נשים לב שמספר הניצחונות המרבי שהקבוצה ה-ii יכולה להשיג עד סוף העונה הוא w(i)+p(i)w(i) + p(i).

ב. נתונה ליגה עם 4 קבוצות, {t1,t2,t3,t4}\{t_1, t_2, t_3, t_4\}. נניח שהחל מנקודת זמן מסוימת במהלך העונה קבוצה t4t_4 מנצחת את כל המשחקים הנותרים. הביעו את הערכים הבאים באמצעות w(i)w(i)ו-p(i)p(i) המתאימים.

  • מספר הניצחונות הכולל של קבוצה t4t_4 בסיום העונה:
  • מספר המשחקים המקסימלי שקבוצה t3t_3 יכולה עוד לנצח עד סוף העונה כך שמספר הניצחונות הכולל שלה יהיה קטן ממש ממספר הניצחונות הכוללשל קבוצהt4t_4 בסיום העונה:

ג. נתונה ליגה עם 4 קבוצות, {t1,t2,t3,t4}\{t_1, t_2, t_3, t_4\}, ונתונה רשת הזרימה הבאה. קבעו קיבולים על הקשתות כך שזרימת המקסימום ברשת היא (pp(4))(p - p(4)) אמ"מ לקבוצה t4t_4 יש סיכוי תאורטי לסיים את העונה עם מספר הניצחונות הגדול (ממש) ביותר. יש להביע את הקיבולים במונחים של w(i)w(i), p(i)p(i) ו-p(i,j)p(i, j).

tikz

ד. תארו אלגוריתם שבהינתן T={t1,,tn}T = \{t_1, \ldots, t_n\}, w(i)w(i), p(i,j)p(i,j) וקבוצה tkt_k כמתואר לעיל, מחשב תרחיש שבו הקבוצה tkt_k מסיימת את העונה במקום הראשון, או קובע שאין תרחיש כזה. יש לנתח סיבוכיות ולהוכיח נכונות.

huffman

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

הציעו אלגוריתם (אסטרטגיה) שיבטיח לבוב את התשובה הנכונה עם מספר ממוצע של

119363.305 \frac{119}{36} \approx 3.305

שאלות (כאשר הממוצע נלקח מעל הטלת הקוביות).

matching
winter_15-16_a

נתונות שתי חלוקות של [n][n] ל-kk קבוצות זרות, A1,,AkA_1, \ldots, A_k ו-B1,,BkB_1, \ldots, B_k בהתאמה. כלומר לכל שני אינדקסים 1i<jk1 \leq i < j \leq k מתקיים כי: AiAj=BiBj=A_i \cap A_j = B_i \cap B_j = \emptyset, וכמו כן מתקיים כי i=1kAi=i=1kBi=[n]\bigcup_{i = 1}^k A_i = \bigcup_{i = 1}^k B_i = [n].

קבוצה S[n]S \subseteq [n] בגודל kk הנחתכת עם כל אחת מ-2k2k הקבוצות A1,,Ak,B1,,BkA_1, \ldots, A_k, B_1, \ldots, B_k תקרא מועצה. שימו לב שמועצה לא בהכרח קיימת.

א. הוכיחו כי אם קיימת מועצה SS, אז בהכרח במועצה זו איבר אחד בדיוק מכל אחת מהקבוצות A1,,Ak,B1,,BkA_1, \ldots, A_k, B_1, \ldots, B_k.

ב. הציעו אלגוריתם המכריע אם קיימת מועצה, ואם היא קיימת גם מחשב אותה בסיבוכיות זמן O(nk)O(nk) (הניחו שלכל מספר i[n]i \in [n] נתון לאילו קבוצות הוא שייך).

shortest_path
summer_18_b

נתון גרף מכוון, G=(V,E)G = (V, E), ונתונה פונקציה f:VN{+,}f:V \to \mathbb{N} \cup \{+, -\}. כלומר, בכל צומת של הגרף נתון מספר טבעי או סימן חיבור או חיסור.

מסלול בגרף v1,,vkv_1, \ldots, v_k הוא חוקי אם ניתן לפרש את f(v1)f(vk)f(v_1) \ldots f(v_k) כביטוי אלגברי חוקי, וערך המסלול הוא ערך הביטוי האלגברי המתאים.

א. נתון הגרף הבא:

tikz

ערכי ff מסומנים על הצמתים ונתון ש-f(s)=f(t)=0f(s) = f(t) = 0. מצאו מסלול חוקי מ-ss ל-tt עם ערך מינימלי או קבעו שלא קיים כזה.

ב. בהינתן גרף מכוון, G=(V,E)G = (V, E), זוג צמתים s,tVs,t \in V ופונקציה ff כמתואר למעלה, הציעו אלגוריתם שקובע אם קיים מסלול חוקי כלשהו מ-ss ל-tt. יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

ג. בהינתן גרף מכוון, G=(V,E)G = (V, E), זוג צמתים s,tVs,t \in V ופונקציה ff כמתואר למעלה, הציעו אלגוריתם שמוצא מסלול חוקי מ-ss ל-tt עם ערך מינימלי או קובע שאין כזה. הניחו כי בגרף לא קיים מעגל חוקי עם ערך שלילי.יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

mst
shortest_path

ענו על הסעיפים הבאים:

1. תנו דוגמה לגרף G=(V,E)G = (V,E), צומת מקור sVs \in V ופונקציית משקל w:ERw:E \to \mathbb{R} כך שקיים עץ פורש מינימלי TT ועץ מרחקים קלים ביותר PP של GG כך שמשקל העץ PP גדול פי 10 ממשקל העץ TT.

2. תנו דוגמה לגרף G=(V,E)G = (V,E), צומת מקור sVs \in V, צומת יעד vVv \in V ופונקציית משקל w:ERw:E \to \mathbb{R} כך שקיים עץ פורש מינימלי TT ועץ מרחקים קלים ביותר PP של GG כך שמשקל המסלול מ-ss ל-vv ב-TT גדול פי 10 ממשקל המסלול ב-PP.

winter_15-16_a
dynamic_programming

נתון נהר ולו שני צדדים - צפון ודרום. בכל אחד מהצדדים יש nn בניינים, A1,,AnA_1, \ldots, A_n ו-B1,,BnB_1, \ldots, B_n בהתאמה. בצפון הבניינים מסודרים לפי הסדר (משמאל לימין): A1,,AnA_1, \ldots, A_n ובדרום הבניינים מסודרים לפי פרמוטציה כלשהי של B1,,BnB_1, \ldots, B_n. המטרה היא לבנות גשרים בין שני הצדדים. מותר לבנות גשר אך ורק בין בניינים AiA_i ו-BiB_i לכל 1in1 \leq i \leq n. כמו כן, אסור שהגשרים יחצו זה את זה.

לדוגמה, אם במקרה הבא, נבחר לבנות גשר בין B2B_2 ל-A2A_2 אזי לא נוכל לבנות גשר בין A1A_1 ל-B1B_1, אך כן נוכל לבנות גשר בין A5A_5 ל-B5B_5.

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

max_flow
min_cut
proof

עבור גרף מכוון G=(V,E)G = (V, E) ושני צמתים s,vVs, v \in V נסמן ב-sGvs \underset{G}{\rightsquigarrow} v אם קיים מסלול מ-ss ל-vv ב-GG וב-s̸Gvs \underset{G}{\not\rightsquigarrow} v אם לא קיים מסלול כזה.

בהינתן רשת זרימה N=(G,c,s,t)N = (G, c, s, t) וזרימת מקסימום ff.

ראינו בהרצאה ש-S={v:sGfv}S = \{v : s \underset{G_f}{\rightsquigarrow} v \} הוא חתך מינימום ב-NN.

א. הוכיחו כי T={v:v̸Gft}T = \{v : v \underset{G_f}{\not\rightsquigarrow} t\} הוא חתך מינימום ב-NN.

ב. הוכיחו כי S=TS = T אמ"מ קיים חתך מינימום יחיד ב-NN.

dynamic_programming
spring_18_b

נתונים nn אינטרוולים, A={a1,,an}A = \{a_1, \ldots, a_n\}, ופונקציית משקל w:AR+w:A \to \mathbb{R}^+. נסמן ב-s(a)s(a) ו-e(a)e(a) את נקודת ההתחלה והסוף של האינטרוול aa בהתאמה (לכל אינטרוול, aa, מתקיים ש-s(a)<e(a)s(a) < e(a)).

אינטרוולים aa ו-bb חופפים אמ"מ אחד התנאים הבאים מתקיים:

  • s(a)s(b)e(a)s(a) \leq s(b) \leq e(a)
  • s(b)s(a)e(b)s(b) \leq s(a) \leq e(b)

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

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

נתונה תת קבוצה של אינטרוולים צהובים YAY \subseteq A. רוצים למצוא תת קבוצה בלתי תלויה שמכילה kk אינטרוולים צהובים לכל היותר במשקל מקסימלי.

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

tikz

ב. הציעו אלגוריתם שבהינתן קבוצת אינטרוולים, AA, פונקציית משקל, ww, תת קבוצה של אינטרוולים צהובים YAY \subseteq A, ופרמטר kk מוצא קבוצה בלתי תלויה של אינטרוולים שמכילה לכל היותר kk אינטרוולים צהובים במשקל מקסימלי.

dynamic_programming

תהא a1,,ana_1, \ldots, a_n סדרת מספרים.

  1. הציעו אלגוריתם המוצא תת סדרה עוקבת מונוטונית לא יורדת ארוכה ביותר של הסדרה.
  2. הציעו אלגוריתם המוצא תת סדרה (לאו דווקא עוקבת) מונוטונית לא יורדת ארוכה ביותר של הסדרה.
dynamic_programming

יהא G=(V,E)G = (V,E) גרף מכוון ללא מעגלים עם משקלות על הקשתות.

  1. הציעו אלגוריתם אשר בהינתן צומת ss, מוצא את משקל מסלול קל ביותר מ-ss לשאר צמתי הגרף. על האלגוריתם לרוץ בסיבוכיות זמן של O(V+E)O(|V| + |E|).
  2. הציעו אלגוריתם אשר בהינתן זוג צמתים s,ts,t בגרף, מוצא את משקל מסלול קל ביותר מ-ss ל-tt המכיל לפחות 3 קשתות, או קובע שלא קיים כזה. סיבוכיות הזמן הנדרשת היא O(V+E)O(|V| + |E|).
  3. נתונים nn מספרים ממשיים a1,ana_1, \ldots a_n. ברצוננו למצוא 1i<jn1 \leq i < j \leq n כך ש-k=ijak\sum_{k = i}^j a_k הוא מינימלי. הציעו פתרון לבעיה המבוסס על רדוקציה לסעיף 2.
mst

נתון גרף לא מכוון, סופי וקשיר G=(V,E)G = (V, E), פונקציית משקל w:ERw: E \to \mathbb{R}, וקבוצת צמתים MVM \subset V.

תהי TM\mathcal{T}_M קבוצת כל העצים הפורשים של GG שבהם כל צמתי MM הם עלים. בהנחה ש-TM\mathcal{T}_M \neq \emptyset, אנו מעוניינים למצוא TTMT' \in \mathcal{T}_M בעל משקל מינימלי.

  1. הוכיחו שאם TTMT \in \mathcal{T}_M אז אין ב-TT קשת (u,v)(u,v) כך ש-u,vMu,v \in M
  2. יהי GG' תת גרף של GG המתקבל ממחיקת כל הצמתים של MM וכל הקשתות שנוגעות בהם. הוכיחו שתת העץ המתקבל מ-T'T על ידי מחיקת צמתי MM והקשתות שנוגעות בהם, הוא עפ"מ של G'G.
  3. תארו אלגוריתם יעיל ככל שתוכלו המוצא TT'.
max_flow
spring_18_b

נתונים שני וקטורים מעל Nn\mathbb{N}^n, rr ו-cc. כמו כן נתונה מטריצה בינרית, AA, מגודל n×nn \times n כך שבחלק מהתאים שלה ישנם אפסים.רוצים למלא את התאים הריקים במטריצה ב-0 או 1 כך שלכל 1in1 \leq i \leq n סכום האיברים בשורה ה-ii שווה ל-r[i]r[i] וסכום האיברים בעמודה ה-ii שווה ל-c[i]c[i]. או להודיע שאין כזאת.

א. מלאו את המטריצה הבאה ב-11 או 00, כך שסכום כל שורה וסכום כל עמודה יתאימו לערכים הנקובים בקצה השורה/העמודה.

20101112 \begin{array}{|c|c|c||c|} \hline &&& 2 \\\hline & 0 & & 1 \\\hline && 0 & 1 \\\hline \hline 1 & 1 & 2& \\\hline \end{array}

ב. הציעו אלגוריתם שבהינתן שני וקטורים, rr ו-cc, בגודל nn עם ערכים שלמים אי-שליליים,מוצא מטריצה

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

נתונה מטריצה מגודל n×nn \times n עם ערכים רציונליים כך שסכום הערכים בכל שורה ובכל עמודה הוא שלם. רוצים לעגל את המטריצה על ידי החלפה של כל ערך, xx, ב-x\lceil x \rceil או ב-x\lfloor x \rfloor מבלי לשנות את סכום הערכים באף שורה ובאף עמודה.

עבור מספר שלם, xx, x=x=x\lceil x \rceil = \lfloor x \rfloor = x

לדוגמה, את המטריצה הבאה ניתן לעגל כך:

1.23.42.43.94.02.17.91.60.5142442811 \begin{array}{|c|c|c|} \hline 1.2 & 3.4 & 2.4 \\\hline 3.9 & 4.0 & 2.1 \\\hline 7.9 & 1.6 & 0.5 \\\hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 4 & 2 \\\hline 4 & 4 & 2 \\\hline 8 & 1 & 1 \\\hline \end{array}

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

רמז: הראו רדוקציה לסעיף ב.

ד. הוכיחו כי כל מטריצה עם ערכים רציונליים כך שסכום הערכים בכל שורה ובכל עמודה הוא שלם תמידניתנת לעגול על ידי החלפה של כל ערך, xx, ב-x\lceil x \rceil או ב-x\lfloor x \rfloor מבלי לשנות את סכום הערכים באף שורה ובאף עמודה.

winter_16-17_a
dynamic_programming

נתון גרף מכוון G=(V,E)G = (V, E), צביעה של הקשתות בצהוב ושחור, c:E{B,Y}c:E \to \{B, Y\} וזוג צמתים s,tVs,t \in V.

א. נניח ש-GG חסר מעגלים. הציעו אלגוריתם הרץ בזמן O(V+E)O(|V| + |E|) המחשב מסלול מ-ss ל-tt המכיל מספר מקסימלי של קשתות צהובות.

ב. בהינתן זוג צמתים s,tVs,t \in V, הציעו אלגוריתם הרץ בזמן O(V+E)O(|V| + |E|) המחשב מסלול "קצר ביותר צהוב ביותר", כלומר מסלול בעל מספר מרבי של קשתות צהובות מתוך כל המסלולים הקצרים ביותר. אין צורך להוכיח נכונות.

שימו לב: הגרף בסעיף זה אינו בהכרח חסר מעגלים.

dynamic_programming

יהא dd מספר טבעי, ויהיו k ו-x1,,xnx_1,\ldots,x_n איברים ב-ZdZ_d. הצע אלגוריתם המחשב בכמה אופנים ניתן להכניס סימנים של חיבור וחיסור בין ה-x-ים, כך שתוצאת הביטוי המתקבל תהיה kk (כל החישובים מתבצעים מודולו dd).

כך למשל, אם ה-x-ים הם 7,6,97,6,9 ו-k=2k=2 אז עבור Z10Z_{10} האלגוריתם יחזיר 2 כי

7+6+92mod107+694mod1076+90mod107692mod10 \begin{array}{l} 7 + 6 + 9 \equiv 2 \mod 10 \\ 7 + 6 - 9 \equiv 4 \mod 10 \\ 7 - 6 + 9 \equiv 0 \mod 10 \\ 7 - 6 - 9 \equiv 2 \mod 10 \end{array}

על האלגוריתם לרוץ בסיבוכיות זמן של O(nd)O(nd) ובסיבוכיות מקום של O(d)O(d).

winter_09-10_b
dynamic_programming
mst

יהא G=(V,E)G = (V, E) גרף לא מכוון עם פונקציית משקל על קשתותיו, ויהא TT עץ פורש (לאו דווקא מינימום) של GG. לכל זוג צמתים u,vVu, v \in V נסמן ב-Pu,vP_{u,v} את המסלול היחיד ב-TT המחבר אותם, ונסמן ב-Wu,vW_{u,v} את משקל הקשת הכבדה ביותר ב-Pu,vP_{u,v}.

א. הציעו אלגוריתם המחשב את Wu,vW_{u,v} לכל u,vVu,v \in V. על האלגוריתם לרוץ בזמן O(V2)O(V^2). הוכיחו נכונות ונתחו סיבוכיות.

ב. הציעו אלגוריתם המוצא את כל הקשתות בגרף שאינן מופיעות באף עץ פורש מינימום.

על האלגוריתם לרוץ בזמן O(V2+ElogV)O(V^2 + E\log V). הוכיחו נכונות ונתחו סיבוכיות.

shortest_path
dynamic_programming

יהא G=(V,E)G = (V,E) גרף לא מכוון. יהא ss צומת מקור ו-tt צומת יעד. תהא w:EN{0}w:E \to \mathbb{N} \cup \{0\} פונקציית משקל על הקשתות, ו-c:ENc:E \to \mathbb{N} פונקציית מחיר על הקשתות. בנוסף, נתון לנו תקציב BNB \in \mathbb{N}.

בעיית המסלול הקל ביותר תחת אילוצי תקציב, היא למצוא ב-GG מסלול s=v1,,vk=ts = v_1, \ldots, v_k = t בעל משקל כולל i=1k1w(vivi+1)\sum_{i = 1}^{k -1} w(v_iv_{i+1}) מינימלי, תוך עמידה באילוצי התקציב, דהיינו - i=1k1c(vivi+1)B\sum_{i = 1}^{k - 1}c(v_iv_{i+1}) \leq B.

הציעו אלגוריתם לבעיית המסלול הקל ביותר תחת אילוצי תקציב הרץ בסיבוכיות זמן של O(V2B)O(|V|^2B). האם זמן הריצה פולינומיאלי באורך הקלט?

greedy

לרגל הפתיחה המחודשת של קפה קפה בבית הסטודנט הכריזו על מבצע, מי שקונה זוג מוצרים מקבל את הזול ביניהם חינם. בהינתן רשימת קניות המכילה 2n2n מוצרים במחירים p1,,p2np_1, \ldots, p_{2n} נרצה לסדרם בזוגות כך שתתקבל הנחה מקסימלית.

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

spring_9_b
shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות חיוביות על הקשתות w:ER+w:E \to \mathbb{R}^+, ויהא sVs \in V. תהא f:VRf:V \to \mathbb{R}. נאמר כי ff היא פונקציית מסלולים קלים ביותר מ-ss אם לכל vVv \in V מתקיים ש-f(v)f(v) הוא משקל המסלול הקל ביותר מ-ss ל-vv ב-GG.

א. הוכיחו את הטענה הבאה: ff היא פונקציית מסלולים קלים ביותר מ-ss אם ורק אם

  • f(s)=0f(s) = 0
  • לכל vV{s}v \in V \setminus \{s\} מתקיים f(v)=minuvE(f(u)+w(uv))f(v) = \displaystyle{\min_{uv \in E}} (f(u) + w(uv)).

ב. הציעו אלגוריתם יעיל ככל שתוכלו, המקבל גרף כמתואר לעיל ופונקציה ff ומכריע האם ff היא פונקצית מסלולים קלים ביותר מ-ss. הוכיחו את נכונות האלגוריתם ונתחו סיבוכיות.

winter_16-17_a
shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון ויהא vVv \in V. נניח כי נתונים המרחקים בין כל זוג צמתים בגרף G=G[V{v}]G' = G[V \setminus \{v\}] ביחס לפונקציית משקל אי שלילית w:ER+w:E \to \mathbb{R}^+. כלומר, לכל זוג צמתים a,bV{v}a,b \in V \setminus \{v\} ידוע dG(a,b)d_{G'}(a,b) - משקל מסלול קל ביותר מ-aa ל-bb בגרף GG'.

א. הציעו אלגוריתם הרץ בזמן O(V2)O(|V|^2) המחשב לכל צומת uVu \in V את משקל המסלול הקל ביותר dG(u,v)d_G(u,v).

ב. גם בסעיף זה נתון G=(V,E)G = (V,E) גרף מכוון ו-vVv \in V. לכל a,bV{v}a,b \in V \setminus \{v\} נתון מראש dG(a,b)d_{G'}(a,b). בנוסף, לכל uVu \in V נתונים המרחקים dG(u,v),dG(v,u)d_G(u,v), d_G(v,u).

הציעו אלגוריתם הרץ בזמן O(V2)O(|V|^2) המחשב לכל זוג צמתים s,tVs,t \in V את המרחק dG(s,t)d_G(s,t).

אין צורך להוכיח נכונות.

dynamic_programming
summer_18_b

נתונים nn מספרים ממשיים, a1,,ana_1, \ldots, a_n, רוצים ליצור מהם ביטוי חשבוני על ידי הוספת פעולות כפל וחיבור בין כל שני מספרים עוקבים,כך שערך הביטוי שיתקבל יהיה מקסימלי.

הערות:

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

א. השלימו את הקלט הבא עם פעולות חיבור וכפל כך שערך הביטוי שמתקבל מקסימלי.

0.1232= \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 0.1 & \quad & -2 & \quad & 3 & \quad & 2 & = &\quad \\\hline \end{array}

ב. הוצע לחשב את ערך הביטוי על ידי נוסחת הנסיגה הבאה:

f(i)=max{ai+f(i+1)aif(i+1) f(i) = \max \begin{cases} a_i + f(i + 1) \\ a_i \cdot f(i + 1) \end{cases}

כאשרf(i)f(i) הוא ערך הביטוי עבור הקלטai,,ana_i, \ldots, a_n ו-f(n)=anf(n) = a_n.

הראו שנוסחה זו אינה מחשבת בהכרח את ערך הביטוי המקסימלי.

ג. תארו אלגוריתם פולינומי שבהינתן nn מספרים ממשיים כלשהם, a1,,ana_1, \ldots, a_n, מוסיף פעולות כפל וחיבור בין כל שני מספרים עוקבים,כך שערך הביטוי שמתקבל יהיה מקסימלי.יש לנתח סיבוכיות זמן ריצה אבל אין צורך להוכיח נכונות.

matching

נתונה מטריצה בינרית, AA, בגודל n×nn \times n. קבוצה מנצחת היא פרמוטציה π:[n][n]\pi:[n] \to [n] כך שלכל i[n]i \in [n] מתקיים A[i][π(i)]=1A[i][\pi(i)] = 1. כלומר קבוצה של nn תאים עם ערך 1 כך שמכל שורה ומכל עמודה של המטריצה נבחר תא אחד בדיוק.

הציעו אלגוריתם שמוצא קבוצה מנצחת במטריצה או מודיע שאין כזאת. על האלגוריתם לרוץ בסיבוכיות O(n3)O(n^3).

min_cut
shortest_path
summer_18_b

נתון גרף מכוון, G=(V,E)G = (V, E).

א. סמנו 2 קשתות שיש להסיר מהגרף הבא על מנת שלא יהיה בו מסלול מצומת ss לצומת tt.

tikz

ב. הציעו אלגוריתם שבהינתן גרף מכוון, G=(V,E)G = (V, E), וזוג צמתים s,tVs, t \in V מוצא את מספר הקשתות המינימלי שיש להסיר על מנת שלא יהיה מסלול מ-ss ל-tt. יש לנתח סיבוכיות ולהוכיח נכונות.

ג. נתון גרף מכוון, G=(V,E)G = (V, E), זוג צמתים, s,tVs, t \in V, ופונקציית משקל, w:ER+w:E \to \mathbb{R}^+. הציעו אלגוריתם שמוצא את מספר הקשתות המינימלי שיש להסיר כך שבגרף המתקבל משקל מסלול קל ביותר מ-ss ל-tt כבד יותר ממשקל מסלול קל ביותר בגרף המקורי. יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

min_cut
max_flow

תהא N=(G,c,s,t)N = (G, c, s, t) רשת זרימה. נסמן ב-σ(N)\sigma(N) את קבוצת חתכי המינימום של NN.

  1. הוכיחו כי σ(N)\sigma(N) סגורה לאיחודים ולחיתוכים.
  2. נגדיר Smax(N)=Sσ(N)SS_{\max}(N) = \bigcup_{S \in \sigma(N)}S ו-Smin(N)=Sσ(N)SS_{\min}(N) = \bigcap_{S \in \sigma(N)}S הציעו אלגוריתם שמוצא את Smin(N)S_{\min}(N) ואת Smax(N)S_{\max}(N).
  3. הציעו אלגוריתם המכריע האם ברשת זרימה קיים חתך מינימום יחיד.
dynamic_programming

תת-מחרוזת משותפת ארוכה ביותר - יהיו w1=a1a1...an,w2=b1b2...bmw_1=a_1a_1...a_n , w_2=b_1b_2...b_m מחרוזות מעל אותו אלפבית, תת מחרוזת היא תת סדרה עולה של אותיות מתוך מחרוזת. (עולה ביחס לאינדקסים), הציעו אלגוריתם שמחזיר את אורך תת המחרוזת המשותפת (תת המחרוזת המופיעה בשתי המחרוזות) הארוכה ביותר הארוכה ביותר וכן את תת המחרוזת עצמה.

shortest_path
dijkstra

נתון גרף מכוון G=(V,E)G = (V,E) עם משקלים אי שליליים על הקשתות, פרט לקשת אחת e=(a,b)e = (a,b) שמשקלה שלילי. נניח שאין מעגלים שליליים בגרף.

בהינתן צומת מקור ss הציעו אלגוריתם בסיבוכיות O(V+ElogV)O(|V| + |E|\log|V|) שמוצא עבור כל צומת vVv \in V את משקל המסלול הקל ביותר מ-ss ל-vv.

spring_5_b
edge_coloring
matching

אינדקס הצביעה של גרף לא מכוון G=(V,E)G = (V, E) הוא המספר הקטן ביותר של צבעים הדרוש לצביעת כל קשתות GG כך שכל זוג קשתות בעלות צומת קצה משותף צבועות בצבעים שונים.

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

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

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

shortest_path

נתונה רשת תקשורת המורכבת מ-nn מחשבים ו-mm ערוצים (כל ערוץ מחבר בין שני מחשבים והינו דו-כיווני), כך שלכל ערוץ ee נתונה הסתברות p(e)p(e) שיקרוס. ההסתברויות בלתי תלויות.

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

winter_16-17_a
mst

נתון גרף לא מכוון וקשיר G=(V,E)G = (V, E), פונקציית משקל w:ERw:E \to \mathbb{R} וצומת vVv \in V כך ש-G[V{v}]G[V \setminus \{v\}] קשיר.

נאמר כי עץ פורש הוא v-קטן אם vv הוא עלה בעץ, וכן העץ הוא בעל המשקל הקטן ביותר מבין על העצים הפורשים בהם vv הוא עלה.

הציעו אלגוריתם המחשב עץ vv-קטן.

dfs
scc
spring_15_a

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

א. הוכיחו/הפריכו: יהי GG גרף חסר מעגלים. בכל הרצה של DFS על GG, הצומת הראשון שנסוגים ממנו (כלומר, הצומת הראשון שמוצא מהמחסנית) הוא בור.

ב. הוכיחו/הפריכו בכל הרצה של DFS על גרף מכוון כלשהו GG, הצומת הראשון שנסוגים ממנו שייך לרק"ה מינימלי.

min_cut
max_flow

תהא N=(G,c,s,t)N = (G, c, s, t) רשת זרימה.

  • קשת eEe \in E תקרא קשת קריטית מלמעלה אם לכל ε>0\varepsilon > 0, הגדלת c(e)c(e) ב-ε\varepsilon תגרום להגדלת ערך זרימת המקסימום ב-NN.
  • קשת eEe \in E תקרא קשת קריטית מלמטה אם לכל ε>0\varepsilon > 0, הקטנת c(e)c(e) ב-ε\varepsilon תגרום להקטנת ערך זרימת המקסימום ב-NN.
  1. הציעו אלגוריתם יעיל ככל האפשר המוצא את כל הקשתות הקריטיות מלמעלה.
  2. הציעו אלגוריתם יעיל ככל האפשר המוצא את כל הקשתות הקריטיות מלמטה.
mst

יהא G=(V,E)G = (V,E) גרף לא מכוון וקשיר עם משקלות על הקשתות.

הציעו אלגוריתם המכריע האם ל-GG בדיוק שני עפ"מ-ים.

dynamic_programming

נתונה סדרה של nn מספרים חיוביים S=(a1,,an)S = (a_1, \ldots, a_n). תת-סדרה של SS נקראת מבודדת אם היא אינה מכילה שני איברים שכנים ב-SS. ערך תת-סדרה של SS הוא סכום המספרים בתת-הסדרה.

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

matching

בהינתן גרף מכוון G=(V,E)G = (V, E) ברצוננו למצוא תת גרף מכוון שלו H=(V,E)H = (V, E') כך שבתת הגרף הנ"ל לכל צומת דרגת כניסה ויציאה של 1.

הציעו אלגוריתם שמוצא תת גרף כזה או מודיע שלא קיים כזה.

dynamic_programming

נתונה קבוצה של nn תיבות שכל אחת מהן מאופיינת על ידי גובה, אורך ורוחב. כאן, הסדר שבו נתונים מימדיה של תיבה אינו חשוב; לכן, תיבה שמימדיה 1×2×31 \times 2 \times 3 זהה לזו שמימדיה 2×1×32 \times 1 \times 3. ניתן להכניס תיבה AA לתוך תיבה BB אם ורק אם ניתן לסובב את AA כך שכל שלושת מימדיה יהיו קטנים ממש מאלו של BB. אין להכניס שתי תיבות (או יותר) זו ליד זו לתוך תיבה אחרת, אם אם הדבר אפשרי מבחינת מידות התיבות.

קבוצה טלסקופית היא קבוצה של תיבות המוכנסות זו בזו.

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

bfs

מציאת קוטר הגרף:

יהא G=(V,E)G = (V, E) גרף קשיר ולא מכוון. לכל זוג צמתים u,vVu,v \in V המרחק δ(u,v)\delta(u,v) בין הצמתים הוא מספר הקשתות במסלול קצר ביותר בניהם. קוטר הגרף, dd, מוגדר כמרחק המקסימלי בין כל זוגות הצמתים בגרף, כלומר d=maxu,vV{δ(u,v)}d = \max_{u,v \in V}\{\delta(u,v)\}.

א. בהינתן גרף, GG, וצומת vv שידוע כי הוא קצה של קוטר ב-GG הציעו אלגוריתם המחזיר את הקוטר של GG ופועל בסיבוכיות זמן O(V+E)O(|V| + |E|) עליכם לנתח את סיבוכיות האלגוריתם ולהוכיח את נכונותו.

ב. בהינתן גרף, GG, הציעו אלגוריתם המחזיר את קוטר GG ופועל בסיבוכיות זמן O(V+E)O(|V| + |E|) עליכם לנתח את סיבוכיות האלגוריתם ולהוכיח את נכונותו.

max_flow
min_cut

יהא G=(V,E)G = (V,E) גרף מכוון, ויהיו U1,U2VU_1, U_2 \subset V שתי קבוצות צמתים זרות.

הציעו אלגוריתם שמחשב את מספר הקשתות המינימלי שיש להסיר מהגרף, כך שלא יהיה שום מסלול מצומת ב-U1U_1 לצומת ב-U2U_2.

spanning_tree
median
bottleneck

יהא G=(V,E)G = (V, E) גרף לא מכוון עם משקלות על הקשתות. הכובד של עץ פורש TT של GG הוא משקל הקשת הכבדה ביותר בעץ (לקשת כזו נקרא צוואר בקבוק). עץ פורש שהכובד שלו הוא הקטן ביותר מבין כל העצים הפורשים יקרא עץ פורש קל ביותר.

  1. הוכיחו/הפריכו - כל עץ פורש מינימום הוא גם עץ פורש קל ביותר.
  2. הוכיחו/הפריכו - כל עץ פורש קל ביותר הוא גם עץ פורש מינימום.
  3. הציעו אלגוריתם, אשר בהינתן מספר bb, מכריע האם כובד עץ פורש קל ביותר הוא לכל היותר bb. על האלגוריתם לרוץ בזמן O(E)O(E).
  4. הציעו אלגוריתם המוצא עץ פורש קל ביותר בסיבוכיות זמן O(E)O(E).
dynamic_programming

במדינת ארצות-הבריל ישנם nn סוגי מטבעות c1,,cnc_1,\ldots,c_n. ערכו של המטבע cic_i הוא wiw_i דולצ'ים. לקוחה ובידה שטר שערכו KK דולצ'ים נכנסת לסניף בנק ומבקשת מפקיד הבנק לפרוט את השטר למספר מינימלי אל מטבעות.

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

shortest_path
matching
spring_18_a

נתון גרף לא מכוון G=(V,E)G = (V, E) וקשיר, פונקציית משקל, w:ERw:E \to \mathbb{R}, ושתי תתי קבוצות זרות של צמתים בגודל kk, U,WVU, W \subseteq V.

רוצים למצוא קבוצה, PP, של kk מסלולים זרים בקצוות מ-UU ל-WW, כלומר, לכל שני מסלולים ב-PP, u1,,utu_1, \ldots, u_t ו-v1,,vlv_1, \ldots, v_l מתקיים ש-u1,v1Uu_1, v_1 \in U, ut,vlWu_t, v_l \in W, u1̸=v1u_1 \neq v_1 ו-ut̸=vlu_t \neq v_l.

הערה: אין אף מגבלה על צמתי הביניים של המסלולים, בפרט יתכנו מסלולים ב-PP עם צמתי ביניים משותפים וצמתי הביניים יכולים להיות ב-UU או WW.

נגדיר את ערך הפתרון להיות משקל המסלול הכבד ביותר מבין kk המסלולים, כלומר: maxpP  w(p)\displaystyle{\max_{p \in P}}\;w(p).

אנו מעוניינים למצוא פתרון עם ערך קטן ככל האפשר.

א. הוצע האלגוריתם החמדן הבא:

  • אתחל PP \leftarrow \emptyset
  • כל עוד P<k|P| < k:
    • יהא p=u,,wp = u, \ldots, w מסלול קל ביותר מבין כל המסלולים מ-UU ל-WW, עדכן:
      • PP{p}P \leftarrow P \cup \{p\}
      • UU{u}U \leftarrow U \setminus \{u\}
      • WW{w}W \leftarrow W \setminus \{w\}
  • החזר את PP.

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

ב. תנאי הכרחי לקיום פתרון עם ערך LL לכל היותר הוא שלכל צומת ב-UU קיים מסלול לצומת ב-WW במשקל לכל היותר LL.

הראו, על ידי דוגמה נגדית, כי התנאי הנ"ל איננו מספיק לקיום פתרון עם ערך LL לכל היותר.

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

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

mst

נתון גרף לא מכוון G=(V,E)G = (V,E) עם משקלות על הקשתות.

  1. הציעו אלגוריתם הרץ בזמן לינארי, שבהינתן קשת ee, מכריע האם קיים עפ"מ המכיל את ee.
  2. הציעו אלגוריתם הרץ בזמן לינארי, שבהינתן קשת ee, מכריע האם כל עפ"מ מכיל את ee.
dynamic_programming

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

ברצוננו לגלות מהי הקומה הקריטית (אם בכלל).

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

לדוגמה: אם נתונה ביצה אחת, יש צורך ב-nn הטלות שכן יש להטיל את הביצה מקומה 1 ועד הקומה ה-nn ויתכן כי הביצה לא תשבר באף אחת מההטלות.

shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות על הקשתות. תהא eEe' \in E ויהיו s,tVs,t \in V.

  1. הציעו אלגוריתם המכריע האם קשת ee' נמצאת על כל מסלול קל ביותר מ-ss ל-tt.
  2. הציעו אלגוריתם המכריע האם הקשת ee' נמצאת על איזשהו מסלול קל ביותר מ-ss ל-tt.
mst
proof

יהא G=(V,E)G = (V,E) גרף לא מכוון, קשיר ובעל משקלות על הקשתות. יהיו Ts,TtT_s, T_t שני עצים פורשים מינימום של GG.

הוכיחו כי קיימת סדרה Ts=T1,,Tk=TtT_s = T_1, \ldots, T_k = T_t של עצים פורשים מינימום של GG כך שכל שני עצים עוקבים הם סמוכים במובן הבא: לכל 1ik1 \leq i \leq k ישנה רק קשת אחת הנמצאת ב-TiT_i ולא ב-Ti+1T_{i + 1}.

max_flow

תהא N=(G,s,t,c)N = (G,s,t,c) רשת זרימה בה הקיבולים של כל הקשתות הם מספרים שלמים זוגיים, מלבד קשת אחת, ee, שלה קיבול שלם אי-זוגי. תהא ff זרימת מקסימום בשלמים ברשת ונניח שערכה אי-זוגי.

הוכיחו/הפריכו: ee רוויה.

scc

יהא G=(V,E)G = (V,E) גרף מכוון. נאמר כי UVU \subseteq V היא קבוצה סגורה אם UU \neq \emptyset ואין קשת מכוונת היוצאת מצומת ב-UU לצומת שאינו ב-UU.

הציעו אלגוריתם הרץ בזמן O(V+E)O(|V| + |E|) המוצא קבוצה סגורה מגודל מינימלי.

spring_5_b
max_flow

nn משפחות {f1,,fn}\{f_1, \ldots, f_n\} מוזמנות לחתונה. נסמן ב-nin_i את מספר האנשים במשפחה fif_i לכל 1nn1 \leq n \leq n. על מנת לעודד הכרות בין האורחים מעוניינים החתן והכלה לפזר את המוזמנים בין השולחנות כך שבני אותה משפחה ישובצו לשולחנות שונים (כלומר, שלא יהיה מצב שבאותו שולחן יושבים שניים או יותר מאותה משפחה). מספר השולחנות הוא mm וסביב כל שולחן יכולים לשבת לכל היותר kk אנשים.

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

mst

יהא G=(V,E)G = (V,E) גרף פשוט, לא מכוון וקשיר עם פונקציית משקל w:ERw:E \to \mathbb{R}.

הציעו אלגוריתם המכריע האם ל-GG יש עפ"מ יחיד.

mst

יהא G=(V,E)G = (V, E) גרף לא מכוון ופונקציית משקל w:ERw:E \to \mathbb{R}. יער k-פורש הוא תת גרף T=(V,E)T = (V, E') של GG המהווה יער עם k עצים. יער k-פורש יקרא יער k-פורש מינימלי אם סכום משקלות קשתותיו אינו גדול מסכום המשקלות של אף יער k-פורש אחר.

הציעו אלגוריתם המוצא יער k-פורש מינימלי.

shortest_path
dijkstra

יהא G=(V,E)G = (V, E) גרף מכוון בעל משקלות אי-שליליות על הקשתות. יהא sVs \in V ושני מספרים 0R,BE0 \leq R,B \leq |E|. כל קשת בגרף צבועה באחד מבין שלושת הצבעים - כחול, לבן או אדום.

הציעו אלגוריתם המוצא מסלול קל ביותר מ-ss לכל צומת בגרף, המשתמש בלכל הפחות RR קשתות אדומות ובלכל היותר BB קשתות כחולות. על האלגוריתם לרוץ בסיבוכיות זמן O(RB(E+ElogV))O(RB(|E| + |E|\log|V|)).

dynamic_programming
spring17_a

נתונים ערכי nn מטבעות c1,c2,,cnN{0}c_1,c_2,\ldots,c_n \in \mathbb{N} \setminus \{0\} וסכום כסף SN{0}S \in \mathbb{N} \cup \{0\}.

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

הציעו אלגוריתם שפותר את הבעיה בסיבוכיות זמן O(nS)O(nS). בניתוח הסיבוכיות נתחו גם את סיבוכיות הזיכרון.

spring_15_b
shortest_path

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

הגרף הבא מייצג מפה כאשר צמתי הדרכים עם תחנת החלפת הסוללה מסומנים בריבוע.

tikz

א. עבור הגרף הנתון, מצאו את המסלול הקל ביותר מ-ss ל-tt כאשר =200= 200 XX.

רשמו את המסלול ואת אורכו (אין צורך להוכיח/לנמק).

ב. עבור הגרף הנתון, מצאו את המסלול הקל ביותר מ-ss ל-tt כאשר =30= 30 XX.

רשמו את המסלול ואת אורכו (אין צורך להוכיח/לנמק).

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

max_flow
min_cut

הצע אלגוריתם אשר בהינתן רשת זרימה N=(G,c,s,t)N = (G,c,s,t) עם קיבולים שלמים, מוצא חתך מינימום בעל מספר מינימלי של קשתות מבין כל חתכי המינימום ברשת.

רמז: הגדירו פונקציית קיבול חדשה.

shortest_path
dijkstra

נתון גרף מכוון G=(V,E)G = (V,E) עם משקלים חיוביים על הקשתות: w:ER+w:E \to \mathbb{R}^+. בנוסף נתון צומת sVs \in V ומספר 0kE0 \leq k \leq |E|. הקשתות צבועות בשני צבעים: שחור ולבן.

הציעו אלגוריתם המוצא לכל vVv \in V, את משקל המסלול הקל ביותר מ-ss ל-vv, מבין כל המסלולים מ-ss ל-vv המשתמשים ב-kk קשתות שחורות בדיוק (לא פחות ולא יותר).

על האלגוריתם לרוץ בסיבוכיות O(k(V+ElogV))O(k (|V| + |E| \log |V|)).

dynamic_programming
matching

נתון עץ לא מכוון T=(V,E)T = (V,E) ופונקציית משקלים אי-שלילית על הקשתות w:ER0w:E \to \mathbb{R}_{\geq 0}. שידוך בגרף הוא קבוצת קשתות MEM \subseteq E כך שכל צומת בגרף הוא קצה של קשת אחת לכל היותר בשידוך. משקל השידוך הוא סכום משקלי הקשתות בו.

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

scc
dynamic_programming

יהא G=(V,E)G = (V,E) גרף מכוון. הצע אלגוריתם המחשב קבוצה UVU \subseteq V בגודל מקסימלי כך שיש ב-GG מסלול (לאו דווקא פשוט) דרך כל צמתי UU.

spring_04_a
matching
greedy

שאלה זו מתייחסת למונחים הבאים:

  • שידוך בגרף לא מכוון G=(V,E)G = (V, E) הוא קבוצת קשתות MEM \subseteq E כך שבכל צומת vVv \in V פוגעת קשת אחת מ-MM לכל היותר.
  • MM הוא שידוך מקסימלי אם לא קיים שידוך שמכיל אותו ממש.
  • MM הוא שידוך מקסימום אם לא קיים שידוך גדול ממנו.

א. נתון גרף לא מכוון G=(V,E)G = (V,E) (שימו לב שהגרף אינו דו צדדי בהכרח). הציעו אלגוריתם בסיבוכיות זמן O(V+E)O(|V| + |E|) המחשב שידוך מקסימלי ב-GG. הוכיחו נכונות ונתחו סיבוכיות.

ב. נתון גרף לא מכוון G=(V,E)G = (V, E). יהא MM שידוך מקסימלי ב-GG ויהא MM^* שידוך מקסימום ב-GG. הוכיחו כי M2M|M^*| \leq 2|M|.

ג. הראו גרף לא מכוון G=(V,E)G = (V, E) עבורו קיימים שידוך מקסימלי MM ושידוך מקסימום MM^* כך ש-M=2M|M^*| = 2|M|.

max_flow
greedy
spring17_a

נתון מספר טבעי nN{0}n \in \mathbb{N} \setminus \{0\}.

ברצוננו לחשב מטריצה MRn×nM \in \mathbb{R}^{n \times n}, על ידי קביעת ערך לכל אחד מ-n2n^2 הנעלמים שבמטריצה (נסמן את הנעלם שבשורה ה-ii ובעמודה ה-jj ב-mijm_{ij}).

לכל שורה i[n]i \in [n] נתון אילוץ: j=1nmijri\sum_{j = 1}^n m_{ij} \leq r_i, ולכל עמודה j[n]j \in [n] נתון אילוץ i=1nmijcj\sum_{i = 1}^n m_{ij} \leq c_j.

בנוסף, לכל i,j[n]i,j \in [n] נתון אילוץ 0mijbij0 \leq m_{ij} \leq b_{ij}.

כל הקבועים הם ממשיים ואי-שליליים, משמע: i,j[n]:ri,cj,bijR0\forall i,j \in [n]: r_i, c_j, b_{ij} \in \mathbb{R}_{\geq 0}

נגדיר:

  • השמה חוקית: קביעת ערך לכל אחד מ-n2n^2 הנעלמים, כך שכל האילוצים מתקיימים.
  • ערך של השמה: סכום איברי המטריצה: i,j[n]mij\sum_{i,j \in [n]} m_{ij}.

1. הציעו אלגוריתם המחזיר השמה חוקית בעלת ערך גבוה ביותר. על האלגוריתם לרוץ בסיבוכיות זמן O(n5)O(n^5).

2. בסעיף זה נתון שלכל i,j[n]i,j \in [n] מתקיים bij=b_{ij} = \infty (כלומר אין חסם עליון על ערכי הנעלמים).

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

שימו לב: פתרונות טריוויאלים המריצים את סעיף 1. לא יתקבלו.

greedy
winter_15-16_a

נתון גרף G=(V,E)G = (V, E) לא מכוון, הציעו אלגוריתם המוצא חתך כך שלפחות מחצית מקשתות הגרף חוצות את החתך.

רמז: חישבו על אלגוריתם שמתחזק שתי קבוצות A1,A2A_1, A_2 שבהתחלה ריקות, ובסיום מכילות את קבוצות הצמתים בחתך המבוקש. כאשר צריך להוסיף צומת vv לאחת הקבוצות, איך כדאי לבחור אותה?

dynamic_programming

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

פורמלית, מחרוזת s1,,sns_1, \ldots, s_n מעל א"ב Σ\Sigma היא פלינדרום אם לכל i[n]i \in [n] מתקיים ש-si=sni+1s_i = s_{n - i + 1}.

מחרוזת σ1,,σm\sigma_1, \ldots, \sigma_m היא תת מחרוזת של s=s1,,sns = s_1, \ldots, s_n אם אפשר לקבל אותה על ידי מחיקת תווים מ-ss.

פורמלית, σ1,,σm\sigma_1, \ldots, \sigma_m היא תת מחרוזת של s1,,sns_1, \ldots, s_n אם קיימת פונקציה מונוטונית עולה ממש, f:[m][n]f:[m] \to [n] כך ש-σi=sf(i)\sigma_i = s_{f(i)} לכל i[m]i \in [m].

הציעו אלגוריתם שבהינתן מחרוזת ss מאורך nn מעל א"ב Σ\Sigma מוצא את אורך תת המחרוזת הארוכה ביותר של ss שהיא פלינדרום.

mst
summer_18_b

א. הוכיחו: אם TT עץ בעל קוטר dd, eTe \in T, ו-e/Te' \notin T, כך ש-T=T{e}{e}T' = T \cup \{e'\} \setminus \{e\} הוא עץ, אז הקוטר של TT' הוא לכל היותר 2d+12d + 1.

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

ב. הוכיחו: אם T1T_1 ו-T2T_2 עפ"מים של GG ו-eT2T1e \in T_2 \setminus T_1 אז קיימת קשת eT1e' \in T_1 כך ש-T1{e}{e}T_1 \cup \{e\} \setminus \{e'\} עפ"מ של GG.

ג. נתון גרף לא מכוון עם משקלים על הקשתות, GG, ונתונים שני עפ"מים שלו, T1T_1 ו-T2T_2 בעלי קטרים 20 ו-100 בהתאמה.

הציעו אלגוריתם שמוצא עפ"מ של GG עם קוטר גדול ממש מ-40 וקטן ממש מ-90.יש להוכיח נכונות ולנתח סיבוכיות.

huffman

תהא W=(w1,,wn)W = (w_1,\ldots,w_n)