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

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

כן, בתנאי שזה מהסמסטר הנוכחי.

כל מה שלא הוכחנו (הסמסטר) בשיעור/תרגול/ש"ב דורש הוכחה.

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

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

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

Re: תכנות לינארי by tal_yanktal_yank, 11 Feb 2019 15:04

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

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

מותר להשתמש בכל שאלה בכל מה שלמדנו (למשל אם זה עוזר להוכיח משהו).

Re: תכנות לינארי by tal_yanktal_yank, 11 Feb 2019 14:39

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

תכנות לינארי by idan_izmirliidan_izmirli, 11 Feb 2019 12:30

היי,
מחפש שותפ/ה למידה שניגש/ת ישר למועד ב' :)
0526599808 פלג

היי אורין,

לי אין תשובות, רק שאלות :)

מועד א' שאלה 2:
מה המשקל המינימלי? כמה קשתות הן ממשקל מינימלי? כמה מתוכן בעפ"מ? מה המשקל הבא בתור?

מועד א' שאלה 4:
מה התשובה עבור $n_1 = n_2 = n_3 = 100$? עבור $n_1 = n_2 = n_3 = 3$? ועבור $n_1 = n_2 = n_3 = 2$?
מה אם $\{n_1,n_2,n_3\} = \{2,3,4\}$? זה משנה בכלל מי זה מי?

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

אכן, יש פתרון לינארי.
כל הקשתות e ממשקל 10 עבורן יש מעגל C ב-G שמכיל את e, כך שכל קשת e'≠e ב-C היא ממשקל <= 10, הן כל הקשתות ממשקל 10 שנמצאות על איזשהו מעגל. לכן אפשר למצוא את כל הקשתות ב-G שנמצאות על איזשהו מעגל (תרגיל בית 2) ולהוסיף לקבוצה שנחזיר את כל אלו שהן ממשקל 10.
כל הקשתות e ממשקל 9 עבורן יש מעגל C ב-G שמכיל את e, כך שכל קשת e'≠e ב-C היא ממשקל <= 9, הן כל הקשתות ממשקל 9 שנמצאות על איזשהו מעגל בתת הגרף שמכיל רק קשתות ממשקל <= 9. ניתן למצוא את כל הקשתות שנמצאות על איזשהו מעגל בגרף זה, ולהוסיף את כל אלו שהן ממשקל 9.
וכך הלאה 8, 7, …, 1.

היי,
אשמח להכוונה בפתרון השאלות הבאות:
מועד א- שאלות 2 ו 4
מועד ב- שאלות 2, 4 (גם כן :)
בתודה מראש על העזרה,
אורין

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

Re: 2018ba-q4
tal_yanktal_yank 10 Feb 2019 21:30
in discussion Discussions / Q&A, Fall 2019 » 2018ba-q4

לא, הקשתות (u,v) ו-(v,u) הן לא קשתות מקבילות (למעשה הן 'אנטי-מקבילות').

Re: 2018ba-q4 by tal_yanktal_yank, 10 Feb 2019 21:30
2018ba-q4
algostualgostu 10 Feb 2019 21:22
in discussion Discussions / Q&A, Fall 2019 » 2018ba-q4

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

האם בגרף מכוון קשתות (u,v) ו-(v,u) נחשבות מקבילות? (כלומר שהן מכוונות הפוך אחת לשנייה)

אם זה אכן כך אז אשמח לעזרה איך למנוע קשתות מקבילות.
חשבתי לעשות רשת זרימה באופן הבא:
צמתים - צומת לכל in_i ולכל out_i ו-s ו-t
קשתות - מ-s לכל צומת in_i מקיבול in_i
מכל in_i לכל out_j (פרט ל-i=j) מקיבול 1
מכל out_i ל-t מקיבול out_i

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

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

2018ba-q4 by algostualgostu, 10 Feb 2019 21:22

יהיה קצת קשה לדעתי להגיע לסתירה כך.
מה שהאלג' שלך בעצם עושה הוא להתחיל מגרף שהוא כמעט עץ (יש בו n+10 במקום n-1 קשתות) ולהסיר בכל שלב את הקשת הכבדה ביותר מאיזשהו מעגל. בסוף התהליך מתקבל גרף עם n-1 קשתות, שהטענה היא שהוא עפ"מ.
כדי להוכיח נכונות, אני ממליץ להוכיח את האינווריאנטה הבאה: אם ל-G יש עפ"מ במשקל w, והסרנו מ-G קשת כבדה ביותר e מאיזשהו מעגל וקיבלנו גרף G', אז גם ל-G' יש עפ"מ במשקל w.
זה לא קשה להוכחה, ניתן להשתמש בקריטריון שהוכח בשיעורי בית למתי קשת נמצאת בכל עפ"מ.

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

Re: שאלה ממבחן by tal_yanktal_yank, 10 Feb 2019 18:36

אם סרקנו קשת $(u,v)$ כאשר $v$ שורש של עץ DFS שהתגלה קודם לכן, אז בזמן זה $v$ שחור והקשת היא קשת חוצה. אם $v$ שורש של עץ ה-DFS הנוכחי, אז הוא אפור וזו קשת לאחור.
בכל מקרה זו לא תהיה קשת עץ.

בדוגמא שלך יער ה-DFS יכיל שני שתילים.

Re: סריקת dfs by RaeNyeRaeNye, 10 Feb 2019 17:10
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License