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

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

★★★★★

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

א) (15 נק') הוכיחו או הפריכו את הטענה הבאה:
לכל

f, g

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

f (n) = O (g (n))

אז

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

.
יש להוכיח על פי ההגדרה או להפריך ע"י דוגמא נגדית.

ב) (10 נק') להלן שתי פונקציות

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) = i = 0 \sum n - 1 \frac{1}{n - i}

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 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 · סמסטר א

★★★★★

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

א) (13 נקודות) תהיינה

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

נגדיר יחס חדש

O_{l}

עבור סעיף זה בלבד:
נגדיר ש-

f (n) = O_{l} (g (n))

אם קיים

ε > 0

שעבורו

f (n) = O (g (n) lo g^{ε} (n))

.

הוכיחו או הפריכו:
אם

f (n) = O_{l} (g (n))

וגם

g (n) = O_{l} (h (n))

אז

f (n) = O_{l} (h (n))

.
יש להוכיח או להפריך על פי ההגדרה.

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

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

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

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

או

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

או

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

.

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

o

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

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

" (למשל).

f (n) = i = 1 \sum n \frac{2 i ^{2} + 1}{i}

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

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתונות הפונקציות הבאות:

f (n) = {1 n n = 2 k, k \in N n = 2 k + 1, k \in N

g (n) = n + 1

עבור שלושת האפשרויות שלהלן, כתבו נכון/לא נכון והסבירו את תשובתכם:
1.

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

f (n) = O (g (n))

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

סיבוכיותסימון אסימפטוטי

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

n = 2^{k} - 1

(עבור

k > 0

)?

לתשובה חיובית, תארו את שיטת השחזור, הסבירו מדוע היא נכונה, ונתחו את זמן הריצה שלה; לתשובה שלילית, הביאו דוגמה נגדית או הסבירו מדוע לא ניתן לשחזר (באופן חד משמעי) את העץ.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

עצי חיפושעץ אדום-שחורסריקת עציםסימון אסימפטוטי

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

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