Recent Forum Posts
From categories:
page 1123...next »
guesto (guest) 26 Feb 2017 20:21
in discussion Discussions / Q&A, Fall 2017 » Q 5 from 2015 exam_2015b_moed-b.pdf

נתסכל על הסדר הממוין של הערכים, זה יראה משהו כמו:

d[1] d[2] d[4] f[4],…


ננסה לעקוב באמצעות DFS אחרי אותו הסדר.
אם אומרים לנו לגלות עכשיו את קדקוד v, ניקח את הקשת מהקדקוד הנוכחי לקדקוד v. (או אם זה בלולאה המרכזית פשוט ניקח אותו)
אם אומרים לנו לסגור את קדקוד v, פשוט סוגרים אותו וממשיכים.
מתי זה לא אפשרי?
אם בשלב מסוים אנחנו לא יכולים לגלות קדקוד שאמרו לנו, או לא יכולים לסגור קדקוד שאמרו לנו.
אפשר לראות שהמקרה הראשון לא רלוונטי, והמקרה השני קורה כשאנחנו רוצים לסגור קדקוד v אבל עדיין יש ממנו קשת לקדקוד u לבן.
זו בהכרח הקשת (e'=(v,u, והיא מקיימת במקרה זה:

f[v]<d[u]


בנוסף, אפשר לראות שאם 'e מקיימת את התנאי הנ"ל אז כל ריצת DFS תחזיר ערכים שונים כי אי-אפשר לסגור את v כשיש לו שכנים לבנים.
לסיכום, זה תנאי הכרחי ומספיק והשאלה נפתרת בזמן קבוע.
by guesto (guest), 26 Feb 2017 20:21

היי כולם,

אשמח אם תוכלו לסייע לי בפתרון שאלה 5 במבחן מ-2015.

(המבחן החמישי ברשימת המבחנים שפורסמו באתר הקורס)

תודה רבה לעונים

Q 5 from 2015 exam_2015b_moed-b.pdf by Daniel Shore (guest), 26 Feb 2017 19:09

טעות, תוקן תודה

Re: תרגיל 6 שאלה 7 by ophirfophirf, 26 Feb 2017 18:04
Re: Questions
RaeNyeRaeNye 26 Feb 2017 18:02
in discussion Discussions / Q&A, Fall 2017 » Questions

1) מה זה אומר בדיוק למצוא את כל המסלולים/מעגלים? אולי יש מספר אקספוננציאלי שלהם? אם הכוונה היא למצוא את קבוצת הצמתים/הקשתות X כך שלכל צומת/קשת מ-X יש מסלול שעובר גם דרכו/דרכה וגם דרך הקשת הנתונה אז BFS.
2) נניח שזה מצומת מקור s. איך מוגדר גרף מק"בים? בד"כ הוא כולל את כל הקשתות (u,v) עבורן $\delta(s,v) = w(u,v)+\delta(s,u)$, אבל מה עושים כאשר המרחקים הם $-\infty$?
3) התכוונת קרוסקל? אין שום סיבה לחשב את הקבוע הנ"ל. אם מתעקשים אז כמדומני מספיק לקחת משהו כמו $\min\{|w(e)-w(e')|\}$ אבל לשם חישוב יעיל של זה צריך למיין את הקשתות לפי סדר עולה של משקלים, כך שזה לא לינארי.
4) זו בעיה NP-קשה. אולי התכוונת בגרף אציקלי?
5) ה"טריק" הוא הרצה אחת של בלמן-פורד, ומחירו $O(|V||E|)$. זה יותר מדייקסטרה בודד, אבל פחות מ-|V| פעמים דייקסטרה.

Re: Questions by RaeNyeRaeNye, 26 Feb 2017 18:02
guesto (guest) 26 Feb 2017 17:19
in discussion Discussions / Q&A, Fall 2017 » פתרון תרגיל בית 2 שאלה 2

איך אתה מציע לעשות את זה ביעילות?
אולי אם נמספר את הרקחים ונשמור לכל רק"ח מערך ממוין של לכל היותר k אינדקסים של רק"חים שנגישים ממנו, נוכל לאחד בין קבוצות ולהוסיף איבר בזמן (O(k, וזה ייתן לנו סה"כ זמן ריצה של (O(E*k.
(בהנחה שלהעתיק ולהשוות מספרים בטווח 1 עד |V| לוקח זמן קבוע ולא logV, נראה לי שזה חוקי אבל אני לא בטוח)

by guesto (guest), 26 Feb 2017 17:19
תרגיל 6 שאלה 7
tal (guest) 26 Feb 2017 17:16
in discussion Discussions / Q&A, Fall 2017 » תרגיל 6 שאלה 7

במשוואה האחרונה בפתרון,
למה נרשם מקסימום ולא מינימום אם המטרה שלשחקן ב' היא למעזר את תוצאת המשחק?

תרגיל 6 שאלה 7 by tal (guest), 26 Feb 2017 17:16
roy (guest) 26 Feb 2017 15:44
in discussion Discussions / Q&A, Fall 2017 » תרגיל 4 שאלה 2

מישהו יכול לשתף באלגוריתם היעיל?

by roy (guest), 26 Feb 2017 15:44
שאלה ממבחן 2008
שאלה ממבחן (guest) 26 Feb 2017 15:06
in discussion Discussions / Q&A, Fall 2017 » שאלה ממבחן 2008

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

תודה

שאלה ממבחן 2008 by שאלה ממבחן (guest), 26 Feb 2017 15:06
Questions
student (guest) 26 Feb 2017 12:36
in discussion Discussions / Q&A, Fall 2017 » Questions

היי אשמח אם תוכלו לענות לי על מספר שאלות :

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

Questions by student (guest), 26 Feb 2017 12:36
פארס (guest) 26 Feb 2017 12:25
in discussion Discussions / Q&A, Fall 2017 » פתרון תרגיל בית 2 שאלה 2

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

by פארס (guest), 26 Feb 2017 12:25
guesto (guest) 26 Feb 2017 10:52
in discussion Discussions / Q&A, Fall 2017 » פתרון תרגיל בית 2 שאלה 2

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

by guesto (guest), 26 Feb 2017 10:52

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

by ophirfophirf, 26 Feb 2017 10:39

על אילו אי שוויונים מדובר?

Re: תרגיל 6 שאלה 2 by alonedenaloneden, 26 Feb 2017 10:13

ראו את הדף הראשון של המבחן בעמוד exams.

by RaeNyeRaeNye, 25 Feb 2017 22:26

האם יעלה גם פתרון לתרגיל בית 6 ?

פתרון תרגיל בית 6 by guest (guest), 25 Feb 2017 21:25
Yotam (guest) 25 Feb 2017 20:21
in discussion Discussions / Q&A, Fall 2017 » פתרון לשאלה 1 בתרגיל בית 3

תודה!

by Yotam (guest), 25 Feb 2017 20:21

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

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

שאלה לגבי המבחן by student (guest), 25 Feb 2017 10:11
tal rosler (guest) 24 Feb 2017 20:14
in discussion Discussions / Q&A, Fall 2017 » 2013, סימסטר א, מועד א, שאלה 4

תודה!

by tal rosler (guest), 24 Feb 2017 20:14
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License