» נושאי לימוד
» נושאי לימוד
יום שישי 10 ביולי 2020
מבחן מסכם
דף ראשי  מבחן מסכם גרסה להדפסה

מבחן מסכם

 

          

                       בנו מכונת טיורינג המקבלת את השפה המכילה את המילה הריקה בלבד

 

 

            

                         תהיינה 2L, 1L שפות מעל אותו אלפבית. הוכיחו כי אם 2L, 1L ניתנות להכרעה ,

             גם 2L Ç 1L ניתנת להכרעה.

 

 

      

                        הוכיחו כי הפונקציה C11  :N->N   ,   C11(x)=1היא פונקציה פרימיטיבית רקורסיבית

 

 

הוכיחו כי sign: N->N

        sign(x)= x=0     0           

 x>0    1            

        היא פונקציה פרימיטיבית רקורסיבית

 

 

    

        הוכיחו כי log2x=ëlog2xû (עיגול כלפי מטה של log על בסיס 2) היא פונקציה פרימיטיבית

        רקורסיבית.

 

      הגדרה: שפת תכנות ברמה הנמוכה ביותר צריכה לכלול את המרכיבים הבאים:

1. השמת קבוע  2. השמת משתנים  3. הסתעפות מותנית- if   4. הסתעפות בלתי מותנית- go to  

 5. פעולות אריתמטיות בסיסיות  6. מערכים.

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

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

)X=31

Y=1(2

3)Z=X

4)If Z==0 then go to 8

5)Y=Y+1

6)Z=Z-1

7)Goto 4

8)End

 

 

 

   

            האם השפה         {P  עוצרת על "ישראל" HIsrael= { P|  ניתנת להכרעה או לא?

 

 

   

          {P  עוצרת על w תוך לא יותר מ- k צעדים | (P,w,k) } = Hk_stop

          האם שפה זו ניתנת להכרעה?

 

 

 

 27-01-04 / 11:20  עודכן ,  01-01-04 / 14:13  נוצר ע"י שמרית דויטש  בתאריך 
 הגדרת בעיות P ו- NP - הקודםהבא - קישורים לאתרים וספרות 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 5