איך לתרגל שאלות משפט האב במבני נתונים ומבוא לאלגוריתמים?

באתר 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 · סמסטר א

★★★★★

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

א) (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 · סמסטר ב

★★★★★

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

מצאו פתרון אסימפטוטי הדוק עבור נוסחת הנסיגה הבאה:

{T (1) = 2 T (n) = 4 T (n /8) + n^{α - 1} \cdot l g^{α} n

כאשר

α \geq 1

הוא פרמטר ממשי.

רמז: התייחסו למספר מקרים אפשריים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

מצאו פתרון אסימפטוטי הדוק עבור נוסחת הנסיגה הבאה:

{T (1) = 1 T (n) = 9 T (n /3) + n^{α} \cdot l g^{α + 1} n

כאשר

α

הוא פרמטר ממשי חיובי.

רמז: התייחסו לשלושה מקרים אפשריים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

T (n) = 4 T (\frac{n}{16}) + 2 n \cdot l g n + l g^{4} n

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

T (n) = 49 T (\frac{n}{7}) + n^{2} + n + 1

פתרו אותה בשיטת משפט האב:

א. זהו

a

b

f (n)

וחשבו

n^{l o g_{b} a}

.

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

ג. כתבו את הפתרון האסימפטוטי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

דף אימון – נוסחאות נסיגה

★★★★★

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

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

T (n) = 2 T (\frac{n}{2}) + n^{2}, T (1) = Θ (1)

פתרו אותה בעזרת משפט האב:

א. זהו את הפרמטרים

a

b

ו-

f (n)

.

ב. חשבו את

n^{l o g_{b} a}

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

ג. אמתו את תנאי הרגולריות (regularity condition) ורשמו את הפתרון.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

שאלה שנוצרה על-ידי AI בסגנון האוניברסיטה הפתוחה

★★★★★

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

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

T (n) = 25 T (\frac{n}{5}) + 125 n^{2}

פתרו אותה בשיטת משפט האב:

א. זהו את

a

b

ו-

f (n)

.

ב. חשבו את

n^{l o g_{b} a}

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

ג. כתבו את הפתרון האסימפטוטי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

דף אימון – נוסחאות נסיגה

★★★★★

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

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

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