האם גוגולפלקס הוא הסמל של סוף המספרים? (לא)

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

אנליזה וקטורית – תכונות בסיסיות של הנגזרת

אז הכרנו את הנגזרת של פונקציה \(f:\mathbb{R}^{n}\to\mathbb{R}^{m}\) וראינו איך אפשר לחשב אותה באמצעות נגזרות חלקיות. בואו נעבור עכשיו לכמה תוצאות תיאורטיות כלליות וקלות יחסית, כדי שנתרגל; עד סוף הפוסט נגיע להצגת תוצאה לא טריוויאלית ושימושית – משפט הפונקציה ההפוכה. אבל … להמשיך לקרוא

משפט קוק-לוין

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

התעלומה המסתורית של הנער המבריק, יחס הזהב והנוסחה השגויה במוזיאון

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

אנליזה וקטורית – נגזרת ונגזרת חלקית

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

אנליזה וקטורית – מבוא

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

על משחקים ומספרים (חלק ב': מספרים. וקצת משחקים)

בפוסט הקודם התחלתי לבנות קבוצה של מספרים שהמוטיבציה אליהם הגיעה איכשהו מתוך משחקים קומבינטוריים. כזכור, הבניה הייתה פשוטה להפליא: כל מספר מיוצג על ידי אובייקט מהצורה \(\left\{ L|R\right\} \) כאשר \(L,R\) הן קבוצות, וכלל הבניה שלנו הוא ש"מספר" הוא אובייקט … להמשיך לקרוא

על משחקים ומספרים (חלק א': משחקים. וקצת מספרים)

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

משפט קלייני – הוכחה נוספת

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

למת הניפוח לשפות רגולריות – גרסה מלאה

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

משפט מייהיל-נרוד – נקודת מבט נוספת, ואלגוריתמי מינימיזציה

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

בעיות הכרעה עבור שפות פורמליות

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

שפות חסרות הקשר – תכונות סגור

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

חידת יום הולדת

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

שפות חסרות הקשר – למת הניפוח, הלמה של אוגדן ושפות רב משמעיות

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

שקילות אוטומט מחסנית ודקדוק חסר הקשר

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

אוטומט מחסנית

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

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

תכירו – מסלולי מוצקין. מסלול מוצקין מאורך \(n\) הוא מסלול ב-\(\mathbb{Z}^{2}\) שמתחיל ב-\(\left(0,0\right)\) ומסתיים ב-\(\left(n,0\right)\) ומורכב משלושה סוגים אפשריים של צעדים: ימינה, למעלה-ימינה ולמטה-ימינה. כלומר, אנחנו כרגע ב-\(\left(x,y\right)\) אז אנחנו יכולים לעבור אל \(\left(x+1,y+\delta\right)\) כאשר \(\delta\in\left\{ -1,0,1\right\} \). והנה העלילה … להמשיך לקרוא

מבוא לדקדוקים חסרי הקשר

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

משפט מייהיל-נרוד

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