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

יש אפשרות להאריך את מועד הגשת תרגיל בית 6 עד 7-10 ימים לפני המבחן או משהו בסגנון?

מועד הגשת תרגיל בית 6 by guesto (guest), 18 Jan 2017 22:49

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

שאלה כללית על תרגיל בית 6 by student (guest), 17 Jan 2017 12:42

שלום,

האם הכוונה היא באמת לפתור את התרגיל הזה?
כבר הגעתי ל-4 משוואות עם 8 (!) משתנים בסך הכל שאני אמור להתחיל לשחק איתם עד שאגיע למקסימום. נראה לי שאיפה שהוא באמצע התבלבלתי מרוב האותיות..

אם באמת אמורים לפתור, כדי שאדע שלא טעיתי, האם מישהו יכול לספר לי כמה איטרציות הוא עשה עד שהגיע לתשובה?

תרגיל בית 5 שאלה 7 by ran (guest), 13 Jan 2017 22:23

אין סיבה להניח את זה

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

שאלה 6 בתרגיל בית 5 by student (guest), 13 Jan 2017 08:37

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

2. אוקיי, תודה :)

3. באופן כללי רק כדי לוודא -
a. בחתך מינימלי (S,T) ברשת עם זרימה מקסימלית, נקבל שכל הקשתות מS ל-T רוויות, וכל הקשתות מT ל-S הן בעלות זרימה 0?
b. ברשת זרימה כללית (ללא זרימה כלשהי), המינימליות של קיבול החתך נמדדת רק לפי קיבול הקשתות מS לT? מה לגבי הקיבולים של קשתות מT לS?

by Yotam (guest), 12 Jan 2017 16:50

1.
תרגיל בית 2 שאלה 1 היא השאלה ש guesto התייחס אליה:
http://tau-algorithms.wdfiles.com/local--files/exercises/Ex2_2016.pdf

2. a. הרשת השיורית בתמונה שגויה. קשת ימנית עליונה מופיעה גם בכיוון ההפוך
b. שוב - הטעות היא בבניית הרשת השיורית.

by ophirfophirf, 12 Jan 2017 12:44

כן, תניחו שהקיבולים שלמים.

by ophirfophirf, 12 Jan 2017 12:06

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

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

2.
a. אם מוצאים חתך מינימלי ע"י לקיחת S ככל הצמתים שנגישים בצורה מכוונת מ-s ברשת השיורית, אז מקבלים חתך שבו כל הקשתות מS לT רוויות, אך ייתכנו קשתות מT לS שיש בהן זרימה (כמו למשל בתמונה הבאה) האם זה תקין?
s28.postimg. org/b94x10tt7/image.jpg
(הפורום מאוד עקשן לא מרשה לפרסם לינקים או תמונות, לכן צריך להוסיף h t t p s : / / לפני הכתובת ולמחוק את הרווח שבכתובת)

b. אם מוצאים חתך מינימלי ע"י לקיחת S ככל הצמתים שנגישים בצורה מכוונת מ-s ברשת השיורית, אז לגבי שאלה 6 בתרגיל בית 5 - לא ברור לי למה יש הבדל בכמות הרווח עבור שתי זרימות מקסימליות תקינות, כמו שמפורט בתמונה הבאה:
s28.postimg. org/bxdrjysiz/image.jpg

תודה וסופ"ש נעים.

by Yotam (guest), 12 Jan 2017 11:37

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

Re: שאלה 3 תרגול 11 by ophirfophirf, 12 Jan 2017 08:34
שאלה 3 תרגול 11
noypitterman (guest) 12 Jan 2017 07:27
in discussion Discussions / Q&A, Fall 2017 » שאלה 3 תרגול 11

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

תודה
נוי

שאלה 3 תרגול 11 by noypitterman (guest), 12 Jan 2017 07:27

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

by guesto (guest), 09 Jan 2017 18:36

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

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

תודה,
יותם

guesto (guest) 08 Jan 2017 15:26
in discussion Discussions / Q&A, Fall 2017 » תרגיל 5 שאלה 2ב

מצטרף לשאלה האם אמור להיות נתון מידע נוסף בסעיף זה.

by guesto (guest), 08 Jan 2017 15:26

רמז: קרא שוב את ההוכחה לשאלה האחרונה בתרגול הראשון על זרימה

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

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

חתך מינימלי קשתות רוויות by paz (guest), 07 Jan 2017 10:28

אני לא מצליח להבין את ההבדל בין שני סוגי הזיווגים
אשמח להבהרה

זיווג מקסימום VS זיווג מקסימלי by paz (guest), 07 Jan 2017 10:09
תרגיל 5 שאלה 2ב
תמי (guest) 06 Jan 2017 09:33
in discussion Discussions / Q&A, Fall 2017 » תרגיל 5 שאלה 2ב

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

תרגיל 5 שאלה 2ב by תמי (guest), 06 Jan 2017 09:33
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License