מפגש חמישי - 26.2.23
בפגישה החמישית עסקנו בשני נושאים. תחילה, דנו בהקבלה של סיבוכיות קולמוגורוב לאינפורמציה ע"פ תורתו של שאנון. ראינו שניתן להגיע להגדרה מקבילה ל"מידע הדדי", כמו בתורתו של שאנון, עד כדי גורמים לוגריתמיים. כך הבנו שהשימוש הסמנטי במונח "מידע" בהקשר של סיבוכיות קולמוגורוב, מוצדק גם ברמה המתמטית. לאחר מכן נחשפנו לראשונה אל ההתפלגות האוניברסלית, ולדוגמה ראשונה בשימוש בה, כדי לעמוד על ההבדלים בין סיבוכיות-הזמן-הממוצעת לסיבוכיות-הזמן-הגרועה-ביותר של האלגוריתם quicksort. ראינו את ההטיה שההתפלגות האוניברסלית מייצרת כלפי קלטים שקל לתאר (בעלי מעט אינפורמציה), ואת ההשלכות עבור ניתוח זמני ריצה באמצעותה.