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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Gran (שיחה | תרומות)
מ ←‏הגדרות: הגהה, עיצוב
שורה 14:
 
{{הגדרה|תוכן=
סיבוכיות קולומוגורוב <math>K(x)</math> של מחרוזת <math>x</math>, היא אורך הקידוד המינימלי של מכונה, שעל קלט ריק עוצרת עם הפלט <math>x</math>:{{רווח קשיח|2}}
<center><math>K(x) = \min_{M \;:\; M(\epsilon) = x} \left|\langle M \rangle\right| </math></center>
}}
 
לעתים מחרוזתהמחרוזת <math>x</math> כבר ידועה, ואנו רוצים לתאר מחרוזת נוספת, <math>y</math>. בהנחה ש<math>x</math> ו<math>y</math> מתארים דברים דומים, ייתכן שתיאורשניתן להשתמש בתיאור של <math>x</math> שנתון לנו, ולאחריועל־מנת תיאורלתאר את <math>y</math> בהנחהבצורה ש<math>x</math> כבר תואר,יותר חסכוניפשוטה. לדוגמה, נניח ש<math>x</math> ו<math>y</math> מתארות כיצד לייצר את דגליהן של אירלנד ובלגיה (תמונות בצד). לאחר שנסביר מהו מלבן, מהו בד, ושאר הדברים שצריך כדי לתאר איך לייצר את דגל אירלנד, אפשר אולי לתאר את ייצור דגל בלגיה באמירה שהוא דומה לדגל אירלנד אלא שצבעיו הם כך וכך.
 
[[File:Flag of Ireland.svg|thumb|Flag of Ireland]]
[[File:Flag_of_Belgium_(civil).svg|thumb|Flag of Belgium (civil)]]
 
[[File:Flag_of_Belgium_(civil).svg|thumb|Flag of Belgium (civil)]]
{{הגדרה|תוכן=
לכל שתי מחרוזת <math>x</math> ו<math>y</math>, '''הסיבוכיות המותנית''' <math>K(y|x)</math> של <math>y</math> בהנתן <math>x</math> היאמוגדרת:{{רווח קשיח|2}}
 
<center><math>K(y|x) = \min_{M \;:\; M(x) = y} \left|\langle M \rangle\right| </math></center>
כלומר, האורך המינימלי של קידוד מ"ט שעבור הקלט <math>x</math> פולטת את <math>y</math>.
 
כלומר, תיאור מ"ט הקצרה ביותר הפולטת את <math>y</math> בהנתן <math>x</math>.
}}
 
{{תרגיל|יישור=ימין
|שאלה=וודא שהנך מביןהוכח את הסיבות לטענותהטענות הבאות:
#<math>K(xx) = K(x) + O(1)</math>
#<math>K(x|x) = O(1)</math>