הבהרה בנוגע לשימוש בלשון זכר: כדי למנוע סרבול מיותר, וכמקובל בשפה העברית, ננקטת לעתים לשון זכר בהתייחסות אל כלל הגולשות והגולשים ובמתן שמות לערכים. אנא קבלו זאת בהבנה.
|
שימו לב: *נא להגיש רק את שאלות 1-5.
- שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.
|
הפונקציה
נתונה על ידי הנוסחה.
.
אנא הוכח
.
רמז
נסה להוכיח זאת באותו אופן בו הוכחנו
. כלומר:
- הוכח בנפרד חסמי
ו .
- ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).
|
אנא מצא חסמים עליונים ותחתונים (כלומר, מסוג
ו
) טובים ככל האפשר לפונקציה
בכל אחד מהסעיפים הבאים. (
מתארת את זמן הריצה של אלגוריתם כלשהו.)
.
.
, כאשר
הוא קבוע כלשהו.
בנוסחת הנסיגה
,
מתארת את זמן הריצה של אלגוריתם כלשהו. אנא פתור את הנוסחה.
מתארת את זמן הריצה של אלגוריתם כלשהו. אנא הוכח שאם
אז
.
להלן פסוודו-קוד לפונקציה Foo
, המקבלת מספר שלם לא-שלילי ומחזירה מספר שלם:
Foo(n)
1 if n == 0
2 return 0
3 return n % 2 + Foo( ⌊n / 2⌋ )
אנא הסבר מה עושה הפונקציה (בלווי נימוק), ונתח את סיבוכיותה.
A[1, ..., n]
הוא מערך של מספרים שונים זה מזה. נאמר ש
הוא היפוך אם
אך
A[i] > A[j]
.
- במערך
[2, 3, 8, 6, 1]
יש 5 היפוכים. אנא רשום אותם.
- אנא מצא אלגוריתם יעיל למציאת מספר ההיפוכים במערך.
דוגמה:
נניח שיזינו לאלגוריתם שתכתוב את המערך בדוגמה של הסעיף הראשון. הפלט שהאלגוריתם שלך אמור להוציא הוא המספר 5.
|
רמז
תוכל אולי לשנות את מיון מיזוג. הוסף משתנים גלובליים ופונקציות עזר כרצונך, אם הדבר יעזור לך.
|
הפונקציה Alg
מוגדרת כך:
Alg(A, i, j)
1 if j <= i + 1
2 return
3 q = Sqrt(j - i + 1) # q = ⌊(j - i + 1)^(1/2)⌋
4 for k in [0, ..., q - 1]
5 Alg(A, i + k * q, i + (k + 1) * (q - 1))
6 Proc(A, i, j)
היא משתמשת בשתי הפונקציות הבאות:
- הפונקציה
Sqrt(n)
מחזירה את השורש הריבועי של
מעוגל כלפי מטה. היא פועלת בזמן
.
- הפונקציה
Proc
היא פונקציה כלשהי המקיימת שזמן ריצת Proc(A, i, j)
הוא
.
מהו זמן הריצה של Alg(A, 1, n)
?
נתונה מטריצה בת
עמודות ו
שורות. כל כניסה במטריצה היא 0 או 1, ולכן כל שורה מתארת מספר בינרי בעל
ביטים. השורות אינן מסודרות בסדר ידוע, אך ידוע שאין שתי שורות זהות. מכאן נובע שחסרה שורה להשלמת כל
המספרים האפשריים בעלי
ביטים.
דוגמה:
עבור , ייתכן שהשורה הראשונה היא המערך [0, 1] (המתאר בבינרית את המספר 1), השורה השנייה היא המערך [1, 1] (המתאר בבינרית את המספר 3), והשורה השלישית היא המערך [0, 0] (המתאר בבינרית את המספר 0). השורה החסרה היא המערך [1, 0] (המתאר בבינרית את המספר 2).
|
אנא תאר אלגוריתם המקבל מטריצה כזו, ומדפיס את השורה החסרה. נסה להגיע לאלגוריתם שסיבוכיותו
.
רמז
נסה להפוך את הבעיה לבעיה קטנה בחצי (בערך) בזמן לינארי.
|
אנא הוכחה את המשפט הבא:
משפט:
פתרון
![{\displaystyle \displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef62acc75f5d5fb22b3af4c4aa5b098c7db57bda) הוא  .
|
מתארת את זמן הריצה של אלגוריתם כלשהו, והיא פתרונה של נוסחת הנסיגה
. בנוסחה זו,
מספר
שלם גדול ממש מ1,
מספר גדול ממש מ1, ו
היא פונקציה
המקיימת
, עבור
שלם גדול ממש מ1.
אנא הוכח
.