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

מילון מונחים

 

 

א    ה    ח    מ    ס    פ    ק    ר   

 

 

א

 

האוסף P הינו האוסף P=U DTIME(f) (f פולינום).

אוסף כל השפות שאפשר להכריע אותם בסיבוכיות זמן פולינומית.

 

NP=U NTIME(f)   האוסף 

כל השפות שיש להן מ"ט לא דטרמיניסטית שמקבלת אותן בזמן פולינומי.

 

ה

 

הכרעת שפות: תהי  S,h),(Q,S,d M=  מכונת טיורינג. נאמר כי M  מכריעה את  

אם לכל wÎS1*  מתקיים:

  ( s , # w #)|-----( h , # 1 # )                                    אם  wÎ L         

                                    ) # o  ( s , # w #)|-----( h , # אם   wÏ L     

כלומר, אם מילה נמצאת בשפה, המכונה תחזיר 1 , אחרת היא תחזיר 0.

 

ח

 

חישוב פונקציה: תהי *1∑→*2∑:f , ותהי S,h),(Q,S,d M=  מכונת טיורינג ,

כאשר    S2 È 1S Ê S

נאמר כי M  מחשבת את f  לכל  wÎS1*

(s, #w # )     M*      (h, #, f (w) # ).

 

חישוב פונקציה עם K פרמטרים: תהי 2* ∑→K(*1∑):f   (= פונקציה ששולחת k פרמטרים, k מחרוזות)  ותהי S,h),(Q,S,d M= מכונת טיורינג.

 נאמר כי M  מחשבת את f  אם לכל   w1, w2,.….wk Î (S1*) k   מתקיים:

( s, #w1#, #w2 #, ….. wk # )|---- (h, #, f (w1,w2, ….wk) # )

 

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