|
שימו לב: *נא להגיש רק את שאלות 1-5.
- שאלה 6 שייכת למעשה לקורס חדו"א. אנא וודאו שהנכם מבינים את המשפט, אך אין צורך להגיש את התשובה.
- שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.
|
אנא הוכח או הפרך את הטענות הבאות:
.
.
.
.
.
|
שימו לב: הכוונה בסעיף הראשון לפונקציה הקבועה , ולא לקבוע 80.
|
נתונות שתי פונקציות:


כאשר
.
- האם
?
- האם
?
נתבונן בפסוודו-קוד הבא:
Foo(n)
1 Bar-1(n)
2 Bar-2(n)
3 Bar-3(n)
נתון:
- זמן הריצה של
Bar-1(n)
הוא
.
- זמן הריצה של
Bar-2(n)
הוא
.
- זמן הריצה של
Bar-3(n)
הוא
.
עבור כל אחד מהחסמים הבאים, אנא ציין האם הוא בהכרח מתקיים, בהכרח לא מתקיים, או שאי אפשר לקבוע בוודאות האם הוא בהכרח מתקיים או לא:
- זמן הריצה של
Foo(n)
הוא
.
- זמן הריצה של
Foo(n)
הוא
.
- זמן הריצה של
Foo(n)
הוא
.
אנא כתוב מימוש יעיל לפונקציה Find-Num-In-Range(A, a, b)
, המקבלת:
- מערך ממויין
A
של מספרים שלמים חיוביים
- מספר שלם חיובי
a
- מספר שלם חיובי
b
גדול ממש מa
ומחזירה את מספר האיברים בA
שכל אחד מהם נמצא בתחום
.
דוגמה:
אם
A = [1, 2, 4, 5, 99 , 11999] ,
אז
Find-Num-In-Range(A, 3, 99) תחזיר 2 (יש שני איברים בתחום).
|
- הערה: אנא מצא מימוש הפועל בזמן לוגריתמי באורך המערך.
להלן הפונקציה Merge
המקבלת שני מערכים ממויינים:
# Merge.
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge(L, R)
1 Merged = Make-Array( Length(L) + Length(R) )
2 l = r = m = 1
3 while l <= Length(L) or r <= Length(R)
4 if r > Length(R)
5 Merged[m++] = L[l++]
6 else if l > Length(L)
7 Merged[m++] = R[r++]
8 else if L[l] < R[r]
9 Merged[m++] = L[l++]
10 else
11 Merged[m++] = R[r++]
12 return Merged
אנא הוכח שהפונקציה מחזירה מערך ממויין המכיל את איחוד ערכי מערכי הכניסה, ונתח את סיבוכיות הפונקציה.
אנא הוכח אחד מחסמי האינטגרלים הבאים (שתי ההוכחות דומות מאד זו לזו):
- אם
מונוטונית לא יורדת, אז ![{\displaystyle \displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e904a3978702831a002b072b8c21e07caa6717db)
- אם
מונוטונית לא עולה, אז ![{\displaystyle \displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7aa781e7f8a129153032b83188b464a60655dfad)
ו
הן פונקציות חיוביות ממש,
והגבול
קיים ושווה ל
. אנא הוכח או
הפרך את הטענה הבאה: אם
או
, אז
.
אנא הוכח או הפרך כ"א מהכללים הבאים:


היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה
כך שמתקיים
אבל הגבול
אינו קיים.