|
שימו לב: *נא להגיש רק את שאלות 1-5.
- שאלה 6 שייכת למעשה לקורס חדו"א. אנא וודאו שהנכם מבינים את המשפט, אך אין צורך להגיש את התשובה.
- שאר השאלות הן לצורך חזרה למבחן בלבד. אין צורך להגיש את התשובות להן.
|
אנא הוכח או הפרך את הטענות הבאות:
.
.
.
.
.
|
שימו לב: הכוונה בסעיף הראשון לפונקציה הקבועה , ולא לקבוע 80.
|
נתונות שתי פונקציות:
![{\displaystyle \displaystyle f(n)=n+c_{1}n\log ^{2}(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b10ff2cb4632bf4b104e99f684688d34dd0ce4d)
![{\displaystyle \displaystyle g(n)=n+c_{2}n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c973cc2997dec311fbf99aab37550fed8e95958)
כאשר
.
- האם
?
- האם
?
נתבונן בפסוודו-קוד הבא:
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)
ו
הן פונקציות חיוביות ממש,
והגבול
קיים ושווה ל
. אנא הוכח או
הפרך את הטענה הבאה: אם
או
, אז
.
אנא הוכח או הפרך כ"א מהכללים הבאים:
![{\displaystyle \displaystyle f(n)+g(n)=\Theta (\max\{f(n),g(n)\})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/005e6bb0e4e4d838bf4f98444b79a7eb17c4cf78)
![{\displaystyle \displaystyle f(n)-g(n)=\Theta (\max\{f(n),g(n)\})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c40c23cb1a25674f06efc2c42cd78af982efe030)
היא פונקציה חיובית ממש, מונוטונית עולה, ושואפת לאינסוף. אנא הוכח שקיימת פונקציה
כך שמתקיים
אבל הגבול
אינו קיים.