602

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

אין בעד מה =]

הלולאה השנייה מובנת? זה לגבי הראשונה: http://i.imgur.com/GAUpaTt.png סה"כ הזמן הוא: T(n)=log(sqrt(n)+sqrt(n)a. log(sqrt(n) קטן מ-sqrt(n) ולכן ניתן להתעלם ממנו בחישוב הסיבוכיות.

יש פה רק פונקציה אחת, שלא קוראת לעצמה, אז נוכל נחלק את הבעיה לשתיים: סיבוכיות הזמן של הלולאה הראשונה ("כמה זמן לוקח לה לרוץ") - ניתן לנתח את זה, ואני אשתדל לערוך את ההודעה מאוחר יותר ולהביא את הניתוח, אבל כרגע אני אבטיח לך (כי פתרתי את השאלה ממקודם) שהסיבוכיות פה תצא קטנה מבלולאה השנייה, ולכן מה שהולך לצאת בלולאה השנייה הוא הדומיננטי והקובע. מה שכן חשוב לשים פה לב, זה שהתנאי של הלולאה הוא x^2>n, ובכל איטרציה מקטינים את x. במילים אחרות, ברגע ש-x יהיה מסדר גודל של שורש n, נצא מהלולאה (x יכול להיות שווה ל(שורש n) או קצת קטן יותר, זה לא חשוב לנו, כי זה עדיין סדר גודל של (שורש n) ולכן x^2 שווה ל-n, אולי קצת קטן יותר, וזה בדיוק התנאי ליציאה מהלולאה). סיבוכיות הזמן של הלולאה השנייה - אז יצאנו מהלולאה, והערך של x הוא כעת מסדר גודל של שורש n. נשים לב כי לולאה זו רצה x פעמים, כלומר היא תרוץ סדר גודל של שורש n פעמים, ולכן סיבוכיות הזמן היא http://www.codecogs.com/gif.latex?O(%5Csqrt%7Bn%7D). אגב נדמה לי שבפייסבוק היה דיון על השאלה הזאת (טוב משם לקחת את התמונה...).

יאי...

עוד שאלה על מועדי ב': אחרי שעוברים את מועד א', האם אפשר לבוא למועד ב', להסתכל על המבחן ואם מקבלים התקף לב אז לא להגיש אותו? (או שמרגע שלדודה יש את הת"ז, הציון של המועד ב' דורס את הציון של המועד א'? O.o)

ממבט שטחי: נראה שהלולאה תרוץ מקסימום n/2 פעמים, אאל"ט בגלל זה רשמתי c_2*n (בד"כ תרוץ פחות כמובן). (בהנחה ששנינו התכוונו למספר האיטרציות שהלולאה עושה, אני לא רואה סיבה שהיא תרוץ logn. אין פה משהו שנחצה כל איטרציה, אלא פשוט מוסיפים 1 ל-i/מורידים 1 מ-j ככה עד שאחד מהם מגיע ל-half, במקרה הגרוע שניהם יגיעו יחדיו ל-half וזה יקח half=n/2 איטרציות.)

אולי זה יעזור? https://docs.google.com/file/d/0B6cTtrH1YMlxOXV4TnB2bF9aYjQ/edit?pli=1 חלק 4. (זה ישן אבל התהליך אותו תהליך, רק שאני לא יודע אם החלק בו אס"ט משתתפת עדיין רלוונטי אז כנראה שתצטרכי לנסוע למרכזית.)

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

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

עריכה: אוקיי הסתדרתי עם הסיבוכיות זמן: http://www.codecogs.com/gif.latex?T(n)=c_%7B1%7D+c_%7B2%7Dn+2T(n/2) (כאשר c_2 כפול n נובע מהלולאה) נציב T(n/2) ונקבל: http://www.codecogs.com/gif.latex?T(n)=3c_%7B1%7D+2c_%7B2%7Dn+2%5E%7B2%7DT(n/4) נמשיך ונמשיך... ולבסוף נקבל: http://www.codecogs.com/gif.latex?T(n)=Qc_%7B1%7D+kc_%7B2%7Dn+2%5E%7Bk%7DT(n/k) (לא רציתי לרשום את Q במפורש, זה פשוט סכום סדרה הנדסית, שבחשבון הסופי היא מסדר גודל של n ולכן לא משנה לנו. Q לא קבוע והוא תלוי ב-k.) נציב http://www.codecogs.com/gif.latex?k=logn ונקבל: http://www.codecogs.com/gif.latex?T(n)=Qc_%7B1%7D+c_%7B2%7Dnlogn+nT(1), ונקבל http://www.codecogs.com/gif.latex?T(n)%5Cin%20O(nlogn).

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

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

תודה רבה! עכשיו יותר מובן אבל עדיין מעורפל. איך אתה יודע שהקריאות הן על חצי מערך? (הקריאה השנייה שולחת חצי מערך, אבל הקריאה הראשונה שולחת את כל המערך רק עם פרמטר n/2 במקום n. אם הבנתי נכון אתה אומר שבכל אחד מהמקרים האלה הפונקציה "מתעסקת" רק עם חצי מהמערך...) בנוגע לעץ רקורסיות, למה יש כל צומת מתפצלת ל-4 צמתים ולא ל-2?

זה באמת O(logn)i, אבל לא הבנתי למה. כל פעם הפונקציה מבצעת שתי קריאות, אחת על כל המערך, ואחת על חצי מערך. בנוסף, איך בכלל מתייחסים ללולאה הזאת בסוף? היא לא תלויה ב-n באופן ישיר, האם ניתן לומר כי כל הלולאה היא O(1)i? (גם זמן וגם מקום)

תודה. טוב הדוגמה למעלה הייתה יחסית פשוטה, יש דברים כמו זה: http://i.imgur.com/Y8Xhgje.png שאין לי מושג מאיפה להתחיל לחשב את הסיבוכיות. יש איזושהי דרך שיטתית לזה (או לפחות דרך נוחה להסתכל על הדברים האלה)?

שלום, מישהו יכול בבקשה לרענן את זכרוני לגבי איך מחשבים סיבוכיות מקום, למשל בפונקציות כמו זו: http://i.imgur.com/ja3lDXI.png איך הייתם מחשבים עבורה את S(n)? (או במילים אחרות אילו דברים "מוסיפים" לסיבוכיות המקום.) תודה מראש =]

גורם לתהות על מה בכלל מדברים שם בהרצאות שזה כזה לא חשוב...

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

הממ שכחתי שיש גם מועד ב', זה רעיון טוב, תודה D: חבל שכבר כמעט בלתי אפשרי לתפוס מקום בקורס... (אגב, לא הלכת בכלל להרצאות?) בקשר לאת"ם מצאתי את הבחינה של החורף האחרון, http://www.scribd.com/doc/125751984/ATAM-moedA-Winter2011-2012, קצת קשה לי לפענח מה הולך שם אבל נראה שזה עונה לתיאור שהבאת.

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

שאלה תמימה: כמה גרוע זה כבר יכול להיות? (בתור מישהו שלא רוצה לדחות את הקורס הזה מסיבות כאלה ואחרות.)

עריכה: אחמ לא משנה, נפלה טעות בפוסט.

סה"כ 4 טרנס'? זה מה שניסיתי לעשות, יצא ממש ארוך אז כנראה שטעיתי איפשהו (למשל בסימן שבתוך הטרנס').

http://i.imgur.com/cwIFtja.png אפשר בבקשה כיוון לשאלה? אני לא בטוח איזו טרנס' לורנץ צריך לעשות פה.