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

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

כמה שאלות ספיקות יש באלגוריתמים?

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

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

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

אלגוריתמים - ספיקות

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

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

רמת קושי:

נתונה נוסחת 3-CNF

φ = φ_{1} \land \dots \land φ_{m}

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

x_{1}, \dots, x_{n}

בזה אחר זה, ולכל משתנה

x_{i}

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

הציגו נוסחת 3-CNF שעליה האלגוריתם החמדן נכשל: הנוסחה ספיקה, אך האלגוריתם מפיק השמה שאינה מספקת.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתונה נוסחת 3-CNF

φ

שבה כל אחד מהמשתנים

x_{1}, \dots, x_{n}

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

ספיקותזרימה ברשתותרדוקציהגרפיםהוכחה

רקע. נוסחת

k

-CNF היא

φ = φ_{1} \land φ_{2} \land \dots \land φ_{m}

, כשכל פסוקית היא

φ_{i} = (z_{i, 1} \lor z_{i, 2} \lor \dots \lor z_{i, k})

וכל

z_{i, j}

הוא ליטרל מבין

x_{1}, \dots, x_{n}, \neg x_{1}, \dots, \neg x_{n}

. השמה מתאימה לכל משתנה ערך

T

F

; היא מספקת את

φ

אם כל פסוקית מסופקת (לפחות ליטרל אחד בה אמת). הנוסחה ספיקה אם קיימת השמה מספקת.

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

φ

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

G

המותאם לנוסחה

φ

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהממ"ן 11

★★★★★

ספיקותגרפיםרדוקציההוכחת נכונות

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

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