סיבוכיות קולמוגורוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט מוסיף: fr:Complexité de Kolmogorov |
מ בוט החלפות: ענייני; |
||
שורה 1:
'''סיבוכיות קולמוגורוב''' ב[[מדעי המחשב]], באה לספק אמת מידה על המשאבים הדרושים לייצור אובייקט מסוים. סיבוכיות קולמוגורוב של [[מחרוזת (תכנות)|מחרוזת]] מוגדרת כאורך תוכנית המחשב המינימלית שהפלט שלה הוא המחרוזת. המושג של סיבוכיות קולמוגורוב מתקשר לנושאים מ[[תורת האינפורמציה]], [[דחיסה]] ו[[למידה חישובית]].
סיבוכיות קולמוגורוב איננה תלויה באופן מהותי בשפת ה[[תכנות]] אליה מתייחסים מכיוון שלכל שתי שפות ניתן לכתוב תוכנית בגודל סופי המהווה [[מפרש (תוכנה)|מפרש]] (interpreter) של אחת לשנייה. הדבר נכון במיוחד
לסיבוכיות קולמוגורוב קוראים גם "סיבוכיות אלגוריתמית". היא פותחה על ידי [[אנדריי קולמוגורוב]], מתמטיקאי [[ברית המועצות|סובייטי]], באמצע שנות הששים של המאה העשרים. במקביל הוצע הרעיון על ידי ריי סולומונוף (Ray Solomonoff) וגרגורי צ'ייטין (Gregory Chaitin).
| |||