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

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

החזרת תרגיל בית 5 by student (guest), 19 Jun 2018 13:21

כן, מותר להביא דף A4 אחד, כתוב משני צידיו.

Re: דף נוסחאות by tal_yanktal_yank, 17 Jun 2018 08:44
דף נוסחאות
Yonatan Karidi (guest) 17 Jun 2018 04:18
in discussion Discussions / Q&A, Spring 2018 » דף נוסחאות

ראיתי שברוב השנים הקודמות יש דף נוסחאות במבחן - האם השנה יש דף נוסחאות גם כן?

דף נוסחאות by Yonatan Karidi (guest), 17 Jun 2018 04:18

אין צורך להניח שבכל אחד מהצדדים יש אותו מספר צמתים, לא קשה להוכיח שזה בהכרח כך בכל גרף דו-צדדי d-רגולרי (כמובן נניח $d\geq1$).
אם הגרף הוא $G=(U,W,E)$ אז מתקיים: $|E|=d|U|=d|W|$ ולכן $|U|=|W|$.

Re: תרגיל 6 שאלה 5 by tal_yanktal_yank, 14 Jun 2018 22:18
תרגיל 6 שאלה 5
רועי זמל (guest) 14 Jun 2018 16:46
in discussion Discussions / Q&A, Spring 2018 » תרגיל 6 שאלה 5

[[>]]

בשאלה 5-לא חסרות הנחות על הקלט? למשל שבכל אחד מצדיו יש אותו מספר צמתים? ואני חושב שאולי עוד דברים חסרים… אשמח אם זה ייבדק.


[[/>]
תרגיל 6 שאלה 5 by רועי זמל (guest), 14 Jun 2018 16:46
tal_yanktal_yank 14 Jun 2018 12:05
in discussion Discussions / Q&A, Spring 2018 » dinic

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

by tal_yanktal_yank, 14 Jun 2018 12:05

היי,

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

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

טל

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

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

תודה רבה מראש!

dror (guest) 12 Jun 2018 12:27
in discussion Discussions / Q&A, Spring 2018 » dinic

הי טל תודה,

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

by dror (guest), 12 Jun 2018 12:27
Re: dinic
tal_yanktal_yank 09 Jun 2018 11:51
in discussion Discussions / Q&A, Spring 2018 » dinic

רלוונטית. Dinic הוא חלק מהחומר.

Re: dinic by tal_yanktal_yank, 09 Jun 2018 11:51
dinic
My Name (guest) 08 Jun 2018 16:15
in discussion Discussions / Q&A, Spring 2018 » dinic

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

dinic by My Name (guest), 08 Jun 2018 16:15
dinic
My Name (guest) 08 Jun 2018 16:13
in discussion Hidden / Deleted threads » dinic

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

dinic by My Name (guest), 08 Jun 2018 16:13

היי, שאלה טובה. הסיבוכיות שתיארנו למציאת זרימה מקס' ברשת 0/1 היא מסקנה מניתוח הסיבוכיות של אלגוריתם דיניץ, שילמד בהרצאה האחרונה.
בעיית הזרימה המקסימלית אכן מוגדרת היטב גם אם יש קשתות מקבילות (ובאלגוריתם של דיניץ לא נניח שאין).

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

  • בגרף כללי - $O(E \cdot V^2)$
  • ברשת 0/1 -
    • כללית - $O(E \cdot E^{1/2})$
    • אם הגרף פשוט - $O(E \cdot \min(E^{1/2},V^{2/3}))$
    • אם הגרף בעל התכונה שבכל צומת מלבד s ו-t דרגת הכניסה או דרגת היציאה חסומות ב-1 - $O(E \cdot V^{1/2})$

כך שבהחלט יש למה לצפות!

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

תודה!

שאלה כללית בנושא זרימה by Liad (guest), 03 Jun 2018 20:31

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

by tal_yanktal_yank, 03 Jun 2018 08:00
liann (guest) 02 Jun 2018 19:32
in discussion Discussions / Q&A, Spring 2018 » מעבר מפרימלית לדואלית

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

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

by liann (guest), 02 Jun 2018 19:32

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

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

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

tal_yanktal_yank 01 Jun 2018 11:57
in discussion Discussions / Q&A, Spring 2018 » סיבוכיות FF

במקרה שמריצים את שיטת פורד פולקרסון על רשת שבה כל הקיבולים הם שלמים - אז הסיבוכיות שלו היא $O(EF^*)$, כיוון שבכל איטרציה הזרימה שמוצאים גדלה בלפחות 1.
לעומת זאת, במקרה שיש ברשת קיבולים אי-רציונליים, שיטת פורד פולקרסון עשויה לא לסיים לעולם, ואז אין בכלל מה לדבר על סיבוכיות.
אם מריצים שיטת פורד פולקרסון ממומשת כך שמציאת המסלול המגדיל היא באמצעות BFS, אז זמן הריצה הוא $O(VE^2)$ - וזה כבר נקרא האלגוריתם של אדמונדס-קארפ, וילמד בשיעור הבא.

לגבי למה סיבוכיות של $O(EF^*)$ היא אקספוננציאלית: אפשר לייצג את הקלט בכל מיני דרכים, ויש ייצוג שבו גודל הייצוג של רשת הזרימה הוא סדר גודל של $|V|+|E|+|E|\log n$. המחובר האחרון הוא גודל ייצוג הקיבולים, כאשר n הוא חסם עליון על הקיבול הגדול ביותר.
הזרימה המקסימלית ברשת יכולה להיות בסדר גודל של $n|V|$, ואז הערך של $|E|F^*$ אקספוננציאלי בגודל הקלט.

אם הקיבולים הם כולם סופיים הזרימה המקסימלית גם סופית.

by tal_yanktal_yank, 01 Jun 2018 11:57
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License