תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 184:
<math>x0^nx^r</math>
כאשר:
#<math>x</math> היא מחרוזת באורך <math>n</math>.
#<math>0^n</math> היא רצף של <math>n</math> אפסים.
#<math>x^r</math> היא המחרוזת <math>x</math> בהיפוך.
 
שורה 192:
היות שמדובר בפלינדרום, <math>M</math> חייבת לזהותו ככזה.
 
כל תו במחרוזת רשום בתא, ויש גבול בינו לבין התא שמימינו. במהלך ריצת האלגוריתם, חוצה ראש המכונה גבול זה מספר פעמים (החציות האי-זוגיות הן לכוון ימין, והאי זוגיות לכוון שמאל). בכל פעם שנחצה הגבול, <math>M</math> נמצאת במצב מסויים. נסמן ב<math>C(i)</math> את סדרת המצבים של החציות של תא <math>i</math>. בפרט נתמקד בסדרות החציות של התווים בחלק האמצעי של המחרוזת (החלק המורכב כולו מאפסים, כלומר <math>n \leq i \leq 2n</math>).
 
נניח שזמן ריצת האלגוריתם הוא
<math>t(n)</math>.
בהכרח, סך כל החציות, ובפרט סך כל החציות בתוך החלק האמצעי, הוא <math>t(n)</math> גם כן. מ[[w:עקרון שובך היונים|עקרון שובך היונים]] נובע שקיים <math>i</math> כלשהו בחלק האמצעי (כלומר <math>n \leq i \leq 2n</math>),
שעבורו
<math>\left|C(i)\right| \leq \frac{t(n)}{n}</math>.
שורה 225:
|פתרון=
המכונה עלולה לזהות גם מחרוזות מהצורה
<math>y = x0^nzz^r</math>.,
ולכן ללא <math>n</math>, לא יהיה זיהוי מוחלט של <math>x</math> דווקא.
}}