אלגוריתמים Flashcards
1
Q
מהם השלבים לפתרון בעיות בקורס?
A
- הגדרה מדויקת של הבעיה
- אלגוריתם נאיבי
- חשיבה מלמעלה למטה
- הוכחת נכוחות - כתיבת משפט + טענות עזר, נוכיח את המשפט בעזרת טענות העזר, נוכיח את טענות העזר.
2
Q
שלבי רדוקציה
A
- קלט x
- ממיר קלט f
- אלג’ לבעיה B
- ממיר פלט g
- פלט y
רדוקציה = יצירת 2 אלגוריתמים
3
Q
תמחישי פתרון פשוט ברדוקציה עם כל השלבים של רדוקציה + השלבים לפתרון בעיות בקורס
A
4
Q
אם קשה לי לפתור בעיה, איזה בעיה אם אני אפתור קודם, אם יהיה לה פתרון אז יהיה פתרון לבעיה
A
“בעיית ההכרעה”
5
Q
תפתרי את בעיית תתי המחרוזות
A
