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

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

אנצל את העובדה שענית כדי להבהיר את הנקודה הבאה:
ההבדל בחסמים על הסיבוכיות שנתנו לmodular exponentiation נובע מכך שגל התייחס לגודל הקלט כאל הערכים העשרוניים a,b,c, ובחסמים שאני נתתי התייחסתי לגודל הקלט כאל החסם על האורך בביטים של כל אחד מ a,b,c.

by Michal-kleinbortMichal-kleinbort, 11 Feb 2017 17:43

לא הצלחתי להבין מה הכוונה ב"ההבדל ב k הוא בגודל 1".

ייצוג הביניים הרגיל יראה כך:


[a, b, c, b, c, d, e, [7,3], d, e]

אורכו יהיה:
9*8 + 1*18 = 90
ביטים.

הפתרון שיקח בחשבון בכל שלב גם אפשרות של "לא לדחוס" יחזיר את הייצוג הביניים הבא:


[a, b, c, b, c, d, e, a, [5,4]]

אורכו יהיה:
8*8 + 1*18 = 64+18 = 82
ביטים.

אם לא טעיתי בחישוב אז המחרוזת הבאה תיצור פער קצת יותר גדול באורך בביטים (אבל רק קצת).
s = "abcbcdefghabcdefgh"

gal (guest) 11 Feb 2017 17:26
in discussion Fall 2016/7 / Exam 2016-7 » הבהרת מושגים

מביך חחחח כשכתבתי עשרים שנה לא ראיתי שאת עונה

by gal (guest), 11 Feb 2017 17:26
gal (guest) 11 Feb 2017 17:25
in discussion Fall 2016/7 / Exam 2016-7 » הבהרת מושגים

pow(a,b,c) עושה את a^b mod c כאשר c הוא אופציונאלי. זה נקרא מודולר אקספוננשיאישן וזו פונקציה של פייתון. הסיבוכיות שלה היא O(log(a)*log(b)*log(c)).
איטרייטד סקווארינג זה עבור a וb נחשב את a^b בכך שנעלה את a בריבוע b-1 פעמים

by gal (guest), 11 Feb 2017 17:25

האלגוריתם שראיתם לחישוב a**b נלמד בהרצאה 5 (שקף 13). אלגוריתם זה משתמש בשיטת iterated squaring.
לא דיברנו על הסיבוכיות שלו בכיתה.
בשיעור, וגם בתרגילי הבית, דיברנו על מספר המכפלות שהוא מבצע.

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

modular exponentiation זו שיטה יעילה לחישוב a**b mod c. כלומר לחישוב pow(a,b,c).
הרעיון הוא שאם עובדים עם מודולו c אז ניתן תמיד להישאר עם מספרים בני n ביטים לכל היותר (אם a,b,c המקוריים בני n ביטים לכל היותר כל אחד).
זה אומר שכל פעולת כפל תעלה לנו O(n**2) בלבד.
אם תסתכלו על הקוד (שמופיע בהרצאה 12 ) ניתן לראות שמתבצעות n איטרציות ובכל אחת יש מכפלה אחת או שתיים של שני מספרים בני n ביטים כל אחד ולאחריה פעולות מודולו (כך שהתוצאה היא בעלת n ביטים).
הסיבוכיות הכוללת של אלגוריתם זה היא O(n**3).

מיכאל (guest) 11 Feb 2017 17:01
in discussion Fall 2016/7 / Exam 2016-7 » איפה כתוב שיבוצי הכיתות למחר

יהיה תלוי על אחד הלוחות מחר בבוקר (בד"כ תולים בכניסה לשנקר-פיזיקה)

by מיכאל (guest), 11 Feb 2017 17:01

איפה כתוב שיבוצי הכיתות למחר

איפה כתוב שיבוצי הכיתות למחר by yotam (guest), 11 Feb 2017 16:16

הסתבכתי עם זה בעצמי (גם בתרגיל וגם בהכנה למבחן), אז אסביר איך הבנתי את זה בסוף ומקווה שזה יעזור.
קודם כל, בשיעורי הבית למדנו טריק נחמד - למצוא את כל תתי הרשימות באורך k של רשימה, זה כמו למצוא את כל תתי הרשימות באורך k שמכילות את האיבר הראשון ברשימה, ואת כל תתי הרשימות שלא מכילות אותו, ולחבר בין שתי הקבוצות הנ"ל.
עד כאן, יחסית פשוט. אבל איך משתמשים בזה כדי לפתור את הבעיה?
נתייחס לכל חלק בנפרד:
1. למצוא את כל תתי הרשימות באורך k שלא מכילות את האיבר הראשון ברשימה - זה היופי ברקורסיה. זאת בעיה קטנה יותר, ולכן אניח שאני יכול לפתור אותה באותו אופן שבו "פתרתי" את הבעיה הגדולה. כלומר, אם קודם התבקשתי למצוא את repetitions([1,2,3], 2), אז למצוא את אותו הדבר עבור הרשימה [2,3] אמור להיות אפשרי.
2. החלק המסובך יותר הוא למצוא את כל תתי הרשימות בגודל k שכן מכילות את האיבר הראשון ברשימה. כעת, נזכור שאמרו לנו בשאלה שאין בעיה שברשימות שנחזיר תהיה חזרה על איברים. אז מה שנעשה זה ניקח את אותה רשימת איברים בדיוק, [1,2,3], ונפעיל עליה את הפונקציה עבור k=1. ככה נגלה את כל הדרכים להרכיב רשימה באורך 1, בין אם היא מכילה את האיבר הראשון או לא. וכעת נוסיף לכל אחת מהרשימות האלה את האיבר הראשון ברשימה בתחילתן, וכך נקבל את כל הרשימות שמכילות את האיבר הראשון ברשימה - גם אם בחלקן הוא מופיע כמה פעמים (אמרו שמותר).
נחבר את הרשימה שקיבלנו בחלק 1 עם הרשימה שקיבלנו בחלק 2, וסיימנו :-)

by guy (guest), 11 Feb 2017 13:47

עניתי כבר לעצמי
לסקרנים - התשובות הן בהתאמה:

floor(log(2, M)) + 1
floor(log(10, M)) + 1

at least:
floor(log(10, 2^n-1)) + 1
at most:
floor(log(10, (2^n)-1)) + 1

at least:
floor(log(2, 2^k-1)) + 1
at most:
floor(log(2, (10^k)-1)) + 1

שלום
יהא מספר שערכו M
מה אורכו ביצוג בינארי?
מה אורכו ביצוג עשרוני?

יהא מספר בן n ביטים
מה אורכו ביצוג עשרוני?

יהא מספר בעל k ספרות עשרוניות
מה אורכו בביטים?

חמדניות למפל זיו
מיכאל (guest) 11 Feb 2017 11:46
in discussion Fall 2016/7 / Exam 2016-7 » חמדניות למפל זיו

היי,
בהמשך לשאלה שנשאלה כאן בתת-פורום אחר, במצגת על למפל זיו צוין כי האלגוריתם של למפל זיו חמדן שכן הוא ישר מחזיר את הפתרון הראשון שהוא מוצא ולא מחפש את האופטימלי.
נטען שיש מקרים בהם k1»k2 (כאשר k מסמל את אורך החזרה בדחיסה).
אמיר נתן את הדוגמה "abcbcdeabcde", אך שם המהבדל בk הוא בגודל אחד.
האם ניתן לתת דוגמה למקרה בו מתקיים k1»k2? לא הצלחנו לחשוב על דוגמה כזאת.
תודה רבה!

חמדניות למפל זיו by מיכאל (guest), 11 Feb 2017 11:46
הבהרת מושגים
ela (guest) 11 Feb 2017 10:18
in discussion Fall 2016/7 / Exam 2016-7 » הבהרת מושגים

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

iterated squering
modular exponentation
pow(a,b,c)

אם תוכלו במשפט להסביר איך עובד כל אלגוריתם ומה הסיבוכיות זה יהיה מעולה

תודה רבה

הבהרת מושגים by ela (guest), 11 Feb 2017 10:18
מיכאל (guest) 11 Feb 2017 10:14
in discussion Fall 2016/7 / Exam 2016-7 » 2016 סמסטר ב מועד ב

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

by מיכאל (guest), 11 Feb 2017 10:14

נכון מאד.
סיבוכיות O(1) היא בהינתן המיקום המדוייק. כלומר אנחנו כבר מחזיקים מצביע לאיבר שאחריו נרצה להכניס או למחוק.
אם אני לנו מצביע לאיבר הזה אז לא נוכל לעשות זאת בזמן טוב יותר מ O(loc).

by Michal-kleinbortMichal-kleinbort, 11 Feb 2017 10:10

עליכם להחזיר רשימה של רשימות של k איברים עם חזרות.
עבור k=0 עליכם להחזיר רשימה שתכיל רשימה אחת בלבד והיא הרשימה הריקה .
לכן תנאי העצירה הוא כזה.

השאלה מאד דומה ל choose sets מתרגיל הבית, רק שכאן יש חזרות.

עקרונית אין הבדל בין רקורסיה עם eager evaluation וכזו עם lazy evaluation, כלומר עם yield.
פשוט הפונקציה "קופאת" כשמגיעים ל- yield, וממשיכה מאותה נקודה בפעם הבאה.
נקודה אחת שכדאי לשים לב אליה בכל זאת: פונקציה רקורסיבית עם yield חייבת לטפל ב- StopIteration, במנגנון של try-except. אחרת, קריאה פנימית (בעומק הרקורסיה) עלולה להקריס את התוכנית. משום כך, אם משתמשים בלולאה, רצוי להשתמש בלולאת for שעושה את זה בשבילנו כבר.

שלום ירון,

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

אמיר

by Amir RubinsteinAmir Rubinstein, 11 Feb 2017 09:42
by Amir RubinsteinAmir Rubinstein, 11 Feb 2017 09:13

אם הראית מילות קוד במרחק 7, פסלת את תשובות 1 ו-3…

by Amir RubinsteinAmir Rubinstein, 11 Feb 2017 09:11
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License