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

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

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

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

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

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

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

עיצוב וניתוח אלגוריתמים, תכנות דינמי, אלגוריתמים חמדניים וגרפים

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

תתי-נושאים של סיבוכיות

רמת קושי:

תת-סדרה רצופה של הסדרה

(x_{1}, x_{2}, ..., x_{n - 1}, x_{n})

הינה סדרה מהצורה

(x_{i}, x_{i + 1}, ..., x_{k - 1}, x_{k})

, עבור איזשהם

1 \leq i \leq k \leq n

. הציגו אלגוריתם שבהינתן סדרת מספרים שלמים

(x_{1}, ..., x_{n})

מוצא בתוכה את תת-הסדרה הרצופה שסכומה מרבי. למשל, בסדרת הקלט

(- 1, 4, - 3, 5, - 1, - 1, 1, - 1)

תת-הסדרה הרצופה שסכומה מרבי הינה

(4, - 3, 5)

שסכומה

4 - 3 + 5 = 6

.

על האלגוריתם המוצע לרוץ בזמן

Θ (n)

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

Θ (1)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

תכנות דינמיניתוח אלגוריתמיםסיבוכיות

(שאלה רלוונטית לסטודנטים משנת 2025/2026)

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

A, B

מסדר

n \times n

מעל שדה פשוט. ניחו לשם פשטות כי

n

הינו חזקה של

2

. תוצאת המכפלה הינה מטריצה

C = A \times B

מסדר

n \times n

, שמקיימת

C_{i, j} = \sum_{1 \leq k \leq n} A_{i, k} \times B_{k, j}

. נפרק כל מטריצה ל-4 תתי-מטריצות מסדר

\frac{n}{2} \times \frac{n}{2}

, כדלקמן:

A = (a c b d), B = (e f g h), C = (r t s u)

מהגדרת כפל מטריצות:

r = a \times e + b \times f, s = a \times g + b \times h

t = c \times e + d \times f, u = c \times g + d \times h

האלגוריתם מחשב את 7 המטריצות הבאות:

P_{3} = (c + d) \times e, P_{5} = (a + d) \times (e + h), P_{1} = a \times (g - h)

P_{4} = d \times (f - e), P_{6} = (b - d) \times (f + h), P_{2} = (a + b) \times h

P_{7} = (a - c) \times (e + g)

(א) הסבירו כיצד לחשב את

r, s, t, u

באמצעות פעולות חיבור וחיסור בלבד על

P_{1}, ..., P_{7}

(ללא הכפלת מטריצות). לדוגמה:

u = - P_{7} + P_{5} + P_{1} - P_{3}

(אסורה הכפלת מטריצות).

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

(א) ברצוננו להפיק תחזית מזג-אוויר למחרתיים, עבור

n

אתרים. לכל אתר

1 \leq k \leq n

נתונות שלוש מטריצות:

A_{k}

מסדר

n \times lo g n

(מצב מזג-האוויר היום),

B_{k}

מסדר

lo g n \times n

(השינוי מהיום למחר, כך ש-

C_{k} := A_{k} \cdot B_{k}

הוא מזג-האוויר מחר), ו-

D_{k}

מסדר

n \times n

(השינוי ממחר למחרתיים, כך שמזג-האוויר במחרתיים הוא

C_{k} \cdot D_{k}

). הציגו אלגוריתם יעיל ככל האפשר לחישוב מזג-האוויר במחרתיים בכל האתרים.

(ב) הציגו אלגוריתם לחישוב המכפלה

A \cdot E

של שתי מטריצות

n \times n

, אם

A

מקיימת שכל שורה בה היא הזזה מחזורית של השורה הראשונה (מטריצה מחזורית/circulant): אם השורה הראשונה היא

(a_{0}, a_{1}, \dots, a_{n - 1})

, אזי שורה

t

היא

(a_{n - t + 1}, \dots, a_{n}, a_{0}, a_{1}, \dots, a_{n - t})

. נדרש זמן

o (n^{3})

(רק אלגוריתם, ללא הוכחה).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

השאלה עוסקת במימושים שונים לתור-קדימויות עם

n

מפתחות, במסגרת הפעלת האלגוריתם של Dijkstra או של Prim. שלושה מימושים: רשימה דו-כיוונית לא ממוינת, ערימה-בינארית, וערימת-פיבונאצ'י (שזמני-הריצה שלה amortized). לכל אורך התשובה השמיטו את הסימנים האסימפטוטיים

O, Θ

. נסמן

n = ∣ V ∣

m = ∣ E ∣

.

(א) השלימו את זמני-הריצה של כל פעולה בכל מימוש.

(ב) רשמו את זמן-הריצה הכולל של Dijkstra/Prim בכל מימוש (בניית התור

+ n \cdot

שליפת-מינימום

+ m \cdot

הקטנת-מפתח), וקבעו לאילו צפיפויות עדיף כל מימוש.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון גרף מכוון

G = (V, E)

עם משקלים אי-שליליים

c (e) \geq 0

על הצלעות, וקדקוד מוצא

r \in V

. הביטו באלגוריתם הבא:

(i) מאתחלים מערך

A

A [r] = 0

ו-

A [v] = \infty

לכל

v \neq = r

.
(ii) לולאה חיצונית: חוזרים שוב ושוב על הפעולה הבאה:
> (ii.1) לולאה פנימית: סורקים את הצלעות בסדר לקסיקוגרפי; לכל

e = (u, v) \in E

מבצעים: אם

A [v] > A [u] + c (e)

אז מעדכנים

A [v] \leftarrow A [u] + c (e)

.
> (ii.2) אם בהרצה הנוכחית של כל הלולאה הפנימית לא בוצע אף עדכון — האלגוריתם מסתיים.

(א) מה האלגוריתם מחשב? (אין צורך להוכיח.)

(ב) יהי

B (n)

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

n

קדקודים. חשבו את

B (n)

, והציגו סדרת גרפים

G_{n}

שעליהם מתבצעות בדיוק

B (n)

איטרציות.

(ג) הציגו סדרת גרפים אחרת

G_{n}^{'}

שעבורם נכנסים ללולאה החיצונית פעמיים בלבד, וזאת למרות שמספר הצלעות שלהם זהה לגרפים מסעיף (ב), כלומר

∣ E (G_{n}^{'}) ∣ = ∣ E (G_{n}) ∣

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

בלמן-פורדגרפיםמסלולים קצריםניתוח אלגוריתמים

נתון גרף מכוון

G = (V, E)

עם משקלים אי-שליליים

c (e) \geq 0

על הצלעות ונתון קדקוד מסוים

r \in V

. הביטו באלגוריתם הבא:

(i) מאתחלים מערך חד-ממדי

A

באמצעות הכלל:

A [v] = {0, \infty, v = r v \neq = r

(ii) לולאה חיצונית: חוזרים שוב ושוב על הפעולה הבאה.

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

e = (u, v) \in E

מבצעים:
אם

A [v] > A [u] + c (e)

אז מעדכנים

A [v] \leftarrow A [u] + c (e)

.

(ii.2) אם בהרצה הנוכחית של כל הלולאה הפנימית לא בוצע אף עדכון, אז האלגוריתם מסיים.

(א) רישמו מה מחשב האלגוריתם (אין צורך להוכיח נכונות).

(ב) יהי

B (n)

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

n

קדקודים. חשבו את

B (n)

, והציגו סדרת גרפים

G_{n}

עליהם מתבצעות בדיוק

B (n)

איטרציות.

(ג) הציגו סדרת גרפים אחרת

G_{n}^{'}

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

∣ E (G_{n}^{'}) ∣ = ∣ E (G_{n}) ∣

לכל

n

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

ניתוח אלגוריתמיםמסלולים קצריםבלמן-פורדסיבוכיותגרפיםמעקב אחר אלגוריתם

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

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