סיבוכיות קולמוגורוב
סיבוכיות קולמוגורוב בודקת כמה קצר צריך להיות הקוד שמייצר מחרוזת. מחרוזת = שורה של 0 ו-1. אם אפשר לתאר מחרוזת בתוכנית קצרה, היא פשוטה. לדוגמה, 001001001... פשוטה. אפשר לכתוב לולאה שמדפיסה 001 כמה פעמים. מחרוזת בלי דפוס ברור נראית מסובכת. לעיתים אין דרך כללית לבדוק כמה מסובכת מחרוזת באמת. אנדריי קו...
אנדריי קולמוגורוב
אנדריי קולמוגורוב (1903, 1987) היה מתמטיקאי רוסי חשוב. נולד בטמבוב. אמו מתה בלידתו. דודתו גידלה אותו. למד בבית ואז באוניברסיטת מוסקבה. אהב מתמטיקה מאוד. היה תלמיד של ניקולאי לוזין. קיבל דוקטורט ב-1929. נסע לצרפת וגרמניה ב-1930. הפך לפרופסור ב-1931. ב-1939 התקבל לאקדמיה. נישא ב-1942. ב-1960 שיפר את ...