סיבוכיות קולמוגורוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ בוט: החלפת טקסט אוטומטית (-שנות הששים +שנות השישים) |
||
שורה 2:
סיבוכיות קולמוגורוב איננה תלויה באופן מהותי בשפת ה[[תכנות]] אליה מתייחסים מכיוון שלכל שתי שפות ניתן לכתוב תוכנית בגודל סופי המהווה [[מפרש (תוכנה)|מפרש]] (interpreter) של אחת לשנייה. הדבר נכון במיוחד כשמתעניינים בסיבוכיות קולמוגורוב של סדרה של מחרוזות,
לסיבוכיות קולמוגורוב קוראים גם "סיבוכיות אלגוריתמית". היא פותחה על ידי [[אנדריי קולמוגורוב]], מתמטיקאי [[ברית המועצות|סובייטי]], באמצע שנות
השימוש במושג מאפשר לעתים לפשט הוכחות מורכבות למדי. לדוגמה, ניתן להוכיח באמצעותו, במספר שורות, גרסה חלשה של [[משפט המספרים הראשוניים]].
|