Recent Forum Posts
From categories:
page 1123...next »
Sharlie Maimonie (guest) 07 Dec 2016 20:24
in discussion Discussions / Q&A, Fall 2017 » בניית גרף העל

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

by Sharlie Maimonie (guest), 07 Dec 2016 20:24

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

Re: שאלה 1 בתרגיל 2 by alonedenaloneden, 05 Dec 2016 12:13

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

Re: בניית גרף העל by alonedenaloneden, 05 Dec 2016 12:11

היי,

שים לב שאפשר לייצג את הרשימה המקושרת ב $O(|E|)$ מקום (לעשות רשומות רק לצמתים שיש קשתות שנוגעות בהם).

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

היי נופר,

ואיך מההרצה הזאת נחשב את $\delta^*(u)$?

Re: שאלה מהתרגול by alonedenaloneden, 05 Dec 2016 12:04
שאלה 1 בתרגיל 2
הילה תשתש (guest) 03 Dec 2016 10:41
in discussion Discussions / Q&A, Fall 2017 » שאלה 1 בתרגיל 2

היי
אני לא בטוחה עד כמה צריך לפרט באלגוריתם
האם אני יכולה פשוט לכתוב
הרצת dfs
הרצת dfs על g-transpose
בניית גרף העל של g
ואז להמשיך את הפתרון של לשאלה

או שאני צריכה לפרט איך אני בונה את גרף העל למשל.

שאלה 1 בתרגיל 2 by הילה תשתש (guest), 03 Dec 2016 10:41
בניית גרף העל
הילה תשתש (guest) 03 Dec 2016 10:38
in discussion Discussions / Q&A, Fall 2017 » בניית גרף העל

היי, זה לא בטוח רלוונטי לתרגיל 2 אבל אני לא מצליחה להבין איך ניתן לבנות את גרף העל בסיבוכיות של (v+e)
השלבים שכן הבנתי עד כה בבנית הגרף

  • הרצת דיאפאס על גרף G

ושמירת רשימת סיוםם של הקודקודים

  • בניית גרף הפוך G- Transpose
  • הרצת דיאפאס על הגרפ ההופכי לפי סדר הפוך של הרשימה של הקודקודי סיום ששמרנו,בריצה זו נשמור גם לכל קודקוד את שורש העץ שלו
  • כך נקבל לכל קודקוד את הרקח אליו הוא שייך , אפשר באותה ריצה גם לבנות את קודקודי גרף העל כך שכל שורש עץ יהיה קודקוד בגרף העל

עד כאן הבנתי

לא הבנתי איך לבנות את הקשתות של גרף העל כך שתהיה קשת אחת בין כל רכיב קשירות (גם אם בגרף המקורי היו כמה קשתות בין אותם רקחים)
אשמח לעזרה

בניית גרף העל by הילה תשתש (guest), 03 Dec 2016 10:38

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

תודה

שאלה מהתרגול
nofar (guest) 01 Dec 2016 21:46
in discussion Discussions / Q&A, Fall 2017 » שאלה מהתרגול

לגבי שאלה 3 מהתרגול לא ברור לי למה נכשל הפיתרון של להפוך קשתות ולהריץ בלמן פורד כך שצומת
הוא צומת המקור מימנה אנו מתחילים V

תודה רבה,
נופר.

שאלה מהתרגול by nofar (guest), 01 Dec 2016 21:46

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

by ophirfophirf, 27 Nov 2016 14:56

כן, צומת נגישה לעצמה ע"י המסלול הריק

Re: תרגיל 2 שאלה 4 by ophirfophirf, 27 Nov 2016 14:41

Hi Guy, the only things you can say without proving are things you saw proven in class (lectures/recitations)

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

Re: שאלה 2א בתרגיל 2 by ophirfophirf, 27 Nov 2016 14:33

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

by elisheva (guest), 27 Nov 2016 13:56

[ [div style="direction:rtl;"] ]
האם יורד ניקוד בתרגילי הבית במידה והאלגוריתם שמציאים הוא מסובך יותר מהפתרון האידיאלי אבל עדין עובד בסיבוכיות הנדרשת?
ספציפית לגבי שאלה 8 בתרגיל הבית. מבקשים שם פתרון ליניארי, האם זה משנה אם האלגוריתם שלי מבצע DFS מספר קבוע של פעמים לעומת פעם אחת בלבד? מספר קבוע של פעמים גורם לסרבול של האלגוריתם אבל הוא עדין עומד בתנאי של ליניאריות.
[ [/div] ]

סיבוכיות הפתרונות בתרגילי הבית by elisheva (guest), 27 Nov 2016 13:54

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

תרגיל 2 שאלה 4 by Ofir MOfir M, 24 Nov 2016 20:52

Suppose we have an undirected graph with calculated d,low values for each vertex (using DFS)
Looking at the DFS tree, can we say that edge u,v is a bridge iff d(v)=low(v)? vertex u is v's parent in the tree.

גשרים בגרף לא מכוון by גיא (guest), 23 Nov 2016 23:19
שאלה 2א בתרגיל 2
רועי (guest) 23 Nov 2016 18:29
in discussion Discussions / Q&A, Fall 2017 » שאלה 2א בתרגיל 2

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

תודה

שאלה 2א בתרגיל 2 by רועי (guest), 23 Nov 2016 18:29

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

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

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

היי,
יש לי בקשה קטנה אודות שיעורי הבית.

תיאור הבעיה:
כשניגשתי לפתור את התרגיל הראשון, לאחר פתרון שאלות 1-3 שאכן עסקו במעגלי אוילר (נושא התרגול הראשון) "נתקעתי" בשאלה 4 מאחר ולא הבנתי שהנושא עליו שואלת השאלה היא BFS (אותו לא תרגלנו בתרגול הראשון אלא רק בשני). לאחר התרגול השני (BFS) המשכתי עם פתרון השיעורים רק שהפעם נתקעתי בשאלות 6-7 המתבססות על ידע אודות אלג' DFS (דובר רק בתרגול 3 - אתמול והיום).
מאחר ותאריך הגשת התרגיל הוא היום (17.11), יצאתי מנקודת הנחה שכל הידע הדרוש לפתרונו כוסה בהרצאות 1-2 ותרגלים 1-2 (BFS ומעגלי אוילר בלבד). מן הסתם הנחה זו התבררה כשגויה השבוע (כששמענו על אלג' למציאת רכיבי קשירות ו"גרף על" בהרצאה על שימושי DFS אתמול (רעיון לפתרון שאלה 6) ותרגלנו את נושא "סיווג הקשתות" של DFS בתרגול (שאלה 7ב)).
כתוצאה מהמתואר לעיל יצא שבזבזתי המון זמן על שאלות 6-7 בניסיון לפתור אותן ללא DFS וחומר אחר שנלמד ותורגל רק אתמול.
הערה: אני מבין שלא חייבים להבין לעומק DFS לפתרון שאלה 6 מאחר ואני סבור שהצלחתי למצוא פתרון "עוקף", אבל ברור שבהינתן הידע על מימושי DFS שאלה זו הופכת לסבירה הרבה יותר. בכל מקרה, עבור 7ב חייבים DFS.
את התחושות לעיל שיתפתי עם חבריי לקורס והתברר שאני לא היחיד שבזבוז הזמן לעיל תסכל אותו.
מאחר והשיעורים מתפרסמים בקוואנטות של שבועיים, אני סבור שסיטואציות דומות יקרו גם בהמשך הקורס.

פתרון מוצע:
אם אפשר לבקש שבעת פרסום תרגיל, תדריכו אותנו (באתר / בפורום / בגוף התרגיל) על אילו נושאים שואלות השאלות, או איזה ידע נדרש אנחנו חייבים על מנת לפתור אותן.
לדוגמא על תרגיל 1: שאלות 1-3 עוסקות במעגל אוילר, שאלות 4-5 מתבססות על ידיעת BFS, שאלות 6-8 על BFS ושימושי DFS. משורת הדרכה כזו המלווה את התרגיל אנו נדע להסיק על אילו שאלות לא לבזבז זמן לפני שלמדנו/תרגלנו/השלמנו נושא מסויים במהלך הקורס.
לחלופין, אם לא תרצו להדריך אותנו על "אילו נושאים" לחשוב בעת פתרון השאלות, אבקש שלפחות תציינו על אילו תרגולים מתבססות השאלות. לדוגמא: שאלות 1-3 מתבססות על נושאי תרגול1, שאלות 4-5 מתבססות על תרגול 2, שאלות 6-8 על תרגול והרצאה 3. הדרכה כזו תשרת את אותה מטרה של אי בזבוז זמן בניסיון פתרון שאלות הדורשות ידע שעוד אין לנו.

תודה מראש,
סטפן.

page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License