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

הפורום חזר לפעול.

Re: בהצלחה לכולם! by tal_yanktal_yank, 13 Aug 2018 13:27

Hi,

I'm trying to understand Dynamic programming and was going through the tutorial - https://www.interviewbit.com/courses/programming/topics/dynamic-programming/

My question is - What are the benefits of starting "bottom-up" instead of "top-down" approach?

הפורום יוצא לפגרה, וישוב בעוד כחודש, לטובת הניגשים למועד ב' :)

בהצלחה לכולם! by tal_yanktal_yank, 28 Jun 2018 19:21
tal_yanktal_yank 28 Jun 2018 18:15
in discussion Discussions / Q&A, Spring 2018 » תרגיל 5

היי,
אני לא בטוח מה הכוונה בכך שנתון ש-b^ty<0.

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

לעומת זאת הדואלית לא בהכרח חסומה, כי זה מינימום. אמנם ערך פונ' המטרה חסום מלמעלה ע"י 0, אבל על בעיית מינימום נגיד שהיא לא חסומה אם היא לא חסומה מלמטה, וזאת אנחנו לא יודעים.
לעומת זאת הדואלית כן בהכרח פיזיבילית, בגלל ש-$\bar y = \bar 0$ תמיד מספק את האילוצים.

by tal_yanktal_yank, 28 Jun 2018 18:15
Guest (guest) 28 Jun 2018 17:33
in discussion Discussions / Q&A, Spring 2018 » תרגיל 5

תודה על הסבלנות.

תודה על הסבלנות.

זו התוכנית הפרימלית שחשבתי עליה.
והדואלית-

min b^ty
A^ty >=0
y>=0

נתון גם ש
b^ty<0

האם הפרימלית חסומה כי ערך פונק' המטרה הוא 0?
(כתבת למעלה שהיא תמיד חסומה)
אני חשבתי שדווקא הדואלית חסומה כי פונקציית המטרה שלה קטנה מ-0..

או בקיצור: הסתבכתי מאוד. מניחה שיש פה משהו פשוט שפספספתי.

by Guest (guest), 28 Jun 2018 17:33
Guest (guest) 28 Jun 2018 16:20
in discussion Discussions / Q&A, Spring 2018 » 2018 AB- 3

תודה!

by Guest (guest), 28 Jun 2018 16:20

היי,
נוסחת הנסיגה נראית לי בכיוון, אך לא בדיוק נכונה. למשל, נראה שבכל תתי הבעיות j הוא תמיד n.
בנוסף למה הבחירה היא בין i+1 ו-i+2? למה שתי האפשרויות האלה ממצות?

בכל אופן, הסיבוכיות של הפתרון הזה היא דווקא $O(n^5)$, כי i ו-j הם בין 0 ל-$n^2+1$ ו-k הוא בין 0 ל-n.
טל

by tal_yanktal_yank, 28 Jun 2018 15:58
tal_yanktal_yank 28 Jun 2018 15:38
in discussion Discussions / Q&A, Spring 2018 » פרים משופר

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

by tal_yanktal_yank, 28 Jun 2018 15:38

היי,
לא נראה שלשים קיבול n על הקשתות אל t יעבוד: זה מקביל לדרישה שכל איבר יבחר ע"י כל הקבוצות, וזה כמובן לא חייב להיות המקרה.
גם לקבוע קיבול k לא יעבוד מאותה סיבה - לא צריך לדרוש שאיבר יבחר ע"י k קבוצות, מספיקה אחת.

אני אסביר למה לתת קיבול של 1 לקשתות אל t כן יעבוד.
אחרי שבדקנו שכל הקבוצות הן בגודל >= k (אחרת בוודאי אין פתרון), אז מספיק למצוא חלוקה זרה של $\{1,...,n^2\}$ לקבוצות $B_1,...,B_n$, כלומר כל איבר יהיה בדיוק בקבוצה אחת. אח"כ נוכל להגדיל את כל קבוצה $B_i$ שגודלה < k ע"י הוספת איברים איברים כלשהם מ-$A_i$ (בדקנו שכל הקבוצות גדולות מספיק). לכן זהו הפתרון הנכון (הוא מבטיח למעשה שכל איבר מופיע בלפחות קבוצה אחת).

אם הופכים את הקשתות בקיבול k ל-k קשתות מקבילות, אז דיניץ ירוץ בסיבוכיות $O(n^{4.5})$.
טל

Re: 2018 AB- 3 by tal_yanktal_yank, 28 Jun 2018 15:19
Amit (guest) 28 Jun 2018 14:41
in discussion Discussions / Q&A, Spring 2018 » פרים משופר

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

by Amit (guest), 28 Jun 2018 14:41
tal_yanktal_yank 28 Jun 2018 14:35
in discussion Discussions / Q&A, Spring 2018 » תרגיל 5

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

(1)
\begin{align} \max\ 0 \newline s.t.\ \ A \bar x \leq \bar b \newline \bar x \geq \bar 0 \end{align}

היא לא בהכרח פיזיבלית, למשל אם b הוא וקטור שכולו שלילי, ו-A מטריצת הזהות.

by tal_yanktal_yank, 28 Jun 2018 14:35
Guest (guest) 28 Jun 2018 14:18
in discussion Discussions / Q&A, Spring 2018 » תרגיל 5

טל, תודה על התשובה!
בצורה שבה אני הבנתי את הבעיה מתקבל:

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

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

א. התכנית הפרימלית והתכנית הדואלית שתיהן חסומות ופיזיביליות ⇔ אחת מהן חסומה ופיזיבילית ⇔ שתיהן פיזיביליות.
ב. D פיזיבילית ו-P לא פיזיבילית ⇔ D פיזיבילית ולא חסומה.
ג. P פיזיבילית ו-D לא פיזיבילית ⇔ P פיזיבילית ולא חסומה.
ד. בדיוק אחד מהמקרים הבאים מתקיים:

P ו-D שתיהן חסומות ופיזיביליות
D פיזיבילית ו-P לא פיזיבילית
P פיזיבילית ו-D לא פיזיבילית
D ו-P שתיהן לא פיזיביליות

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

by Guest (guest), 28 Jun 2018 14:18

לא, פשוט חסר בה בהתחלה $\forall 1 \leq i<j \leq n:$

by tal_yanktal_yank, 28 Jun 2018 14:16
tal_yanktal_yank 28 Jun 2018 14:12
in discussion Discussions / Q&A, Spring 2018 » תרגיל 5

היי Guest, כתבתי תשובה למטה

by tal_yanktal_yank, 28 Jun 2018 14:12
guest (guest) 28 Jun 2018 14:12
in discussion Discussions / Q&A, Spring 2018 » תרגיל בית 3 שאלה 5

אז נוסחת הנסיגה המוצעת שגויה?

by guest (guest), 28 Jun 2018 14:12
tal_yanktal_yank 28 Jun 2018 14:11
in discussion Discussions / Q&A, Spring 2018 » תרגיל 5

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

by tal_yanktal_yank, 28 Jun 2018 14:11
tal_yanktal_yank 28 Jun 2018 14:06
in discussion Discussions / Q&A, Spring 2018 » 2017BA - שאלה 5

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

(1)
\begin{align} \max 1/2 \newline s.t.\ x \leq 5 \newline x \geq 0 \end{align}

והתכנית הדואלית:

(2)
\begin{align} \min 5y \newline s.t.\ y \geq 1/2 \newline y \geq 0 \end{align}

לתכנית הפרימלית יש פתרון אופטימלי בשלמים (למשל $x=0$), לתכנית הדואלית אין ($y=1/2$ הוא הפתרון).

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

טל

by tal_yanktal_yank, 28 Jun 2018 14:06

כדי להבין למה זה מקרה הבסיס, כדאי לענות על השאלה: האם ניתן לחשב את $c(A,i,i)$ באמצעות נוסחת הנסיגה שרשומה כאן? כדאי להבין למה זה בעייתי.
יש $n^2$ תתי בעיות: 2 אפשרויות לשחקן * n אפשרויות ל-i *י n אפשרויות ל-j = $2n^2$.

by tal_yanktal_yank, 28 Jun 2018 13:44

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

Re: פרים משופר by tal_yanktal_yank, 28 Jun 2018 13:31
guest (guest) 28 Jun 2018 13:00
in discussion Discussions / Q&A, Spring 2018 » תרגיל בית 3 שאלה 5

הפיתרון המדובר הוא נוסחת הנסיגה הבאה:

$c(A,i,j) = max(a_i + c(B,i+1,j), a_j + c(B,i,j-1)$

$c(B,i,j) = min(-a_i + c(A,i+1,j), -a_j + c(A,i,j-1)$

ומקרי הבסיס המצוינים בסעיף 1 למעלה.

אם כך, מדוע אלו הם מקרי הבסיס?
ולגבי הסיבוכיות, אני מבין שעלות כל חישוב היא $O(1)$ כי מדובר בהשוואה בין שני מספרים, אבל מדוע ישנם $n^2$ חישובים?

by guest (guest), 28 Jun 2018 13:00
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License