מציג תוצאות 1 עד 3 מתוך 3

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

  1. #1
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

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

    שלום חברים.

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

    אני לא יודע איך עושים את זה.

    אשמח לקבל דרך.
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: png קטלן.png‏ (87.6 ק"ב , 8 צפיות) Find_1D_Local_Peak(arr, left, right)1. n right-left+12. If n=1 return left3. mid L3] + left4. If mid=1 and arr[mid +1] Sarr[mid]a. Return mid5. Else if arr[mid - 1] arr[mid]i. Return Find_1D_Local_Peak(arr, left, mid-1)b. Elsei. Return Find_1D_Local_Peak(arr, mid+1, right)Question 5Prove the correctness of the effecient correct) algorithm for finding a 1D localpeak you saw in the lecture. You can find its pseudocode in the recitationsummary (the routine named Find 1D Local Peak in the recitation summaryin the moodle)


  2. #2
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    תראה ניסיון ואגיד לך אם אתה בכיוון.
    אהבתי Helpme אהב \ אהבו את התגובה
     

  3. #3
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

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

    עד כאן התשובה לכך שהאלגוריתם באמת עוצר.
    זה נכון?

    בעניין הנכונות:
    נוכיח את הטענה באינדוקציה על גודל המערך.

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

    צעד האינדוקציה: נניח שהטענה נכונה על כל מערך בגודל של עד n (כולל).
    כעת יש לנו מערך בגודל n+1.
    התוכנית לוקחת את אמצע המערך ומחלקת ל-3 מקרים (שורה 4,5, ו-6):

    1. האמצע הוא פיק, אז התוכנית מחזירה אותו וסיימנו.

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

    א'. אם הוא צמוד לאיבר הנוכחי אז בתת-מערך הוא מהווה את הקצה הימיני, ולכן התוכנית אומרת לנו שהוא אינו קטן יותר מהאיבר שמשמאלו, בנוסף - אנחנו יודעים שהוא גדול יותר מהאיבר שמימינו שהרי האיבר שמימינו זה האיבר הנוכחי והגענו למקרה הזה תחת ההנחה שהוא גדול יותר מהאיבר הנוכחי (שורה 5.a).

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

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

    3. מטעמי סימטריה אותה הוכחה כמו 2 רק מחליפים בין ימין לשמאל.


מידע אודות האשכול הנוכחי

Users Browsing this Thread

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

ביקרו באשכול זה : 2

הרשאות

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

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו