מערך A בגודל n נקרא "יוני-מודאלי" (Unimodal) אם הסדרה עולה עד לאיבר מקסימלי מסוים ("הפסגה") ואחריו יורדת. לדוגמה: {1,2,4,9,12,8,5} (הפסגה היא 12). מותר להניח שכל איברי המערך שונים זה מזה. הפסגה יכולה להיות גם בקצה (מקרה מונוטוני).
א. (10 נק') כתבו אלגוריתם המוצא את האינדקס של האיבר המקסימלי (הפסגה) במערך יוני-מודאלי בזמן O(logn). הסבירו בקצרה את נכונות האלגוריתם.
ב. (8 נק') נתון מערך יוני-מודאלי. תארו בקצרה אלגוריתם למיון המערך בזמן לינארי (O(n)). ניתן להשתמש במערך עזר. הסבירו בקצרה את נכונות האלגוריתם.
ג. (7 נק') נתון מערך כלשהו של n מספרים שונים (לאו דווקא יוני-מודאלי). הוכיחו שלא ניתן להפוך אותו ליוני-מודאלי (כלומר לשנות את סדר איבריו כך שהוא יהיה יוני-מודאלי) בזמן o(nlogn) (או קטנה של nlogn).
הערה: המספרים בכל הסעיפים לאו דווקא שלמים.
האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א
חיפוש בינאריסיבוכיותאלגוריתמיםמערכיםמיוןחסם תחתוןהוכחת נכונות
נתבונן בשגרה הבאה המקבלת כקלט מערך A של מספרים שונים זה מזה:
הסבר: בכל שלב של הלולאה השגרה בוחרת את ערך המיקום ה- ⌊n/2⌋ בתחום הנתון (1 עד n), ומשתמשת בו כאיבר ציר כדי לבצע חלוקה בתחום זה. בלולאה הבאה התחום מצטמצם בחצי.
הערה: השגרה partitionWithPivot מחליפה את איבר הציר עם האיבר האחרון וקוראת לשגרת החלוקה הרגילה.
א. מהו זמן הריצה של השגרה הנתונה?
ב. נוסיף לתכונת ערימת המינימום את התכונה הבאה: כל איבר ברמה h קטן מכל האיברים ברמה h+1.
הוכיחו או הפריכו: ניתן לבנות ערימת מינימום המקיימת את התכונה שלעיל בזמן לינארי.
האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א
סיבוכיותניתוח אלגוריתמיםסטטיסטיקות סדרערימותמבנה נתוניםהוכחת נכונותתכנון מבנה נתונים
נתונה ערימת מקסימום בינארית H עם n איברים שונים, המיוצגת על-ידי מערך.
א. (10 נק') נתון מספר x. תארו אלגוריתם שמחזיר את כל האיברים בערימה שגדולים מ-x בסדר יורד. האלגוריתם צריך להיות output-sensitive. כלומר, זמן הריצה יהיה O(mlogm), כאשר m הוא מספר הצמתים שהוחזרו. מותר זיכרון נוסף O(m).
הסבירו בקצרה מדוע האלגוריתם נכון וכיצד תכונת הערימה מאפשרת "גיזום" תתי-עצים.
ב. (8 נק') ידוע שהצומת y הוא עלה בערימה H. כתבו נכון/לא נכון: זמן הריצה למחיקת הצומת y מהערימה הוא O(1) במקרה הגרוע. נמקו את תשובתכם בקצרה.
ג. (7 נק') הוכיחו שכל אלגוריתם המקבל את הערימה H ומספר k, וקובע בוודאות האם k נמצא בערימה חייב במקרה הגרוע לבקר Ω(n) צמתים. שימו לב: יש לספק הוכחה ולא להסתפק בהסבר כללי ש"ערימה אינה עץ חיפוש".
האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א
ערימותתכנון מבנה נתוניםאלגוריתמיםסיבוכיותניתוח אלגוריתמיםחסם תחתוןהוכחת נכונות
א) נגדיר "מחסנית מינימום" SM (Stack Minimum), כמבנה המכיל מספרים טבעיים ותומך בפעולות הבאות: הציעו מימוש ל"מחסנית מינימום".
המפתחות אינם ייחודיים (יכולות להיות חזרות).
יש לכתוב שגרות עבור כל הפעולות. ב) פרופסור טונוס טוען שמצא מימוש ל"מחסנית מינימום" עם הזמנים הנדרשים בסעיף א, והוא טוען שהוסיף למבנה גם את הפעולה הבאה: הוכיחו שהפרופסור טועה. הערות: - כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.
האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר ב
מבנה נתוניםמחסניותתכנון מבנה נתוניםסיבוכיותחסם תחתוןהוכחת נכונותמיון
א) (9 נקודות) נתונה ערימת מינימום A אשר כל איבר בה הוא מספר ממשי (המפתח).
הערמה הייתה נתונה למתקפת סייבר של יריב זדוני, ויתכן שהוחלפו בה ערכי המפתחות בצמתים השונים, אך לא היו שינויים מעבר לכך.
כתבו שגרה ליניארית הבודקת אם הערימה היא עדיין ערימת מינימום תקנית.
תזכורת: ערימה ממומשת ע"י מערך.ב) (8 נקודות) נתון עץ חיפוש בינארי T אשר כל צומת בו מכיל מספר ממשי (המפתח).
העץ היה נתון למתקפת סייבר של יריב זדוני, ויתכן שהוחלפו בו ערכי המפתחות בצמתים השונים, אך לא היו שינויים מעבר לכך.
כתבו שגרה ליניארית הבודקת אם העץ הוא עדיין עץ חיפוש בינארי תקני.ג) (8 נקודות) נתון עץ ערכי מיקום T אשר כל צומת בו מכיל מספר ממשי (המפתח).
העץ היה נתון למתקפת סייבר של יריב זדוני, ויתכן שהוחלפו בו ערכי size של הצמתים השונים, אך לא היו שינויים מעבר לכך.
כתבו שגרה ליניארית הבודקת אם העץ הוא עדיין עץ ערכי מיקום תקני.הערות:- שימו לב לפתור באופן עדין ולהקפיד על סדר הפעולות.
- אנא הקפידו על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
- בשאלה זו (בשלושת הסעיפים) מספיק הסבר נכונות אינטואיטיבי וקצר.
- כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.
האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר ב
ערימותעצי חיפושעץ חיפוש בינארימבני נתונים מורחביםעץ ערכי מיקוםמבנה נתוניםסיבוכיותניתוח אלגוריתמיםסריקת עציםהוכחת נכונותמערכים
נתונה ערימת מקסימום A בגודל n שכל איבר בה הוא מספר ממשי ייחודי (כלומר, אין שני מספרים זהים), וכן נתון מספר טבעי k<n.א) (12 נקודות) כתבו שגרה המדפיסה את k המספרים הגדולים ביותר בערימה.
פתרו בזמן O(k2).
תוכלו להניח כי k<logn.
ניתן "להרוס" את הערימה המקורית.תזכורת: אם אתם מניחים הנחה כלשהי לגבי מיקום k האיברים הגדולים ביותר יש להסביר היטב מדוע היא מתקיימת (אין צורך בהוכחה פורמאלית).ב) (13 נקודות) כתבו שגרה המדפיסה את k המספרים הקטנים ביותר בערימה.
פתרו בזמן O(n).
ניתן "להרוס" את הערימה המקורית.הערות:- בקורס זה ערימה ממומשת ע"י מערך.
- בשאלות אלגוריתמיות יש להקפיד על כתיבת רעיון, אלגוריתם, נכונות וסיבוכיות.
- אלגוריתם = שגרה = סדרת פקודות מוגדרות היטב בעברית או באנגלית.
- שימו לב לפרט בנכונות טענות וסדרי פעולות שאינם טריוויאליים.
- כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.
האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר ב
ערימותמבנה נתוניםאלגוריתמיםסיבוכיותניתוח אלגוריתמיםסטטיסטיקות סדרמערכיםהוכחת נכונות
שאלה מותאמת לסמסטר הלימוד
שאלה 6 (25 נקודות) – השאלה מיועדת רק לסטודנטים שלמדו בשנת 2024תכננו מבנה S, שהוא עץ א"ש, שמפתחותיו הם מספרים טבעיים, ושניתן לבצע עליו את הפעולות הבאות:BUILD(S,A): בניית S ממערך ממוין A בגודל n, בזמן ריצה O(n).INSERT(S,k): מכניס את המפתח k למבנה. זמן הריצה O(logn).HEAVIEST−PATH(S): החזרת סכום מפתחותיו של המסלול הפשוט הכבד ביותר שמתחיל בשורש, בזמן ריצה O(n).
(מסלול פשוט = מסלול שאינו עובר באף צומת יותר מפעם אחת).דוגמא: בעץ זה, המסלול הכבד ביותר המתחיל בשורש הוא המסלול 5-2-4-3, וסכום מפתחותיו הוא 14.
(הצמתים השחורים בעץ שחורים באיור והצמתים האדומים בעץ אפורים באיור)א) (8 נקודות) הוכיחו בשלילה כי המסלול הפשוט הכבד ביותר שמתחיל בשורש חייב להסתיים בצומת ששני בניו הם T[nill].ב) (9 נקודות) כתבו את שגרת HEAVIEST−PATH(S).ג) (8 נקודות) כתבו את שגרת BUILD(S,A).הערות:- המבנה צריך להיות כזה שמאפשר את כל הפעולות המפורטות ביעילות הנדרשת, אך אין צורך לממש פעולות שלא נדרשתם לממש.
האוניברסיטה הפתוחהמועד ב · 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)=2T(n−3)+1
האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר א
סימון אסימפטוטיאסימפטוטיקההוכחת נכונותנוסחת נסיגהרקורסיהניתוח אלגוריתמים
א) (13 נקודות) תהיינה f,g:N→R+נגדיר יחס חדש Ol עבור סעיף זה בלבד:
נגדיר ש- f(n)=Ol(g(n)) אם קיים ε>0 שעבורו f(n)=O(g(n)logε(n)).הוכיחו או הפריכו:
אם f(n)=Ol(g(n)) וגם g(n)=Ol(h(n)) אז f(n)=Ol(h(n)).
יש להוכיח או להפריך על פי ההגדרה.ב) (12 נקודות) להלן שתי פונקציות f,g:N→R+. יש לקבוע ולהוכיח האם מתקייםf(n)=Θ(g(n)) או f(n)=ω(g(n)) או f(n)=o(g(n)).שימו לב לא לכתוב "מתקיים יחס o", אלא "מתקיים f(n)=o(g(n))" (למשל).f(n)=i=1∑ni2i2+1g(n)=n2log(n)הערות:- כל אחד מהסעיפים עומד בפני עצמו, וניתן לפתרון גם אם לא פתרתם הסעיף האחר.
האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר א
סימון אסימפטוטיהשוואת פונקציותאסימפטוטיקההוכחת נכונותניתוח אלגוריתמים
א) (15 נק') נתון עץ חיפוש בינארי T עם מפתחות ייחודיים, ונתונים מצביעים לשני צמתים U,V, כאשר נתון U.key<V.key.
נתבונן באלגוריתם הבא שמבקר בכל האיברים בטווח [U…V]:
הראו כי זמן הריצה של האלגוריתם הוא O(h+k), כאשר h הוא גובה העץ, ו-k הוא מספר האיברים בתחום. הניחו כי Visit(X) מתבצע בזמן O(1).
אין צורך בניתוח פורמאלי. מספיק הסבר מדוייק.
הדרכה: שרטטו עץ וסמנו עליו את הצמתים הרלוונטיים ואת המסלול שעושה האלגוריתם.
ב) (10 נק') פרופסור בוניאן סבור שגילה תכונה מעניינת ביותר של עצי חיפוש בינאריים.
נניח שחיפוש מפתח k בעץ חיפוש בינארי מסתיים בעלה. נתבונן בשלוש קבוצות:
A - המפתחות משמאל למסלול החיפוש.
B - המפתחות במסלול החיפוש.
C - המפתחות מימין למסלול החיפוש.
פרופסור בוניאן טוען שכל שלושה מפתחות a∈A,b∈B,c∈C מקיימים בהכרח a≤b≤c.
הביאו דוגמא נגדית לטענתו של הפרופסור ע"י שרטוט עץ חיפוש קטן שמפריך את טענתו.
האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר א
עצי חיפושניתוח אלגוריתמיםסיבוכיותהוכחת נכונותסריקת עצים