איך לתרגל שאלות נוסחת נסיגה במבני נתונים ומבוא לאלגוריתמים?

באתר prepd תמצאו שאלות נוסחת נסיגה במבני נתונים ומבוא לאלגוריתמים ממבחנים אמיתיים של האוניברסיטה הפתוחה. השאלות ממוינות לפי רמת קושי.

כמה שאלות נוסחת נסיגה יש במבני נתונים ומבוא לאלגוריתמים?

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

מה חשוב לדעת על נוסחת נסיגה לקראת מבחן במבני נתונים ומבוא לאלגוריתמים?

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

מבני נתונים ומבוא לאלגוריתמים - נוסחת נסיגה

סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש

סטטיסטיקות מבחנים

תתי-נושאים של רקורסיה

רמת קושי:

א. פתרו את נוסחת הנסיגה הבאה:

T (n) = T (n /2) + lo g n

T (1) = Θ (1)

ב. קבעו נכון/לא נכון, עם נימוק קצר:

$lo g (n!) = Θ (n lo g n)$
$n = o (n lo g n)$
$(lo g n)^{10} = o (n^{0.1})$
$\sum_{k = 0}^{l o g n} k = Θ (lo g n)$

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א

★★★★★

נוסחת נסיגהסימון אסימפטוטימשפט האבהשוואת פונקציותאסימפטוטיקה

א. נתון אלגוריתם הרץ באופן רקורסיבי. בכל שלב, האלגוריתם מבצע עבודה של

n

(לינארית בגודל הקלט), ומבצע קריאה רקורסיבית אחת לקלט בגודל

n - 2

.
1. כתבו את נוסחת הנסיגה

T (n)

.
2. פתרו את הנוסחה ומצאו חסם (

Θ

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

(lo g n)^{3}, n \cdot lo g n, n / lo g n, n^{0.9}, lo g (n!)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א

★★★★★

נוסחת נסיגהרקורסיהניתוח אלגוריתמיםאסימפטוטיקהסימון אסימפטוטיהשוואת פונקציותסיבוכיות

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 2 T (\frac{n}{2}) + n lo g^{2} (n) if n < 100 if n \geq 100

ב) (12 נקודות) נתונות שתי פונקציות

f, g : N \to R^{+}

f (n) = 2^{l o g_{4} n}

g (n) = n^{2}

i. (6 נקודות) פרופסור אילוביץ' טענה כי השיטה הכי טובה להכריע מהו היחס האסימפטוטי בין

f (n)

ל-

g (n)

היא להחיל

lo g ()

על שתי הפונקציות, לבדוק מהו היחס האסימפטוטי בין

lo g (f (n))

ל-

lo g (g (n))

, ולטעון כי היחס האסימפטוטי נשמר.
הסבירו מהי הבעיה הלוגית בשיטתה של פרופסור אילוביץ'.

ii. (6 נקודות) יש לקבוע ולהוכיח האם מתקיים

f (n) = Θ (g (n))

או

f (n) = ω (g (n))

או

f (n) = o (g (n))

.
שימו לב לא לכתוב "מתקיים יחס

o

", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

הערות:

כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר ב

★★★★★

נוסחת נסיגהמשפט האבסיבוכיותאסימפטוטיקהניתוח אלגוריתמיםסימון אסימפטוטיהשוואת פונקציות

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 2 T (\frac{2 n}{3}) + 5 n \cdot lo g^{3} (n) i f n = 1 i f n > 1

ב) (12 נקודות) הוכיחו או הפריכו כל אחת מהטענות הבאה:

i.

2^{n} = Θ (2^{2 + n})

ii.

2^{n} = Θ (2^{2 \cdot n})

הערה: ניתן להפריך יחס

f (n) = Θ (g (n))

ע"י הוכחה שמתקיים יחס

f (n) = ω (g (n))

, או יחס

f (n) = o (g (n))

.

הערות:

כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר ב

★★★★★

נוסחת נסיגהמשפט האבסימון אסימפטוטיניתוח אלגוריתמיםהשוואת פונקציותאסימפטוטיקה

א) (13 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

T (n) = {Θ (1) 4 T (\frac{n}{4}) + n + \frac{1}{n} i f n = 1 i f n > 1

ב) (12 נקודות) להלן שתי פונקציות

f, g : N \to R^{+}

. יש לקבוע ולהוכיח האם מתקיים

f (n) = o (g (n))

או

f (n) = ω (g (n))

או

f (n) = Θ (g (n))

.
שימו לב לא לכתוב "מתקיים יחס o", אלא "מתקיים

f (n) = o (g (n))

" (למשל).

f (n) = n^{10 l o g n}

g (n) = (lo g n)^{n}

הערות:

כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר ב

★★★★★

נוסחת נסיגהמשפט האבסימון אסימפטוטיניתוח אלגוריתמיםהשוואת פונקציותאסימפטוטיקה

א) (10 נקודות) הוכיחו על פי ההגדרה את תכונת הטרנזיטיביות עבור היחס

Ω

:
לכל

f, g, h

פונקציות מהטבעיים לטבעיים,
אם

f (n) = Ω (g (n))

וגם

g (n) = Ω (h (n))

אזי

f (n) = Ω (h (n))

.

ב) (15 נקודות) מצאו חסם אסימפטוטי הדוק עבור

T (n)

. הניחו כי

T (0) = 1

T (n) = 2 T (n - 3) + 1

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר א

★★★★★

סימון אסימפטוטיאסימפטוטיקההוכחת נכונותנוסחת נסיגהרקורסיהניתוח אלגוריתמים

להלן נתונה השגרה הרקורסיבית הבאה, שהקלט שלה הוא תמורה של

(1, 2, ..., n)

(האינדקסים של

A

הם בין 1 לבין

n

, וכן מתקיים שלכל

1 \leq i \leq n

קיים

1 \leq j \leq n

יחיד כך ש

A [j] = i

), וכן שני אינדקסים

1 \leq p, r \leq n

.
הקריאה הראשית לשגרת DoesItSort על מערך

A

הינה: DoesItSort(A, 1, n).

השגרה ReverseSort(A, i, j) ממיינת הפוך את תת המערך $A [i ... j]$ , למשל ReverseSort(A, 2, 5) עבור $A = [3, 4, 6, 1, 2, 5]$ ישנה את $A$ ל- $A = [3, 6, 4, 2, 1, 5]$ .
Partition היא שגרת החלוקה המופיעה בעמוד 122 בספר.

א) (5 נקודות) הריצו את השגרה DoesItSort על המערך

A = (7, 5, 1, 3, 2, 4, 6)

.

ב) (10 נקודות) הוכיחו או הפריכו: DoesItSort(A, 1, n) ממיינת את מערך

A

.
אם לדעתכם השגרה ממיינת כל מערך

A

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

A

בגודל

n

שהוא תמורה של

(1, ..., n)

, שעבורו

A

בסוף ביצוע השגרה אינו ממויין.

ג) (10 נקודות) נתחו את זמן הריצה של DoesItSort(A, 1, n) במקרה הגרוע ביותר ובמקרה הטוב ביותר, בהנחה שסיבוכיות ReverseSort(A, 1, n) היא

Θ (n^{2})

.
יש לכתוב נוסחאות נסיגה עבור המקרה הגרוע ועבור המקרה הטוב ולפתור אותן.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר א

★★★★★

סיבוכיותרקורסיהנוסחת נסיגהמיוןניתוח אלגוריתמיםמעקב אחר אלגוריתםמיון מהירהוכחת נכונות

דני שינה את תנאי העצירה של מיון מהיר ובמקום לכתוב

if p < r

בשורה הראשונה הוא כתב

if p < r - k

(שגרת מיון מהיר נמצאת בעמ' 122).

בהנחה ש-

k

הוא פרמטר לשגרה, מה יהיה זמן הריצה של מיון מהיר של דני במקרה הטוב ובמקרה הגרוע כפונקציה של

n

ו-

k

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2024 · סמסטר א

★★★★★

מיוןמיון מהירסיבוכיותנוסחת נסיגה

פתרו את נוסחת הנסיגה הבאה:

T (n) = 2 T (0.7 n) + n + n

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמבחן סמסטר א · 2024 · סמסטר א

★★★★★

נוסחת נסיגהסיבוכיותמשפט המאסטר

נתון יחס הנסיגה הבא לאלגוריתם רקורסיבי:

T (n) = 2 T (\frac{n}{2}) + n

פתרו את יחס הנסיגה בשתי שיטות:

א. שיטת עץ הרקורסיה.

ב. משפט האב (Master Theorem). ציינו לאיזה מקרה שייכת הנסיגה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחה2023 · סמסטר ב

★★★★★

רקורסיהסיבוכיותנוסחת נסיגה

שאלות נוסחת נסיגה במבני נתונים ומבוא לאלגוריתמים עם פתרונות

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