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

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

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

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

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

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

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

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