קודים לתיקון שגיאות (שניתנים לבדיקה מקומית)

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

משפט ה-PCP או: איך למדתי להפסיק לדאוג ולאהוב הוכחות הניתנות לבדיקה הסתברותית

אחד מהנושאים הלוהטים ביותר במדעי המחשב המודרניים הוא משפט ה-PCP, הרחבותיו והשלכותיו. אלא שכל הקשור ל-PCP עשוי להישמע מוזר מאוד כששומעים לראשונה מה ראשי התיבות הללו מסמלים: Probabilistically Checkable Proofs, הוכחות הניתנות לבדיקה הסתברותית. מה זה בכלל, ואיך אפשר לזהם … להמשיך לקרוא

אז מה הקשר בין אוטומטים ופונקציות יוצרות?

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

פונקציות יוצרות

אחת מהבעיות הבסיסיות בקומבינטוריקה היא בעיית הספירה של אובייקטים. יש קבוצה של אובייקטים מסוג מסויים – נניח, מספרים שמקיימים תכונה מסויימת, גרפים שנראים כך וכך, דרכים לחלק גלידה לילדים, קלטים האפשריים לאלגוריתם וכו', ואנחנו רוצים לדעת כמה בדיוק יש. לרוב … להמשיך לקרוא