שיחה:88-280 תשעג סמסטר א

חזרה לדף הקורס

גלול לתחתית העמוד

הוספת שאלה חדשה

הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).

-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן

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

שאלות

תרגיל 1

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

תשובה:

אפשר פשוט להשתמש בהגדרה:

[math]\displaystyle{ f(n)=o(g(n)) }[/math] (סימון אחר [math]\displaystyle{ f(n)\ll g(n) }[/math]) אם [math]\displaystyle{ \lim_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|=0 }[/math].

(כלומר g גדלה מהר יותר מ-f)

וככה לדרג את כל הפונקציות

תרגיל 1 שאלה 4

נראה לי שיש טעות באלגוריתם. בשורה: return j, זה צריך להיות לדעתי return i. כמו שזה עכשיו הוא תמיד יחזיר את אותו הערך, את n.
אגב, קצת פחות חשוב, אבל צריך להיות רשום A[j]==i במקום a[j]==i

תשובה: נכון, זה צריך להיות return i. אני מעלה מחדש את קובץ התרגיל עם התיקון. תודה

שאלה 1 פונקציה 1

[math]\displaystyle{ e^{\log_d n^3} = e^{3\log_d n} = e^{3\frac{\log_e n}{\log_e d}} = n^{\frac{3}{\log_e d}} }[/math] מדוע במקרה זה לא חשוב לדעת את הבסיס של הלוגריתם?

לדוגמא, במידה ו [math]\displaystyle{ d=\sqrt[100]{e} }[/math] אז הפונקציה שייכת ל: [math]\displaystyle{ O(n^{300}) }[/math] ואילו אם [math]\displaystyle{ d=e^3 }[/math] אז הפונקציה שייכת ל: [math]\displaystyle{ O(n) }[/math]
וזה משפיע כמובן על היחס של קצב הגידול שלה לעומת פונקציה 2 לדוגמא.

תשובה: נכון

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

אך כאשר מדובר בלוגריתם באקספוננט זה זה כן משנה.
המשך שאלה:
אז איך אני אמור לדרג את הפונקציה הזאת לעומת פונקציות 2,6 או 8 כשהבסיס אינו ידוע?

תשובה: אתם יכולים להניח שהבסיס הוא e, כלומר זה ln. --Jeniiiiibee 11:59, 4 בנובמבר 2012 (IST)

שאלות (טכניות) לגבי תרגיל 2

1. לכותבים ב-c++, מהם שמות ההגשה? בקובץ עצמו רשומים אותם שמות הגשה לשני החלקים. שמות הגשה צוינו בתרגיל
2. בקבצים עצמם, הפונקצייה שאני צריך להגיש היא פונקציית main? פונקציית ה-main צריכה להיות הראשית בקובץ
3. האם צריך להגיש גם מייקפייל? לא, כל התוכנית צריכה להיות בקובץ אחד (אתם מגישים קובץ יחיד)
4. בעבור חלק 1 כתוב שאם יש מסלול הוא יחיד, מצד שני בדוגמה השנייה שנתת יש שתי אפשרויות למסלולים (פעם אחת המסלול שנפל, ופעם השנייה המסלול שנפלט בתוספת ה-W האחרונה). האם להניח שאכן יש מסלול אחד? אם אי אפשר להניח זאת, איזה מסלול לפלוט? אפשר להניח שקיים מסלול יחיד. אני אתקן את הדוגמא
5. בחלק 1, האם המחסנית חייבת להיות מחסנית של האותיות במבוך, או לחילופין אפשר שהמחסנית תכלול בתוכה מבני נתונים אחרים (למשל, structים בסיסיים או מחרוזות).המחסנית צריכה להכיל את הנקודות של המסלול בלבד
6. בחלק 2, בדוגמות - עבור הדוגמה הראשונה, האם הפלט לא אמור להיות 6 (עבור המסלול A -> B -> b -> p -> t -> g), ובדוגמה השנייה, האם הפלט לא אמור להיות 5? כתוב ששתי אותיות זהות לא יכולות להיות צמודות במסלול

תודה מראש.

שאלה על תרגיל 2

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