תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרה: הגהה, קישורים פנימיים |
|||
שורה 7:
==דוגמה לרדוקציה ומאפייניה==
נניח שנתנת לנו הבעיה הבאה: נתונה רשימת מספרים, ועלינו למצוא האם האיבר הגדול ביותר מופיע לפחות שלוש פעמים. כמובן שאפשר לפתור זאת בדרכים שונות. עם זאת, נניח שעומדת ברשותנו שגרה המקבלת רשימת מספרים, ומוצאת האם האיבר ה''קטן'' ביותר מופיע
# נקח את הרשימה המקורית, ונמיר אותה לרשימת המספרים ההפוכים בסימניהם לרשימה המקורית (לדוגמה, הרשימה <math>[1, -3, 4, 2]</math> תהפוך לרשימה <math>[-1, 3,-4, -2]</math>).
# נפעיל את השגרה שכבר קיימת לנו,
קל לראות ששיטה זו פותרת את הבעיה החדשה. אמ"ם האיבר הקטן ביותר ברשימה החדשה, נסמנו כ
<math>-y</math>
מופיע
אפשר לראות שהמרנו בעיה חדשה לבעיה קודמת, לגביה אנו יודעים יותר (במקרה זה, יש כבר שגרה כתובה לה), באופן שמועיל לפתרון. מה מאפיין המרה זו?
|