Recent Forum Posts
From categories:
page 1123...next »

שאלה 1

by Oz A (guest), 26 Mar 2017 18:41

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

יש להוכיח, אחרת איך תדעי שהתנאי נכון?
אעדכן את הקובץ תודה

Re: שאלה 4
ophirfophirf 26 Mar 2017 15:29
in discussion Discussions / Q&A, Spring 2017 » שאלה 4

א. קשת יכולה לחזור פעמיים
ב. כן

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

Re: שאלה 4 by ophirfophirf, 26 Mar 2017 15:29

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

היי,

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

בתודה,
עוז

הוכחת טענה באמצעות אלגוריתם by Oz A (guest), 25 Mar 2017 15:04

האם יש להוכיח שהתנאי שמצאנו הוא הכרחי ומספיק?

תודה:)

תרגיל 1 שאלה 3 סעיף א by מאיה (guest), 25 Mar 2017 14:58
שאלה 4
Tomer Solomon (guest) 25 Mar 2017 09:33
in discussion Discussions / Q&A, Spring 2017 » שאלה 4

היי,

מספר שאלות לגבי תרגיל 4:
א. כשכתוב "מסלול, לאו דווקא פשוט" - האם הכוונה שאותה קשת יכולה לחזור מספר פעמים, או שרק אותו קודקוד יכול לחזור מספר פעמים? באיזה אופן זה "מסלול"
ב. האם מבחינת ההגדרות בשאלה, x או y יכולים להיות צמתים פנימיים במסלול הנ"ל? (אני יכול לחשוב על גרפים שבהם זה קורה)
(אני שואל כי אז מצאתי איך להשתמש ב-BFS, אבל כשמריצים את BFS על הגרף ונקודה x, אז לא יחזיר את x כקודקוד שנגיש מ-x)

תומר

שאלה 4 by Tomer Solomon (guest), 25 Mar 2017 09:33

מתי יפורסמו הסריקות?

סריקת מחברות בחינה by myname (guest), 24 Mar 2017 11:52

היי
1. כן
2. לרוב אין צורך לדבר על המבנה נתונים שמייצג את הגרף, אבל לא ברור לאיזו שאלה התייחסת.
3. מילולית זה מספיק, אבל שיהיה ברור, לדוגמא (אלגוריתם חסר תועלת):
קלט: גרף A
1. הפוך קשתות A ושמור בגרף B
2. עבור על קשתות B, לכל קשת e=u->v של הגרף B:
2.1 הדפס v

4. כן

שלום,

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

האם יש צורך להסביר את האלגוריתם מבחינת מה קורה ברשימות המקושרות ממש בכל שלב?

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

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

תודה רבה !

תיאור האלגוריתם וסיבוכיות הזמן by אילור (guest), 22 Mar 2017 17:58

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

Re: שאלה 6 by alonedenaloneden, 22 Mar 2017 12:56
שאלה 6
Guy77Guy77 22 Mar 2017 07:32
in discussion Discussions / Q&A, Spring 2017 » שאלה 6

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

שאלה 6 by Guy77Guy77, 22 Mar 2017 07:32

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

Re: גרף קשיר by alonedenaloneden, 21 Mar 2017 20:25
פתרון מועד א
בלמן-פורד (guest) 21 Mar 2017 09:34
in discussion Discussions / Q&A, Fall 2017 » פתרון מועד א

שלום רב,האם אפשר לעלות פתרון רשמי למועד א?

פתרון מועד א by בלמן-פורד (guest), 21 Mar 2017 09:34
גרף קשיר
Student (guest) 21 Mar 2017 09:21
in discussion Discussions / Q&A, Spring 2017 » גרף קשיר

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

גרף קשיר by Student (guest), 21 Mar 2017 09:21
matan (guest) 20 Mar 2017 18:47
in discussion Discussions / Q&A, Spring 2017 » a small question regarding BFS time complexity

Thanks.

by matan (guest), 20 Mar 2017 18:47

בגרף המלא, $|E|=|V|\cdot\left(|V|-1\right)/2$, כך שזה לא סותר.

Hi,
How do we conclude that the time it takes to travel all the adjacent edges of all given vertices during BFS is O(E)? At the worst case we could be touring V*V edges (in case the graph is a complete graph), why is this number bounded by O(E)?

Thank you,
Matan.

a small question regarding BFS time complexity by matan (guest), 19 Mar 2017 17:03
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License