שאלות ותשובות – מקבץ מס’ 6

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

אוטומטים סופיים ושפות רגולריות

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

דיון מקרי על אלגוריתמים הסתברותיים

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

אז איך באמת בודקים ראשוניות (בעזרת אלגוריתם מילר-רבין)?

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