Recent Forum Posts
From categories:
page 1123...next »
מועד ב
YahavYahav 06 Sep 2010 11:48
in discussion Hidden / news » מועד ב

שלום לכולם,

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

לציון המבחן הוספו 6 נקודות,
וכמו בדרך כלל, ציונים בין 55 ל-60 עוגלו ל-60.

הציון הסופי חושב כמו במועד א'.

שנה טובה,
יהב

מועד ב by YahavYahav, 06 Sep 2010 11:48

הבנתי
תודה רבה!

Re: שאלה 2 מועד א' by tomeryetomerye, 28 Aug 2010 17:59

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

Re: שאלה 2 מועד א' by YahavYahav, 28 Aug 2010 17:57

הבנתי את החסם
m

Re: שאלה 2 מועד א' by tomeryetomerye, 28 Aug 2010 17:32

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

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

וגם לא הבנתי את החסם
m

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

Re: שאלה 2 מועד א' by tomeryetomerye, 28 Aug 2010 17:12

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

Re: שאלה 2 מועד א' by YahavYahav, 28 Aug 2010 16:51

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

החסם התחתון מורכב משני חלקים:
צריך לעבור על כל האותיות במקרה הגרוע (למשל שכל המחרוזות זהות),
ולכן נקבל $\Omega(m)$. בנוסף צריך למיין $n$ מחרוזות, לכן
יש $n!$ פלטים אפשריים. מכאן, עץ ההשואות של כל אלגוריתם הוא
בעומק $\Omega(n \log n)$, לא משנה מה אנחנו משווים.
סה"כ קיבלנו
$\Omega(m + n \log n)$.

Re: שאלה 2 מועד א' by YahavYahav, 28 Aug 2010 16:47

אז לא הבנתי את הפתרון שלך…

איך אתה מגיע לחסם תחתון
nlogn?
הרי אתה לא יכול להשתמש במודל ההשוואות למילים כי אתה לא יכול להשוות בין מילים.

וגם החלק השני לא ברור
ברור שצריך לעבור על כל האותיות…

Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 17:04

אני דיברתי על סעיף ג', כדוגמה נגדית לטענה שלך מ-17:24

Re: שאלה 2 מועד א' by YahavYahav, 27 Aug 2010 16:47
Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 16:04

על איזה סעיף אתה מדבר?
אני מדבר על סעיף ב
צריך להוכיח חסם תחתון למיון
n
מילים

Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 16:03

באופן כללי
$O(f(n) + g(n))$
זה בדיוק אותו דבר כמו
$O(\max\{f(n),g(n)}\})$
עבור פונקציות שמתארות זמן ריצה (חיוביות, לא יורדות,…)
ההוכחה לפי ההגדרה -
כיוון אחד ברור כי הסכום גדול מהמקסימום,
בכיוון השני ניקח את $n_0$ הגדול מבין השניים, ונכפיל ב-2 את $c$ הגדול מבין השניים,
כאשר $c, n_0$ הם כמו בהגדרה.

Re: שאלה 2 מועד א' by YahavYahav, 27 Aug 2010 16:02

עבור האלגוריתם הספציפי שמופיע בשאלה זהו זמן הריצה.

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

מספר הקריאות הרקורסיביות הוא $O(t)$, זמן הריצה של כל קריאה הוא $O(n)$ וסה"כ קיבלנו:
$O(nt) = O(m)$

Re: שאלה 2 מועד א' by YahavYahav, 27 Aug 2010 15:58

ועוד שאלה
כשמופיע בביטוי לסיבוכיות חיבור של שני איברים האם הכוונה לגדול מיביניהם
לדוג'
O(m+nlogn)=MAX(O(m)+O(nlogn))

Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 15:06

לא הבנתי…
אתה יכול להסביר למה במקרה שכל המחרוזות שוות הזמן הוא
m
?
אני מדבר על מחרוזות שוות לא אותיות שוות
כלומר משהו בסגנון:
צמנ צמנ צמנ צמנ צמנ
כאשר t=3 n=5 m=15

Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 15:03

אין קשר בין הדברים.
העובדה שבמקרה הגרוע תשווה שתי מחרוזות בזמן $O(t)$
לא אומרת שכל השוואה שתבצע תהיה בין שתי מחרוזות שלמות ותיקח את הזמן הזה
האלגוריתם משווה אות-אחר-אות וכך חוסך את ההשוואות המלאות,
כי אם האותיות שונות, לא צריך להמשיך ולהשוות את המחרוזות.

Re: שאלה 2 מועד א' by YahavYahav, 27 Aug 2010 14:57

אני יודע שאני לא חייב להשוות את כל המילה אבל במקרה הגרוע אני כן אצטרך לעבור על כל המילה כלומר לעבור אות אות ולהשוות, וזה יקח
O(t)
לפי מודל ההשוואות אני אצטרך לבצע
nlogn
השוואות של מילים
ולכן סה"כ
t*n*logn=mlogn

אולי לא הבנתי את האלגוריתם ?

Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 14:39

ועומק העץ הוא $\Omega(n \log n)$ כי יש $n!$ פלטים אפשריים.

Re: שאלה 2 מועד א' by YahavYahav, 27 Aug 2010 14:31

אין שום דבר שמכריח אותך להשוות תמיד שתי מילים בזמן $\Omega(t)$ ולא להשוות אות-אות

תבחן את הדוגמה שלך, ותריץ עליה את האלגוריתם מסעיף ג', אם תעשה את זה תגלה שזה דווקא
המקרה הקל של האלגוריתם, האלגוריתם ירוץ בזמן $O(m)$ במקרה המסויים הזה שבו כל המחרוזות זהות.

Re: שאלה 2 מועד א' by YahavYahav, 27 Aug 2010 14:29

אם הקלט יהיה רשימה של מילים זהות הסיבוכיות תיהיה
mlogn
לא?

Re: שאלה 2 מועד א' by tomeryetomerye, 27 Aug 2010 14:24
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License