רדוקציה וצרות אחרות

[אדם 08]

רדוקציה וצרות אחרות

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

 

[shira shira]

תנסה בפורום שיעורי בית או בפורום מתמטיקה

בהצלחה

 

[בני שור]

רדוקציות

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

 

[שלמה יונה]

הנושא לא טריוויאלי

אני יכול להמליץ על ספר לימוד שבו עשיתי שימוש כדי ללמוד את החומר הנ"ל כשלא הבנתי את המרצה: Introduction to the Theory of Computation מאת Michael Sipser לא תמצא שם מתכון כללי לרדוקציות, אמנם, אבל כן תמצא הסברים ברורים ומבוססים ודוגמאות רבות. ספר לימוד מצויין, לדעתי.

 

[אדם 08]

תודה