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

שלום לכולם, וברוכים הבאים.
שימו לב:

  1. כדי לפרסם בפורום יש להתחבר עם משתמש wikidot.
  2. אנחנו מזמינים את כולם לנסות ולענות לשאלות של אחרים, השתתפות בדיון מרבה את הלמידה של כולם.
  3. אנא הקדישו מחשבה לניסוח ולהנגשת כל הודעה בפורום. בסוף, אחרים צריכים לקרוא אותה.
  4. הפורום נועד לשאלות מקצועיות.
  5. שאלה בסגנון של "זה הפתרון שחשבתי עליו, האם הוא נכון?" היא לא שאלה טובה (בוודאי לפני תאריך ההגשה של תרגיל).
    במקומה, אפשר לכתוב איפה נתקעתם בנסיון ההוכחה, או למה לדעתכם הפיתרון שגוי.
  6. ניתן לכתוב בעברית או באנגלית, ואם כותבים בעברית יש לעטוף את המלל כמו בדוגמא הנ"ל, כדי שתהיה מיושרת.
    [[>]]
    [[div style="direction:rtl;"]]
    גוף ההודעה
    [[/div]]
    [[/>]]
    (לחיצה על Ctrl+Right_Shift לא תשפיע על ההודעה המתפרסמת, אבל תאפשר לכם לכתוב בנוחות).
  7. ייתכן שהודעות שמחמיצות נקודות אלו לא תיעננה.

השתתפות נעימה.

תלמידים יקרים,

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

כמו כן, שימו לב לשיעור ההשלמה שנקבע ליום שישי בשבוע של הבחירות לשלטון המקומי

שיהיה סמסטר מוצלח,
צוות הקורס.

עדכוני שביתה by RaeNyeRaeNye, 15 Oct 2018 19:54
tal_yanktal_yank 01 Oct 2018 18:04
in discussion Discussions / Q&A, Spring 2018 » 2017ab - q4

חשבתי שבשלב 4 התכוונת לקדקודים שעוד לא ביקרנו בהם.

שוב, זה עדיין לא עובד ולא יכול לעבוד, לא השתמשת בעובדה ש-k קטן.
יש שתי אפשרויות (לא לגמרי ברור ממה שכתבת): או שהתעלמת ממנגנון הצבעים של DFS (ואז האלג' שלך יכול להכנס ללולאה אינסופית ואין בכלל מה לדבר על סיבוכיות), או שלא התעלמת ואז הוא לא עובד. אם לא התעלמת אז הסתכל\י למשל על הגרף הבא:
pic_1.jpeg
יש מעגל פשוט שמכיל את כל הצבעים (אדום, כחול, ירוק, צהוב).
אבל אם נתחיל למשל מהקדקוד A, אז נניח שהקדקוד b מופיע לפני B ברשימת השכנויות שלו, ונעבור ממנו אליו; מ-b נעבור ל-B ומכאן כבר אין שום דרך ש"נסגור מעגל" שבו כל צבע מופיע פעם אחת. כאשר נחזור ל-A, אז הקודקוד B כבר צבוע ולכן לא ננסה שוב כאשר עוברים ישירות אליו.
באופן סימטרי אם מתחילים מ-B, מ-C או מ-D.
by tal_yanktal_yank, 01 Oct 2018 18:04

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

Re: 2018ba - q2 by tal_yanktal_yank, 01 Oct 2018 17:43
2018ba - q2
guest (guest) 01 Oct 2018 17:09
in discussion Discussions / Q&A, Spring 2018 » 2018ba - q2

השאלה:
נתון גרף מכוון עם פונקצית משקל על מהקשתות למספרים חיוביים ממש וצומת s. ידוע שכל צומת v בגרף נגיש מ-s.
מצאו משקל מקסימלי של מסלול בגרף המתחיל ב-s או הודיעו שלא קיים.

האם פתרון אפשרי הוא לשנות את פונקצית המשקלים להיות w/1 ואז להריץ דייקסטרה ולהחזיר את המסלול שקיבלנו כהכי קל?
(קודם לבדוק עם dfs אם יש מעגל כי במקרה כזה אין מסלול עם משקל מקסימלי)

2018ba - q2 by guest (guest), 01 Oct 2018 17:09
guest (guest) 01 Oct 2018 17:02
in discussion Discussions / Q&A, Spring 2018 » 2017ab - q4

כן, עבור הריצה על v0=a, אבל זה שלב 4 אומר שאם הגיע לפה הוא ינסה מחדש עם קודקוד אחר.

הסיבוכיות לא תהיה טובה יותר ממה שכתבת בתגובה קודמת. היא תהיה גם פה O(V(V+E))

by guest (guest), 01 Oct 2018 17:02
tal_yanktal_yank 01 Oct 2018 15:57
in discussion Discussions / Q&A, Spring 2018 » 2017ab - q4

היי, הוא לא. למשל בגרף הבא:
a->b
b->c
c->b
נניח שיש רק שני צבעים וש-b->c->b הוא מעגל פשוט שמכיל רק את שניהם.
אם האלג' שלך מתחיל מ-a (כלומר v0=a), לא תהיה בכלל שום "קשת אחורית" בחזרה ל-a, ולכן תמיד יוחזר false למרות שצריך היה להחזיר true.

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

by tal_yanktal_yank, 01 Oct 2018 15:57
guest (guest) 01 Oct 2018 15:20
in discussion Discussions / Q&A, Spring 2018 » 2017ab - q4

הבנתי את הפספוס - אם רק"ח מכיל k צבעים זה לא בהכרח אומר שיש בו מעגל פשוט. כלומר גם בו צריך להריץ את ה-DFS.

שאלה ממוקדת - האם ה-dfs הבא, מוצא מעגלים פשוטים מ-k צבעים:
[אין קשתות בין קודקודים באותו צבע]
1. נחזיק מערך צבעים באורך k. נאתחל את כל הערכים להיות 0.
2. נבחר צומת כלשהי v0. נעדכן את ערך הצבע שלה להיות 1
3. נבחר קשת של הצומת v -
3.1 אם היא רגילה (לצומת לבן u) - בודקים מה ערך הצבע של הצומת u. אם הוא 0 מעדכנים להיות 1 וצובעים את v באפור ועושים את שלב 3 עבור הצומת u. אם ערך הצבע 1 חוזרים לשלב 3 ובוחרים קשת אחרת
3.2 אם זאת קשת אחורית - בודקים האם זה ל-v0. אם לא חוזרים לשלב 3 ובוחרים קשת אחרת. אם כן, בודקים האם כל הערכים במערך הם 1. אם לא חוזרים לשלב 3 ובוחרים צומת אחרת. אם כן מחזירים אמת.
3.3 אם אין יותר קשתות - מעדכנים את הערך של הצבע של v להיות 0, צובעים בחזרה ללבן ועולים לאבא שלו w לשלב 3
4. אם הגענו לפה נבחר צומת v0 אחר ונעשה שוב את האלגוריתם אלא אם כן נגמרו הצמתים ואז נחזיר שקר

by guest (guest), 01 Oct 2018 15:20
guest (guest) 01 Oct 2018 14:36
in discussion Discussions / Q&A, Spring 2018 » 2018 aa q3

זה לא טוב כי אתה מוסיף קיבול לכל הקשתות במסלול הזה
באותה מידה יכולת למצוא כל מסלול אחר מ-s ל-t ופשוט להוסיף לכל הקשתות שלו וזה היה עובד
אבל אולי יש מסלול שרוב הקשתות לאורכו לא רוויות ולהן אתה לא צריך להוסיף קיבול אלא רק לאלו במסלול הזה שהן כן רוויות

by guest (guest), 01 Oct 2018 14:36
tal_yanktal_yank 01 Oct 2018 11:50
in discussion Discussions / Q&A, Spring 2018 » 2018ba - q4

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

by tal_yanktal_yank, 01 Oct 2018 11:50
tal_yanktal_yank 01 Oct 2018 11:49
in discussion Discussions / Q&A, Spring 2018 » 2018 aa q3

לא נראה נכון.

by tal_yanktal_yank, 01 Oct 2018 11:49
guest (guest) 01 Oct 2018 11:45
in discussion Discussions / Q&A, Spring 2018 » 2018ba - q4

איך ניתן לשפר סיבוכיות זו?

by guest (guest), 01 Oct 2018 11:45
guest (guest) 01 Oct 2018 11:01
in discussion Discussions / Q&A, Spring 2018 » 2018 aa q3

http://tau-algorithms.wdfiles.com/local--files/exams/exam_2018a_moed-a.pdf

שאלה 3,בלינק למעלה,

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

by guest (guest), 01 Oct 2018 11:01

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

Re: 2018 aa q3 by tal_yanktal_yank, 01 Oct 2018 10:57
tal_yanktal_yank 01 Oct 2018 10:54
in discussion Discussions / Q&A, Spring 2018 » 2017ab - q4

אני מצטער אבל לא הבנתי למה את\ה מתכוונ\ת כאן.
כתרגיל נסה\נסי להוכיח במדוייק נכונות של האלג' הזה (אבל זה לא יצליח).

by tal_yanktal_yank, 01 Oct 2018 10:54
2018 aa q3
guest (guest) 01 Oct 2018 10:54
in discussion Discussions / Q&A, Spring 2018 » 2018 aa q3

הצעת פתרון:
1.נבנה את הרשת השיורית,נשים לב שאין מסלול בשיורית מ s to t(אחרת זו מסילה משפרת זרימה).
2.אבל בשיורית יש מסלול מ t to s(אחרת בגרף המקורי עם הזרימה המקס' לכל מסלול מ s ל t היתה קשת עם זרימה 0) נריץ bfs בשיורית מ t.
3.נהפוך את כיוון קשתות המסלול הקצר ביותר מ t to s, ניגש לגרף המקורי נעבר על מסלול זה לאחר הפיכת הקשתות ונוסיף לכל קשת קיבול 1.(קיים מסלול כזה בגרף המקורי מאותו נימוק ב2.
נשים לב שלאחר הוספת קיבול 1 לקשתות הנ"ל,נבנה שוב רשת שיורית והפעם מובטח לנו למצוא מסילה משפרת מ s ל t.

זו קבוצה מינימלית כי זאת המסילה המשפרת הקצרה ביותר מ s לt (הרצנו חיפוש לרוחב)
1 2 ו 3 עלות לינארית

האם האלגוריתם נכון?

2018 aa q3 by guest (guest), 01 Oct 2018 10:54
tal_yanktal_yank 01 Oct 2018 10:44
in discussion Discussions / Q&A, Spring 2018 » 2018ab - q2

היי,
מי זה v ?v מתחלף כל פעם בהתאם לקשת שכרגע בוחנים. אם נריץ דייקסטרא מכל v כזה הסיבוכיות לא תצא טובה.

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

by tal_yanktal_yank, 01 Oct 2018 10:44
guest (guest) 01 Oct 2018 10:42
in discussion Discussions / Q&A, Spring 2018 » 2017ab - q4

ריצת DFS לא מבטיחה מעגל פשוט? הרי אם קשת מחברת לצומת אפור/שחור לא לוקחים אותה, אלא רק לבנים - כלומר כל פעם הולכים לצומת חדש

by guest (guest), 01 Oct 2018 10:42
Dan (guest) 01 Oct 2018 10:12
in discussion Discussions / Q&A, Spring 2018 » 2018ab - q2

היי טל,

תודה על התגובה
יש רק קשת שלילית אחת אפשרית במסלול האם אפשר להריץ דיקסטרה על v ולא על t ?
ואז כמובן למצוא את המסלול המינימלי מ- s ל - t
מתוך המסלול ללא הקשת השלילית מ - s ל - t, ומהמסלול עם קשת שלילית מהמסלול הקצר ביותר מ - s עד ל - u +
משקל הקשת השלילית + מסלול קצר ביותר מ - v ל - t

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

by Dan (guest), 01 Oct 2018 10:12

היי,
"ההסבר ארוך מדי" - הבודק חשב שההסבר ארוך מדי…
אין לי מושג לגבי זה, אבל האם היה ניתן לכתוב תשובה מדוייקת יותר? בהחלט כן. כדאי להתחיל בלא להאניש את קודקודי הגרף. בסה"כ היה צריך להציג זרימה שגודלה כמס' המשימות. אולי להגיד במילה שהיא תקינה: מתקיימים אילוצי קיבול, ואילוצי שימור זרימה.
טל

Re: 2014aa q4b by tal_yanktal_yank, 01 Oct 2018 09:21
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License