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

ברוכים הבאים לקורס מבוא מורחב למדעי המחשב.

0) אתר הקורס: אתר הקורס נמצא ב- http://tau-cs1001-py.wikidot.com וניתן להגיע אליו גם מקישור בדף הקורס ב- moodle (דף הקורס במודל משמש בעיקר להגשת תרגילים). באתר זה יופיעו מצגות ההרצאות, חומר התרגולים, תרגילי הבית, ועוד. כמו כן מופיע באתר מידע על נהלי הקורס השונים (כולל תרגילי בית), אותם חובה לקרוא בעיון.

1) שאלון נהלים: כתמריץ לקריאת נהלי הקורס, ישנו ב moodle שאלון קצר להיכרות עם נהלים אלו, שמקנה למי שיענה נכון על כל השאלות תוספת של 2 נקודות לממוצע תרגילי הבית. שימו לב למועד האחרון למילוי השאלון כפי שמופיע במודל, לא יינתנו הארכות.

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

3) תרגיל בית ראשון: תרגיל בית מספר 1 יפורסם בשבוע הראשון של הסמסטר, ויכלול חומר שיילמד בשתי ההרצאות הראשונות, ובתרגול הראשון.

4) קבוצות רישום: יש להגיע לשיעור ולתרגיל אליהם אתם רשומים בלבד, ולא לקבוצה אחרת, בגלל שחלק מהכיתות מלאות.

בברכת סמסטר מהנה ומוצלח,
צוות הקורס

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

שלום שלום,

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

by Guest (guest), 06 Sep 2017 10:22

אני מקווה שהבנתי נכון את תיאור הפתרון שלך.

יצרת מטריצה בגודל k^2, שבה תא (i,j) מחזיק מונה למספר הפעמים שהופיע הזוג (i,j) ברשימה המקורית.

יצירת המטריצה תיקח זמן O(k^2)
מילוי המטריצה יקח זמן לינארי באורך הרשימה.

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

הוספה של איבר לסוף רשימה באמצעות append תיקח זמן קבוע - כי הרשימה לא מועתקת למקום חדש בזיכרון. נעשה זאת n פעמים ולכן הוספת כל האיברים לרשימה החדשה תיקח בסה"כ O(n) .

לסיכום O(k^2 + n) זמן לכל התהליך.

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

by Michal-kleinbortMichal-kleinbort, 06 Sep 2017 07:51

That's true.

The command
a= lst
creates a name "a" that points to the balloon in memory that the name "lst" points to.

This indeed takes O(1) time, and O(1) additional memory, because the list is not copied.

The second command a = [0 for i in range(n)] creates a new list in memory using list comprehension.
The time and space(memory) complexity are both linear in the size of the created list.

by Michal-kleinbortMichal-kleinbort, 06 Sep 2017 07:36

The time complexity for slicing depends on the size of the list created by the slicing operation.

- Suppose that the initial list is of size n and that the slicing creates a list of size log n.
Then, the time complexity of slicing in this case is O(log n).
- If the slicing creates a list of a constant size (that is, its size is not a function of the input size), then the time for slicing is constant (O(1)).

by Michal-kleinbortMichal-kleinbort, 06 Sep 2017 07:29
אנונימי (guest) 06 Sep 2017 07:19
in discussion Spring 2017 / Exam - Spring 2017 » תשובה לשאלה 4 סעיף ב מועד א השנה

תודה רבה

by אנונימי (guest), 06 Sep 2017 07:19

הרעיון היה להשתמש באלגוריתם קארפ רבין להתאמת מחרוזות.
הפרמטרים שנעביר לקארפ רבין יהיו:
text = s*2
pattern = t

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

הרעיון הוא כזה: נרצה לדעת מהו k המינימלי שמבטיח שתת העץ (שהוא צומת יחיד) שמייצג את התו A לא יאוחד עם אף תת עץ אחר במהלך הבניה למעט בשלב האחרון.
בשלב האחרון יאוחדו 3 תתי עצים.

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

תודה על הבדיקה אמיר.
זה דווקא נשמע הגיוני.

by Michal-kleinbortMichal-kleinbort, 06 Sep 2017 06:48

דרך אחרת להתסכל על הבעיה (שהיא כמובן רחבה יותר מהשאלה הספציפית
הזו)

יש לי 2 לולאות מקוננות, כל אחת עושה K חזרות.

בתוך הלולאות האלו אני צריכה "לדחוף" o(n) עבודה.
לא ידוע באיזו קונסטלציה.

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

תודה מראש

by Guest (guest), 06 Sep 2017 05:21

שלום,
בהערות לבדיקה לתרגילי הבית נכתב שסיבוכיות המיון של רשימת טאפלים (אשר ידעו שהם חסומים ע"י ערך מסויים, K)
בפיתרון שעושה שימוש במטריצת קאונטרים הינו:
O(k^2+n)

אולם אני חושבת שהסיבוכיות היא
O(n*k^2+n)

ואשמח לוודא היכן הטעות שלי.

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

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

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

לדעתי הראשון O1
שכן זו השמה בלבד. והרשימה כבר קיימת בזיכרון.. וכבר תופסת
ON
זיכרון.

לגבי השאלה ה-2-
לדעתי ON

by Guest (guest), 05 Sep 2017 18:20
Adi (guest) 05 Sep 2017 17:56
in discussion Spring 2017 / Exam - Spring 2017 » slicing time complexity

היי,
דנו בנושא ב
http://tau-cs1001-py.wikidot.com/forum/t-3215324/

by Adi (guest), 05 Sep 2017 17:56

בעת הגדרת משתנה שהוא רשימה שכבר ידועה לנו, לדוגמא
a = lst
האם מדובר בO(1)
זיכרון או O(n)
כאשר n ?מייצג את אורך הרשימה

כמו כן, מהי סיבוכיות הזיכרון עבור רשימה שנוצרת באותו הרגע, למשל
a = [0 for i in range(n)]

תודה רבה מראש

היי,
מה הייתה התשובה או הכיוון הכללי לתשובה בשאלה 4 סעיף ב במועד א של השנה?

תשובה לשאלה 4 סעיף ב מועד א השנה by אנונימי (guest), 05 Sep 2017 15:42

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

תודה

עמוד השער של מועד ב' by Student (guest), 05 Sep 2017 15:09
slicing time complexity
Guest (guest) 05 Sep 2017 11:17
in discussion Spring 2017 / Exam - Spring 2017 » slicing time complexity

what is the time complexity of slicing and do we need to take this into consideration while we determine the complexity of a code?

slicing time complexity by Guest (guest), 05 Sep 2017 11:17
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License