סיבוכיות קולמוגורוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Felagund-bot (שיחה | תרומות) מ בוט - מחליף מסויים במסוים |
הסרת דעה אישית |
||
שורה 1:
'''סיבוכיות קולמוגורוב''' ב[[מדעי המחשב]] באה לספק אמת מידה על המשאבים הדרושים לייצור אובייקט מסוים. סיבוכיות קולמוגורוב של [[מחרוזת (תכנות)|מחרוזת]] מוגדרת כאורך תוכנית המחשב המינימלית שהפלט שלה הוא המחרוזת. המושג של סיבוכיות קולמוגורוב
סיבוכיות קולמוגורב איננה תלויה באופן מהותי בשפת התכנות אליה מתייחסים מכיוון שלכל שתי שפות ניתן לכתוב תוכנית בגודל סופי המהווה [[מפרש (תוכנה)|מפרש]] (interpreter) של אחת לשניה.
לסיבוכיות קולמוגורוב קוראים גם "סיבוכיות אלגוריתמית". היא פותחה ע"י [[אנדריי קולמוגורוב]], מתמתיקאי סובייטי.
==דוגמא==
בשביל להמחיש את הרעיון, ניתן לחשוב על המחרוזת הבאה: 001001001001001001001001001001001001001
שורה 8 ⟵ 9:
לעומת זאת, המחרות הבאה היא כנראה יותר מסובכת: 01100011100111100111000111000111110101101101
מכיוון שלא ניכר כלל פשוט המייצר אותה.
[[en:Kolmogorov Complexity]]
[[קטגוריה:מדעי המחשב]]
[[קטגוריה:מידע]]
| |||