איך לתרגל שאלות סיבוכיות באלגוריתמים?

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

★★★★★

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

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

1, 3, 5

. בהינתן מחיר

n \geq 1

של מוצר, יהי

f (n)

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

4

אפשר כ-

3

ואז

1

, או

1

ואז

3

— שתי דרכים שונות).

(א) הציגו אלגוריתם יעיל שבהינתן

n \geq 1

מחשב את

f (n)

.

(ב) הוכיחו כי

f (n)

גדל בקצב מעריכי, כלומר קיים קבוע

c > 1

שעבורו

f (n) \geq c^{n}

. (מותר להניח לשם פשטות כי

n

מתחלק ב-

5

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

תכנות דינמינוסחת נסיגהסיבוכיות

הנחיות: אסור להשתמש באלגוריתם של 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 · סמסטר א

★★★★★

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

נתונה רשימה של

n

תיבות מלבניות: לכל

1 \leq i \leq n

נתון האורך

ℓ (i)

, הרוחב

w (i)

והגובה

h (i)

של התיבה מספר

i

. כל הרוחבים שונים, כל האורכים שונים וכל הגבהים שונים.

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

j

מונחת רק מעל תיבה

i

שמקיימת

w (j) < w (i)

וגם

ℓ (j) < ℓ (i)

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

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

Θ (n^{2})

. (בהקשר זה פעולות חיבור, חיסור והשוואה של מימדים

ℓ (i), w (i), h (i)

נחשבות פעולות אלמנטריות, שמתבצעות בזמן

Θ (1)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G = (V, E)

עם משקלים

w (e) > 0

וקדקוד מקור

s

. בנוסף נתון עץ פורש מכוון

T

המושרש ב-

s

. הציגו אלגוריתם המכריע האם

T

הוא אכן עץ מסלולים מזעריים (עמ"מ) מ-

s

. האלגוריתם חייב לרוץ מהר יותר אסימפטוטית מ-Dijkstra, ופלטו הוא "כן (Accept)" או "לא (Reject)" בלבד (אינכם נדרשים לחשב עמ"מ בעצמכם).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

יהי

f (n)

מספר הדרכים לסדר

n

עצמים באמצעות שני היחסים

<

ו-

=

. למשל

f (2) = 3

: עבור

2

עצמים

a, b

ישנם בדיוק

3

סידורים אפשריים:

a < b

a = b

, או

b < a

. באופן דומה

f (3) = 13

. הציגו אלגוריתם שעל קלט

n

מחשב את

f (n)

בזמן

Θ (n^{2})

ובזיכרון

Θ (n)

(פעולה אריתמטית — חיבור/כפל/השוואה של מספרים — מתבצעת בזמן

Θ (1)

). הדרכה: כל סידור מגדיר חלוקה של

n

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

<

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

תכנות דינמינוסחת נסיגהסיבוכיות

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

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