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

אשכול: הסבר לרדוקציה

  1. #1
    משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל הסבר לרדוקציה

    שלום,
    אני לא מצליח לרדת לשורש העניין ברדוקציה.
    למשל נתונה לי
    CodeCogsEqn.gif

    אומרים
    אם L מזוהה טיורינג (בת מניה) ולא כריעה אז L^R מזוהה טיורינג (בת מניה) ולא כריעה

    אז עכשיו מוכיחים את זה בעזרת רדוקציה
    מוכיחים ש L^R מזוהה טיורינג ע"י הרדוקציה L
    CodeCogsEqn (1).gif

    ויש צד שני שאותו נעזוב כרגע.
    איך מוכיחים את הרדוקציה הזאת?
    הבנתי שהפונקציה של הרדוקציה היא
    f(x) = x^R
    מה זה אומר?

    ואשמח להסבר

    תודה

  2. #2
    הסמל האישי שלגל_כהן חובב מתמטיקה מושבע חבר Emath בכיר

    פרטי משתמש

    ברירת מחדל

    כאששר אתה עושה רדוקציה משפה A לשפה B, אזי למעשה אתה מגדיר פונקציה חשיבה (כזו שבהינתן קלט כלשהו תוכל לחשב
    את הפלט הנדרש) אשר עבורה $x\in A \iff f(x)\in B$. במקרה הזה, הפונקציה שלך תהיה $f(x)=x^R$, כלומר בהינתן מחרוזת x,
    הפונקציה תחזיר את המחרוזת ההפוכה. כעת, f היא חשיבה ומובן ש-$x\in L\iff x^R\in L^R$, אזי זוהי רדוקציה כנדרש.
    אהבתי abuksis12 אהב \ אהבו את התגובה
     
    עזרו לך? תן פידבק!

    ציטוט :

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



  3. #3
    משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי גל כהן צפה בהודעה
    כאששר אתה עושה רדוקציה משפה A לשפה B, אזי למעשה אתה מגדיר פונקציה חשיבה (כזו שבהינתן קלט כלשהו תוכל לחשב
    את הפלט הנדרש) אשר עבורה $x\in A \iff f(x)\in B$. במקרה הזה, הפונקציה שלך תהיה $f(x)=x^R$, כלומר בהינתן מחרוזת x,
    הפונקציה תחזיר את המחרוזת ההפוכה. כעת, f היא חשיבה ומובן ש-$x\in L\iff x^R\in L^R$, אזי זוהי רדוקציה כנדרש.
    אוקי תודה הבנתי,
    אפשר לתאר את האלגוריתם של f(x) ככה? :

    הרדוקציה:
    בהינתן קלט <M,w> לשפה L^R נבנה קלט <N> לשפה L כך ש:
    CodeCogsEqn (2).gif

    N(x) :
    - נפעיל את M על w
    - אם w=x^R נעצור ונקבל
    - אחרת נעצור ונדחה

    אפשר ככה? (זה פשוט התבנית שלמדנו לרדוקציה)

  4. #4
    אסיסטנט חבר Emath בכיר

    פרטי משתמש

    ברירת מחדל

    קצת התבלבלת - מה שכתבת זה תבנית לרדוקציה כאשר השפות הן שפות של מכונות טיורינג עם תכונה כלשהי (למשל בעיית העצירה). במקרה הזה L היא שפה של מילים כלשהן מעל הא"ב שלך ולאו דווקא שפה של קידודי מכונות טיורינג.
    הרדוקציה היא בדיוק מה שגל כתב מקודם - בהינתן קלט $x$ לשפה $L^R$ הפלט של הרדוקציה (שהוא בעצם קלט לשפה $L$) יהיה $x^R$.
    בצורה יותר קצרה פונקציית הרדוקציה f מוגדרת להיות $f(x)=x^R$. ברור ש-f חשיבה ומקיימת את תנאי הרדוקציה $x\in L^R \Leftrightarrow f(x) \in L$.
    אהבתי abuksis12 אהב \ אהבו את התגובה
     

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

Users Browsing this Thread

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

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

There are no members to list at the moment.

הרשאות

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

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