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

יש סיבה קונקרטית לכך?

by Alex (guest), 23 Jul 2017 15:38

אין מפורסמים פיתרונות רשמיים למבחנים בקורס.

בהצלחה לכולם.

מצטרפת לבקשה

by nufar (guest), 16 Jul 2017 11:32
by Michal (guest), 09 Jul 2017 16:47
by Yotam KimaYotam Kima, 09 Jul 2017 13:48

ההוראות הקודמות תקפות גם לתרגיל זה? 4 ימים הארכה והגשה עד 12:00?
בתרגיל עצמו רשום כי ההגשה עד מחר ב-9:00 בבוקר והדבר נראה מוזר כשהמבחן עצמו ב-14:00 וההגשה היא פרונטלית.

by Daario Naharis (guest), 09 Jul 2017 09:17

? E*(V^1/2)מדוע הסיבוכיות שפיצלנו כל קודקוד ל2 היא לא
כי שנפצל כל קודקוד ונחבר בקשת דרגת יציאה או כניסה תהיה 1

Daario Naharis (guest) 09 Jul 2017 08:30
in discussion Discussions / Q&A, Spring 2017 » תרגול 12, שאלה 3

valar morghulis

הבנת נכון לגביי בניית הרשת. הבחירה ב-FF על-פני דיניץ נובעת מכך שהסיבוכיות של FF במקרה זה תהיה טובה יותר (שקופית 21).
וחיפוש זרימה בגודל M יניב כי כל הקשתות מ-s למשימות תהיינה רוויות, הדבר שקול לחיפוש זרימה מקסימלית והשוואתה ל-M.

valar dohaeris

by Daario Naharis (guest), 09 Jul 2017 08:30
תרגול 12, שאלה 3
A girl has no name (guest) 09 Jul 2017 08:22
in discussion Discussions / Q&A, Spring 2017 » תרגול 12, שאלה 3

היי,
אפשר לקבל הסבר/עזרה לפתרון של שאלה 3? במצגת יש רק דוגמה ואני רוצה לוודא שהבנתי את הפתרון.
אם הבנתי נכון- שמים m קשתות מ-s לכל משימה ובכל קשת שמים קיבול של 1, ואז מכל משימה שמים קשתות למכונות שיודעות לבצע אותה עם קיבול 1 גם כן. המכונות יחוברו ל-t בקשתות עם קיבול 1, נכון?
ובגלל שכל הקיבולים הם שלמים אז משתלם בעצם להריץ FF ולא דיניץ?
בנוסף, רשום שצריך לחפש זרימה בגודל m. האם זה שקול ללהגיד שנחפש זרימה בגודל המקסימלי ואם הזרימה אינה m אז נחזיר שלא קיימת השמה מתאימה?

תודה רבה לעוזרים!~

תרגול 12, שאלה 3 by A girl has no name (guest), 09 Jul 2017 08:22
Daario Naharis (guest) 09 Jul 2017 08:03
in discussion Discussions / Q&A, Spring 2017 » מציאת זרימה מקסימלית לא רציונלית

הכוונה הייתה כמובן לקיבולים לא לזרימה אי רציונלית

by Daario Naharis (guest), 09 Jul 2017 08:03

valar morghulis

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

valar dohaeris

A girl has no name (guest) 09 Jul 2017 07:25
in discussion Discussions / Q&A, Spring 2017 » אלגוריתמים הסתברותיים?

לא נראה לי שזה משהו שלמדנו, אז לא…

by A girl has no name (guest), 09 Jul 2017 07:25

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

אלגוריתם למשקל כללי (לא רק 0-1)
תהפכי את סימן המשקלים
תריצי בלמן פורד על גרף הציקלי
סיבוכיות לינארית

valar morghulis
במבחן מועד א' אביב 2015 הסטודנטים נתבקשו ליצור אלגוריתם שבשלב מסוים מחפש מסלול כבד ביותר בגרף פשוט חסר מעגלים מקודקוד מסויים לקודקוד אחר (שנמצאו במיון טופולוגי) (נניח שהמשקלים 0-1). נאמר שניתן למצוא מסלול זה בסיבוכיות לינארית. יש למישהו רעיונות?

valar dohaeris

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

אחלה פיתרון יותם!

by alonedenaloneden, 07 Jul 2017 19:01

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

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