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

מילון מונחים מ-פ

 

א    ה    ח    מ    ס    פ    ק    ר   

 

 מ

 

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

המכונה מכילה בקר מרכזי שמכיל מספר סופי של מצבים (מצבי המכונה).

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

 יש לו קצה שמאלי.

החלק השלישי של המכונה הוא הראש קורא- כותב, שיכול לזוז ימינה ושמאלה, לקרא ולכתוב.

 

מכונת טיורינג לא דטרמינסטית הינה חמישיה: S,h), (Q, Δ, = N

כאשר: Q                    קבוצת מצבים סופית.

S             א"ב  סופי ( S Î (#

 Î Q             h      מצב עצירה.

             Î Q s      מצב התחלתי.

                  Δ       טבלת מעברים

 [ (Q – { h } ) x S ] x [ Q x S È { L, R }

 

תהי S קבוצת סימנים. מערכת ריצוף מעל S הינה זוג (A=(C,c0

כאשר CεS×S×S×S קבוצת אריחים סופית.

coεC – אריח התחלתי (לפינה השמאלית התחתונה).

 

ס

 

תהי L שפה, ותהי f:N→N . נאמר כי L בעלת סיבוכיות זמן f, אם קיימת מ"ט M שפועלת בסיבוכיות זמן f ו-M מכריעה את L.

 

פ

 

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

 

פונקציה תקרא פונקציה רקורסיבית אם אפשר ליצור אותה מהפונקציות הבסיסיות בשימוש של הרכבה רקורסיה ומינימיזציה.

 10-02-04 / 11:05  עודכן ,  10-02-04 / 09:52  נוצר ע"י שמרית דויטש  בתאריך 
 מילון מונחים א-ח - הקודםהבא - מילון מונחים ק-ר 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 7