איך לתרגל שאלות הסתברות במבוא למדעי המחשב?

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

כמה שאלות הסתברות יש במבוא למדעי המחשב?

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

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

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

מבוא למדעי המחשב - הסתברות

תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות

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

רמת קושי:

בשאלה זו 4 סעיפים שאינם קשורים זה לזה.

סעיף א' (5 נק'):
נתון הקוד הבא:

א. עבור הקלט

l s t = [1, 3, 5, 5, 5, 5, 6, 7]

k ey = 5

, מה תחזיר הפונקציה?

ב. נסמן ב-

n

את אורך רשימת הקלט

l s t

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

n

.

סעיף ב' (5 נק'):
נתון האל"ב

{a, b, c, d}

וכן נתונים חמישה קידודים. לכל קידוד סמנו האם הוא prefix free, uniquely decodable but not prefix free, או not uniquely decodable. סמנו ב-X את המשבצת המתאימה.

1.

a = 0, b = 00, c = 000, d = 0000

a = 00, b = 01, c = 10, d = 11

a = 00, b = 01, c = 101, d = 110

a = 10, b = 101, c = 1011, d = 11

a = 0, b = 01, c = 011, d = 0111

סעיף ג' (10 נק'):
נזכר בהגדרה של hash_mod מתוך המחלקה hashtable שראינו בכיתה:
self.hash_mod = lambda key: hash_func(key) % m

נסמן ב-

n

את כמות האיברים שמכניסים ל-hashtable, וב-

m

את גודל הטבלה. נתון כי

n = 1024 \cdot m

, ומכניסים את כל המספרים מ-1 עד

n

ל-hashtable.

עבור המימושים הבאים ל-hash_func, ציינו עבור כל מימוש האם הוא:
1. מאפשר הכנסה וחיפוש תקינים בסיבוכיות זמן ממוצעת

O (1)

(כתלות ב-

n

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

O (1)

(כתלות ב-

n

).
3. לא מאפשר הכנסה או חיפוש תקינים.

סמנו X במשבצת הנכונה. הניחו כי פעולות אריתמטיות ופונקציות מהספרייה math ו-random רצות בזמן

O (1)

. לזכירכם, הפונקציה math.log(x,b) מחזירה float המייצג (בקירוב) את הערך של

lo g_{b} (x)

lambda x: x%10
lambda x: random.randint(x)
lambda x: 1
lambda x: -1*x
lambda x: int(math.log(x,2))

סעיף ד' (5 נק'):
נתונה הפונקציה הבאה המבוססת על הפונקציה page rank אשר ראינו בכיתה, אך אינה זהה לה:

עבור כל אחת מהטענות הבאות, קבעו האם היא נכונה או לא נכונה בסוף ריצת הפונקציה:

1. עבור

G = [[1], [2], [0]]

t = 30

— הרשימה counters תכיל את אותו מספר בכל האינדקסים.
2. עבור

G = [[1], [2], [0]]

t = 35

— הרשימה counters תכיל את אותו מספר בכל האינדקסים.
3. עבור

G = [[1, 3], [2], [0], [1]]

t = 30

— הרשימה counters תכיל את אותו מספר באינדקסים

0, 1, 2

.
4. עבור

G = [[1, 2], [3], [3], [0]]

t = 30

— הרשימה counters תכיל את אותו מספר באינדקסים

0, 3

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2026 · סמסטר א

★★★★★

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

נתונה הפונקציה הבאה המבוססת על הפונקציה page rank אשר ראינו בכיתה, איך אינה זהה לה:

עבור כל אחת מהטענות הבאות, קבעו האם היא נכונה או לא נכונה בסוף ריצת הפונקציה:

1. עבור

G = [[1], [2], [0]]

t = 30

— הרשימה counters תכיל את אותו מספר בכל האינדקסים.
2. עבור

G = [[1], [2], [0]]

t = 35

— הרשימה counters תכיל את אותו מספר בכל האינדקסים.
3. עבור

G = [[1, 3], [2], [0], [1]]

t = 30

— הרשימה counters תכיל את אותו מספר באינדקסים

0, 1, 2

.
4. עבור

G = [[1, 2], [3], [3], [0]]

t = 30

— הרשימה counters תכיל את אותו מספר באינדקסים

0, 3

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר א

★★★★★

מעקב אחר קודגרפיםPageRankהסתברות

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

נתונה ההרצה הבאה:

עבור כל אחת משורות הקוד הבאות, סמנו האם ערך הביטוי הוא בוודאות True, בוודאות False, או לא ניתן לקבוע בוודאות (ייתכן שהוא True וייתכן שהוא False):

1. res[1] + res[2] == 1
2. res[1] + res[2] > 0.2
3. res[4] <= res[3]
4. (res[0] == res[4]) or (res[4] == res[3])

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2023 · סמסטר ב

★★★★★

מעקב אחר קודגרפיםPageRankהסתברות

לפניכם הפונקציה PageRank שראיתם בתרגול, עם שינוי קטן בשורת ה-return של הפונקציה (השורה המקורית מחוקה, ושורה חדשה מודגשת). הניחו כי הספריה random יובאה (אחת ממחוקה). הניחו כי הפונקציה random.random() מחזירה מספר אקראי בקטע

[0, 1)

(לא כולל 1).

תזכורת:

r an d o m . r an d o m ()

מחזירה מספר אקראי בקטע

[0, 1)

.

בהינתן הרשמה

G = [[1, 2, 4], [3], [1, 2], [], []]

p = 1

t = 3

.

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

T r u e

, בוודאות

F a l se

, או לא ניתן לקבוע (ייתכן

T r u e

וייתכן

F a l se

):

1. res == [1,1,1,0,0] → אפשרי / לא אפשרי
2. res == [1,0,0,0,2] → אפשרי / לא אפשרי
3. res == [0,1,0,2,0] → אפשרי / לא אפשרי

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2023 · סמסטר א

★★★★★

מעקב אחר קודגרפיםPageRankהסתברות

שאלה 4 (25 נקודות)

סעיף א (5 נקודות)

השלימו בדף התשובות את הגדרת הפונקציה

public static int randomElement(int[] array)

פונקציה זו מקבלת מערך ומחזירה ערך אקראי מתוך המערך. יש להשתמש בפונקציה Math.random().

יש להניח שהמערך array אינו null ושאורכו לא אפס. יש לאפשר להחזיר כל ערך מתוך איברי המערך. להלן דוגמת שימוש:

תזכורת: הפונקציה Math.random() מחזירה ערך אקראי כלשהו

0.0 \leq x < 1.0

מטיפוס double.

סעיף ב (20 נקודות)

הגדרה: ערך האיבר ה-

k

במערך של מספרים שאורכו לפחות

k + 1

, הוא האיבר שהיה נמצא באינדקס ה-

k

של המערך אילו המערך היה ממוין מהקטן לגדול. להלן דוגמת שימוש:

השלימו (בעזרת פונקציות העזר הנתונות בהמשך) בדף התשובות את הגדרת הפונקציה הרקורסיבית

public static int kthValue(int[] array, int k)

שמקבלת ערך אי-שלילי

k

ומערך array שאורכו לפחות

k + 1

, ומחזירה את ערך האיבר ה-

k

במערך.

יש להניח שהערך

k

אינו שלילי, שהמערך array אינו null, שאורכו לפחות

k + 1

, ושכל האיברים במערך שונים זה מזה. אין למיין את המערך.

פונקציות עזר: נתונות לכם שתי פונקציות עזר בהם תוכלו להשתמש. הפונקציה splitLess מקבלת מערך array של שלמים וערך שלם value ומחזירה מערך בו כל הערכים מתוך array שהם קטנים ממש מהערך value. הפונקציה splitGreater מקבלת מערך array של שלמים וערך שלם value ומחזירה מערך בו כל הערכים מתוך array שהם גדולים ממש מהערך value.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת בן גוריוןמועד ב · 2020 · סמסטר א

★★★★★

רקורסיהמערכיםחיפושהסתברות

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

סעיף א

נתונה רשימה lst באורך

n

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

i

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

i

ברשימה lst.

על הפונקציה להיות מסיבוכיות זמן

O (n)

במקרה הגרוע.

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

סעיף ב

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

המחלקה תכיל שתי מתודות: __init__ ו-choose שאותן עליכם להשלים.

המתודה __init__ תקבל שני קלטים מטיפוס list בנוסף ל-self:
items הינו רשימה של $n$ איברים כלשהם,
weights הינו רשימה של $n$ מספרים מטיפוס float בתחום $(0, 1]$ שמייצגים משקלים.

כמו כן, מתקיים כי sum(weights) שווה 1.
קלטים אלו מקיימים שלכל

0 \leq i < n

המשקל של items[i] הינו weights[i].
המתודה שומרת את items בתוך שדה self.items, ואת weights בתוך השדה self.weights. בנוסף לשמירת הקלטים המתודה יכולה גם לעשות פעולות נוספות ולהגדיר שדה או שדות נוספים (וכן, גם להשתמש בפונקציה מסעיף א').
דרישה מחייבת: על סיבוכיות זמן הריצה הכוללת של __init__ להיות

O (n)

במקרה הגרוע.

המתודה choose לא תקבל קלט מלבד self. הפעלה שלה תחזיר איבר אקראי מתוך self.items בהתאם למשקל המתאים לו. כלומר הסיכוי של כל איבר להיבחר צריך להיות כמשקלו.

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

x

מטיפוס float שמקיים

0 \leq x < 1

.
דרישות מחייבות:

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

דוגמאות הרצה:

השלימו את המתודות __init__ ו-choose כנדרש:

ציינו מהי סיבוכיות המתודה choose שמימשתם כפונקציה של

n

O ()

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2018 · סמסטר א

★★★★★

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

לפניכם הפונקציה is_prime אשר נלמדה בהרצאה:

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

m

הוא פריק אף על פי שהוא בעצם ראשוני, בהסתברות של

(\frac{1}{4})^{100}

.

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

m

אשר יש לפרקו לגורמים — הוא יקרא לפונקציה is_prime(m, True). אם המספר אינו ראשוני הפונקציה תדפיס גם את העד (witness). כאשר דני יחלק את המספר

m

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

m

וכך יפצח את הקוד. האם תוכניתו של דני תצליח לפרק מספר פריק

m > 2^{1000}

לגורמים? אם לא, נמקו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2012 · סמסטר ב

★★★★★

הסתברותקריפטוגרפיה

אבן-נייר-מספריים. בסיבוב שני שחקנים שולפים סימן מ-

{R, P, S}

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

P < S

S < R

R < P

— והוא מקבל נקודה.

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

ב. יהופץ הבחין שצפניה לא חוזר על אותו סימן בסיבוב עוקב — הוא שלח רובוט:

כיתבו פונקציה player_yehopatz(history) שמקבלת את מהלך המשחק עד כה (רשימת זוגות) ומחזירה את הסימן הבא של יהופץ. מטרתו: לנצח כמה שיותר ולהפסיד כמה שפחות. הסבירו את האסטרטגיה.

ג. נתחו משחק בן

21

סיבובים בין player_yehopatz לבין רובו-צפניה: מהי התוצאה הטובה ביותר, הגרועה ביותר, והאופיינית ליהופץ?

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2012 · סמסטר א

★★★★★

הסתברותגנרטוריםמערכים

תמורה באורך

n

היא איברי

range (n)

מסודרים בסדר כלשהו. להלן מימוש בסיסי של מחלקת תמורות:

א. נגדיר את מטריצת התמורה

P = P (π)

המתאימה לתמורה

π

באורך

n

כמטריצה ריבועית

n \times n

שבה:

P_{ij} = {1, 0, π [i] = j π [i] \neq = j

כיתבו מתודה בשם to_matrix שמחזירה Matrix ובו מטריצת התמורה המתאימה ל-self. הסבירו במילים וממשו בקוד פייתון.

ב. נאמר שתמורה היא מלכותית אם כשנציב

n

מלכות על־גבי לוח שחמט

n \times n

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

π

ומחזירה ערך בוליאני האם היא מלכותית. דוגמה:

π = [4, 2, 0, 6, 1, 7, 5, 3]

מלכותית.

ג. נתון גנרטור perms(n) המחזיר איטרטור שעובר (בסדר כלשהו) על כל התמורות באורך

n

. כיתבו פונקציה royal_prob(n) שמחזירה מספר ממשי

0 \leq p_{n} \leq 1

שהוא ההסתברות שתמורה מקרית (מהתפלגות אחידה) באורך

n

היא מלכותית.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2011 · סמסטר ב

★★★★★

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

נתון כרומוזום

X

המיוצג כמחרוזת באורך

n = 200000000

תווים מעל הא"ב

Σ = {A, C, G, T}

. הכרומוזום מכיל מספר לא ידוע של צמדי חזרות ארוכים (

k \geq 100

).

שלשת מספרים

(i, j, k)

תיקרא צמד חזרה אם

0 \leq i < j \leq n - k

ומתקיים

X [i : i + k] = X [j : j + k]

. צמד חזרה ייקרא מקסימלי אם הוא לא מוכל בצמד חזרה אחר:

X [i - 1] \neq = X [j - 1]

ו-

X [i + k] \neq = X [j + k]

.

*דוגמה:* ב-

X =

"ATCAAGTCAATCA" הצמדים המקסימליים מאורך

\geq 3

הם

(0, 9, 4), (1, 6, 4), (6, 10, 3)

.

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

k \geq 100

ב-

X

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

ב. ממשו את האלגוריתם בקוד פייתון, עם הערות לחלקים הלא-טריוויאליים.

ג. הניחו

m

צמדי חזרות, כולם באורך

100 \leq k < 1000

. תנו חסם על מספר הפעולות ועל כמות הזיכרון הנצרכת (כפונקציה של

n, m

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2011 · סמסטר ב

★★★★★

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

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

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